0
$\begingroup$

I am confused why zero-padding in the frequency domain does not result in linear convolution in the time-domain using the relationship:

$$corr(a,b) = ifft(fft(a) fft(b))$$

See my process below for more details:

1.

$$a = \{a_0, a_1,\dots,a_{N-1}\},\;\;\;\; w = \mathrm{rect\{N\}}$$ $$\boxed{y_c = \mathrm{conv}(a, w)}$$

2. $$M=2N-1$$ $$X_a = \mathrm{FFT}(a, M),\;\;\;\;W_a = \mathrm{FFT}(w, M)$$ $$\boxed{y_f=\mathrm{IFFT}\left(X_a * W_a\right)}$$

3. $$y_c=y_f$$

  • I am aware that zero-padding in frequency domain is interpolation in time- domain.

4.

$$X_b = \mathrm{FFT}(a, N),\;\;\;\;W_b = \mathrm{FFT}(w, N)$$

  • Now zeropad the $X_b$ and $W_b$ the spectrum to size $M$
  • Perform frequency domain multiplication
  • Take inverse transform $$\boxed{y_{zf}=\mathrm{IFFT}(X_{zb} * W_{zb})}$$

where, $X_{zb}$ and $W_{zb}$ are zero-padded spectrum of $X_b$ and $W_b$


Results: $y_{zf} \neq \left(y_c\;|\; y_f\right)$

Attached MATLAB example below

clear all;

clear;

M = 7;
N = 4;

A = 1:4;
window = ones(1, 4);

y_c = conv(A, window)

A3 = fft(A, M); 
W3 = fft(window, M); 

y_t = ifft(A3.*W3)        % y_t = y_c


A1 = fft(A, N); 
middle_a = A1(N/2+1)/2; 
A2 = [A1(1:N/2) middle_a zeros(1, M-length(A1)-1) middle_a A1(N/2+2:end)];

W1 = fft(window, N);
middle_w = W1(N/2+1)/2;
W2 = [W1(1:N/2) middle_w zeros(1, M-length(W1)-1) middle_w W1(N/2+2:end)];


y_f = ifft(A2.*W2, M)     % Expected y_f = y_t = y_c but y_f gives bad results
$\endgroup$
  • 1
    $\begingroup$ 1. Ask a signal processing question, please. 2. "gives bad results" is not really helpful at all. What did you expect, what are you getting, how's that different. Why did you choose something this complicated to test your algorithm, instead of, say, two all-zero-but-a-single-1 vectors? Do a bit of debugging. $\endgroup$ – Marcus Müller Feb 6 at 17:59
1
$\begingroup$

The result is expected as you are simply appending zeros to the product

fft(A1).*fft(A2)

Which does the time domain interpolation as you describe. However the ifft of the above product results in a series of constant values in the time domain since it is a circular convolution. Appending additional zeroes simply interpolates this for more constant values (in addition to a scaling factor).

To achieve the result you desire, which is the linear correlation of the two vectors, you must interpolate in the frequency domain prior to the multiplication (not insert zeros). This is exactly what occurs if you review the result of fft(A,M) which appends zeros in the time domain prior to taking the FFT, resulting in frequency domain interpolation.

Essentially, the process is to zero-pad the time domain samples prior to circular convolution, which results in linear convolution. Zero padding in frequency is not actually introduced in the process ifft(fft(A,M).*fft(B,M)).

|improve this answer|||||
$\endgroup$
  • $\begingroup$ A1 is FFT of sequence A of length $N$. A2 is zero-padded version of A1. Similarly W1 and W2. $\endgroup$ – jomegaA Feb 6 at 18:52
  • 1
    $\begingroup$ @jomega That's right. But zero padding and then multiplying prior to the IFFT interpolates the time domain result you would get if you didn't zero pad. Hence it is not an approach to achieve linear convolution. You are simply interpolating in time the circular convolution result. Hence the answer you got (all constants) $\endgroup$ – Dan Boschen Feb 6 at 18:54
  • 1
    $\begingroup$ Notice how fft(A, M) results in interpolated frequency samples. When you multiply those and then take the IFFT of that sequence without any zero padding, the result is what you would get with linear convolution.. It's the identical process to zero padding in time prior to doing a circular convolution--- which is what is required to make that a linear convolution--- not zero pad in frequency. $\endgroup$ – Dan Boschen Feb 6 at 18:56
  • $\begingroup$ Yes that's true. $\endgroup$ – jomegaA Feb 6 at 18:59
  • $\begingroup$ I am not a signal processing guy but what inspired to do that programming is, If there is a structure with N stages, the output of the first stage in frequency domain say $Y_1(\omega)$ and want to calculate the output of the next stage $Y_2(\omega)=Y_1(\omega) * H_2(\omega)$...but then what I was thinking was wrong. $\endgroup$ – jomegaA Feb 6 at 19:28

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.