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" ).

Questions & Answers

what is biology
Hajah Reply
the study of living organisms and their interactions with one another and their environments
AI-Robot
what is biology
Victoria Reply
HOW CAN MAN ORGAN FUNCTION
Alfred Reply
the diagram of the digestive system
Assiatu Reply
allimentary cannel
Ogenrwot
How does twins formed
William Reply
They formed in two ways first when one sperm and one egg are splited by mitosis or two sperm and two eggs join together
Oluwatobi
what is genetics
Josephine Reply
Genetics is the study of heredity
Misack
how does twins formed?
Misack
What is manual
Hassan Reply
discuss biological phenomenon and provide pieces of evidence to show that it was responsible for the formation of eukaryotic organelles
Joseph Reply
what is biology
Yousuf Reply
the study of living organisms and their interactions with one another and their environment.
Wine
discuss the biological phenomenon and provide pieces of evidence to show that it was responsible for the formation of eukaryotic organelles in an essay form
Joseph Reply
what is the blood cells
Shaker Reply
list any five characteristics of the blood cells
Shaker
lack electricity and its more savely than electronic microscope because its naturally by using of light
Abdullahi Reply
advantage of electronic microscope is easily and clearly while disadvantage is dangerous because its electronic. advantage of light microscope is savely and naturally by sun while disadvantage is not easily,means its not sharp and not clear
Abdullahi
cell theory state that every organisms composed of one or more cell,cell is the basic unit of life
Abdullahi
is like gone fail us
DENG
cells is the basic structure and functions of all living things
Ramadan
What is classification
ISCONT Reply
is organisms that are similar into groups called tara
Yamosa
in what situation (s) would be the use of a scanning electron microscope be ideal and why?
Kenna Reply
A scanning electron microscope (SEM) is ideal for situations requiring high-resolution imaging of surfaces. It is commonly used in materials science, biology, and geology to examine the topography and composition of samples at a nanoscale level. SEM is particularly useful for studying fine details,
Hilary
cell is the building block of life.
Condoleezza Reply
Got questions? Join the online conversation and get instant answers!
Jobilize.com Reply
<< 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