Pipelined FFT processor with memory address interleaving

• US 20050114420A1
• Filed: 05/13/2004
• Published: 05/26/2005
• Est. Priority Date: 11/26/2003
• Status: Active Grant

• Current Assignee: Microsemi Storage Solutions Ltd. (Microchip Technology Incorporated)
• Original Assignee: RAD3 Communications Incorporated
• Inventors: Gibb, Sean G., Graumann, Peter J.W.
• Granted Patent: US 7,428,564 B2
• Time in Patent Office: Days
• US Class Current: 708/404
• CPC Class Codes: G06F 17/142 Fast Fourier transforms, e.g. using a Cooley-Tukey type algorithm

Abstract

An FFT processor using a single delay path and a permuter provides a reduction in the implementation area and a related reduction in power consumption through efficiencies obtained by the modification of a butterfly unit and the use of a novel interleaver. The modified butterfly unit is obtained by removal of complex variable multipliers, which is possible due to the simplification of twiddle factors in the stages that correspond to the modified butterfly unit.

Claims

1. A single path delay fast Fourier transform (FFT) processor for performing an FFT on a series of input samples organized as pairs, the processor comprising:

a first butterfly unit for receiving the series of input samples, for performing a first butterfly operation on each received pair of samples to provide a serial output;

an interleaver for receiving the serial output, for permuting samples in the serial output to provide a permutation as a pairwise series of samples; and

a second butterfly unit for serially receiving the pairwise series of samples from the interleaver, for performing a second butterfly operation on each pair of samples in the pairwise series to obtain an output series of samples corresponding to an FFT of the series of input samples.

2. The FFT processor of claim 1 wherein the second butterfly unit is a modified butterfly unit and includes a set of adders for receiving real and imaginary components of each sample, and for performing the second butterfly operation using the received real and imaginary components of each sample.

3. The FFT processor of claim 1 wherein the first butterfly unit is a modified butterfly unit and includes:

a multiplexer for receiving the series of input samples, for swapping real and imaginary components of selected samples and for providing the selectively swapped components as an output; and

a set of adders, for performing the first butterfly operation using the selectively swapped components from the multiplexer.

4. The FFT processor of claim 3 further including a modulo counter for controlling the multiplexer to perform component swapping on one half of the input samples of the received series.

5. The FFT processor of claim 1 further including:

a modified butterfly unit for receiving the series of input samples, for performing a modified butterfly operation on each received pair of samples to provide a serial output; and

a further interleaver for receiving the serial output of the modified butterfly unit, for permuting the samples in the serial output of the modified butterfly to provide the permuted samples as the input series to the first butterfly module.

6. The FFT processor of claim 5 wherein the modified butterfly unit includes:

a multiplexer for selectively swapping real and imaginary components of the pairs of samples;

a set of adders, for performing the modified butterfly operation using the selectively swapped components from the multiplexer; and

a constant multiplier for selectively applying a constant twiddle factor to the result of the modified butterfly operation and for providing the selectively multiplied result to the further interleaver.

7. The FFT processor of claim 1 wherein the first and second butterfly modules are both multiplierless butterfly units for performing butterfly operations on the received pairs of samples.

8. The FFT processor of claim 1 wherein the interleaver includes:

an addressable memory for receiving and storing the serial output of the first butterfly module; and

an address generator for generating memory addresses at which each result from the first butterfly can be stored.

9. The FFT processor of claim 8 wherein the addressable memory is sized to store one half of the serial output of the first butterfly module.

10. The FFT processor of claim 8 wherein the interleaver further includes a complete compressing permuter for providing the address generator with memory addresses for the first half of the serial output of the first butterfly module.

11. The FFT processor of claim 10 wherein for an x^th sample in the serial output, the complete compressing permuter generates an address in accordance with the formula

$c_m$

