（生物医学工程专业论文）离散正弦类正交变换的快速算法研究.pdf

东南大学硕士学位论文 a b s t r 。a c t u pt on o w ，p e o p l ep r o p o s e dt e n so fk i n d so fd i f f e r e n tt r a n s f o r m si nm a n ys u b j e c t s ，e a c ho f t h e mh a si t ss p e c i a lt h e o r ya n da p p l i c a t i o nb a c k g r o u n d ，a n dm a n yo ft h e mh a v eb e e nu s e di n s i g n a lp r o c e s s i n g a m o n gt h e m ，t h eo r t h o g o n a lt r a n s f o r m sh a v eaw i d er a n g eo fa p p l i c a t i o n si n s i g n a lp r o c e s s i n ga n di m a g ep r o c e s s i n gd u et oi t ss p e c i a lp r o p e r t y t h er e s e a r c ho b j e c to ft h i s d i s s e r t a t i o ni sak i n do f v e r yi m p o r t a n tt r a n s f o r mo f o r t h o g o n a lt r a n s f o r m s - - - - o r t h o g o n a ld i s c r e t e s i n u s o i d a lt r a n s f o r m s s o m eo f t h e m ，s u c ha st h ed i s c r e t ec o s i n et r a i l s f o r i t l ( d c da n dd i s c r e t ew t r a n s f o r mh a v eb e e np r o v e dm o r ee f f i c i e n tt h a nt h et r a d i t i o n a ld 阿i ns o m ea p p l i c a t i o nf i e l d t h e y c a na v o i dt h ec a l c u l a t i o no fc o m p l e xn u m b e rt h a tc a r ln o tb ea v o i db yd f t e s p e c i a l l y ，w h i c hc a l l s a t t e n t i o no f m a n yr e s e a r c h e r s t h er e s e a r c ho b j e c to ft h i sd i s s e r t a t i o na r et w ok i n d so fo r t h o g o n a ld i s c r e t es i n u s o i d a l t r a n s f o r m ：g e n e r a l i z e dd i s c r e t ef o u r i e rt r a n s f o r m ( g d f t ) a n dd i s c r e t ewt r a n s f o r m ( d w t ) ，a n d t h er e s e a r c hf i e l di st h ef a s ta l g o r i t h m so f t h i st w ot r a n s f o r m s ，e s p e c i a l l yf o e a so nd e v e l o p i n gt h e f a s ta l g o r i t h m so fa r b i t r a r yl e n g t h t h i sd i s s e r t a t i o np r e s e n t saf a s ta l g o r i t h mf o rt h eo d d - t i m e ，o d d f r e q u e n c ya n do d d s q u a r e d d i s c r e t ef o u r i e rt r a n s f o r m s ( d f t ) o fl e n g t hp 2 “w h e r epi s 锄o d di n t e g e r t h eo d d t i m e ， o d d - f r e q u e n c yd f tc a l lb ec o m p u t e db yt w ol e n g t h - n 2d f t , a n do d d - s q u a r e dd f tc a nb e c o m p u t e db yt w ol e n g t h - n 2d f to d d - t i m ed f t n e x tar e c u r s i v ea l g o r i t h mf o rc o m p u t i n gt h ed w ti s p r o p o s e d b yu s i n gc l e n s h a w s r e c u i t e n c ef o r m u l a , w ed e r i v e e f f i c i e n tm e t h o df o rc o m p u t i n gt h et y p “1 ，- i i i ，a n d i vd w t o fs e q u e n c e sw i t hg e n e r a ll e n g t h t h er e s u l t si n d i c a t et h a tt h ep r o p o s e da l g o r i t h m sa c h i e v ea s i m p l ec o m p u t a t i o n a ls t r u c t u r ew h i c hi sp a r t i c u l a r l ys u i t a b l ef o rp a r a l l e lv l s ir e a l i z a t i o n t h e n ，b yr e s p e c t i v e l yf o l d i n gt h ei n p u t so ft h et y p e - i id w t a n dt h eo u t p u t so ft h et y p e - i l l d w t e f f i c i e n tf o r m u l a t i o n sa r ed e r i v e dt 0c o n s t r u c tt h ek e r n e lw a r t s f o r m s t h ec l e n s h a w s r e c u r r e n c ef o r m u l ai st h e nu s e dt or e a l i z et h er e c u r s i v es n n e t u r e s t h et y p e - l vd w ti sc o n v e r t e d i n t ot h et y p e i id w t b a s e do nt h ep r o p o s e da l g o r i t h m s ，t h ec o m p u t a t i o no f t y p “i id w tn e e d s o n l yn 2r e c u r s i v ec y c l e s , a n dt h a to f t y p e - - l la n d - i vd w t sr e q u i r e so n l y n 4r e e u r s i v ec y c l e st o o b t a i nt h ec o e f f i c i e n t so f o n e p o i n to na v e r a g e k e yw o r d s i i a b s t r a c t f a s ta l g o r i t h m s ，g e n e r a l i z e dd i s c r e t ef o u r i e rt r a n s f o r m ( g d f t ) ，d i s c r e t ewt r a n s f o r m ( d w d ， c l e n s h a w sr e c u r r e n c ef o r m u l a i i l 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含为获得东南大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 研究生签名：建萝日期：兰! ! 垒生 qf ，日 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位 论文的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人 电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论 文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包 括刊登) 授权东南大学研究生院办理。 渡琦 绛竿多 柚啤3 9f 了日 第一章绪论 1 1 引言 第一章绪论 在现实生活中，有大量的信号需要我们进行分析，例如我们说话的声音、机器的振动、 金融变化数据、地震信号、音乐信号、医疗图像等。很多信号需要进行有效的编码、压缩、 消噪、重建、建模和特征提取，为此，人们一直在努力寻找各种有效的信号处理方法。从物 理学和信息学的角度来看，任何信息都可以从多种角度进行研究。对于某些信息，当从某个 角度描述有困难时人们常常对其实施一定的变换使变换后的特征容易被人们识别，从而 达到研究的目的。这一点无论是在数学还是在其它科学，尤其是信息科学中己经成为最常用 的手段。信号分析对信号的传输、处理有着重要的作用。它包括时( 空) 域特性分析和变换域 特性分析，根据不同的特性才能选择不同的方法进行信号处理。例如在数字图像处理系统中， 需要对图像进行采样、量化和压缩等处理，这就要求对图像在空域或变换域的特性必须了解。 在数字基带传输系统中，必须设计合理的数字基带信号以使数字信息变换为适合于给定信道 传输特性的频谱结构；在数字信号的带通传输中，必须对数字信号进行载波调制；在控制系 统中，传感器输出有用信息的获得和干扰与噪声地滤除，这些都要涉及到信号的分析。 迄今为止，人们在各个学科领域提出的的各种各样的变换不下几十种，其各自有着特殊 的理论和应用背景，很多变换在信号处理中取得了重要的应用。其中正交变换由于其特殊的 性质在信号处理和图像处理中的到了广泛的应用。 在1 9 0 9 年，h a a r 通过在【o ，l 】区间引入简单的方波函数作为基函数，并实施平移得到 h a a r 正交变换，由于h a a r 函数系的前两个函数为全局函数( 在单位区间 0 ，1 ) 上非零) ，而 其它函数均为局部函数( 在单位区间的部分上非零) ，这种全局局部结构应用于图像处理的边 缘检测，轮廓提取以及图像编码等方面是非常有用的。 1 9 2 3 年，w a l s h 则建立了一种完备的w a l s h 正交函数系统。基于上述两种正交变换构成 的离散正交变换，由于变换矩阵的元素为士1 因此具有运算简便( 如只需要二进制移位) ， 容易建立快速算法的特点，但是，由于方波函数作为信号( 函数) 的近似存在精度偏低的缺 陷，同时变换本身在物理意义上欠缺直观解释，因此，其应用范围受到较多的限制。 众所周知自从1 8 2 2 年傅里叶( f o u r i e r ) 发表“热传导解析理论”以来，傅里叶变换一直是 信号处理领域中应用最广泛的一种分析手段。傅里叶变换的基本思想是将信号分解成一系列 不同频率的连续正弦波的叠加，或者从另外一个角度来说是将信号从时间域转换到频率域。 而在数字信号处理领域中。其对应的离散傅里叶变换( d i s c r e t ef o u r i e r t r a n s f o r m ) 就是离散 东南大学硕士学位论文 正弦类正交变换的一种。1 9 6 5 年，c o o l e y 与t u k e y 等人在离散傅里叶变换( d f t ) 的基础 上提出的快速傅立叶变换( f f t ) 算法，从而大大降低了d f t 计算的时间复杂度，人们 认为，正是f f t 的提出使信号处理领域产生了一次飞跃。 离散余弦变换( d c t ) 是n a m n e d 等人在1 9 7 4 年提出的正交变换方法，尤其是它的第 二种类型，经常被信号处理和图像处理使用，用于对信号和图像( 包括静止图像和运动图像) 进行有损数据压缩。它常被认为是对语音和图像信号进行变换的最佳方法。这是由于离散余 弦变换具有很强的”能量集中”特性：大多数的自然信号( 包括声音和图像) 的能量都集中在离 散余弦变换后的低频部分，而且当信号具有接近马尔科夫过程( m a r k o vp r o c e s s e s ) 的统计特性 时，离散余弦变换的去相关性接近于k - l 变换( k a r h t m e n - l 0 6 v e 变换其具有最优的去相关 性) 的性能。由于近年来数字信号处理芯片( d s p ) 的发展，加上专用集成电路设计上的优 势，这就牢固地确立离散余弦变换( d c t ) 在目前图像编码中的重要地位，成为h 2 6 1 、 j p e g 、m p e g 等国际上公用的编码标准的重要环节。在视频压缩中，最常用的变换方法是 d c t 。 本文研究的内容包括提出离散正弦类正交变换中的广义离散傅里叶变换( g e n e r a l i z e d d i s c r e t ef o u r i e rt r a n s f o r m ) 和离散w 变换( d i s c r e t ewt r a n s f o r m ) 的快速算法研究，主要 集中在研究这两种变换任意长度的快速算法研究上。 1 2 正交变换简介和性质 1 2 1 信号的正交分解 将一个实际的物理信号分解为有限或无限的小的信号“细胞”是信号分析和处理中常用 的方法。这样有助于我们了解信号的性质了解它含有哪些有用的信息并知道如何提取这些 信息。同时，对信号的分解过程也是对信号“改造”和“加工的过程。有助于去除噪声及信号 中的冗余( 如相关性) ，这对于信号的压缩、编码都是十分有用的。 设j 为一希尔伯特空间，其维数为，并设x 是工中的一个元素。盖可以是连续信号， 也可以是离散信号，可以是有限值也可以是无穷。设朔，仇，御为一组基函数可 以是离散的，也可能是连续的，视x 而定。这样。我们可将z 这样一组向量作分解即 x = 吒 2 第一章绪论 式中a l ，a 2 ，a n 是分解系数，它们是一组离散值。如果仇，仍，御是一组两两互 相正交的向量，则( 1 1 ) 式称为x 的正交展开。或正交分解。分解系数鳓，啦，甜是x 在 各个基向量上的投影。 为求分解系数，我们设想在空间z 中另有一组向量：n ，忱，。满足如下关系 ( 训= 拈暑 这样，用晰和( 1 2 ) 式两边做内积，有 口，= ( x o l 0 ) ) = z o 砂? 0 ) ( 1 2 ) ( 1 3 ) ( 1 3 ) 式称为信号的变换，变换的结果是求出一组系数a 1 ，a 2 ，a ；而( 1 1 ) 称为信 号的综合和反变换。朔，忱，称为竹，卿，吼的对偶基或倒数基。若( 仇 是完 备的，且是线性无关的，则 体 是j 中的一组基向量，这时，其对偶向量 存在且惟一， 即存在( 1 2 ) 式的双正交关系。如果一组基向量卿，卿，卿的对偶向量是其自身，即 仍= 们，卿= 蛳，那么这一组基向量就构成了维空间中的正交基。 下面我们再从线性代数的角度米讨论一下正交变换的含义。 设u 为h i b e r t 空间( 简写日空间) ，t 是 ，中的线性变换，若变换前后由内积定义的 范数不变，即( 石= ( t x ，嘲，z u 那么称r 为 ，中的酉变换，若u 为实空间， 则r 称为正交变换。由矩阵理论可知，在标准正交基f 的酉变换矩阵一是酉矩阵，此时满足 五4 7 = 1 ，a 7 = 一；若为正交变换则为正交矩阵，此时满足丘4 1 = i 。a t = a 。 质。 1 2 2 正交变换的性质 信号的正交分解或正交变换”1 ，是信号处理中最常见的一类变换，它有一系列重要的性 性质l ：正交变换的基向量 他) 即是其对偶基向量 ) 。 这类变换有着非常明显的优点： ( 1 ) 若正变换存在，那么反变换定存在且变换是惟一的。 ( 2 ) 正交变换在计算上最为简单。如果x 是离散信号且为有限值，那么( 1 1 ) 式 3 - 东南大学硕士学位论文 的分解与( 1 3 ) 式的变换只是简单的矩阵和向量变换。 容易。 ( 3 ) 反变换不需要矩阵求逆。用硬件来实现时，不需要增加新的器件，且编程也非常 性质2 ：展开系数是信号x 在基向量 弛 上的准确投影。 性质3 ：正交变换保证变换前后信号的能量不变。 此性质又称为“保范变换”，说明如下。由于 2 = 工( 疗) r + ( 开) - - i x ，对 = ( ，仇，) = 吼( 仇，吼) 、n k nk = 口，a ：6 ( n 一) = 1 口。1 2 = i l 口6 2 一k一 ( 1 ，4 ) 即信号的范数等于分解系数的范数，所以正交变换又称“保范变换”。( 1 4 ) 式即是 p a r s e v a l 定理。 性质4 ：信号正交分解具有最小平方近似性质。 性质5 ；将原始信号x 经正交变换后得到一组离散系数a l ，眈，蛳，这一组系数具有 减少x 中个分量的相关性及将x 的能量集中于少数系数上的功能。相关性去除的程度及能量 集中的程度取决于所选择的基函数 儡1 ) 的性质。这一性质是信号与图像压缩编码的理论基 础。 1 2 3 正交变换的种类 正交变换总的可以分为两大类，即非正弦类正交变换与正弦类正交变换。前者包括 w l a s h h a d a m a r d 变换( w h t ) 、h a r t 变换( h r t ) 及斜变换( s l t ) 等，后者包括离散傅 里叶变换( d f t ) 、广义离散傅里叶变换( g d f t ) 、离散余弦变换( d c t ) 、离散正弦变换( d s t ) ， 离散h a r t l e y 交换( d h t ) 及离散w 变换( d w t ) 等。以w h t 为代表的非正弦类变换，由 于其运算时不需要乘法，因此在2 0 世纪6 0 及7 0 年代曾受到推崇并被用于图像编码与数据 压缩。由于具有硬件乘法器的高速d s p 芯片的问世以及具有优良性能的d c t ，d s t 及d w t 等新变换的提出，正弦类正交变换越来越引起了人们的关注。 以上介绍的各种正弦娄变换中，d f t 广泛应用于信号的频谱分析以及相关和卷积的快速 4 第一章绪论 计算，但是这些计算无论输入数据是否实数都是在复数域中进行的。d h t 和d w t 可以在 实数域中实现信号的频谱分析并且具有d f t 的其他功能。实际上d h t 是d w t 的一个特例。 d c t 和d s t 也是实数变换，它们广泛应用于图像的编码和数据压缩。 1 3 信号处理快速算法简介 信号处理是一门内容非常广泛，而又不十分明确的边缘科学，位于电子学、计算机科学、 通信、数学等学科的结合部，已广泛应用于通信、医疗、雷达、声纳、地震勘测、气象等许 多方面，有着非常广泛的应用前景目前正蓬勃发展。微电子技术的发展是促使数字信号处 理技术进一步发展的正要原因，目前，各种数字信号处理器，即专用的信号处理计算机正在 开发，有的已经投放市场，用超大规模集成电路来制造数字信号处理器，已经成为热门话题， 所有这些，进一步促成了数字信号处理技术在更多领域中的广泛应用。但是在这之前一段时 间，由于相关变换计算量太大，限制了其应用。例如频域分析常常比时域分析更优越，不 仅简单且易于分析复杂信号。但用d f t 进行谱分析，在f f t 出现前是不切实际的，这是由 于d f t 计算量太大，而c o o l e y - t u k e y 的快速傅里叶变换( f a s tf o u r i e rt r a n s f o r m a t i o n ) 是将 一个大点数的d f t 分解为若干小点的d f t 的组合，将运算量明显降低，运算时间旱数量 级的缩短人们不会忘记，正是f f t 将数字信号处理推向了一个新的高度，大大推动了信 号处理技术的进步，使数字信号处理技术走向应用。除此之外，巧妙地设计算法可以满足更 高的要求，因此，快速算法是数字信号处理技术的重要支柱。 数字信号处理就其理论来讲就是一些算法的集合，因此有人把它列入计算数学的一个分 支。国内外许多有成就的数学家正在从事这方面的研究。在这门学科中许多问题要研究其快 速算法，否则难以实现，例如离散傅里叶变换( d f t ) ，卷积和相关，矩阵运算，滤波，编 码于译码等无不如此。目前，这个领域发表的论文已经浩如烟海，许多算法已经非常成熟， 在实际应用中得到了广泛的应用。 1 4 目前研究现状和本文意义 在对d f t 的变换核p 啦“进行时间和频率上的移位以后可以得到广义离散傅立叶变换 ( g d f d 的定义【2 】它在诸如滤波器、卷积和信号重建等数字信号处理领域有着重要的作用 1 3 - 5 1 。 东南大学硕士学位论文 p e ia 1 l u o 6 1 利用了d l l l l a l t l e l 的分裂基快速算法将一个长度为| 的g d f r 转化为一个长度 为 他和两个长度为4 的g d f t 来计算。b i r c h e n 7 1 提出了通过计算离散余弦变换( d c t ) 来计 算g d f t 的快速算法。最近，b r i t a n a k 和r a o l s 币u 用稀疏矩阵提出了一种有效计算实数序列 输入的g d f t 快速算法。 离散w 变换( d w t ) 是王中德提出的实数域上定义的一种正交变换，b r a c e w e l l 提出的 离散h a r t l e y 变换( d h t ) 是d w t 的特例。目前已经有多种计算d w t 的快速算法。 w a n g t 2 提出了一种素数因子的d w t i 型快速算法：当序列长度| v ；矿时( 其中g 为奇数) ， b i t 3 1 通过将序列分解为若干短序列的d w t 和离散余弦变换( d c t ) ，实现了一种d w ti i 型的 快速算法；b 【l ”还对= p x 2 “( 其中p 为奇数) 的情形提出了一种基2 的分解方法：曾泳鸿【l ” 等人提出了一种基于素数因子分解的一维任意长度的d w t 快速算法，曾”训还将二维d w t 转 化为一种可分离核的变化来提高计算效率，并提出了利用基于多项式变换的多维d w t 的快 速算法【”】；钟广掣”1 等人利用维d w t 以及多维多项式变换来计算多维d f t ；此外，针对 不同类型的d h t ，h u 四1 对于序列长度= 2 m 的情况，提出了基2 的快速计算g d h t l i 型、i l i 型和i v 型的方法。 现在发表的各种变换( 例如d f t d c t ，d w t 等等) 的快速算法，大多是针对序列长 度为基2 的快速算法，多为类似快速傅里叶变换( f f t ) 的蝶型结构算法。假如所要计算的 序列长度不满足算法的要求，必须进行补零，从而降低算法的效率，而且上述算法大部分是 蝶型的快速算法，在硬件结构上实现并行计算比较复杂，使得其在用硬件实现的时候在计算 效率以及硬件消耗上尚待提高。 由于上述原因，各国学者开始研究任意长度的快速算法：在过去的十多年中，b i 和c h e n 例 提出了支持序列长度为日2 “的d f t 其中g 为奇数：l i u 等人【1 9 1 通过将三角函数展开为泰勒级 数，建立t d w t - 与- - 维信号几何矩之间的关系，实现了一种仅需进行加法运算的d w t f 壬意 长度计算方法。c h o u 和s i u 口2 。2 ”，w a n g 2 ”，a b u r d e l l 1 以及n i k o i 萄e v i e 和f e t t w e i s 口6 】分别 提出了计算任意长度的d c t 和m d c t 系数的递归算法，章品正1 2 7 j 等人利用c l e n s h a w 递归关 系式得到t - - 维t c h e b i c h e f - 正交矩反变换的快速算法。c h i a n g 雨l i u 3 0 1 提出了改进的递归算法 来减少递归的次数。 本文主要提出了任意长度长度的快速算法。其中，第一部分提出了长度为p 2 “的奇一时， 奇一频和奇一时频的离散傅立叶变换( d f d 的快速算法，其中p 为奇数。第二部分针对任意长 度的序列提出了一种新的计算离散w 变换( d w t ) 的递归方法。我们利用c l e n s h a w 递归关 系式推导出了一种可以有效计算i i 型，i i i 型和型d w t 系数的递归算法，接着又针对提出的 算法进行了改进，使得此算法的递归循环次数进一步降低。 一6 一 第一章绪论 1 5 本论文的组织结构 本论文主要部分共有四章，从介绍离散正弦类正交变换开始，推出了广义离散傅立叶变 换( g d f t ) 1 1 离散w 变换( d w t ) 快速算法。 第1 章 第2 章 第3 章 第4 章 绪论。本章对信号处理、正交变换的定义和性质、信号处理的快速算法这些 内容进行了简单介绍，这些都是本论文涉及的背景知识。并对国内外关于快 速算法研究以及本论文重点研究的基于长度任意的序列的快速算法研究现状 进行了简述。 提出了长度为p 2 m 的奇一时，奇一频和奇一时频的离散傅立叶变换( d f t ) 的 快速算法，其中p 为奇数。快速算法将奇一时和奇一频d f t 分解成为两个长 为n 2 的d f t 来计算，而奇一时频d f t 则可以利用2 个长为n 2 的奇一时 d f t 来实现。 针对任意长度的序列提出了一种新的计算d w t 的递归方法。我们利用 c l e n s h a w 递归关系式推导出了一种可以有效计算i i 型，i i i 型和i v 型d w t 系数的递归算法，并给出其信号流图。最后给出了递归算法的计算复杂度分 析，结果表明，该算法不仅结构简单，而且非常适合利用并行v l s i 来实现。 接着针对提出的算法进行了改进，通过分别将输入序列和输出序列对折，推 导出了一种可以有效计算i i 型，i i i 型和i v 型d w t 系数的递归算法，其中递 归算法由c l e n s h a w 递归关系式实现。而i v 型d w t 转化为计算i i 型d w t 。 接着给出了新的算法和原始算法的计算复杂度比较，结果表明，相对未改进 的递归算法，i i i 型d w t 计算只需要一半的递归次数，而i i 型和i v 型d w t 则只需要1 4 的递归次数。 结论和展望。总结了本论文工作获得的成果与尚需改进之处，并对下一步的 研究做了展望。 - ， 东南大学硕士学位论文 2 0 引言 第二章n = p 舟2 “的g d f t 快速算法 离散傅立叶变换( d f t ) 和快速傅立叶变换( f f t ) 在数字信号处理领域有许多的应用。在对 d f t 的变换核g q ”“进行时间和频率上的移位以后可以得到广义离散傅立叶变换( g d f n 的定义【2 】。它在诸如滤波器、卷积和信号重建等数字信号处理领域有着重要的作用p 。】。许 多学者提出了快速算法来降低其计算复杂度。p c i 和l u o t 6 f j 用了d u h a m e l 的分裂基快速算 法将一个长度为的g d f t 转化为一个长度为n 2 和两个长度为n 4 的g d f t 来计算。b i 和c h e n 7 1 提出了通过计算离散余弦变换( d c t ) 来计算g d f t 的快速算法。最近，b r i t a n a k 和 r a o i s l 利用稀疏矩阵提出了一种有效计算实数序列输入的g d f t 快速算法。 上述文献中提出的算法在序列长度为2 ”的时候非常有效，但是在数字信号处理和其他 应用中经常需要计算不同长度的序列，这时候如果利用上述算法计算这些长度的序列就必须 要在序列后面补零，从而降低了计算的效率。为了支持更广范围的序列长度，b i 和c h e n 【9 】 提出了支持序列长度为q * 2 ”的d f t ，其中q 为奇数。借鉴b i 提出的算法， 我们可以推导 出一种支持更广范隔序列长度的g d f t 快速算法。 本文第一节介绍了利用时间抽取技术计算奇一时d f t 的分裂基算法。第二、三节则利 用频率抽取推导出了奇一频和奇一时频d f t 的算法。第四节分析和比较了算法的时间复杂 度。最后一节给出了相应的结论与总结。 首先给出长度为j 的g d f t 2 j t 拘定义如下 础) = 专蓑m 孵州) ，”“ ( 2 1 ) 其中w n = e x p ( - 2 2 ，r n ) 其中是序列长度，口和b 分别为时间和频率原点。当a - - 0 且 b 一1 2 时，称为奇一频d f t ，当a = l 2 且6 = o 时，称为奇一时d f t 。类似的，当a = b = l 2 时， 则叫做奇一时频d f t 。 苎三兰丝三：! ：堕旦望= ! 皇塑塑型l 一 2 1 奇一时d f t 的分裂基算法 奇一时d f t 定义如下： ( 2 2 ) 在计算奇一时d f t 之前，为了使推导公式过程撕1 ) 不越界，我们首先将输入序列d 砷 进行如下重新排列， y o ) = 基于( 2 3 ) 式，( 2 2 ) 中定义的奇一时d f t 可以分解如下式 x ) = z 一+ 孚妒守+ 篙1 杠譬) ) 2 竹+ 刳蝶w 2 + 篙1 y ( ：舻p ：+ i w 。2 w ” 2 一+ 孚) c o s ( 等 卟i n ( 等) p + 篙y ( 2 n 一譬) c o s ( 等 小i n ( 等 蝶“ s ( 百n p k j u 台2 = 1 + 字) 小一孚) 孵“ ”；n ( 等瑚y ( z 玎一譬) 七十刳p “ ( 2 3 ) s 降帕i n 降 9 2+ o 矽g x | | 、，g口 r “必 n 玎 ， 一 o 讲 埘加啦 攻攻哎胁嚣嚣 东南大学硕士学位论文 工( 七+ 争引n = 0z 一+ 孚扩小习+ 引n = 02 一一竽矿洳；) 书，譬笠n = 0 1 恤孚 m 舟细s ( 等舻 二 i vl 巾，字善1 攻z 疗一孚) s 血( 等卜。s ( 等舯“ 却) 。s ( 等) 苫1 攻z 疗+ 孚h ： 一孚) 睇“ + ( - 1 ) n ( 百z r p k n 白2 = i y ( 2 ”+ 等) 一y ( z 一- 5 “- 、1 ) j 扪n 却，孚 s i n ( 等 删母。s ( 等 曰叫 其中k = - 0 1 , n 2 1 。且 删= 4 ) = 孙( z 胛+ 刳+ 忙孚) 嘭： ( 2 5 ) 占伍，= 占( 七+ 訇= 篆1 m ：疗一孚 一y ( z 疗+ 孚 嘲：， 可以看出( 2 6 ) 和( 2 7 ) 式均为长度为 ，2 的d f t ，符合 9 中提出的快速算法对长度的要求， 可以利用其提出的快速算法计算。得到一( 七) 和曰( 七) 后，可以( 2 4 ) 和( 2 5 ) 式计算出坝n 和 x ( 纠- n 2 ) 。 2 2 奇一频d f t 的分裂基算法 奇一频d f t 定义如下： n i x 肼 ) = x 0 沙妒“心h ( 2 8 ) 为了降低计算复杂度，我们利用频率抽取的方法来计算奇一频d f t 。我们将奇一频d f t 分解如下： 1 0 一 蔓三量苎三：! ：塑鱼旦坚堡望竺些 同时定义c ( 七) 和d ( 句， x ( z 后十字建n = ox o 一钞 x ( z 七一刳= n 窆= o z d 一詈， ( 2 9 ) ( 2 1 0 ) c ) ：i 乙n - i x d ；) + ； ” lj = 丢n - i x o 孵。s 等 =苫1x。职“c。s警+。；n-1n=o2 z o 孵“c 。s 等 叫， v n = ， v = 苫m 臃吩。s 等+ ( - 1 ) t p + ln 刍2 - 工( 胛+ 譬 崂n 等 = 卦c o s 等+ ( _ 1 ) 字z 卜争7 r p n p t w 2 。忙) ：丢芝。d 才+ 引一一目 叫萎n - ix ( ”胯咖等 = 一吐善1 x 。职“s m 等一( - 1 ) 孚苫1 x ( 肘学) 暇s 等 叫孙啪等- ( - 1 ) 譬x ( 一母s 警p ：， 其中t = o ，1 2 ，n 2 1 。( 2 1 1 ) 和( 2 1 2 ) 式均为长度为n 2 的d f t ，符合【9 】中提出的快速算 法对长度的要求，可以利用其提出的快速算法计算。 通过( 2 9 ) - - ( 2 1 2 ) 式，显而易见奇一频d f t 可以如下得到： x p 譬) = c ”荆 垄妻奎兰堡主兰垒堡兰一 x 卜譬 = c 睁荆o k _ n 2 - 1 可见，得到c 和d ( 句以后，还需要次加法才可以得到坦。 2 3 奇一时频d f t 的分裂基算法 奇一时频d f t 定义如下： x ，g ) ；n - 1 ，o 烈”+ 瓣) ( 2 1 4 ) 为了降低计算复杂度，我们同样利用频率抽取的方法来计算奇一时频d f t 。可以将奇 一时频d f t 分解如下： 同时定义五( 妁和f ( 的， x ( z 七+ 字 = 艺n = o x o 1 ；3 卜= 芝n f f i o x 。舻1 ； z r ( t ) ：丢篓x ( 一 矗”+ ；) 【2 t 峙 + 砖”+ ；1 2 i 1 2 - ( 2 1 5 ) f 2 1 6 ) ( 2 1 7 ) 趔 咿 哿p 卿嚣斡掣掣掣铷 叱 炒 稚 槲枷桫卜 md患思思cl 第二章n = p + 2 “的g d f t 快速算法 ，? 忙) = 圭篓石。) 孵2 + 导一睇2 i 一； = 一n 。- 。i j zx ( n ) w ( 。2 月+ l k s i n n p n = 一 “+ l n r n 4 u 1 叫阵x o 雕, , * 0 s i nw p n 一( = 一卅x o 雕f 一( ih - 0 ，芦p + l 。n - i ：。( 。+ 警 阡，2 一“