快速傅里叶变换FFT算法及其应用

本文格式为Word版，下载可任意编辑——快速傅里叶变换FFT算法及其应用

快速傅里叶变换FFT算法及其应用

摘要

本文较为系统地阐述了快速傅里叶变换的算法原理及其在数字信号处理等工程技术中的应用。根据抽取方法的不同，一维基2FFT算法分为两种：频域抽取的FFT算法和时频域抽取的FFT算法。第1节阐述了这两种FFT算法的原理。第2节给出了两种算法的编程思想和步骤。第3节阐述了一维非基2FFT的两种算法：Cooley-tukeyFFT算法和素因子算法(PrimeFactorAlgorithm)的思想原理，给出了在把一维非基2DFT的多层分解式转化为二层分解的过程中，如何综合运用这两种算法以达到总运算次数最少的方案；并以20点DFT为例描述了非基2FFT算法实现的一般步骤。第4节介绍了一维FFT算法在计算连续时间信号的傅里叶变换、离散信号的线性卷积、离散信号压缩和滤波等数字信号处理中的典型应用。第5节把一维FFT变换推广到二维FFT变换，并在一维FFT算法的基础上，给出了二维FFT算法的原理和实现过程。最终在附录中给出了一维DFT的基2FFT算法（包括频域抽取的FFT和IFFT算法、时域抽取的FFT和IFFT算法），一维任意非基2FFT算法，二维DFT的基2FFT算法以及二维DFT的任意非基2FFT算法的详细的VisualC++程序。

本文通过各种流程图和表格，较为深入系统地阐述了FFT的算法原理；运用Matlab编程，通过大量生动的实例，图文并茂地列举出了FFT算法的各种应用，并在每个实例中都附上了完整的Matlab程序，可供读者参考。由于篇幅所限，本文未涉及FFT变换以及其应用的数学理论背景知识。

快速傅里叶变换FFT算法及其应用

接着，两个N/2点DFT仍可用上述方法各经N/4个乘N/2个加划分成两个

N/4点DFT（同时还要做相应的频域抽取），从而共划分成4个N/2点DFT，

总划分计算量仍是N个加和N/2个乘。这样的划分可一步步做下去，不难看出，每步的总划分计算量都是N个加和N/2个乘。

经过M?1步的划分后就划成了N/2个如下两点DFT的计算问题

??（9）1?011?0?B?aW2?bW2?(a?b)?W2??1A?aW20?0?bW2?0?a?b上式所需计算量是2个加和1个乘，于是完成N/2个两点DFT的总计算量仍是N个加和N/2个乘。从而完成全部N点DFT的总计算量M?N?Nlog2N个加和M?N/2?(N/2)log2N个乘，这比直接按定义计算所需的N2个乘和加要少得多。例如，N?210?1024，M?10，用FFT算法计算所需的乘法个数为

M?N/2?5?1024，而直接按定义计算所需的乘法个数为N2?1024?1024，二

者相差1024/5?200倍。若直接计算需半小时，而用FFT计算只需9s即可完成，可见其效率之高，而且N越大，FFT的效率提高越明显。

f[0]F[0]000F[0]F[0]000f[1]-1W20F[4]100F[2]F[1]001g[n]f[2]-1W40F[2]010F[4]F[2]010f[3]-1W41-1W20F[6]110F[6]F[3]011f[4]-1W80F[1]001F[1]F[4]100f[5]-1W81-1W20F[5]101F[3]F[5]101p[n]f[6]-1W82-1W40F[3]011F[5]F[6]110f[7]-1W83-1W41-1W20F[7]111F[7]F[7]111图1频域抽取的8点FFT计算流图

一般状况下，由于做了M?1次分奇偶的抽取，此算法最终的N/2个两点

DFT计算出的F[k]不是顺序抽取的。次序的变化可用二进码来说明：第一次抽

取所分的奇偶是由二进码第1位是1或0来区分的，该位为0时为偶数，该位为1时为奇数，其次次抽奇偶是由二进码第2位是1或0来区分的??，每次抽取

5

1一维DFT的快速算法—FFT

都是把偶数项放在前（左）边，把奇数项放在后（右）边，从而抽取以后数的二进码是依照二进制位从左向右依次排列的，和普通二进制数从右向左依次排列的的规律正好相反，所以称为倒位序。在计算出F[k]之后要把倒位序变成顺序。1.1.2逆变换的计算

