3.3: The DFT as a Polynomial Evaluation

The \(\mathit{Z}\)-transform of a number sequence \(x(n)\) is defined as:

\[X(z)=\sum_{n=0}^{\infty }x(n)z^{-n} \nonumber \]

which is the same as the polynomial description in Equation 3.1.1 but with a negative exponent. For a finite length-\(N\) sequence the above equation becomes

\[X(z)=\sum_{n=0}^{\infty }x(n)z^{-n} \nonumber \]

\[X(z)=x(0)+x(1)z^{-1}+x(2)z^{-2}+...+x(N-1)z^{-N+1} \nonumber \]

This \(N-1\) order polynomial takes on the values of the DFT of \(x(n)\) when evaluated at

\[z=e^{j2\pi k/N} \nonumber \]

which gives

\[C(k)=X(z)\mid _{z=e^{j2\pi k/N}}=\sum_{n=0}^{N-1}x(n)e^{-j2\pi nk/N} \nonumber \]

In terms of the positive exponent polynomial from the above equation, the DFT is:

\[C(k)=X(s)\mid _{s=W^{k}} \nonumber \]

where

\[W=e^{-j2\pi /N} \nonumber \]

is an \(N^{th}\) root of unity (raising \(W\) to the \(N^{th}\) power gives one). The \(N\) values of the DFT are found from \(X(s)\) evaluated at the \(N\) \(N^{th}\) roots of unity which are equally spaced around the unit circle in the complex s plane.

One method of evaluating \(X(z)\) is the so-called Horner's rule or nested evaluation. When expressed as a recursive calculation, Horner's rule becomes the Goertzel algorithm which has some computational advantages especially when only a few values of the DFT are needed.

Another method for evaluating \(X(s)\) is the residue reduction modulo (\(s-W^k\)) as shown in Equation 3.3.1 above. Each evaluation requires \(N\) multiplications and therefore, \(N^2\) multiplications for the \(N\) values of \(C(k)\).

\[C(k)=((X(s)))_{(s-W^{k})} \nonumber \]

A considerable reduction in required arithmetic can be achieved if some operations can be shared between the reductions for different values of \(k\). This is done by carrying out the residue reduction in stages that can be shared rather than done in one step for each \(k\) in the above equation.

The \(N\) values of the DFT are values of \(X(s)\) evaluated at \(s\) equal to the \(N\) roots of the polynomial

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

which are \(W^k\). First, assuming \(N\) is even, factor \(P(s)\) as:

\[P(s)=(s^{N}-1)=P_{1}(s)P_{2(s)}=(s^{N/2}-1)(s^{N/2}+1) \nonumber \]

X(s)\(X(s)\) is reduced modulo these two factors to give two residue polynomials, \(X_1(s)\) and \(X_2(s)\). This process is repeated by factoring \(P_1\) and further reducing \(X_1\) then factoring \(P_2\) and reducing \(X_2\). This is continued until the factors are of first degree which gives the desired DFT values as in Equation. This is illustrated for a length-8 DFT. The polynomial whose roots are \(W^k\), factors as

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

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

\[P(s)=[(s^{2}-1)(s^{2}+1)][(s^{2}-j)(s^{2}+j)] \nonumber \]

\[P(s)=[(s-1)(s+1)(s-j)(s+j)][s-a)(s+a)(s-ja)(s+ja)] \nonumber \]

where

\[a^{2}=j \nonumber \]

Reducing \(X(s)\) by the first factoring gives two third degree polynomials:

\[X(s)=x_{0}+x_{1}s+x_{2}s^{2}+...+x_{7}s^{7} \nonumber \]

gives the residue polynomials

\[X_{1}(s)=((X(S)))_{(s^{4}-1)}=(x_{0}+x_{4})+(x_{1}+x_{5})s+(x_{2}+x_{6})s^{2}+(x_{3}+x_{7})s^{3} \nonumber \]

\[X_{2}(s)=((X(S)))_{(s^{4}+1)}=(x_{0}-x_{4})+(x_{1}-x_{5})s+(x_{2}-x_{6})s^{2}+(x_{3}-x_{7})s^{3} \nonumber \]

Two more levels of reduction are carried out to finally give the DFT. Close examination shows the resulting algorithm to be the decimation-in-frequency radix-2 Cooley-Tukey FFT. Martens has used this approach to derive an efficient DFT algorithm.

Other algorithms and types of FFT can be developed using polynomial representations and some are presented in the generalization in DFT and FFT - An Algebraic View.

Contributor

• ContribEEBurrus