Radix-2 Decimation in Frequency FFT Algorithm

Contents

Introduction

In the previous section Decimation in Time FFT Algorithm was considered in detail.

Consider one more method of divide and conquer which is called decimation in frequency.

Decimation in Frequency FFT Algorithm

Let $N$ samples of the input signal $s(n)$, $n = 0 \ldots N-1$ be, at the same time $N$ is the whole degree of two $N = 2^L$.

In FFT algorithm with decimation in time there was dividing of the input signal according to the bit reversal. Thus, we received the first and second half of discrete Fourier transform (DFT).

In the decimation in frequency algorithm the pickup input $s(n)$, $n = 0 \ldots N-1$, is halved, i.e.
$s_0(m) = s(m)$ and $s_1(m) = s\left(m+\frac{N}{2}\right)$, $m = 0 \ldots \frac{N}{2} - 1$.

Then the DFT signal $s(n)$ can be written in the form:

$$
S(k) = \sum_{n = 0}^{N - 1} s(n) \cdot W_N^{n\cdot k}
=\sum_{m = 0}^{\frac{N}{2} - 1} \left[ s(m) \cdot W_N^{m\cdot k} +
s\left( m + \frac{N}{2} \right) \cdot W_N^{\left(m + \frac{N}{2} \right)\cdot k} \right] =
$$
$$
=\sum_{m = 0}^{\frac{N}{2} - 1} \left[ s(m) \cdot W_N^{m\cdot k} +
s\left( m + \frac{N}{2} \right) \cdot W_N^{m \cdot k} \cdot W_N^{\frac{N}{2} \cdot k}\right] =
$$
$$
=\sum_{m = 0}^{\frac{N}{2} - 1} \left[ s(m) +
s\left( m + \frac{N}{2} \right) \cdot W_N^{\frac{N}{2} \cdot k}\right]\cdot W_N^{m \cdot k}, \textrm{ }k=0 \ldots N-1.
$$

(1)

Consider (1) for spectral samples $S(2\cdot p)$, $p = 0 \ldots \frac{N}{2}-1$, with even indexes:

\begin{equation} \label{fft_dec_in_freqs:eq2}
S(2 \cdot p) = \sum_{m = 0}^{\frac{N}{2} - 1} \left[ s(m) +
s\left( m + \frac{N}{2} \right) \cdot W_N^{\frac{N}{2} \cdot 2 \cdot p}\right]\cdot W_N^{m \cdot 2\cdot p}, \textrm{ }p = 0 \ldots \frac{N}{2}-1.
\end{equation}

(2)

Take into account in (2) that $W_N^{\frac{N}{2} \cdot 2 \cdot p} = W_N^{N \cdot p} = 1$, and also $W_N^{m \cdot 2\cdot p} = W_{\frac{N}{2}}^{m \cdot p}$, then we get:

\begin{equation} \label{fft_dec_in_freqs:eq3}
S(2 \cdot p) = \sum_{m = 0}^{\frac{N}{2} - 1} \underbrace{\left[ s(m) +
s\left( m + \frac{N}{2} \right) \right]}_{x_0(m)}\cdot W_{\frac{N}{2}}^{m \cdot p} = \underbrace{\sum_{m = 0}^{\frac{N}{2} - 1} x_0(m) \cdot W_{\frac{N}{2}}^{m \cdot p}}_{\frac{N}{2}-\textrm{points DFT}}, \textrm{ } p = 0 \ldots \frac{N}{2}-1.
\end{equation}

(3)

Thus, spectral samples $S(2\cdot p)$, $p = 0 \ldots \frac{N}{2}-1$, with even indexes are $\frac{N}{2}-$ point DFT of the signal $x_0(m) = s(m) + s\left( m + \frac{N}{2} \right)$.

Similarly consider (1) for spectral samples $S(2\cdot p+1)$, $p = 0 \ldots \frac{N}{2}-1$, with odd indexes:

\begin{equation}
S(2 \cdot p+1) = \sum_{m = 0}^{\frac{N}{2} - 1} \left[ s(m) +
s\left( m + \frac{N}{2} \right) \cdot W_N^{\frac{N}{2} \cdot (2 \cdot p+1)}\right]\cdot W_N^{m \cdot (2 \cdot p+1)}, \textrm{ }p = 0 \ldots \frac{N}{2}-1.
\end{equation}

(4)

Take into account in (4) that $W_N^{\frac{N}{2} \cdot (2 \cdot p+1)} = W_N^{\frac{N}{2} \cdot 2 \cdot p} \cdot W_N^{\frac{N}{2}} = -1$, and also that
$W_N^{m \cdot (2 \cdot p+1)} =W_N^{m} \cdot W_N^{m \cdot 2 \cdot p} = W_N^{m} \cdot W_{\frac{N}{2}}^{m \cdot p}$. Then (4) can be presented in the form:

\begin{equation}
S(2 \cdot p+1) = \sum_{m = 0}^{\frac{N}{2} - 1} \underbrace{\left[ s(m) -
s\left( m + \frac{N}{2} \right) \right] \cdot W_N^m}_{x_1(m)} \cdot W_{\frac{N}{2}}^{m \cdot p} =
\underbrace{\sum_{m = 0}^{\frac{N}{2} - 1} x_1(m) \cdot W_{\frac{N}{2}}^{m \cdot p}}_{\frac{N}{2}- \textrm{points DFT}}, \textrm{ }p = 0 \ldots \frac{N}{2}-1.
\end{equation}

(5)

Spectral samples $S(2\cdot p+1)$, $p = 0 \ldots \frac{N}{2}-1$, with odd indexes $2 \cdot p+1$ are $\frac{N}{2}-$ point DFT of the signal $x_1(m)= \left[s(m) -
s\left( m + \frac{N}{2} \right)\right] \cdot W_N^{m}$.