所谓逆变换是指由F[k]求f[n]的计算，若直接按定义

1N?1?knf[n]??F[k]WNNk?00?n?N?1

做计算，则除了求和号和正变换一致的计算量外，每算一个f[n]都还需再多做一个乘1/N的乘法运算。故按定义完成全部N点DFT的总计算量是N2个加和

N(N?1)个乘。下面从图导出它的快速算法，先探讨第3列的2点DFT的逆运

算如何完成。由式（7）得，

?a?b?A?0(a?b)?W?B?2由上式不难解出

1(A?BW2?0)2（10）

1b?(A?BW2?0)2a?F[0]000F[0]F[0]0001/8f[0]F[1]001F[2]F[4]1001/8W2-0-1f[1]F[2]010F[4]F[2]0101/8W4-0-1f[2]F[3]011F[6]F[6]1101/8W2-0-1W4-1-1f[3]F[4]100F[1]F[1]0011/8W8-0-1f[4]F[5]101F[3]F[5]1011/8W2-0-1W8-1-1f[5]F[6]110F[5]F[3]0111/8W4-0-1W8-2-1f[6]F[7]111F[7]F[7]1111/8W2-0-1W4-1-1W8-3-1f[7]图2频域抽取的8点IFFT计算流图

6

快速傅里叶变换FFT算法及其应用

此计算过程如图2所示，可以看出：左边各列的划分计算也都是由N/2个碟形运算来完成的，只是各碟形运算所乘的相移因子W不同。把每个碟形运算都用图的方法变成对应的逆运算，并把它们按输入在左、输出在右重新排列，就得到了全部N点IDFT的计算流图。给出了N?8的例如，图中先对顺序输入的并把3个乘1/2的运算合成了一个乘1/8的运算放在F[k]做M?1次的频域抽取，

了最前边，然后就开始做求逆的碟形运算。

1.2时域抽取的基2算法

比较正变换DFT和反变换IDFT的定义式

knF[k]??f[n]WNn?0N?10?k?N?1

1N?1?knf[n]??F[k]WNNk?00?n?N?1

可见，去掉乘1/N的运算，把W?1换成W，交换F[k]、f[n]和k、n，反变换定义式就变成了正变换的定义式。对图2做这些变换，则得到图3的流程图。对图1做这些变换，则得到图4的流程图。这就是时域抽取的算法流图。进行碟形运算之前，先要对顺序的时域输入序列进行M?1次的奇偶抽取，故称为时域抽取的FFT算法。

f[0]000f[0]f[0]000F[0]f[1]001f[2]f[4]100W20-1F[1]f[2]010f[4]f[2]010W40-1F[2]f[3]011f[6]f[6]110W20-1W41-1F[3]f[4]100f[1]f[1]001W80-1F[4]f[5]101f[3]f[5]101W20-1W81-1F[5]f[6]110f[5]f[3]011W40-1W82-1F[6]f[7]111f[7]f[7]111W20-1W41-1W83-1F[7]图3时域抽取的8点FFT计算流图

7

2一维基2FFT算法编程

比较图2和图3不难看出，两种算法的计算量是完全一样的。这里先算出

N/2个两点的DFT

?A?f(n)W20?0?f(n?N/2)W201?f(n)?f(n?N/2)

1B?f(n)W21?0?f(n?N/2)W2?1?f(n)?f(n?N/2)（11）

f[0]1/8F[0]000F[0]F[0]000f[1]1/8-1W2-0F[4]100F[2]F[1]001f[2]1/8-1W4-0F[2]010F[4]F[2]010f[3]1/8-1W4-1-1W2-0F[6]110F[6]F[3]011f[4]1/8-1W8-0F[1]001F[1]F[4]100f[5]1/8-1W8-1-1W2-0F[5]101F[3]F[5]101f[6]1/8-1W8-2-1W4-0F[3]011F[5]F[6]110f[7]1/8-1W8-3-1W4-1-1W2-0F[7]111F[7]F[7]111图4时域抽取的8点IFFT计算流图

然后把N/2个两点的DFT组合成N/4个4点的DFT，再把N/4个4点的

DFT组合成N/8个8点的DFT，经过M?1次的组合之后，就得到了顺序N点DFT计算结果。算法原理

快速傅里叶变换FFT算法及其应用

