Digital Signal Processing Reference
In-Depth Information
6
1
1
0
5
7
−1
0.5
0
2
4
6
(b) Sample
0
4
0
−0.5
1
3
1
0
−1
2
−1
−1
−0.5
0
0.5
1
0
2
4
6
(a) Real
(c) Sample
1
6
1
0
5
7
−1
0.5
0
2
4
6
(e) Sample
0
4
0
−0.5
1
3
1
0
−1
2
−1
−1
−0.5
0
0.5
1
0
2
4
6
(d) Real
(f) Sample
Figure 3.19:
(a) The complex correlators for an 8-pt DFT, for
k
= 1; (b) Real part of the complex
correlators shown in (a); (c) Imaginary part of the complex correlators shown in (a); (d) The complex
correlators for an 8-pt DFT (
k
= 1), generated as the complex correlators for a 4-pt DFT (marked with
circles), and the same 4-pt correlators multiplied by the phase factor exp(-j2
π(
1
)/
8), marked with stars.
3.14.2 DECIMATION-IN-TIME
This principle of breaking a length 2
n
sequence into even and odd subsequences, and expressing the
DFT of the longer sequence as the sum of two shorter DFTs, can be continued until only length-1 DFTs
remain. A sequence of length 8, for example, is decimated into even and odd subsequences several times,
in this manner.
Matrix (3.20) shows the steps for DIT of a length-8 sequence. It may be interpreted as follows:
TD (1 X 8), for example, means that the sequence (whose original sample indices lie to the right), is 1
sequence of length 8, whereas TD (2 X 4) means that the original sample indices to the right form 2
sequences of 4 samples each, and so on.
TD(1 X 8) 01234567
TD(2 X 4) 02461357
TD(4 X 2) 04261537
TD(8 X 1) 04261537
FD(8 X 1) 04261537
(3.20)
The length-8 sequence (in the first row of the matrix) is divided into two length-4 sequences
by taking its even and odd indexed parts, shown in the second row. Then the two 4-sample sequences
