快速付立叶变换(FFT) 用这些措施后总的乘法次数约为（当N很大时）： 当N=1024时乘粢数ī05NP024=1048576相 比，减小了近200倍。 FFT除了提高速度，还要减少计算时所用的内存。 理想的方法是实现原位计算，即每次运算的结 果就放在输入数据的位置上，最后输出结果就 放在原输入数据的位置上。这样所需的内存数 目就是N个。为此，在具体实现FFT时，要遵 循一些规则和技巧： 16
16 快速付立叶变换(FFT) 用这些措施后总的乘法次数约为（当N很大时）： 当N=1024时，结果为5120，与10242＝1048576相 比，减小了近200倍。 FFT除了提高速度，还要减少计算时所用的内存。 理想的方法是实现原位计算，即每次运算的结 果就放在输入数据的位置上，最后输出结果就 放在原输入数据的位置上。这样所需的内存数 目就是N个。为此，在具体实现FFT时，要遵 循一些规则和技巧： 2 乘法次数 = 0.5 log N N
FFT如何节省内存（排序） (1)输入数据和输出数据的下标按二进制排序： 时域抽取法(Decimate-in-time一DIT)一输入数据遵 循倒序排列，则输出按顺序排列。如N=8, 二进制顺序为[000,001,010,011,100,101,110,111]： 即：0,1,2,3,4,5,6,7 二进制倒序为[000,100,010,110,001,101,011,111]： 即：0,4,2,6,1,5,3,7 故DT输入数据按x(0),x(4),x(2),(6),(5),(3),x(3) x(7)排列，输出下标即为顺序排列。 17
17 FFT如何节省内存(排序） (1).输入数据和输出数据的下标按二进制排序： 时域抽取法(Decimate-in-time—DIT)—输入数据遵 循倒序排列，则输出按顺序排列。如N=8, 二进制顺序为[000,001,010,011,100,101,110,111] ： 即：0,1,2,3,4,5,6,7 二进制倒序为[000,100,010,110,001,101,011,111] ： 即：0,4,2,6,1,5,3,7 故DIT输入数据按x(0),x(4),x(2), x(6), x(5), x(3), x(3), x(7)排列，输出下标即为顺序排列
快速付立叶变换(FT) (2).运算结构图按蝶形运算成对安排；每一段蝶形 运算完成后，左边的一对数据就无用了，它们 的位置就用来保存右边的一对数据。 (3)运算从左到右，按段进行。每一段运算完成后， 左一列数据就用不到了，全用右一列数据来取 代。 (4).各段全部运算完毕后，N个输入数据就换成了N 个输出数据。其下标序号则由倒序变成了顺序。 18
18 快速付立叶变换(FFT) (2).运算结构图按蝶形运算成对安排；每一段蝶形 运算完成后，左边的一对数据就无用了，它们 的位置就用来保存右边的一对数据。 (3).运算从左到右，按段进行。每一段运算完成后， 左一列数据就用不到了，全用右一列数据来取 代。 (4).各段全部运算完毕后，N个输入数据就换成了N 个输出数据。其下标序号则由倒序变成了顺序
快速付立叶变换(FFT) 快速付立叶变换的其他变型和讨论： 以上讨论的方法称为基2-DIT-FFT方法 (1).仔细分析可以发现，N不必分解到2（基2），基 4的计算速度是最快的。 (2).DIF-FFT方法与DIT-FFT形成对偶： (3).N不是2的幂次时可按素数分解，构成其他FFT 算法. (4).FFT算法通常都用汇编语言编写，以进一步提 高运算速度，所以各种软件系统都有℉T模块可 供调用。一般不需自己编程。 19
19 快速付立叶变换(FFT) 快速付立叶变换的其他变型和讨论： 以上讨论的方法称为基2-DIT-FFT方法 (1).仔细分析可以发现，N不必分解到2(基2)，基 4的计算速度是最快的。 (2). DIF-FFT方法与DIT-FFT形成对偶； (3). N不是2的幂次时可按素数分解,构成其他FFT 算法. (4).FFT算法通常都用汇编语言编写，以进一步提 高运算速度，所以各种软件系统都有FFT模块可 供调用。一般不需自己编程
快速付立叶变换(FFT) 用MATLAB模仿FFT算法 function y=myditfft(x) m=nextpow.2(x);N=2^m;号长度x对应的2的幂次m 号若x的长度不是2的幂，补零到2的整数幂 if length(x)<N x=[x,zeros(1,N-length (x))]end 号求1：N数列的倒序 nxb=dec2bin([1:N]-1,m);号求二进制顺序值 nxd=bin2dec(f1iplr(nxd))+1;求十进制倒序值 y=x(nxd); 号将x倒序排列作为y的初始值 (接下页) 20
20 快速付立叶变换(FFT) 用MATLAB模仿FFT算法 function y=myditfft(x) m=nextpow2(x);N=2^m; % 长度x对应的2的幂次m % 若x的长度不是2的幂，补零到2的整数幂 if length(x)<N x=[x,zeros(1,N-length(x))]; end % 求1:N数列的倒序 nxb=dec2bin([1:N]-1,m); %求二进制顺序值 nxd=bin2dec(fliplr(nxd))+1;求十进制倒序值 y=x(nxd); % 将x倒序排列作为y的初始值 （接下页）