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.


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