手把手教你理解(FFT)

实验原理

傅里叶变换是一种将信号从时域变换到频域的变换形式，是信号处理的重要分析工具。离散傅里叶变换（DFT）是傅里叶变换在离散系统中的表示形式。但是DFT的计算量非常大，FFT就是DFT的一种快速算法,FFT将DFT的N2步运算减少至(N/2)log2N步。离散信号x(n)的傅里叶变换可以表示为:

N1

X(k)x[n]WNnk

N0

WNej2/N

式中的WN称为蝶形因子，利用它的对称性和周期性可以减少运算量。一般而言，FFT算法分为时间抽取（DIT）和频率抽取（DIF）两大类。两者的区别是蝶形因子出现的位置不同，前者中蝶形因子出现在输入端，后者中出现在输出端。本实验以时间抽取方法为例。前者和后者如图所示：

时间抽取FFT是将N点输入序列x(n)按照偶数项和奇数项分解为偶序列和奇序列。偶序列为：x(0),x(2),x(4),…,x(N-2)；奇序列为：x(1),x(3),x(5),…,x(N-1)。这样x(n)的N点DFT可写成：

N/21n0N/21n0

X(k)

x2nW

2nkN

x2n1W

(2n1)kN

考虑到WN的性质，即

2WN[ej(2)/N]2ej2/(N/2)WN/2

因此有：

X(k)

或者写成：

N/21n0

x2nW

nkN/2

W

kN

N/21n0

x2n1W

nkN/2

X(k)YkWNkZk

由于Y(k)与Z(k)的周期为N/2，并且利用W

fft在matlab中可以按原理采样来运算，也可以用快速fft算法。

clear

fs=1000

t=0:1/fs:0.6;

f1=100;

f2=300;

x=sin(2*pi*f1*t)+sin(2*pi*f2*t);

subplot(711)

plot(x);

title('f1（100Hz）\f2(300Hz)的正弦信号，初相0')

xlabel('序列（n）')

grid on

number=512

y=fft(x,number);

n=0:length(y)-1;

f=fs*n/length(y);

subplot(713)

plot(f,abs(y));

title('f1\f2的正弦信号的FFT（512点）')

xlabel('频率Hz')

grid on

x=x+randn(1,length(x));

subplot(715)

plot(x);

title('原f1\f2的正弦信号（含随机噪声）')

xlabel('序列（n）')

grid on

y=fft(x,number);

n=0:length(y)-1;

f=fs*n/length(y);

subplot(717)

plot(f,abs(y));

title('原f1\f2的正弦信号（含随机噪声）的FFT（512点）')

xlabel('频率Hz')

grid on

快速傅氏变换?

function X=myfft(x)

%myfft函数 用递归实现

N=length(x);

t=log2(N);

t1=floor(t);

t2=ceil(t);

if t1~=t2; %若x的长度N不为2的整数次幂，则补0至最接近的2的整数次幂

x=[x zeros(1,2^t2-N)];

N=2^t2;

end

w0=exp(-j*2*pi/N);

X=zeros(1,N);

if N==2

X(1)=x(1)+x(2);

X(2)=x(1)-x(2);

else

n=1:N/2;

xe(n)=x(2*n-1);

xo(n)=x(2*n);

XE=myfft(xe); %递归调用

XO=myfft(xo);

for n=1:N/2

X(n)=XE(n)+XO(n)*(w0^(n-1));

X(n+N/2)=XE(n)-XO(n)*(w0^(n-1));

end

end