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

《改进型离散余弦变换的快速算法 毕业论文.doc》由会员分享，可在线阅读，更多相关《改进型离散余弦变换的快速算法 毕业论文.doc（29页珍藏版）》请在三一文库上搜索。

1、1 引言数字信号处理（digital signal processing，DSP）是利用计算机或专用处理设备，用数值计算的方法对信号进行采集，交换，综合，估值与识别等加工处理，借以达到提取信息和便于应用的目的。数字信号处理系统具有灵活，精确，抗干扰强，设备尺寸小，造价低，速度快等突出优点1，2，这些都是模拟信号处理系统无法比拟的。 数字信号处理的起源可追溯到17世纪，当时已提出了有限差分，数值积分和数值插值得方法。自20世纪60年代以来，随着计算机和信息学科的飞速发展，数字信号处理技术应运而生并迅速发展，现已形成一门独立的学科体系3。数字信号处理就是研究用数字的方法，正确快速地处理信号，提取各

2、类信息的一门科学。在国际上，一般把1965年快速傅里叶变换（FFT ,Fast Fourier Transform）的问世，作为数字信号信号处理这一新兴学科的开端3，4。目前，伴随着通信技术、电子技术计算机的飞速发展，数字信号处理的理论也在不断地丰富的丰富和完善，各种新算法、新理论正在不断地推出。在这近四十多年的发展中，数字信号处理自身已基本形成一套较完整的理论体系4。傅立叶变换在数字信号处理中扮演着重要的角色4。在数字信号处理中,最重要也是最基本的表达信号的两个变量是时间和频率。通过傅立叶变换或反变换,可以把时间域信号转到频率域或把频率域信号转到时间域,但又由于我们所要测量的信号大都是连续周

3、期信号，不能直接在计算机上计算它的傅里叶变换，而DFT及其快速算FFT是一种时域和频域都离散化的变换，能在计算机上实现信号的频谱分析及其他方面的处理，因此DFT在数字信号处理和数字图像处理中得到了广泛的应用，它建立了离散时域与离散频域之间的关系5。如果信号或图像处理直接在时域或空域上处理，计算就会随着离散采样点数的增加而激剧增加。使得计算机计算量大，费时，难以达到实时的要求6。因此，一般采用DFT方法，将输入的数字信号首先进行DFT变换，把时域中的卷积和相关运算简化为在频域上的相成处理，然后进行DFT反变换，恢复为时域信号。这样大大减少计算量，提高处理速度。最重要的是DFT有多种快速算法，统称

4、为快速傅立叶变换,从而使信号的实时处理和设备的简化得以实现。所以说，DFT不仅在理论上有重要意义，而且在各种信号的处理中也起核心作用。离散傅立叶变换（DFT）是复数域的运算，尽管借助于FFT可以提高运算速度，但在实际应用，特别是实时处理中带来了不便。由于实偶函数的傅立叶变换只含有实的余弦项，因此构造了一种实域的变换-离散余弦变换(DCT)。离散余弦变换（DCT）是N Ahmed等人在1974年提出的正交变换方法5。它是一种正交变换，它类似于离散傅里叶变换(DFT)，但是只使用实数。离散余弦变换相当于一个长度大概是它两倍的离散傅里叶变换，这个离散傅里叶变换是对一个实偶函数进行的。它的思想是将一个

5、实函数对称延拓成一个实偶函数，实偶函数的傅立叶变换也必然是实偶函数，连续函数和离散函数（CFT）都是基于这一原理。在20世纪80年代至90年代初期，人们对DCT快速算法的研究较多，并且取得了巨大的成功。早在1977年，Chen根据变换矩阵具有对称性，利用稀疏矩阵分解法第一次提出DCT的快速算法。l984年BGLed 提出了一种使用余割因子的DCT矩阵分解方法，得到Cooley-Tukey式的简单结构，受到广泛重视。后来Duhamel将DCT看成是一种基于循环卷积的算法，并证明。对于一维的8点DCT，其乘法的理论下限值是l1次，CLoeffler 具体实现了这种ll步乘法的算法。从此以后，一维D

