第四章快速傅立叶变换

第四章快速傅立叶变换－－FFT算法引言快速傅立叶变换――FFT（TheFastFourierTransform）是离散傅立叶变换的一种快速算法。它是1965年由Cooly和Tukey提出的，快速算法使得离散傅立叶变换的次数大大减少，并使得离散傅立叶变换应用于实际变成了现实。直接计算DFT的问题及改进的途径离散傅立叶变换对：10)()]([)(10NkWnxnxDFTkXNnknN10)(1)]([)(10NnWkXNkXIDFTnxNkknN讨论DFT正变换的运算量整个DFT运算共需要次实数乘法和次实数加法101010])Re[)](Im[]Im[)]((Re[]Im[)](Im[]Re[)](Re[]Im[]Re[)](Im[)](Re[)()(NnknNknNknNknNNnknNknNNnknNWnxWnxjWnxWnxWjWnxjnxWnxkX24N))1(22(NNN的性质周期性：对称性：knNWnNkNNnkNknN)()(nkNNknNknN)(可约性knmmNknNWWmknmNknNWW//knNNnkNNknN)()(12NNWkNNkNWW)2(快速傅立叶变换在时域中抽选称为按时间抽选（decimation-in-time）在频域中抽选称为按频率抽选（decimation-in-frequency）DIT的基－2FFT算法（库利－图基算法）算法原理设序列长度为为整数LNL,210)()()(NkWnxWnxkXnknNnknN奇偶＋rnn2为偶数时，12＋为奇数时，rnn12021202120)12(1202)12()2()12()2()(NrrkNkNNrrkNNrkrNNrrkNWrxWWrxWrxWrxkX＋＋)()12(),()2(21rxrxrxrx12,,1,0Nr)()()()()12()2()(21120221202112021202kXWkXWrxWWrxWrxWWrxkXkNNrrkNkNNrrkNNrrkNkNNrrkN＋＋问题：和都是点序列，而却是点序列，按照上式计算得到的只有其中的一半。另一半如何得到？)()(21rxrx和)()(21kXkX、2N)(kXN解决利用系数的周期性22222222NkrNNkrNjrkNjrkNWeeW)()()(21120211202211kXWrxWrxkNXNrrkNNrkNrN)(222kXkNXkNNkNWW)2(12,...,1,0)()()(21NkkXWkXkXkN)()()2()2()2(212)2(1kXWkXNkXWNkXNkXkNNkN12,...,1,0Nk抽选算法的蝶形运算流图符号)(1kX)(2kXkNW－1)()()(21kXWkXkXkN)()()2(21kXWkXNkXkN点DFT分解为两个点DFT流图N2N运算次数时当2222222NNNNNN继续分解LN2140)12(21140221120211)12()2()()(NlklNNllkNNrrkNWlxWlxWrxkX14,...,1,0)12()()2()(1413Nlrxlxrxlx14,...,1,0)()()()()(423140442140431NkkXWkXWlxWWlxkXkNNllkNkNNllkN14,...,1,0)()()4(4231NkkXWkXNkXkN14,...,1,0)()()()()(625140462140452NkkXWkXWlxWWlxkXkNNllkNkNNllkN14,...,1,0)()()4(6252NkkXWkXNkXkN的流图)(1kX4N点DFT4N点DFT)0()0()0(13xxx)4()2()1(13xxx)2()1()0(14xxx)6()3()1(14xxx)0(3X)1(3X)0(4X)1(4X02NW12NW－1－1)0(1X)1(1X)2(1X)3(1X点DFT分解为四个DFT（）N4N8N变化为一点离散傅立叶变换运算量共有级蝶形，每级都有个蝶形运算组成，而每个蝶形有一次复数乘法，两次复数加法构成，因此每级运算都需要次复数乘法，次复数加法构成为整数LNL,2L2N2NN复数乘法：复数加法：NNLNmF2log22NNNLaF2log直接计算DFT和FFT算法之间的计算量之比NNNNNLNN2222log2log222481632641282565121024416642561024409616384655362621441048576141232801924481024230451204.04.05.48.012.821.436.664.0113.8204.8N2NNN2log2NNN22log2按照时间抽选的FFT算法的特点原位运算（同址运算）倒位序规律倒位序的实现蝶形运算两结点的“距离”的确定存储单元rNW原位运算（同址运算）)(1kXm)(1jXmrNW－1)()()(11jXWkXkXmrNmm)()()(11jXWkXjXmrNmm倒位序规律)(012nnnx0n1n2n00011010101011)000(x)100(x)010(x)110(x)001(x)101(x)011(x)111(x倒位序的实现nnˆ补充：换位的时候有个换位产生倒码的算法顺码二进制二进制倒码0000000010011004201001023011110641000011510110156110011371111117最高位为“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)()(NkIBRkIBR)24()()(NNkIBRkIBR)428()()(NNNkIBRkIBR)221()()(NkIBRkIBR二进制倒码)(kIBR出口全“1”码出口二进制倒码)(kIBR入口YNYYYNNN输入N22NNV1NMNI0I0JJITIAIAJAJAT)()()()(2NVKJKKJJ1IIMNIIKJJ2KKYYYNNN蝶形运算两结点的“距离”以前面8点的FFT为例，其输入是倒位序的，输出是自然顺序的，其第一级的每个蝶形的两节点间“距离”为1。第二级的每个蝶形的两节点“距离”为2，依此类推对点FFT，当输入为倒位序，输出为自然顺序时，其第级运算，每个蝶形的两节点“距离”为LN212m的确定的确定rNWrNmmmmmrNmmmmWkXkXkXWkXkXkX)2()()2()2()()(1111111rkNmmmmmkNmmmmmLmLWkXkXkXWkXkXkX211112111)2()()2()2()()(kNkNmLmLWW22krmL2存储单元由于是原位运算，只需输入序列的个存储单元，加上系数的个存储单元。)1,...,1,0)((NnnxN)12,...,1,0(NrWrN2N按时间抽选，输入自然顺序，输出倒位序的FFT流图：按时间抽选，输入输出均为自然顺序的FFT流图：按时间抽取，各级具有相同几何形状，输入倒位序，输出自然顺序的FFT流图：按频率抽选（DIF）的基－2FFT算法（桑得－图基算法）算法原理1)2(02/1)2(0)2(1)2(0121)2(010)2()()2()()()()()(NnnkNNkNNnkNnNNnnkNNNnnkNNnnkNNnnkNWWNnxnxWNnxWnxWnxWnxWnxkX1,...,1,0Nk12NNWkNkNW)1(21)2(0)2()1()()(NnnkNkWNnxnxkXrk212rk1)2(02)2()()2(NnrnNWNnxnxrXrnNNnnNWWNnxnxrX21)2(0)2()()12()2()()(1NnxnxnxnNWNnxnxnx)2()()(212,...,1,0Nn1)2(021)()2(NnrnNWnxrXrnNNnWnxrX21)2(02)()12(12,...,1,0Nr点DFT按的奇偶分解为两个点的DFTNk2N原位运算rNmmmmmmWjXkXjXjXkXkX)()()()()()(1111蝶形运算两节点间的“距离”mmLN22的计算rNWkNmmmmmmmmmmWNkXkXNkXNkXkXkX121111)2()()2()2()()(1122mmkNkNWW12mkr按频率抽选法与按时间抽选法的异同page155表格离散傅立叶反变换（IDFT）的快速计算方法一种思想：10)()]([)(NnnkNWnxnxDFTkX10)(1)]([)(NknkNWkXNkXIDFTnx另一种思想：1010)(1)(1)(NknkNNknkNWkXNWkXNnx)(1)(1)(10kXDFTNWkXNnxNknkN若不满足有几种方法解决：（1）补零值点的方法，以使增长到最邻近的一个，根据DFT的性质可知，补零后并不影响频谱，只不过是频谱的抽样点数增加了，结果是增加了计算量。但是有的时候计算量增加太多，造成很大浪费（2）如果要求准确的点DFT，而是个素数，则只能采用直接DFT方法，或者用后面将要介绍的CZT（ChirpZ）变换的方法（3）若是复合数，则可以用混合基FFT算法算法－－混合基算法为复合数的FFTNLN2整数的多基多进制表示形式二进制多基多进制进制r二进制，任何一个都可以表示成为01221110222)(nnnnnLLLL212102)(LLnnnnn0121nnnnLLLn2LN212211010222)(LLLLnnnnn则任何一个的正整数可以用r为基数表示成形式进制rLrNLrn进制r0121nnnnLL01221110)(nrnrnrnnLLLLrLLrnnnnn1210)(12211010)(LLLLnrnrnrnn多基多进制对的任何一个正整数，都可以按照多基多进制形式按个基表示成多基多进制形式LrrrN21Lrrrn21LLrrrLLnnnn2101210143232110nr