Recoded radix-2 pipeline FFT processor
A single-path delay feedback pipelined fast Fourier transform processor comprising at least one set of triplet FFT stage means: a first FFT stage means comprising a radix-2 butterfly, a feedback memory, and a multiplication by unity; a second FFT stage means comprising a trivial coefficient pre-multiplication, a radix-2 butterfly, a feedback memory, and a multiplication by selectable unity or W N N/8 ; and a third FFT stage means comprising a trivial coefficient pre-multiplication, a butterfly, a feedback memory, and a complex twiddle coefficient multiplication with coefficients determined using a twiddle factor decomposition technique.
1 . A pipelined fast Fourier transform (FFT) processor for receiving an input sequence, the processor comprising:
at least one FFT triplet having first, second and third butterfly modules connected in series by selectable multipliers for selectively performing trivial co-efficient multiplication and complex co-efficient multiplication on output sequences of adjacent butterfly modules, each of the at least one FFT triplets terminating in a twiddle factor multiplier for applying a twiddle factor to an output of the third butterfly module of the respective triplet, the at least one FFT triplet for receiving the input sequence and for outputting a final output sequence representing an FFT of the input sequence.
2 . The processor of claim 1 , wherein each butterfly module includes a radix-2 butterfly unit and a feedback memory.
3 . The processor of claim 2 , wherein, for an input sequence of N samples, an output sequence X(k, n) of each butterfly module is equal to
x
(
n
)
+
(
-
1
)
k
x
(
n
+
N
2
)
.
4 . The processor of claim 1 , wherein at least one of the selectable multipliers for performing trivial co-efficient multiplication is integrated in an adjacent butterfly module.
5 . The processor of claim 1 , wherein the selectable multipliers each include a multiplier and a switch for bypassing the multiplier.
6 . The processor of claim 1 , wherein the first and second butterfly modules are connected by a selectable multiplier for selectively applying trivial co-efficient multiplication.
7 . The processor of claim 6 , wherein the second and third butterfly modules are connected by a selectable multiplier for performing trivial co-efficient multiplication and a selectable multiplier for performing the complex co-efficient multiplication W N N/8 .
8 . The processor of claim 2 , wherein, for an input sequence having N samples, the feedback memories for the first, second and third butterfly modules hold N2, N/4 and N/8 samples, respectively.
9 . The processor of claim 1 wherein the input sequence is of length N, where (log 2 N)mod3=1, the processor having a plurality of FFT triplets in seriatim and further including an FFT terminator having a butterfly unit and a corresponding memory sized to hold a single sample, the FFT terminator for receiving the output sequence from the final twiddle factor multiplier and for performing a butterfly operation on the received output sequence to render an FFT of the input sequence.
10 . The processor of claim 1 wherein the input sequence is of length N, where (log 2 N)mod3=2, the processor having a plurality of FFT triplets in seriatim and further including an FFT terminator having first and second butterfly units having corresponding memories sized to hold two samples and a single sample respectively, the first butterfly unit connected to the second butterfly unit by a selectable multiplier for selectively multiplying the output of the first butterfly unit by −j, the FFT terminator for receiving the output sequence from the final twiddle factor multiplier and for performing a pair of butterfly operations on the received output sequence to render an FFT of the input sequence.
11 . The processor of claim 1 , wherein the twiddle factor multiplier is a cordic rotator.
12 . A pipelined fast Fourier transform (FFT) processor for receiving an input sequence of N samples, the processor comprising:
at least one FFT triplet, the triplet having:
a first FFT stage having a first stage radix-2 butterfly unit for receiving the input sequence and for providing a first stage output sequence in accordance with a butterfly operation performed on the input sequence, the first stage radix-2 butterfly unit having a first feedback memory connected thereto;
a second FFT stage having a selectable multiplier for selectively multiplying the first stage output sequence by a trivial co-efficient, and a second stage radix-2 butterfly unit for providing a second stage output sequence in accordance with the butterfly operation performed on the output of the selectable multiplier, the second stage radix-2 butterfly unit having a second feedback memory connected thereto; and
a third FFT stage having a multiply selectable multiplier for selectively multiplying the second stage output sequence by at least one of the trivial co-efficient and a complex co-efficient, a third stage radix-2 butterfly unit for providing a butterfly output in accordance with the butterfly operation performed on the output of the multiply selectable multiplier, the third stage radix-2 butterfly unit having a third feedback memory connected thereto, and a multiplier for multiplying the butterfly output by a twiddle factor, to provide an output sequence corresponding to an FFT of the input sequence.
13 . The FFT processor of claim 12 , wherein each of the first, second and third stage output sequences X(k,n) is equal to
x
(
n
)
+
(
-
1
)
k
x
(
n
+
N
2
)
.
14 . The FFT processor of claim 12 , wherein at least one of the butterfly units includes an integrated pre-multiplication function for applying a trivial co-efficient multiplication to a received input sequence.
The FFT processor of claim 12 , further including an FFT terminator determined in accordance with the length N of the input sequence.
15 . A pipelined fast Fourier transform (FFT) processor for receiving an input sequence of N samples, the processor comprising:
at least one FFT triplet, the triplet having:
a first FFT stage having a first stage radix-2 butterfly unit for receiving the input sequence and for providing a first stage output sequence in accordance with a butterfly operation performed on the input sequence, the first stage radix-2 butterfly unit having a first feedback memory connected thereto;
a second FFT stage having a multiply selectable multiplier for selectively multiplying the first stage output sequence by at least one of the trivial co-efficient and a constant complex co-efficient, and a second stage radix-2 butterfly unit for providing a second stage output sequence in accordance with the butterfly operation performed on the output of the selectable multiplier, the second stage radix-2 butterfly unit having a second feedback memory connected thereto; and
a third FFT stage having a selectable multiplier for selectively mUltiplying the second stage output sequence by a trivial co-efficient, a third stage radix-2 butterfly unit for providing a butterfly output in accordance with the butterfly operation performed on the output of the selectable multiplier, the third stage radix-2 butterfly unit having a third feedback memory connected thereto, and a multiplier for multiplying the butterfly output by a twiddle factor, to provide an output sequence corresponding to an FFT of the input sequence.
16 . The FFT processor of claim 15 , wherein each of the first, second and third stage output sequences X(k,n) is equal to
x
(
n
)
+
(
-
1
)
k
x
(
n
+
N
2
)
.
17 . The FFT processor of claim 15 , wherein at least one of the butterfly units includes an integrated pre-multiplication function for applying a trivial co-efficient multiplication to a received input sequence.
18 . The FFT processor of claim 15 , further including an FFT terminator determined in accordance with the length N of the input sequence.
19 . The FFT processor of claim 18 , wherein the FFT terminator includes a butterfly module having a memory sized to store a single sample, for receiving as a terminator input, the output of the third FFT stage multiplier and for performing a butterfly operation on the terminator input to render an FFT of the input sequence of N samples.
20 . The FFT processor of claim 18 , wherein the FFT terminator includes a first butterfly module having a memory sized to store a pair of samples, for receiving as a terminator input, the output of the third stage multiplier and for performing a butterfly operation on the terminator input, and a second butterfly module connected to the first butterfly module of the terminator by a selectable multiplier, the selectable multiplier for selectively multiplying the output of the first butterfly module of the terminator by −j, the second butterfly module having a memory sized to store a single sample and for performing a butterfly operation on the selectively multiplied output of the first butterfly module of the terminator to render an FFT of the output sequence.
21 . A method of performing an FFT on a sequence of N samples in an FFT processor having a butterfly module, the method comprising:
for all integers 1≦x≦log 2 N, repeating the steps of receiving and buffering
N
2
x
samples at a time from a sequence having N samples;
generating a 2-point FFT using the n th and the
(
n
+
N
2
x
)
th
samples;
selectively multiplying the generated 2-point FFT sequence by a complex valued multiplicand;
terminating the FFT using a termination sequence determined in accordance with a (log 2 N)mod3 relationship.
22 . The method of claim 21 wherein the complex valued multiplicand is selected from a list including 1,
-
j
,
2
2
-
j
2
2
,
and a complex twiddle factor co-efficient.
23 . The method of claim 21 wherein (log 2 N)mod3=1 and the step of terminating the FFT includes buffering a sample received from the final selective multiplication and performing a 2-point FFT using the buffered sample and the subsequent sample in the sequence to obtain the FFT of the sequence of N samples.
24 . The method of claim 21 wherein (log 2 N)mod3=2 and the step of terminating the FFT includes:
buffering a pair of samples received from the final selective multiplication and performing pair-wise 2-point FFTs using the two buffered samples and the two subsequent samples in the sequence;
selectively multiplying the result of the pair-wise 2 point FFT by −j; and
buffering a sample received from the selective multiplication of the pair-wise 2-point FFT and performing a 2-point FFT using the buffered sample and the subsequent sample in the sequence to obtain the FFT of the sequence of N samples.