6、CT快速算法的研究进展缓慢。2000年TracDTrar提出了一种DCT的近似快速算法，在算法中也没有用到乘法，但使用了移位运算。在国内，赵耀等人也提出了一种“基于矩阵分解的DCT-I算法”16 ，该方法也用到了l2次乘法。离散余弦变换的提出虽然比快速傅立叶变换(FFT)晚，但其性能更接近于理想的KLT变换，并且由于KLT 到目前为止没有发现有效的快速速算法，所以DCT在信号处理中得到了广泛应用6。离散余弦变换(DCT)域是数字信号处理技术中最常用的线性变换之一，和离散傅里叶变换一样，也存在着快速算法。它的快速算法也是在继承完善DFT的基础上不断进步的。但由于离散余弦变换(DCT)的变换核为实

7、数的余弦函数，因此它的计算速度比变换核为复数指数的DFT要快。所以高效快速的离散余弦变换(DCT)得到了广泛应用，并且不断激发人们对其快速算法的研究7，8，9。基于以上研究现状，如何改进DCT的快速算法是本文的研究重点。本文首先系统阐述了离散傅立叶变换(DFT)的基础理论及其快速算法FFT,然后详细论述了离散余弦变换的基本概念及其二维DCT快速算法的基本理论和实现方法，重点研究了一种改进的离散余弦变换的快速算法，并推导了算法的进行过程。本文着眼于如何改进离散余弦变换的快速算法，分析了一维8点DCT快速算法的原理和二维8乘8DCT快速算法的理论，推导出了改进的DCT快速算法的基本思路，并将此算法

8、与其它算法做了比较，最后举出具体实例，演绎了算法的进行过程，结果表明该算法的运算量明显减少。2 离散傅立叶变换(DFT)及其快速算法(FFT)DFT是先将信号在时域离散化，求其连续傅里叶变换后，再在频域离散化的结果。它通常用于频谱分析和滤波,它提供了使用计算机来分析信号和系统的一种方法，尤其是DFT的快速算FFT，在许多科学技术领域中得到了广泛的应用，并推动了数字信号处理技术的迅速发展10。2.1 离散傅立叶变换(DFT)的定义和DFT性质在计算机上实现信号的频谱分析及其他方面的处理工作时，对信号的要求是：在时域和频域都是离散的，且都应是有限长。离散傅立叶变换不是一个新的傅立叶变换形式，它实际

9、上来自于DFS，只不过仅在时域，频域各取一个周期，其实质是有限长序列傅立叶变换的有限点离散采样，从而开辟了频域离散化的道路，使数字信号处理可以在频域采用数字运算的方法进行，大大增加了数字信号处理的灵活性。（1） 正变换： (2.1.1)（2） 反变换： (2.1.2)离散傅立叶变换适用于有限长序列，和只有N个 值，但隐含周期性。是Z变换在单位圆上等距离的抽样值，是序列频谱的采样值，。 假定与是长度为N的有限长序列，其各自的离散傅立叶变换分别为 ， 。则DFT具有以下性质：(1) 线性 ，为任意常数 (2) 循环移位 有限长序列的循环移位定义为： 表示的周期延拓序列的移位： 表示对移位的周期序列

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

11、为两个有限长序列的长度。 (5) 奇偶对称特性时域序列奇对称时，其也奇对称，即若 ，则。时域序列偶对称时，其也偶对称，即若 ，则。(6) 虚实特性若 ，则 。当为纯实数序列时，共轭偶对称。 当为纯虚数序列时，共轭奇对称。2.2 快速傅立叶变换定义和算法思路自从1965年土基和库利在计算机数学(Math.Computation,Vol.19,1965)杂志上发表了著名的机器计算傅立叶变换的一种算法论文后，桑德-图基等快速算法相继出现，又经人们改进，很快形成一套高效的运算方法，这就是现在的快速傅立叶变换，简称FFT(Fast Fourier Transform)。这种算法使DFT的运算效率提高12

12、个数量级，为数字信号处理技术应用于各种信号的实时处理创造了良好的条件，大大推动了数字信号处理的发展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算法利用了蝶形因子内在的性质，从而加快了运算的速

