• Home
•  
• Call for Papers
• Paper Status
• Registration
• Workshops
• Exhibits
•  
• Technical Program
• Side Meetings
• Tutorials
• Plenaries
• Special Sessions
• Panel Sessions
• My Schedule
•  
• Practicalities
• Housing & Venue
• Special Events
• Visits
• Supporters
•  
• Contact / Discussion
• Organizing Committee
• Program Committee
• Review Committee
•  
• Related Conferences

Technical Program

Paper Detail

Paper:	DISPS-L1.1
Session:	Fast Algorithm Design and Synthesis
Time:	Wednesday, May 17, 16:30 - 16:50
Presentation:	Lecture
Topic:	Design and Implementation of Signal Processing Systems: Fast Algorithms
Title:	Algebraic Derivation of General Radix Cooley-Tukey Algorithms for the Real Discrete Fourier Transform
Authors:	Yevgen Voronenko, Markus Püschel, Carnegie Mellon University, United States
Abstract:	We first show that the real version of the discrete Fourier transform (called RDFT) can be characterized in the framework of polynomial algebras just as the DFT and the discrete cosine and sine transforms. Then, we use this connection to algebraically derive a general radix Cooley-Tukey type algorithm for the RDFT. The algorithm has a similar structure as its complex counterpart, but there are also important differences, which are exhibited by our Kronecker product style presentation. In particular, the RDFT is decomposed into smaller RDFTs but also other auxiliary transforms, which we then decompose by their own Cooley-Tukey type algorithms to obtain a full recursive algorithm for the RDFT.