快速付立叶变换(FFT) for mm=l:m号将DFT作m次基2分解，对每次作DFT运算 Nmr=2mm;u=1; 号旋转因子u初始化 WN=exp (-i*2*pi/Nmr); 名基本DFT因子 for j=1:Nmr/2 号本次间隔内的各次蝶形运算 for k=j:Nmr:N %本次蝶形运算跨越间隔 Nmr=2^mm;kp=k+Nmr/2;号蝶形运算的下标 t=y(kp)*u; 号蝶形运算的乘积项 y(kp)=y(k)-t; 号 蝶形运算的加法项 y(k)=y(k)+t; 号蝶形运算的减法项 end u=u*WN 修改旋转因子， end, end 21
21 快速付立叶变换(FFT) for mm=1:m % 将DFT作m次基2分解, 对每次作DFT运算 Nmr=2^mm;u=1; % 旋转因子u初始化 WN=exp(-i*2*pi/Nmr); % 基本DFT因子 for j=1:Nmr/2 % 本次间隔内的各次蝶形运算 for k=j:Nmr:N % 本次蝶形运算跨越间隔 Nmr=2^mm;kp=k+Nmr/2; %蝶形运算的下标 t=y(kp)*u; % 蝶形运算的乘积项 y(kp)=y(k)-t; % 蝶形运算的加法项 y(k)=y(k)+t; % 蝶形运算的减法项 end u=u*WN; % 修改旋转因子, end, end
快速付立叶反变换(IFFT) 快速付立叶反变换(IFFT):它和正变换是互成对 偶的并有相似的形式： N-1 x(m)= 两端取共轭： 可见x*(n)是X*(k)/N的傅立叶变换，故要求X(k) 的反变换x(n),可先求X*(k)/N的FPT,再把求得 的结果取共軛。 22
22 快速付立叶反变换(IFFT) 快速付立叶反变换(IFFT):它和正变换是互成对 偶的并有相似的形式: 两端取共轭： 可见x *(n)是X *(k)/N的傅立叶变换，故要求X(k) 的反变换x(n),可先求X *(k)/N的FFT,再把求得 的结果取共軛。 − = − = 1 0 ( ) 1 ( ) N k kn WN X k N x n − = − = − = = 1 0 1 0 ( ) ( ) ( ) N k k n N N k k n N W N X k W N X k x n
用MATLAB计算FFT和IFFT MATLAB中FFT函数的调用： 正变换：X=f(x);或X=(x,N) N指定了FFT的长度。在默认条件下，它取x 的长度。因为当N取2的幂次时，计算的速 度最快，所以当x的长度不是2的幂次时， 应尽量指定N。 反变换用的是函数，其调用方法与函数 类似x=i(X):或 x-ifft(x.N) 23
23 用MATLAB计算FFT和IFFT MATLAB中FFT函数的调用： 正变换：X=fft(x);或 X=fft(x,N) N指定了FFT的长度。在默认条件下，它取x 的长度。因为当N取2的幂次时，计算的速 度最快，所以当x的长度不是2的幂次时， 应尽量指定N。 反变换用的是ifft函数，其调用方法与fft函数 类似x=ifft(X);或 x=ifft(x,N)
数字信号处理器(DSP)中的FFT ·FFT进行的是重复性的乘积累加计算(MAC Multiply-Accumulate-Calculation),普通PC机 用的通用处理器需要用许多个指令周期才能完 成一个MAC。所以开发了专门的DSP处理器， 其主要特点是能高效地实现MAC运算。例如 最新的DSP处理器可以在一个指令周期内完成 一条MAC,并且在硬件中实现位倒序。在所 有的DSP芯片开发系统中，FFT也都是标准的固 件。 24
24 数字信号处理器(DSP)中的FFT • FFT进行的是重复性的乘积累加计算（MAC— Multiply-Accumulate-Calculation），普通PC机 用的通用处理器需要用许多个指令周期才能完 成一个MAC。所以开发了专门的DSP处理器， 其主要特点是能高效地实现MAC运算。例如 最新的DSP处理器可以在一个指令周期内完成 一条MAC，并且在硬件中实现位倒序。在所 有的DSP芯片开发系统中，FFT也都是标准的固 件
4.3用FFT计算序列的频谱 有限长序列的频谱计算：设已知位于n1~n2区间 的xn),要求其频谱。 在使用FFT时，必须用主值区间n=0,.,N-1的数 据，FFT函数会产生N个数据，它们应该定位在 下列频点上。 ok=kdo=k*2π/N,k=0,1,…,N-1 如果要求频谱关于零频率对称，可以利用 X1=fftshift(X)函数。此时X1应分布在下列频 点上。 os=kdo,k=-(N-1)/2:(N-1)/2 25
25 4.3 用FFT计算序列的频谱 有限长序列的频谱计算 ：设已知位于n1~n2区间 的x(n)，要求其频谱。 在使用FFT时，必须用主值区间n=0,…,N-1的数 据，FFT函数会产生N个数据，它们应该定位在 下列频点上。 如果要求频谱关于零频率对称，可以利用 X1=fftshift(X)函数。此时X1应分布在下列频 点上。 2 / , 0,1, , 1 k = = = − kd k N k N , ( 1) / 2 : ( 1) / 2 k = = − − − kd k N N