Fourier Transform and Signal Spectrum - Digital Signal Processing: A Practitioner's Approach - page 86

Figure 4.8 Decimation in time

We replicate the odd sequence DFT to make a 16-point sequence and multiply point
by point with a factor W

16 . We generate another 16-point sequence by replicating
the even DFT sequence. By adding together both sequences we will get the desired
16-point DFT, shown as step B in Figure 4.8. This process is recursive, hence it
leads to very efficient DFT computation.

4.4.4 Decimation in Frequency
For decimation in frequency, we divide the sequence into two halves, premultiply
with weights known as twiddle factors and compute the DFT (Figure 4.9). We
rewrite (4.15) as

X k ¼ X

16 þ X

7 15

x n W nk x n W nk

16 :

ð 4 : 18 Þ

n ¼ 0 n ¼ 8

Figure 4.9 Decimation in frequency