3.1: Introduction

Fast Fourier Transforms · LibreTexts

0%

Contents

    Text

    Size
    100%
    Theme
    Typeface
    Line length
    Spacing

    Read aloud

    How

    Speed: 1×
    Light up
    Highlight

    Symbols: Mulberry Symbols, © 2018–2026 Steve Lee, CC BY-SA 4.0 (licence, the set), the site's own copies.

    From LibreTexts, under CC BY, as the source states it; its equations are written in TeX, which the PDF shows typeset. This page at LibreTexts.

    3.1: Introduction

    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 was last modified on Sun, 22 May 2022 22:24:41 GMT and is shared under a CC BY license and was authored, remixed, and/or curated by C. Sidney Burrus.