基于多项式变换的DCT快速算法 毕业论文doc.doc

1 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 不仅在理论上有重要意 2 义,而且在各种信号的处理中也起核心作用。离散傅立叶变换( DFT )是复数域的运算,尽管借助于 FFT 可以提高运算速度,但在实际应用,特别是实时处理中带来了不便。由于实偶函数的傅立叶变换只含有实的余弦项,因此构造了一种实域的变换---离散余弦变换(DCT )。离散余弦变换( DCT )是 N Ahmed 等人在 1974 年提出的正交变换方法[5]。它是一种正交变换,它类似于离散傅里叶变换(DFT) ,但是只使用实数。离散余弦变换相当于一个长度大概是它两倍的离散傅里叶变换,这个离散傅里叶变换是对一个实偶函数进行的。它的思想是将一个实函数对称延拓成一个实偶函数,实偶函数的傅立叶变换也必然是实偶函数,连续函数和离散函数( CFT )都是基于这一原理。在20世纪 80年代至 90年代初期,人们对 DCT 快速算法的研究较多,并且取得了巨大的成功。早在 1977 年, Chen ?根据变换矩阵具有对称性,利用稀疏矩阵分解法第一次提出 DCT 的快速算法。 l984 . 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) 得到了广泛应用,并且不断激发人