改进型离散余弦变换的快速算法毕业论文.doc

1 引言数字信号处理（digital signal processing，DSP）是利用计算机或专用处理设备，用数值计算的方法对信号进行采集，交换，综合，估值与识别等加工处理，借以达到提取信息和便于应用的目的数字信号处理系统具有灵活，精确，抗干扰强，设备尺寸小，造价低，速度快等突出优点[1，2]，这些都是模拟信号处理系统无法比拟的 数字信号处理的起源可追溯到17世纪，当时已提出了有限差分，数值积分和数值插值得方法自20世纪60年代以来，随着计算机和信息学科的飞速发展，数字信号处理技术应运而生并迅速发展，现已形成一门独立的学科体系[3]数字信号处理就是研究用数字的方法，正确快速地处理信号，提取各类信息的一门科学在国际上，一般把1965年快速傅里叶变换（FFT ,Fast Fourier Transform）的问世，作为数字信号信号处理这一新兴学科的开端[3，4]目前，伴随着通信技术、电子技术计算机的飞速发展，数字信号处理的理论也在不断地丰富的丰富和完善，各种新算法、新理论正在不断地推出在这近四十多年的发展中，数字信号处理自身已基本形成一套较完整的理论体系[4]傅立叶变换在数字信号处理中扮演着重要的角色[4]。

在数字信号处理中,最重要也是最基本的表达信号的两个变量是时间和频率通过傅立叶变换或反变换,可以把时间域信号转到频率域或把频率域信号转到时间域,但又由于我们所要测量的信号大都是连续周期信号，不能直接在计算机上计算它的傅里叶变换，而DFT及其快速算FFT是一种时域和频域都离散化的变换，能在计算机上实现信号的频谱分析及其他方面的处理，因此DFT在数字信号处理和数字图像处理中得到了广泛的应用，它建立了离散时域与离散频域之间的关系[5]如果信号或图像处理直接在时域或空域上处理，计算就会随着离散采样点数的增加而激剧增加使得计算机计算量大，费时，难以达到实时的要求[6]因此，一般采用DFT方法，将输入的数字信号首先进行DFT变换，把时域中的卷积和相关运算简化为在频域上的相成处理，然后进行DFT反变换，恢复为时域信号这样大大减少计算量，提高处理速度最重要的是DFT有多种快速算法，统称为快速傅立叶变换,从而使信号的实时处理和设备的简化得以实现所以说，DFT不仅在理论上有重要意义，而且在各种信号的处理中也起核心作用离散傅立叶变换（DFT）是复数域的运算，尽管借助于FFT可以提高运算速度，但在实际应用，特别是实时处理中带来了不便。

由于实偶函数的傅立叶变换只含有实的余弦项，因此构造了一种实域的变换---离散余弦变换(DCT)离散余弦变换（DCT）是N Ahmed等人在1974年提出的正交变换方法[5]它是一种正交变换，它类似于离散傅里叶变换(DFT)，但是只使用实数离散余弦变换相当于一个长度大概是它两倍的离散傅里叶变换，这个离散傅里叶变换是对一个实偶函数进行的它的思想是将一个实函数对称延拓成一个实偶函数，实偶函数的傅立叶变换也必然是实偶函数，连续函数和离散函数（CFT）都是基于这一原理在20世纪80年代至90年代初期，人们对DCT快速算法的研究较多，并且取得了巨大的成功早在1977年，Chen⋯根据变换矩阵具有对称性，利用稀疏矩阵分解法第一次提出DCT的快速算法l984年B．G．Led 提出了一种使用余割因子的DCT矩阵分解方法，得到Cooley-Tukey式的简单结构，受到广泛重视后来Duhamel将DCT看成是一种基于循环卷积的算法，并证明对于一维的8点DCT，其乘法的理论下限值是l1次，C．Loeffler 具体实现了这种ll步乘法的算法从此以后，一维DCT快速算法的研究进展缓慢2000年Trac．D．Trar提出了一种DCT的近似快速算法，在算法中也没有用到乘法，但使用了移位运算。

