1
$\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
  • 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$ Feb 6, 2020 at 17:59

1 Answer 1

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)).

$\endgroup$
7
  • $\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, 2020 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$ Feb 6, 2020 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$ Feb 6, 2020 at 18:56
  • $\begingroup$ Yes that's true. $\endgroup$
    – jomegaA
    Feb 6, 2020 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, 2020 at 19:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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