Algorithm 749: fast discrete cosine transform

ABSTRACT

An in-place algorithm for the fast, direct computation of the forward and inverse discrete cosine transform is presented and evaluated. The transform length may be an arbitrary power of two.

REFERENCES

• 1: AHMED, N., NATARAJAN, T., AND RAO, K. R. 1974. Discrete cosine transform. IEEE Trans. Comput. C-23, i (Jan.), 90-93.
• 2: CHAN, S.-C. AND HO, K.-L. 1992. Fast algorithms for computing the discrete cosine transform. IEEE Trans. Circuzts Syst. H 39, 3 (Mar.), 185-190.
• 3: CttEN, W.-H., SMITH, C. H., AND FRALICK, S.C. 1977. A fast computational algorithm for the discrete cosine transform. IEEE Trans. Commun. COM-25, 9 (Sept.), 1004 1009.
• 4: CVETKOVIC, Z. AND POPOVIC, M.V. 1992. New fast recursive algorithms for the computation of discrete cosine and sine transforms. IEEE Trans. Signal Process. SP-40, 8 (Aug.), 2083-2086.
• 5: Hou, H. S. 1987. A fast recursive algorithm for computing the discrete cosine transform. IEEE Trans. Acoust. Speech S~gnal Process. ASSP-35, 10 (Oct.), 1455-1461.
• 6: LEE, B.G. 1984. A new algorithm to compute the discrete cosine transform. IEEE Trans. Acoust Speech Signal Process. ASSP-32, 6 (Dec.), 1243-1245.
• 7: LI, W. 1991. A new algorithm to compute the DCT and its inverse. IEEE Trans. Signal Process. 39, 6 (June), 1305-1313.
• 8: MAKHOUL, J. 1980. A fast cosine transform in one and two dimensions. IEEE Trans. Acoust. Speech S,gnal Proces,~. ASSP-28, 1 (Feb.), 27-34.
• 9: MALVAR, H. S. 1986. Fast computation of the discrete cosine transform through the fast Hartley transform. Elec. Lett. 27, (Mar.), 352-353.
• 10: MONRO, D.M. 1979. Interpolation by fast Fourier and Chebyshev transforms. Int. J. Num. Methods Eng. 14, 11, 1679-1692.
• 11: NARASmHA, M. J. AND PETERSON, A. M. 1978. On the computation of the discrete cosine transform. IEEE Trans. Commun. COM-26, 6 (June), 934-936.
• 12: K. R. Rao , P. Yip, Discrete cosine transform: algorithms, advantages, applications, Academic Press Professional, Inc., San Diego, CA, 1990
• 13: SKODRAS, A. N. AND CHmSTOPOULOS, C.A. 1993. Split-radix fast cosine transform algorithm. Int. J. Elec. 74, 4 (Apr.), 513-522.
• 14: WANG, Z. 1984. Fast algorithms for the discrete W transform and for the discrete Fourier transform. IEEE Trans. Acoust. Speech S~gnal Process. ASSP-32, 4 (Aug.), 803-816.
• 15: YIP, P. AND RAO, K.R. 1988. The decimation-in-frequency algorithms for a family of discrete sine and cosine transforms. Circuits Syst. Signal Process. 7, 1, 3-19.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computation of transforms (e.g., fast Fourier transform)

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: FORTRAN

  E. Data
  E.4 CODING AND INFORMATION THEORY
      Subjects: Data compaction and compression

  G. Mathematics of Computing

  I. Computing Methodologies
  I.4 IMAGE PROCESSING AND COMPUTER VISION

General Terms:
Algorithms

Keywords:
data compression, discrete cosine transform, fast transform