13、度。的以下三种性质在FFT运算中得到了应用：性质 1： 的周期性 =性质 2： 的对称性 =性质 3： 的可约性 =，=FFT算法将长序列的DFT分解为短序列的DFT。N点的DFT先分解为2个点的DFT，每个点的DFT又分解为点的DFT，等等。最小变换的点数即所谓的“基数(Radix)，因此，基数为2的算法的最小变换(或称蝶形)是2点DFT。一般的，对N点FFT，对应于N个输入样值，有N个频域样值与之对应。 一般而言 ，FFT算法可以分为时间抽取(DIT)FFT和频率抽取(DIF)FFT两大类。2.2.1 时间抽取(DIT)FFT时间抽取算法是将N点的输入序列按照偶数和奇数分解为偶序列和奇序列

14、两个序列： 偶序列：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总共有个蝶形运算。 图

15、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，重

16、复这个过程， N点的DFT用一组2点的DFT来计算。设N=，则共有M级运算。DIF的基2蝶形运算如图3所示。图2.3 基2的DIF-FFT蝶形运算图2.4 8点DIF-FFT的信号流程图设蝶形的输入分别为A和B，输出分别为C和D， 则有 ，则一个8点DIF-FFT的信号流程图如图2.4。从图2.1和图2.3可以看出，DIT和DIF两种FFT算法的区别是旋转因子出现的位置不同，DIT中在输入端而DIF中在输出端。除此之外，两种方法是一样的。3 离散余弦变换的基本理论离散余弦变换（DCT for Discrete Cosine Transform）是一种正交变换，它类似于离散傅立叶变换 (DFT)

17、,但它只使用实数。离散余弦变换相当于一个长度大概是它两倍的离散傅里叶变换，这个离散傅里叶变换是对一个实偶函数进行的(因为一个实偶函数的傅里叶变换仍然是一个实偶函数)，在有些变形里面需要将输入或者输出的位置移动半个单位(DCT有8种标准类型，其中4种是常见的)。最常用的一种离散余弦变换的类型是下面给出的第二种类型，通常我们所说的离散余弦变换指的就是这种。它的逆，也就是下面给出的第三种类型，通常相应的被称为反离散余弦变换，逆离散余弦变换或者IDCT。有两个相关的变换，一个是离散正弦变换 (DST for Discrete Sine Transform),它相当于一个长度大概是它两倍的实奇函数的离散

18、傅立叶变换；另一个是改进的离散余弦变换 (MDCT for Modified Discrete Cosine Transform),它相当于对交叠的数据进行离散余弦变换13。3.1 一维离散余弦变换的各种定义余弦变换是傅里叶变换的一种特殊情况。在傅里叶级数展开式中，如果被展开的函数是实偶函数，那么，其傅里叶级数中只包含余弦项，再将其离散化由此可导出余弦变换，或称之为离散余弦变换（DCT）。下图(3.1),(3.2)分别给出偶对称和奇对称的。 图3.1 偶对称的 图3.2 奇对称的设一维离散函数f(x)，x=0，1，N-1，把f(x)扩展成为偶函数的方法有两种，以N=4为例，可得出如图3.1和图

19、3.2所示的两种情况。图3.1称偶对称，图3.2称奇对称，从而有偶离散余弦变换（EDCT）和奇离散余弦变换（ODCT）。由图1和2看出，对于偶对称扩展，对称轴在x=处。= (3.1.1)采样点数增到2N。对于奇对称扩展，对称轴在x=0处。= (3.1.2)采样点数增到2N1。由离散傅里叶变换定义出发，对公式（3.1.1）作傅里叶变换，以表示，则得= (3.1.3)式中，当 u=0, =当当 ，且=2考虑正交变换公式与逆变换公式的对称性，令 (3.1.4) 式中 (3.1.5) (3.1.6) (3.1.7) 定义式（3.1.4）和式（3.1.5）为离散偶余弦正变换公式；式（3.1.6）和式（3

