×

Bilinear algorithms for discrete cosine transforms of prime lengths. (English) Zbl 1172.94342

Summary: This paper presents a strategy to design bilinear discrete cosine transform (DCT) algorithms of prime lengths. We show that by using multiplicative groups of integers, one can identify and arrange the computation as a pair of convolutions. When the DCT length \(p\) is such that \((p-1)/2\) is odd, the computation uses two \((p-1)/2\) point cyclic convolutions. When \((p-1)/2=2mq\) with \(m>0\) and \(q\) odd, the computation requires one \((p-1)/2\) point cyclic convolution and a combination of a \(q\) point cyclic convolution and a \(2m\) point Hankel product. Using bilinear algorithms for convolutions and Hankel products, one gets a bilinear DCT algorithm. We also show that the additions required beyond the convolutions can be minimized by a small modification to the convolution algorithms. This minimization exploits the fact that efficient bilinear convolution algorithms are almost always based on Chinese Remainder Theorem.

MSC:

94A11 Application of orthogonal and other special functions
65T50 Numerical methods for discrete and fast Fourier transforms
PDF BibTeX XML Cite
Full Text: DOI Link