# Convolution and Modulation Theorem with Octave Example

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.

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


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.