Skip to content Skip to navigation Skip to collection information

Connexions

You are here: Home » Content » An Introduction to Source-Coding: Quantization, DPCM, Transform Coding, and Sub-band Coding » The Optimal Orthogonal Transform

Navigation

Lenses

What is a lens?

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

This content is ...

Affiliated with (What does "Affiliated with" mean?)

This content is either by members of the organizations listed or about topics related to the organizations listed. Click each link to see a list of all content affiliated with the organization.

Also in these lenses

  • UniqU content

    This collection is included inLens: UniqU's lens
    By: UniqU, LLC

    Click the "UniqU content" link to see all content selected in this lens.

  • Lens for Engineering

    This module and collection are included inLens: Lens for Engineering
    By: Sidney Burrus

    Click the "Lens for Engineering" link to see all content selected in this lens.

Recently Viewed

This feature requires Javascript to be enabled.

Tags

(What is a tag?)

These tags come from the endorsement, affiliation, and other lenses that include this content.
 

The Optimal Orthogonal Transform

Module by: Phil Schniter. E-mail the author

Summary: 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 average of coefficient variances.)

    Aside: Eigen-Analysis of Autocorrelation Matrices:

    Say that R is the N×NN×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=RtR=Rt, while a Toeplitz matrix has equal elements on all diagonals.)
    2. R is positive semidefinite or PSD. (PSD means that xtRx≥0xtRx≥0 for any real-valued x.)
    3. R has an eigen-decomposition
      R=VΛVt,R=VΛVt,
      (1)
      where V is an orthogonal matrix (VtV=IVtV=I) whose columns are eigenvectors {vi}{vi} of R:
      V=(v0v1⋯vN-1),V=(v0v1⋯vN-1),
      (2)
      and Λ is a diagonal matrix whose elements are the eigenvalues {λi}{λi} of R:
      Λ=diag(λ0λ1⋯λN-1).Λ=diag(λ0λ1⋯λN-1).
      (3)
    4. The eigenvectors {λi}{λi} of R are real-valued and non-negative.
    5. The product of the eigenvectors equals the determinant (∏k=0N-1λk=|R|∏k=0N-1λk=|R|) and the sum of the eigenvalues equals the trace (∑k=0N-1λk=∑k[R]k,k∑k=0N-1λk=∑k[R]k,k).
  • The KLT: Using the outer product,
    y(m)yt(m)=y02(m)y0(m)y1(m)⋯y0(m)yN-1(m)y1(m)y0(m)y12(m)⋯y1(m)yN-1(m)⋮⋮⋱⋮yN-1(m)y0(m)yN-1(m)y1(m)⋯yN-12(m)y(m)yt(m)=y02(m)y0(m)y1(m)⋯y0(m)yN-1(m)y1(m)y0(m)y12(m)⋯y1(m)yN-1(m)⋮⋮⋱⋮yN-1(m)y0(m)yN-1(m)y1(m)⋯yN-12(m)
    (4)
    Using Ak,kAk,k to denote the kthkth diagonal element of a matrix A, matrix theory implies
    ∏k=0N-1σyk2=∏k=0N-1E{y(m)yt(m)}k,k≥E{y(m)yt(m)}=TE{x(m)xt(m)}Tt=Tt·T︸IE{x(m)xt(m)}︸RxTt·T︸Isince|TtA|=|A|=|AT|fororthogonalT=∏k=0N-1λkRx,∏k=0N-1σyk2=∏k=0N-1E{y(m)yt(m)}k,k≥E{y(m)yt(m)}=TE{x(m)xt(m)}Tt=Tt·T︸IE{x(m)xt(m)}︸RxTt·T︸Isince|TtA|=|A|=|AT|fororthogonalT=∏k=0N-1λkRx,
    (5)
    thus minimization of ∏kσyk2∏kσyk2 would occur if equality could be established above. Say that the eigen-decomposition of the autocorrelation matrix of x(n)x(n), which we now denote by Rx, is
    Rx=VxΛxVxtRx=VxΛxVxt
    (6)
    for orthogonal eigenvector matrix Vx and diagonal eigenvalue matrix Λx. Then choosing T=VxtT=Vxt, otherwise known as the Karhunen-Loeve transform (KLT), results in the desired property:
    E{y(m)yt(m)}=E{Vxtx(m)xt(m)Vx}=VxtRxVx=VxtVxΛxVxtVx=Λx.E{y(m)yt(m)}=E{Vxtx(m)xt(m)Vx}=VxtRxVx=VxtVxΛxVxtVx=Λx.
    (7)
    To summarize:
    1. the orthogonal transformation matrix T minimizing reconstruction error variance has rows equal to the eigenvectors of the input's N×NN×N autocorrelation matrix,
    2. the variances of the optimal-transform outputs {σyk2}{σyk2} are equal to the eigenvalues of the input autocorrelation matrix, and
    3. the optimal-transform outputs {y0(m),⋯,yN-1(m)}{y0(m),⋯,yN-1(m)} are uncorrelated. (Why? Note the zero-valued off-diagonal elements of Ry=E{y(m)yt(m)}Ry=E{y(m)yt(m)}.)
  • Note that the presence of mutually uncorrelated transform coefficients supports our approach of quantizing each transform output independently of the others.

Example 1: 2×22×2 KLT Coder

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

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

The eigenvector v0 corresponding to eigenvalue λ0=1+ρλ0=1+ρ solves Rxv0=λ0v0Rxv0=λ0v0. Using the notation v0=v00v01v0=v00v01 and v1=v10v11v1=v10v11,

v00+ρv01=(1+ρ)v00ρv00+v01=(1+ρ)v01⇔v01=v00.v00+ρv01=(1+ρ)v00ρv00+v01=(1+ρ)v01⇔v01=v00.
(9)

Similarly, Rxv1=λ1v1Rxv1=λ1v1 yields

v10+ρv11=(1-ρ)v10ρv10+v11=(1-ρ)v11⇔v11=-v10.v10+ρv11=(1-ρ)v10ρv10+v11=(1-ρ)v11⇔v11=-v10.
(10)

For orthonormality,

v002+v012=1⇒v0=1211v002+v012=1⇒v0=1211
(11)
v102+v112=1⇒v1=121-1.v102+v112=1⇒v1=121-1.
(12)

Thus the KLT is given by T=Vxt=(v0v1)t=12111-1T=Vxt=(v0v1)t=12111-1.
Using the KLT and optimal bit allocation, the error reduction relative to PCM is

σr2|TCσr2|PCM=γyγx·(1+ρ)(1-ρ)12(1+ρ)+(1-ρ)=1-ρ2σr2|TCσr2|PCM=γyγx·(1+ρ)(1-ρ)12(1+ρ)+(1-ρ)=1-ρ2
(13)

since γy=γxγy=γx for Gaussian x(n)x(n). This value equals 0.6 when ρ=0.8ρ=0.8, and 0.98 when ρ=0.2ρ=0.2 (compare to Figure 2 from "Background and Motivation").

Collection Navigation

Content actions

Download:

Collection as:

EPUB (?)

What is an EPUB file?

EPUB is an electronic book format that can be read on a variety of mobile devices.

Downloading to a reading device

For detailed instructions on how to download this content's EPUB to your specific device, click the "(?)" link.

| More downloads ...

Module as:

PDF | EPUB (?)

What is an EPUB file?

EPUB is an electronic book format that can be read on a variety of mobile devices.

Downloading to a reading device

For detailed instructions on how to download this content's EPUB to your specific device, click the "(?)" link.

| More downloads ...

Add:

Collection to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks

Module to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks