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 x0 and x1 are given by McKinney [124]

(19.7) c19e007

(19.8) c19e008

The original sum in Eq. 19.1 is now split as

(19.9) c19e009

We notice that c19ue002 can be written as

(19.10) c19e010

We can write Eq. 19.9 as

(19.11) c19e011

(19.12) c19e012

where X0(k) and X1(k) are the N/2-point DFTs of x0(n) and x1(n), respectively. Notice, however, that X(k) is defined for 0 ≤ k < N, while X0(k) and X1(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 X0(k) and X1(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.