Frequency domain multiplication

Question

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

Answer 1

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