Fast fourier transform (FFT) architecture in a multi-mode wireless processing system
View Patent ↗A system and method Fast Fourier Transform (FFT) method in a multi-mode wireless processing system. The method can include loading an input vector into an input buffer, initializing a second counter and a variable N, where N=log 2 (input vector size), and s is the value of the second counter, performing an FFT stage, and comparing s to N and performing additional FFT stages until s=N. Performing the FFT stage can include performing vector operations on data in the input buffer and sending results to an output buffer, the data in the input buffer comprising a plurality of segments, advancing the value of the second counter; and switching roles of the input and output buffers. The vector operations can include performing Radix-4 FFT vector operations on the four input data at a time and multiplying the resulting output vectors with a Twiddle factor.
1. A Fast Fourier Transform (FFT) method in a multi-mode wireless processing system, the method comprising:
loading an input vector into an input buffer;
initializing a second counter and a variable N, where N=log.sub.2 (input vector size), and s is a value of the second counter;
performing an FFT stage, the FFT stage comprising:
performing vector operations on data in the input buffer and sending results to an output buffer, the data in the input buffer comprising a plurality of segments;
advancing the value of the second counter by a value greater than one; and
switching roles of the input and output buffers; and
comparing s to N, and performing additional FFT stages until s=N.
2. The method of claim 1 , wherein the second counter is initialized to two, advanced by two in the FFT stage, and is set to N in a last FFT stage if N is odd.
3. The method of claim 1 , wherein the vector operations operate on one segment of the data in the input buffer at a time until all of the segments have been operated on.
4. The method of claim 1 , wherein the vector operations comprise:
loading a plurality of input data from the input buffer into a processing unit;
performing Radix-4 FFT vector operations with a Radix-4 FFT engine on the plurality of data loaded in the processing unit to generate a plurality of output vectors;
multiplying each output vector of the plurality of output vectors with a corresponding Twiddle factor having a real component and an imaginary component; and
bypassing multiplication of one of the plurality of output vectors when the corresponding Twiddle factor is unity.
5. The method of claim 4 , further comprising:
bypassing multiplication of the first output vector.
6. The method of claim 4 , wherein if N is odd and the last FFT stage is being executed, two input data are loaded from the input buffer into the processing unit and are used as first and third Radix-4 FFT engine input vectors, wherein second and fourth Radix-4 FFT engine input vectors being set to zero.
7. The method of claim 1 , further comprising:
generating a first address based on a value of the second counter;
retrieving the data in the input buffer based on the first address.
8. The method of claim 4 , wherein the processing unit operates at a multi-mode wireless processing system clock frequency reduced by a factor of four, except for when a last FFT stage is being performed and N is odd, in which case the processing unit operates at the multi-mode wireless processing system clock frequency reduced by a factor of two.
9. The method of claim 8 , wherein a master counter is used as a loop variable that is initialized, advanced, and compared to a length of the data in the input buffer to determine when all of the segments of the data in the input buffer data have been operated on.
10. The method of claim 9 , wherein input buffer addresses are generated as follows:
bits N to (s+1) of the master counter are mapped bits (N−s) to 1 of the input buffer address, bits s to 1 of the master counter are mapped to bits N to (N−s+1) of the input buffer address, and remaining highest-order bits of the input buffer address are set to zero, where bit 1 is the lowest-order bit of the input buffer address and the master counter.
11. The method of claim 10 , wherein the input address is 13 bits.
12. The method of claim 10 , wherein an output buffer address is equal to the input buffer address for all of the FFT stages except for the last FFT stage in which the output buffer address is generated as follows:
bits 13 to 13 -N bits of the output buffer address are set to zero, and if N is even, bits N to 1 of the output buffer follow a first mapping sequence I.sub.2, I.sub.1, I.sub.4, I.sub.3, . . . I.sub.N, I.sub.N−1, and if N is odd, bits N to 1 of the output buffer follow a second mapping sequence I.sub.1, I.sub.3, I.sub.2, I.sub.5, I.sub.4, . . . I.sub.N, I.sub.N−1, where I is the input buffer address, and where bit 1 is the lowest-order bit of the output buffer, where bit 1 is the lowest-order bit of the input and output buffer addresses.
13. The method of claim 4 , wherein the Twiddle factor is generated by:
generating a preliminary Twiddle address;
generating a control word for controlling manipulation of the Twiddle factor;
generating a final Twiddle address;
determining whether the Twiddle factor needs to be accessed from a memory based upon the preliminary Twiddle address; and
if the Twiddle factor needs to be accessed:
reading the Twiddle factor from the memory at the final Twiddle address;
manipulating the Twiddle factor based upon the control word; and
storing a manipulated Twiddle factor in the processing unit.
14. The method of claim 13 , wherein the manipulated Twiddle factor stored in the processing unit is stored in a register.
15. The method of claim 13 , wherein the preliminary Twiddle address is generated as follows:
highest-order (N−s) bits of the preliminary Twiddle address are mapped to bits (N−s) to 1 of the input buffer address, and remaining lower-order bits of the preliminary Twiddle address are set to zero, where bit 1 is the lowest-order bit of the input buffer address.
16. The method of claim 13 , wherein the preliminary and final Twiddle addresses are 11 bits.
17. The method of claim 13 , wherein the control word is three highest-order bits of a product between the preliminary Twiddle address and two lowest-orders bits of the master counter.
18. The method of claim 13 , wherein the Twiddle factor is manipulated according to the control word bits as follows:
first, if bit 1 of the control word XOR bit 2 of the control word=1, the real and the imaginary components of the Twiddle factor are swapped and the real and imaginary components of the Twiddle factor are negated;
second, if bit 2 of the control word=1, the real component of the Twiddle factor are negated; and
third, if bit 3 of the control word=1, the real and imaginary components of the Twiddle factor are negated.
19. The method of claim 13 , wherein the final Twiddle address is generated by:
multiplying the preliminary Twiddle address by two lowest-order bits of the master counter and generating a product;
subtracting bits 9 to 0 of the product from 512 and producing a remainder, where bit 0 is the least significant bit of the product, sending the remainder to a first input of a 2:1 multiplexer, bits 9 to 0 of the product to a second input of the 2:1 multiplexer, and bit 10 of the product to a select input of the 2:1 multiplexer, the final Twiddle address being an output of the 2:1 multiplexer.
20. A system for performing a Fast Fourier Transform (FFT) in a multi-mode wireless processing system, the system comprising:
a processing unit for performing vector operations;
a memory for providing mathematical functions to the processing unit;
a program memory containing instructions for executing an FFT algorithm;
an instruction controller for receiving and executing instructions from the program memory;
a counter configured to store a value indicative of a current stage of the FFT algorithm, where s is a value of the second counter, and wherein the value of the counter is configured to be adjusted by a value greater than one in response to an indication that a stage of the FFT algorithm has completed an operation; and
a pair of buffers that alternate between acting as an input buffer and an output buffer in successive FFT stages of the FFT algorithm, data in the input buffer comprising a plurality of segments.
21. The system of claim 20 , wherein the memory providing mathematical functions contains Twiddle factors.
22. The system of claim 20 , wherein the memory providing mathematical functions is a ROM.
23. The system of claim 20 , wherein the processing unit comprises:
a Radix-4 FFT engine that performs eight complex additions on four input vectors and generates four output vectors;
a Twiddle multiplier for multiplying a generated output vector with an associated Twiddle factor, the Twiddle factor having a real component and an imaginary component;
a serial-to-parallel converter for receiving the four input vectors serially from the input buffer and sending the four input vectors to the Radix-4 FFT engine in parallel;
a parallel-to-serial converter for receiving the four generated output vectors in parallel and delivering the four output vectors serially to the Twiddle multiplier and output buffer;
a set of registers for storing manipulated Twiddle factors in the processing unit;
a Twiddle octant manipulator that manipulates Twiddle factors based upon a control word;
a master counter used as a loop variable for monitoring progress of the FFT algorithm in a given FFT stage;
an input address generator that generates an input buffer address, the input buffer address being used as an output buffer address for all FFT stages except for when a last FFT stage is being performed and N is odd, where N=log 2 (size of data in the input buffer);
a Twiddle address generator for generating a preliminary Twiddle address;
a DiBit interleaving generator that generates the output buffer address for the last FFT stage if N is odd;
a Twiddle address multiplier for generating the control word;
a summer for subtracting bits 9 to 0 of the product generated by the Twiddle address multiplier from 512 and generating a remainder; and
a 2:1 multiplexer for generating the final Twiddle address from the remainder and the product generated by the Twiddle address multiplier.
24. The system of claim 23 , wherein the counter is initialized to two, advanced by two in the FFT stage, and is set to N in the last FFT stage if N is odd.
25. The system of claim 23 wherein the processing unit operates on one segment of the data in the input buffer at a time until all of the segments have been operated on.
26. The system of claim 23 , further comprising a multiplier bypass indicator for indicating when the Twiddle multiplier is to be bypassed.
27. The system of claim 23 , wherein when N is odd and the last FFT stage is being executed, the serial-to-parallel converter receives two input data from the input buffer and the two received input data become the first and third Radix-4 FFT engine input vectors, and the second and fourth Radix-4 FFT engine input vectors are set to zero.
28. The system of claim 23 , wherein the processing unit operates at a multi-mode wireless process system clock frequency reduced by a factor of four, except for when the last FFT stage is being performed and N is odd in which case the processing unit operates at the system clock frequency reduced by a factor of two.
29. The system of claim 23 , wherein the input buffer address are generated as follows:
bits N to (s+1) of the master counter are mapped bits (N−s) to 1 of the input buffer address, bits s to 1 of the master counter are mapped to bits N to (N−s+1) of the input buffer address, and remaining highest-order bits of the input buffer address are set to zero, where bit 1 is the least significant bit of the master counter and input buffer address.
30. The system of claim 23 , wherein the input buffer address is 13 bits.
31. The system of claim 23 , wherein the output buffer address is equal to the input buffer address for all FFT stages except for the last FFT stage in which the output buffer address is generated as follows:
bits 13 to 13 -N bits of the output buffer are set to zero, and if N is even, bits N to 1 of the output buffer follow a first mapping sequence I.sub.2, I.sub.1, I.sub.4, I.sub.3, . . . I.sub.N, I.sub.N−1, and if N is odd, bits N to 1 of the output buffer follow a second mapping sequence I.sub.1, I.sub.3, I.sub.2, I.sub.5, I.sub.4, . . . I.sub.N, I.sub.N−1, where I is the input buffer address, where bit 1 is the lowest-order bit of the input and output buffer addresses.
32. The system of claim 23 , wherein the Twiddle address generator determines if new Twiddle factors need to be accessed from the memory providing mathematical functions and generates a Twiddle address transition indicator indicating that new Twiddle factors need to be accessed from the memory providing mathematical functions, the Twiddle address transition indicator being sent to the set of registers.
33. The system of claim 23 , wherein the preliminary Twiddle address is generated as follows:
highest-order (N−s) bits of the preliminary Twiddle address are mapped to bits (N−s) to 1 of the input buffer address, and remaining lower-order bits of the preliminary Twiddle address are set to zero, where bit 1 is the lowest-order bit of the input buffer address.
34. The system of claim 23 , wherein the control word is three highest-order bits of the product of the preliminary Twiddle address and two lowest-orders bits of the master counter.
35. The system of claim 23 , wherein the Twiddle factor is manipulated according to the control word as follows:
first, if bit 1 of the control word XOR bit 2 of the control word=1, the real and the imaginary components of the Twiddle factor are swapped, and the real and imaginary components of the Twiddle factor are negated;
second, if bit 2 of the control word=1, the real component of the Twiddle factor is negated;
third, if bit 3 of the control word=1, both the real and imaginary components of the Twiddle factor are negated.
36. The system of claim 23 , wherein the remainder is sent to a first input of the 2:1 multiplexer, bits 9 to 0 of the product generated by the Twiddle address multiplier are sent to a second input of the 2:1 multiplexer, bit 10 of the product generated by the Twiddle address multiplier is sent to a select input of the 2:1 multiplexer, and the final Twiddle address is an output of the 2:1 multiplexer.
37. A method, comprising:
loading an input vector into an input buffer;
initializing a counter and a variable N, where N=log.sub.2 (input vector size), and s is a value of the counter;
performing an FFT stage, the FFT stage comprising:
determining a first address based on a value of the counter;
accessing data stored at the input buffer based on the first address;
performing vector operations on the data in the input buffer and sending results to an output buffer; and
advancing the value of the counter by a value greater than one; and
comparing s to N, and performing additional FFT stages until s=N.