第四章快速傅立叶变换

1、第四章 快速傅立叶变换FFT算法引言 快速傅立叶变换FFT（The Fast Fourier Transform）是离散傅立叶变换的一种快速算法。它是1965年由Cooly和Tukey提出的，快速算法使得离散傅立叶变换的次数大大减少，并使得离散傅立叶变换应用于实际变成了现实。 直接计算DFT的问题及改进的途径 离散傅立叶变换对： 10)()()(10NkWnxnxDFTkXNnknN10)(1)()(10NnWkXNkXIDFTnxNkknN讨论DFT正变换的运算量 整个DFT运算共需要 次实数乘法和 次实数加法 101010)Re)(ImIm)(ReIm)(ImRe)(ReImRe)(Im)

2、(Re)()(NnknNknNknNknNNnknNknNNnknNWnxWnxjWnxWnxWjWnxjnxWnxkX24N)1(22(NNN 的性质周期性：对称性： knNWnNkNNnkNknNWWW)()(nkNNknNknNWWW)(可约性 knmmNknNWWmknmNknNWW/knNNnkNNknNWWW)()(12NNWkNNkNWW)2(快速傅立叶变换 在时域中抽选称为按时间抽选（decimation-in-time） 在频域中抽选称为按频率抽选（decimation-in-frequency） DIT的基2FFT算法（库利图基算法） 算法原理 设序列长度为 为整数LNL,

3、210)()()(NkWnxWnxkXnknNnknN奇偶rnn2为偶数时，12 为奇数时，rnn12021202120)12(1202) 12()2() 12()2()(NrrkNkNNrrkNNrkrNNrrkNWrxWWrxWrxWrxkX)() 12(),()2(21rxrxrxrx12, 1 , 0Nr)()()()()12()2()(21120221202112021202kXWkXWrxWWrxWrxWWrxkXkNNrrkNkNNrrkNNrrkNkNNrrkN问题：问题： 和 都是 点序列，而 却是 点序列，按照上式计算得到的只有其中的一半。另一半如何得到？ )()(21rx

4、rx和)()(21kXkX、2N)(kXN解决解决 利用系数的周期性 22222222NkrNNkrNjrkNjrkNWeeW)()()(21120211202211kXWrxWrxkNXNrrkNNrkNrN)(222kXkNXkNNkNWW)2(12,.,1 , 0)()()(21NkkXWkXkXkN)()()2()2()2(212)2(1kXWkXNkXWNkXNkXkNNkN12,.,1 , 0Nk抽选算法的蝶形运算流图符号 )(1kX )(2kX kNW 1 )()()(21kXWkXkXkN )()()2(21kXWkXNkXkN 点DFT分解为两个 点DFT流图 N2N运算次数

5、时当2222222NNNNNN 继续分解 LN2140)12(21140221120211) 12()2()()(NlklNNllkNNrrkNWlxWlxWrxkX14,.,1 , 0) 12()()2()(1413Nlrxlxrxlx14,.,1 , 0)()()()()(423140442140431NkkXWkXWlxWWlxkXkNNllkNkNNllkN14,.,1 , 0)()()4(4231NkkXWkXNkXkN14,.,1 , 0)()()()()(625140462140452NkkXWkXWlxWWlxkXkNNllkNkNNllkN14,.,1 , 0)()()4(6

6、252NkkXWkXNkXkN 的流图 )(1kX 4N点 DFT 4N点 DFT )0()0()0(13xxx )4()2() 1 (13xxx )2() 1 ()0(14xxx )6()3() 1 (14xxx )0(3X ) 1 (3X )0(4X ) 1 (4X 02NW 12NW 1 1 )0(1X ) 1 (1X )2(1X ) 3(1X 点DFT分解为四个 DFT（ ） N4N8N变化为一点离散傅立叶变换 运算量 共有 级蝶形，每级都有 个蝶形运算组成，而每个蝶形有一次复数乘法，两次复数加法构成，因此每级运算都需要 次复数乘法， 次复数加法构成 为整数LNL,2L2N2NN复数乘

7、法：复数加法： NNLNmF2log22NNNLaF2log直接计算DFT和FFT算法之间的计算量之比 NNNNNLNN2222log2log222 4 8 16 32 64 128 256 512 1024 4 16 64 256 1024 4096 16384 65536 262144 1048576 1 4 12 32 80 192 448 1024 2304 5120 4.0 4.0 5.4 8.0 12.8 21.4 36.6 64.0 113.8 204.8 N2NNN2log2NNN22log2按照时间抽选的FFT算法的特点 原位运算（同址运算） 倒位序规律 倒位序的实现 蝶形运

8、算两结点的“距离” 的确定 存储单元 rNW原位运算（同址运算） )(1kXm )(1jXm rNW 1 )()()(11jXWkXkXmrNmm )()()(11jXWkXjXmrNmm 倒位序规律 )(012nnnx 0n 1n 2n 0 0 0 1 1 0 1 0 1 0 1 0 1 1 )000(x )100(x )010(x )110(x )001(x )101(x )011(x )111(x 倒位序的实现 n n 补充：换位的时候有个换位产生倒码的算法 顺码二进制二进制倒码0000000010011004201001023011110641000011510110156110011

9、371111117最高位为“0”的倒码的下一个倒码仅与它的最高位差“1”。即若在最高位用“1”代替“0”，便可以得到0，2，1，3相应的下一个倒码4，6，5，7。一般可以表示成为： 2)() 1(NkIBRkIBR如果倒码的最高位不是“0”而是“1”，如给出的倒码为“4”，则下一个倒码除了要把最高位的“1”改为“0”以外，尚应该测试次高位，若次高位为“0”，则用“1”替代，可得 24)() 1(NNkIBRkIBR )(kIBR的 最 高 位 是 1 ？ )(kIBR的 次 高 位 是 1 ？ )(kIBR的 第 三 位 是 1 ？ )(kIBR的 最 低 位 是 1 ？ 2)()(NkIBR

10、kIBR )24()()(NNkIBRkIBR )428()()(NNNkIBRkIBR )221()()(NkIBRkIBR 二 进 制 倒 码)(kIBR出 口 全 “ 1 ” 码 出 口 二 进 制 倒 码)(kIBR入 口 Y N Y Y Y N N N 输入N 22NNV 1 NMNI 0I 0J JI TIAIAJAJAT)()()()( 2NVK JK KJJ 1 II MNII KJJ 2KK Y Y Y N N N 蝶形运算两结点的“距离” 以前面8点的FFT为例，其输入是倒位序的，输出是自然顺序的，其第一级的每个蝶形的两节点间“距离”为1。第二级的每个蝶形的两节点“距离”为

11、2，依此类推对 点FFT，当输入为倒位序，输出为自然顺序时，其第级运算，每个蝶形的两节点“距离”为 LN212m 的确定 的确定rNWrNmmmmmrNmmmmWkXkXkXWkXkXkX)2()()2()2()()(1111111rkNmmmmmkNmmmmmLmLWkXkXkXWkXkXkX211112111)2()()2()2()()(kNkNmLmLWW22krmL2存储单元 由于是原位运算，只需输入序列 的 个存储单元，加上系数 的 个存储单元。 ) 1,.,1 , 0)(NnnxN) 12,.,1 , 0(NrWrN2N按时间抽选，输入自然顺序，输出倒位序的按时间抽选，输入自然顺序

12、，输出倒位序的FFT流图：流图： 按时间抽选，输入输出均为自然顺序的按时间抽选，输入输出均为自然顺序的FFT流图：流图： 按时间抽取，各级具有相同几何形状，输入倒位序，输按时间抽取，各级具有相同几何形状，输入倒位序，输出自然顺序的出自然顺序的FFT流图：流图： 按频率抽选（DIF）的基2FFT算法（桑得图基算法） 算法原理 1)2(02/1)2(0)2(1)2(0121)2(010)2()()2()()()()()(NnnkNNkNNnkNnNNnnkNNNnnkNNnnkNNnnkNWWNnxnxWNnxWnxWnxWnxWnxkX1,.,1 , 0Nk12NNWkNkNW) 1(21)2(

13、0)2() 1()()(NnnkNkWNnxnxkXrk212 rk1)2(02)2()()2(NnrnNWNnxnxrXrnNNnnNWWNnxnxrX21)2(0)2()() 12()2()()(1NnxnxnxnNWNnxnxnx)2()()(212,.,1 , 0Nn1)2(021)()2(NnrnNWnxrXrnNNnWnxrX21)2(02)() 12(12,.,1 , 0Nr 点DFT按 的奇偶分解为两个 点的DFT Nk2N原位运算 rNmmmmmmWjXkXjXjXkXkX)()()()()()(1111蝶形运算两节点间的“距离” mmLN22的计算rNWkNmmmmmmmm

14、mmWNkXkXNkXNkXkXkX121111)2()()2()2()()(1122mmkNkNWW12mkr按频率抽选法与按时间抽选法的异同 page155 表格 离散傅立叶反变换（IDFT）的快速计算方法 一种思想：一种思想： 10)()()(NnnkNWnxnxDFTkX10)(1)()(NknkNWkXNkXIDFTnx 另一种思想：另一种思想： 1010)(1)(1)(NknkNNknkNWkXNWkXNnx)(1)(1)(10kXDFTNWkXNnxNknkN若不满足 有几种方法解决： （1） 补零值点的方法，以使增长到最邻近的一个，根据DFT的性质可知，补零后并不影响频谱，只不

15、过是频谱的抽样点数增加了，结果是增加了计算量。但是有的时候计算量增加太多，造成很大浪费 （2） 如果要求准确的点DFT，而是个素数，则只能采用直接DFT方法，或者用后面将要介绍的CZT（Chirp Z）变换的方法 （3） 若是复合数，则可以用混合基FFT算法算法混合基算法为复合数的FFTNLN2整数的多基多进制表示形式 二进制 多基多进制 进制r二进制 ，任何一个 都可以表示成为01221110222)(nnnnnLLLL212102)(LLnnnnn0121nnnnLLLn2LN212211010222)(LLLLnnnnn 则任何一个 的正整数可以用r为基数表示成 形式 进制rLrN Lr

16、n 进制r0121nnnnLL01221110)(nrnrnrnnLLLLrLLrnnnnn1210)(12211010)(LLLLnrnrnrnn多基多进制 对 的任何一个正整数，都可以按照多基多进制形式按 个基表示成多基多进制形式 LrrrN21Lrrrn21LLrrrLLnnnn210121 0143232110nrnrrrnrrrnnLLLLL1122211121010)(LLLLnrnrrrnrrrnn1,.,1 , 01,.,1 , 01,.,1 , 011110rnrnrnLLL例如例如 则2153rrN 01021105nnnrnn10110103)(nnnrnn4 , 3 ,

17、 2 , 1 , 0; 2 , 1 , 001nn5310)13(315)8(101010133)8(5310)24(425)14(101014234)14(例如例如 321234rrrN 0120313221026nnnnrnrrnn21021121010412)(nnnnrnrrnn1 , 0; 2 , 1 , 0; 3 , 2 , 1 , 0012nnn234103100123620 10107314012)20(算法原理 的快速算法21rrN 21rrN 1,.,1 , 01,.,1 , 0,2011021rnrnnrnn12rrN 1,.,1 , 01,.,1 , 0,1021011

18、rkrkkrkk实际上是把一位数字用一个矩阵形式表示 例如： ，则 82421rrN1 , 03 , 2 , 1 , 0,20101nnnnn84212rrN3 , 2 , 1 , 01 , 0,40101kkkkk 1010011010011010)(012100101120110001101220111112000110122011011012),(),()()(),()()(rnrnknNnrkNknrNrnrnrknrNknNnrkNknrNrnrnkrknnrNNnnkNWWWnnxWWWWnnxWnnrxWnxkkXkrkXkX11112211112rknrrrrknrNWW),(

19、),( ),(),(),(),(102100011000110100110100101012200122000012201100011011201100012kkXWnkXWWnkXWWWnnxWWWnnxkkXnkrrnnkrrnknNnkrrnrnknNknrnrkNrnrnknNknrN 101001001110111,.,1 , 0,),(),(rnknrrkWnnxnkX00),(),( 001001knNWnkXnkX1021001102201021,.,1 , 0,),( ),(rnknrrkWnkXkkX),(),(10201kkXkkX算法步骤：算法步骤： 将 ，利用),()

