Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1999-08-11
2001-06-12
Mai, Tan V. (Department: 2121)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S404000
Reexamination Certificate
active
06247034
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to fast Fourier transforming apparatus and method for performing fast Fourier transform.
In accordance with recent development in digital communication techniques and semiconductor integration techniques, digitalization has been proceeded in television broadcasting and radio broadcasting. In most of digital broadcasting using ground waves, OFDM (orthogonal frequency division multiplex) is adopted for modulation-demodulation. A variety of data can be efficiently transmitted within a limited frequency band by the OFDM, and the OFDM has a characteristic advantageous to the ground waves that it is excellent in avoiding multipath interference. The OFDM, however, requires a large scale of fast Fourier transform of several thousand samples, and hence, decrease in cost of a fast Fourier transforming apparatus is significantly desired for practical use of the OFDM.
An example of a conventional fast Fourier transforming apparatus is described in “A Channel Demodulator IC for Digital Audio Broadcasting” by A. Delaruelle, et al. (IEEE Custom Integrated Circuit Conference, May 1994). This fast Fourier transforming apparatus includes three RAMs (random access memories) as a storage, one of which is an input buffer RAM for storing input data and the other two of which are fast Fourier transform RAMs for storing immediate data obtained during an operation and output data. When data in number corresponding to the number of samples for the Fourier transform is designated as one symbol, in a processing of continuous plural symbols, a current symbol is processed by using the two fast Fourier transform RAMs and input data of a following symbol is stored in the input buffer RAM.
Another example of the conventional fast Fourier transforming apparatus is described in “A Fast Single Chip Implementation of 8192 Complex Points FFT” by E. Bidet, et al. (IEEE Custom Integrated Circuit Conference, May 1994). This fast Fourier transforming apparatus includes, as a storage, pipeline registers at a predetermined number of stages disposed between operators, and each of the operators is pipeline-operated for the processing. When the pipeline registers are used, although this fast Fourier transforming apparatus is equivalent in the memory capacity to the aforementioned apparatus using the two RAMs, the apparatus using the pipeline registers has a problem that the orders of input data and output data are different from each other because data are output in the order of processing. In a fast Fourier transforming apparatus used for modulation-demodulation, it is preferred that the orders of input data and output data are the same for reducing processes after the fast Fourier transform. Therefore, the apparatus additionally includes a data arranging RAM so as to re-arrange the output data. As a result, the memory capacity of the apparatus using the pipeline registers is equivalent to that of the above-described fast Fourier transforming apparatus using the three RAMs.
A fast Fourier transforming apparatus needs a storage for storing input data of one symbol, intermediate data obtained during the operation and output data. Furthermore, a fast Fourier transforming apparatus used for modulation-demodulation is required to process continuous plural symbols, and hence, it additionally needs another storage for storing input data of a following symbol in parallel with the processing of a current symbol. Since these storages occupy a larger part in the entire fast Fourier transforming apparatus, a cost of the fast Fourier transforming apparatus can be decreased by decreasing a necessary memory capacity.
The two exemplified conventional fast Fourier transforming apparatuses are equivalent in their memory capacities. However, in the case where the fast Fourier transforming apparatus is realized by using ASICs or the like, the former that can use a RAM library as a storage is advantageous in decreasing cost. Therefore, the configuration of the former apparatus is generally adopted in using ASICs or the like.
However, the former apparatus requires the three RAMs each having a memory capacity sufficient for storing data of one symbol: one as the input buffer RAM and two as the fast Fourier transform RAMs. As a result, this fast Fourier transforming apparatus has a problem of a large circuit scale. This problem is more serious as the number of samples of every symbol is increased.
In the present invention, the attention is paid to the following point: When input data of one symbol can be written in the fast Fourier transform RAM after reading output data of a previous symbol from the same fast Fourier transform RAM, the fast Fourier transform RAM can also be provided with the function as the input buffer RAM, so that the input buffer RAM can be omitted.
When the input buffer RAM is omitted, the fast Fourier transform is performed as follows: First, input data is stored in the fast Fourier transform RAM, and a butterfly operation is performed with intermediate data stored in this fast Fourier transform RAM. Ultimately, the data stored in the fast Fourier transform RAM is read as output data.
However, there arises another problem in such a case. With regard to the input/output data stored in the fast Fourier transform RAM, an input data and an output data having a common index, which indicates their orders in the symbols, cannot be stored at the same address in the fast Fourier transform RAM due to a characteristic of the fast Fourier transform algorithm. Accordingly, in the general configuration, input data of a following symbol is written in the order of reading addresses of output data stored in the RAM, and hence, the orders of the input data and the output data are different from each other. In order to make the orders of the input data and the output data accord with each other, the input or output data are re-arranged after being stored in the RAM. However, in this case, it is necessary to provide an additional data arranging RAM having a memory capacity sufficient for storing data of one symbol. As a result, the memory capacity cannot be decreased.
SUMMARY OF THE INVENTION
According to the present invention, a necessary memory capacity required in fast Fourier transform is decreased, thereby decreasing a cost.
Specifically the fast Fourier transforming apparatus of this invention for performing the fast Fourier transform comprises a RAM (random access memory) for storing input data of every symbol, one symbol corresponding to a unit of data for fast Fourier transform; and an FFT processor for performing a fast Fourier transform processing (FFT processing) using a butterfly operation on input data stored in the RAM, wherein the RAM stores data resulting from the FFT processing by the FFT processor on input data of one symbol stored in the RAM as output data of the one symbol, and the FFT processor performs the FFT processing in a manner that, among output data of one symbol and input data of another symbol to be stored in the RAM subsequently to the output data of the one symbol, data having a common index indicating orders thereof in the symbols are stored at the same address in the RAM.
In this fast Fourier transforming apparatus, owing to the FFT processing by the FFT processor, among output data of one symbol and input data of a following symbol, data having a common index indicating their orders in the symbols can be stored at the same address in the RAM. Accordingly, a space area of the RAM from which output data is read can be used as an input buffer for storing input data of a following symbol.
Thus, an input buffer RAM can be omitted without additionally providing a data arranging RAM. As a result, a memory capacity required in the fast Fourier transform can be decreased.
Preferably, the FFT processor includes a RAM address generator for generating an access address for the RAM, and makes an access to the RAM in accordance with an address generated by the RAM address generator, and the RAM address generator converts an address to be generated in every symbo
Furuta Akihiro
Nakai Yuji
Mai Tan V.
Matsushita Electric - Industrial Co., Ltd.
McDermott & Will & Emery
LandOfFree
Fast fourier transforming apparatus and method, variable bit... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Fast fourier transforming apparatus and method, variable bit..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast fourier transforming apparatus and method, variable bit... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2505036