Convolution Calculator

Calculate the discrete convolution of two sequences with step-by-step multiplication and summation.

Enter Sequences

Enter values separated by commas
Enter values separated by commas

Result

Convolution (f * g)[n]
0, 1, 2.5, 4, 1.5
Length: 5
f[n] length 3
g[n] length 3
Result length 5
Sum of result 9

Step-by-Step Solution

(f*g)[n] = Sum of f[k]*g[n-k]

Understanding Discrete Convolution

Convolution is a fundamental mathematical operation in signal processing, linear systems theory, and probability. The discrete convolution of two finite sequences f and g produces a new sequence that represents the "blending" of the two original sequences.

The discrete convolution is defined as: (f * g)[n] = Sum over k of f[k] * g[n - k]. For two finite sequences of lengths M and N, the result has length M + N - 1.

Convolution Formulas and Properties

Discrete Convolution

Sum of products of overlapping elements as one sequence slides over the other.

(f*g)[n] = Sum f[k]*g[n-k]

Commutativity

The order of convolution does not matter.

f * g = g * f

Associativity

Convolution of three sequences can be grouped either way.

(f * g) * h = f * (g * h)

Distributivity

Convolution distributes over addition.

f * (g + h) = f*g + f*h

Output Length

The result of convolving sequences of length M and N.

Length = M + N - 1

Identity Element

Convolving with the unit impulse returns the original signal.

f * delta = f

How Discrete Convolution Works

To compute the convolution manually, follow these steps:

  1. Reverse one of the sequences (typically g).
  2. Slide the reversed sequence across the other sequence.
  3. At each position n, multiply overlapping elements together.
  4. Sum all the products to get the output value at that position.

This "slide, multiply, and sum" process is repeated for each output index from n = 0 to n = M + N - 2.

Example: Convolving [1, 2, 3] with [0, 1, 0.5]

At n=0: f[0]*g[0] = 1*0 = 0. At n=1: f[0]*g[1] + f[1]*g[0] = 1*1 + 2*0 = 1. At n=2: f[0]*g[2] + f[1]*g[1] + f[2]*g[0] = 1*0.5 + 2*1 + 3*0 = 2.5. And so on for n=3 and n=4.

Applications of Convolution

  • Signal processing: Filtering audio, images, and other signals using convolution with filter kernels.
  • Image processing: Blurring, sharpening, and edge detection all use convolution with specific kernels.
  • Probability: The distribution of the sum of two independent random variables is the convolution of their individual distributions.
  • Polynomial multiplication: The coefficients of the product of two polynomials are the convolution of their coefficient sequences.
  • Deep learning: Convolutional Neural Networks (CNNs) use convolution layers as their fundamental building block.
  • Control systems: The output of a linear time-invariant system is the convolution of the input with the impulse response.

Convolution vs. Correlation

Convolution and cross-correlation are closely related but differ in one key aspect: convolution reverses one signal before the slide-multiply-sum process, while correlation does not. Cross-correlation measures similarity between two signals at different offsets, while convolution computes the system output.

Efficient Computation

For long sequences, direct convolution (O(M*N) operations) can be slow. The Fast Fourier Transform (FFT) allows convolution to be computed in O(N log N) time by multiplying the Fourier transforms and then taking the inverse transform. This is known as the convolution theorem.