Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1998-12-18
2002-06-18
Malzahn, David H. (Department: 2121)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S408000
Reexamination Certificate
active
06408319
ABSTRACT:
FIELD OF THE INVENTION
The invention relates to the field of electronic computing devices, and, more particularly, to an electronic device having a pipeline 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-Tukey 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 performing 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 is 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 pipeline according to terminology well known by one skilled in the art.
More precisely, an electronic device for computing a Fourier transform having a pipeline 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 pipeline architectures are described in an article by Bi and Jones, entitled “A Pipeline 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 is equal to 2N0 for an initial size of a Fourier transform equal to N0, while the minimum theoretical storage capacity is equal to N0.
SUMMARY OF THE INVENTION
The invention provides a different approach to the above described problem. An object of the invention is to provide a device having a pipelined architecture for computing a Fourier transform. The device operates with very high clock frequencies while minimizing the memory size required, which may equal the theoretical minimum. Another object of the invention is to provide such a device using conventional and readily available storage elements, regardless of the implemented technology.
Yet another object of the invention is to provide an electronic device for computing a Fourier transform capable of being easily tested with full scan test methods, which are well known to one skilled in the art. 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.
The invention therefore provides an electronic device having a pipelined architecture for computing a Fourier transform. The electronic device comprises a plurality of successive processing stages connected in series between the input and the output of the device. 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 electronic device comprises at least one radix 4 processing stage. The radix 4 processing stage includes elementary processing means performing processing operations for Fourier transforms of elementary size equal to 4 on blocks of data. An elementary storage means comprising a random access memory is also included in the radix 4 processing stage. In particular, the random access memory comprises a single-access static memory.
The use of a random access memory, whether dual-access (dual port) or single-access (single port), requires specific management for addressing so the intermediate data in the memory can be stored and redelivered in the right order. This management is more complex when the radix of the Fourier transform is greater than 2, and in particular, when it is equal to 4. The single access permits either write-access or read-access at each cycle of the internal clock of the device. This approach goes against all current teachings on the subject, which provides for the use of delay lines or shift registers.
The use of random access memories enables the storage capacity to be reduced stage by stage. Therefore, the total storage capacity of the device is reduced relative to the storage capacity required when using delay lines. Such components are more readily available, particularly, in their simplest form, i.e., a single-access static memory. Random access memories are independent of the technology used, and are compatible with very high clock frequencies.
Various inte
Allen Dyer Doppelt Milbrath & Gilchrist, P.A.
Jorgenson Lisa K.
Malzahn David H.
STMicroelectronics S.A.
LandOfFree
Electronic device for computing a fourier transform and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Electronic device for computing a fourier transform and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Electronic device for computing a fourier transform and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2920669