Improved Fourier and Hartley transform algorithms: Application to cyclic convolution of real data
- 1 June 1987
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Acoustics, Speech, and Signal Processing
- Vol. 35 (6) , 818-824
- https://doi.org/10.1109/tassp.1987.1165218
Abstract
This paper highlights the possible tradeoffs between arithmetic and structural complexity when computing cyclic convolution of real data in the transform domain. Both Fourier and Hartley-based schemes are first explained in their usual form and then improved, either from the structural point of view or in the number of operations involved. Namely, we first present an algorithm for the in-place computation of the discrete Fourier transform on real data: a decimation-in-time split-radix algorithm, more compact than the previously published one. Second, we present a new fast Hartley transform algorithm with a reduced number of operations. A more regular convolution scheme based on FFT's is also proposed. Finally, we show that Hartley transforms belong to a larger class of algorithms characterized by their "generalized" convolution propertyKeywords
This publication has 15 references indexed in Scilit:
- Implementation of "Split-radix" FFT algorithms for complex, real, and real-symmetric dataIEEE Transactions on Acoustics, Speech, and Signal Processing, 1986
- On computing the split-radix FFTIEEE Transactions on Acoustics, Speech, and Signal Processing, 1986
- Split-radix fast Hartley transformElectronics Letters, 1986
- On computing the discrete Hartley transformIEEE Transactions on Acoustics, Speech, and Signal Processing, 1985
- An extension of the discrete Fourier transformIEEE Transactions on Circuits and Systems, 1985
- Discrete Fourier transform algorithms for real valued sequencesIEEE Transactions on Acoustics, Speech, and Signal Processing, 1984
- Very fast computation of the radix-2 discrete Fourier transformIEEE Transactions on Acoustics, Speech, and Signal Processing, 1982
- Automatic generation of time efficient digital signal processing softwareIEEE Transactions on Acoustics, Speech, and Signal Processing, 1977
- Fast Convolution using fermat number transforms with applications to digital filteringIEEE Transactions on Acoustics, Speech, and Signal Processing, 1974
- A fast Fourier transform algorithm for symmetric real-valued seriesIEEE Transactions on Audio and Electroacoustics, 1972