Convolution

Convolution — Mathematical Operation Between Two Discrete‑Time Signals

Convolution is a key operation in DSP (Digital Signal Processing). It combines two signals to produce a third signal.

Basic Idea

• One signal is fixed → impulse response h[n]
• The other signal slides over it → input signal x[n]
• At each position, multiply overlapping samples and sum them
• This produces the output y[n]

Convolution is used in:

• Pattern matching
• Weighted averaging
• Filtering
• Image smoothing or sharpening

Mathematical Definition

y[n] = Σ (from k = -∞ to ∞) x[k] * h[n — k]

For finite-length (practical DSP):

y[n] = Σ (from k = 0 to N-1) x[k] * h[n — k]

Where:

• x[n] = input audio/speech/music
• h[n] = impulse response (system behavior)
• y[n] = processed output

Example

x[n] = {1, 2, 1} h[n] = {1, -1}

Length of x = 3 Length of h = 2

Output length = 3 + 2–1 = 4

Step-by-Step Computation

y[0]= x[0]*h(0) + x[1]*h[-1] + x[2]*h[-2] = 1*1+2*0+1*0  = 1
y[1]= x[0]*h(1) + x[1]*h[0]  + x[2]*h[-1] = 1*-1+2*1+1*0 = 1
y[2]= x[0]*h(2) + x[1]*h[1]  + x[2]*h[0]  = 1*0+2*-1+1*1 = -1
y[3]= x[0]*h(3) + x[1]*h[2]  + x[2]*h[1]  = 1*0+2*0+1*-1 = -1

Final Output

y[n] = {1, 1, -1, -1}

#include <stdio.h>
#include <stdlib.h>

// y[n] = x[n] * h[n-k]
void convulation(int *x, int *y, int *h, int xLen, int oLen, int hLen)
{
    for(int n = 0; n < oLen; n++)
    {
        y[n] = 0;
        for(int k = 0; k < hLen; k++)
        {
            if(((n - k) >= 0) && ((n - k) < xLen))
            {
                y[n] += x[n - k] * h[k];
            }
        }
    }
}

int main()
{
    int x[3] = {1, 2, 1};
    int h[2] = {1, -1};
    int y[4];

    int xLen = sizeof(x) / sizeof(int);
    int hLen = sizeof(h) / sizeof(int);
    int oLen = xLen + hLen - 1;

    convulation(x, y, h, xLen, oLen, hLen);

    for(int n = 0; n < oLen; n++)
    {
        printf("y[%d] = %d\n", n, y[n]);
    }
}

1. Linear convolution — Its standard convolution used when filter length is small

Fir Filters

Small echos

Equalizers

Basic filters

2. Circular convolution — Its uses zero padding to perform circular convolution and apply modulo and used for large lengths

FFT processing

Block conversion

Fast filtering

Circular convolution:

x[n] = {1,2,3,4} h[n] = {4,3,2,1}

n = 0 =>  (0−0) mod 4 = 0 → h[0] = 4
          (0−1) mod 4 = 3 → h[3] = 1
          (0−2) mod 4 = 2 → h[2] = 2
          (0−3) mod 4 = 1 → h[1] = 3
n = 1 =>  (1−0) mod 4 = 1 → h[1] = 3
          (1−1) mod 4 = 0 → h[0] = 4
          (1−2) mod 4 = 3 → h[3] = 1
          (1−3) mod 4 = 2 → h[2] = 2
n = 2 =>  (2−0) mod 4 = 2 → h[2] = 2
          (2−1) mod 4 = 1 → h[1] = 3
          (2−2) mod 4 = 0 → h[0] = 4
          (2−3) mod 4 = 3 → h[3] = 1
n = 2 =>  (3−0) mod 4 = 3 → h[3] = 1
          (3−1) mod 4 = 2 → h[2] = 2
          (3−2) mod 4 = 1 → h[1] = 3
          (3−3) mod 4 = 0 → h[0] = 4

Y[0] = 1 * 4 + 2 * 1 + 3 * 2 + 4 * 3 = 24 
Y[1] = 1 * 3 + 2 * 4 + 3 * 1 + 4 * 2 = 22
Y[2] = 1 * 2 + 2 * 3 + 3 * 4 + 4 * 2 = 28 
Y[3] = 1 * 1 + 2 * 2 + 3 * 3 + 4 * 4 = 30

          Y[n] = {24,22,28,30}

Circular convolution in time domain is equal to multiplication in frequency domain

y[n]=x[n]⊛h[n]

“DFT”{y[n]}=X[k]⋅H[k]

y[n]=”IDFT”(X[k]H[k])

#include <stdio.h>
#include <stdlib.h>

// y[n] = x[n] * h[n-k]
void Circular_conv(int *x, int *y, int *h, int xLen, int oLen, int hLen)
{
    for(int n = 0; n < oLen; n++)
    {
        y[n] = 0;
        for(int k = 0; k < hLen; k++)
        {
            //Theroritically (n-k mod N) but mathematically 
          // it will result negative values   
            int idx = (n + oLen - k) % xLen; 
            y[n] += x[idx] * h[k];

        }
    }
}

int main()
{
    int x[4] = {1, 2, 3, 4};
    int h[4] = {4, 3, 2, 1};
    int y[4];

    int xLen = sizeof(x) / sizeof(int);
    int hLen = sizeof(h) / sizeof(int);
    int oLen = xLen;

    Circular_conv(x, y, h, xLen, oLen, hLen);

    for(int n = 0; n < oLen; n++)
    {
        printf("y[%d] = %d\n", n, y[n]);
    }
}

Computational complexity

Sample codes

Fs = 8000; 
t = 0:1/Fs:1;

% Input: mix of low and high frequency
x = sin(2*pi*100*t) + 0.5*sin(2*pi*2000*t);

% Impulse response: 5-point moving average
h = ones(1,5)/5;

% Convolution
y = conv(x, h, 'same');

% Plot
figure;
subplot(2,1,1);
plot(t, x);
title('Original Signal (100 Hz + 2000 Hz)');
xlabel('Time (s)'); ylabel('Amplitude');

subplot(2,1,2);
plot(t, y);
title('Filtered Signal (After Convolution)');
xlabel('Time (s)'); ylabel('Amplitude');

Filtered convolution output

Basically moving average filter will act as low pass filter so 200 Hz frequency gets attenuated and results only 100 Hz frequency