2
$\begingroup$

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
$\endgroup$
  • $\begingroup$ Please take a look on the result of x and x2. Disregarding 0 they are the same albeit with a shift. $\endgroup$ – jomegaA Feb 7 at 8:12
  • $\begingroup$ 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 $\endgroup$ – user9568523 Feb 7 at 9:18
  • $\begingroup$ A5 = fft([A3 zeros(1, M-length(A3))], M); x3 = fftshift(abs(ifft(A5.* conj(B2), M))) $\endgroup$ – jomegaA Feb 7 at 9:25
1
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Your expression for A3 looks like it is missing items? $\endgroup$ – Dan Boschen Feb 5 at 13:20
  • $\begingroup$ 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? $\endgroup$ – jomegaA Feb 5 at 13:25
  • $\begingroup$ Also the number of zeros must be computed. I just left it there. $\endgroup$ – jomegaA Feb 5 at 13:27
  • $\begingroup$ Include it as a complete MATLAB/octave expression and I will upvote $\endgroup$ – Dan Boschen Feb 5 at 13:28
  • 1
    $\begingroup$ Included the complete expression... $\endgroup$ – jomegaA Feb 5 at 13:50
1
$\begingroup$
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)))


| improve this answer | |
$\endgroup$
  • $\begingroup$ I don't really see that you answered his question? $\endgroup$ – Dan Boschen Feb 7 at 4:13
  • $\begingroup$ But I would like to know the reason why fftshift is requried to get the correct result. $\endgroup$ – jomegaA Feb 7 at 8:07
  • $\begingroup$ @DanBoschen Update the code as an answer. $\endgroup$ – jomegaA Feb 7 at 8:08
  • $\begingroup$ 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? $\endgroup$ – Dan Boschen Feb 7 at 12:00
  • $\begingroup$ 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 $\endgroup$ – jomegaA Feb 7 at 12:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.