在国内，赵耀等人也提出了一种“基于矩阵分解的DCT-I算法”[16] ，该方法也用到了l2次乘法离散余弦变换的提出虽然比快速傅立叶变换(FFT)晚，但其性能更接近于理想的KLT变换，并且由于KLT 到目前为止没有发现有效的快速速算法，所以DCT在信号处理中得到了广泛应用[6]离散余弦变换(DCT)域是数字信号处理技术中最常用的线性变换之一，和离散傅里叶变换一样，也存在着快速算法它的快速算法也是在继承完善DFT的基础上不断进步的但由于离散余弦变换(DCT)的变换核为实数的余弦函数，因此它的计算速度比变换核为复数指数的DFT要快所以高效快速的离散余弦变换(DCT)得到了广泛应用，并且不断激发人们对其快速算法的研究[7，8，9]基于以上研究现状，如何改进DCT的快速算法是本文的研究重点本文首先系统阐述了离散傅立叶变换(DFT)的基础理论及其快速算法FFT,然后详细论述了离散余弦变换的基本概念及其二维DCT快速算法的基本理论和实现方法，重点研究了一种改进的离散余弦变换的快速算法，并推导了算法的进行过程本文着眼于如何改进离散余弦变换的快速算法，分析了一维8点DCT快速算法的原理和二维8乘8DCT快速算法的理论，推导出了改进的DCT快速算法的基本思路，并将此算法与其它算法做了比较，最后举出具体实例，演绎了算法的进行过程，结果表明该算法的运算量明显减少。

2 离散傅立叶变换(DFT)及其快速算法(FFT)DFT是先将信号在时域离散化，求其连续傅里叶变换后，再在频域离散化的结果它通常用于频谱分析和滤波,它提供了使用计算机来分析信号和系统的一种方法，尤其是DFT的快速算FFT，在许多科学技术领域中得到了广泛的应用，并推动了数字信号处理技术的迅速发展[10]2.1 离散傅立叶变换(DFT)的定义和DFT性质在计算机上实现信号的频谱分析及其他方面的处理工作时，对信号的要求是：在时域和频域都是离散的，且都应是有限长离散傅立叶变换不是一个新的傅立叶变换形式，它实际上来自于DFS，只不过仅在时域，频域各取一个周期，其实质是有限长序列傅立叶变换的有限点离散采样，从而开辟了频域离散化的道路，使数字信号处理可以在频域采用数字运算的方法进行，大大增加了数字信号处理的灵活性1） 正变换： (2.1.1)（2） 反变换： (2.1.2)离散傅立叶变换适用于有限长序列，和只有N个 值，但隐含周期性是Z变换在单位圆上等距离的抽样值，，是序列频谱的采样值， 假定与是长度为N的有限长序列，其各自的离散傅立叶变换分别为 ， 。

则DFT具有以下性质：(1) 线性 ，，为任意常数 (2) 循环移位    有限长序列的循环移位定义为：    表示的周期延拓序列的移位：    表示对移位的周期序列取主值序列所以仍然是一个长度为N的有限长序列实际上可看作序列排列在一个N等分圆周上，并向左旋转m位 序列循环移位后的DFT为：实际上，利用的周期性，将代入DFT定义式，同样很容易证明 同样，对于频域有限长序列X(k)的循环移位，有如下反变换特性：(3) 循环卷积若 则 或 同样，若 则 所以，离散时间序列(或离散傅立叶变换)的循环卷积与离散傅立叶变换(或离散时间序列)的乘积相对应这就说明循环卷积的运算可利用离散傅立叶变换转换成乘积实现4) 有限长序列的线性卷积与循环卷积(循环卷积的应用)有限长序列的线性卷积等于循环卷积，而不产生混淆的必要条件是延拓周期 L≥N+M-1，其中N、M为两个有限长序列的长度 (5) 奇偶对称特性时域序列奇对称时，其也奇对称，即若 ，则时域序列偶对称时，其也偶对称，即若 ，则6) 虚实特性若 ，则 当为纯实数序列时，＝→共轭偶对称 当为纯虚数序列时，＝→共轭奇对称。