20、.1.7）为离散偶余弦变换核公式。离散偶余弦逆变换公式为C(0)+C(u) (3.1.8) x = 0，1，N-1将公式（3.1.4）和公式（3.1.5）合并、化简，可得到一维离散偶余弦正变换公式即C(u)=E(u) 式中当u=0时，E(u)= ； 当时， 总上述可归纳：若给定序列，则其离散有限傅里叶变换为： （3.1.9）当时，为实数，则其离散余弦变换定义为 （3.1.10） （3.1.11）显然，其变换的核函数 （3.1.12） 是实数，式中系数 （3.1.13）这样，若是实数，那么它的DCT变换也是实数。对傅里叶变换，若是实数，其DFT一般为复数。由此可以看出，DCT避免了复数运算。将（

21、3.1.9）式写成矩阵，有 （3.1.14）式中，都是的向量，是的变换矩阵，其元素由（3.1.12）式给出。当时，有 （3.1.13） 可以证明，的行、列向量均有如下的正交关系：可见变换矩阵是归一化的正交阵，DCT是正交变换，由此立即得到DCT的反变换关系： （3.1.14）即 （3.1.15）当k 为其他值时,为了实现实数域运算,对其进行改造,将信号以原点为中心对称增加一倍,从N个扩展到 2N个，并对相位也进行修改,除了N 改2N 外,还要加上0+ 与0- 的相位,他们分别为与，则式（3.1.1）应该为式（3.1.2），即： 由于信号的安排为，并且，故式（3.1.1）展开相加之后，所有项都抵

