Type-II/III DCT/DST algorithms with reduced number of arithmetic operations

Xuancheng Shao; Steven G. Johnson

doi:10.1016/j.sigpro.2008.01.004

Type-II/III DCT/DST algorithms with reduced number of arithmetic operations

Xuancheng Shao, Steven G. Johnson

Mathematics

Research output: Contribution to journal › Article › peer-review

44 Scopus citations

Abstract

We present algorithms for the discrete cosine transform (DCT) and discrete sine transform (DST), of types II and III, that achieve a lower count of real multiplications and additions than previously published algorithms, without sacrificing numerical accuracy. Asymptotically, the operation count is reduced from 2 N log₂ N + O (N) to frac(17, 9) N log₂ N + O (N) for a power-of-two transform size N. Furthermore, we show that an additional N multiplications may be saved by a certain rescaling of the inputs or outputs, generalizing a well-known technique for N = 8 by Arai et al. These results are derived by considering the DCT to be a special case of a DFT of length 4 N, with certain symmetries, and then pruning redundant operations from a recent improved fast Fourier transform algorithm (based on a recursive rescaling of the conjugate-pair split-radix algorithm). The improved algorithms for the DCT-III, DST-II, and DST-III follow immediately from the improved count for the DCT-II.

Original language	English
Pages (from-to)	1553-1564
Number of pages	12
Journal	Signal Processing
Volume	88
Issue number	6
DOIs	https://doi.org/10.1016/j.sigpro.2008.01.004
State	Published - Jun 2008

Bibliographical note

Funding Information:
This research was supported by DARPA and ARO under contract DAAG29-85-C-0028. The authors would like to thank Barry Cole for antireflection coating the samples, Robert Horning and Mary Hibbs-Brenner for the X-Ray measurements, Cynthia Kelley and Hai Ly for sample preparation and Tom Nohava for MBE growth.

Keywords

Arithmetic complexity
Discrete cosine transform
Fast Fourier transform

ASJC Scopus subject areas

Control and Systems Engineering
Software
Signal Processing
Computer Vision and Pattern Recognition
Electrical and Electronic Engineering

Access to Document

10.1016/j.sigpro.2008.01.004

Cite this

@article{96ca684ea387453fb65bbcf2febcf7fe,

title = "Type-II/III DCT/DST algorithms with reduced number of arithmetic operations",

abstract = "We present algorithms for the discrete cosine transform (DCT) and discrete sine transform (DST), of types II and III, that achieve a lower count of real multiplications and additions than previously published algorithms, without sacrificing numerical accuracy. Asymptotically, the operation count is reduced from 2 N log2 N + O (N) to frac(17, 9) N log2 N + O (N) for a power-of-two transform size N. Furthermore, we show that an additional N multiplications may be saved by a certain rescaling of the inputs or outputs, generalizing a well-known technique for N = 8 by Arai et al. These results are derived by considering the DCT to be a special case of a DFT of length 4 N, with certain symmetries, and then pruning redundant operations from a recent improved fast Fourier transform algorithm (based on a recursive rescaling of the conjugate-pair split-radix algorithm). The improved algorithms for the DCT-III, DST-II, and DST-III follow immediately from the improved count for the DCT-II.",

keywords = "Arithmetic complexity, Discrete cosine transform, Fast Fourier transform",

author = "Xuancheng Shao and Johnson, {Steven G.}",

note = "Funding Information: This research was supported by DARPA and ARO under contract DAAG29-85-C-0028. The authors would like to thank Barry Cole for antireflection coating the samples, Robert Horning and Mary Hibbs-Brenner for the X-Ray measurements, Cynthia Kelley and Hai Ly for sample preparation and Tom Nohava for MBE growth.",

year = "2008",

month = jun,

doi = "10.1016/j.sigpro.2008.01.004",

language = "English",

volume = "88",

pages = "1553--1564",

number = "6",

}

TY - JOUR

T1 - Type-II/III DCT/DST algorithms with reduced number of arithmetic operations

AU - Shao, Xuancheng

AU - Johnson, Steven G.

N1 - Funding Information: This research was supported by DARPA and ARO under contract DAAG29-85-C-0028. The authors would like to thank Barry Cole for antireflection coating the samples, Robert Horning and Mary Hibbs-Brenner for the X-Ray measurements, Cynthia Kelley and Hai Ly for sample preparation and Tom Nohava for MBE growth.

PY - 2008/6

Y1 - 2008/6

N2 - We present algorithms for the discrete cosine transform (DCT) and discrete sine transform (DST), of types II and III, that achieve a lower count of real multiplications and additions than previously published algorithms, without sacrificing numerical accuracy. Asymptotically, the operation count is reduced from 2 N log2 N + O (N) to frac(17, 9) N log2 N + O (N) for a power-of-two transform size N. Furthermore, we show that an additional N multiplications may be saved by a certain rescaling of the inputs or outputs, generalizing a well-known technique for N = 8 by Arai et al. These results are derived by considering the DCT to be a special case of a DFT of length 4 N, with certain symmetries, and then pruning redundant operations from a recent improved fast Fourier transform algorithm (based on a recursive rescaling of the conjugate-pair split-radix algorithm). The improved algorithms for the DCT-III, DST-II, and DST-III follow immediately from the improved count for the DCT-II.

AB - We present algorithms for the discrete cosine transform (DCT) and discrete sine transform (DST), of types II and III, that achieve a lower count of real multiplications and additions than previously published algorithms, without sacrificing numerical accuracy. Asymptotically, the operation count is reduced from 2 N log2 N + O (N) to frac(17, 9) N log2 N + O (N) for a power-of-two transform size N. Furthermore, we show that an additional N multiplications may be saved by a certain rescaling of the inputs or outputs, generalizing a well-known technique for N = 8 by Arai et al. These results are derived by considering the DCT to be a special case of a DFT of length 4 N, with certain symmetries, and then pruning redundant operations from a recent improved fast Fourier transform algorithm (based on a recursive rescaling of the conjugate-pair split-radix algorithm). The improved algorithms for the DCT-III, DST-II, and DST-III follow immediately from the improved count for the DCT-II.

KW - Arithmetic complexity

KW - Discrete cosine transform

KW - Fast Fourier transform

UR - http://www.scopus.com/inward/record.url?scp=39749108683&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=39749108683&partnerID=8YFLogxK

U2 - 10.1016/j.sigpro.2008.01.004

DO - 10.1016/j.sigpro.2008.01.004

M3 - Article

AN - SCOPUS:39749108683

SN - 0165-1684

VL - 88

SP - 1553

EP - 1564

JO - Signal Processing

JF - Signal Processing

IS - 6

ER -

Type-II/III DCT/DST algorithms with reduced number of arithmetic operations

Abstract

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this