# how I can use the FFT data to compute the convolution?

First,I have a vector A of length N,through process

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


Now,I need compute the convolution of vector A2 with vector B,vector B is another vector with N elements，I noticed that seemed that I could use

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


to calculate convolution. fft(A3,2N) means padding A3 with N zeros.

In fact, A2 = fft(A3,N)

So, the problem is what can I do to avoid calculate A3 and fft(A3) by using A2?

Or maybe the problem is how can I use A2 to calculate fft(A3,2N)?I wan to know if I can reduce some calculations in the whole process.thanks.
Here is a matlab test

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

• Please take a look on the result of x and x2. Disregarding 0 they are the same albeit with a shift. – jomegaA Feb 7 at 8:12
• yes,I knew about it.But my question is how can I do to make x3=x2=x1 by using The data before this line(A3 = ifft(A2, N);),like padding A2 or Insert some value.So maybe i should review the formula of FFT to find out how is each element calculated – user9568523 Feb 7 at 9:18
• A5 = fft([A3 zeros(1, M-length(A3))], M); x3 = fftshift(abs(ifft(A5.* conj(B2), M))) – jomegaA Feb 7 at 9:25

You can pad zeros in frequency domain. But you need to take care about Nyquist bin when N is even.

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)];

Here Nyquist bin is A2(N/2+1)/2 and zeros are padded in the middle of the spectrum

For N-odd

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

This is only for the case if you need to interpolate in time-domain. Almost irrelevant to the problem you have.

Posted the solution to you problem below.

• Your expression for A3 looks like it is missing items? – Dan Boschen Feb 5 at 13:20
• Indeed. If it is other than the square bracket then I would like to ask what else is missing in A3 of even or A3 of odd? – jomegaA Feb 5 at 13:25
• Also the number of zeros must be computed. I just left it there. – jomegaA Feb 5 at 13:27
• Include it as a complete MATLAB/octave expression and I will upvote – Dan Boschen Feb 5 at 13:28
• Included the complete expression... – jomegaA Feb 5 at 13:50
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)))


• I don't really see that you answered his question? – Dan Boschen Feb 7 at 4:13
• But I would like to know the reason why fftshift is requried to get the correct result. – jomegaA Feb 7 at 8:07
• @DanBoschen Update the code as an answer. – jomegaA Feb 7 at 8:08
• Sorry I still don't see how this answers the question- am I missing that? He is doing convolution with length 2N, you do 2N-1 (how come?). Also it wouldn't make sense to take the absolute value, would it? What if the result is negative? – Dan Boschen Feb 7 at 12:00
• True, but 2N will give an extra 0 to the output sequence. With fftshift, 0 is at the first index of the output. Or, are you trying to bring an idea about circular convolution – jomegaA Feb 7 at 12:05