2
$\begingroup$

Apparently these 3 terms are some how similar but what is exact difference between them?please kindly explain with example, because the number of terms in result/output are different in all 3 cases

Especially in context of signal processing, when do we need to multiplication, when we need to do convolution and when we need to do polynomial multiplication?

$\endgroup$
2
  • 1
    $\begingroup$ All three terms might have different definitions, depending on the domain where you use them. They are indeed related. Could you tell us more details about: what definitions you got, what makes you feel they are different or equal? $\endgroup$ Apr 12, 2020 at 18:13
  • 1
    $\begingroup$ you multiply polynomials using convolution, as in [1 1] convolved with [1 1] is [1 2 1] similar to (x+1)(x+1) $\endgroup$ Apr 12, 2020 at 19:13

2 Answers 2

2
$\begingroup$

The convolution theorem is a fundamental signal processing property that links the frequency and time domains. Specifically convolution in one domain is multiplication in the other. Often this can be used to simplify the number of operations required for solving signal processing problems. The utility of this is amplified given the significance of the Fast Fourier Transform in how efficiently it can be used to translate between domains.

With this in mind, consider that the output of a linear system in time is related to its input using convolution:

$$y(t) = x(t)\star h(t)$$

Where $\star$ represents the convolution operator, $x(t)$ is the input and $h(t)$ is the impulse response of the system.

If we took the Fourier Transform of $x(t)$ and $h(t)$, then this same problem is solved using an element by element product:

$$Y(\omega) = X(\omega)H(\omega)$$

Similarly we use convolution to multiply polynomials by convolving the coefficients. So we could use the FFT for polynomial multiplication as follows:

Consider the simple example of a product of $x^3 + 2x^2 - 4x +1$ with $5x^2+3$

This is solved by convolving the coefficients as:

$$[1, 2, -4, 1] \star [5, 0, 3] = [5, 10, -17, 11, -12, 3]$$

Resulting in $5x^5 + 10x^4 -17x^3+11x^2-12x+3$

Similarly this could be done in the frequency domain with FFT processing, but to do this properly the coefficients of the polynomial are loaded starting with the lowest power of x and we must zero-pad out to 6 samples that we would expect in the result:

FFT of $[1,-4, 2,1,0,0] = [0, -3+1.73j, 3+5.20j, 6, 3-5.2j, -3-1.73j]$

FFT of $[3,0,5,0,0,0] = [8, 0.5-4.33j, 0.5+4.33j, 8, 0.5-4.33j, 0.5+4.33j]$

Element by element product of the FFTs: $[0, 6+13.85j, -21+15.59j, 48, -21-15.59j, 6-13.95j]$

Inverse FFT of the product: $[3, -12, 11, -17, 10, 5]$

Corresponding to $5x^5+10x^4-17x^3+11x^2-12x+3$

For something this small as in this example, it would be more efficient to do the convolution directly, but as the length of the polynomials grow, the FFT approach becomes significantly more efficient.

$\endgroup$
4
  • $\begingroup$ What do you mean by" element by element product"?do you mean simple multiplication or polynomial multiplication? $\endgroup$
    – DSP_CS
    Apr 13, 2020 at 13:06
  • $\begingroup$ In contrast to a dot product which is a sum of products. So element by element product is [a b c] x [c d e] = [ab bd cd] $\endgroup$ Apr 13, 2020 at 13:22
  • $\begingroup$ Do you mean,polynomial multiplication is something different from both dot product and element by element multiplication? $\endgroup$
    – DSP_CS
    Apr 13, 2020 at 16:42
  • $\begingroup$ Yes with regards to the coefficients of the polynomial—- do you see from above that polynomial multiplication is the convolution of the coefficients? $\endgroup$ Apr 13, 2020 at 16:44
4
$\begingroup$

Sometimes academic explanations are very theoretical, to the point we don't realize we already know what they are talking about. I believe this is the case for sequence, polynomial and convolution. Ordinary people use them all the time, there is nothing new.

A number is a polynomial

For example, the number $\small 412$ is actually the short form of the polynomial $\small 4\times10^{2}+1\times10^{1}+2\times10^{0}$. But we don't talk about $\small 10^2$, we just use hundreds. Similarly we don't talk about coefficient $\small 4$, but about digit $\small 4$.

This is how our decimal numeral system is built. Numeral systems with other bases are built the same way. The polynomial form gives the value of the number: $\small 100$ in base 10 is $\small 1 \times 10^2$, but $\small 100$ in base 2 is $\small 1 \times 2^2$.

Thus we know very well what is a polynomial, and we also know how to perform some operations on them, like addition or multiplication

Polynomial multiplication

The long form of the multiplication of two numbers, e.g. $\small 412 \times 21$, is the multiplication of the corresponding polynomials:

