1. Home
  2. An introduction to source-coding
  3. Transform coding
  4. Optimal bit allocation

3.1 Optimal bit allocation

<< Chapter < Page
  An introduction to source-coding   Page 1 / 1
Chapter >> Page >
For transform coding with a fixed total bit rate, the optimal (SNR-maximizing) allocation of bit rates is derived.
  • Motivating Question: Assuming that T is an N × N orthogonal matrix, what is the MSE-optimal bitrate allocation strategy assumingindependent uniform quantization of the transform outputs? In other words, what { R ℓ } minimize average reconstruction error for fixed average rate 1 N ∑ ℓ R ℓ ?
  • Say that the k t h element of the transformed output vector y ( n ) has variance { σ y k 2 } . With uniform quantization, example 1 from Background and Motivation showed that the k t h quantizer error power is
    σ q k 2 = γ y k σ y k 2 2 - 2 R k ,
    where R k is the bit rate allocated to the k t h quantizer output and where γ y k depends on the distribution of y k . From this point on we make the simplifying assumption that γ y k is independent of k . As shown in example 1 from Background and Motivation , orthogonal matrices imply that the mean squared reconstruction error equals the mean squared quantizationerror, so that
    σ r 2 = 1 N ∑ k = 0 N - 1 σ q k 2 = γ y N ∑ k = 0 N - 1 σ y k 2 2 - 2 R k .
    Thus we have the constrained optimization problem
    min { R k } ∑ k = 0 N - 1 σ y k 2 2 - 2 R k s.t. R = 1 N ∑ k = 0 N - 1 R k .
    Using the Lagrange technique, we first set
    ∂ ∂ R ℓ ∑ k σ y k 2 2 - 2 R k - λ 1 N ∑ k R k = 0 ∀ ℓ .
    Since 2 - 2 R k = ( e ln 2 ) - 2 R k = e - 2 R k ln 2 , the zero derivative implies
    0 = - 2 ln 2 · 2 - 2 R ℓ · σ y ℓ 2 - λ N ⇒ R ℓ = - 1 2 log 2 λ - 2 N σ y ℓ 2 ln 2 ∀ ℓ .
    Hence
    R = 1 N ∑ k R k = - 1 2 N ∑ k log 2 λ - 2 N σ y k 2 ln 2 = - 1 2 log 2 λ - 2 N ln 2 + 1 2 N ∑ k log 2 σ y k 2
    so that
    - 1 2 log 2 λ - 2 N ln 2 = R - 1 2 log 2 ∏ k σ y k 2 1 / N .
    Rewriting [link] and plugging in the expression above,
    R ℓ = - 1 2 log 2 λ - 2 N ln 2 + 1 2 log 2 σ y ℓ 2 = R - 1 2 log 2 ∏ k σ y k 2 1 / N + 1 2 log 2 σ y ℓ 2 = R + 1 2 log 2 σ y ℓ 2 ∏ k = 0 N - 1 σ y k 2 1 / N .
  • The optimal bitrate allocation expression [link] (lower equation) is meaningful only when R ℓ ≥ 0 , and practical only for integer numbers of quantization levels 2 - 2 R ℓ (or practical values of R ℓ for a particular coding scheme). Practical strategies typically
    • set R ℓ = 0 to when [link] (lower equation) suggests that the optimal R ℓ is negative,
    • round positive R ℓ to practical values, and
    • iteratively re-optimize { R ℓ } using these rules until all R ℓ have practical values.
  • Plugging [link] (lower equation) into [link] , we find that optimal bit allocation implies
    σ q ℓ 2 = γ y 2 - 2 R ∏ k = 0 N - 1 σ y k 2 1 / N ∀ ℓ ,
    which means that, with optimal bit allocation, each coefficient contributes equally to reconstruction error.(Recall a similar property of the Lloyd-Max quantizer.)
<< 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