PROCESSING DEVICE AND METHOD FOR PERFORMING A ROUND OF A FAST FOURIER TRANSFORM
A data processing device and a method for performing a round of an N point Fast Fourier Transform are described. The round comprises computing N output operands on the basis of N input operands by applying a set of N/P radix-P butterflies to the N input operands, wherein P is greater or equal two and the input operands are representable as N/(M*P)̂ 2 input operand matrices, wherein M is greater or equal one, each input operand matrix is a square matrix with M*P lines and M*P columns, and each column of each input operand matrix contains the input operands for M of said butterflies.
1 . A data processing device for performing a round of an N point Fast Fourier Transform, the data processing device comprising:
an input operand memory unit; and
an input buffer, wherein
the round comprises computing N output operands on the basis of N input operands by applying a set of N/P radix-P butterflies to the N input operands, wherein P is greater or equal two and the input operands are representable as a set of N/(M*P)̂2 input operand matrices (M 1 , M 2 ), wherein M is greater or equal one, each input operand matrix is a square matrix with M*P lines and M*P columns, and each column of each input operand matrix contains the input operands for M of said butterflies, the data processing device is arranged to compute, for each of said input operand matrices, a corresponding output operand matrix by:
reading the respective input operand matrix from the input operand memory unit and buffering it as a whole in the input buffer, and
for each column of the buffered input operand matrix, computing the corresponding column of the output operand matrix by applying the respective M butterflies to the respective column.
2 . The device of claim 1 configured to perform said reading of the respective input operand matrix from the input operand memory unit by reading the respective input operand matrix line by line.
3 . The device of claim 2 configured to perform said reading of the respective input operand matrix from the input operand memory unit line by line by
reading the lines of the respective input operand matrix in M*P successive clock cycles,
and wherein said computing of the corresponding column of the output operand matrix comprises:
computing the corresponding column in a single clock cycle.
4 . The device of claim 1 is arranged to store the M*P lines of each of said input operand matrices at contiguous addresses in the input operand memory unit.
5 . The device of claim 1 , wherein the input operand memory unit is a random-access memory unit.
6 . The device of claim 1 , arranged to read a current column of the buffered input operand matrix from the input buffer, apply the respective M butterflies to the current column, and write a line of a next input operand matrix to that region of the input buffer that is occupied by the current column of the buffered input operand matrix.
7 . The device of claim 6 , arranged to read said current column of the buffered input operand matrix from the input buffer within a single clock cycle and to write said line of said next input operand matrix to said region of the input buffer within the same clock cycle.
8 . The device of claim 6 , wherein the input buffer comprises a set of (M*P)̂2 individually addressable buffer cells, each cell being capable of buffering one input operand.
9 . The device of claim 1 , wherein the round is the first round of the Fast Fourier Transform.
10 . The device of claim 1 , implemented in a single integrated circuit.
11 . A method for performing a round of a Fast Fourier Transform, the method comprising:
computing N output operands on the basis of N input operands by applying a set of N/P radix-P butterflies to the N input operands, wherein
P is greater or equal two, and
the input operands can be arranged in N/(M*P)̂2 input operand matrices,
M is greater or equal one,
each input operand matrix is a square matrix with M*P lines and M*P columns, and
each column of each input operand matrix contains the input operands for M of said butterflies; and
for each of said input operand matrices, computing a corresponding output operand matrix by:
reading the respective input operand matrix from an input operand memory unit and buffering it as a whole, and
for each column of the respective buffered input operand matrix, computing the corresponding column of the output operand matrix by applying M butterflies to the respective column.
12 . The method of claim 11 , wherein said reading of the respective input operand matrix from the input operand memory unit comprises:
reading the respective input operand matrix line by line.
13 . The method of claim 11 , wherein said reading of the respective input operand matrix from the input operand memory unit line by line comprises:
reading the lines of the respective input operand matrix in M*P successive clock cycles;
and wherein said computing of the corresponding column of the output operand matrix comprises:
computing the corresponding column in a single clock cycle.
14 . The method of claim 11 , comprising:
providing the M*P lines of each of said input operand matrices at contiguous addresses in the input operand memory.
15 . The method of claim 11 , comprising: reading a current column of the buffered input operand matrix from the input buffer, applying the respective M butterflies to the current column, and writing a line of a next input operand matrix to that region of the input buffer that is occupied by the current column of the buffered input operand matrix.