Shifted Fourier transform-based tensor algorithms for the 2-D DCT

In this paper, tensor algorithms for calculating the two-dimensional (2-D) discrete cosine transform (DCT) are presented. The tensor approach is based on the concept of the covering revealing the transforms, which yields in particular the splitting of the shifted 2 ^r×2^r-point Fourier and cosine transforms into 2^r-13 one-dimensional (1-D) incomplete 2^r-point transforms. The multiplicative complexity of the 2-D 2^r×2^r-point discrete cosine transforms in terms of the tensor representation is 4^r3-2^r-2(r ²+7r+14), which is reduced to 4^r/83-2^r(r²+7r+10)-20/3 when using the improved tensor algorithm. The multiplicative complexity in the general L^r×L^r case, with a prime L>2, as well as in the L₁L₂×L₁L₂ case, with arbitrary co-prime L₁, L₂>1, is provided. The examples of the tensor algorithms for calculating the 8×8-point DCT through 104, 88, and 84 multiplications are given in detail. Based on the proposed concept, the fast algorithm for calculating the 1-D DCT-I is also developed. The multiplicative complexity of the 2^r-point DCT-I is 2^r+1-(r-2)(r+5)/2-8. The comparative estimates with the known algorithms are given