Pipelined FFT processor with memory address interleaving

• US 7,428,564 B2
• Filed: 05/13/2004
• Issued: 09/23/2008
• Est. Priority Date: 11/26/2003
• Status: Expired due to Fees

• Current Assignee: Microsemi Storage Solutions Ltd. (Microchip Technology Incorporated)
• Original Assignee: RAD3 Communications Incorporated
• Inventors: Graumann, Peter J. W., Gibb, Sean G.
• Primary Examiner(s): Mai, Tan V.
• Application Number:
  US10/844,316
• Publication Number:
  US 20050114420A1
• Time in Patent Office: 1,594 Days
• Field of Search: 708/409
• US Class Current: 708/409
• CPC Class Codes: G06F 17/142 Fast Fourier transforms, e.g. using a Cooley-Tukey type algorithm

Abstract

A fast Fourier transform 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 the 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 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 the series of input samples to provide a serial output;

an interleaver for receiving the serial output of the first butterfly unit, for permuting samples in the serial output to provide an output sequence organized as a pairwise series of samples the interleaver comprising

a plurality of memory elements, each element having a write storage address for storing a sample from the serial output, wherein the number of memory elements is less than the number of samples in the serial output, and

an interleaver controller for receiving a sample from the serial output, determining the write storage address of one of the plurality of memory elements for storing the sample, writing the sample to the memory element associated with the determined write storage address, determining a read storage address associated with a memory element, and reading out the sample stored in the memory element associated with the determined read storage address to provide a sample of an output sequence, wherein the samples from the serial output are interleaved in accordance with a non-repeating pattern; and

a second butterfly unit for serially receiving the output sequence from the interleaver, for performing a second butterfly operation on each pair of samples in the pairwise series of samples of the output sequence 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 of the output sequence, and for performing the second butterfly operation using the received real and imaginary components of each sample of the output sequence.

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 in the series of input 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 of input samples.

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 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 input 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><br><br>\mathrm{mod}<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 the series of input samples and an associated butterfly unit for performing butterfly operations on the series of input 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 serial output resulting from performing a butterfly process on the series of input samples received by the at least one of the plurality of butterfly modules having an interleaving memory, and for permuting the series of samples in the serial output to obtain an output sequence organized as a pairwise series of samples, and for serially providing an associated butterfly unit with the output sequence, the interleaving memory comprising

a plurality of memory elements, each element having a write storage address for storing a sample in the serial output, wherein the number of memory elements is less than the number of samples in the serial output, and

an interleaver controller for receiving a sample from the serial output, determining the write storage address of one of the plurality of memory elements for storing the sample, writing the sample to the memory element associated with the determined write storage address, determining a read storage address associated with a memory element, and reading out the sample stored in the memory element associated with the determined read storage address to provide a sample of an output sequence, wherein the samples from the serial output are interleaved in accordance with a non-repeating pattern.

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

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

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

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

19. The FFT processor of claim 16 wherein the modified butterfly unit includes:

a multiplexer for receiving the samples in the output sequence 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.

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

21. 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.

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

23. The FFT processor of claim 21 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.

24. The FFT processor of claim 23 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.

25. The FFT processor of claim 24 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><br><br>\mathrm{mod}<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.