Relations between DCT_II and DST_I

Contents

Definitions

Result of transform is y=x*T, where y, x are row-vectors T is transform matrix

DST_I matrix definition

N=8;
DST1=sin(pi/N*((0:N-2)+1)'*((0:N-2)+1))
DST1 =
    0.3827    0.7071    0.9239    1.0000    0.9239    0.7071    0.3827
    0.7071    1.0000    0.7071    0.0000   -0.7071   -1.0000   -0.7071
    0.9239    0.7071   -0.3827   -1.0000   -0.3827    0.7071    0.9239
    1.0000    0.0000   -1.0000   -0.0000    1.0000    0.0000   -1.0000
    0.9239   -0.7071   -0.3827    1.0000   -0.3827   -0.7071    0.9239
    0.7071   -1.0000    0.7071    0.0000   -0.7071    1.0000   -0.7071
    0.3827   -0.7071    0.9239   -1.0000    0.9239   -0.7071    0.3827

DCT_II matrix definition

DCT2=cos(pi/N*(0:N-1)'*((0:N-1)+1/2))
DCT2 =
    1.0000    1.0000    1.0000    1.0000    1.0000    1.0000    1.0000    1.0000
    0.9808    0.8315    0.5556    0.1951   -0.1951   -0.5556   -0.8315   -0.9808
    0.9239    0.3827   -0.3827   -0.9239   -0.9239   -0.3827    0.3827    0.9239
    0.8315   -0.1951   -0.9808   -0.5556    0.5556    0.9808    0.1951   -0.8315
    0.7071   -0.7071   -0.7071    0.7071    0.7071   -0.7071   -0.7071    0.7071
    0.5556   -0.9808    0.1951    0.8315   -0.8315   -0.1951    0.9808   -0.5556
    0.3827   -0.9239    0.9239   -0.3827   -0.3827    0.9239   -0.9239    0.3827
    0.1951   -0.5556    0.8315   -0.9808    0.9808   -0.8315    0.5556   -0.1951

Finding relations

From [1] we know that DSTI matrix can be expressed in terms of Tschebyshev polynomials

where

are roots of polynomial

DCTII matrix can be analogously expressed as

where

are roots of polynomial

Because there exist relation

and

we can express DCTI through DSTII

where

B=-diag(ones(1,N))+diag(ones(1,N-1),-1); B(1,:)=1;
D1=diag([1, sin(pi/N*((0:N-2)+1))]);
D2=diag(cos(pi/2/N*(0:N-1)));

Check expression of DCT_II through DST_I

DST1a=eye(N);DST1a(2:end,2:end)=DST1;
D2*inv(D1)*DST1a*B
ans =
    1.0000    1.0000    1.0000    1.0000    1.0000    1.0000    1.0000    1.0000
    0.9808    0.8315    0.5556    0.1951   -0.1951   -0.5556   -0.8315   -0.9808
    0.9239    0.3827   -0.3827   -0.9239   -0.9239   -0.3827    0.3827    0.9239
    0.8315   -0.1951   -0.9808   -0.5556    0.5556    0.9808    0.1951   -0.8315
    0.7071   -0.7071   -0.7071    0.7071    0.7071   -0.7071   -0.7071    0.7071
    0.5556   -0.9808    0.1951    0.8315   -0.8315   -0.1951    0.9808   -0.5556
    0.3827   -0.9239    0.9239   -0.3827   -0.3827    0.9239   -0.9239    0.3827
    0.1951   -0.5556    0.8315   -0.9808    0.9808   -0.8315    0.5556   -0.1951

Check computation of DCTII transform

x=randn(1,N)
y=x*DCT2                           % true result
y1=x*D2*inv(D1)*DST1a*B            % compute DCTII using DSTI transform
x =
   -0.2656   -1.1878   -2.2023    0.9863   -0.5186    0.3274    0.2341    0.0215
y =
   -2.7362   -2.4709   -0.3854    0.7842    1.8413    2.7057    0.5551   -2.4187
y1 =
   -2.7362   -2.4709   -0.3854    0.7842    1.8413    2.7057    0.5551   -2.4187

Check expression of DST_I through DCT_II

inv(D2)*D1*DCT2*inv(B)
ans =
    1.0000         0    0.0000    0.0000    0.0000    0.0000    0.0000    0.0000
    0.0000    0.3827    0.7071    0.9239    1.0000    0.9239    0.7071    0.3827
   -0.0000    0.7071    1.0000    0.7071    0.0000   -0.7071   -1.0000   -0.7071
    0.0000    0.9239    0.7071   -0.3827   -1.0000   -0.3827    0.7071    0.9239
    0.0000    1.0000    0.0000   -1.0000   -0.0000    1.0000    0.0000   -1.0000
    0.0000    0.9239   -0.7071   -0.3827    1.0000   -0.3827   -0.7071    0.9239
   -0.0000    0.7071   -1.0000    0.7071    0.0000   -0.7071    1.0000   -0.7071
   -0.0000    0.3827   -0.7071    0.9239   -1.0000    0.9239   -0.7071    0.3827

Check computation of DSTI transform

x=randn(1,N-1)
y=x*DST1                            % true result
y1=[0 x]*inv(D2)*D1*DCT2*inv(B)     % compute DSTI using DCTII transform
x =
   -1.0039   -0.9471   -0.3744   -1.1859   -1.0559    1.4725    0.0557
y =
   -2.4987   -2.6871    1.2287   -1.7412   -1.8860    2.1522   -0.8699
y1 =
   -0.0000   -2.4987   -2.6871    1.2287   -1.7412   -1.8860    2.1522   -0.8699

Reference

[1] Markus Pueschel, Jose M.F. Moura. The Algebraic Approach to the Discrete Cosine and Sine Transforms and their Fast Algorithms SIAM Journal of Computing 2003, Vol. 32, No. 5, pp. 1280-1316.