$$\small \begin{align*} 412\times21= & \; \left(4\times10^{2}+1\times10^{1}+2\times10^{0}\right)\left(2\times10^{1}+1\times10^{0}\right)\\ = & \; (4\times10^{2})(2\times10^{1})+(4\times10^{2})(1\times10^{0})\\ & \; + (1\times10^{1})(2\times10^{1})+(1\times10^{1})(1\times10^{0})\\ & \; + (2\times10^{0})(2\times10^{1})+(2\times10^{0})(1\times10^{0})\\ = & \; 8\times10^{3}+(4+2)\times10^{2}+(1+4)\times10^{1}+2\times10^{0}\\ = & \; 8\times10^{3}+6\times10^{2}+5\times10^{1}+2\times10^{0}\\ = & \; 8652 \end{align*}$$

Convolution of sequences

Of course nobody carry out an integer multiplication using polynomials, we use only the coefficients (the digits). We use a multiplication algorithm involving 1x1 digit products, row shifts and column sums (known as grade school multiplication in the US):

$$\small \begin{array}{ccccccc} & & 4 & & 1 & & 2\\ & & & & 2 & & 1\\ \hline & & (1\times4) & & (1\times1) & & (1\times2)\\ (2\times4) & & (2\times1) & & (2\times2)\\ \hline 8 & & 6 & & 5 & & 2 \end{array}$$

You might be surprised, but this algorithm is the one used to perform the convolution of the two sequences of coefficients. To clarify, let's replace the values by by their origin in term of elements of sequences:

$$\small \begin{array}{ccccccc} & & a[2] & & a[1] & & a[0]\\ & & & & b[1] & & b[0]\\ \hline & & (b[0]\times a[2]) & & (b[0]\times a[1]) & & (b[0]\times a[0])\\ (b[1]\times a[2]) & & (b[1]\times a[1]) & & (b[1]\times a[0])\\ \hline 8 & & 6 & & 5 & & 2 \end{array}$$

If we name $\small y$ the sequence of the result, we can see a pattern:

$$\small \begin{align} y[0] &= b[0] a[0] + b[1] a[-1] \\ y[1] &= b[0] a[1] + b[1] a[0] \\ y[2] &= b[0] a[2] + b[1] a[1] \\ y[3] &= b[0] a[3] + b[1] a[2] \end{align}$$

This can be generalized in:

$$\small y[n] = \sum_{k} b[k] a[n-k]$$

This is the equation of the convolution of sequences $\small a$ and $\small b$. So anybody who can read this page has been performing convolutions since the age of 7 or so.

For the sake of completeness, there are --strictly equivalent but,-- more efficient ways than this one (brute force) to perform the convolution:

Now we can build a new polynomial with coefficients from the sequence $\small y$, and this polynomial is the same than the one calculated earlier from polynomials multiplication:

$$\small 8 \times 10^{3} + 6 \times 10^{2} + 5 \times 10^{1} + 2 \times 10^{0} = 8652 $$

The resulting polynomial has order 3 (the order is the highest exponent of 10). This order is the sum of the input polynomial orders 2 and 1.

Polynomial multiplication and sequence convolution

To perform the multiplication of two numbers, we ignore the fact they are actually polynomials, we just use the coefficients of these polynomials, and instead of multiplying the polynomials we actually perform a sequence convolution.

Apparently these 3 terms [convolution, multiplication and polynomial multiplication] are somehow similar but what is exact difference between them?

  • Multiplication is the general term for the operation resulting in a product. For example when performing the convolution we multiply coefficients by pairs.

  • Polynomial multiplication refers to a multiplication where operands are polynomials, this is what we could do to multiply two numbers.

  • Convolution is an operation where operands are sequences, this is what we actually do when multiplying two numbers using only the digits, not the polynomials.

Polynomial multiplication is not the same than sequence convolution. One is used when operands are polynomials, the other is used when operands are sequences.

They are not interchangeable, but both operations are linked: Instead of performing the multiplication of two polynomials we can perform a convolution on the sequences of their coefficients and vice-versa.

Example

If we need to multiply these two polynomials of variable $\small x$:

$$\small \begin{align} p(x) &= 42 x^{6} + 7 x^{5} + 34 x^{4} + 9 x^{3} + 89 x^{2} + 27 x^{1} + 2 x^{0} \\ q(x) &= 2 x^{5} + 8 x^{4} + 51 x^{3} + 48 x^{2} + 31 x^{1} + 67 x^{0} \end{align} $$

we could expand the product, but this would be a bit tedious. Instead we can use the convolution of their coefficients. First we create sequences of coefficients:

$$\small \begin{align} a &= [42, 7, 34, 9, 89, 27, 2] \\ b &= [2, 8, 51, 48, 31, 67] \end{align} $$

and use the convolution function of MATLAB or Numpy:

c = np.convolve(a, b)

This returns a sequence:

[84, 350, 2266, 2663, 3622, 5888, 6714, 8222, 4760, 6896, 1871, 134]

And we can transform this sequence into a polynomial, which is also the product of $p(x)$ and $q(x)$:

$$\small\begin{align} r(x) = & 84 x^{11} + 350 x^{10} + 2266 x^9 + 2663 x^8 \\ & + 3622 x^7 + 5888 x^6 + 6714 x^5 + 8222 x^4 \\ & + 4760 x^3 + 6896 x^2 + 1871 x^1 + 134 x^0 \end{align} $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.