Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1999-07-15
2002-08-06
Mai, Tan V. (Department: 2121)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S400000
Reexamination Certificate
active
06430587
ABSTRACT:
BACKGROUND
The present invention relates to the area of Fast Fourier Transforms (FFT) and in particular to methods for performing FFT on a serial input of blocks of data.
In digital telecommunications new applications for FFT have arisen. The principle of using FFT to modulate data onto multiple orthogonal carrier frequencies is becoming widely spread in different types of communication systems such as wideband cellular mobile radio systems and terrestrial digital video broadcasting.
In all these types of products the main part of the computation carried out is FFT computation. In the new applications mentioned above, in contrast to most of the earlier FFT applications, the input data is not all available at the same time; instead a more or less constant flow of data is received. Thus input buffers are used to store the incoming data. When an input buffer is full, the data is computed in a processing device and written to the same buffer, which is then used as an output buffer or to another output buffer.
One problem with such computations is that the data is written out from the data processor in a different order from how it is read in, depending on the radix used. If radix-2 is used, the order will be bit reversed, i.e. the points will appear in the order given by reversing the binary representation of each point's index. With other radices, groups of bits in the binary representation are reordered instead, while the internal bit order in each group is maintained. This is called digit reversal.
Normally the data points are delivered to the FFT device serially in natural order as they are available. When a complete block of input data has been received, FFT computation is performed on the data block, and the output data is written to the same buffer or to another buffer. The device receiving the computed FFT data expects the output data to be sent serially, in natural order and with the same rate.
As the FFT algorithm changes the order of the data, this means that the output points must be reordered before they are sent to the output. Assuming a buffer size of N points, this means that N read and N write operations must be performed in the buffer before the data can be sent to the output.
A known apparatus for FFT computation uses two buffers, each of which is adapted to alternately connecting to 1) an input source and an output and 2) an FFT computation device. When one buffer is-receiving input data and transmitting output data, the FFT computation device is processing the data in the other buffer. The buffers are then swapped, so that the newly received input data is processed, while the new output data is transmitted from, and new input data is received from, the other buffer.
Before the output data is written from a buffer to the output, and new input data can be read to that buffer, the order of the data points must be changed. This procedure prolongs the computation process significantly.
Another known solution is to use separate output buffers to which the processed data is written from the data processing means. In this way, new input data can be written to the output buffer without the risk of overwriting output data However, extra hardware is required. Also, the actual time of the computations is not reduced.
SUMMARY
Thus it is an object of the invention to provide a method and an apparatus for FFT computation of a constant flow of data.
It is another object of the invention to provide a method and an apparatus for FFT computation of a constant flow of data in which data is received and passed on in natural order with a minimum need for additional hardware.
It is also an object of the invention to provide a method and an apparatus which reduce the time needed for FFT computation by eliminating the need for bit reversal in connection with the FFT computation.
According to the invention, these objects are achieved by eliminating the need for bit reversal in the buffer. This may be done in several ways, as disclosed in the independent claims.
A preferred embodiment of the invention uses the fact that an FFT algorithm can be arranged in two ways: 1) the input data is written to the buffers in a natural order and the transformed data is written to the buffer in a bit reversed or digit reversed order, or 2) the data is written to the buffer in a bit reversed or digit reversed, order and the transformed data is written to the buffer in a natural order.
In the preferred embodiment, input data is written to the buffer alternately in natural order and in bit reversed or digit reversed order. Thus, when the bit reversed or digit reversed output data is read from the buffer, the buffer can be addressed in such a way that the points appear in the natural order. In this case, writing new input data to the buffer in natural order would cause some output data to be overwritten before it was sent to the output. Instead the new input data is written to the buffer in the bit reversed order, which is the sane order that is used for reading the output data from the buffer. When the input data that arrived in a bit reversed order has been processed it will appear in the buffer in the natural order. This time the output data will be read in the natural order and hence, the input data can be written to the buffer in the natural order. Consequently, this time the processed output data will appear in the bit reversed order, and so on.
This involves rearranging the FFT algorithm when operating on input data that is in a bit reversed order. This can be done with minimum effect on the FFT device, provided an algorithm with the same radix in all columns is used. The rearrangement consists of simply reversing the order in which the butterfly columns are executed while still using the same twiddle factors. This arrangement causes the output data to appear in the output buffer in natural order. An FFT device that is adapted for one of the structures is also well suited for the other structure. How to use the reverse algorithm is well known to the person skilled in the art.
When data is received in the buffer in natural order, the transformed data appears in the buffer in bit reversed or digit reversed order. To avoid having to change the order of the data in the buffer before reading it to the output, the buffer is addressed in a bit reversed or digit reversed order. This gives rise to one problem: reading the new data to the buffer in the same order as before, would cause the old data to be over-written before it could be outputted. Therefore, according to the invention, the new data is written to the buffer in reverse order.
The invention offers the following advantages:
A constant flow of data can be received in natural order, processed according to an FFT algorithm and transmitted in natural order.
The execution time for one FFT is reduced with N read cycles and N write cycles to the memory buffers at a negligible hardware cost and increased complexity.
Thus, the FFT device can perform the same number of computations per time unit at reduced power consumption, or the rate at which FFTs are being computed may be increased.
REFERENCES:
patent: 3731284 (1973-05-01), Thies
patent: 4821224 (1989-04-01), Liu et al.
patent: 4977533 (1990-12-01), Miyabayashi et al.
patent: 5268853 (1993-12-01), Tanaka et al.
patent: 5297070 (1994-03-01), Hua et al.
patent: 5365470 (1994-11-01), Smith
patent: 5473556 (1995-12-01), Aguilar et al.
patent: 6081821 (2000-06-01), Hopkinson
Choinski, et al., “Generation of Digit Reversed Address Sequences for Fast Fourier Transforms”, IEEE Transactions on Computers, vol. 40, No. 6, Jun. 1991.
Walker, J., “A New Bit Reversal Algorithm”, IEEE Transactions on Acoustics, Speech, and Signal Processing, vol. 38, No. 8, Aug. 1990.
Rodriguez, J., “An Improved FFT Digit-Reversal Algorithm”, IEEE Transactions on Acoustics, Speech, and Signal Processing, vol. 37, No. 8, Aug. 1989.
Burns Doane Swecker & Mathis L.L.P.
Mai Tan V.
Telefonaktiebolaget LM Ericsson (publ)
LandOfFree
Method and apparatus for FFT computation does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for FFT computation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for FFT computation will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2974463