PROCESSING DEVICE AND METHOD FOR PERFORMING A STAGE OF A FAST FOURIER TRANSFORM

摘要

A data processing device and a method for performing second or next stage of an N point Fast Fourier Transform is suggested. The processing device comprises an input operand memory unit and an input buffer comprising a plurality of addressable memory cells arranged in lines and columns. Furthermore, the device comprises a number of radix-P operation units for producing output operands that are buffered in an output buffer. Input operands are read from the input operand memory unit and buffering into the input buffer. The input operands are stored and fetched from the input buffer according to a reordering scheme that allows efficient parallel processing of the operands by the butterflies and the buffering of subsequent input operands.

主权项

1. A data processing device for performing a stage of an N point Fast Fourier Transform, the stage 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, with N being a positive integer and P being a value equal to 2 or 4, wherein the data processing device comprises:
an input operand memory unit arranged to store a plurality of input operands addressable in blocks of K operands, with K being a positive integer; an input buffer comprising a plurality of addressable memory cells arranged in lines and columns; K/P radix-P operation units for calculating the N/P radix-P butterflies, each operation unit being connected to the input buffer; a logic circuit arranged to control the input operand memory unit and the input buffer according to an addressing scheme so as to:
read P subsequent blocks of K input operands from the input operand memory unit;buffer the P subsequent blocks into P subsequent lines of the input buffer;transfer K column oriented input operands from K/P subsequent columns of the input buffer to the radix-P operation units for processing by the radix-P operation units;repeat transferring of the K column oriented input operands from the K/P subsequent columns of the input buffer to the radix-P operation units for processing until K of the columns of the input buffer are transferred and processed;read P further subsequent blocks of K input operands from the input operand memory unit;buffer the P further subsequent blocks into P subsequent columns of the input buffer;transfer K line oriented input operands from K/P subsequent lines of the input buffer to the radix-P operation units for processing by the radix-P operation units;repeat transferring of the K line oriented input operands from the K/P subsequent lines of the input buffer to the radix-P operation units for processing until K of the lines of the input buffer are transferred and processed.