High speed FFT hardware architecture for an OFDM processor

1. An FFT for an OFDM processor comprising:

two or more FFT stages that receives a set of N data signals, wherein each FFT stage performs FFT operation on r i data signals and outputs transformed N data signals, wherein r i is computed using the equation

N

=

∏

i

=

0

m

-

1

⁢

ri

wherein r i is a power of 2 and m being a number of stages in the FFT.

2. The FFT of claim 1 , wherein the two or more FFT stages comprise a first stage (stage 0 ) FFT and one or more subsequent FFT stages (i th stage, i=1 to (m−1)), wherein the first stage FFT comprises:

a r 0 point FFT module to transform the r 0 samples of received N data signals over (N/r 0 ) clock cycles; and

a storage element coupled to the r 0 point FFT module that stores the r 0 transformed samples of data signals received from the r 0 point FFT stage module and accumulates intermediate outputs of the stage 0 .

3. The FFT of claim 2 , wherein each of the one or more subsequent FFT stages (i th stage, i=1 to (m−1)) comprise:

a MUX to receive the N data signals associated with the i th stage and outputs r i samples of data signals;

a Twiddle ROM;

complex multipliers connected to the MUX receives the r i sample of data signals from the MUX and associated subsequent stage Twiddle ROM coefficients from the Twiddle ROM and outputs complex multiplied r i data signals;

a r i point FFT module to transform the received r i data signals; and

a storage element coupled to store the transformed r i data signals received from the r i point FFT module and accumulates intermediate outputs of the i th stage.

4. The FFT of claim 3 , wherein a number of bits required in the Twiddle ROM in each stage is computed using the equation

2

*

∑

i

=

1

m

-

1

⁢

r

i

*

bt

i

bits

wherein bt i is a bit precision of the real/imaginary components of each twiddle coefficient in the i th stage.

5. The FFT of claim 3 , wherein the Twiddle ROM is a Read Only Memory that stores the complex multiplication coefficients, and wherein the Twiddle ROM is addressed by a counter that sequentially increments the address for the Twiddle ROM.

6. A two-stage sequential FFT for an OFDM processor comprising:

a first stage, wherein the first stage comprises:

a r 0 point FFT module to transform r 0 samples of received N data signals over (N/r 0 ) clock cycles;

a MUX associated with first stage;

a storage element coupled to the MUX associated with the first stage;

a second stage coupled to the first storage element of the first stage, wherein the second stage comprises:

a MUX associated with the second stage to select a set of r 1 samples from the storage element;

a Twiddle ROM associated with the second stage;

complex multipliers connected to the MUX and the Twiddle ROM associated with the second stage receives the r 1 samples of data signals from the MUX associated with the second stage and Twiddle ROM coefficients from the Twiddle ROM associated with the second stage and outputs complex multiplied r 1 data signals; and

an r 1 point FFT module coupled between the complex multipliers and the MUX associated with the first stage transforms the received complex multiplied r 1 data signals and outputs transformed N data signals via the MUX and the storage element associated with the stage 0 .

7. The FFT of claim 6 , wherein a number of bits required in the Twiddle ROM in each stage is computed using the equation

2

*

∑

i

=

1

m

-

1

⁢

r

i

*

bt

i

bits

wherein bt i is a bit precision of the real/imaginary components of each twiddle coefficient in the i th stage and r i is computed using the equation

N

=

∏

i

=

0

m

-

1

⁢

ri

wherein r i is a power of 2 and m being a number of stages in the FFT.

8. The FFT of claim 6 , wherein the Twiddle ROM is a Read Only Memory that stores the complex multiplication coefficients, and wherein the Twiddle ROM is addressed by a counter that sequentially increments the address for the Twiddle ROM.

9. A two-stage sequential FFT for an OFDM processor comprising:

a first stage, wherein the first stage comprises:

a r 0 point FFT module to transform the r 0 samples of received N data signals over (N/r 0 ) clock cycles;

a MUX associated with the r 0 point FFT module of first stage;

a second stage coupled to a storage element of the first stage, wherein the second stage comprises:

a MUX associated with the second stage to select a set of r 1 samples from the storage element of the first stage;

a Twiddle ROM associated with the second stage;

complex multipliers connected to the MUX and the Twiddle ROM associated with the second stage receives the r 1 samples of data signals from the MUX associated with the second stage and Twiddle ROM coefficients from the Twiddle ROM associated with the second stage and outputs complex multiplied r 1 data signals;

a storage element associated with the second stage receives the complex multiplier output of r 1 data signals and stores the complex r 1 data signals; and

an r 1 point FFT module coupled to the storage element associated with the second stage receives the stored r 1 data signals and transforms the received r 1 data signals and outputs the transformed N data signals via the MUX and the storage element associated with the first stage (stage 0 ).

10. The FFT of claim 9 , wherein a number of bits required in the Twiddle ROM in each stage is computed using the equation

2

*

∑

i

=

1

m

-

1

⁢

r

i

*

bt

i

bits

wherein bt i is a bit precision of the real/imaginary components of each twiddle coefficient in the i th stage and r i is computed using the equation

N

=

∏

i

=

0

m

-

1

⁢

ri

wherein r is a power of 2 and m being a number of stages in the FFT.

11. The FFT of claim 9 , wherein the Twiddle ROM is a Read Only Memory that stores the complex multiplication coefficients, and wherein the Twiddle ROM is addressed by a counter that sequentially increments the address for the Twiddle ROM.

12. A two-stage pipelined FFT architecture for an OFDM processor comprising:

a first stage (stage 0 ), wherein the first stage comprises:

a r 0 point FFT module to transform the r 0 samples of received N data signals over (N/r 0 ) clock cycles; and a storage element coupled to the r 0 point FFT module that stores the r 0 transformed samples of data signals received from the r 0 point FFT stage module and accumulates the intermediate outputs of the first stage (stage 0 );

a second stage coupled to the storage element of the first stage, wherein the second stage comprises:

a MUX associated with the second stage to select a set of r 1 samples from the storage element of the first stage;

a Twiddle ROM associated with the second stage;

complex multipliers connected to the MUX and the Twiddle ROM receives the r 1 samples of data signals from the MUX and Twiddle ROM coefficients from the Twiddle ROM and outputs complex multiplied r 1 data signals;

a first storage element associated with the second stage receives the complex multiplier output of r 1 data signals and stores the complex r 1 data signals;

an r 1 point FFT module coupled to the first storage element associated with the second stage receives the stored r 1 data signals and transforms the received r 1 data signals and outputs the transformed N data signals; and

a second storage element associated with the second stage coupled to the r 1 point FFT module stores and outputs the transformed N data signals.

13. The FFT of claim 12 , wherein a number of bits required in the Twiddle ROM in each stage is computed using the equation

2

*

∑

i

=

1

m

-

1

⁢

r

i

*

bt

i

bits

wherein bt i is a bit precision of the real/imaginary components of each twiddle coefficient in the i th stage and r i is computed using the equation

N

=

∏

i

=

0

m

-

1

⁢

ri

wherein r i is a power of 2 and m being a number of stages in the FFT.

14. The FFT of claim 12 , wherein the Twiddle ROM is a Read Only Memory that stores the complex multiplication coefficients, and wherein the Twiddle ROM is addressed by a counter that sequentially increments the address for the Twiddle ROM.