1.4 Quantizer design for entropy coded sytems

An introduction to source-coding Page 1 / 1

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 theaverage transmission rate for a given σ _q ² (or vice versa). Is it optimal to cascade a σ _q ² -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)$ followed by uniform quantizer,
2. find $c (x)$ minimizing entropy H _y for a fixed error variance σ _q ² .
Compander curve: nonuniform input regions mapped to uniform output regions (for subsequent uniform quantization)
First we must express σ _q ² and H _y in terms of $c (x)$ . [link] suggests that, for large L , the slope $c^{'} (x) : = d c (x) / d x$ obeys
$c^{'} (x) |_{x \in X_{k}} = \frac{2 x_{max} / L}{Δ_{k}},$
so that we may write
$Δ_{k} = \frac{2 x_{max}}{L c^{'} (x)} |_{x \in X_{k}} .$
Assuming large L , the σ _q ² -approximation equation 9 from MSE-Optimal Memoryless Scalar Quantization (lower equation) can be transformed as follows.
$\begin{matrix} σ_{q}^{2} & = & \frac{1}{12} \sum_{k = 1}^{L} P_{k} Δ_{k}^{2} \\ = & \frac{x_{max}^{2}}{3 L^{2}} \sum_{k = 1}^{L} \frac{P_{k}}{c^{'} {(x)}^{2}} |_{x \in X_{k}} \\ = & \frac{x_{max}^{2}}{3 L^{2}} \sum_{k = 1}^{L} \frac{p_{x} (x)}{c^{'} {(x)}^{2}} Δ_{k} |_{x \in X_{k}} since P_{k} = p_{x} (x) |_{x \in X_{k}} Δ_{k} for large L \\ = & \frac{x_{max}^{2}}{3 L^{2}} \int_{- x_{max}}^{x_{max}} \frac{p_{x} (x)}{c^{'} {(x)}^{2}} d x . \end{matrix}$
Similarly,
$\begin{matrix} H_{y} & = & - \sum_{k = 1}^{L} P_{k} {log}_{2} P_{k} \\ = & - \sum_{k = 1}^{L} p_{x} (x) Δ_{k} {log}_{2} (p_{x}, (x), Δ_{k}) |_{x \in X_{k}} \\ = & - \sum_{k = 1}^{L} p_{x} (x) Δ_{k} {log}_{2} p_{x} (x) |_{x \in X_{k}} - \sum_{k = 1}^{L} p_{x} (x) Δ_{k} {log}_{2} Δ_{k} |_{x \in X_{k}} \\ = & \underset{h_{x} : ``differential entropy''}{\underset{︸}{- \int_{- x_{max}}^{x_{max}} p_{x} (x) {log}_{2} p_{x} (x) d x}} - \int_{- x_{max}}^{x_{max}} p_{x} (x) {log}_{2} \underset{Δ_{k}}{\underset{︸}{\frac{2 x_{max}}{L c^{'} (x)}}} d x \\ = & h_{x} - {log}_{2} \frac{2 x_{max}}{L} \underset{= 1}{\underset{︸}{\int_{- x_{max}}^{x_{max}} p_{x} (x) d x}} + \int_{- x_{max}}^{x_{max}} p_{x} (x) {log}_{2} c^{'} (x) d x \\ = & constant + \int_{- x_{max}}^{x_{max}} p_{x} (x) {log}_{2} c^{'} (x) d x \end{matrix}$
Entropy-Minimizing Quantizer: Our goal is to choose $c (x)$ which minimizes the entropy rate H _y subject to fixed error variance σ _q ² . We employ a Lagrange technique again, minimizingthe cost $\int_{- x_{max}}^{x_{max}} p_{x} (x) {log}_{2} c^{'} (x) d x$ under the constraint that the quantity $\int_{- x_{max}}^{x_{max}} p_{x} (x) {(c^{'}, (x))}^{- 2} d x$ equals a constant C . This yields the unconstrained cost function
$\begin{matrix} J_{u} (c^{'} (x), λ) = \int_{- x_{max}}^{x_{max}} \underset{φ (c^{'} (x), λ)}{\underset{︸}{[p_{x} (x) {log}_{2} c^{'} (x) + λ (p_{x} (x) {(c^{'}, (x))}^{- 2} - C)]}} d x, \end{matrix}$
with scalar λ , and the unconstrained optimization problem becomes
$min_{c^{'} (x), λ} J_{u} (c^{'} (x), λ) .$
The following technique is common in variational calculus (see, e.g., Optimal Systems Control by Sage&White). Say $a^{⋆} (x)$ minimizes a (scalar) cost $J (a (x))$ . Then for any (well-behaved) variation $η (x)$ from this optimal $a^{⋆} (x)$ , we must have
$\frac{\partial}{\partial ϵ} J (a^{⋆} (x) + ϵ η (x)) |_{ϵ = 0} = 0$
where ϵ is a scalar. Applying this principle to our optimization problem, we search for $c^{'} (x)$ such that
$\forall η (x), \frac{\partial}{\partial ϵ} J_{u} (c^{'} (x) + ϵ η (x), λ) |_{ϵ = 0} = 0 .$
From [link] we find (using ${log}_{2} a = {log}_{2} e \cdot {log}_{e} a$ )
$\begin{matrix} \frac{\partial J_{u}}{\partial ϵ} |_{ϵ = 0} & = & \int_{- x_{max}}^{x_{max}} \frac{\partial}{\partial ϵ} φ (c^{'} (x) + ϵ η (x), λ) |_{ϵ = 0} d x \\ = & \int_{- x_{max}}^{x_{max}} \frac{\partial}{\partial ϵ} [p_{x} (x) {log}_{2} (e) {log}_{e} (c^{'} (x) + ϵ η (x)) + λ (p_{x} (x) {(c^{'} (x) + ϵ η (x))}^{- 2} - C)] |_{ϵ = 0} d x \\ = & \int_{- x_{max}}^{x_{max}} [{log}_{2} (e) p_{x} (x) {(c^{'} (x) + ϵ η (x))}^{- 1} η (x) - 2 λ p_{x} (x) {(c^{'} (x) + ϵ η (x))}^{- 3} η (x)] |_{ϵ = 0} d x \\ = & \int_{- x_{max}}^{x_{max}} p_{x} (x) {(c^{'}, (x))}^{- 1} [{log}_{2} (e) - 2 λ {(c^{'}, (x))}^{- 2}] η (x) d x \end{matrix}$
and to allow for any $η (x)$ we require
${log}_{2} (e) - 2 λ {(c^{'}, (x))}^{- 2} = 0 \Leftrightarrow c^{'} (x) = \underset{a constant!}{\underset{︸}{\sqrt{\frac{2 λ}{{log}_{2} e}}}} .$
Applying the boundary conditions,
$\{\begin{matrix} c (x_{max}) = x_{max} \\ c (- x_{max}) = - x_{max} \end{matrix}\} \to \begin{matrix} c (x) = x \end{matrix} .$
Thus, for large- L , the quantizer that minimizes entropy rate H _y for a given quantization error variance σ _q ² is the uniform quantizer. Plugging $c (x) = x$ into [link] , the rightmost integral disappears and we have
$H_{y} |_{uniform} = h_{x} - {log}_{2} \underset{Δ}{\underset{︸}{\frac{2 x_{max}}{L}}},$
and using the large- L uniform quantizer error variance approximation equation 6 from Memoryless Scalar Quantization ,
$H_{y} |_{uniform} = h_{x} - \frac{1}{2} {log}_{2} (12, σ_{q}^{2}) .$
It is interesting to compare this result to the information-theoretic minimal average rate for transmission of a continuous-amplitudememoryless source x of differential entropy h _x at average distortion σ _q ² (see Jayant&Noll or Berger):
$R_{min} = h_{x} - \frac{1}{2} {log}_{2} (2, π, e, σ_{q}^{2}) .$
Comparing the previous two equations, we find that (for a continous-amplitude memoryless source) uniform quantizationprior to entropy coding requires
$\frac{1}{2} {log}_{2} (\frac{π e}{6}) \approx \begin{matrix} 0.255 bits/sample \end{matrix}$
more than the theoretically optimum transmission scheme, regardless of the distribution of x . Thus, 0.255 bits/sample (or $\sim 1.5$ dB using the $6.02 R$ relationship) is the price paid for memoryless quantization .

<< Chapter < Page Page > Chapter >>

Read also:

Get Jobilize Job Search Mobile App in your pocket Now!

100% Free Mobile Applications
Receive real-time job alerts and never miss the right job again

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

	Negotiations Conflict Management BUS403 By Charles Jumper Start Quiz
	15 Sociology 15 Religion MCQ By OpenStax Start Quiz
	10 Sociology 10 Global Inequality MCQ By OpenStax Start Quiz
	Lean Startup Quiz By Yasser Ibrahim Start Quiz
	Understanding basic music theory By OpenStax Read Online Course
	Thermal-Fluid Systems MCQ By Steve Gibbs Start Quiz
	19 AP Key Terms 19 Cardiovascular System Heart By OpenStax Start Key Terms
	Pre-class Online Quiz - Case Control Studies By Mucho Mizinduko Start Quiz
	American Government MCQ By Saylor Foundation Start Quiz
	American Politics MCQ By Nicole Bartels Start Quiz