-0.3435+0.0000i-0.1065+0.0000i0.5219+0.0000i-0.7682+0.0000i0.7656+0.0000i-0.5148+0.0000i0.0971+0.0000i0.3520+0.0000i-0.6870+0.0000i0.7994+0.0000i-0.6527+0.0000i0.2945+0.0000i0.1592+0.0000i-0.5612+0.0000i0.7814+0.0000i-0.7484+0.0000i0.4728+0.0000i-0.0440+0.0000i-0.3991+0.0000i0.7128+0.0000i-0.7955+0.0000i0.6204+0.0000i-0.2442+0.0000i-0.2111+0.0000i0.5980+0.0000i-0.7911+0.0000i0.7278+0.0000i-0.4287+0.0000i-0.0094+0.0000i0.4445+0.0000i-0.7354+0.0000i0.7881+0.0000i-0.5853+0.0000i0.1929+0.0000i0.2621+0.0000i-0.6321+0.0000i0.7973+0.0000i-0.7041+0.0000i0.3826+0.0000i0.0628+0.0000i-0.4878+0.0000i0.7548+0.0000i-0.7772+0.0000i

FFT变换后的信号：

-0.2416+0.0000i-0.2415-0.0146i-0.2413-0.0294i-0.2409-0.0443i-0.2402-0.0595i-0.2394-0.0751i-0.2384-0.0911i-0.2371-0.1078i-0.2355-0.1253i-0.2336-0.1438i-0.2314-0.1634i-0.2286-0.1844i-0.2253-0.2072i-0.2214-0.2322i-0.2165-0.2600i-0.2106-0.2911i-0.2032-0.3268i-0.1939-0.3683i-0.1818-0.4177i-0.1658-0.4784i-0.1439-0.5557i-0.1124-0.6588i-0.0643-0.8062i0.0168-1.0398i0.1783-1.4797i0.6372-2.6746i8.8462-23.4497i-1.6196+2.9360i-0.9624+1.2195i-0.7711+0.6680i-0.6881+0.3740i-0.6501+0.1707i-0.6389+0.0000i-0.6501-0.1707i-0.6881-0.3740i-0.7711-0.6680i-0.9624-1.2195i-1.6196-2.9360i8.8462+23.4497i0.6372+2.6746i0.1783+1.4797i0.0168+1.0398i-0.0643+0.8062i-0.1124+0.6588i-0.1439+0.5557i-0.1658+0.4784i-0.1818+0.4177i-0.1939+0.3683i-0.2032+0.3268i-0.2106+0.2911i-0.2165+0.2600i-0.2214+0.2322i-0.2253+0.2072i-0.2286+0.1844i-0.2314+0.1634i-0.2336+0.1438i-0.2355+0.1253i-0.2371+0.1078i-0.2384+0.0911i-0.2394+0.0751i-0.2402+0.0595i-0.2409+0.0443i-0.2413+0.0294i-0.2415+0.0146i

IFFT变换后的信号：

0.0000-0.0000i0.4366+0.0000i-0.7317-0.0000i0.7897+0.0000i-0.5917-0.0000i0.2023-0.0000i0.2532+0.0000i-0.6263-0.0000i0.7964-0.0000i

45

附录

-0.7085-0.0000i0.3909-0.0000i0.0534+0.0000i-0.4803-0.0000i0.7516+0.0000i-0.7793+0.0000i0.5545-0.0000i-0.1499+0.0000i-0.3032-0.0000i0.6581-0.0000i-0.7997-0.0000i0.6821+0.0000i-0.3435+0.0000i-0.1065-0.0000i0.5219+0.0000i-0.7682+0.0000i0.7656+0.0000i-0.5148+0.0000i0.0971-0.0000i0.3520+0.0000i-0.6870-0.0000i0.7994-0.0000i-0.6527+0.0000i0.2945-0.0000i0.1592+0.0000i-0.5612-0.0000i0.7814+0.0000i-0.7484+0.0000i0.4728-0.0000i-0.0440+0.0000i-0.3991-0.0000i0.7128-0.0000i-0.7955-0.0000i0.6204-0.0000i-0.2442+0.0000i-0.2111-0.0000i0.5980+0.0000i-0.7911+0.0000i0.7278-0.0000i-0.4287+0.0000i-0.0094-0.0000i0.4445+0.0000i-0.7354-0.0000i0.7881-0.0000i-0.5853+0.0000i0.1929-0.0000i0.2621+0.0000i-0.6321+0.0000i0.7973+0.0000i-0.7041+0.0000i0.3826-0.0000i0.0628+0.0000i-0.4878-0.0000i0.7548-0.0000i-0.7772+0.0000i

