Relations between DCT_I and DCT_II

Contents

Definitions

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

DCT_I matrix definition

N=8;
DCT1=cos(pi/N*(0:N)'*(0:N))

DCT1 =
  Columns 1 through 8
    1.0000    1.0000    1.0000    1.0000    1.0000    1.0000    1.0000    1.0000
    1.0000    0.9239    0.7071    0.3827    0.0000   -0.3827   -0.7071   -0.9239
    1.0000    0.7071    0.0000   -0.7071   -1.0000   -0.7071   -0.0000    0.7071
    1.0000    0.3827   -0.7071   -0.9239   -0.0000    0.9239    0.7071   -0.3827
    1.0000    0.0000   -1.0000   -0.0000    1.0000    0.0000   -1.0000   -0.0000
    1.0000   -0.3827   -0.7071    0.9239    0.0000   -0.9239    0.7071    0.3827
    1.0000   -0.7071   -0.0000    0.7071   -1.0000    0.7071    0.0000   -0.7071
    1.0000   -0.9239    0.7071   -0.3827   -0.0000    0.3827   -0.7071    0.9239
    1.0000   -1.0000    1.0000   -1.0000    1.0000   -1.0000    1.0000   -1.0000
  Column 9
    1.0000
   -1.0000
    1.0000
   -1.0000
    1.0000
   -1.0000
    1.0000
   -1.0000
    1.0000

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 DCTI 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+1))+diag(ones(1,N),1); B(end,:)=2*(-1).^(0:N); B(1,1)=2; B(end-1,end)=2; B=B/2;
D=diag([cos(pi/2/N*((0:N-1))), 1]);

Check expression of DCT_I through DCT_II

DCT2a=eye(N+1);DCT2a(1:end-1,1:end-1)=DCT2;
inv(D)*DCT2a*B

ans =
  Columns 1 through 8
    1.0000    1.0000    1.0000    1.0000    1.0000    1.0000    1.0000    1.0000
    1.0000    0.9239    0.7071    0.3827    0.0000   -0.3827   -0.7071   -0.9239
    1.0000    0.7071    0.0000   -0.7071   -1.0000   -0.7071   -0.0000    0.7071
    1.0000    0.3827   -0.7071   -0.9239   -0.0000    0.9239    0.7071   -0.3827
    1.0000    0.0000   -1.0000   -0.0000    1.0000    0.0000   -1.0000   -0.0000
    1.0000   -0.3827   -0.7071    0.9239    0.0000   -0.9239    0.7071    0.3827
    1.0000   -0.7071   -0.0000    0.7071   -1.0000    0.7071    0.0000   -0.7071
    1.0000   -0.9239    0.7071   -0.3827   -0.0000    0.3827   -0.7071    0.9239
    1.0000   -1.0000    1.0000   -1.0000    1.0000   -1.0000    1.0000   -1.0000
  Column 9
    1.0000
   -1.0000
    1.0000
   -1.0000
    1.0000
   -1.0000
    1.0000
   -1.0000
    1.0000

Check computation of DCTI transform

x=randn(1,N+1)
y=x*DCT1                      % true result
y1=x*inv(D)*DCT2a*B           % compute DCTI using DCTII transform

x =
  Columns 1 through 8
   -0.2135   -0.1989    0.3075   -0.5723   -0.9776   -0.4468    1.0821    2.3726
  Column 9
    0.2293
y =
  Columns 1 through 8
    1.5823   -3.4144    3.2511   -0.7632   -2.3515    0.9730   -1.2643    1.4333
  Column 9
   -0.7269
y1 =
  Columns 1 through 8
    1.5823   -3.4144    3.2511   -0.7632   -2.3515    0.9730   -1.2643    1.4333
  Column 9
   -0.7269

Check expression of DCT_II through DCT_I

D*DCT1*inv(B)

ans =
  Columns 1 through 8
    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
         0         0   -0.0000    0.0000         0         0         0         0
  Column 9
         0
    0.0000
    0.0000
    0.0000
    0.0000
   -0.0000
    0.0000
   -0.0000
    1.0000

Check computation of DCTII transform

x=randn(1,N)
y=x*DCT2                      % true result
y1=[x 0]*D*DCT1*inv(B)        % compute DCTII using DCTI transform

x =
   -0.2666    0.7017   -0.4876    1.8625    1.1069   -1.2276   -0.6699    1.3409
y =
    1.6256    0.0621   -2.0430   -2.0108    4.4566   -0.9202   -1.2960   -2.0072
y1 =
  Columns 1 through 8
    1.6256    0.0621   -2.0430   -2.0108    4.4566   -0.9202   -1.2960   -2.0072
  Column 9
    0.0000

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.


Published with MATLAB® 7.3