# 离散序列的卷积运算和相关运算的快速傅里叶变换
离散序列卷积运算与快速傅里叶变换
离散序列信号f(n),g(n)的卷积为:
如果直接进行卷积运算,每个f(n)的值都必须与每个g(n)的值相乘,假如f(n)与g(n)的长度相同,也需要进行N的平方次乘法运算,这对处理器的性能有很高的的要求,并且还浪费时间。
%%%% 普通方法求卷积
a = [1 2 3 4]; % 序列1
b = [4 6 8 2]; % 序列2
c = conv(a,b); % 求两个序列的卷积和
c
c =
4 14 32 52 52 38 8
大概流程:
1、分别求两个序列的傅里叶变换;
2、求频域相乘的乘积;
3、傅里叶反变换;
%%%% FFT求卷积
a = [1 2 3 4]; % 序列1
b = [4 6 8 2]; % 序列2
c = conv(a,b); % 求两个序列的卷积和
a1 = [1 2 3 4 0 0 0];% 扩充维度与卷积结果的维度一致
b1 = [4 6 8 2 0 0 0];% 扩充维度与卷积结果的维度一致
a_f = fft(a1); % 序列求傅里叶变换
b_f = fft(b1); % 序列求傅里叶变换
c_f = a_f .* b_f; % 频域相乘
C = ifft(c_f); % 傅里叶反变换
C
C =
4.0000 14.0000 32.0000 52.0000 52.0000 38.0000 8.0000
可以发现,普通方法和FFT法求得的c和C的结果是完全相同的,FFT的运算速度更快(这个可以在运算中感受到)。
离散序列相关运算与快速傅里叶变换
离散序列信号f(n),g(n)的相关运算为:
与卷积运算相比,相关运算少了一个时间反转。
%%%% 普通相关运算
a = [1 2 3 4]; % 序列1
b = [4 6 8 2]; % 序列2
c = xcorr(a,b); % 求两个序列的相关运算
c
c =
2.0000 12.0000 28.0000 48.0000 58.0000 36.0000 16.0000
下面借助FFT算法进行分析:
1、对两个序列做傅里叶变换得A(k)、B(k);
2、将A(k)、B(k)进行共轭相乘,A(k)B*(k);
3、傅里叶反变换;
%%%% FFT相关运算
a = [1 2 3 4]; % 序列1
b = [4 6 8 2]; % 序列2
c = xcorr(a,b); % 求两个序列的相关运算
a1 = [1 2 3 4 0 0 0]; % 扩充维度与相关运算结果的维度一致
b1 = [4 6 8 2 0 0 0]; % 扩充维度与相关运算结果的维度一致
a_f = fft(a1); % 序列求傅里叶变换
b_f = fft(b1); % 序列求傅里叶变换
b_F = conj(b_f); % 取共轭
c_f = a_f .* b_F; % 频域相乘
C = ifft(c_f); % 傅里叶反变换
C = fftshift(C); % 移动零频点到频谱中间
>> C
C =
2.0000 12.0000 28.0000 48.0000 58.0000 36.0000 16.0000
经验证,结果相同。
结论
运算结果相同的前提下,FFT的运算速度会更快。
参考文献
[1]傅晓林.离散卷积和相关运算的快速傅立叶仿真研究[J].重庆交通学院学报,2003(04):76-79.