Understanding Discrete Convolution as Polynomial Multiplication
Convolution is a fundamental operation in digital signal processing
Convolution is a fundamental operation in digital signal processing. It is usually defined by the formula:
DSP books start with this definition, explain how to compute it in detail. We learn how convolution in the time domain is the same as multiplication in the frequency domain via Fourier transform. The operation of finite and infinite impulse response filters is explained in terms of convolution. This becomes the foundation for all digital filter designs. However, the definition of convolution itself remains somewhat esoteric. For me, this definition was always a bit magical until I studied polynomial algebra carefully. Then, the realization happened about how this definition arises naturally. It has remained with me since then. My sister asked me today to explain the convolution operation. Initially, I tried to explain with the typical DSP approach and it was not going anywhere. Finally, I reverted to the polynomial multiplication approach and it became obvious to her. So here it comes.
Consider two simple polynomials:
Compute their product:
If we write h(x) as
then we can match the coefficients of h(x) as:
A pattern seems to be emerging. Let’s get more adventurous with second-degree polynomials:
Here is their product:
h(x) now has a degree of 4 with the coefficients:
given by the identities:
It is time to generalize. We will now look at two polynomials f(x) with degree J and g(x) with degree L.
Their product is the polynomial h(x) with degree J + L:
where the polynomial coefficients are given by the relationship:
with the assumption that f_k and g_k are assumed to be zero for the indices for which they are not specified. i.e. both f_n and g_n are zero for negative n. f_n is 0 for n > J and g_n is zero for n > L. Reader is advised to check that this definition of h_n aligns with the previous results for multiplications for degree 1 and degree 2 polynomials. In fact, if we disregard the issue of convergence of an infinite sum, then with these assumptions of polynomial coefficients being zero outside the indices [0,J] and [0,K] for f(x) and g(x) respectively, there is nothing wrong in writing this formula as:
We can now form the (finite) sequences f[n], g[n], h[n] for the coefficients of the polynomials f(x), g(x) and h(x) and define the convolution operation as:
where the definition has arisen out of treating the sequences as coefficients of the corresponding polynomials.
Summary: If we treat digital sequences as coefficients of polynomials, then their convolution is nothing but the product of corresponding polynomials.
A note on convergence: In general, convergence is a nonissue for finite sequences. However, it becomes relevant for IIR filters as their impulse response has an infinite number of terms. From real analysis, it can be shown that the convolutional sum will converge if the sequences f_n and g_n are absolutely summable. i.e. if the sums:
converge, then their convolution also converges for every n.
