Digital Signal Processing Reference
In-Depth Information
3.14.1 N-PT DF T FROM TWO N/2-PT DF TS
We'll consider the simple radix-2
Decimation-in-Time
(
DIT
) algorithm, which is based on the idea that
any sequence having a length equal to a power of two can be divided into two subsequences, comprised of
the even and odd indexed members of the original sequence. A DFT can then be computed for the two
shorter sequences (each of which is half the length of the original sequence), and the two DFTs can be
put together to result in the DFT of the original sequence. There is a computational savings achieved by
doing this. You can keep dividing each subsequence into two parts until the original sequence of length
N
has been divided into
N
sequences of length one, each of which is its own DFT. From this,
N/
2 DFTs
each having two bins can be assembled. The
N/
2 two-bin DFTs are then assembled into
N/
4 four-bin
DFTs, and so on until a length-
N
DFT has been computed.
Consider the DFT (
X
[
k
]
) of a sequence
x
[
n
]
of length eight samples, which can be computed in
MathScript as
X(k) = sum(x(n).*exp(-j*2*pi*(0:1:7)*k/8))
The signal
x
[
n
]
can be rewritten as the sum of two length-4 DFTs by dividing it into its even and
odd indexed samples:
]
which, in MathScript, would be, owing to the fact that MathScript array indices start with 1 rather than
0,
xE
=
x
[
0
:
2
:
7
];
xO
=
x
[
1
:
2
:
7
xE = x(1:2:8); xO = x(2:2:8)
For an 8-pt DFT, the complex correlator is
1
8
:
7
8
))
exp
(
−
j
2
πk(
0
:
1
:
7
)/
8
)
=
exp
(
−
j
2
πk(
0
:
For a 4-pt DFT, the complex correlator is
6
8
))
The latter expression is just the even indexed correlators (starting with index 0) for an 8-pt DFT.
The odd indexed correlators for an 8-pt DFT can be obtained from the 4-pt DFT by a simple phase
shift:
1
4
:
3
4
))
2
8
:
exp
(
−
j
2
πk(
0
:
=
exp
(
−
j
2
πk(
0
:
6
8
))
Then setting
n = 0:1:3
; and
Phi = exp(-j*2*pi*k/8 )
, the 8-pt DFT, expressed as the sum of two
4-pt DFTs, would be
j
2
πk(
1
2
8
:
7
8
))
2
8
:
−
8
:
=
−
−
:
exp
(
exp
(
j
2
πk/
8
)
exp
(
j
2
πk(
0
X(k) = sum(xE.*exp(-j*2*pi*(0:1:3)*k/4)) +...
Phi*sum(xO*exp(-j*2*pi*(0:1:3)*k/4))
(3.16)
At this point, we can simplify the notation by setting
