Digital Signal Processing Reference
In-Depth Information
X
3
¼½
x
0
þ
x
2
e
j2
p
2
=
4
þ½
x
1
e
j2
p
3
=
4
þ
x
3
e
j2
p
1
=
4
¼½
x
0
þ
x
2
e
j2
p
2
=
4
þ½
x
1
þ
x
3
e
j2
p
2
=
4
e
j2
p
3
=
4
Here is the result:
X
0
¼½
x
0
þ
x
2
þ½
x
1
þ
x
3
X
1
¼½
x
0
þ
x
2
e
j2
p
2
=
4
þ½
x
1
þ
x
3
e
j2
p
2
=
4
e
j2
p=
4
X
2
¼½
x
0
þ
x
2
þ½
x
1
þ
x
3
e
j4
p=
4
X
3
¼½
x
0
þ
x
2
e
j2
p
2
=
4
þ½
x
1
þ
x
3
e
j2
p
2
=
4
e
j6
p=
4
Now comes the insightful part. Comparing the four equations
above, you can see that the bracketed terms used for X
0
and X
1
are
also present in X
2
and X
3
. So we don't need to recompute these
terms during the calculation of X
2
and X
3
. We can simply multiply
them by the additional exponential outside the brackets. This
reusing of partial products in multiple calculations is the key to
understanding the FFT efficiency, so at the risk of being repeti-
tive, this is shown again more explicitly below.
/
define A
¼½
x
0
þ
x
2
;
B
¼½
x
1
þ
x
3
X
0
¼½
x
0
þ
x
2
þ½
x
1
þ
x
3
¼
A
þ
B
define C
¼½
x
0
þ
x
2
e
j2
p
2
=
4
D
¼½
x
1
þ
x
3
e
j2
p
2
=
4
;
/
X
1
¼½
x
0
þ
x
2
e
j2
p
2
=
4
þ½
x
1
þ
x
3
e
j2
p
2
=
4
e
j2
p=
4
¼
C
þ
D
e
j2
p=
4
X
2
¼½
x
0
þ
x
2
þ½
x
1
þ
x
3
e
j4
p=
4
¼
A
þ
B
e
j4
p=
4
X
3
¼½
x
0
þ
x
2
e
j2
p
2
=
4
þ½
x
1
þ
x
3
e
j2
p
2
=
4
e
j6
p=
4
¼
C
þ
D
e
j6
p=
4
This process quickly gets out of hand for anything larger than
a four point (N
¼
4) FFT. So we are going to use a type of repre-
sentation called a flow graph, shown in
Figure 12.1
below.
The flow graph is an equivalent way of representing the
equations, and moreover, represents the actual organization of
the computations. You can check the simple example above to
see the flow graph gives the same results as the DFT equations.
For example, X
0
¼
x
0
þ
x
1
þ
x
2
þ
x
3
, and by examining the flow
