Digital Signal Processing Reference
In-Depth Information
6.5 BIT REVERSAL FOR UNSCRAMBLING
A bit-reversal procedure allows a scrambled sequence to be reordered. To illustrate
this bit-swapping process, let
N
8, represented by three bits. The first and third bits
are swapped. For example, (100)
b
is replaced by (001)
b
. As such, (100)
b
specifying
the address of
X
(4) is replaced by or swapped with (001)
b
specifying the address of
X
(1). Similarly, (110)
b
is replaced/swapped with (011)
b
, or the addresses of
X
(6) and
X
(3) are swapped. In this fashion, the output sequence in Figure 6.5 with the DIF,
or the input sequence in Figure 6.10 with the DIT, can be reordered.
This bit-reversal procedure can be applied for larger values of
N
. For example,
for
N
=
64, represented by six bits, the first and sixth bits, the second and fifth bits,
and the third and fourth bits are swapped.
Several examples in this chapter illustrate the FFT algorithm, incorporating
algorithms for unscrambling.
=
6.6 DEVELOPMENT OF THE FFT ALGORITHM WITH RADIX-4
A radix-4 (base 4) algorithm can increase the execution speed of the FFT. FFT
programs on higher radices and split radices have been developed. We use a DIF
decomposition process to introduce the development of the radix-4 FFT. The last
or lowest decomposition of a radix-4 algorithm consists of four inputs and four
outputs. The order or length of the FFT is 4
M
, where
M
is the number of stages. For
a 16-point FFT, there are only two stages or iterations, compared with four stages
with the radix-2 algorithm. The DFT in (6.1) is decomposed into four summations
instead of two as follows:
(
)
-
(
)
-
(
)
-
N
41
N
21
341
N
N
-
1
Â
Â
Â
Â
()
=
()
()
()
()
nk
nk
nk
nk
(6.30)
Xk
xnW
+
xnW
+
xnW
+
xnW
n
=
0
nN
=
4
nN
=
2
nN
=
34
Let
n
3
N
/4 in the second, third, and fourth sum-
mations, respectively. Then (6.30) can be written as
=
n
+
N
/4,
n
=
n
+
N
/2, and
n
=
n
+
(
N
41
)
-
(
N
41
)
-
Â
Â
()
=
()
(
)
Xk
xnW
nk
+
W
k N
4
xn N
+
4
W
nk
n
=
0
n
=
0
(
)
-
(
)
-
N
41
N
41
Â
Â
(
)
(
)
+
W
kN
2
x n
+
N
2
W
nk
+
W
3
kN
4
x n
+
3
N
4
W
nk
(6.31)
n
=
0
n
=
0
which represents four (
N
/4)-point DFTs. Using
N
kN
4
=
(
)
k
=
()
We
kN
4
-
j
2
p
=
e
-
jk
p
2
j
k
= -
()
We
kN
2
=
-
jk
p
1
k
=
()
3
kN
4
Wj
Search WWH ::
Custom Search