2．一维任意非基2FFT算法VisualC++程序

设原始信号f[n]由连续信号f(t)?sin(4?t)?0.5cos(10?t)离散化采样获得，即

f[n]?sin(4??n/20)?0.5cos(10??n/20)n?0,1,?,19

#include#include#include#definepi3.14159265#defineN20#defineN15#defineN22#defineN32

typedefstd::complexcomplex;

/*一维任意非基2FFT算法*/voidfft(complexf[]){intn1,n2,n3,k1,k2,k3;complexx[N1][N2][N3];complext[N],temp;/*将一维数组映射为三维数组*/for(n1=0;n1

附录

-0.7682+0.0000i0.7656+0.0000i-0.5148+0.0000i0.0971+0.0000i0.3520+0.0000i-0.6870+0.0000i0.7994+0.0000i-0.6527+0.0000i0.2945+0.0000i0.1592+0.0000i-0.5612+0.0000i0.7814+0.0000i-0.7484+0.0000i0.4728+0.0000i-0.0440+0.0000i-0.3991+0.0000i0.7128+0.0000i-0.7955+0.0000i0.6204+0.0000i-0.2442+0.0000i-0.2111+0.0000i0.5980+0.0000i-0.7911+0.0000i0.7278+0.0000i-0.4287+0.0000i-0.0094+0.0000i0.4445+0.0000i-0.7354+0.0000i0.7881+0.0000i-0.5853+0.0000i0.1929+0.0000i0.2621+0.0000i-0.6321+0.0000i0.7973+0.0000i-0.7041+0.0000i0.3826+0.0000i0.0628+0.0000i-0.4878+0.0000i0.7548+0.0000i-0.7772+0.0000i

FFT变换后的信号：

-0.2416+0.0000i-0.2415-0.0146i-0.2413-0.0294i-0.2409-0.0443i-0.2402-0.0595i-0.2394-0.0751i-0.2384-0.0911i-0.2371-0.1078i-0.2355-0.1253i-0.2336-0.1438i-0.2314-0.1634i-0.2286-0.1844i-0.2253-0.2072i-0.2214-0.2322i-0.2165-0.2600i-0.2106-0.2911i-0.2032-0.3268i-0.1939-0.3683i-0.1818-0.4177i-0.1658-0.4784i-0.1439-0.5557i-0.1124-0.6588i-0.0643-0.8062i0.0168-1.0398i0.1783-1.4797i0.6372-2.6746i8.8462-23.4497i-1.6196+2.9360i-0.9624+1.2195i-0.7711+0.6680i-0.6881+0.3740i-0.6501+0.1707i-0.6389+0.0000i-0.6501-0.1707i-0.6881-0.3740i-0.7711-0.6680i-0.9624-1.2195i-1.6196-2.9360i8.8462+23.4497i0.6372+2.6746i0.1783+1.4797i0.0168+1.0398i-0.0643+0.8062i-0.1124+0.6588i-0.1439+0.5557i-0.1658+0.4784i-0.1818+0.4177i-0.1939+0.3683i-0.2032+0.3268i-0.2106+0.2911i-0.2165+0.2600i-0.2214+0.2322i-0.2253+0.2072i-0.2286+0.1844i-0.2314+0.1634i-0.2336+0.1438i-0.2355+0.1253i-0.2371+0.1078i-0.2384+0.0911i-0.2394+0.0751i-0.2402+0.0595i-0.2409+0.0443i-0.2413+0.0294i-0.2415+0.0146i

IFFT变换后的信号：

0.0000-0.0000i0.4366+0.0000i-0.7317+0.0000i0.7897-0.0000i-0.5917-0.0000i0.2023+0.0000i0.2532-0.0000i-0.6263+0.0000i0.7964-0.0000i-0.7085+0.0000i0.3909-0.0000i0.0534-0.0000i

40

快速傅里叶变换FFT算法及其应用

-0.4803+0.0000i0.7516-0.0000i-0.7793+0.0000i0.5545+0.0000i-0.1499+0.0000i-0.3032-0.0000i0.6581