0.7 Dft and fft: an algebraic view  (Page 2/5)

In this chapter, the DFT will naturally arise as a linear mapping with respect to chosen bases, i.e., as a matrix. Indeed, the definitionshows that if all input and outputs are collected into vectors $X=\left(X\right(0),\cdots ,X(N-1\left)\right)$ and $C=\left(C\right(0),\cdots C(N-1\left)\right)$ , then Winograd’s Short DFT Algorithms is equivalent to

where

The matrix point of view is adopted in the FFT books [link] , [link] .

Polynomial algebras and the dft

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

For further background on the mathematics in this section and polynomial algebras in particular, we refer to [link] .

Polynomial algebra

An algebra $\mathcal{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). Examples include the sets of complex or real numbers $\mathbb{C}$ or $\mathbb{R}$ , and the sets of complex or real polynomials in the variable $s$ : $\mathbb{C}\left[s\right]$ or $\mathbb{R}\left[s\right]$ .

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

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

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

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

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

As a simple example we consider $\mathcal{A}=\mathbb{C}\left[s\right]/(s^2-1)$ , which has dimension 2. A possible basis is $b=(1,s)$ . In $\mathcal{A}$ , for example, $s·(s+1)=s^2+s\equiv s+1\text{mod}(s^2-1)$ , obtained through division with rest

or simply by replacing $s^2$ with 1 (since $s^2-1=0$ implies $s^2=1$ ).

Chinese remainder theorem (crt)

Assume $P\left(s\right)=Q\left(s\right)R\left(s\right)$ 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 $\mathcal{A}$ -modules.

Here, $\oplus$ is the Cartesian product of vector spaces with elementwise operation (also called outer direct sum). In words, the CRTasserts that computing (addition, multiplication, scalar multiplication) in $\mathbb{C}\left[s\right]/P\left(s\right)$ is equivalent to computing in parallel in $\mathbb{C}\left[s\right]/Q\left(s\right)$ and $\mathbb{C}\left[s\right]/R\left(s\right)$ .

If we choose bases $b,c,d$ in the three polynomial algebras, then $\Delta$ can be expressed as a matrix. As usual with linear mappings, 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\left(s\right)=s^2-1=(s-1)(s+1)$ and the CRT decomposition