O'Reilly logo

Algorithms and Parallel Computing by Fayez Gebali

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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 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

(19.13)

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

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required