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 x0 and x1 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 x0(n) and x1(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
Get Algorithms and Parallel Computing now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.