1. Home
  2. An introduction to source-coding
  3. Transform coding
  4. The optimal orthogonal transform

3.3 The optimal orthogonal transform

<< Chapter < Page
  An introduction to source-coding   Page 1 / 1
Chapter >> Page >
In this module, we establish that for transform coding, the optimum orthogonal tranform is the Karhunen-Loeve Transform (KLT). Related properties are also discussed.
  • Ignoring the effect of transform choice on uniform-quantizer efficiency γ y , Gain Over PCM suggests that TC reconstruction error can be minimized by choosing the orthogonal transform T that minimizes the product of coefficient variances. (Recall that orthogonal transforms preserve the arithmetic averageof coefficient variances.)

    Eigen-analysis of autocorrelation matrices

    Say that R is the N × N autocorrelation matrix of a real-valued, wide-sense stationary, discrete time stochastic process.The following properties are often useful:
    1. R is symmetric and Toeplitz. (A symmetric matrix obeys R = R t , while a Toeplitz matrix has equal elements on all diagonals.)
    2. R is positive semidefinite or PSD. (PSD means that x t Rx ≥ 0 for any real-valued x .)
    3. R has an eigen-decomposition
      R = V Λ V t ,
      where V is an orthogonal matrix ( V t V = I ) whose columns are eigenvectors { v i } of R :
      V = ( v 0 v 1 ⋯ v N - 1 ) ,
      and Λ is a diagonal matrix whose elements are the eigenvalues { λ i } of R :
      Λ = diag ( λ 0 λ 1 ⋯ λ N - 1 ) .
    4. The eigenvectors { λ i } of R are real-valued and non-negative.
    5. The product of the eigenvectors equals the determinant ( ∏ k = 0 N - 1 λ k = | R | ) and the sum of the eigenvalues equals the trace( ∑ k = 0 N - 1 λ k = ∑ k [ R ] k , k ).
  • The KLT: Using the outer product,
    y ( m ) y t ( m ) = y 0 2 ( m ) y 0 ( m ) y 1 ( m ) ⋯ y 0 ( m ) y N - 1 ( m ) y 1 ( m ) y 0 ( m ) y 1 2 ( m ) ⋯ y 1 ( m ) y N - 1 ( m ) ⋮ ⋮ ⋱ ⋮ y N - 1 ( m ) y 0 ( m ) y N - 1 ( m ) y 1 ( m ) ⋯ y N - 1 2 ( m )
    Using A k , k to denote the k t h diagonal element of a matrix A , matrix theory implies
    ∏ k = 0 N - 1 σ y k 2 = ∏ k = 0 N - 1 E { y ( m ) y t ( m ) } k , k ≥ E { y ( m ) y t ( m ) } = T E { x ( m ) x t ( m ) } T t = T t · T ︸ I E { x ( m ) x t ( m ) } ︸ R x T t · T ︸ I since | T t A | = | A | = | AT | for orthogonal T = ∏ k = 0 N - 1 λ k R x ,
    thus minimization of ∏ k σ y k 2 would occur if equality could be established above.Say that the eigen-decomposition of the autocorrelation matrix of x ( n ) , which we now denote by R x , is
    R x = V x Λ x V x t
    for orthogonal eigenvector matrix V x and diagonal eigenvalue matrix Λ x . Then choosing T = V x t , otherwise known as the Karhunen-Loeve transform (KLT), results in the desired property:
    E { y ( m ) y t ( m ) } = E { V x t x ( m ) x t ( m ) V x } = V x t R x V x = V x t V x Λ x V x t V x = Λ x .
    To summarize:
    1. the orthogonal transformation matrix T minimizing reconstruction error variance has rows equal to the eigenvectorsof the input's N × N autocorrelation matrix,
    2. the variances of the optimal-transform outputs { σ y k 2 } are equal to the eigenvalues of the input autocorrelation matrix, and
    3. the optimal-transform outputs { y 0 ( m ) , ⋯ , y N - 1 ( m ) } are uncorrelated. (Why? Note the zero-valued off-diagonal elements of R y = E { y ( m ) y t ( m ) } .)
  • Note that the presence of mutually uncorrelated transform coefficients supports our approach of quantizing each transform output independentlyof the others.

2 × 2 Klt coder

Recall Example 1 from "Background and Motivation" with Gaussian input having R x = 1 ρ ρ 1 . The eigenvalues of R x can be determined from the characteristic equation R x - λ I = 0 :

1 - λ ρ ρ 1 - λ = ( 1 - λ ) 2 - ρ 2 = 0 ⇔ 1 - λ = ± ρ ⇔ λ = 1 ± ρ .

The eigenvector v 0 corresponding to eigenvalue λ 0 = 1 + ρ solves R x v 0 = λ 0 v 0 . Using the notation v 0 = v 00 v 01 and v 1 = v 10 v 11 ,

v 00 + ρ v 01 = ( 1 + ρ ) v 00 ρ v 00 + v 01 = ( 1 + ρ ) v 01 ⇔ v 01 = v 00 .

Similarly, R x v 1 = λ 1 v 1 yields

v 10 + ρ v 11 = ( 1 - ρ ) v 10 ρ v 10 + v 11 = ( 1 - ρ ) v 11 ⇔ v 11 = - v 10 .

For orthonormality,

v 00 2 + v 01 2 = 1 ⇒ v 0 = 1 2 1 1
v 10 2 + v 11 2 = 1 ⇒ v 1 = 1 2 1 - 1 .

Thus the KLT is given by T = V x t = ( v 0 v 1 ) t = 1 2 1 1 1 - 1 .
Using the KLT and optimal bit allocation, the error reduction relative to PCM is

σ r 2 | TC σ r 2 | P C M = γ y γ x · ( 1 + ρ ) ( 1 - ρ ) 1 2 ( 1 + ρ ) + ( 1 - ρ ) = 1 - ρ 2

since γ y = γ x for Gaussian x ( n ) . This value equals 0.6 when ρ = 0 . 8 , and 0.98 when ρ = 0 . 2 (compare to Figure 2 from "Background and Motivation" ).
<< Chapter < Page Page > Chapter >>

Read also:

Get Jobilize Job Search Mobile App in your pocket Now!

Get it on Google Play Download on the App Store Now




Source:  OpenStax, An introduction to source-coding: quantization, dpcm, transform coding, and sub-band coding. OpenStax CNX. Sep 25, 2009 Download for free at http://cnx.org/content/col11121/1.2
Google Play and the Google Play logo are trademarks of Google Inc.

Notification Switch

Would you like to follow the 'An introduction to source-coding: quantization, dpcm, transform coding, and sub-band coding' conversation and receive update notifications?

Ask