Fast Fourier transform twiddle multiplication

A Fast Fourier Transform (FFT) processing apparatus, the apparatus comprising:

• a sample memory adapted to store eight complex sample values in each row;
• a transpose memory arranged as 8×8 storage locations;
• a radix-8 butterfly core adapted to retrieve a row of values, perform the radix-8 butterfly, and write output values columnwise into the transpose memory;
• a twiddle memory adapted to store four twiddle values in each row;
• a multiplier module having four complex multipliers, the multiplier module adapted to retrieve a row from the twiddle memory and four adjacent values from the transpose memory, perform a complex multiplication on the four values from adjacent transpose memory locations using values from the twiddle memory row, and write the product back to the four adjacent transpose memory locations;
• and
• a normalization register adapted to receive values read from the transpose memory in a row-by-row manner, normalize the values, and write the normalized values row by row to original locations in the sample memory, for sample values corresponding to one of data FFTs, channel estimation FFTs, local and wide identification channel processing, or fine timing IFFTs, and further adapted to receive values read from the transpose memory in a column-by-column manner, normalize the values, and write the normalized values row by row to original locations in the sample memory, for sample values corresponding to one of estimation IFFTs, pilot FFTs, or pilot IFFTs.

A method of performing a Fast Fourier Transform (FFT) processing operation, the method comprising:

• reading a plurality of rows of sample memory equal to a radix of the FFT;
• determining the butterflies for values in a row of the sample memory and writing the butterfly values columnwise to a transpose memory;
• retrieving a row of twiddle factors from a twiddle ROM having a plurality of twiddle factor values stored in the row;
• multiplying a plurality of butterfly values with the twiddle factor values in a single cycle to generate twiddled butterfly values;
• writing the twiddled butterfly values back to memory locations of the plurality of butterfly values in the transpose memory;
• reading values from the transpose memory in a row-by-row manner if the plurality of rows read from the sample memory correspond to one of data FFTs, channel estimation FFTs, local and wide identification channel processing, or fine timing IFFTs;
• reading values from the transpose memory in a column-by-column manner if the plurality of rows read from the sample memory correspond to one of estimation IFFTs, pilot FFTs, or pilot IFFTs;
• sending, to a normalization register, the values read from the transpose memory;
• normalizing the values in the normalization register;
• and
• writing the normalized values row by row to original locations in the sample memory.

A Fast Fourier Transform (FFF) processing apparatus, the apparatus comprising:

• means for storing a number of samples values stored in each row equal to a radix of the FFT;
• means for transposing a plurality of values;
• means for operating a butterfly core configured to receive a row of values from sample memory, perform a butterfly operation on the values, and write results to a column of transpose memory;
• means for multiplying a predetermined number of adjacent values from the transpose memory with a corresponding twiddle factor and writing results to same locations of the adjacent values in the transpose memory;
• means for reading values from the transpose memory in a row-by-row manner for sample values corresponding to one of data FFTs, channel estimation FFTs, local and wide identification channel processing, or fine timing IFFTs;
• means for reading values from the transpose memory in a column-by-column manner for sample values corresponding to one of estimation IFFTs, pilot FFTs, or pilot IFFTs;
• and
• means for normalizing the values read from the transpose memory prior to writing the values row by row to original locations in the sample memory.

A tangible computer-readable storage medium encoded with a computer program configured to cause a computer to perform the steps comprising:

• reading a plurality of rows of sample memory equal to a radix of an FFT;
• performing a butterfly operation on values in a row of the sample memory and writing resulting butterfly values columnwise to a transpose memory;
• retrieving a row of twiddle factors having a plurality of twiddle factor values stored in the row;
• multiplying a plurality of butterfly values with the twiddle factor values in a single cycle to generate twiddled butterfly values;
• writing the twiddled butterfly values back to memory locations of the plurality of butterfly values;
• reading values from the transpose memory in a row-by-row manner for the plurality of rows read from the sample memory corresponding to one of data FFTs, channel estimation FFTs, local and wide identification channel processing, or fine timing IFFTs;
• reading values from the transpose memory in a column-by-column manner for the plurality of rows read from the sample memory corresponding to one of estimation IFFTs, pilot FFTs, or pilot IFFTs;
• sending, to a normalization register, the values read from the transpose memory;
• normalizing the values in the normalization register;
• and
• writing the normalized values row by row to original locations in the sample memory.