1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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
$\endgroup$
0
$\begingroup$

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.

$\endgroup$

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.