Multi-port mixed-radix FFT

1. A processor for performing a Fast Fourier Transform (FFT), comprising:

at least one radix-2 butterfly structure;

at least one radix-4 butterfly structure;

a buffer structure for inputting a data stream and storing data output from the radix-2 and radix-4 butterfly structures;

FFT logic configured to perform an FFT on a data stream in multiple stages by alternately coupling the data stream to inputs of the radix-2 butterfly structure or to inputs of the radix-4 butterfly structure, the FFT logic being capable of performing at least two different resolution fast Fourier transforms dependent on the inputs selected; and

address generation logic configured to generate buffer addresses for the buffer structure during the multiple stages by reordering bits of a sequential counter, and

wherein the buffer structure is structured in a parallel paired configuration such that addressing for the radix-4 butterfly structure at a first resolution is reusable for addressing the radix-2 butterfly structure at a second resolution.

2. The processor of claim 1 , further comprising: inverse FFT (IFFT) logic configured to perform an IFFT on a receive data stream in multiple stages by alternately coupling the receive data stream to inputs of the radix-2 butterfly structure or to inputs of the radix-4 butterfly structure, the IFFT logic being capable of performing at least two different resolution IFFTs dependent on the inputs selected.

3. The processor of claim 1 , wherein: the buffer structure comprises at least first and second buffers, each arranged as parallel banks of N entries; and entries separated by N are written into adjacent halves of the same addressable location.

4. The processor of claim 3 , wherein: each entry is one byte wide; each addressable location is two bytes wide; and entries separated by N are written to most significant and least significant bytes of the same addressable word.

5. The processor of claim 4 , wherein pairs of bytes written into the same addressable word are read out from the buffer structure simultaneously when addressed with a buffer address corresponding to the addressable word.

6. The processor of claim 1 , wherein

the FFT logic performs the FFT operation in at least first and second stages; and

the address generation logic generates the buffer addresses by reordering bits of the sequential counter in a first manner to produce buffer addresses separated by a first amount in the first stage and by reordering bits of the sequential counter in a second manner to produce buffer addresses separated by a second amount in the second stage.

7. An apparatus for wireless communication, comprising:

at least one radix-2 butterfly structure;

at least one radix-4 butterfly structure;

a buffer structure for inputting a data stream and storing data output from the radix-2 and radix-4 butterfly structures, wherein the buffer structure is structured in a parallel paired configuration such that addressing for the radix-4 butterfly structure at a first resolution is reusable for addressing the radix-2 butterfly structure at a second resolution;

Fast Fourier Transform (FFT) logic configured to generate a transmit symbol by performing an FFT on a data stream in multiple stages by alternately coupling the data stream to inputs of the radix-2 butterfly structure or to inputs of the radix-4 butterfly structure, the FFT logic being capable of performing at least two different resolution fast Fourier transforms dependent on the inputs selected;

address generation logic configured to generate buffer addresses for the buffer structure during the multiple stages by reordering bits of a sequential counter; and

a transmitter for transmitting the transmit symbol.

8. The apparatus of claim 7 , further comprising: inverse FFT (IFFT) logic configured to perform an IFFT on a receive data stream in a multiple stages by alternately coupling the receive data stream to inputs of the radix-2 butterfly structure or to inputs of the radix-4 butterfly structure, the IFFT logic being capable of performing at least two different resolution IFFTs dependent on the inputs selected.

9. The apparatus of claim 7 , wherein: the buffer structure comprises at least first and second buffers, each arranged as parallel banks of N entries; and entries separated by N are written into adjacent halves of the same addressable location.

10. The apparatus of claim 9 , wherein: each entry is one byte wide; each addressable location is two bytes wide; and entries separated by N are written to most significant and least significant bytes of the same addressable word.

11. The apparatus of claim 10 , wherein pairs of bytes written into the same addressable word are read out from the buffer structure simultaneously when addressed with a buffer address corresponding to the addressable word.

12. The apparatus of claim 7 , wherein

the FFT logic performs the FFT operation in at least first and second stages; and

the address generation logic generates the buffer addresses by reordering bits of the sequential counter in a first manner to produce buffer addresses separated by a first amount in the first stage and by reordering bits of the sequential counter in a second manner to produce buffer addresses separated by a second amount in the second stage.

13. A method for performing a fast Fourier transform (FFT), comprising:

performing a Fast Fourier Transform (FFT) on a data stream in multiple stages by alternately coupling the data stream to inputs of a radix-2 butterfly structure or to inputs of a radix-4 butterfly structure;

