Algorithms and Parallel Computing

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₀ and x₁ are given by McKinney [124]

(19.7)

(19.8)

The original sum in Eq. 19.1 is now split as

(19.9)

We notice that can be written as

(19.10)

We can write Eq. 19.9 as

(19.11)

(19.12)

where X₀(k) and X₁(k) are the N/2-point DFTs of x₀(n) and x₁(n), respectively. Notice, however, that X(k) is defined for 0 ≤ k < N, while X₀(k) and X₁(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₀(k) and X₁(k) are each periodic with a period N/2, we can express Eq. 19.12 as

(19.13)

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