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">
\[\mathbb{A}=\mathbb{C}[s]/(s^2-1) \nonumber \]
which has dimension \(2\). A possible basis is b=(1,s)b=(1,s)" role="presentation" style="position:relative;" tabindex="0">\(b=(1,s)\). In \(\mathbb{A}\), for example,
\[s\cdot (s+1)=s^2+s\equiv s+1\; \text{mod}\; (s^2-1) \nonumber \]
obtained through division with rest
\[s^2+s=1\cdot (s^2-1)+(s+1) \nonumber \]
or simply by replacing \(s^2\) with 1 (since \((s^2-1)=0\) implies \(s^2=1\)).
Chinese Remainder Theorem (CRT)
Assume \(P(S)=Q(s)R(s)\) factors into two coprime (no common factors) polynomials \(Q\) and \(R\). Then the Chinese remainder theorem (CRT) for polynomials is the linear mapping, more precisely, isomorphism of algebras or isomorphism of \(\mathfrak{A}\)-modules.
\[\Delta : \mathbb{C}[s]/P(s)\rightarrow \mathbb{C}[s]/Q(s)\oplus \mathbb{C}[s]/R(s) \nonumber \]
\[X(s) \mapsto (X(s)\: \text{mod}\: Q(s),X(s)\: \text{mod}\: R(s)) \nonumber \]
Here, \(\oplus\) is the Cartesian product of vector spaces with elementwise operation (also called outer direct sum). In words, the CRT asserts that computing (addition, multiplication, scalar multiplication) in \(\mathbb{C}[s]/P(s)\) is equivalent to computing in parallel in \(\mathbb{C}[s]/Q(s)\) and \(\mathbb{C}[s]/R(s)\).
If we choose bases \(b,c,d\) in the three polynomial algebras, then \(\Delta\) can be expressed as a matrix. As usual with linear mapping, this matrix is obtained by mapping every element of \(b\) with \(\Delta\), expressing it in the concatenation \(c\cup d\) of the bases \(c\) and \(d\), and writing the results into the columns of the matrix.
As an example, we consider again the polynomial P(s)=s2-1=(s-1)(s+1)P(s)=s2-1=(s-1)(s+1)" role="presentation" style="position:relative;" tabindex="0">
\[P(s)=s^2-1=(s-1)(s+1) \nonumber \]
and the CRT decomposition
\[\Delta :\mathbb{C}[s]/(s^2-1)\rightarrow \mathbb{C}[s]/(s-1)\oplus \mathbb{C}[s]/(s+1) \nonumber \]
As bases, we choose \(b=(1,x),c=(1),d=(1).\Delta (1)=(1,1)\) with the same coordinate vector in \(c\cup d=(1,1)\). Further, because of \(x\equiv 1\: \text{mod}\: (x-1)\) and \(x\equiv -1\: \text{mod}\: (x+1)\), \(\Delta (x)=(x,x)\equiv (1,-1)\) with the same coordinate vector. Thus \(\Delta\) in matrix form is the so-called butterfly matrix, which is a DFT of size 2:
\[DFT_2=\begin{bmatrix} 1 & 1\\ 1 & -1 \end{bmatrix} \nonumber \]
Polynomial Transforms
Assume \(P(s)\in \mathbb{C}[s]\) has pairwise distinct zeros α=(α0,⋯,αN-1)α=(α0,⋯,αN-1)" role="presentation" style="position:relative;" tabindex="0">\(\alpha =\alpha _0,...,\alpha _N-1\). Then the CRT can be used to completely decompose C[s]/P(s)C[s]/P(s)" role="presentation" style="position:relative;" tabindex="0">\(\mathbb{C}[s]/P(s)\) into its spectrum:
\[\Delta :\mathbb{C}[s]/P(s)\rightarrow \mathbb{C}[s]/(s-\alpha _0)\oplus ...\oplus \mathbb{C}[s]/(s-\alpha _{N-1}) \nonumber \]
\[X(s)\mapsto (X(s)\: \text{mod}\: (s-\alpha _0),...,X(s)\: \text{mod}\: (s-\alpha _{N-1}))=(s(\alpha _0),...,s(\alpha _{N-1})) \nonumber \]
If we choose a basis b=(P0(s),⋯,PN-1(s))b=(P0(s),⋯,PN-1(s))" role="presentation" style="position:relative;" tabindex="0">\(b=(P_0(s),...,P_{N-1}(s))\) in C[s]/P(s)C[s]/P(s)" role="presentation" style="position:relative;" tabindex="0">\(\mathbb{C}[s]/P(s)\) and bases bi=(1)bi=(1)" role="presentation" style="position:relative;" tabindex="0">\(b_i=(1)\) in each \(\mathbb{C}[s]/(s-\alpha _i)\) then \(\Delta\), as a linear mapping, is represented by a matrix. The matrix is obtained by mapping every basis element PnPn" role="presentation" style="position:relative;" tabindex="0">\(P_n,\: 0\leq n< N\), and collecting the results in the columns of the matrix. The result is:
\[\mathfrak{P}_{b,\alpha }=\left [ P_n(\alpha _k) \right ]_{0\leq k,n< N} \nonumber \]
and is called the polynomial transform for A=C[s]/P(s)A=C[s]/P(s)" role="presentation" style="position:relative;" tabindex="0">\(\mathfrak{A}=\mathbb{C}[s]/P(s)\) with basis \(b\)
If, in general, we choose bi=(βi)bi=(βi)" role="presentation" style="position:relative;" tabindex="0">\(b_i=(\beta _i)\) as spectral basis, then the matrix corresponding to the decomposition equation is the scaled polynomial transform
\[\text{diag}_{0\leq k< N}(1/\beta _n)\mathfrak{P}_{b,\alpha } \nonumber \]
where \(\text{diag}_{0\leq k< N}(\gamma _n)\) denotes a diagonal matrix with diagonal entries γnγn" role="presentation" style="position:relative;" tabindex="0">\(\gamma _n\).
We jointly refer to polynomial transforms, scaled or not, as Fourier transforms.
DFT as a Polynomial Transform
We show that the DFTNDFTN" role="presentation" style="position:relative;" tabindex="0">\(\text{DFT}_N\) is a polynomial transform for A=C[s]/(sN-1)A=C[s]/(sN-1)" role="presentation" style="position:relative;" tabindex="0">\(\mathfrak{A}=\mathbb{C}[s]/(s^N-1)\) with basis \(b=1,s,...,s^{N-1}\). Namely,
\[s^{N-1}=\prod_{0\leq k< N}(x-W_{N}^{k}) \nonumber \]
which means that \(\Delta\) takes the form
\[\Delta :\mathbb{C}[s]/(s^N-1)\rightarrow \mathbb{C}[s]/(s-W_{N}^{0})\oplus ...\oplus \mathbb{C}[s]/(s-W_{N}^{N-1}) \nonumber \]
\[X(s)\mapsto (X(s)\: \text{mod}\: (s-W_{N}^{0}),...,X(s)\: \text{mod}\: (s-W_{N}^{N-1}))=(X(W_{N}^{0}),...,X(W_{N}^{N-1})) \nonumber \]
The associated polynomial transform hence becomes
\[\mathfrak{P}_{b,\alpha }=\left [ W_{N}^{kn} \right ]_{0\leq k,n< N}=\text{DFT}_N \nonumber \]
This interpretation of the DFT has been known for a long time and clarifies the connection between the evaluation points in and the circular convolution in the equations.
DFTs of types \(1-4\) are defined, with type \(1\) being the standard DFT. In the algebraic framework, type \(3\) is obtained by choosing A=C[s]/(sN+1)A=C[s]/(sN+1)" role="presentation" style="position:relative;" tabindex="0">\(\mathfrak{A}=\mathbb{C}[s]/(s^N+1)\) as algebra with the same basis as before:
\[\mathfrak{P}_{b,\alpha }=\left [ W_{N}^{(k+1/2)n} \right ]_{0\leq k,n< N}=\text{DFT}-3_{N} \nonumber \]
The DFTs of type \(2\) and \(4\) are scaled polynomial transforms.