Boots – shoes – and leggings
Patent
1995-06-07
1998-06-30
Elmore, Reba I.
Boots, shoes, and leggings
382280, G06F 1500
Patent
active
057743886
DESCRIPTION:
BRIEF SUMMARY
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention concerns Fourier transform calculation devices having a so-called serial or "pipeline" architecture, and their mode of operation.
2. Description of the Related Art
The literature describes many implementations of Fourier transforms that are either dedicated or programmed on signal processing microprocessors. Most of these implementations use a variant of the Cooley-Tukey algorithm, which is well known to the person skilled in the art, and which reduces the number of arithmetic operations required to calculate the Fourier transform. Among other things, this algorithm simplifies the calculation of a fast Fourier transform of size r.sup.p where r represents the "root". as it is usually called by the person skilled in the art, by breaking the calculation down into the calculation of r Fourier transforms of size r.sup.p-1 with further complex multiplications and additions. By applying this simplification iteratively the calculation of Fourier transforms of size r is made easy, especially if r is chosen as equal to 2 or 4, with intermediate additions and multiplications.
The Cooley-Tukey algorithm uses a calculation graph with a butterfly shape, well known to the person skilled in the art.
Various hardware architectures can be used to implement this butterfly calculation structure.
A first solution uses a respective hardware operator capable of carrying out a butterfly type calculation for each butterfly of the graph. This solution is feasible only for implementation of small Fourier transforms, however.
A second solution uses a single butterfly hardware operator which carries out in succession the calculations corresponding to all the butterflies of all the stages of the graph. A solution of this kind has the drawback of needing a very fast hardware operator and an input memory separate from the memory into which intermediate calculation results are written. This is to avoid access conflict when a data block enters the operator while the preceding block is still being processed. It is therefore necessary to provide two memories each having a capacity of N complex words where N denotes the size of the Fourier transform, with the result that the circuit as a whole has a large surface area, especially if N is large.
An intermediate solution is to use a butterfly type hardware operator for each stage of the graph and a memory element the function of which is to present the data to the input of the operator in the correct order, given the butterflies of the graph of the stage in question.
Architectures of this kind are called series or pipeline architectures by the person skilled in the art.
A pipeline architecture circuit for calculating a Fourier transform of predetermined initial size comprises a plurality of successive processing stages connected in series between the input and the output of the circuit by internal data paths. Each stage includes butterfly type processing means for processing Fourier transforms having a predetermined size smaller than the initial size using blocks of data of progressively decreasing size from one stage to the next. These transform sizes can be the same and equal to the root of the Fourier transform. The expression "uniform root Fourier transform" is then used. The transform sizes can be different from one stage to the next in the case of "mixed" root Fourier transforms.
One example of a pipeline architecture of this kind is described in the 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, p. 1982-1985.
Independently of the type of architecture used, the problem arises of the dynamics of the intermediate and output data, given the dynamic of the input data. By "dynamic" is meant in the present context the number of bits, including the sign bit, used to represent the data. Butterfly type hardware operators carry out complex multiplications and additions. It is of course unrealistic to
REFERENCES:
patent: 3746848 (1973-07-01), Clary
patent: 3783258 (1974-01-01), Chwastyk
patent: 3892956 (1975-07-01), Fuss
patent: 3899667 (1975-08-01), Simone
patent: 4534009 (1985-08-01), McGee
patent: 4929954 (1990-05-01), Elleaume
IEEE Transactions on Acoustics, Speech and Signal Processing vol. 37, No. 12, Dec. 1989, New York.
Proceedings of the 7th Symposium on Computer Arithmetic, IEEE Computer Society New York US 4 Jun. 1985, Urbana Illinois pp. 223-230.
IEEE Journal of Solid-State Circuits vol. 20, No. 3, Jun. 1985, New York pp. 761-769.
IEEE Transactions on Acoustics, Speech and Signal Processing vol. 23, No. 2, Apr. 1975, New York pp. 189-201.
Proceedings of the 10th International Conference on Pattern Recognition IEEE Press New York US 16 Jun. 1990, Atlantic City NJ pp. 385-388.
Systems & Computers in Japan vol. 18, No. 12, Dec. 1987, New York pp. 18-27 .
Bidet Emmanuel
Joanblanq Christophe
Elmore Reba I.
France Telecom
Moise Emmanuel L.
LandOfFree
Device for electronically calculating a fourier transform and me 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 for electronically calculating a fourier transform and me, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Device for electronically calculating a fourier transform and me will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-1867062