Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



A polynomial approach to fast algorithms for discrete Fourier-cosine and Fourier-sine transforms

Authors: G. Steidl and M. Tasche
Journal: Math. Comp. 56 (1991), 281-296
MSC: Primary 65T20; Secondary 94A11
MathSciNet review: 1052103
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: The discrete Fourier-cosine transform $ (\cos {\text{-DFT}})$, the discrete Fourier-sine transform $ (\sin {\text{-DFT}})$ and the discrete cosine transform (DCT) are closely related to the discrete Fourier transform (DFT) of real-valued sequences. This paper describes a general method for constructing fast algorithms for the $ (\cos {\text{-DFT}})$, the $ (\sin {\text{-DFT}})$ and the DCT, which is based on polynomial arithmetic with Chebyshev polynomials and on the Chinese Remainder Theorem.

References [Enhancements On Off] (What's this?)

  • [1] A. V. Aho, J. E. Hopcroft, and J. D. Ullmann, The design and analysis of computer algorithms, Addison-Wesley, Reading, Mass., 1976. MR 0413592 (54:1706)
  • [2] G. Bruun, z-transform DFT filters and FFTs, IEEE Trans. Acoust. Speech Signal Process. 26 (1978), 56-63.
  • [3] P. Duhamel, Implementation of "split-radix" FFT algorithms for complex, real and realsymmetric data, IEEE Trans. Acoust. Speech Signal Process. 34 (1986), 285-295. MR 835552 (87e:94006)
  • [4] D. Garbe, On the level of irreducible polynomials over Galois fields, J. Korean Math. Soc. 22 (1985), 117-124. MR 826437 (87d:11093)
  • [5] I. S. Gradshteĭn and I. M. Ryzhik, Tables of integrals, sums, series and products, Nauka, Moscow, 1971. (Russian)
  • [6] M. T. Heideman and C. S. Burrus, On the number of multiplications necessary to compute a length-$ {2^n}$ DFT, IEEE Trans. Acoust. Speech Signal Process. 34 (1986), 91-95. MR 832319 (87e:94007)
  • [7] H. S. Hou, A fast recursive algorithm for computing the discrete cosine transform, IEEE Trans. Acoust. Speech Signal Process. 35 (1987), 1455-1462.
  • [8] B. G. Lee, A new algorithm to compute the discrete cosine transform, IEEE Trans. Acoust. Speech Signal Process. 32 (1984), 1243-1245.
  • [9] M. J. Narasimha and A. M. Peterson, On computing the discrete cosine transform, IEEE Trans. Comm. 26 (1978), 934-936.
  • [10] H. J. Nussbaumer, Fast Fourier transform and convolution algorithms, Springer, Berlin-Heidelberg-New York, 1981. MR 606376 (83e:65219)
  • [11] S. Paszkowski, Numerical application of Chebyshev polynomials and series, Nauka, Moscow, 1983. (Russian)
  • [12] T. J. Rivlin, The Chebyshev polynomials, Wiley, New York-London-Sydney-Toronto, 1974. MR 0450850 (56:9142)
  • [13] H. V. Sorensen, D. L. Jones, C. S. Burrus, and M. T. Heideman, On computing the discrete Hartley transform, IEEE Trans. Acoust. Speech Signal Process. 33 (1985), 1231-1238. MR 811328 (87e:94008)
  • [14] H. V. Sorensen, D. J. Jones, M. T. Heideman, and C. S. Burrus, Real-valued fast Fourier transform algorithms, IEEE Trans. Acoust. Speech Signal Process. 35 (1987), 849-863.
  • [15] M. Vetterli and H. J. Nussbaumer, Simple FFT and DCT algorithms with reduced number of operations, Signal Process. 6 (1984), 267-278. MR 760430 (85m:65128)
  • [16] S. Winograd, On computing the discrete Fourier transform, Math. Comp. 32 (1978), 175-199. MR 0468306 (57:8142)
  • [17] -, Arithmetic complexity of computations, CBMS Regional Conf. Ser. in Math., vol. 33, SIAM, Philadelphia, 1980. MR 565260 (81k:68039)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 65T20, 94A11

Retrieve articles in all journals with MSC: 65T20, 94A11

Additional Information

Keywords: Discrete Fourier-cosine transform, discrete Fourier-sine transform, discrete cosine transform, polynomial arithmetic, Chebyshev polynomials, computational complexity, discrete Fourier transform
Article copyright: © Copyright 1991 American Mathematical Society

American Mathematical Society