Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Patent
1998-04-20
2000-08-01
Malzahn, David H.
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
708408, G06F 1714
Patent
active
060980885
DESCRIPTION:
BRIEF SUMMARY
The present invention relates to real-time pipeline fast fourier transform processors and, in particular, such processors based on a radix-2.sup.2 algorithm.
Pipeline digital fourier transform processors are a specified class of processors used to perform DFT computations. A real-time pipeline processor is a processor whose processing speed matches the input data rate, i.e. the data acquisition speed for continuous operation. For an FFT processor, this means that a length `N` DFT must be computed in `N` clock cycles since the data acquisition speed is one sample per cycle. Pipeline operation enables a partial result, obtained from a preceding stage of the processor, to be immediately used in a following stage, without delay.
FFT processors find application, inter alia, in digital mobile cellular radio systems where there exists considerable constraints on power consumption and chip size. The primary constraining factor may, therefore, be chip complexity, in terms of the number of adders, the number of multipliers, data storage requirements and control complexity, rather than speed of operation.
The present invention emerges from a new approach to the design of real-time pipeline FFT processors. The architecture of a real-time FFT processor, according to the present invention, can be described as a radix-2.sup.2 single-path delay feedback, or R2.sup.2 SDF, architecture. Such a processor can operate on the basis of a hardware oriented radix-2.sup.2 algorithm, developed by integrating a twiddle factor decomposition technique in a divide and conquer approach to form a spatially regular signal flow graph. In a divide and conquer technique the computation of a DFT is decomposed into nested DFTs of shorter length. Divide and conquer techniques are well known in the derivation of fast algorithms and, in the case of the present invention, refer to approachs in which an N-point DFT is decomposed into successively smaller DFTs which are then computed separately and combined to give the final result. The twiddle factor refers to intervening phase shift, or rotational factor. In the present invention, two stages of radix-2 decomposition are performed together and re-decomposed, so that the first stage has only trivial factors which do not require multiplication. However, it should be noted that the two steps are not computed simultaneously.
The algorithm used in the present invention is referred to as a radix-2.sup.2 algorithm because it has the same multiplicative complexity as a radix-4 algorithm but requires radix-2 butterflies in its signal flow graph. The architecture of the processor is described as a single-path delay feedback because only a single data path exists between butterfly stages and each butterfly uses a FIFO buffer in the feedback loop. The signal flow graph is described as spatially regular, because only every alternate column in the SFG has a non-trivial multiplicative operation. This contrasts with an ordinary radix-2 SFG in which there is a non-trivial multiplication in every column in the SFG.
A pipeline DFT processor is characterised by real-time continuous processing of the data sequence passed to the processor. The time complexity of the processor is N and, therefore, it is an AT.sup.2 non-optimal approach with AT.sup.2 =O(N.sup.3), since the area lower bound is O(N). However, in ["Fourier transform in VLSI" - C. D. Thompson, IEEE Trans. Comput., C-32(11):1047-1057, Nov. 1983], it has been suggested that for real-time processing a new metric should be introduced, since it is necessarily non-optimal given the time complexity of O(N). Although asymptotically almost all the feasible approaches have reached the area lower bound, [see S. He and M. Torkelson "A new expandable 2D systolic array for DFT computation based on symbiosis of 1D arrays" Proc. ICA.sup.3 PP'95, pages 12-19, Brisbane Australia Apr 1995], one particular class of pipeline processors with the application of recursive Common Factor Algorithm, (collectively known as Fast Fourier Transform), [see C. S. Burrus "Index mapping for mul
REFERENCES:
patent: 3746848 (1973-07-01), Clary
patent: 3892956 (1975-07-01), Fuss
patent: 4563750 (1986-01-01), Clarke
patent: 5293330 (1994-03-01), Sayegh
patent: 5808925 (1998-09-01), Ito et al.
"Fourier Transforms in VLSI", Thompson, Clark D., IEEE Transactions On Computers, vol. C-32, No. 11, Nov. 1983, pp. 1047-1057.
"A New Expandable 2D Systolic Array for DFT Computation Based on Symbiosis of 1D Arrays", He, Sousheng, and Torkelson, Mats, IEEE, 1995, pp. 12-19.
"Index Mappings for Multidimensional Formultation of the DFT and Convolution", Burrus, C. Sidney, IEEE Transactions On Acoustics, Speech, And Signal Processing, vol. ASSP-25, No. 3, Jun. 1997, pp. 239-242.
"A Radix 4 Delay Commutator for Fast Fourier Transform Processor Implementation", Swartzlander, Earl E., Young, Wendell K.W., Joseph, Saul J., IEEE Journal Of Solid-State Circuits, vol. SC-19, No. 5, Oct. 1984, pp. 702-709.
"A Fast Single-Chip Implementation of 8192 Complex Point FFT", Bidet E., Castelain D., Joanblanq, C. and Senn, P., IEEE Journal Of Solid-State Circuits, vol. 30, No. 3, Mar. 1995, pp. 300-305.
"Principles of Modulation and Channel Coding for Digital Broadcasting for Mobile Receivers", Alard, M. and Lasalle, R., EBU Review, Technical No. 224, Aug., 1987, pp. 47-69.
"Pipeline and Parallel-Pipeline FFT Processors for VLSI Implementations", Wold, Erling H. and Despain, Alvin M., IEEE Transactions On Computers, vol. C-33, No. 5, May 1984, pp. 414-426.
"Fourier Transform Computers Using CORDIC Iterations", Despain, Alvin M., IEEE Transactions On Computers, vol. C-23, No. 10, Oct. 1974, pp. 993-1001.
Introduction To Digital Signal Processing, Proakis, John G. and Manolakis, Dimitris G., Macmillan Publishing Company, 1989, preface only.
"A Radix-8 Wafer Scale FFT Processor", Swartzlander, Jr., Earl E., Jain, Vijay, K. and Hikawa, Hiroomi, Journal of VLSI Signal Processing, 4, 165-176, Kluwer Academic Publishers (1992), pp. 165-176.
"A Pilelined FFT Processor for Word-Sequential Data", Bi, Guoan and Jones, E.V., IEEE Transactions On Acoustics, Speech, And Signal Processing, vol. 37, No. 12, Dec. 1989, p. 1982-1985.
"Very Fast Fourier Transform Algorithms Hardware for Implementation", Despain, Alvin M., IEEE Transactions On Computers, vol. C-28, No. 5, May 1979, pp. 333-341.
"Radix-2 FFT-Pipeline Architecture With Reduced Noise-To-Signal Ratio", Storn, R., IEE Proc.-Vis. Image Signal Process, vol. 141, No. 2, Apr. 1994, pp. 81-86.
He Shousheng
Torkelsson Mats
Malzahn David H.
Teracom AB
LandOfFree
Real-time pipeline fast fourier transform processors does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Real-time pipeline fast fourier transform processors, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Real-time pipeline fast fourier transform processors will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-673657