# Relations between DCT_II and DST_I

## 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.