How to obtain the output sequence of linear convolution through circular convolution

To obtain the output sequence of linear convolution using circular convolution, you can follow these steps. This approach leverages the circular convolution property and the use of zero-padding to simulate the effects of linear convolution.

Steps to Obtain Linear Convolution via Circular Convolution:

1. Zero-Pad the Sequences:

   • Given two sequences x[n]x[n]x[n] and h[n]h[n]h[n] of lengths NxN_xNx? and NhN_hNh? respectively, zero-pad both sequences to a length of N=Nx+Nh−1N = N_x + N_h - 1N=Nx?+Nh?−1. This ensures that circular convolution (which typically results in periodic extension) behaves like linear convolution over a finite range.

   x′[n]={x[n]for 0≤n<Nx0for Nx≤n<Nx'[n] = \begin{cases} x[n] & \text{for } 0 \leq n < N_x \\ 0 & \text{for } N_x \leq n < N \end{cases}x′[n]={x[n]0?for 0≤n<Nx?for Nx?≤n<N?

   h′[n]={h[n]for 0≤n<Nh0for Nh≤n<Nh'[n] = \begin{cases} h[n] & \text{for } 0 \leq n < N_h \\ 0 & \text{for } N_h \leq n < N \end{cases}h′[n]={h[n]0?for 0≤n<Nh?for Nh?≤n<N?

2. Perform Circular Convolution:

   • Compute the circular convolution yc[n]y_c[n]yc?[n] of the zero-padded sequences x′[n]x'[n]x′[n] and h′[n]h'[n]h′[n] using the discrete Fourier transform (DFT) and inverse DFT (IDFT):

   Yc[k]=X′[k]⋅H′[k]Y_c[k] = X'[k] \cdot H'[k]Yc?[k]=X′[k]⋅H′[k]

   yc[n]=IDFT{Yc[k]}y_c[n] = \text{IDFT}\{ Y_c[k] \}yc?[n]=IDFT{Yc?[k]}

   Where X′[k]X'[k]X′[k] and H′[k]H'[k]H′[k] are the DFTs of x′[n]x'[n]x′[n] and h′[n]h'[n]h′[n], respectively.

3. Extract the Output Sequence:

   • After computing the circular convolution yc[n]y_c[n]yc?[n], extract the first Nx+Nh−1N_x + N_h - 1Nx?+Nh?−1 samples to obtain the output sequence y[n]y[n]y[n] of linear convolution:

   y[n]={yc[n]}0Nx+Nh−2y[n] = \{ y_c[n] \}_{0}^{N_x + N_h - 2}y[n]={yc?[n]}0Nx?+Nh?−2?

Example:

Consider x[n]={1,2,3}x[n] = \{1, 2, 3\}x[n]={1,2,3} and h[n]={4,5}h[n] = \{4, 5\}h[n]={4,5}.

• Zero-pad x[n]x[n]x[n] and h[n]h[n]h[n] to the length N=4N = 4N=4 (since Nx+Nh−1=3+2−1=4N_x + N_h - 1 = 3 + 2 - 1 = 4Nx?+Nh?−1=3+2−1=4):

  x′[n]={1,2,3,0}x'[n] = \{1, 2, 3, 0\}x′[n]={1,2,3,0} h′[n]={4,5,0,0}h'[n] = \{4, 5, 0, 0\}h′[n]={4,5,0,0}

• Compute the DFTs:

  X′[k]={6,−1+2j,−1,−1−2j}X'[k] = \{6, -1 + 2j, -1, -1 - 2j\}X′[k]={6,−1+2j,−1,−1−2j} H′[k]={9,−1+5j,4,−1−5j}H'[k] = \{9, -1 + 5j, 4, -1 - 5j\}H′[k]={9,−1+5j,4,−1−5j}

• Perform circular convolution in the frequency domain:

  Yc[k]=X′[k]⋅H′[k]={54,−5+13j,−4,−5−13j}Y_c[k] = X'[k] \cdot H'[k] = \{54, -5 + 13j, -4, -5 - 13j\}Yc?[k]=X′[k]⋅H′[k]={54,−5+13j,−4,−5−13j}

• Compute the inverse DFT to obtain yc[n]y_c[n]yc?[n]:

  yc[n]={6,23,26,15}y_c[n] = \{6, 23, 26, 15\}yc?[n]={6,23,26,15}

• Extract the first 3 samples (since Nx+Nh−1=3+2−1=4N_x + N_h - 1 = 3 + 2 - 1 = 4Nx?+Nh?−1=3+2−1=4) to get the linear convolution output y[n]y[n]y[n]:

  y[n]={6,23,26}y[n] = \{6, 23, 26\}y[n]={6,23,26}

This approach effectively uses circular convolution with zero-padding to simulate the linear convolution process, allowing you to obtain the correct output sequence y[n]y[n]y[n] as if computed directly through linear convolution.