Skip to main content
Engineering LibreTexts

7.2: Polynomial Algebras and the DFT

  • Page ID
    2001
  • \( \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}}\)

    In this section we introduce polynomial algebras and explain how they are associated to transforms. Then we identify this connection for the DFT. Later we use polynomial algebras to derive the Cooley-Tukey FFT.

    Polynomial Algebra

    An algebra \(\mathbb{A}\) is a vector space that also provides a multiplication of its elements such that the distributivity law holds (see link for a complete definition). Exampels include the sets off complex or real numbers \(\mathbb{C}\) or \(\mathbb{R}\), and the sets of complex or real polynomials in the variable \(s: \mathbb{C}[s]\) or \(\mathbb{R}[s].\)

    The key player in this chapter is the polynomial algebra. Given a fixed polynomial \(P(s)\) of degree \(\text{deg}(P)=N\), we define a polynomial algebra as the set

    \[\mathbb{C}[s]/P(s)=\{X(s)\,|\,\text{deg}\,(X)\lt\text{deg}(P)\} \nonumber \]

    of polynomials of degree smaller than \(N\) with addition and multiplication modulo \(P\). Viewed as a vector space, \(\mathbb{C}[s]/P(s)\) hence has dimension \(N\).

    Every polynomial \(X(s) \in \mathbb{C}[s]\) is reduced to a unique polynomial \(R(s)\) modulo \(P(s)\) of degree smaller than \(N.\,R(s)\) is computed using division with rest, namely

    \[X(s)=Q(s)P(s)+R(s),\;\text{deg}\,(R)\lt\text{deg}\,(P) \nonumber \]

    Regarding this equation modulo \(P,P(s)\) becomes zero, and we get

    \[X(s)\equiv R(s)\,\text{mod}\,P(s) \nonumber \]

    We read this equation as "\(X(s)\) is congruent (or equal) \(R(s)\) modulo \(P(s)\)." We will also write \(X(s)\,\text{mod}\,P(s)\) to denote that \(X(s)\) is reduced modulo \(P(s)\). Obviously,

    \[P(s) \equiv 0\,\text{mod}\,P(s) \nonumber \]

    As a simple example we consider A=C[s]/(s2-1)A=C[s]/(s2-1)" role="presentation" style="position:relative;" tabindex="0">


    This page titled 7.2: Polynomial Algebras and the DFT is shared under a CC BY license and was authored, remixed, and/or curated by C. Sidney Burrus.

    • Was this article helpful?