Algorithms and Parallel Computing

19.4 DECIMATION-IN-FREQUENCY FFT

In the decimation-in-frequency FFT, the splitting algorithm breaks up the sum in Eq. 19.1 into the first N/2 points and the last N/2 points. This is equivalent to considering the even and odd parts of X(k). By contrast, in decimation-in-time, we considered the even and odd parts of x(n). The first and second part sequences x₀ and x₁ of x(n) are given by McKinney [124]

(19.18)

(19.19)

The original sum in Eq. 19.1 is now split as

(19.20)

We can express the above equation in terms of x₀(n) and x₁(n) as

(19.21)

Consider the even samples of X(k) in the above equation:

(19.22)

where e^−jπk = 1 when k is even. On the other hand, the odd part of X(k) is given by

(19.23)

where e^−jπk = −1 when k is odd.

In summary, the even and the odd terms of the DFT can be obtained from the N/2-DFTs:

(19.24)

(19.25)

where the input sequences a