Thus, the divide procedure includes calculating signals of half duration $x_0(m)$ and $x_1(m)$, $m = 0 \ldots \frac{N}{2} - 1$. Then it is possible to replace $N-$point DFT with two $\frac{N}{2}-$points DFT of signals $x_0(m)$ and $x_1(m)$.

Decimation in Frequency FFT Algorithm Butterfly Diagram

The procedure of calculating signals of half duration

\begin{align}
x_0(m) &= s(m) + s\left( m + \frac{N}{2}\right), & m &= 0 \ldots \frac{N}{2}-1; \nonumber \\
x_1(m) &= \left[ s(m) - s\left( m + \frac{N}{2}\right) \right] \cdot W_N^m, & m &= 0 \ldots \frac{N}{2}-1
\end{align}

(6)

can be presented in the form of the butterfly diagram as it is shown in Figure 1.

Figure 1. Butterfly Diagram of Decimation in Frequency FFT Algorithm

Difference of the butterfly diagram of the decimation in frequency FFT algorithm from a similar diagram for the decimation in time FFT algorithm is that multiplication by the twiddle factor $W_N^m$ is performed after subtracting places. In the butterfly diagram of the decimation in time FFT algorithm multiplication by the twiddle factor was performed before subtracting places.

Complete Diagram of Decimation in Frequency FFT Algorithm

We replaced calculating $N-$points DFT with two $\frac{N}{2}-$points.
As a result the diagram of decimation in frequency FFT algorithm for $N=8$ is given in Figure 2.

Figure 2. Diagram of Decimation in Frequency FFT Algorithm for $N=8$

At the same time each of $\frac{N}{2}-$points DFT can be also calculated using the decimation in frequency FFT algorithm. As a result we will receive the complete diagram of decimation in frequency FFT algorithm as it is shown in Figure 3.

Figure 3. Complete Diagram of Decimation in Frequency FFT Algorithm for $N=8$

At the first stage we receive $x_0(m)$ and $x_1(m)$ according to (6):

\begin{align}
x_0(0) & = s(0) + s(4);\nonumber \\
x_0(1) & = s(1) + s(5);\nonumber \\
x_0(2) & = s(2) + s(6);\nonumber \\
x_0(3) & = s(3) + s(7);\nonumber \\
x_1(0) & = [s(0) - s(4)] \cdot W_8^0;\nonumber \\
x_1(1) & = [s(1) - s(5)]\cdot W_8^1 ;\nonumber \\
x_1(2) & = [s(2) - s(6)]\cdot W_8^2 ;\nonumber \\
x_1(3) & = [s(3) - s(7)]\cdot W_8^3 .
\end{align}

(7)

To calculate 4-points DFT of signals $x_0(m)$ and $x_1(m)$, $m = 0 \dots 3$, we use the decimation in frequency FFT algorithm again. Then we receive signals:

\begin{align}
x_{00}(0) & = x_0(0) + x_0(2);\nonumber \\
x_{00}(1) & = x_0(1) + x_0(3);\nonumber \\
\\
x_{01}(0) & = [x_0(0) - x_0(2)] \cdot W_4^0;\nonumber \\
x_{01}(1) & = [x_0(1) - x_0(3)] \cdot W_4^1;\nonumber \\ \\
x_{10}(0) & = x_1(0) + x_1(2);\nonumber \\
x_{10}(1) & = x_1(1) + x_1(3);\nonumber \\
\\
x_{11}(0) & = [x_1(0) - x_1(2)] \cdot W_4^0;\nonumber \\
x_{11}(1) & = [x_1(1) - x_1(3)] \cdot W_4^1.\nonumber
\end{align}

(8)

After calculating two-points DFT at the last level of dividing we receive the spectral samples:

\begin{align}
S(0) & = x_{00}(0) + x_{00}(1);\nonumber \\
S(4) & = [x_{00}(0) - x_{00}(1)] \cdot W_2^0;\nonumber \\
\\
S(2) & = x_{01}(0) + x_{01}(1);\nonumber \\
S(6) & = [x_{01}(0) - x_{01}(1)] \cdot W_2^0;\nonumber \\
\\
S(1) & = x_{10}(0) + x_{10}(1);\nonumber \\
S(5) & = [x_{10}(0) - x_{10}(1)] \cdot W_2^0;\nonumber \\
\\
S(3) & = x_{11}(0) + x_{11}(1);\nonumber \\
S(7) & = [x_{11}(0) - x_{11}(1)] \cdot W_2^0,\nonumber
\end{align}

(9)

which we have to subject to the bit reversal in the same way as this procedure in the algorithm with decimation in time is performed.

Conclusions

In this section we considered radix-2 decimation in frequency FFT algorithm. In the following section we will consider computing efficiency of radix-2 FFT algorithms and some questions of program implementing FFT algorithms.

You can provide your any feedbacks, questions and wishes in the message board or в guestbook.

Reference

[1]
James W. Cooley and John W. Tukey
An Algorithm for the Machine Calculation of Complex Fourier Series.
Mathematics of Computation, 1965 p. 297–301.

[2]
Richard E. Blahut
Fast Algorithms for Signal Processing.
Cambridge University Press, 2010.

[3]
Nussbaumer Henri J.
Fast Fourier Transform and Convolution Algorithms.
Second Corrected and Updated Edition.
Springer-Verlag, 1982.

[4]
Oppenheim Alan V. and Schafer Ronald W.
Discrete-Time Signal Processing
Second Edition.
Prentice-Hall, New Jersey, 1999.