Linear Convolution Using Circular Convolution

By on

 If you’ve started learning Digital Signal Processing (DSP), you might be wondering how to connect linear convolution and circular convolution. Believe it or not, you can compute linear convolution using circular convolution — and in this post, we’ll show you how using the matrix method!

Let’s take an example and go through the steps.


1. Select N = L+M−1 = 6. For our signals, L=4 and M=3, so N=6. We need N at least as large as L+M−1 to capture the full linear convolution.


2. Zero-pad both signals to length 6. Extend x[n] and h[n] by adding zeros at the end so each has 6 samples. In this case:

  • x[n] = [1, 2, 3, 4, 0, 0]

  • h[n] = [5, 6, 7, 0, 0, 0]
    Now both are of length 6. 


3. Form the circulant convolution matrix from h. We build a 6×6 matrix where each row is a right-shift (circular shift) of the previous row. First, we take h[−n] for our padded h = [5,6,7,0,0,0], this gives

    
Then each subsequent row is the previous row shifted one step to the right (the last element wraps around to the front).

This h[-n] will be our Row 0.

For example, the next rows become

  • Row 1: [6, 5, 0, 0, 0, 7]

  • Row 2: [7, 6, 5, 0, 0, 0]

  • Row 3: [0, 7, 6, 5, 0, 0]

  • Row 4: [0, 0, 7, 6, 5, 0]

  • Row 5: [0, 0, 0, 7, 6, 5].

4. Multiply the circulant matrix by x to get y. Write x as a 6×1 column vector: 
[1  2  3  4  0  0] .


Now multiply the 6×6 matrix by this vector. Each output y[n] is the dot product of row
with the x-vector. For example: 

  • y[0] = 5∗1+0∗2+0∗3+0∗4+7∗0+6∗0=5.

  • y[1] = 6∗1+5∗2+0∗3+0∗4+0∗0+7∗0=16.

  • y[2] = 7∗1+6∗2+5∗3+0∗4+0∗0+0∗0=34.


 Continuing this, we get the full result y = [5,  16,  34,  52,  45,  28].
This exactly matches the standard linear convolution of [1,2,3,4] with [5,6,7].

Comments

  1. Raushan Kumar SinghMay 16, 2025 at 1:13 AM

    Great explanation! Could you clarify why we need to choose N = L + M - 1 specifically? What happens if we pick a smaller N, like N = 4 or 5 in this case?

    ReplyDelete
    Replies
    1. Rohan KumarMay 16, 2025 at 1:21 AM

      In discrete-time DSP, choosing N = L+M-1 ensures that the circular convolution matches the linear convolution without overlap. For the example we have taken in blog, we select N = L+M-1 = 6. This length is necessary because the linear convolution output y[n] has length N = L+M-1 = 6, covering all non-zero output samples from the sum.

      Delete
  2. Kalhan BhatMay 16, 2025 at 1:25 AM

    I noticed the example uses small signals. How does this scale for larger signals, say with lengths L = 100 and M = 50? Does the matrix size become a bottleneck?

    ReplyDelete
    Replies
    1. Rohan KumarMay 16, 2025 at 1:46 AM

      The circulant matrix approach for computing circular convolution (to match linear convolution) scales poorly due to the matrix size, making it computationally inefficient.
      To ensure the circular convolution equals the linear convolution, we choose N = L+M-1 = 149.Both signals are zero-padded to length N = 149. For cyclic convolution, a circulant matrix of size (L+M-1) * (L+M-1) = 149*149 = 22,201 elements. Memory of around 177 KB will be used.
      Storing full n*n matrix requires O(n^2) memory.
      Therefore, for even greater values of length, matrix size will surely become bottleneck.

      Delete
  3. Pradnyesh KeluskarMay 16, 2025 at 1:50 AM

    The circulant matrix structure is fascinating! Is there a way to generate this matrix programmatically, like in Python or MATLAB, for arbitrary h[n]?

    ReplyDelete
    Replies
    1. Rohan KumarMay 16, 2025 at 1:54 AM

      In Python, you can use NumPy to efficiently create a circulant matrix. The scipy.linalg.circulant function is a straightforward option, but you can also build it manually for flexibility.

      Delete
  4. Vishal RainaMay 16, 2025 at 2:14 AM

    How does the circulant matrix method compare to directly computing linear convolution in terms of clarity or computational cost? Are there scenarios where the matrix approach is more intuitive or efficient?

    ReplyDelete
    Replies
    1. Rohan KumarMay 16, 2025 at 2:19 AM

      Clarity Comparison:
      Matrix Method: More intuitive for those familiar with linear algebra or when analyzing the mathematical structure of convolution. It’s especially clear in educational contexts or when exploring the circular-to-linear convolution relationship.
      Direct Method: More intuitive for beginners or practical implementations, as the sliding process is easier to visualize without matrix concepts.
      Winner: Depends on the user. The matrix method excels in theoretical clarity and system analysis, while direct convolution is clearer for practical, hands-on understanding.

      Computational Cost Comparison:
      Matrix Method: Higher cost due to O(N^2) complexity. Direct Method: Lower cost with O(L*M) complexity. Winner: Direct convolution is computationally more efficient.

      Delete
  5. Krishika JalaliMay 16, 2025 at 2:27 AM

    I’m just starting with signal processing. Could you explain in simple terms how a circulant matrix helps convert circular convolution into linear convolution?

    ReplyDelete
    Replies
    1. Rohan KumarMay 16, 2025 at 2:32 AM

      Linear convolution: Imagine sliding a small pattern (like a sound effect or filter) across a longer signal (like music). At each step, you multiply overlapping parts, add them up, and get a new signal. If your signal is 100 samples long and the pattern is 50 samples, the result is 149 samples long.
      Circular convolution: This is similar, but the signal “loops” like a circle. When the pattern slides past the end of the signal, it wraps around to the start.

      A circulant matrix is a special grid of numbers (like a table) where each row is a slightly shifted version of the row above it.
      The circulant matrix acts like a tool that organizes the circular convolution’s looping behavior so it matches the sliding behavior of linear convolution.

      Delete

Post a Comment