（应用数学专业论文）快速傅立叶变换算法的研究.pdf

快速傅立叶变换算法的研究 专业：应用数学 姓名：李莉 导师：姜正禄副教授 中文摘要 快速傅立叶变换( 户阳) 是数字处理的基本工具之一，它广泛应用于诸如通讯， 医学和天文学许多领域。在信号处理中有大量的数据，因此尽可能地减少计算快 速傅立叶变换所需要的时间，是非常重要的。本文介绍了现有的几种常用的算法， 总结了各种算法的特征，以及适用性，并分析了其计算的复杂性。本文还借助于 基一2 f 阳1 算法和w f t d 算法的优点，给出了一种新的f f t 算法。该改进的算法不 仅运算量少而且结构简单。 关键词：快速傅立叶变换，离散傅立叶变换，基一2 所7 算法，w f t a 算法 r e s e a r c ho nf a s tf o u rie rt r a n s f o r m a i g o ri t h m s m a j o r ：a r l p l i e dm a t h e = a t i c s n a m e ：l il i s u p e r v i s o r ：a s s o c i a t ep r o f e s s o rj i a n gz h e n g l u a b s t r a c t f a s tf o u r i e rt r a n s f o r m ( f e z ) i so n eo ft h eb a s i co p e r a t i o n si nd i g i t a l p r o c e s s i n g ，w h i c h h a sb e e n w i d e l yu s e di nm a n yf i e l d s ，s u c ha s c o m m u n i c a t i o n ，m e d i c i n ea n da s t r o n o m y i ns i g n a lp r o c e s s i n g ，w h e r eam a s s o fd a t an e e dt ob ep r o c e s s e d ，i ti sc r u c i a lt or e d u c ea sm u c ha sp o s s i b l e t h et i m er e q u i r e df o rc o m p u t i n gt h ed i s c r e t ef o u r i e rt r a n s f o r m ( 皿叼t h i s p a p e ri n t r o d u c e sv a r i o u sf f la l g o r i t b m s g i v e st h e i rp r o p e r t i e sa n d s u i t a b i l i t y ，a n da n a l y z e st h e i rc o m p u t a t i o nc o m p l e x i t y an e w 月叮 a l g o r i t h mi sa l s op r e s e n t e dw i t ht h eh e l po ft h ea d v a n t a g e so ft w os u c h a l g o r i t h m sa sr a d i x 一2f f ta n df f t a t h i sa l g o r i t h mn o to n l yr e d u c e st h e c a l c u l a t i o nt i m e sb u ta l s om a i n t a i n st h es i m p l es t r u c t u r e ， k e yw o r d s ：f a s tf o u r i e rt r a n s f o r m ，d i s c r e t ef o u r i e rt r a n s f o r m ，r a d i x 一2 胛a l g o r i t h m f f t a i i 引言 1 8 2 2 年，傅立叶( j o s e p hf o u r i e r ) 发表了“热传导解析理论”，提出了 傅立叶变换它本质上提出了一种与空间思维不同的频域思维方法傅立叶变 换是十九世纪数学界和工程界最辉煌的成果之一它一直是信号处理领域最完 美，应用最广泛的一种分析手段，它也是线性系统分析的有利工具它能够定量 地分析诸如数字化系统，采样点，电子放大器，卷积滤波器，噪声等 然而在实际应用中傅立叶变换的计算量是相当大的，因此寻求它的快速算法 是非常重要的1 9 6 5 年c o o l e y 和t u k e y 发表的关于离散傅立叶变换( 舭乃的 快速算法( f b 7 ) 的著名论文( 见 1 0 ) ，使得助叮的运算量从o ( n 2 1 降为 o ( n l o g n ) ，引起了学术界的广泛兴趣运算量的大大减少使得傅立叶变换的广 泛应用变得可能，促进了数字信号处理级数的迅猛发展 f f t 是近代数值数学最重要的成果之一，在众多领域中发挥了很大的作用， 它的意义远远超过了一个算法的范围，它使得某些数据的事后处理及系统的模拟 研究转入到数据的实时处理的研究，尤其在数字信号处理和图像处理等方面为广 泛采用数字方法打开了一个崭新的局面 快速傅立叶变换在信号处理及其他许多领域得到广泛应用由于不同领域 的需要，2 0 多年来，各种快速算法相继出现，成为数值代数方面最活跃的一个 领域 自从上文提到的c o o l e y 和t u k e y 的著名论文发表以来，关于快速算法的研 究就不断发展，许多人都基于原有的算法，产生出各种新的算法 目前离散傅立叶变换快速算法大概有基一2 月哏基一4 f f l r , r a d e r b r e n n e r 算 法、p r e u s sf f 7 算法、w i n o g r a d 算法、素因子算法、分裂基f f 7 算法( s r f f t ) 以及递归割圆分解算法( r c f a ) 基- 2 f f t 算法首次是由c o o l e y 和t u k e y 提出的( 见 1 0 ) ，其主要的原理是 采用时间或频率抽取的方法基一4 f f t 算法的原理与基一2 f f t 的基本相同，只是 把时间或频率抽取的基变为4 ，这两种算法一直作为经典的f f t 算法被广泛使用 r a d e r b r e n n e r 算法是对基一2 f f f 算法的直接改进，它是用实数( 或纯虚数) 与复数的乘法来代替复数乘法的，从而减少运算量但是这种算法的缺点在于在 运算过程中的某些乘法会引起误差，引起数值不稳定 p r e u s s 胛算法是针对对称实序列及反对称实序列的离散傅立叶变换的快 速计算而产生出来的，这种算法对于这种序列的计算有很好的效果 刚刚介绍的四种快速算法都有一个重要特点，就是算法的各级计算中可以用 同一个计算单元不管软件还是硬件实现，这都非常重要的，但有一个明显的限 制，即变换长度必须是单一整数的幂 1 9 7 7 年8 月，p k o l b a 和w p a r k 利用一维到多维的映射，提出一种素因子 算法( p f a ) ( 见 1 2 ) 这种算法是利用作为卷积来计算的小离散傅立叶计算来 实现的，其效率在大多数情况下比快速傅立叶变换更高，如将聊和p f a 结合 在一起用，效率会更高但是算法的程序相当长，且有相当大的复杂性差不 多同一时期，s w i n o g r a d 提出了一种根本不同的计算离散傅立叶的方法，称为 g f t a ( 见 1 3 ) 这种算法也是利用作为卷积来计算的小傅立叶变换进行嵌套来 实现的对于许多不同长度的离散傅立叶变换，其效率比经典快速傅立叶变换更 高 1 9 8 4 年，法国的杜哈梅尔和霍尔曼提出了分裂基算法( 见 1 ) ，这是一种将 基一2 f f t 和基一4 f f t 运用于变换过程中不同部位的算法基本思路是对偶序号输 出使用基- 2 f f t 算法，奇序号输出使用基一4 f l y 算法，将大点数的b f t 逐级分解 成小点数d f t 运算由于分解的不对称性，算法结构比“固定”基算法比较复杂 但是就目前的n = 2 “的算法来说，它具有最少的乘法和加法次数文献 2 指出 对n = 2 “的一类f f t 算法，至少对一维序列而言，已很难再使乘法量进一步减小 到更接近理论值的下界 上世纪9 0 年代，j bm a r t e n s 用2 ”一1 的一种特殊分解，即将z ”一1 分解为 割圆多项式的乘积，由此推导出一种新的算法，称之为递归割圆分解算法这种 算法特别适合于实序列的b f t 计算( 参见文献 3 ) 以上是对目前的几种快速算法作了一个简单的描述从这些描述，我们可以 大致了解了离散傅立叶快速算法的发展历史与现状 传统上，由于计算机的乘法运算需要通过加法运算来实现，所以进行一次乘 法运算的时间要比一次加法运算的时间多得多因此在传统f f 7 的研究中，主要 是针对减少乘法次数的从快速算法的研究发展来看，主要是从两个方面着手： 一个是针对等于2 的基数次幂的算法，其中主要的代表为基一2 、基一4 算法和 分裂基算法等；另一个是不等于2 的整数次幂算法，其中的代表为i n o g r a d 算法( g f t a ) 和素因子算法( p f a ) 上世纪八十年代以来，随着计算机技术的 发展，用于实现数字信号处理的计算机结构发生了重大的变化，使得执行乘法的 时间变得与加法相同所以在衡量f f t 算法优劣的时候，乘法次数不再是唯一的 2 评判标准，数据的传递与运算的流程也是不可忽略的因素因此一个高效f f t 算法除了要具备较少的乘法和加法次数外，还需具备较少的数据传递和简单的结 构 本论文将介绍几种常用的传统傅立叶变换快速算法的原理，并从算法复杂性 和算法结构方面分析算法，并指出算法适用的范围与此同时，本文还借助于基 一2 月可算法和w f t a 算法的优点，给出了一种新的f f t 算法该改进的算法不仅 运算量少而且结构简单 我们首先从傅立叶变换最基本的描述开始，逐步介绍到在实际应用中的离散 傅立叶变换，再到各种离散变换的快速算法具体安排如下：第一章是傅立叶变 换的描述，第二章是有关离散傅立叶变换的，第三章介绍各种快速算法的基本原 理及分析算法复杂性，第四章探讨一下如何将现有的算法结合使用，使得在效率 上有所提高 3 第一章傅立叶变换的描述 在引言中曾经提到：1 8 2 2 年，傅立叶发表了“热传导解析理论”，提出了傅 立叶变换其实早在1 8 0 8 年，傅立叶就已经完成了这本著作，但是直到1 8 2 2 年才得以出版在该著作中，傅立叶详细地研究了三角级数，并利用三角函数解 决了许多热传导问题傅立叶当时的工作饱受争议，主要原因是他的观点对于当 时的数学家来说是很陌生的从傅立叶最初的工作至今，已经过去了近两个世纪 了，事实证明以他命名的傅立叶级数在理论和实践有非常重要的意义而傅立叶 变换正是在傅立叶级数的基础上发展起来的，因此这一章的论述从傅立叶级数开 始，我们可以从这一章了解到傅立叶变换是如何在傅立叶级数的基础上发展起来 的 1 1 傅立叶级数 我们知道一个定义在一石z 石上的函数f = f ( x ) 可以展开为有限或无限 三角函数的和，其形式为： 口。+ c o s 儆) + 瓯s m ( k x ) ， ( 卜1 ) 其中 = 去，( z 胁，= 妻c 咖o s ( 埘) 出 = 去砂( 咖i n ( 脏尬 c 栩 称( 1 - 1 ) 为函数，的傅立叶级数，称n 。和玩为函数厂的傅立叶系数我们还可 以将傅立叶级数拓展到任意长度的区间一a x a 的函数，其傅立叶展开为 ，( = + 妻以c 。s ( 尼7 ) + s i n ( 七7 ) ， ( 1 3 ) 其中 = 去少( x 鸭= 吉p ( 咖。s ( 七形胁，吨= 丢，( 曲s i n ( 尼形胁c 圳 傅立叶在十九世纪就提出傅立叶级数的概念通常是在实变函数框架下或者在 h i l b e r t 空间中处理( 参见 4 、 5 等) ，有着广泛的应用背景( 见 3 、 6 和 7 ) 傅立叶级数在信号处理上的直观意义是：傅立叶级数把定义在 一石，石】上 4 的信号分解为频率为整数倍关系的谐波分量组合我们也可以用复数形式定义 傅立叶级数一个定义在一万x 万上的函数f ( x ) ，它的傅立叶级数的复数形 式为：厂( x ) 2 萋e “，其中瓯2 击，( x ) e 一“出，f = j 如果，是实值函 数，那么其傅立叶级数的实数形式可以由复数形式推导得出，反之亦然事实上， 如，是实值的，则a 一。= 瓦，从而就有，( 并) = + ( 口。e “) + ( e “) ；又因 为对于任意复数z ，有- z + 7 = 2 r e ( z ) ，所以厂o ) = + 2 r e ( p “) 注意到 吒，巩和吒满足= 口。且吒= 丢。一溉) ，其中n l ，我们就有 厂( 工) = 口。+ r e ( ( - i b ) ( c o s n x + i s i n n x ) ) = + kc o s n x + b s i n n x ( 1 5 ) = lh = l 这就是，的傅立叶级数从复数形式到实数形式的推导把以上的推导过程反过 来，即可由傅立叶级数的实数形式推导出复数形式 1 2 傅立叶变换与其逆变换 在前一节中我们可以知道一个定义在 一f ，】上的连续函数f = f ( x ) 的傅立叶 m 甜 级数的复数形式为：f f x ) = e 了， 其中= 寺( d 芦出- 如果该函数 f = - ，u ) 定义在整个实轴上，则令，斗+ 。o ，便有 厂( x ) = 。l + i m + 。 = x i ：。，；1 , j f f ( t ) e “f t d l 】 ( 1 6 ) 再令 = 竽，a = 九“一 2 予，( 1 6 ) 式就变为 ，c = 曾萤去，e & i ( x - t ) d t m c 们 最后，令鼻( 五) = 2 去一i ，f ( t ) e 厶h “切，( 1 7 ) 式就简化为 5 ，( 曲= 巧魄) 越 ( 1 - 8 ) ( 卜8 ) 式右边的和式类似于积分j 5 ( x ) d x 的黎曼和式的定义当f 趋于无穷， m 趋于0 ，这样五就成为积分式仁( x ) a x 中的以所以就有 m ) = 熄弘( 五) 以另一方面，当f 斗m 时，_ ( d = 击，州“讥因此 可知 删= 娃p e “础呦 将上式括号中的部分记为，( a ) ，即为 夕( 栌去少e “出 m 称函数夕( a ) 为厂的傅立叶变换而称，( x ) = p ( 旯) p “以为傅立叶逆变换- 令a ：2 z m ，则( 卜9 ) 式可以变换成，( 奶= 眇( f ) p 一2 “出这就说明了傅立 叶变换可将一个无限时宽的信号分解为频率为五的一系列频率分量，其中2 可以 是任意实数甚至是复数而相应地，傅立叶级数把定义在【一疗，石】上的信号分解为 频率为整数倍关系的谐波分量组合 6 第二章离散傅立叶变换 傅立叶变换与傅证叶级数技术可以用于分析连续信号，然而在许多应用场 合，信号本身就己经是离散的，在这种情况下需要利用傅立叶变换的离散形式来 分析离散信号本章介绍离散傅立叶变换( 0 p 7 3 ，并给出实例 2 1 离散傅立叶变换的定义 在，( f ) 的定义域上等e o i n i 辅地取2 n + 1 个米样点y ( k a t ) ，k = 0 ，+ - 1 ，+ - 2 ，n 当充分大时，( m ) = ，( f ) e 一“疵可以写为，和) = ，厂p ) e 。“出，用矩形和 来代替积分，则有 ，( 甜) 一ff ( k a t ) e 。2 “。a t ( 2 1 ) t ! 而 将和式( 2 1 ) 分为正、负两部分，并做变量替换k7 = k + n ，就得 m ) “荟傩k - n ) 血】+ ，炉“眦 2 2 然后，令m = 丙乞，2o ，1 一1 ，盖2 ，( 志) ，也2 【，( ( t n ) a f ) + ，( 心) 】f ， 那么当n 充分大的时候，我们就得到离散傅立叶变换的式子 置5 荟掣一矿- 娌书 在结束本节前要指出的是，如果x 是由一个定义在【0 ，研1 上的连续信号，得到 的，那么当女相对h 很小时，x ，就与，的第女个傅立叶系数精确近似 2 2 离散傅立叶变换在实际中的应用 离散傅立叫变换是信号处理中一个非常有用的工具下面给出两个在实际 应用中的例子 考虑如图2 1 所示的信号，它由阻下函数产生： y ( t ) = e 一。“。 s i n ( 2 t ) + 2 c o s ( 4 t ) + o 4 s i n t s i n ( 5 0 t ) 】， 其中0s teh 日的是从该信号中滤除高频噪卢步骤如下：首先在0 s ts2 z 7 上把信号离散化为2 s 。2 5 6 个等间隔的样值点，然后对采样点y ；作离散傅立叶变 换得到夕。，k ：o ，2 5 5 由图2 - 1 中观察可知，噪声频率大于5 ( 每扫为一个周 期) 于是可以保留0 s k 5 时的丸，而其余值的萝。设为0 最后，对经过滤 波的九，应用离散傅立叶逆变换，得到经过滤波后的复原信号，如图2 - 2 所示 图2 - 2 用月可滤波后的信号 离散傅立叶除了可以用于滤波外，还可以用于信号的压缩下面将要介绍的 就是用月町压缩信号的例子考虑由以下函数产生的信号，如图2 - 3 所示 y ( t ) = e1 0 【s i n ( 2 t ) + 2 c o s ( 4 t ) + o 4 s i n ts i n ( 1 0 t ) 】 其中0s fs 幼同上面的例子一样，首先在0 s tsh 七把信号离散化为 8 2 8 = 2 5 6 个等间隔的样值点，然后对采样点y 。作离散傅立叶变换得到 九，k = o ，2 5 5 ，得到允令其中较小的y i 为0 若要对信号进行3 0 的压缩， 则令3 0 个最小的y k 为0 然后对新的y 。进行快速傅立叶逆变换，最后得到压 缩后的信号图2 - 4 中所给出的是用离散傅立叶变换压缩8 0 后的信号 小 u v 一” 八八八， - u v 一 、八2 - 3 未= 鹪 u v 一5 | f 八厂 u一 6 v 图2 - 4用f f t 压缩8 0 后的信号 本节仅介绍了两个离散傅立叶变换应用在信号处理中的简单例子其实它 在许多领域都有广泛的应用，而且这些应用中还涉及许多其他方面的知识如果 想对其有更深入的了解可以参见文献 8 和 9 既然离散傅立叶变换有如此广泛的应用，那么研究它的快速算法研究就非常 重要在下一章将转入对其快速算法的研究 9 第三章离散傅立叶变换快速算法 这一章主要介绍的是各种离散傅立叶变换快速算法的原理，以及从加法计算 次数和乘法计算次数去分析算法的复杂性 设上一章( 2 3 ) 式中的是长为n 的复数序列，令w = e “”，那么离散 傅立叶变换可以表示为 乃= x , w 。( ，= o ，1 ，n 一1 ) ， ( 3 1 ) 其逆变换为 = 寺矿“ ( k = o ，1 ，n 1 ) ( 3 - 2 ) t i = o 不难看出，直接计算x i ，需2 次复数乘法和n ( n 一1 ) 次复数加法，当n 充分大 时，计算量相当大的，这还不包括复数矿封的计算，因此寻求它们的快速算法是 非常重要的 3 1 傅立叶快速算法的基本原理 考虑n 点的d f t , 设n = 1 n 2 ( n i 1 ，2 1 ) ，将下标- ，和| j 改写为 k = 脚2 + n 1 ，j = 2 毛+ 如( 吩，岛= 0 , 1 ，m - 1 ；i = l ，2 ) ，令= e 弛，呒= p - i 2 7 9 l 2 一f 2 m ， 代入( 3 - 1 ) 式得 x u , h + 屯= 彬呐形1 h x n i n 2 + n i 时2 屯( 珥，i = o 1 ，m 一1 ；i = 1 ，2 ) - ( 3 3 ) = 0n 2 = o f h ( 3 3 ) 式可知，一的计算可以分作三步： 第一步，计算1 个长度为2 点的d f t 芋n ，并令每个觑叮序列为k 一： ：窆x n i n 2 + n j 时t z ( 铲o 1 ，1 一l ；也：o ，1 ，2 1 ) ； 2 = 0 第二步，计算南w “南。 第三步，对( e 内w “也) ，计算2 个长度为l 点的所丁序列 1 0 j ：x 2 ”七2 ：n - 1 ( 嘛) 磁柏，或按下式的顺序进行计算 n z - o 一l m - l x 怕+ b = b ( 肖l 。w 响) ”，其中，k f = 0 , 1 ，i 一1 2 - - - - 0月1 2 0 i = 1 , 2 因此，f f f 算法有两种不同的形式，从计算复杂性考虑，它们是等价的，他们都 是利用几个小的d f f 的计算来代替一个大的钟7 的计算，从而达到提高效率的目 的事实上，按上述步骤计算直接计算m 点饼7 的运算量为研次乘法和 m ( m 一1 ) 次加法，则仅需m = ( 1 + 2 + 1 ) 次乘法和a = n q 1 + n 2 - 2 ) 次加 法加法次数和乘法次数明显减少当是一个高度复合数时，也就是说当 1 ，：也是复合数时，上述计算步骤可以反复使用后来常用的几种傅立叶快速 算法都是在这个思想的基础上发展起来的本文接下来将介绍几种常用的傅立 叶变换快速算法 3 2 基- 2 f f t 算法 设= 2 ( t 1 ) ，取l = 2 ，n 2 = 2 “，根据3 1 中所叙述的方法，一个点 d f t 就按下标分为奇、偶两个部分： 以一i叫一1 巧= x 2 , w 2 每+ 矿也w 2 9 ( ，= o 1 n 一1 ) ( 3 4 ) 其中w ：e 1 ”将( 3 4 ) 分作前后两个2 点序列，就有 x 产n 董x 2 , w t m + w j t o i x 2 。：“cu ，：。，一， n 1 x n 牙 x ：t r w t m + w j 罗以, x 2 k = ok f f i “咿 m 由于形，：。一”，因此形，+ ：。学：。一。一4 ：一， 就可以写为 彬一1 吲一1 x + 旷 - x 2 i “一形屯m 矿” ( 3 5 ) ( 3 6 ) 于是( 3 - 6 ) ( 3 7 ) 我们称这种分解方法为时间抽取法( d e c i m a t i o n - i n - t i m ef f ta l g o r i t h m s ) ( 见 1 0 1 ) ，这是因为在实际应用中，输入下标通常与时间变量有关令 明一l喇一l g j = 芝也t “，h j = 羔工：。矿“，则( 3 5 ) 和( 3 - 7 ) 式可写为 x j2 q + 矽q ，以2 嘭一矿。h j ( j = 0 , 1 ，一1 ) ( 3 8 ) 不难看出，q 和巧其实是两个长度的d f x 当计算出嘭和哆后，我们就 可以得到我们也可以用同样的方法把q 和分解为前后4 个长度的 d f t 序列，就得 n ，一1 n ，_ 、 嘭：釜- 。目+ w z 。笠l 。矿且 ( ，：o ，1 ，以一1 ) ， ( 3 9 ) 啄= 备一，孙砖， 净 e c ,以1 q = - 矽4 “1 + 矿2 。善懈3 形俳“。( ，= 0 , 1 ，么一1 ) ( 3 一1 1 ) 么_ 1么- l _ + 。k - - - - o _ w m 一矿“姜“形“ ( 3 - 1 2 ) 令彰：n 至i x 4 k ：笙x 4 k + 2 胪妒m 州，t ；致。一哪， 令彰=矿”，雪，= 形“，l = _ 。+ ，4 仕“，t = _ 。矿q “o ， 则( 3 - 9 ) 、( 3 - i 0 ) 、( 3 1 i ) 和( 3 1 2 ) 变成 g i = g i + w _ 童j ， ( 1 3 ) q + 2 g j 一矽2 7 雪， ( 3 1 4 ) h i = h i + w 2 j i 。 ( 3 1 5 ) + 以= 吩一矿2 7 t ( 3 1 6 ) 这是一个递归的过程下一步就是拆分计算毋、白、t 和t ，如此继续下去， 一般地，第i 步是将2 i 个长度为2 t - i ( n = 2 ，( t 1 ) ) 点的d f t 转换为2 个长度 为2 t + 1 的d f t , 所需乘法和加法次数分别为能和n ，f = l o g ：n 步后就得到x j 在每一层计算中，加法次数为n ，而乘法次数为噬，所以基一2 f f t 算法的复杂 性如下： 乘法次数：m ；m o g ：1 ( 3 - 1 7 ) 加法次数：a = n l o g ：l 下文将利用一个长度为8 的d f ) - 例子说明算法的思想当n = 8 时，根据上 面的分析可知，计算可以分解为三步图3 1 、图3 2 和图3 - 3 分别显示了这三 步计算的具体过程类似于这三个图的图通常被称为蝶型图( b u t t e r f y ) ( 参见 i 0 ) 蝶型图中的节点代表上一步计算所得结果，而结果通过直线连接与箭头 下方元素相乘，在两直线交汇处将两个结果相加，如图3 2 中就有g 。- g 。+ o 。， g ，一g ，+ 1 。详细观察图3 一l 、图3 2 和图3 - 3 ，我们可以知道每一步问其实存 在如图3 4 的关系根据图3 - 4 把图3 一l 、图3 2 和图3 - 3 连接起来，就得到图 3 5 一妒。 图3 - 1 第一层计算蝶型图 一w 图3 - 2 第二层计算蝶型图 1 3 蜘 如 如 此。 第f m 一1 图3 - 3 第三层计算蝶型图 暇 一1 图3 4 每一层问的关系 1 4 第m 步 x l x 2 x x e 图3 5n = 8 的d f t 全过程蝶型图 图3 5 显示出计算的全过程及其中每步数据的传递在这里要指出的是，在 实际中，计算机实现的过程与算法分析的过程是相反的在算法思路分析中我们 是将d f t 分解，而计算机计算的过程则是先计算最后一层的结果，然后逐层把结 果组合，最终得到我们想要的长度为的d f t 在整个计算的过程中，我们只需要建立两个数组去存储数据一个数组彳存 放待计算数据，一个数组占存放计算结果而上一步的计算结果就作为下一步的 待计算数据，而新得到的结果就放在原来的数组a 中 重新考察图3 - 5 ，我们不难发现，得到的输出结果墨( f = 1 n 一1 ) 是有序 的这种输出结果有序的算法被称为s e l f s o r t i n gi n p l a c ea l g o r i t h m ( 参见 文献 1 1 ) 然而输入部分的数据就是不规则排列的所以要实现整个计算过程 我们就必须首先对数据进行重排 1 5 首先将输入数据的下标改写为二进制表示： x o 。x m x l2x o o l x 22 x o l o ，而2 x o l l 。0 0 ，屯2 x 1 0 1 2 x l l o ，x 7 。 1 1 而这些数据将存放在数组a 中，存放顺序如下： x 0 0 0 一一0 0 0 x i 寸a 1 x 0 l o a o i o x 0 1 l 4 l o x 1 0 0 a 0 l x l o i a 1 0 1 i o 斗a o l l l io4 1 1 将( 3 1 9 ) 中的数列按顺序写出，便可以得到图3 - 1 中的输入数据顺序： 4 o = 工o ，a 1 0 02 x 4 l2 。4 ，a l o l2 x 5 以l o = 工2 ，a i t o = x 3 4 l l = ，a l l l = x 7 ( 3 - 1 8 ) ( 3 - 1 9 ) ( 3 - 2 0 ) 从( 3 2 0 ) 中我们可以发现数据重排的规则：就是将原数放入数列中下标为原下 标的反序的位置若而= x n m 。( i = 0 , 1 一一1 ) 则有 x i + 4 m 在图3 - 6 中给出在计算机中执行的过程 图3 - 6 数据重排示意图 1 6 彬削 m 圳舻刷 刖刖 基一2 胛算法结构简单，存储方便，有利于计算机硬件实现理论上基一4 f f t 算法点数的取值种类应该是基一2 圩7 算法的一半，这样使得基一4 抒7 的应用受到 限制下面我们将介绍基一4 辟7 算法，看看它在运算速度上是否有改进 基本原理与基- 2 f f t 算法大致相同设= 2 ，这时可取1 = 4 ，2 = 2 “ 将一分作前后四个序列，其中一个序列为 k 圳鳌k = o l 矿哟矿棼。旷蚴 + 矿：，n 芝- i - 。矿。t 蚴+ 致k + 3 矸7 4 k ( j + 纷( 3 2 1 ) 其中矿：p - i 兹”，而4 t ( 一) ：矿“，所以有 矿以警w 哟叫孙一 睁z z ， 同理求出( 3 2 2 ) 中的其余部分，并记 i 蜀j = _ i 州矽州( f = o 1 23 ；k = o l ，蟛一1 ) ，( 3 2 3 ) k - - o 于是( 3 - 2 2 ) 式可以写为 t + 嘣2 矿。矗厂i w 7 墨，广w 2 j x 2 ，j + i r l ：3 7 墨j ( 3 2 4 ) 同理可以写出 以= 缈。x o ，+ 矽置，+ 形2 x 2 j + 矿 墨 ( 3 2 5 ) x h 2 w “x b 。i w ix t 。l w i x ! i w i ixll，(3-26) x j + 3 以2 形。x o ，+ i w 7 x 1 ，一w 2 1 x 2 一f 形3 五，j ， ( 3 2 7 ) 其中= 0 , i ，么一1 这样就将一个长度为的胛转换成四个长度为的d b 7 来计算，所需乘法次数和加法次数各为，么和3 每一个z u 为新的删：薯，又 可以分解为四个长度为的口吁下面以五，( = o ，1 ，么一1 ) 为例，回忆( 3 2 4 ) 式，可知 1 7 五。：致。胪 将五i 。分为四部分而6 k + 1 ) e l m ；，而。，和玉m 。，( ，= 0 , i ，必一1 ) ，则有 = 各。咿圳即咎。， ：厶”1 , 一 t n 厶3 6 l - i 西6 h l 形1 鲫) ( 3 - 2 8 ) 其中，= l ，5 ，9 ，1 3 , k = 0 ，1 ，一1 令墨? ：笠- 1 m f 矿哪则( 3 2 8 ) 式可以写为 n ， 五，= w 。墨? + 矿“艇? + 矿”矗? + 矿“础：，( 3 - 2 9 ) + 叼= w o 础一i w ”y o 厂) w “础+ i w ”雒0 ， ( 3 3 0 ) 一冉以= 缈。础一w “。x - 5 1 0 ，) + 矿“碰? 一矽”张j ， ( 3 3 1 ) 一j + 3 蟛= w 。础+ i w ”x o j ) 一w ”硝一i w ”砧j ( 3 3 2 ) 与基一2 f f t 算法一样，这样重复拆分下去，经过l 0 9 4n = - ii o g ：步的计算后， 二 就可以得到髟，而且每一层的计算所需的乘法次数和加法次数各为，和3 n 次， 因此估计出的基一4 的f f t 的运算量为 m = 吾。g ： ：昙1 。9 2 ( 3 - 3 3 ) 将( 3 3 3 ) 式与( 3 1 7 ) 比较看来，基一4 的f f t 的乘法次数减少了而加法次数 似乎增加了，但我们重新注意( 3 - 2 9 ) 、( 3 3 0 ) 、( 3 - 3 1 ) 和( 3 3 2 ) ，发现它们 的计算有对称性记巧。= w ”x 。，这四个式可以写成 。( j + e j ) + f f l 。，+ e j ) ，( 3 3 4 ) 2 y o j - y ：) - i ( 一) + 詈2 k ，+ k ，) 一k ，+ 匕， 1 8 ( 3 3 5 ) ( 3 3 6 ) 工，+ i 3 n 。，一匕，抄瓯一匕，) ( 3 3 7 ) 实际上只需要计算k ，+ y 2 ，j ，x ，+ 匕，一，- y 3 ，和，一e ，就可以了这样 每一层的加法次数只需要2 次了，乘法次数也只需要次所以实际的算法复 杂性为：m = ( 1 4 ) n l o g ，a = n l o g ! 由此可见，基一4 f f t 算法的乘法次数比 基一2 胛算法减少必，而且迭代次数比基一2 胛算法减少了一半，每次迭代运算 需取出和存入n 个数据，所以基一4 胛算法需要访问内存的次数也可以减少一 半，这样也有利于提高运算速度但是基一4 f f t 算法点数的取值种类应该是基 一2 f f t 算法的一半，这样使得基一4 f f t 的应用受到限制，而且基一4 f f 7 的蝶型图 也比基- 2 f f t 算法要复杂得多其实从理论上说，基数越高总的计算量就越少， 所以采用基一8 和基一1 6 算法应该可以使运算次数进一步减少，但减少量会越来越 不显著，而基一8 、基一1 6 算法的蝶型图会更加复杂，硬件和软件实现也非常不便， 所以一向以来对它们的研究与利用并不多特别值得指出的是，在大规模集成电 路迅速发展的时代，高速阵列乘法器的出现使得乘法计算量减少几分之一不再具 有太大的吸引力因此在现在算法的简单性和规则性将更加适合大规模集成 这也是基一8 、基一1 6 算法不受青睐的原因 3 4 素因子算法 无论是基一2 还是基一4 算法，都对助叮的长度有非常大的限制，它们必须 是2 或4 的次方但是在实际应用往往是不可能的由于这个原因，后来发展 的口盯算法很好地解决了这个问题1 9 7 7 年k o l b a 和p a r k 提出了与基一2 类算法 结构完全不同的素因子算法( p f a ) ( 参见文献 1 2 ) ，该算法在当时受到普遍关注 该算法的基本思路是将一个一维的d f t 变换为二维甚至是多维的小点数 d f t , 逐层计算以获得一些计算上的优越性，本文以一维觑可转换成二维的# f t 为例说明算法的基本原理 将( 3 一1 ) 式中的，j 作映射变换： ( 3 3 8 ) ( 3 3 9 ) 其中，七。，。= o 1 一，一1 ；七：，j ：= 0 , 1 ：一1 ，( ) 代表对括号中的数求关于m 勺余 数，且n j 的选取必须满足如下规则 0 。n ，) 。一n ：，( n ：n a ) 。= ，( n l n 。) 。= o ，( 一：一s ) 。= 0 1 9 将( 3 - 3 8 ) 和( 3 - 3 9 ) 式代入( 3 - 1 ) 式，就有 n 一1m 一1 x ，2x ( ，- ，z ) 。哥荟z ( k l , k 2 嘲“飚， 3 圳 其中巩，；p “一，巩，。e “z 显然( 3 - 4 0 ) 式是二维胛的形式，而这个二其中= p 肿1 ，一e “2 显然( 4 0 ) 式是二维胛的形式，而这个二 维变换是由两个独立的一维变换嵌套而成，而且嵌套次序是可以改变的先将 个数据z ( ，k ：) 以j ：为间距循环抽取组合，一共可以抽取出1 个组，每一组有： 个数据，并完成这1 个长度为2 点的i u t 运算，在送回原存储地址；然后再按 j 。间隔抽取，得到：个组，每组。个长度数据，对每组进行长度为1 点所7 运算每完成一组长度为1 点d f t 的计算就将结果分别送回原址，最后的 x ，- x ( l ，：) 由l 组j v ：点d f t 2 组l 点d f t 嵌套组合而成 这样得出的结果是必须进行重排的如果要使得到的结果是顺序的，就必须 预先对输入数据进行处理，具体做法与时间抽取的碳似当由多个因子组 合而成时，即n ；n ，n ：。( m 为整数) ，重复使用分解公式，即可将删扩 展至多维情况( 参见文献 1 4 ) p f a 算法的优点是以简便的结构将大点矾为多维小点o f t , 以减少运 算量，整个算法的运算量取决于各小点删具体运算量我们可以从附录c 的列表得知，相邻两个数，偶数点的硎运算量要比级奇数点的运算量要少， 但是由于删算法的前提条件是1 ，j l r ：一，其中两两为互素因子，所以其中只 能有一个偶数因子，故当较大时，算法中含有许多奇数长度的d r r , t 算，使得 总运算量反而比长度相近的基一2 f 1 略有增加但是素因子算法最大的缺点在 于它必须进行复杂的下标变换，增加了它在软件与硬件实现上的难度 3 5w f t a 算法 受到p f a 的启发，s w i n o g r a d 随后提出了w b y a 算法( 参见文献 1 3 ) 素因子算 法p f a 与l c b y a 相似之处是：它们都适用于长度为n = n 。n ：的d t ：z 接下来将 介绍这种的算法 回顾离散傅立叶变换的定义，由3 1 式知，_ 5 荟屯4 j = 叫，一1 2 0 令x = 而 工2 x n 一1 ，x 。 五 x 2 x n ，并建立一个x 矩阵阡0 。，其中阡，。( j 】 ，) = ( 阡) = ( 蝶m o d n ) ，( 七，j = 0 , 1 n 1 ) ，则( 3 1 ) 式就可写为 x = 腑( 3 - 4 1 ) 我们先来讨论为比较小素数的情况，以n = 7 为例子说明当= 7 时，有 矽“o 矽“1 “2 “3 o 。4 o 。5 矿” 矽1 。o 形“1 矽。2 形1 ” 。4 “5 形k 6 ” 矽2 。1 2 “2 矽“3 矽2 。4 矿“5 缈2 ” 形3 ” 舻3 “1 矿3 “2 矽” 形“4 矽3 。5 矿“ 5 。o 矿5 “ 5 。2 形5 ” “4 矽5 4 形“6 二堡 其中w = e 。由于形的对称性，( 3 - 4 2 ) 可以变为 x o 置 丑 x 、 x 4 x s x 6 1 1 lll 1 矿2 3 彤4 1 2 4 6 1 1 3 矽6 2 矿5 1 形4 1矽5 2 l 矿5 矿3 矽1矽6 1 6 矽5 矿4 矿3 将( 3 - 4 3 ) 中的矩阵做行列变换可得 l11 1矿1形3 1形3矿2 1 形2矿6 1矿6矿4 1形4矿5 15 矿1 l 矽6 w w w w鹾 l1l 64矿 肜45矿 矿5缈1矿 肜3 矿 3形2矿 2矿6矿 2 1 ( 3 - 4 2 ) ( 3 - 4 3 ) ( 3 - 4 4 ) 确确砌胁舢船靠 viii二jjjii凡 鲫 叫 眦 ：窨 晰 矿矿矿矿 螂 州 忱 似 郴 惭 矿矿矿形矿矿矿 氓置五五致以瓦 ，形矿形矿矿矿 斯而勘鼽如舢船 2 6 4 5 3 矽矿矿缈矿肜 惯旧哺旧旧令 w 矽 w 矽 矿 w ( 3 4 5 ) 则由( 3 4 4 ) 知，= + _ + 也十而+ x 4 + 鼍+ 矗，x 1 = x o + z 1 ，x 2 x o + z 2 ， x 3 = x o + z 3 ，x 4 = x o + z 4 ，x s = x o 十z 5 ，x 6 = x o + z 6 明显地，( 3 4 5 ) 是一个循 环卷积( 关于循环卷积的定义，以及计算方法参见附录爿及附录b ) 我们可以 通过计算循环卷积的方法算出z i ( i = 1 , 2 6 ) 当为一个比较小的素数的时候 ( 比如说，n = 2 ，3 ，4 , 5 ，7 ) ，( 3 3 8 ) 式均可以利用循环卷积的方式进行计算( 计 算方法及过程参见附录c ) 接下来我们看看n = p 7 的情况( 其中p 为素数) ，以n = 9 为例当n = 9 时， 二型 其中矿= p ，做行列变换，就得 ( 3 - 4 6 ) ( 3 4 7 ) 瓤托瓢靠n砖 viiiiioiijij几 矿矿矿矿 6 4 5 l 3 2 矿矿矿矿缈矿 i 5 i 3 矿矿形矿 3 2 6 4 5 矿形矿矿矿 l 3 2 6 4 5 矿矿矿矽矿矿 函乃乃靠“乃 如而如舢如船新鲰 vijjiiiii二“iiiijjjjjj八 矿矿矿矿矿矿矿矿矿矿矿矿矿形矿矿 o 6 3 0 6 3 o 6 3 形矿矿矿形肜矿矿 0 5 6 2 7 3 8 4 矿矿矿矿矿矿矿矿 o 8 3 7 2 6 l 5 矿矿矿矿矿矿矿 0 3 6 o 3 6 o 3 6 缈