( x ) = { x , 0 ≤

x ⁢

 

⁢

mod ⁢

 

⁢

2 m <

2 m - 1 2 m ⁢

⌊

x 2 m ⌋

+ f ⁡

( x ⁢

 

⁢

mod ⁢

 

⁢

2 m - 1 ) , 2 m - 1 ≤

x ⁢

 

⁢

 

⁢

mod ⁢

 

⁢

2 m <

2 m ,

where 2^m is the size of the addressable memory, and

$f<br><br>\left(x\right)=\frac{x}{2^{{\log }_2<br><br>\left(g<br><br>\left(x+1\right)\right)+1}},$

where g(x) is the bitwise-and of the sample and its sign inverse.

12. The FFT processor of claim 11 wherein the complete compressing permuter includes:

a compressing permuter for determining an address in accordance with

$2^m<br><br>\lfloor <br><br>\frac{x}{2^m}\rfloor <br><br>+f<br><br>\left(x<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{mod}<br><br>\text{\hspace{1em}<br><br>}<br><br>2^{m-1}\right);<br><br>$

 

and

a multiplexer for switching between the address determined by the compressing permuter and an address determined in accordance with the position of the sample in the serial output.

13. The FFT processor of claim 11 wherein the address generator includes a sequence permuter for shifting the address generated by the complete compressing permuter to prevent overwriting data not provided to the second butterfly unit.

14. A single path delay fast Fourier transform (FFT) processor for performing an FFT on a series of input samples organized as pairs, the processor comprising:

a plurality of butterfly modules connected in series each having a memory for receiving a series of samples and an associated butterfly unit for performing butterfly operations on the series of samples in the memory, the first butterfly module in the plurality for receiving and storing the series of input samples in memory, the final butterfly module in the plurality for providing a butterfly operation output as a series of samples corresponding to an FFT of the series of input samples; and

at least one of the plurality of butterfly modules having an interleaving memory for receiving and storing a series of samples, and for permuting the samples to obtain a pairwise series of samples, and for serially providing an associated buttefly unit with the permuted pairwise series.

15. The FFT processor of claim 14 wherein the interleaving memory receives the series of samples from a previous butterfly module.

16. The FFT processor of claim 14 wherein the interleaving memory serially receives the series of samples.

17. The FFT processor of claim 14 wherein the at least one of the plurality of butterfly module includes a modified butterfly unit.

18. The FFT processor of claim 17, wherein the modified butterfly unit is a multiplierless butterfly unit.

19. The FFT processor or claim 17 wherein the modified butterfly unit includes a set of adders for receiving real and imaginary components of each sample from the interleaving memory, and for performing the butterfly operation using the received real and imaginary components of each sample.

20. The FFT processor of claim 14 wherein the modified butterfly unit includes:

a multiplexer for receiving the samples from the interleaving memory, for swapping real and imaginary components of selected samples and for providing the selectively swapped components as an output; and

a set of adders, for performing the butterfly operation using the selectively swapped components from the multiplexer.

21. The FFT processor of claim 20 further including a modulo counter for controlling the multiplexer to perform component swapping on one half of the samples.

22. The FFT processor of claim 14 wherein the interleaver includes:

an addressable memory for receiving and storing the serial output of the first butterfly module; and

an address generator for generating memory addresses at which each result from the first butterfly can be stored.

23. The FFT processor of claim 22 wherein the addressable memory is sized to store one half of the serial output of the first butterfly module.

24. The FFT processor of claim 22 wherein the interleaver further includes a complete compressing permuter for providing the address generator with memory addresses for the first half of the serial output of the first butterfly module.

25. The FFT processor of claim 24 wherein for a the x^th sample in the serial output, the complete compressing permuter generates an address in accordance with the formula

$c_m$

( x ) = { x , 0 ≤

x ⁢

 

⁢

mod ⁢

 

⁢

2 m <

2 m - 1 2 m ⁢

⌊

x 2 m ⌋

+ f ⁡

( x ⁢

 

⁢

mod ⁢

 

⁢

2 m - 1 ) , 2 m - 1 ≤

x ⁢

 

⁢

 

⁢

mod ⁢

 

⁢

2 m <

2 m ,

where 2^m is the size of the addressable memory, and

$f<br><br>\left(x\right)=\frac{x}{2^{{\log }_2<br><br>\left(g<br><br>\left(x+1\right)\right)+1}},$

where g(x) is the bitwise-and of the sample and its sign inverse.

26. The FFT processor of claim 25 wherein the complete compressing permuter includes:

a compressing permuter for determining an address in accordance with

$2^m<br><br>\lfloor <br><br>\frac{x}{2^m}\rfloor <br><br>+f<br><br>\left(x<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{mod}<br><br>\text{\hspace{1em}<br><br>}<br><br>2^{m-1}\right);<br><br>$

 

and

a multiplexer for switching between the address determined by the compressing permuter and an address determined in accordance with the position of the sample in the serial output.