Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2006-10-10
2006-10-10
Mai, Tan V. (Department: 2193)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
07120658
ABSTRACT:
A more computationally efficient and scalable systolic architecture is provided for computing the discrete Fourier transform. The systolic architecture also provides a method for reducing the array area by limiting the number of complex multipliers. In one embodiment, the design improvement is achieved by taking advantage of a more efficient computation scheme based on symmetries in the Fourier transform coefficient matrix and the radix-4 butterfly. The resulting design provides an array comprised of a plurality of smaller base-4 matrices that can simply be added or removed to provide scalability of the design for applications involving different transform lengths to be calculated. In this embodiment, the systolic array size provides greater flexibility because it can be applied for use with any transform length which is an integer multiple of sixteen.
REFERENCES:
patent: 4777614 (1988-10-01), Ward
patent: 5034910 (1991-07-01), Whelchel et al.
patent: 5093801 (1992-03-01), White et al.
patent: 5168460 (1992-12-01), Tower
patent: 5179714 (1993-01-01), Graybill
patent: 6023742 (2000-02-01), Ebeling et al.
patent: 6098088 (2000-08-01), He et al.
patent: 2276960 (1994-10-01), None
Kung HT, Leiserson CE “Systolic Arrays (for V1SI),” Symposium on Sparse Matrix Computations, p. 256-282, 1978.
Zhang CN, Yun YY “Multidimensional Systolic Networks for Discrete Fourier Transform,” 11 th Annual International Symposium on computer archetecture, p. 215-222, 1984.
Roziner TD, Karpovsky MG “Multidimensional Fourier Transforms by Systolic Archeitecture,” Jounal of VLSI Signal Processing, 4, 343-354, 1992.
Marino F, Swatzlander EE“Parallel Implementation of Multidimensional Transforms Without Interprocessor Communication,” IEEE Transactions on Computers, vol. 48 No. 9, 1999.
Shietun et al., “Design of Array Processors for 2-D Discrete Fourier Transform,” IEEE Trans. Inf. & Syst., vol. E80-D, No. 4, Apr. 1987.
Thompson CD, “Fourier Transforms in VLSI,” IEEE Transactions on Computers, vol. C-32 No. 11, Nov. 1983.
Izidor et al., “VLSI Architectures for Multidimensional Fourier Tranform Processing,” IEEE Transactions on Computers, vol. C-36, No. 11, Nov. 1987.
Jones KJ “High Throughput, Reduced Hardware Systolic Solution to Prime Factor Discrete Fourier Transform Alogorithm,” IEEE Proceed., vol. 137, Pt. E, No. 3 May '90.
Marwood et al. “Matrix Product Machine and the Fourier Transform,” IEEE Proceedings, vol. 137, Pt. G, No. 4, Aug. 1990.
Choi et al., “A New Linear Systolic array for FFT Computation,” IEEE Trans. on Cir. and Syst, II: Analog and Digital Signal Proc. vol. 39, No. 4, Apr. 1992.
Arabepola B “Discrete Fourier Transform Processor Based on the Prime Factor Algorithm,” IEEE Proceedings, vol. 130, Pt. G, No. 4, Aug. 1983.
Bayoumi et al. “A VLSI Arraay For Computing the DFT Based on RNS,” ICASSP 86 Tokyo, p. 2147-2150, 1986 IEEE.
Beraldin et al. “Efficient One-Dimensional Systolic Array Realization of the Discrete Fourier Transform,” IEEE Trans. on Cir. and Syst., vol. 36, No. 1, Jan. 1989, p. 95-100.
Chang et al. “A New Systolic Array for Discrete Fourier Transform,” IEEE Trans. on Acoustics, Speech and Sig. Proc., vol. 36, No. 10, Oct. 1988, p. 1665-6.
Shousheng et al. “A New Apporach to Pipeline FFT Processor,” Proceedings of 10th Int. Parallel Proc. Symposium, 1063-7133/96, p. 766-770.
Hyesook et al. “Multidimensional Systolic Arrays for the Implementation of Discrete Fourier Transforms,” Transactions on Sig. Proc. vol. 47, No. 5, May 1999, p. 1359-70.
Colin et al. “A New FFT Architecture and Chip Design for Motion Compensation Based on Phase Correlation,” Proc. of 1996 Int. Conference on Apl-Specific Systems, Archeitectures, and Processors, 1996, p. 83-92.
Sungwook et al. “A Pipelined Architecture for the Multidimensional DFT” IEEE Transactions on Signal Processing, vol. 49, No. 9, Sep. 2001, p. 2096-2102.
Mai Tan V.
Nash Kenneth L.
LandOfFree
Digital systolic array architecture and method for computing... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Digital systolic array architecture and method for computing..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Digital systolic array architecture and method for computing... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3647495