快速傅里叶变换

分别用直接卷积和快速卷积两种方法求以下两个序列的卷积。

tic、toc，利用matlab计时，tic为起始时间，toc为结束时间，最终显示时间=toc-tic
直接卷积：conv，快速卷积：利用fft，利用时域的卷积等于频域的乘积

x(n)=0.2n*R19(n)   ，  h(n)=(0.8)n*R15(n)。
%直接卷积与快速卷积所花时间的比较
% x(n)=0.2n*R19(n)   ，  h(n)=(0.8)^n*R15(n)。Rx（n）长度为x+1
xn=0.2*(1:20);%生成xn序列，长度为20
hn=0.8.^(1:16);%生成hn序列，长度为16
tic;%利用matlab进行计时，tic表示计时开始，toc表示计时结束，显示时间=toc-tic
yn=conv(xn,hn);%利用直接卷积计算xn与hn的卷积
toc;%计时结束，输出直接卷积所花费的时间
L=pow2(nextpow2(16+20-1));%取快速卷积的长度L≥M+N-1，且保证L为2的整次幂
tic;%同理，获取快速卷积的时间
Xk=fft(xn,L);%用fft计算x（n）的离散傅里叶变换，长度为L，不足补零
Hk=fft(hn,L);%用fft计算h（n）的离散傅里叶变换
Yk=Xk.*Hk;%依次将Xk与Hk中元素相乘，则输出结果为yn的频域形式
yn=ifft(Yk,L);%利用ifft计算yn
toc;%计时结束
subplot(221),stem(xn,'.');ylabel('x(n)');%2行2列的第一顺位
title('x（n）序列');
subplot(222),stem(hn,'.');ylabel('h(n)');%2行2列的第二顺位
title('h（n）序列');
subplot(212),ny=1;stem(real(yn),'.');ylabel('y(n)');%2行1列的第二顺位
title('y（n）序列');

用FFT计算序列x（n）和y（n）的互相关函数rxy（m）。

x（n）={-4，-3，-2，1，0，1，2，2}，y（n）={4，2，-2，1，0，2，2，-3}

conj：去共轭

%已知xn和yn计算互相关函数rm
xn=[-4 -3 -2 -1 0 1 2 2];
yn=[4 2 -2 -1 0 2 2 -3];
k=length(xn);
xk=fft(xn,2*k);%计算fft，数据长度为2*k
yk=fft(yn,2*k);
rm=real(ifft(conj(xk).*yk));%conj为取共轭
rm=[rm(k+2:2*k) rm(1:k)];
m=(-k+1):(k-1);
stem(m,rm);grid;%就单一个图无需排版额情况下可以不加subplot
xlabel('m');ylabel('幅度');