next up previous
Next: Division with remainder using Newton Up: Efficient implementation Previous: Efficient implementation

Towards an iterative algorithm for the DTF

We first change the intermediate polynomials. Let n = 2r be a power of 2, let $ \omega$ $ \in$ R be a primitive n-th root of unity and A(x) = $ \Sigma_{{{0 \, \leq \, i \, < \, n}}}^{{}}$ ai xi. We define

A[0](x) = a0 + a2x + a4x2 + ... + an-2xn/2-1
A[1](x) = a1 + a3x + a5x2 + ... + an-1xn/2-1
(51)

such that

A(x)  =  A[0](x2) + x A[1](x2) (52)

Hence evaluating A at 1,$ \omega$,$ \omega^{{2}}_{{}}$,...,$ \omega^{{{n-1}}}_{{}}$ is reduced to evaluate A[0] and A[1] at 1,$ \omega^{{2}}_{{}}$,$ \omega^{{4}}_{{}}$,...,$ \omega^{{{2n-2}}}_{{}}$. But this second sequence of values consists of two identical sequences of length n/2. Indeed for every integer k we have

($\displaystyle \omega^{{{k+ n/2}}}_{{}}$)2  =  ($\displaystyle \omega^{{{k}}}_{{}}$)2 (53)

This shows

$\displaystyle \omega^{{{k+ n/2}}}_{{}}$  =   - $\displaystyle \omega^{{{k}}}_{{}}$ (54)

Hence we only need to evaluate A[0] and A[1] at

1,$\displaystyle \omega^{{2}}_{{}}$,$\displaystyle \omega^{{4}}_{{}}$,...,$\displaystyle \omega^{{{n-2}}}_{{}}$ (55)

which allows us to evaluate A at

1,$\displaystyle \omega$,$\displaystyle \omega^{{2}}_{{}}$,...,$\displaystyle \omega^{{{n/2-1}}}_{{}}$ (56)

Then to compute at A at

$\displaystyle \omega^{{{n/2}}}_{{}}$,$\displaystyle \omega^{{{n/2+1}}}_{{}}$,...,$\displaystyle \omega^{{{n-1}}}_{{}}$ (57)

we use the fact these numbers are respectively equal to

-1, - $\displaystyle \omega$, - $\displaystyle \omega^{{2}}_{{}}$,..., - $\displaystyle \omega^{{{n/2-1}}}_{{}}$. (58)

Algorithm 3  

\fbox{
\begin{minipage}{10 cm}
\begin{description}
\item[{\bf Input:}] $n = 2^r$...
...k+n/2}$\ := $y_k^{[0]} - t$\ \\
\> {\bf return} $y$\end{tabbing}\end{minipage}}

The recursive calls of DFT(n, A,$ \Omega$) defines a ordering of the coefficients of A shown on Figure 1. Let us call this ordering the DFT ordering of A.

THIS PART REQUIRES PROCESSING COMPLETELY BY HAND THE CASE n = 8.

Figure 1: Recursive calls for n = 8.
\begin{figure}\htmlimage
\centering\includegraphics[scale=.5]{figures/fft8.eps}
\end{figure}

Algorithm 4  

\fbox{
\begin{minipage}{12 cm}
\begin{description}
\item[{\bf Input:}] $n = 2^r$...
...A[k + j + m/2]$\ := $u - t$\ \\
\> {\bf return} $A$\end{tabbing}\end{minipage}}

THE FORMULA FOR t IN THE ABOVE ALGORITHM NEEDS TO BE CHECKED.

Remark 8   To get the DFT ordering for A, that is [a0, a4, a2, a6, a1, a5, a3, a7], observe that this ordering changes

000, 001, 010, 011, 100, 101, 011, 111 (59)

to

000, 100, 010, 110, 001, 101, 110, 111 (60)

Remark 9   The ring $ \mbox{${\mathbb Z}$}$ does not have any interesting roots of unity. In order to take advantage of the FFT-based multiplication one could use a modular approach as follows.


next up previous
Next: Division with remainder using Newton Up: Efficient implementation Previous: Efficient implementation
Marc Moreno Maza
2004-04-27