Editing Quantization (signal processing) (section)

===Rate–distortion quantizer design===
A scalar quantizer, which performs a quantization operation, can ordinarily be decomposed into two stages:
;Classification
:A process that classifies the input signal range into <math>M</math> non-overlapping ''[[interval (mathematics)|intervals]]'' <math>\{I_k\}_{k=1}^{M}</math>, by defining <math>M-1</math> ''decision boundary'' values <math> \{b_k\}_{k=1}^{M-1} </math>, such that <math> I_k = [b_{k-1}~,~b_k)</math> for <math>k = 1,2,\ldots,M</math>, with the extreme limits defined by <math> b_0 = -\infty</math> and <math> b_M = \infty</math>. All the inputs <math>x</math> that fall in a given interval range <math>I_k</math> are associated with the same quantization index <math>k</math>.
;Reconstruction
:Each interval <math> I_k </math> is represented by a ''reconstruction value'' <math> y_k </math> which implements the mapping <math> x \in I_k \Rightarrow y = y_k </math>.

These two stages together comprise the mathematical operation of <math>y = Q(x)</math>.

[[Entropy coding]] techniques can be applied to communicate the quantization indices from a source encoder that performs the classification stage to a decoder that performs the reconstruction stage. One way to do this is to associate each quantization index <math>k</math> with a binary codeword <math>c_k</math>. An important consideration is the number of bits used for each codeword, denoted here by <math>\mathrm{length}(c_k)</math>. As a result, the design of an <math>M</math>-level quantizer and an associated set of codewords for communicating its index values requires finding the values of <math> \{b_k\}_{k=1}^{M-1} </math>, <math>\{c_k\}_{k=1}^{M} </math> and <math> \{y_k\}_{k=1}^{M} </math> which optimally satisfy a selected set of design constraints such as the ''bit rate'' <math>R</math> and ''distortion'' <math>D</math>.

Assuming that an information source <math>S</math> produces random variables <math>X</math> with an associated PDF <math>f(x)</math>, the probability <math>p_k</math> that the random variable falls within a particular quantization interval <math>I_k</math> is given by:
:<math> p_k = P[x \in I_k] = \int_{b_{k-1}}^{b_k} f(x)dx </math>.

The resulting bit rate <math>R</math>, in units of average bits per quantized value, for this quantizer can be derived as follows:
:<math> R = \sum_{k=1}^{M} p_k \cdot \mathrm{length}(c_{k}) = \sum_{k=1}^{M} \mathrm{length}(c_k) \int_{b_{k-1}}^{b_k} f(x)dx </math>.

If it is assumed that distortion is measured by mean squared error,{{efn|Other distortion measures can also be considered, although mean squared error is a popular one.}} the distortion '''D''', is given by:
:<math> D = E[(x-Q(x))^2] = \int_{-\infty}^{\infty} (x-Q(x))^2f(x)dx = \sum_{k=1}^{M} \int_{b_{k-1}}^{b_k} (x-y_k)^2 f(x)dx </math>.

A key observation is that rate <math>R</math> depends on the decision boundaries <math>\{b_k\}_{k=1}^{M-1}</math> and the codeword lengths <math>\{\mathrm{length}(c_k)\}_{k=1}^{M}</math>, whereas the distortion <math>D</math> depends on the decision boundaries <math>\{b_k\}_{k=1}^{M-1}</math> and the reconstruction levels <math>\{y_k\}_{k=1}^{M}</math>.

After defining these two performance metrics for the quantizer, a typical rate–distortion formulation for a quantizer design problem can be expressed in one of two ways:
# Given a maximum distortion constraint <math>D \le D_\max</math>, minimize the bit rate <math>R</math>
# Given a maximum bit rate constraint <math>R \le R_\max</math>, minimize the distortion <math>D</math>