selecting one of at least two different resolution fast Fourier transforms to be performed on said data stream dependent on the inputs; and

generating buffer addresses for transferring data into or out of a buffer structure during the multiple stages of the FFT by reordering bits of a sequential counter, the buffer structure comprising at least first and second buffers arranged as parallel banks of N entries; and entries separated by N are written into adjacent halves of the same addressable location.

14. The method of claim 13 , wherein:

each entry is one byte wide;

each addressable location is two bytes wide; and

entries separated by N are written to most significant and least significant bytes of the same addressable word.

15. The method of claim 14 , wherein pairs of bytes written into the same addressable word are read out from the buffer structure simultaneously when addressed with a buffer address corresponding to the addressable word.

16. The method of claim 13 , wherein

the FFT logic performs the FFT operation in at least first and second stages; and

the address generation logic generates the buffer addresses by reordering bits of the sequential counter in a first manner to produce buffer addresses separated by a first amount in the first stage and by reordering bits of the sequential counter in a second manner to produce buffer addresses separated by a second amount in the second stage.

17. An apparatus for performing a fast Fourier transform (FFT), comprising:

means for performing a Fast Fourier Transform (FFT) on a data stream in multiple stages by alternately coupling the data stream to inputs of a radix-2 butterfly structure or to inputs of a radix-4 butterfly structure, whereby at least two different resolution fast Fourier transforms may be performed dependent on the inputs selected; and

means for generating buffer addresses for transferring data into or out of a buffer structure during the multiple stages of the FFT by reordering bits of a sequential counter, wherein the buffer structure is structured in a parallel paired configuration such that addressing for the radix-4 butterfly structure at a first resolution is reusable for addressing the radix-2 butterfly structure at a second resolution.

18. The apparatus of claim 17 , wherein: the buffer structure comprises at least first and second buffers, each arranged as parallel banks of N entries; and entries separated by N are written into adjacent halves of the same addressable location.

19. The apparatus of claim 18 , wherein: each entry is one byte wide; each addressable location is two bytes wide; and entries separated by N are written to most significant and least significant bytes of the same addressable word.

20. The apparatus of claim 19 , wherein pairs of bytes written into the same addressable word are read out from the buffer structure simultaneously when addressed with a buffer address corresponding to the addressable word.

21. The apparatus of claim 17 , wherein

the means for performing the FFT includes means for performing the FFT operation in at least first and second stages; and

the means for generating the buffer addresses includes means for generating the buffer addresses by reordering bits of the sequential counter in a first manner to produce buffer addresses separated by a first amount in the first stage and by reordering bits of the sequential counter in a second manner to produce buffer addresses separated by a second amount in the second stage.

22. A software storage apparatus for performing a fast Fourier transform (FFT) including a memory having instructions stored thereon, wherein the instructions are executable by one or more processors, the instructions comprising:

code for performing a Fast Fourier Transform (FFT) on a data stream in multiple stages by alternately coupling the data stream to inputs of a radix-2 butterfly structure or to inputs of a radix-4 butterfly structure, whereby at least two different resolution fast Fourier transforms may be performed dependent on the inputs selected; and

code for generating buffer addresses for transferring data into or out of a buffer structure during the multiple stages of the FFT by reordering bits of a sequential counter, the buffer structure being structured in a parallel paired configuration such that addressing for the radix-4 butterfly structure at a first resolution is reusable for addressing the radix-2 butterfly structure at a second resolution.

23. The software storage apparatus of claim 22 , wherein: the buffer structure comprises at least first and second buffers, each arranged as parallel banks of N entries; and entries separated by N are written into adjacent halves of the same addressable location.

24. The software storage apparatus of claim 23 , wherein: each entry is one byte wide; each addressable location is two bytes wide; and entries separated by N are written to most significant and least significant bytes of the same addressable word.

25. The software storage apparatus of claim 24 , wherein pairs of bytes written into the same addressable word are read out from the buffer structure simultaneously when addressed with a buffer address corresponding to the addressable word.

26. The software storage apparatus of claim 22 , wherein

the code for performing the FFT includes code for performing the FFT operation in at least first and second stages; and

the code for generating the buffer addresses includes code for generating the buffer addresses by reordering bits of the sequential counter in a first manner to produce buffer addresses separated by a first amount in the first stage and by reordering bits of the sequential counter in a second manner to produce buffer addresses separated by a second amount in the second stage.