Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2000-01-25
2003-05-13
Malzahn, David H. (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06564236
ABSTRACT:
FIELD OF THE INVENTION
The invention relates to electronic calculating devices making it possible to calculate the direct or inverse Fourier transform of the product of a complex input symbol of size N times a complex sinusoidal waveform of period n, and their modes of operation. The invention applies, for example, to devices having a so-called “serial” or “pipelined” architecture.
BACKGROUND OF THE INVENTION
In numerous applications, especially in digital terrestrial television applications, using OFDM (Orthogonal Frequency Division Multiplexing) coding for transmission, it is necessary to multiply the input symbol by a complex exponential, before performing the direct or inverse Fourier transform, in particular for adaptive equalization purposes. The solution presently used includes performing the multiplication in a multiplier whose output drives the processor dedicated to the Fourier transform calculations. However, this leads to extra hardware and requires an additional rounding mechanism. So as not to impair the accuracy of calculation, it is necessary to provide additional bits, i.e. to increase the size of the data paths.
Numerous implementations of Fourier transforms which are dedicated or programmed on microprocessors for signal processing are known. Most of these implementations use a variant of the Cooley-Tukey algorithm, well known to the person skilled in the art, which makes it possible to reduce the number of arithmetic operations required to calculate the Fourier transform. In particular, this algorithm thus makes it possible to reduce the calculation of a fast Fourier transform of initial size r
p
, where r represents the “radix” according to the terminology customarily used by the person skilled in the art, into that of r Fourier transforms of size r
p−1
and of additional complex additions and multiplications. By iteratively repeating this reduction, we arrive at the calculation of Fourier transforms of size r, which are easily achievable, especially if r is chosen equal to 2 or 4.
The Cooley-Tukey algorithm uses a calculation graph exhibiting a general butterfly-shaped structure, well known to the person skilled in the art, and commonly referred to by the term “butterfly”. Several hardware architectures are then possible in order to implement a butterfly-shaped calculation structure.
A first solution includes constructing a hardware operator capable of performing a butterfly-type calculation, per butterfly of the graph. However, such a solution can only be implemented for Fourier transforms of small size. A second solution includes constructing just a single hardware operator of the butterfly type for successively performing the calculations corresponding to all the butterflies of all the stages of the graph. Such a solution requires on the one hand a very fast hardware operator, and on the other hand an input memory which is separate from the memory serving to write the intermediate calculation results. This is to avoid access conflicts when a data block enters the operator while the previous block is still undergoing processing.
An intermediate solution includes constructing a hardware operator of the butterfly type per stage of the graph, as well as a storage element, such as, for example, delay lines or shift registers, whose function is to input the data into the operator in the correct order with respect to the butterflies of the graph of the relevant stage. Such architectures are said to be “serial” or “pipelined” according to the usual terminology employed by the person skilled in the art.
More precisely, an electronic device for calculating a Fourier transform of so-called “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 elementary processing means able to perform processings of Fourier transforms of elementary sizes which are smaller than the initial size, on data blocks of sizes which are successively reduced from one stage to the next and, elementary storage means. The expression “initial size” of the Fourier transform is understood to mean the size of the blocks received at the input of the device by the first stage, here and in the subsequent text. The elementary sizes of the Fourier transforms performed by the various stages can be identical and equal to the radix of the Fourier transform. Thus, there may be a “uniform” radix Fourier transform or “mixed” radix Fourier transforms which may differ from one stage to another.
SUMMARY OF THE INVENTION
An object of the invention is to perform the multiplication of an input symbol times a complex exponential while eliminating any additional rounding component other than those already existing with respect to Fourier transform processing.
Another object of the invention is to eliminate any additional calculation noise, while also reducing the additional hardware required to perform this multiplication.
The invention applies to any type of hardware architecture capable of implementing a butterfly-shaped calculation structure. More precisely, the invention proposes an electronic device, comprising processing means able to calculate the direct or inverse Fourier transform of the product of a complex input symbol of size N times a complex sinusoidal waveform of period n, on the basis of elementary processings of the butterfly type corresponding to several stages of a general butterfly-shaped calculation graph. According to a general characteristic of the invention, n is an integer less than N, and the processing means comprise first elementary processing means able simultaneously to perform the multiplication and the Fourier transform calculations relating to the first stage of the graph.
In other words, the invention proposes to carry out the complex multiplication of the input symbol times the sinusoidal waveform of period n, simultaneously with the butterfly-type processings relating to the first stage of the calculation graph. In practice, if a pipelined architecture is used, the complex multiplication will be implemented within the first processing stage (input stage) of the pipelined-architecture device. The other processing stages are not modified relative to the conventional stages of Fourier transform processing.
According to one embodiment of the invention, which applies to any type of hardware architecture, e.g. pipelined or otherwise, the first elementary processing means comprises:
a complex adder/subtractor module of the modified butterfly type with respect to the rank z of the data item within the input symbol and the value of n modulo r, where r denotes the radix of the elementary Fourier transform associated with the first stage;
a memory containing N complex coefficients respectively equal to e
2jq&pgr;/N
, q being an integer;
computation means able to determine the integer q on the basis of the rank z of the input data item, (z varying from 0 to N−1) of the sector p in which the input data item lies (p varying from 0 to r−1) and of n; and
a multiplier able to perform the multiplication of the coefficients extracted successively from the memory times the output values delivered successively by the complex adder/subtractor module.
More precisely, for a direct Fourier transform, the integer q is equal to (p−n)i modulo N, where i is equal to z modulo N/r, and the computation means advantageously comprises a first multiplier calculating the sector p by performing the product of the rank z of the input data item times the ratio r/N.
REFERENCES:
patent: 4101738 (1978-07-01), Bellanger et al.
patent: 6195675 (2001-02-01), Wang et al.
patent: 6393066 (2002-05-01), Moretti et al.
patent: 6408319 (2002-06-01), Cambonie
patent: 2001/0051967 (2001-12-01), Jaber
Fliege, “Orthogonal Multiple Carrier Data Transmission”, European Transactions on Telecommunications and Related Technologies, vol. 3, No. 3, May/Jun. 1992 pp. 255-264.
Shousheng He et al., “Designing pipeline FFT proccesor for ODF (de) modulation” 1998 URSI Int
Cambonie Joël
Mazzoni Simone
Allen Dyer Doppelt Milbrath & Gilchrist, P.A.
Jorgenson Lisa K.
Malzahn David H.
STMicroelectronics SA
LandOfFree
Device and associated method for calculating the direct or... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Device and associated method for calculating the direct or..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Device and associated method for calculating the direct or... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3059937