Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2011-01-11
2011-01-11
Do, Chat C (Department: 2193)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
07870177
ABSTRACT:
The embodiments of the present invention provide a scalable method for implementing FFT/IFFT computations in multiprocessor architectures that provides improved throughput by eliminating the need for inter-processor communication after the computation of the first “log2P” stages for an implementation using “P” processing elements, comprising computing each butterfly of the first “log2P” stages on either a single processor or each of the “P” processors simultaneously and distributing the computation of the butterflies in all the subsequent stages among the “P” processors such that each chain of cascaded butterflies consisting of those butterflies that have inputs and outputs connected together, are processed by the same processor. The embodiments of the invention also provide a system for obtaining scalable implementation of FFT/IFFT computations in multiprocessor architectures that provides improved throughput by eliminating the need for inter-processor communication after the computation of the first “log2P” stages for an implementation using “P” processing elements.
REFERENCES:
patent: 4547862 (1985-10-01), McIver et al.
patent: 5093801 (1992-03-01), White et al.
patent: 5293330 (1994-03-01), Sayegh
patent: 5303172 (1994-04-01), Magar et al.
patent: 5313413 (1994-05-01), Bhatia et al.
patent: 5473556 (1995-12-01), Aguilar et al.
patent: 5831883 (1998-11-01), Suter et al.
patent: 5991787 (1999-11-01), Abel et al.
patent: 6061705 (2000-05-01), Hellberg
patent: 6247034 (2001-06-01), Nakai et al.
patent: 6304887 (2001-10-01), Ju et al.
patent: 6366936 (2002-04-01), Lee et al.
patent: 6618800 (2003-09-01), Weiss et al.
patent: 6751643 (2004-06-01), Jaber
patent: 6792441 (2004-09-01), Jaber
patent: 6839727 (2005-01-01), Kechriotis
patent: 6907439 (2005-06-01), Wicker
patent: 6996595 (2006-02-01), LaRocca et al.
patent: 7164723 (2007-01-01), Sunwoo
patent: 7409418 (2008-08-01), Saha et al.
patent: 7489742 (2009-02-01), Saha et al.
patent: 2001/0051967 (2001-12-01), Jaber
patent: 2002/0184279 (2002-12-01), Kechriotis
patent: 2003/0041080 (2003-02-01), Jaber
patent: 2004/0167950 (2004-08-01), Saha et al.
patent: 2005/0138098 (2005-06-01), Saha et al.
patent: 2006/0072674 (2006-04-01), Saha et al.
patent: 2009/0103622 (2009-04-01), Tripathi et al.
patent: 2009/0154558 (2009-06-01), Agarwal et al.
patent: 2009/0209989 (2009-08-01), Blake et al.
patent: 2009/0265739 (2009-10-01), Arora et al.
patent: 1426872 (2004-06-01), None
patent: 1447752 (2004-08-01), None
patent: 1426872 (2006-02-01), None
patent: 1447752 (2006-02-01), None
patent: 1208/DEL/2002 (2002-12-01), None
patent: 0169424 (2001-09-01), None
Toshihiro et al., Radix R Parallel FFT algorithms with a global interconnection networks and its Evaluation, 1997, IEEE, pp. 424-428.
Douglas et al., A Bus-Oriented Multiprocessor Fast Fourier Transform, 1991, IEEE, pp. 2547-2552.
Laxmi et al., Performance Analysis of FFT Algorithms on Multiprocessor Systems, 1983, IEEE, pp. 512-521.
European Search Report, European Application No. EP 04 10 0617, Dated Dec. 23, 2005, 3 Pages.
Piedra (1994) “Paraellel 1-D FFT Implementation With TMS320C4X DSPS”; Texas Instruments, Application Report SPRA108, XP002360704, HTTP://FOCUS.TI.COM/LIT/AN/SPRA108/SPRA108.PDF.
Chu et al. (2000) “Inside the FFT Black Box: Serial and Parallel Fast Fourier Transform Algorithms”; CRC Press; pp. 69-79, 177-182, 209-210, 226-227.
Dawoud (2002) “An Effective Memory Addressing Scheme for Multiprocessor FFT System”; 2002 6th IEEE Africon Conference, Univ. of Pretoria, George., South Africa; 1:29-34.
European Search Report Dated Dec. 23, 2005, for European Patent Publication No. EP1426872 A3 Published Feb. 22, 2006.
Narayan Srijib
Saha Kaushik
Do Chat C
Graybeal Jackson LLP
Jorgenson Lisa K.
Rusyn Paul F.
STMicroelectronics Pvt. Ltd.
LandOfFree
Method and system for multi-processor FFT/IFFT with minimum... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for multi-processor FFT/IFFT with minimum..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for multi-processor FFT/IFFT with minimum... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2724027