Methods and apparatus for providing an FFT engine using a reconfigurable single delay feedback architecture
Methods and apparatus for providing an FFT engine using a reconfigurable single delay feedback architecture. In one aspect, an apparatus includes a radix-2 (R2) single delay feedback (SDF) stage that generates a radix-2 output and a radix-3 (R3) SDF stage that generates a radix-3 output. The apparatus also includes one or more radix-2 squared (R2^2) SDF stages that generate a radix-4 output. The apparatus further includes a controller that configures a sequence of radix stages selected from the R2, R3, and R2^2 stages based on an FFT point size to form an FFT engine. The FFT engine receives input samples at a first stage of the sequence and generate an FFT output result that is output from a last stage of the sequence. The sequence includes no more than one R3 stage.
1. An apparatus configured to generate time domain samples for transmitting information across a communication network utilizing one or more Fast Fourier Transform (FFT) engines for time to frequency domain conversion, the apparatus comprising:
a radix-2 (R2) single delay feedback (SDF) stage that generates a radix-2 output;
a radix-3 (R3) SDF stage that generates a radix-3 output;
one or more radix-2 squared (R2^2) SDF stages that generate a radix-4 output;
a controller that configures a sequence of radix stages selected from the R2, R3, and R2^2 stages based on an FFT point size to form an FFT engine, wherein the FFT engine receives input samples at a first stage of the sequence and generate an FFT output result that is output from a last stage of the sequence, and wherein the sequence includes no more than one R3 stage;
a divider that divides an FFT output index associated with the FFT output result by a number associated with the FFT point size, wherein the divider generates a quotient and a remainder;
a bit reverser that bit reverses the remainder to generate a bit reversed remainder;
a multiplier that multiplies the bit reversed remainder by three (3) to generate a modified remainder; and
an adder that adds the quotient to the modified remainder to generate a re-ordered index for the FFT output result.
2. The apparatus of claim 1 , wherein the R3 stage is selected to be the first stage.
3. The apparatus of claim 2 , wherein the sequence further includes no more than one R2 stage.
4. The apparatus of claim 3 , wherein the FFT point size is selected from a group of FFT point sizes comprising 4096, 3072, 2048, 1536, 1024, 512, 256, 126, and 64 point sizes.
5. The apparatus of claim 1 , wherein the R2 stage comprises a modified R2 stage comprising two ports that receive selected input samples.
6. The apparatus of claim 1 , wherein the R3 stage comprises a modified R3 stage comprising three ports that receive selected input samples.
7. The apparatus of claim 1 , further comprising one or more multiplexers within the sequence, wherein each multiplexer selects an output signal from two or more input signals based on a multiplexer control signal, and wherein the output signal is input to a next stage of the sequence.
8. The apparatus of claim 7 , wherein the controller generates the multiplexer control signal for each multiplexer.
9. The apparatus of claim 8 , wherein the controller generates the multiplexer control signal to configure the FFT engine to compute a 4096 point FFT result, and wherein the sequence comprises serially connected stages in the following order from first to last: R2^2, R2^2, R2^2, R2^2, R2^2, and R2^2.
10. The apparatus of claim 8 , wherein the controller generates the multiplexer control signal to configure the FFT engine to compute a 3072 point FFT result, and wherein the sequence comprises serially connected stages in the following order from first to last: R3, R2^2, R2^2, R2^2, R2^2, and R2^2.
11. The apparatus of claim 8 , wherein the controller generates the multiplexer control signal to configure the FFT engine to compute a 2048 point FFT result, and wherein the sequence comprises serially connected stages in the following order from first to last: R2, R2^2, R2^2, R2^2, R2^2, and R2^2.
12. The apparatus of claim 8 , wherein the controller generates the multiplexer control signal to configure the FFT engine to compute a 1536 point FFT result, and wherein the sequence comprises serially connected stages in the following order from first to last: R3, R2, R2^2, R2^2, R2^2, and R2^2.
13. The apparatus of claim 8 , wherein the controller generates the multiplexer control signal to configure the FFT engine to compute a 1024 point FFT result, and wherein the sequence comprises serially connected stages in the following order from first to last: R2^2, R2^2, R2^2, R2^2, and R2^2.
14. The apparatus of claim 8 , wherein the controller generates the multiplexer control signal to configure the FFT engine to compute a 512 point FFT result, and wherein the sequence comprises serially connected stages in the following order from first to last: R2, R2^2, R2^2, R2^2, and R2^2.
15. The apparatus of claim 8 , wherein the controller generates the multiplexer control signal to configure the FFT engine to compute a 256 point FFT result, and wherein the sequence comprises serially connected stages in the following order from first to last: R2^2, R2^2, R2^2, and R2^2.
16. The apparatus of claim 1 , wherein the communication network includes at least one user equipment (UE), a radio tower, a switching network, and a front end accelerator block (FEAB).
17. A method for generating time domain samples for transmitting wireless information utilizing one or more Fast Fourier Transform (FFT) engines to provide time to frequency domain conversion via a communication network, the method comprising:
determining an FFT point size of a FFT output result to be computed;
factoring the point size into a factorization having factors of 2, 3, and 4;
configuring a sequence of radix stages selected from R2, R3, and R2^2 single delay feedback (SDF) stages corresponding to the factors of the factorization to form an FFT engine, wherein the FFT engine receives input samples at a first stage of the sequence and generates the FFT output result that is output from a last stage of the sequence, and wherein the sequence includes no more than one R3 stage;
dividing an FFT output index associated with the FFT output result by a number associated with the FFT point size, wherein the dividing generates a quotient and a remainder;
bit reversing the remainder to generate a bit reversed remainder;
multiplying the bit reversed remainder by three (3) to generate a modified remainder; and
adding the quotient to the modified remainder to generate a re-ordered index for the FFT output result.
18. The method of claim 17 , wherein the FFT point size is selected from a group of FFT point sizes comprising 4096, 3072, 2048, 1536, 1024, 512, 256, 126, and 64 point sizes.
19. The method of claim 17 , wherein the configuring comprises configuring the FFT engine to compute a 3072 point FFT output result, and wherein the sequence comprises serially connected stages in the following order from first to last: R3, R2^2, R2^2, R2^2, R2^2, and R2^2.
20. The method of claim 17 , further comprising selecting the R3 stage to be the first stage.
21. The method of claim 17 , further comprising modifying an R2 stage having two ports configured to receive selected input samples.
22. The method of claim 17 , wherein the communication network includes at least one user equipment (UE), a radio tower, a switching network, and a front end accelerator block (FEAB).