Often the solution to these problems can be equivalently (or approximately) expressed and solved by converting the formulation to the unconstrained problem <math>\min\left\{ D + \lambda \cdot R \right\}</math> where the [[Lagrange multiplier]] <math>\lambda</math> is a non-negative constant that establishes the appropriate balance between rate and distortion. Solving the unconstrained problem is equivalent to finding a point on the [[convex hull]] of the family of solutions to an equivalent constrained formulation of the problem. However, finding a solution – especially a [[Closed-form expression|closed-form]] solution – to any of these three problem formulations can be difficult. Solutions that do not require multi-dimensional iterative optimization techniques have been published for only three PDFs: the uniform,<ref>{{cite journal | last1=Farvardin | first1=N. |author-link=Nariman Farvardin| last2=Modestino | first2=J. | title=Optimum quantizer performance for a class of non-Gaussian memoryless sources | journal=IEEE Transactions on Information Theory | publisher=Institute of Electrical and Electronics Engineers (IEEE) | volume=30 | issue=3 | year=1984 | issn=0018-9448 | doi=10.1109/tit.1984.1056920 | pages=485–497}}(Section VI.C and Appendix B)</ref> [[Exponential distribution|exponential]],<ref name=SullivanIT>{{cite journal | last=Sullivan | first=G.J. |author-link=Gary Sullivan (engineer)| title=Efficient scalar quantization of exponential and Laplacian random variables | journal=IEEE Transactions on Information Theory | publisher=Institute of Electrical and Electronics Engineers (IEEE) | volume=42 | issue=5 | year=1996 | issn=0018-9448 | doi=10.1109/18.532878 | pages=1365–1374}}</ref> and [[Laplace distribution|Laplacian]]<ref name=SullivanIT/> distributions. Iterative optimization approaches can be used to find solutions in other cases.<ref name=GrayNeuhoff/><ref name=Berger72>{{cite journal | last=Berger | first=T. |author-link=Toby Berger| title=Optimum quantizers and permutation codes | journal=IEEE Transactions on Information Theory | publisher=Institute of Electrical and Electronics Engineers (IEEE) | volume=18 | issue=6 | year=1972 | issn=0018-9448 | doi=10.1109/tit.1972.1054906 | pages=759–765}}</ref><ref name=Berger82>{{cite journal | last=Berger | first=T. |author-link=Toby Berger| title=Minimum entropy quantizers and permutation codes | journal=IEEE Transactions on Information Theory | publisher=Institute of Electrical and Electronics Engineers (IEEE) | volume=28 | issue=2 | year=1982 | issn=0018-9448 | doi=10.1109/tit.1982.1056456 | pages=149–157}}</ref>

Note that the reconstruction values <math>\{y_k\}_{k=1}^{M}</math> affect only the distortion – they do not affect the bit rate – and that each individual <math>y_k</math> makes a separate contribution <math> d_k </math> to the total distortion as shown below:
:<math> D = \sum_{k=1}^{M} d_k </math>
where
:<math> d_k = \int_{b_{k-1}}^{b_k} (x-y_k)^2 f(x)dx </math>
This observation can be used to ease the analysis – given the set of <math>\{b_k\}_{k=1}^{M-1}</math> values, the value of each <math>y_k</math> can be optimized separately to minimize its contribution to the distortion <math>D</math>.

For the mean-square error distortion criterion, it can be easily shown that the optimal set of reconstruction values <math>\{y^*_k\}_{k=1}^{M}</math> is given by setting the reconstruction value <math>y_k</math> within each interval <math>I_k</math> to the [[conditional expected value]] (also referred to as the ''[[centroid]]'') within the interval, as given by:
:<math>y^*_k = \frac1{p_k} \int_{b_{k-1}}^{b_k} x f(x)dx</math>.

The use of sufficiently well-designed entropy coding techniques can result in the use of a bit rate that is close to the true information content of the indices <math>\{k\}_{k=1}^{M}</math>, such that effectively
:<math> \mathrm{length}(c_k) \approx -\log_2\left(p_k\right)</math>
and therefore
:<math> R = \sum_{k=1}^{M} -p_k \cdot \log_2\left(p_k\right) </math>.

The use of this approximation can allow the entropy coding design problem to be separated from the design of the quantizer itself. Modern entropy coding techniques such as [[arithmetic coding]] can achieve bit rates that are very close to the true entropy of a source, given a set of known (or adaptively estimated) probabilities <math>\{p_k\}_{k=1}^{M}</math>.

In some designs, rather than optimizing for a particular number of classification regions <math>M</math>, the quantizer design problem may include optimization of the value of <math>M</math> as well.  For some probabilistic source models, the best performance may be achieved when <math>M</math> approaches infinity.