2.2 快速傅立叶变换定义和算法思路自从1965年土基和库利在《计算机数学》(Math.Computation,Vol.19,1965)杂志上发表了著名的《机器计算傅立叶变换的一种算法》论文后，桑德--图基等快速算法相继出现，又经人们改进，很快形成一套高效的运算方法，这就是现在的快速傅立叶变换，简称FFT(Fast Fourier Transform)这种算法使DFT的运算效率提高1~2个数量级，为数字信号处理技术应用于各种信号的实时处理创造了良好的条件，大大推动了数字信号处理的发展[11]快速傅立叶变换(FFT)是离散傅立叶变换DFT (Discrete Fourier Transform)的快速算法，它就是利用的特性，逐步地将N点序列分解成较短的序列，计算短序列的DFT，然后组合成原序列的DFT，使运算量显著减少FFT是DFT的快速计算方法，DFT是连续傅立叶变换的离散形式 =，=0，1，…N-1 (2.2.1) 式中， =，称为蝶形因子此式实际上就是N点的DFT由(2.2.1)式可以看出，计算所有的的运算量很大。

FFT算法利用了蝶形因子内在的性质，从而加快了运算的速度的以下三种性质在FFT运算中得到了应用：性质 1： 的周期性 =性质 2： 的对称性 =性质 3： 的可约性 =，=FFT算法将长序列的DFT分解为短序列的DFTN点的DFT先分解为2个点的DFT，每个点的DFT又分解为点的DFT，等等最小变换的点数即所谓的“基数(Radix)"，因此，基数为2的算法的最小变换(或称蝶形)是2点DFT一般的，对N点FFT，对应于N个输入样值，有N个频域样值与之对应 一般而言 ，FFT算法可以分为时间抽取(DIT)FFT和频率抽取(DIF)FFT两大类2.2.1 时间抽取(DIT)FFT时间抽取算法是将N点的输入序列按照偶数和奇数分解为偶序列和奇序列两个序列： 偶序列：x(0)， x(2)， x(4)，…，x(N-2)奇序列：x(1)， x(3) ，x(5)，…，x(N-1)因此，的N点FFT可以表示 =+ (2.2.1.1)因为 ===所以 =+，令，则有 =+ (2.2.1.2)由于和的周期为，因此 k=0，1，…，。

由 =- 可知 =- (2.2.1.3)用（2.2.1.2）,(2.2.1.3)两式分别用来计算和的以同样的方式进一步抽取，就可以得到N/4的DFT，重复这个抽取过程，就可以使N点的DFT用一组2点的DFT来计算在基数为2的FFT中，设N=，则总共有M级运算，每级中有N/2个2点FFT蝶形运算，因此，N点FFT总共有个蝶形运算 图2.1 时间抽取算法碟形运算图基2DIT的蝶形如图2.1所示设蝶形的输入分别为A和B ，输出分别为C和D，则有 ，图2.2 N=8点DIT-FFT算法流图2.2.2 频率抽取(DIF)FFT频率抽取FFT算法是在频域里把序列分解为奇、偶的形式来进行计算，频率抽取FFT算法首先将输入序列按照自然顺序分为前半部分和后半部分：偶序列：x(0)，x(2)，x(4)，…，x()奇序列：x(1)，x(3)，x(5)，…，x()因此，的N点FFT可以表示为：=+= (2.2.1.4)k为偶数时： =，k=0，1，…()k为奇数时：= ，k=0，1，…()因为 令　=，则有： ＝＝以同样的方式，就可以得到N/4点的DFT，重复这个过程， N点的DFT用一组2点的DF。