NDLI: An efficient FFT algorithm for real-symmetric data

Content Provider	IEEE Xplore Digital Library
Author	Chen, J. Sorensen, H.
Copyright Year	1992
Description	Author affiliation: Dept. of Electr. Eng., Pennsylvania Univ., Philadelphia, PA, USA (Chen, J.; Sorensen, H.)
Abstract	A very efficient algorithm for computing the discrete Fourier transform (DFT) of real-symmetric input is presented. The algorithm is based on Bruun's algorithm where, except for the last stage, all twiddle factors are purely real. It is well-known that about half of the arithmetic operations and memory requirements can be removed when the input is real-valued. It may be assumed that another half of the computational and memory requirements can be eliminated when the input is real and symmetric. This is, however, impossible with a standard radix-2 fast Fourier transform (FFT), but can be achieved by the Bruun algorithm. The symmetries within the algorithm with for real-symmetric input are exploited to remove about three fourths of the butterflies and memory locations. The algorithm presented achieves the same low arithmetic as the split-radix FFT for real-symmetric data, but has a structure that is as simple as the radix-2. The implementation on the TMS320C30 shows that the new algorithm fits a DSP processor very well. The program requires 0.51-0.60 ms to compute a length 1024 FFT with real-symmetric data.<>
Starting Page	17
Ending Page	20
File Size	358963
Page Count	4
File Format	PDF
ISBN	0780305329
ISSN	15206149
DOI	10.1109/ICASSP.1992.226669
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	1992-03-23
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Digital signal processing Discrete Fourier transforms Zinc Filters Fast Fourier transforms Digital arithmetic Indexing Computational complexity
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in