# Connexions

You are here: Home » Content » An Introduction to Source-Coding: Quantization, DPCM, Transform Coding, and Sub-band Coding » Quantizer Design for Entropy Coded Sytems

### 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?

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

#### 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.
• NSF Partnership

This collection is included inLens: NSF Partnership in Signal Processing
By: Sidney Burrus

Click the "NSF Partnership" link to see all content affiliated with them.

Click the tag icon to display tags associated with this content.

• Featured Content

This collection is included inLens: Connexions Featured Content
By: Connexions

Click the "Featured Content" link to see all content affiliated with them.

Click the tag icon to display tags associated with this content.

#### 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.

Inside Collection (Course):

Course by: Phil Schniter. E-mail the author

# Quantizer Design for Entropy Coded Sytems

Module by: Phil Schniter. E-mail the author

Summary: Motivated by the cascade of memoryless quantization and entropy coding, the entropy-minimizing scalar memoryless quantizer is derived. Using a compander formulation and tools from the calculus of variations, it is shown that the entropy-minimizing quantizer is the simple uniform quantizer. The penalty associated with memoryless quantization is then analyzed in the asymptotic case of many quantization levels.

• Say that we are designing a system with a memoryless quantizer followed by an entropy coder, and our goal is to minimize the average transmission rate for a given σq2 (or vice versa). Is it optimal to cascade a σq2-minimizing (Lloyd-Max) quantizer with a rate-minimizing code? In other words, what is the optimal memoryless quantizer if the quantized outputs are to be entropy coded?
• A Compander Formulation: To determine the optimal quantizer,
1. consider a companding system: a memoryless nonlinearity c(x)c(x) followed by uniform quantizer,
2. find c(x)c(x) minimizing entropy Hy for a fixed error variance σq2.
• First we must express σq2 and Hy in terms of c(x)c(x). Figure 1 suggests that, for large L, the slope c'(x):=dc(x)/dxc'(x):=dc(x)/dx obeys
c'(x) | x X k =2xmax/LΔk,c'(x) | x X k =2xmax/LΔk,
(1)
so that we may write
Δk=2xmaxLc'(x) | x X k .Δk=2xmaxLc'(x) | x X k .
(2)
Assuming large L, the σq2-approximation equation 9 from MSE-Optimal Memoryless Scalar Quantization (lower equation) can be transformed as follows.
σq2=112k=1LPkΔk2=xmax23L2k=1LPkc'(x)2 | x X k =xmax23L2k=1Lpx(x)c'(x)2Δk | x X k since P k = p x ( x ) | x X k ΔkforlargeL=xmax23L2-xmaxxmaxpx(x)c'(x)2dx.σq2=112k=1LPkΔk2=xmax23L2k=1LPkc'(x)2 | x X k =xmax23L2k=1Lpx(x)c'(x)2Δk | x X k since P k = p x ( x ) | x X k ΔkforlargeL=xmax23L2-xmaxxmaxpx(x)c'(x)2dx.
(3)
Similarly,
Hy=-k=1LPklog2Pk=-k=1Lpx(x)Δklog2px(x)Δk | x X k =-k=1Lpx(x)Δklog2px(x) | x X k -k=1Lpx(x)Δklog2Δk | x X k =--xmaxxmaxpx(x)log2px(x)dxhx:differentialentropy''--xmaxxmaxpx(x)log22xmaxLc'(x)Δkdx=hx-log22xmaxL-xmaxxmaxpx(x)dx=1+-xmaxxmaxpx(x)log2c'(x)dx=constant+-xmaxxmaxpx(x)log2c'(x)dxHy=-k=1LPklog2Pk=-k=1Lpx(x)Δklog2px(x)Δk | x X k =-k=1Lpx(x)Δklog2px(x) | x X k -k=1Lpx(x)Δklog2Δk | x X k =--xmaxxmaxpx(x)log2px(x)dxhx:differentialentropy''--xmaxxmaxpx(x)log22xmaxLc'(x)Δkdx=hx-log22xmaxL-xmaxxmaxpx(x)dx=1+-xmaxxmaxpx(x)log2c'(x)dx=constant+-xmaxxmaxpx(x)log2c'(x)dx
(4)
• Entropy-Minimizing Quantizer: Our goal is to choose c(x)c(x) which minimizes the entropy rate Hy subject to fixed error variance σq2. We employ a Lagrange technique again, minimizing the cost -xmaxxmaxpx(x)log2c'(x)dx-xmaxxmaxpx(x)log2c'(x)dx under the constraint that the quantity -xmaxxmaxpx(x)c'(x)-2dx-xmaxxmaxpx(x)c'(x)-2dx equals a constant C. This yields the unconstrained cost function
Juc'(x),λ=-xmaxxmaxpx(x)log2c'(x)+λpx(x)c'(x)-2-Cφ(c'(x),λ)dx,Juc'(x),λ=-xmaxxmaxpx(x)log2c'(x)+λpx(x)c'(x)-2-Cφ(c'(x),λ)dx,
(5)
with scalar λ, and the unconstrained optimization problem becomes
minc'(x),λJu(c'(x),λ).minc'(x),λJu(c'(x),λ).
(6)
The following technique is common in variational calculus (see, e.g., Optimal Systems Control by Sage & White). Say a(x)a(x) minimizes a (scalar) cost Ja(x)Ja(x). Then for any (well-behaved) variation η(x)η(x) from this optimal a(x)a(x), we must have
ϵJa(x)+ϵη(x) | ϵ = 0 =0ϵJa(x)+ϵη(x) | ϵ = 0 =0
(7)
where ϵ is a scalar. Applying this principle to our optimization problem, we search for c'(x)c'(x) such that
η(x),ϵJuc'(x)+ϵη(x),λ | ϵ = 0 =0.η(x),ϵJuc'(x)+ϵη(x),λ | ϵ = 0 =0.
(8)
From Equation 5 we find (using log2a=log2e·logealog2a=log2e·logea)
Juϵ | ϵ = 0 =-xmaxxmaxϵφc'(x)+ϵη(x),λ | ϵ = 0 dx=-xmaxxmaxϵpx(x)log2(e)logec'(x)+ϵη(x)+λpx(x)c'(x)+ϵη(x)-2-C | ϵ = 0 dx=-xmaxxmaxlog2(e)px(x)c'(x)+ϵη(x)-1η(x)-2λpx(x)c'(x)+ϵη(x)-3η(x) | ϵ = 0 dx=-xmaxxmaxpx(x)c'(x)-1log2(e)-2λc'(x)-2η(x)dxJuϵ | ϵ = 0 =-xmaxxmaxϵφc'(x)+ϵη(x),λ | ϵ = 0 dx=-xmaxxmaxϵpx(x)log2(e)logec'(x)+ϵη(x)+λpx(x)c'(x)+ϵη(x)-2-C | ϵ = 0 dx=-xmaxxmaxlog2(e)px(x)c'(x)+ϵη(x)-1η(x)-2λpx(x)c'(x)+ϵη(x)-3η(x) | ϵ = 0 dx=-xmaxxmaxpx(x)c'(x)-1log2(e)-2λc'(x)-2η(x)dx
(9)
and to allow for any η(x)η(x) we require
log2(e)-2λc'(x)-2=0c'(x)=2λlog2eaconstant!.log2(e)-2λc'(x)-2=0c'(x)=2λlog2eaconstant!.
(10)
Applying the boundary conditions,
c(xmax)=xmaxc(-xmax)=-xmaxc(x)=x.c(xmax)=xmaxc(-xmax)=-xmaxc(x)=x.
(11)
Thus, for large-L, the quantizer that minimizes entropy rate Hy for a given quantization error variance σq2 is the uniform quantizer. Plugging c(x)=xc(x)=x into Equation 4, the rightmost integral disappears and we have
Hy | uniform =hx-log22xmaxLΔ,Hy | uniform =hx-log22xmaxLΔ,
(12)
and using the large-L uniform quantizer error variance approximation equation 6 from Memoryless Scalar Quantization,
Hy | uniform =hx-12log212σq2.Hy | uniform =hx-12log212σq2.
(13)
It is interesting to compare this result to the information-theoretic minimal average rate for transmission of a continuous-amplitude memoryless source x of differential entropy hx at average distortion σq2(see Jayant & Noll or Berger):
Rmin=hx-12log22πeσq2.Rmin=hx-12log22πeσq2.
(14)
Comparing the previous two equations, we find that (for a continous-amplitude memoryless source) uniform quantization prior to entropy coding requires
12log2πe60.255bits/sample12log2πe60.255bits/sample
(15)
more than the theoretically optimum transmission scheme, regardless of the distribution of x. Thus, 0.255 bits/sample (or 1.51.5 dB using the 6.02R6.02R relationship) is the price paid for memoryless quantization.

## Content actions

EPUB (?)

### What is an EPUB file?

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

PDF | EPUB (?)

### What is an EPUB file?

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

#### 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?

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?

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

### Reuse / Edit:

Reuse or edit collection (?)

#### Check out and edit

If you have permission to edit this content, using the "Reuse / Edit" action will allow you to check the content out into your Personal Workspace or a shared Workgroup and then make your edits.

#### Derive a copy

If you don't have permission to edit the content, you can still use "Reuse / Edit" to adapt the content by creating a derived copy of it and then editing and publishing the copy.

| Reuse or edit module (?)

#### Check out and edit

If you have permission to edit this content, using the "Reuse / Edit" action will allow you to check the content out into your Personal Workspace or a shared Workgroup and then make your edits.

#### Derive a copy

If you don't have permission to edit the content, you can still use "Reuse / Edit" to adapt the content by creating a derived copy of it and then editing and publishing the copy.