22、消，而可化简为： (3.1.16)（3.1.17）这就是离散余弦变换的关系式。 从形式上来看，离散余弦变换一个线性的可逆的函数: (其中R是实数集, 或者等价的说一个的方阵。离散余弦变换有几种变形的形式，它们都是根据下面的某一个公式把 n 个实数变换到另外n个实数的操作。下面给出离散余弦变换的四种类型：DCT-I =(+)+ DCT-II =DCT-III =+DCT-IV =3.2 二维离散余弦变换的定义及反变换DCT变换被认为是一种准最佳变换，具有压缩比高、误码率小，信息集中能力和计算复杂性综合效果好等优点10。一个MN矩阵A 的二维DCT定义如下： （3.2.1）其中： 式中， F( u

23、 ,v )为空间域图像在( x, y )处的灰度值，x ，y=0，1，2， ，N-1， f(x ,y)为变换系数矩阵，u ,v =0，1，2， ，N-1，N为数字图像的宽度和高度。二维离散余弦反变换公式如下： （3.2.2） 其中：为空间域采样值；为频率域采样值。通常，数字图像用象素方阵表示，即，在这种情况下，二维离散余弦的正反变换可简化为： （3.2.3） （3.2.4）其中：4 离散余弦变换（DCT）的快速算法 离散余弦变换也象DFT一样具有快速实现的算法。对于n个点的DCT变换，其算法复杂度为O()。4.1 一维离散余弦变换的快速算法 DCT首先由NAhmad等人于1974年提出的13，

24、设数据序列x(n)，n=0，1 ，N-1，则X(n)的DCT定义为： ,k=0,1, ,N-1 (4.1.1)在这里，Y(k)是第K个DCT系数。若写成矩阵形式，则有：其中表示DCT变换矩阵，离散余弦逆变换（IDCT）定义为： (4.1.2)4.2 二维88快速DCT的基本原理及其实现方法 离散余弦变换（Discrete Cosine Transform ,DCT）是一种最接近统计最优变换K-L变换的正交变换，已有的各种成熟的压缩标准如JPEG,MPEG1/2/4,H.26X以及HDTV等都无一例外地采用基于DCT/IDCT的压缩编码。但通常的DCT运算量比较大，为了降低DCT算法的运算量，提

25、高运算速度，人们提出了多种快速计算DCT的方法。例如在2D-DCT快速算法中，Duhame和Guillemot提出了一种直接多项式变换法；Vetterli提出了一种间接算法，用附加一些旋转方法将2D-DCT映射为2D-DFT,再用多项式计算2D-DFT；Wu和Paoloni提出了一种矩阵分解法，利用Kronecker积将N乘N的DCT转化为N的平方点的一维变换，然后对此一维变换矩阵进行分解，减少矩阵中所包含的乘法次数等等。后来提出的快速算法几乎都是在上面提出的集中快速算法的基础上的改进，以及针对一些特殊情况的快速算法。在DCT的快速算法中，Loeffer,Ligtenberg和Moschytz

26、在1989年提出的算法最有代表性。在图像和视频压缩中，二维8乘8快速DCT变换是使用最普遍的2D-DCT快速算法11。在此主要介绍二维88快速DCT的基本原理及其实现方法。由于二维8乘8快速DCT的算法是通过计算行方向的一维DCT和列方向的一维DCT来实现的，因此首先介绍一维8点快速DCT算法。4.2.1 一维8点快速算法DCT在20世纪80年代，DCT算法受到了人们的关注，人们提出了多种针对一维8点DCT的算法。下表4.1给出七种不同的快速算法的比较，这些算法都是针对8点的一维DCT，各算法以其作者进行标志。表4.1 各种快速DCT快速算法的比较作者ChenWang LeeVetterliS

27、uehiroHouLoeffler乘法次数16131212121211加法次数26292929292929若把DCT看做一种循环旋转运算，则对于8点的一维DCT算法，理论上最少需要11次乘法和29次加法。Loeffler的算法是达到这一极限的算法。直接计算DCT需要64次乘法和56次加法，而用Loeffler的快速算法来计算以维DCT只需要11次乘法和29次加法，可见Loeffler 快速算法在很大程度上减少了计算量。Loeffler快速算法是一种极具有代表性的一维8点快速DCT算法，下面详细介绍Loeffler快速算法。（1） Loeffler快速算法的基本原理。快速DCT算法把一维DCT算

28、法分为4级，由于各级之间的输入输出具有依存关系，4级操作必须串进行，而各级内部的运算可采用并联方式来进行处理。它有三种运算因子：蝶形因子，旋转因子和倍乘因子。下图是Lo 图4.1 Loeffler算法流程图 (a)蝶形因子 （b）旋转因子 (c)倍乘因子图4.2 Loeffler快速DCT算法中的三种因子上图中表示Loeffler快速DCT算法中的三种，其中,或表示输入，或表示输出。几种运算因子之间的关系介绍如下。蝶形因子的输入输出关系是: 由上式可见，完成一个蝶形因子需要2次加法运算。旋转因子的输入输出关系是：根据上面的公式，直接计算旋转因子需要4次乘法和2次加法。为了减少运算量，对上面描述

29、旋转因子输入输出关系的等式做变换，变形为: 采用上面变形后的等式，只需要3次乘法和3次加法就可以完成一个旋转因子的运算。等式变换后使旋转因子的计算量减少。 倍乘因子的输入输出关系是： 倍乘因子只需要一次乘法。以上分析可得出结论：计算蝶形因子需要2次加法操作，计算旋转因子需要3次乘法因子和3次加法操作，计算倍乘因子需要1次乘法操作。而 Loeffler的快速算法流程图中共存在10个蝶形因子，3个旋转因子和2个倍乘因子，因此，总的乘法次数是33+2=11，总的加法次数是102+33=29。(2) Loeffler 快速算法DCT算法的计算 前面介绍了Loeffler快速算算法的运算流程，并且对其在

30、运算过程中所需要的乘法和加法操作的次数，也就是运算量进行了分析。下面来推导一维DCT快速算法的8个系数。进一步验证Loeffler快速算法的正确性。按DCT系数y(0),y(4),y(2)y(6),y(7),y(3),y(5),y(1)的顺序来排列。偶系数y(0) ,y(4),y(2).y(6), 按照位序增序排序，而奇系数 y(7),y(3),y(5),y(1) 按倒位序降序排列。按这种顺序将每个DCT系数的表达式化为流程图中三种因子的组合。给出一维8点DCT的公式为： F（u）=式中 对于一维DCT的系数F(0),F(4),根据一维8点DCT的公式，有F(0)= =F(4)= =+-+y(

31、0)和y(4)都可以表示为3级蝶形因子的级联。同理，其余的6个系数也可以得出：F(2)= =-+-F(6)= =-F(7)= =+-+-+-+F(3)= =-+-+ F(5)= =+-+ F(1)= =+-+ -+-+由上面的DCT系数的表示公式可以看出，y(0)和y(4)都可以表示为3级蝶形因子的级联；y(2)和y(6)表示为2级蝶形因子与一级旋转因子的级联；y(7)和y(1) 表示为1级蝶形运算与1级旋转运算级联后，再级联2级蝶形运算；y(5)和y(3)表示为1级蝶形，1级旋转，1级蝶形和一级倍乘运算的依次顺序级联。综上所述，一维8点DCT的8个系数利用一维8点DCT的公式来计算，其结果可

32、以转化为三种因子的级联形式，从而证明一维8点DCT算法的流程图是正确的。4.2.2 二维 8乘8 DCT 快速算法为了减弱或消除图像数据的空间相关性，可以运用二维DCT变换，将图像 f( x ,y )从空间域转换到DCT变换域。二维8乘8快速DCT算法及其逆变换IDCT的计算公式定义如下：F（u，v）=C（u）C（v）F(x ,y)= F( u ,v ) 式中 f( x ,y )表示像素的值，F( u ,v )表示DCT系数。对于二维DCT的计算方法很多或进行行-列方法运算。直接方法是二维的数据；而行-列方法是根据DCT/IDCT的正交可分解性，通过对输入矩阵先行行方向的一维DCT,再作列方向

33、的一维 DCT 。即将 N乘N 数据按行（或列）方向进行N 个一维DCT计算，产生中间数据矩阵再按列（行）方向进行N 个一维DCT计算，最后得到二维DCT的结果。 下图（4.3）所描述的是二维离散余弦变换（2D-DCT）和二维离散余弦逆变（2D-IDCT）的处理流程。在图中有两个一维DCT/IDCT 的处理模块和一个转置RAM模块。输入数据首先要经过串-并转换模块，把串行输入的数据转换为并行的形式；再经过第一个DCT/IDCT处理模块，按行方向进行一维DCT/IDCT；然后产生的中间数据输入到转置RAM中；将转置后的数据输入到第二个DCT/IDCT处理模块，按列方向进行一维DCT/IDCT；最

34、后数据再经过并-串转换模块，把并行的数据变为串行的数据。 图4.3 二维DCT/IDCT处理流程图上图描述的二维DCT快速算法的处理流程中有三种模块：DCT/IDCT处理模块，转置RAM模块，串-并（并-串）转换模块。串-并模块是实现数据的串-并转换模块的功能与串-并转换模块的功能正好相反，即把没收到的一组8个并行数据转换成8个串行数据输出。转置RAM模块对两个一维DCT处理模块之间的中间数据进行转置处理。DCT/IDCT模块用来对输入的数据做DCT/IDCT处理。针对二维8乘8快速DCT的计算，DCT模块完成一维8点DCT计算，采用Loeffler的一维快速DCT算法。5 一种新的改进型离散

35、余弦快速算法改进型的离散余弦变换（Modified discrete cosine transform）作为良好的时频分析工具，在信号处理的实时性上显得至关重要，为此需要研究其快速算法。下面论述基于快速DCT变换的MDCT快速算法的原理。5.1 算法原理 改进型离散余弦变换（MDCT ：Modified Discrete Cosine Transform）的定义为： （5.1.1）式中，。式（5.1.1）与DCT相比多了一个常数为此首先简化该式，分离余弦函数中包含的信息。利用三角公式中的余弦和积关系：2cosAcosB=cos(A+B)+cos(A-B)。令 对大括号进一步调整 其中（推导见附

36、录1）所以式（5.1.1）可改写为如下形式： （5.1.2）其中， 由此，对X(k)的计算转化为系数Z(k)的计算，明显地,Z(k)具有对称性，Z(n-1-k)=Z(k)，所以只需计算一半系数，即 对Z(k)分离其奇偶序号项对后半部分进一步解析，令（推导见附录2）其中 再令 于是Z(k)可重写为： （5.1.3）至此，本文将N点的转化为两个点的的计算，其递推公式（5.1.3），这样的递推形式与传统将N点DCT分解为一个点DCT和一个点DST的线性组合不同，其子变换仍为的形式，便于编程；这与FFT相似，但所有运算皆为实数运算。5.2 举例以N=8为例，具体演绎算法的进行过程。依据下面的过程可以类

37、推N=(n为大于3的自然数)。（1） 预处理z(0)=x(0)-x(3)z(1)=x(1)-x(2)-x(4) z(2)=x(2)-x(1)-x(5)z(3)=x(3)-x(0)-x(6) z(4)=x(4)-x(7)z(5)=x(5)z(6)=x(6) z(7)=x(7)图5.1 奇偶分序数组示意图（2） 构造奇偶分序组（见图5.1）（3） 递推（见图5.2） 图5.2 递推示意图（4） 后处理 （5） 结论 除预处理操作复杂外，本算法的结构简单，递推中半蝶形运算的所有操作皆为实数，再加上系数具有对称性，因此其该乘法加法次数都较基于FFT的算法少。由上述分析可知，其实数加法和乘法次数分别为和

38、，与文献 14，15相比，具体数据见表5.1。表5.1算法实数操作比较N本文文献14文献15加乘加乘加乘82416564824481664401601286411232160964163201602566438422410247683845761288965122432179289612802562048115256324096204828165124608256012800921646086144 由表5.1可知基于DCT变换的快速算法的运算量明显减少。并将此算法的结果与其它算法的结果作了比较，结果表明：算法速度提高了，虽然算法的结果仍是正确的。6 结束语DCT的快速算法有多种，基于多项式变

39、换的DCT快速算法，基于查表的无乘法DCT快速算法，利用循环卷积实现的DCT快速算法等，本文以离散余弦变换的快速算法的基本理论为基础，提出了改进型离散余弦变换的快速算法，并用具体实例进行验证，结果表明此算法可行，说明此算法在一定程度上减少了运算量，尤其是减少了将近三分之一的乘法的运算次数。但是，该算法过程中的预处理操作比较复杂，所以在运算简便方面不是太理想。由于改进型的DCT是良好的时频分析工具，其快速算法也显得至关重要。在以后的时间里，我将继续研究，完善基于快速DCT变换的MDCT快速算法。参考文献1 胡广书， 数字信号处理导论M. 北京: 清华大学出版社, 2005.2 丁玉美, 高西全.

40、 数字信号处理M. 西安: 西安电子科技大学出版社,1994.3 奥本海姆著. 刘树棠，黄建国译. 离散时间信号处理M. 西安: 西安交通大学出版社 2001.4 朱秀昌, 刘峰, 胡栋. 数字图像处理与图像通信M. 北京: 北京邮电大学出版社,2002.5 Kenneth R.Castleman 著, 朱志刚, 石定机等译. 数字图像处理M. 北京: 电子工业出版社,2002.6 李在铭. 数字图像处理压缩与识别技术M. 成都: 电子科技大学出版社, 2000.7 谷获隆嗣（日本）. 快速算法与并行信号处理M. 北京: 科学出版社, 2003.8 K.R. Rao and P. Yip, 离

41、散余弦变换 : 算法、优点和应用 (Discrete Cosine Transform: Algorithms, Advantages, Applications) (Academic Press, Boston, 1990). 9 Syed Ali Khayam , Department of Electrical & Computer Engineeri . Michigan State University . The Discrete Cosine Transform(DCT):Theory and , Application March 10th 2003.10 Gilbert Strang Massachusetters Institute of Technology . Discrete Cosine Transform(DCT).11 何小敏, 王正勇. 数字图像通信及其应用M. 成都: 四川大学出版社, 2006.12 陈禾, 毛志刚, 叶以正. DCT快速算法及其VLSI实现J. 哈尔滨工业大学学报, 1998.13 徐盛, 胡剑凌, 陈 健. 一种新的MDCT快速算法J. 上海交通大学，200030, 2000. 12.14 杜相文, 陈贺毒, 赵岩. 基于查表的无乘法DCT快速算法J.吉林大学南岭校区通信工程学院测控技术与仪器系，长春13002