Relations between DCTVII and DCTVIII

Contents

Definitions

Transform matrix is defined for operating on column-vectors y=T*x, where y, x are column-vectors, T is transform matrix

DCTVII matrix definition

$${\mathbf{DCTVII}}\mathrm{{=}}{\mathrm{\left\{{\cos\left({\frac{\mathrm{\pi}}{{n}{-}\frac{1}{2}}\left({{k}{+}\frac{1}{2}}\right){l}}\right)}\right\}}}_{k\mathrm{,}l}$$

N1=9; N=N1;
k=0:N1-1;  l=0:N1-1;
DCT7=cos(pi/(N-1/2)*(k+1/2)'*l)       % display DCTV matrix

DCT7 =
  Columns 1 through 7
    1.0000    0.9830    0.9325    0.8502    0.7390    0.6026    0.4457
    1.0000    0.8502    0.4457   -0.0923   -0.6026   -0.9325   -0.9830
    1.0000    0.6026   -0.2737   -0.9325   -0.8502   -0.0923    0.7390
    1.0000    0.2737   -0.8502   -0.7390    0.4457    0.9830    0.0923
    1.0000   -0.0923   -0.9830    0.2737    0.9325   -0.4457   -0.8502
    1.0000   -0.4457   -0.6026    0.9830   -0.2737   -0.7390    0.9325
    1.0000   -0.7390    0.0923    0.6026   -0.9830    0.8502   -0.2737
    1.0000   -0.9325    0.7390   -0.4457    0.0923    0.2737   -0.6026
    1.0000   -1.0000    1.0000   -1.0000    1.0000   -1.0000    1.0000
  Columns 8 through 9
    0.2737    0.0923
   -0.7390   -0.2737
    0.9830    0.4457
   -0.9325   -0.6026
    0.6026    0.7390
   -0.0923   -0.8502
   -0.4457    0.9325
    0.8502   -0.9830
   -1.0000    1.0000

DCTVII in terms of Tschebyshev polynomials

The DCTVII matrix can be expressed in terms of Tschebyshev polynomials [1]

$${\mathbf {DCTVII}} = \left[ {T_l \left( {\alpha _k } \right)} \right]_{k,l} $$

where

$${\mathrm{\alpha}}_{k}\mathrm{{=}}\cos\left({\frac{\left({{k}\mathrm{{+}}\frac{1}{2}}\right)\mathit{\pi}}{{N}\mathrm{{-}}\frac{1}{2}}}\right){\mathrm{,}}{k}\mathrm{{=}}{0}\mathrm{\ldots}{N}\mathrm{{-}}{1}$$

are roots of polynomial

$${U}_{DCTVII}\mathrm{{=}}\mathrm{\left({{x}{+}{1}}\right)}{V}_{{n}\mathrm{{-}}{1}}$$

alpha=sort([roots(TschebyshevV(N-1)); -1],'descend');
DCT7t=zeros(N1);
for l=0:N1-1,
    DCT7t(:,l+1)=polyval(TschebyshevT(l),alpha)';
end
Da7=diag(cos(0*pi/(N-1/2)*(k+1/2)));
DCT7t=Da7*DCT7t                    % display DCTV matrix

% compare DCT7 and DCT7t matrices (show that both definitions above are equivalent)
max(max(abs(DCT7-DCT7t)))

DCT7t =
  Columns 1 through 7
    1.0000    0.9830    0.9325    0.8502    0.7390    0.6026    0.4457
    1.0000    0.8502    0.4457   -0.0923   -0.6026   -0.9325   -0.9830
    1.0000    0.6026   -0.2737   -0.9325   -0.8502   -0.0923    0.7390
    1.0000    0.2737   -0.8502   -0.7390    0.4457    0.9830    0.0923
    1.0000   -0.0923   -0.9830    0.2737    0.9325   -0.4457   -0.8502
    1.0000   -0.4457   -0.6026    0.9830   -0.2737   -0.7390    0.9325
    1.0000   -0.7390    0.0923    0.6026   -0.9830    0.8502   -0.2737
    1.0000   -0.9325    0.7390   -0.4457    0.0923    0.2737   -0.6026
    1.0000   -1.0000    1.0000   -1.0000    1.0000   -1.0000    1.0000
  Columns 8 through 9
    0.2737    0.0923
   -0.7390   -0.2737
    0.9830    0.4457
   -0.9325   -0.6026
    0.6026    0.7390
   -0.0923   -0.8502
   -0.4457    0.9325
    0.8502   -0.9830
   -1.0000    1.0000
ans =
   2.5778e-13

DCTVIII matrix definition

$${\mathbf{DCTVIII}}\mathrm{{=}}{\left\{{\cos\left({\frac{\mathit{\pi}}{{n}\mathrm{{+}}\frac{1}{2}}\left({{k}\mathrm{{+}}\frac{1}{2}}\right)\left({{l}\mathrm{{+}}\frac{1}{2}}\right)}\right)}\right\}}_{k\mathrm{,}l}$$

N2=8; N=N2;
k=0:N2-1;  l=0:N2-1;
DCT8=cos(pi/(N+1/2)*(k+1/2)'*(l+1/2))       % display DCTV matrix

DCT8 =
  Columns 1 through 7
    0.9957    0.9618    0.8952    0.7980    0.6737    0.5264    0.3612
    0.9618    0.6737    0.1837   -0.3612   -0.7980   -0.9957   -0.8952
    0.8952    0.1837   -0.6737   -0.9957   -0.5264    0.3612    0.9618
    0.7980   -0.3612   -0.9957   -0.1837    0.8952    0.6737   -0.5264
    0.6737   -0.7980   -0.5264    0.8952    0.3612   -0.9618   -0.1837
    0.5264   -0.9957    0.3612    0.6737   -0.9618    0.1837    0.7980
    0.3612   -0.8952    0.9618   -0.5264   -0.1837    0.7980   -0.9957
    0.1837   -0.5264    0.7980   -0.9618    0.9957   -0.8952    0.6737
  Column 8
    0.1837
   -0.5264
    0.7980
   -0.9618
    0.9957
   -0.8952
    0.6737
   -0.3612

DCTVIII in terms of Tschebyshev polynomials

The DCTVIII matrix can be expressed in terms of Tschebyshev polynomials [1]

$${\mathbf{D}}{\mathbf{C}}{\mathbf{TVII}}{\mathbf{I}}\mathrm{{=}}{\mathbf{D}}_{DCTVIII}\mathrm{\cdot}{\left[{{V}_{l}\left({{\mathit{\beta}}_{k}}\right)}\right]}_{k\mathrm{,}l}$$

where

$${\mathit{\beta}}_{k}\mathrm{{=}}\cos\mathrm{\left({\frac{\left({{k}{+}\frac{1}{2}}\right)\mathrm{\pi}}{{N}{+}\frac{1}{2}}}\right)}{\mathrm{,}}{k}\mathrm{{=}}{0}\mathrm{\ldots}{N}\mathrm{{-}}{1}$$

are roots of polynomial

$${U}_{DSTVII}\mathrm{{=}}{V}_{n}$$

$${\mathbf{D}}_{DCTVIII}\mathrm{{=}}{diag}{\mathrm{\left\{{\cos\left({\left({{k}{+}\frac{1}{2}}\right)\frac{\mathrm{\pi}}{{2}\left({{N}{+}\frac{1}{2}}\right)}}\right)}\right\}}}_{k}$$

beta=sort([roots(TschebyshevV(N))],'descend');
DCT8t=zeros(N);
for l=0:N2-1,
    DCT8t(:,l+1)=polyval(TschebyshevV(l),beta)';
end
Db8=diag(cos(1/2*pi/(N+1/2)*(k+1/2)));
DCT8t=Db8*DCT8t                    % display DCTV matrix

% compare DCT8 and DCT8t matrices (show that both definitions above are equivalent)
max(max(abs(DCT8-DCT8t)))

DCT8t =
  Columns 1 through 7
    0.9957    0.9618    0.8952    0.7980    0.6737    0.5264    0.3612
    0.9618    0.6737    0.1837   -0.3612   -0.7980   -0.9957   -0.8952
    0.8952    0.1837   -0.6737   -0.9957   -0.5264    0.3612    0.9618
    0.7980   -0.3612   -0.9957   -0.1837    0.8952    0.6737   -0.5264
    0.6737   -0.7980   -0.5264    0.8952    0.3612   -0.9618   -0.1837
    0.5264   -0.9957    0.3612    0.6737   -0.9618    0.1837    0.7980
    0.3612   -0.8952    0.9618   -0.5264   -0.1837    0.7980   -0.9957
    0.1837   -0.5264    0.7980   -0.9618    0.9957   -0.8952    0.6737
  Column 8
    0.1837
   -0.5264
    0.7980
   -0.9618
    0.9957
   -0.8952
    0.6737
   -0.3612
ans =
   2.3428e-13

Finding relations

Because there exist relation

$$ T_l = \frac{{V_l + V_{l - 1} }}{2} $$

and

$$\begin{array}{l} {{\mathrm{\alpha}}_{k}\mathrm{{=}}{\mathrm{\beta}}_{k}{\mathrm{,}}{k}\mathrm{{=}}{0}\mathrm{\ldots}{N}\mathrm{{-}}{1}}\\ {{\mathrm{\alpha}}_{N}\mathrm{{=}}\mathrm{{-}}{1}} \end{array}$$

we can express DCTVII through DCTVIII

$$\begin{array}{l} {{\mathbf{DCTVII}}\mathrm{{=}}{\mathrm{\left[{{T}_{l}\left({{\mathrm{\alpha}}_{k}}\right)}\right]}}_{k\mathrm{,}l}\mathrm{{=}}{\mathrm{\left[{\begin{array}{cc}{{V}_{l}\left({{\mathrm{\beta}}_{k}}\right)}&{}\\{}&{1}\end{array}}\right]}}_{k\mathrm{,}l}\mathit{\cdot}{\mathbf{B}}\mathrm{{=}}\left[{\begin{array}{cc}{{\left({{\mathbf{D}}_{DCTVIII}}\right)}^{\mathrm{{-}}{1}}\mathit{\cdot}{\mathbf{D}}_{DCTVIII}\mathit{\cdot}{\left[{{V}_{l}\left({{\mathit{\beta}}_{k}}\right)}\right]}_{k\mathrm{,}l}}&{}\\{}&{1}\end{array}}\right]\mathit{\cdot}{\mathbf{B}}\mathrm{{=}}}\\ {\mathrm{{=}}\left[{\begin{array}{cc}{{\left({{\mathbf{D}}_{DCTVIII}}\right)}^{\mathrm{{-}}{1}}\mathrm{\cdot}{\mathbf{D}}{\mathbf{C}}{\mathbf{TVI}}{\mathbf{I}}{\mathbf{I}}}&{}\\{}&{1}\end{array}}\right]\mathrm{\cdot}{\mathbf{B}}} \end{array}$$

where

$${\mathbf{B}}\mathrm{{=}}\frac{1}{2}\left[{\begin{array}{cccccc}{2}&{1}&{}&{}&{}&{}\\{}&{1}&{1}&{}&{}&{}\\{}&{}&{1}&{\mathrm{\ddots}}&{}&{}\\{}&{}&{}&{\mathrm{\ddots}}&{1}&{}\\{}&{}&{}&{}&{1}&{1}\\{2}&{\mathrm{{-}}{2}}&{2}&{\mathrm{\cdots}}&{\mathrm{{-}}{2}}&{2}\end{array}}\right]$$

B=toeplitz([0.5 zeros(1,N-1)]',[0.5         0.5 zeros(1,N-length([0.5         0.5]))]);
B(1,1)=1;
B=[B [0; B(1:end-1,end)]];
B=[B; (-1).^(0:size(B,2)-1)];

Check expression of DCTVII through DCTVIII

$${\mathbf{DCTVII}}\mathrm{{=}}\mathrm{\left[{\begin{array}{cc}{{\left({{\mathbf{D}}_{DCTVIII}}\right)}^{{-}{1}}\cdot{\mathbf{DCTVIII}}}&{}\\{}&{1}\end{array}}\right]}\mathrm{\cdot}{\mathbf{B}}$$

DCT7a=Da7*blkdiag(inv(Db8)*DCT8,1)*B
% compare DCT7 and DCT7a matrices (show correctness of representation of DCTVII through DCTVIII)
max(max(abs(DCT7-DCT7a)))

DCT7a =
  Columns 1 through 7
    1.0000    0.9830    0.9325    0.8502    0.7390    0.6026    0.4457
    1.0000    0.8502    0.4457   -0.0923   -0.6026   -0.9325   -0.9830
    1.0000    0.6026   -0.2737   -0.9325   -0.8502   -0.0923    0.7390
    1.0000    0.2737   -0.8502   -0.7390    0.4457    0.9830    0.0923
    1.0000   -0.0923   -0.9830    0.2737    0.9325   -0.4457   -0.8502
    1.0000   -0.4457   -0.6026    0.9830   -0.2737   -0.7390    0.9325
    1.0000   -0.7390    0.0923    0.6026   -0.9830    0.8502   -0.2737
    1.0000   -0.9325    0.7390   -0.4457    0.0923    0.2737   -0.6026
    1.0000   -1.0000    1.0000   -1.0000    1.0000   -1.0000    1.0000
  Columns 8 through 9
    0.2737    0.0923
   -0.7390   -0.2737
    0.9830    0.4457
   -0.9325   -0.6026
    0.6026    0.7390
   -0.0923   -0.8502
   -0.4457    0.9325
    0.8502   -0.9830
   -1.0000    1.0000
ans =
   2.1649e-15

Check expression of DCTVIII through DCTVII

$$\mathrm{\left[{\begin{array}{cc}{\mathbf{DCTVIII}}&{}\\{}&{1}\end{array}}\right]}\mathrm{{=}}\mathrm{\left[{\begin{array}{cc}{{\mathbf{D}}_{DCTVIII}}&{}\\{}&{1}\end{array}}\right]}\mathrm{\cdot}{\mathbf{DCTVII}}\mathrm{\cdot}{\mathbf{B}}^{\mathrm{{-}}{1}}$$

DCT8a=blkdiag(Db8,1)*inv(Da7)*DCT7*inv(B);
DCT8a=DCT8a(1:end-1,1:end-1)
% compare DCT8 and DCT8a matrices (show correctness of representation of DCTVIII through DCTVII)
max(max(abs(DCT8-DCT8a)))

DCT8a =
  Columns 1 through 7
    0.9957    0.9618    0.8952    0.7980    0.6737    0.5264    0.3612
    0.9618    0.6737    0.1837   -0.3612   -0.7980   -0.9957   -0.8952
    0.8952    0.1837   -0.6737   -0.9957   -0.5264    0.3612    0.9618
    0.7980   -0.3612   -0.9957   -0.1837    0.8952    0.6737   -0.5264
    0.6737   -0.7980   -0.5264    0.8952    0.3612   -0.9618   -0.1837
    0.5264   -0.9957    0.3612    0.6737   -0.9618    0.1837    0.7980
    0.3612   -0.8952    0.9618   -0.5264   -0.1837    0.7980   -0.9957
    0.1837   -0.5264    0.7980   -0.9618    0.9957   -0.8952    0.6737
  Column 8
    0.1837
   -0.5264
    0.7980
   -0.9618
    0.9957
   -0.8952
    0.6737
   -0.3612
ans =
   1.8874e-15

Check computation of DCTVII transform

x=randn(N1,1);
disp('x''=');disp(x');
y=DCT7*x;                      % true result
disp('y''=');disp(y');
y1=Da7*blkdiag(inv(Db8)*DCT8,1)*B*x;            % compute DCTVII using DCTVIII transform
disp('y1''=');disp(y1');

x'=
  Columns 1 through 7
   -0.7423   -1.0616    2.3505   -0.6156    0.7481   -0.1924    0.8886
  Columns 8 through 9
   -0.7648   -1.4023
y'=
  Columns 1 through 7
    0.3768   -0.7363   -2.7897   -0.7917   -4.5927   -0.2618   -2.2207
  Columns 8 through 9
    2.4680    4.4770
y1'=
  Columns 1 through 7
    0.3768   -0.7363   -2.7897   -0.7917   -4.5927   -0.2618   -2.2207
  Columns 8 through 9
    2.4680    4.4770

Check computation of DCTVIII transform

x=randn(N2,1);
disp('x''=');disp(x');
y=DCT8*x;                      % true result
disp('y''=');disp(y');
y1=blkdiag(Db8,1)*inv(Da7)*DCT7*inv(B)*[x;0];            % compute DCTVIII using DCTVII transform
disp('y1''=');disp(y1');
% Reference

x'=
  Columns 1 through 7
   -1.4224    0.4882   -0.1774   -0.1961    1.4193    0.2916    0.1978
  Column 8
    1.5877
y'=
  Columns 1 through 7
    0.2109   -3.4368   -0.0534   -1.2631    0.3469   -4.0060   -0.1737
  Column 8
    0.2406
y1'=
  Columns 1 through 7
    0.2109   -3.4368   -0.0534   -1.2631    0.3469   -4.0060   -0.1737
  Columns 8 through 9
    0.2406    0.0000


Published with MATLAB® 7.14