Modular pipeline fast Fourier transform
View Patent ↗A modular pipeline algorithm and architecture for computing discrete Fourier transforms is described. For an N point transform, two pipeline √{square root over (N)} point fast Fourier transform (FFT) modules are combined with a center element. The center element contains memories, multipliers and control logic. Compared with standard N point pipeline FFTs, the modular pipeline FFT maintains the bandwidth of existing pipeline FFTs with reduced dynamic power consumption and reduced complexity of the overall hardware pipeline.
1. A device, comprising:
a first FFT unit that performs a first fast Fourier transform (FFT) on a set of inputs to produce intermediate values;
center element logic that multiplies the intermediate values by pre-rotation coefficients to produce pre-rotated intermediate values, wherein the pre-rotated intermediate values are organized into first groups, and reorganizes the pre-rotated intermediate values into new groups, each new group containing one of the intermediate values from each of the first groups; and
a second FFT unit that performs a second fast Fourier transform on the reorganized pre-rotated intermediate values to produce a set of outputs.
2. A device, comprising:
a first FFT unit that performs a first fast Fourier transform (FFT) on a set of N inputs to produce N intermediate values;
center element logic that multiplies the N intermediate values by a set of N pre-rotation coefficients to produce N pre-rotated intermediate values organized into √{square root over (N)} new groups, each new group containing one of the N intermediate values from each of the √{square root over (N)} first groups; and
a second FFT unit that performs a second fast Fourier transform (FFT) on the set of N reorganized pre-rotated values to produce N outputs.
3. A system, comprising:
a first stage that performs a first fast Fourier transform (FFT) on a set of inputs to produce intermediate values;
a center stage that performs a pre-rotation of the intermediate values; and
a second stage that performs a second fast Fourier transform on the pre-rotated intermediate values to produce a set of outputs.
4. The system of claim 3 , wherein the center stage multiplies the intermediate values by pre-rotation coefficients to produce pre-rotated intermediate values.
5. The system of claim 4 , wherein the pre-rotated intermediate values are organized into first groups, and wherein the center stage further reorganizes the pre-rotated intermediate values into new groups, each new group containing one of the intermediate values from each of the first groups.
6. The system of claim 3 , wherein the first stage and the second stage are implemented using identical hardware.
7. The system of claim 3 , wherein to perform an N point transform, a set of N inputs are organized into √{square root over (N)} groups, and wherein the first stage performs √{square root over (N)} transforms on the set of N inputs to produce N intermediate values.
8. The system of claim 7 , wherein the N intermediate values are organized into √{square root over (N)} new groups, each new group containing one of the N intermediate values from each of the √{square root over (N)} intermediate groups.
9. The system of claim 8 , wherein the second stage performs √{square root over (N)} transforms on the set of N intermediate values to produce the N outputs.
10. The system of claim 3 wherein the pre-rotation is a multiplication of the intermediate values by pre-rotation coefficients.
11. The system of claim 3 , wherein the center stage includes data memory.
12. The system of claim 11 , wherein all of the first stage FFT's are performed and stored in the data memory before the second stage FFT's are performed.
13. The system of claim 3 , wherein the center stage includes pre-rotation coefficient memory that stores the pre-rotation coefficients.
14. The system of claim 3 , wherein the center stage multiplies the intermediate values by pre-rotation coefficients to produce pre-rotated intermediate values, and wherein the pre-rotation coefficients are defined by
W
N
k
=
ⅇ
-
j
2
π
k
N
,
where W N k is the pre-rotation coefficient, N is the number of points in the fast Fourier transform, and 0≦k≦N−1.
15. The system of claim 3 , wherein an equation by which the first stage, center stage, and third stage perform an N point fast Fourier transform is given by:
X
(
N
k
1
+
k
0
)
=
∑
m
0
=
0
N
-
1
W
N
m
0
k
0
(
(
∑
m
1
=
0
N
-
1
x
(
N
m
1
+
m
0
)
W
N
m
1
k
0
)
W
N
m
0
k
1
)
=
∑
m
0
=
0
N
-
1
∑
m
1
=
0
N
-
1
x
(
N
m
1
+
m
0
)
W
N
m
1
k
0
W
N
m
0
k
1
W
N
m
0
k
0
=
∑
m
0
=
0
N
-
1
∑
m
1
=
0
N
-
1
x
(
N
m
1
+
m
0
)
W
N
m
1
k
0
N
W
N
m
0
k
1
N
W
N
m
0
k
0
=
∑
m
0
=
0
N
-
1
∑
m
1
=
0
N
-
1
x
(
N
m
1
+
m
0
)
W
N
m
1
k
0
N
+
m
0
k
1
N
+
m
0
k
0
0
≤
k
0
,
k
1
≤
N
-
1
,
where W N k is the pre-rotation coefficient, N is the number of points in the fast Fourier transform, and 0≦k≦N−1.