Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1998-12-18
2001-11-27
Malzahn, David H. (Department: 2121)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S406000
Reexamination Certificate
active
06324561
ABSTRACT:
FIELD OF THE INVENTION
The invention relates to the field of electronic computing devices, and, more particularly, At to an electronic device having a pipelined architecture for computing a Fourier transform, and a related method.
BACKGROUND OF THE INVENTION
Numerous dedicated Fourier transform implementations, including those programmed on signal processing microprocessors, have been disclosed. Most of these implementations use a variation of the Cooley-Turkey algorithm, which makes it possible to reduce the number of arithmetic operations required for computing the Fourier transform. This algorithm is well known to one skilled in the art.
In particular, the Cooley-Tukey algorithm reduces the computation of a fast Fourier transform of initial size r
P
into that of r Fourier transforms of size r
P−1
, and of supplementary complex multiplications and additions. According to the terminology customarily used by one skilled in the art, r represents the radix. Iterative repetition of this reduction produces the computation of Fourier transforms of size r. These computations can easily be carried out, especially if r is chosen equal to 2 or 4. The Cooley-Tukey algorithm uses a computation graph that takes on the appearance of a structure of a general butterfly shape, and is commonly referred to simply as a butterfly. This appearance is well known to one skilled in the art.
Several hardware architectures are possible for implementing a butterfly-shaped computation structure. A first approach includes a hardware operator capable of performing a butterfly type computation per butterfly of the graph. However, such an approach may be used only for the implementation of Fourier transforms of small size.
A second approach includes just a single hardware operator of the butterfly type, and intending to perform in succession the computations corresponding to all the butterflies of all the stages of the graph. Such an approach has the drawback of requiring a very fast hardware operator. An input memory separate from the memory is required for writing the intermediate computation results. This avoids access conflicts when a data block enters the operator while the previous block is still being processed. It is therefore necessary to provide two memories of N0 complex words, where N0 denotes the initial size of the Fourier transform. This leads to an overall circuit of considerable size, especially when N0 is large.
An intermediate approach includes a hardware operator of the butterfly type per stage of the graph, as well as a storage element. This includes delay lines or shift registers, whose function in to input the data to the operator in the right order, while aware of the butterflies of the graph of the relevant stage. Such architectures are termed serial or pipelined according to terminology well known by one skilled in the art.
More precisely, an electronic device for computing a Fourier transform having a pipelined architecture comprises a plurality of successive processing stages connected in series between the input and the output of the device by internal data paths. These stages respectively comprise processing means and storage means. The processing means performs processing operations for Fourier transforms of smaller elementary sizes than the initial size on blocks of data whose sizes are reduced in succession from one stage to the next.
The term “initial size” of the Fourier transform is understood here and in the remainder of the text to mean the size of the blocks received as input to the device by the first stage. The elementary sizes of the Fourier transforms performed by the various stages may be identical and equal to the radix of the Fourier transform; i.e., a Fourier transform with uniform radix. However, they may be different from one stage to another, as in the case of Fourier transforms with mixed radix.
Examples of pipelined architectures are described in an article by Bi and Jones, entitled “A Pipelined FFT Processor for Word-Sequential Data”, IEEE Transactions on Acoustic Speech and Signal Processing, vol. 37, No. 12, December 1989, pages 1982-1985, and in an article by Bidget et al., entitled “A Fast Single-Chip Implementation of 8192 Complex Point FFT”, IEEE Journal of Solid-State Circuits, vol. 30, No. 3, March 1995, pages 300-305.
The storage means described in these known architectures includes delay lines which are very simple elements to manage. They have the advantage of being generally compact, and use three transistors per stored bit. However, these elements are not always available as standard cells in ordinary libraries of components used in defining and designing integrated circuits. Furthermore, their electrical characteristics are dependent on the technology used, so that the architecture of the circuit must be carefully re-examined each time the technology advances. Such architectures use delay lines whose storage capacity per radix
4
stage is equal to 3N/2, where N is the size of the blocks processed by the stage. The architecture with delay lines, with a per-stage storage capacity equal to 3N/2, allows for processing of Fourier transforms on each symbol, while also delivering data temporally delayed by the length of a symbol, thus enabling the desired correlation to be performed.
In certain applications, especially in terrestrial applications of digital television using OFDM (Orthogonal Frequency Division Multiplex) coding for transmission, the various symbols to be processed by Fourier transforms are separated by a guard interval. More precisely, in an OFDM application, each symbol received is preceded by a guard interval which is identical to the terminal part of the symbol. In this kind of application, it is then particularly advantageous to use this property to detect the temporal position of the various symbols in the incoming flow, and thereby monitor the proper temporal synchronization of these various symbols. In this regard, a correlation of the incoming flow with the last symbol received, and its associated guard interval is generally performed. This additionally requires, in particular, the storage of a complete symbol.
SUMMARY OF THE INVENTION
The invention provides a different approach to the above described problem with respect to the memory size required for the storage of each last symbol received. An object of the invention is to provide a radix
4
processing stage for a device for computing a Fourier transform. The device includes a pipelined architecture capable of operating with very high clock frequencies, and for storing each last symbol received. The process is performed while minimizing the memory size required, while using conventional and readily available storage elements, regardless of the implemented technology.
Another object of the invention is to provide a radix
4
processing stage capable of easily being tested with full scan test methods, which are well known to one skilled in the art. Yet another object of the invention is to take account of any guard interval separating the various symbols to be processed by Fourier transform, especially in terrestrial applications of digital television which use OFDM (Orthogonal Frequency Division Multiplex) coding for transmission. This is done so even if the length of this guard interval is not known a priori.
The invention therefore provides a process for controlling a radix
4
processing stage of an electronic device for computing a Fourier transform, wherein the electronic device has a pipelined architecture. An electronic computing device having a pipelined architecture comprises a plurality of successive processing stages connected in series between the input and the output of the device. These stages respectively comprises processing means and storage means. The processing means performs processing operations for Fourier transforms of smaller elementary sizes than the initial size on blocks of data whose sizes are reduced in succession from one stage to the next. A radix
4
processing stage includes processing means which performs processing operations fo
Allen Dyer Doppelt Milbrath & Gilchrist, P.A.
Jorgenson Lisa K.
Malzahn David H.
STMicroelectronics S.A.
LandOfFree
Process and device for computing a fourier transform having... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Process and device for computing a fourier transform having..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Process and device for computing a fourier transform having... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2577248