Pipelined fast fourier transform processor

Details Pipelined fast fourier transform processor Pipelined fast fourier transform processor

1999-03-12

2001-12-11

Mai, Tan V. (Department: 2121)

Electrical computers: arithmetic processing and calculating

Electrical digital calculating computer

Particular function performed

C708S408000

Reexamination Certificate

active

06330580

ABSTRACT:

BACKGROUND OF THE INVENTION
The present invention relates to a pipelined Fast Fourier Transform processor as is described in the non-characteristic part of claim
1
.
Such a pipelined Fast Fourier Transform processor is already known in the art, e.g. from the published European Patent Application “Pipelined Fast Fourier Transform processor”, publication number 0478128A2. Therein, a pipelined Fast Fourier Transform processor is described, including a cascade of four Butterfly Arithmetic Units, abbreviated with BAU in the prior art document. Each of these units processes data received at its input ports and generates a pair of output signals, which are consecutively applied to the input ports of the next stage, or in case of the final fourth stage, to memory locations via a multiplexer. Within each unit, the output signals , before being delivered to the next unit, are temporarily stored in four registers. Two of the cascaded units of the prior art document can thus be considered as corresponding to the first and second arithmetic unit of the present invention, whereas the four registers included in the first stage of the prior art, can be considered as corresponding to the scratch memory of the pipelined Fast Fourier Transform processor of the invention. The multiplexer together with the memory locations of the prior art thereby constitute the memory arrangement included within the Fast Fourier Transform processor of the invention.
The units of the prior art processor all include the same building blocks for performing a radix-two-operation Fast Fourier Transform, hereafter abbreviated by FFT, operation on their respective input data, as is explained in the prior art document.
For some applications, such as for instance in Very High Speed Digital Subscriber Line transmission and receiving modules, a 512 point real FFT, is to be performed in less than 1024 clock cycles, whereby during each cycle one data point is read from the memory arrangement into the first arithmetic unit. As is well known by a person skilled in the art, performing a 512 point real FFT in fact corresponds to performing a 256 point complex FFT, taken into account some changes such as these explained for instance in the US Patent nr. 5,633,817 “Fast Fourier Transform Dedicated Processor”. However, when performing a 256 point complex FFT using the architecture of the prior art processor, too much multipliers are needed for obtaining the target timing restrictions. Indeed, for performing a 256 point complex FFT, 8 of the prior art radix-2 type BAU's have to be passed. Using only two of these BAU's or stages in cascade, while passing 4 times through the pipeline, already consumes more than 4×256 clock cycles for reading input data from the memory arrangement to the first BAU, definitely already exceeding the target timing restrictions. Therefore, for complying with the timing restrictions, minimum three of these BAU's are required to be put in the cascade. Since each prior art BAU includes 4 multipliers, as is clear from
FIG. 2
of the prior art document, in total thus 12 multipliers have to be included in the processor. Taken however into account the state of the art of the integrated circuit technology at the time of the invention, a total of 12 multipliers would result in a too large integrated circuit area.
Summary of the Invention
An object of the present invention is to provide a Fast Fourier Transform processor of the above known type but which succeeds in compromising both restrictive timing as well as integrated circuit area requirements.
According to the invention, this object is achieved due to the fact that said Fast Fourier Processor is further adapted as is described in the characteristic part of claim
1
.
In this way, two dedicated arithmetic units are provided, a smaller one, only adapted for performing at least one type of butterfly FFT calculations, and a larger one, adapted for performing, besides the aforementioned type, at least one second type of butterfly FFT arithmetic calculations. In stead of thus using three stages in series, now only two of them are needed, a small and a large one. This solution definitely requires less chip area with respect to the prior art solution. With respect to the timing, for performing a 512 point real FFT, this solution only requires 3 passes through the cascade or pipeline, as will be explained more into detail in a further paragraph. The timing is thus within the timing specification.
The above mentioned object is also achieved as described in the characteristic part of claim
2
which is a straightforward alternative of claim
1
and wherein the first arithmetic unit in which the input data are first treated, may as well be the smaller one, whereby the second arithmetic unit which is to be passed in the pipelined structure, is the larger one.
Yet a further characteristic feature of the present invention is described in claims
3
and
4
.
For some applications, it may be desirable to first bypass the first arithmetic unit, after which the second arithmetic unit in the pipeline will execute the first FFT related operation. For these applications a simpler control of the memory arrangement is obtained, especially when the number of butterfly FFT operations to be performed by the arithmetic units is non-even, as will be explained more into detail in the descriptive part of this document.
Still a further characteristic feature of the present invention is described in claim
5
.
If, after the first pass through the pipeline, the final FFT result is not yet obtained, a second pass will be necessary. This claim indicates that the pipeline is always to be followed in the same direction, from the first arithmetic unit to the second, after which the memory arrangement is adapted to deliver the intermediate FFT results back to the first arithmetic unit and so on. This is the direction which was also followed in the prior art FFT processor.
Another characteristic feature of the present invention is described in claims
6
and
7
.
This means that the direction of processing within the pipeline can be reversed after each pass through the pipeline. The reversal of the direction after each pass results in a simpler memory arrangement. Indeed, since the memory arrangement includes some dedicated locations for storing input data, to be delivered to the first arithmetic unit, and dedicated locations for storing intermediate results delivered by the second arithmetic unit, re-use of the connection between the second arithmetic unit and the memory arrangement through re-use of these intermediate FFT results by this second arithmetic unit, definitely results in a simpler arrangement compared to the case where additional connections need to be established between the locations for storing these intermediate results and the first arithmetic unit.
Further characteristic features of the present invention are mentioned in the appended claims
8
to
11
.
The basic computational steps executable by both arithmetic units thereby consist of a radix-4 type Fast Fourier Transform step, whereas the extra alternative steps, executable by the largest of both arithmetic units consist of a radix-2 type Fast Fourier Transform step, a radix-2 type Fast Fourier Transform step followed by an add/subtract step, and a radix-4 type Fast Fourier Transform step preceded by an add/subtract step. All real and complex Fast Fourier Transform as well as all real and complex inverse Fast Fourier Transforms on an amount of points equal to a power of 2, can thereby be realised using a combinations of these mentioned steps, as is well known from e.g. specialised literature in the field. From the same literature it is also known that radix-2 type as well as radix-4 type arithmetic units both can be realised with merely 4 multipliers. Within the most complex arithmetic unit these four multipliers may be shared since only one of the 4 mentioned sets of butterfly Fast Fourier Transform arithmetic calculations is to be performed at a time. Therefore the total amount of multipliers needed wi

Affiliated with

Also associated with

Rating

Pipelined fast fourier transform processor does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Pipelined fast fourier transform processor, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Pipelined fast fourier transform processor will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2585289