20、(01nnxnx改写为1,.,1 , 01,.,1 , 0),()()(201101012rnrnnnxnnrxnx利用 得到： 101001001110111,.,1 , 0,),(),(rnknrrkWnnxnkXDFTrr点个做12),(001nkX利用 得到：1021001102201021,.,1 , 0,),( ),(rnknrrkWnkXkkXDFTrr点个做21),(102kkX利用 ，进行整序),(),(10201kkXkkX),()(01kkXkX例如：对于前面)24(8242121，其中rrrrN1 , 03 , 2 , 1 , 0,20101nnnnn3 , 2 , 1

21、 , 01 , 0,40101kkkkk步骤：3004010011013,.,1 , 0,),(),(nknkWnnxnkX008001001),(),( knWnkXnkX10120011020101 , 0,),( ),(nknkWnkXkkX),(),(10201kkXkkX另外，也可以采用先乘以旋转因子再进行DFT的算法 10100101201101100012),(),(rnrnknrknNnkrWWnnxWkkX运算量的估计为复合数时FFTN21rrN ) 1(:11221212rrrrrDFTrr复数加法复数乘法点个直接法求NN个旋转因子：复数乘法乘 ) 1(:21222121r

22、rrrrDFTrr复数加法复数乘法点个直接法求) 1() 1(212112221212rrrrrrrrNrr复数加法复数乘法总计：) 1(2NNNDFTN复数加法复数乘法的运算量为：点直接计算一个基4FFT算法 若4.21Lrrr3 , 2 , 1 , 043 , 2 , 1 , 041010iLiiiiLiiikkknnn30303001211001110,),()()(nnnnkNLLNnnkNNkWnnnnxWnxkXL101044LiiiLiiiknnk010110221011104444444nkNnkNnkNnkNnkNLiiiLiiiLLLiiiLLLiiiWWWWWLN4010

23、1202201101444444nkNnkNnkkNnkNnkNLiiiLiiiLLLLWWWWW0101202201011101444443030304012110),()()(nkNnkNnkkNnnnnkNLLNnnkNLiiiLiiiLLLLLWWWWnnnnxWnxkX30401213040121012011101101),(),(),(LLLLLnnkLLnnkNLLLWnnnnxWnnnnxnnnkX3044012013044012010131022212022202211),(),(),(LLLLLLLLLnnknkNLnnkNnkNLLWWnnnkXWWnnnkXnnnkkX

24、304)4(401310201421033323013),(),(LLLLnnknkkNLLWWnnnkkXnnnkkkX30444012101011110120),(),(mLmLmmLmiiimLnnknkNmLmmmLmmWWnnnkkkXnnnkkkX3044021011210001020),(),(nnknkNLLLLLLLiiiWWnkkkXkkkkX),(),()(01211210kkkkXkkkkXkXLLLLL例如：2416 N以第一级为例， 的四点DFT可以表示为： ),(01knjWWjWW34241404, 1, 1调整输出的顺序 绘制成为流图形式 第二级运算 按照二进制倒位