Convolution and Modulation Theorem with Octave Example

Question

As far as I know, convolution theorem stated that $$ x[n] * y[n] = X(e^{j \omega}) Y(e^{j \omega}) $$ $$ X(e^{j \omega}) * Y(e^{j \omega}) = x[n] y[n] $$

I tried a simple experiment using GNU Octave which code is provided in the following

x = zeros(1,31);
h = zeros(1,31);
x(14:18) = [20 -30 40 -30 20];
h(14:18) = [1/5 1/5 1/5 1/5 1/5];

So now, we have

x =

 Columns 1 through 20:

    0    0    0    0    0    0    0    0    0    0    0    0    0   20  -30   40  -30   20    0    0

 Columns 21 through 31:

    0    0    0    0    0    0    0    0    0    0    0

h =

 Columns 1 through 10:

   0.00000   0.00000   0.00000   0.00000   0.00000   0.00000   0.00000   0.00000   0.00000   0.00000

 Columns 11 through 20:

   0.00000   0.00000   0.00000   0.20000   0.20000   0.20000   0.20000   0.20000   0.00000   0.00000

 Columns 21 through 30:

   0.00000   0.00000   0.00000   0.00000   0.00000   0.00000   0.00000   0.00000   0.00000   0.00000

 Column 31:

   0.00000

Next, the following code demonstrates whether $ x[n] * y[n] = X(e^{j \omega}) Y(e^{j \omega}) $

conv_result = round( conv(x,h,shape="same") );
freq_product_result = round( ifft( fft(x) .* fft(h) ) );

Then the results are

conv_result =

 Columns 1 through 25:

   0   0   0   0   0   0   0   0   0   0   0   4  -2   6   0   4   0   6  -2   4   0   0   0   0   0

 Columns 26 through 31:

   0   0   0   0   0   0

freq_product_result =

 Columns 1 through 25:

   0   6  -2   4   0  -0   0  -0   0  -0   0  -0  -0   0  -0  -0   0   0  -0   0  -0   0  -0   0  -0

 Columns 26 through 31:

  -0   4  -2   6   0   4

Indeed both have the $\{4 , -2 , 6 , 0 , 4 , 0 , 6, -2, 4\}$ pattern, but the pattern doesn't appear at the same column index. Is my experiment correct? Should both the result be identical? I think I still don't understand the concept completely.

Answer 1

You are making the standard mistake of computing a linear convolution by performing a circular convolution which is implemented with an inverse DFT of wrong size.

Now assume that your signals $x[n]$ and $h[n]$ are of length $L_x$ and $L_h$ samples each. Then the discrete-convolution of $x[n]$ with $h[n]$ would produce the new sequence $$y[n] = h[n] \star x[n]$$ whose length is $$L_y = L_x + L_h - 1.$$ This convolution is also referred to as the linear convolution of $x[n]$ and $h[n]$.

According to the well known theorem of DTFT the linear convolution of $x[n]$ and $h[n]$ is related to the multiplication of their DTFTs as: $$ h[n] \star x[n] \longleftrightarrow X(e^{j \omega})H(e^{j \omega})$$ where $H(e^{j \omega})$ and $X(e^{j \omega})$ are the theoretical DTFTs of $x[n]$ and $h[n]$.

The practical verification of this theorem is based on the multiplication of DFTs $X[k]$ and $H[k]$, however, which computes a circular convolution instead of a linear one. So one has to be careful in selecting the correct length for both forward and inverse DFT sizes.

In your implementation you have selected a shorter than necessary length so that there will be aliasing. Apart from specific instances aliasing should be avoid. The following MATLAb/Octave code shows the corrected version.

Lx = 12;           % Length of x[n]
Lh = 15;           % Length of h[n]
Ly = Lx + Lh -1;   % Length of y[n] = x[n]*h[n]

x = randn(1,Lx);   % sequence x[n]
h = randn(1,Lh);   % sequence h[n]

y1 = conv( x, h ); % y[n] computed in time domain by direct linear convolution
y2 = real( ifft( fft(x,Ly).*fft(h,Ly) , Ly) ); % y[n] computed by DFT method

Answer 2

The question whether $e^{j\omega}$ begins with $\omega = 0$ or with $\omega = - \frac{f_{Nyquist}}2$ is purely a question of convention; in your case, that convention leads to a shift.