如何使用 FFT 数据计算卷积？

信息处理 fft IFFT 零填充
2022-02-25 01:40:03

首先，我有一个A长度向量N，通过过程

A1 = fft(A,N);
A2 = Filter(A1);
A3 = ifft(A2,N);

现在，我需要计算向量A2与向量的卷积B，向量B是另一个包含N元素的向量，我注意到似乎我可以使用

ifft(fft(A3,2N).*fft(B,2N))

计算卷积。表示用零fft(A3,2N)填充。A3N

事实上，A2 = fft(A3,N)

那么，问题是我该怎么做才能避免使用 A2 计算 A3 和 fft(A3)？

或者问题是我如何使用 A2 来计算 fft(A3,2N)？我想知道我是否可以减少整个过程中的一些计算。谢谢。
这是一个matlab测试

clear;
N = 4;
A = 1:4;
B = 3:6;
A1 = fft(A);
A2 = (A1).*2020+1234;%filter(no sense)
A3 = ifft(A2);
A4 = fft(A3,2*N);
B2 = fft(B,2*N);
x = xcorr(A3,B)%ans: 0.1952    0.4051    0.6958    1.0470    0.7676    0.5050    0.2424
x2 = ifft(A4.*conj(B2),2*N)%ans: 1.0470    0.7676    0.5050    0.2424         0    0.1952    0.4051    0.6958
x3 = ifft([A2(1:N/2) A2(N/2+1)/2 zeros(1, 2*N-length(A2)-1) A2(N/2+1)/2 A2(N/2+2:end)].*conj(B2),2*N)
%ans: 3.5624    4.2973    5.4391    6.3191    6.2232    5.2077    4.0659    3.4665
2个回答

您可以在频域中填充零。但是当 N 为偶数时，您需要注意 Nyquist bin。

A3 = [A2(1:N/2) A2(N/2+1)/2 zeros(1, 2*N-length(A2)-1) A2(N/2+1)/2 A2(N/2+2:end)];

这里 Nyquist bin 是A2(N/2+1)/2，并且在频谱的中间填充了零

对于 N 奇数

A3 = [A2(1:(N-1)/2+1) zeros(1, 2*N-length(A2)) A2((N-1)/2+2:end)];

这仅适用于需要在时域内插值的情况。几乎与您遇到的问题无关。

在下面发布了您的问题的解决方案。

clear;

N = 4;
M = 2*N-1;

a = 1:4;
r = ones(1, N);           % Rectangular window

A1 = fft(a);
W = fft(r, N);

A2 = (A1).*W;
A3 = ifft(A2, N);

B = 3:6;
x = xcorr(A3,B)

A4 = fft(A3,M);           % A3 is interpolated by a factor of M
B2 = fft(B, M); 

Freq_Multiplication = (A4.*conj(B2));

x2 = fftshift(abs(ifft(Freq_Multiplication, M)))

% Zeropadding A2 is actually interpolation in time-domain. Not really a linear convolution. x3 will show constant results

Zero_pad_A2 = [A2(1:N/2) A2(N/2+1)/2 zeros(1, M-length(A2)-1) A2(N/2+1)/2 A2(N/2+2:end)];

A5 = fft([A3 zeros(1, M-length(A3))], M);

%x3 = ifft(Zero_pad_A2.* conj(B2), M) % This not performing linear convolution

x3 = fftshift(abs(ifft(A5.* conj(B2), M)))
其它你可能感兴趣的问题
上一篇模拟滤波器的相位响应 下一篇Tukey 窗口的使用及其对图形的影响