19.2 DECIMATION-IN-TIME FFT

In the decimation-in-time FFT, the splitting algorithm breaks up the sum in Eq. 19.1 into even- and odd-numbered parts. The even and odd sequences x_{0} and x_{1} are given by McKinney [124]

(19.7)

(19.8)

The original sum in Eq. 19.1 is now split as

We notice that can be written as

(19.10)

We can write Eq. 19.9 as

(19.11)

where X_{0}(k) and X_{1}(k) are the N/2-point DFTs of x_{0}(n) and x_{1}(n), respectively. Notice, however, that X(k) is defined for 0 ≤ k < N, while X_{0}(k) and X_{1}(k) are defined for 0 ≤ k < N/2. A way must be determined then to evaluate Eq. 19.12 for values of k > N/2. Since X_{0}(k) and X_{1}(k) are each periodic with a period N/2, we can express Eq. 19.12 as

Equations 19.12 and 19.13 are referred to as the butterfly ...

Get *Algorithms and Parallel Computing* now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.