Skip to main content
Engineering LibreTexts

3.1: Introduction

  • Page ID
    1972
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    Learning Objectives

    • Polynomials are important in digital signal processing because calculating the DFT can be viewed as a polynomial evaluation problem and convolution can be viewed as polynomial multiplication

    This is indeed the basis for the important results of Winograd discussed in Winograd's Short DFT Algorithms. A length-\(N\) signal \(x(n)\) will be represented by an \(N-1\) degree polynomial \(X(s)\) defined by:

    \[X(s)=\sum_{n=0}^{N-1}x(n)s^{n} \nonumber \]

    This polynomial \(X(s)\) is a single entity with the coefficients being the values of \(x(n)\). It is somewhat similar to the use of matrix or vector notation to efficiently represent signals which allows use of new mathematical tools.

    The convolution of two finite length sequences, \(x(n)\) and \(h(n)\), gives an output sequence defined by

    \[y(n)=\sum_{k=0}^{N-1}x(k)h(n-k) \nonumber \]

    \[n=0,1,2,...,2N-1\; \; where\; \; h(k)=0\; \; for\; \; k<0 \nonumber \]

    This is exactly the same operation as calculating the coefficients when multiplying two polynomials. The equation is the same as

    \[Y(s)=X(s)H(s) \nonumber \]

    In fact, convolution of number sequences, multiplication of polynomials, and the multiplication of integers (except for the carry operation) are all the same operations. To obtain cyclic convolution, where the indices in the equation are all evaluated modulo \(N\), the polynomial multiplication in the equation is done modulo the polynomial:

    \[P(s)=s^{N}-1 \nonumber \]

    This is seen by noting that \(N=0\, mod\, N\) therefore, \(s^N=1\) and the polynomial modulus is \(s^N=1\).

    Contributor

    • ContribEEBurrus

    This page titled 3.1: Introduction is shared under a CC BY license and was authored, remixed, and/or curated by C. Sidney Burrus.

    • Was this article helpful?