Quantization Distortion
   HOME

TheInfoList



OR:

Quantization, in mathematics and
digital signal processing Digital signal processing (DSP) is the use of digital processing, such as by computers or more specialized digital signal processors, to perform a wide variety of signal processing operations. The digital signals processed in this manner are ...
, is the process of mapping input values from a large set (often a continuous set) to output values in a (countable) smaller set, often with a finite number of elements.
Rounding Rounding means replacing a number with an approximate value that has a shorter, simpler, or more explicit representation. For example, replacing $ with $, the fraction 312/937 with 1/3, or the expression with . Rounding is often done to obta ...
and
truncation In mathematics and computer science, truncation is limiting the number of digits right of the decimal point. Truncation and floor function Truncation of positive real numbers can be done using the floor function. Given a number x \in \mathbb ...
are typical examples of quantization processes. Quantization is involved to some degree in nearly all digital signal processing, as the process of representing a signal in digital form ordinarily involves rounding. Quantization also forms the core of essentially all
lossy compression In information technology, lossy compression or irreversible compression is the class of data compression methods that uses inexact approximations and partial data discarding to represent the content. These techniques are used to reduce data size ...
algorithms. The difference between an input value and its quantized value (such as
round-off error A roundoff error, also called rounding error, is the difference between the result produced by a given algorithm using exact arithmetic and the result produced by the same algorithm using finite-precision, rounded arithmetic. Rounding errors are d ...
) is referred to as quantization error. A device or algorithmic function that performs quantization is called a quantizer. An
analog-to-digital converter In electronics, an analog-to-digital converter (ADC, A/D, or A-to-D) is a system that converts an analog signal, such as a sound picked up by a microphone or light entering a digital camera, into a digital signal. An ADC may also provide ...
is an example of a quantizer.


Example

For example,
rounding Rounding means replacing a number with an approximate value that has a shorter, simpler, or more explicit representation. For example, replacing $ with $, the fraction 312/937 with 1/3, or the expression with . Rounding is often done to obta ...
a
real number In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every real ...
x to the nearest integer value forms a very basic type of quantizer – a ''uniform'' one. A typical (''mid-tread'') uniform quantizer with a quantization ''step size'' equal to some value \Delta can be expressed as :Q(x) = \Delta \cdot \left\lfloor \frac + \frac \right\rfloor, where the notation \lfloor \ \rfloor denotes the
floor function In mathematics and computer science, the floor function is the function that takes as input a real number , and gives as output the greatest integer less than or equal to , denoted or . Similarly, the ceiling function maps to the least int ...
. The essential property of a quantizer is having a countable-set of possible output-values members smaller than the set of possible input values. The members of the set of output values may have integer, rational, or real values. For simple rounding to the nearest integer, the step size \Delta is equal to 1. With \Delta = 1 or with \Delta equal to any other integer value, this quantizer has real-valued inputs and integer-valued outputs. When the quantization step size (Δ) is small relative to the variation in the signal being quantized, it is relatively simple to show that the
mean squared error In statistics, the mean squared error (MSE) or mean squared deviation (MSD) of an estimator (of a procedure for estimating an unobserved quantity) measures the average of the squares of the errors—that is, the average squared difference between ...
produced by such a rounding operation will be approximately \Delta^2/ 12.W. R. Bennett,
Spectra of Quantized Signals
, ''
Bell System Technical Journal The ''Bell Labs Technical Journal'' is the in-house scientific journal for scientists of Nokia Bell Labs, published yearly by the IEEE society. The managing editor is Charles Bahr. The journal was originally established as the ''Bell System Techn ...
'', Vol. 27, pp. 446–472, July 1948.
Seymour Stein and J. Jay Jones,
Modern Communication Principles
',
McGraw–Hill S&P Global Inc. (prior to April 2016 McGraw Hill Financial, Inc., and prior to 2013 The McGraw–Hill Companies, Inc.) is an American publicly traded corporation headquartered in Manhattan, New York City. Its primary areas of business are financ ...
, , 1967 (p. 196).
Mean squared error is also called the quantization ''noise power''. Adding one bit to the quantizer halves the value of Δ, which reduces the noise power by the factor ¼. In terms of
decibels The decibel (symbol: dB) is a relative unit of measurement equal to one tenth of a bel (B). It expresses the ratio of two values of a Power, root-power, and field quantities, power or root-power quantity on a logarithmic scale. Two signals whose ...
, the noise power change is \scriptstyle 10\cdot \log_(1/4)\ \approx\ -6\ \mathrm. Because the set of possible output values of a quantizer is countable, any quantizer can be decomposed into two distinct stages, which can be referred to as the ''classification'' stage (or ''forward quantization'' stage) and the ''reconstruction'' stage (or ''inverse quantization'' stage), where the classification stage maps the input value to an integer ''quantization index'' k and the reconstruction stage maps the index k to the ''reconstruction value'' y_k that is the output approximation of the input value. For the example uniform quantizer described above, the forward quantization stage can be expressed as :k = \left\lfloor \frac + \frac\right\rfloor, and the reconstruction stage for this example quantizer is simply :y_k = k \cdot \Delta. This decomposition is useful for the design and analysis of quantization behavior, and it illustrates how the quantized data can be communicated over a
communication channel A communication channel refers either to a physical transmission medium such as a wire, or to a logical connection over a multiplexed medium such as a radio channel in telecommunications and computer networking. A channel is used for informa ...
– a ''source encoder'' can perform the forward quantization stage and send the index information through a communication channel, and a ''decoder'' can perform the reconstruction stage to produce the output approximation of the original input data. In general, the forward quantization stage may use any function that maps the input data to the integer space of the quantization index data, and the inverse quantization stage can conceptually (or literally) be a table look-up operation to map each quantization index to a corresponding reconstruction value. This two-stage decomposition applies equally well to
vector Vector most often refers to: *Euclidean vector, a quantity with a magnitude and a direction *Vector (epidemiology), an agent that carries and transmits an infectious pathogen into another living organism Vector may also refer to: Mathematic ...
as well as scalar quantizers.


Mathematical properties

Because quantization is a many-to-few mapping, it is an inherently
non-linear In mathematics and science, a nonlinear system is a system in which the change of the output is not proportional to the change of the input. Nonlinear problems are of interest to engineers, biologists, physicists, mathematicians, and many other ...
and irreversible process (i.e., because the same output value is shared by multiple input values, it is impossible, in general, to recover the exact input value when given only the output value). The set of possible input values may be infinitely large, and may possibly be continuous and therefore
uncountable In mathematics, an uncountable set (or uncountably infinite set) is an infinite set that contains too many elements to be countable. The uncountability of a set is closely related to its cardinal number: a set is uncountable if its cardinal numb ...
(such as the set of all real numbers, or all real numbers within some limited range). The set of possible output values may be
finite Finite is the opposite of infinite. It may refer to: * Finite number (disambiguation) * Finite set, a set whose cardinality (number of elements) is some natural number * Finite verb, a verb form that has a subject, usually being inflected or marked ...
or
countably infinite In mathematics, a set is countable if either it is finite or it can be made in one to one correspondence with the set of natural numbers. Equivalently, a set is ''countable'' if there exists an injective function from it into the natural numbers; ...
. The input and output sets involved in quantization can be defined in a rather general way. For example, vector quantization is the application of quantization to multi-dimensional (vector-valued) input data.


Types


Analog-to-digital converter

An
analog-to-digital converter In electronics, an analog-to-digital converter (ADC, A/D, or A-to-D) is a system that converts an analog signal, such as a sound picked up by a microphone or light entering a digital camera, into a digital signal. An ADC may also provide ...
(ADC) can be modeled as two processes: sampling and quantization. Sampling converts a time-varying voltage signal into a
discrete-time signal In mathematical dynamics, discrete time and continuous time are two alternative frameworks within which variables that evolve over time are modeled. Discrete time Discrete time views values of variables as occurring at distinct, separate "po ...
, a sequence of real numbers. Quantization replaces each real number with an approximation from a finite set of discrete values. Most commonly, these discrete values are represented as fixed-point words. Though any number of quantization levels is possible, common word-lengths are
8-bit In computer architecture, 8-bit Integer (computer science), integers or other Data (computing), data units are those that are 8 bits wide (1 octet (computing), octet). Also, 8-bit central processing unit (CPU) and arithmetic logic unit (ALU) arc ...
(256 levels), 16-bit (65,536 levels) and 24-bit (16.8 million levels). Quantizing a sequence of numbers produces a sequence of quantization errors which is sometimes modeled as an additive random signal called quantization noise because of its
stochastic Stochastic (, ) refers to the property of being well described by a random probability distribution. Although stochasticity and randomness are distinct in that the former refers to a modeling approach and the latter refers to phenomena themselv ...
behavior. The more levels a quantizer uses, the lower is its quantization noise power.


Rate–distortion optimization

'' Rate–distortion optimized'' quantization is encountered in
source coding In information theory, data compression, source coding, or bit-rate reduction is the process of encoding information using fewer bits than the original representation. Any particular compression is either lossy or lossless. Lossless compression ...
for lossy data compression algorithms, where the purpose is to manage distortion within the limits of the
bit rate In telecommunications and computing, bit rate (bitrate or as a variable ''R'') is the number of bits that are conveyed or processed per unit of time. The bit rate is expressed in the unit bit per second (symbol: bit/s), often in conjunction w ...
supported by a communication channel or storage medium. The analysis of quantization in this context involves studying the amount of data (typically measured in digits or bits or bit ''rate'') that is used to represent the output of the quantizer, and studying the loss of precision that is introduced by the quantization process (which is referred to as the ''distortion'').


Mid-riser and mid-tread uniform quantizers

Most uniform quantizers for signed input data can be classified as being of one of two types: ''mid-riser'' and ''mid-tread''. The terminology is based on what happens in the region around the value 0, and uses the analogy of viewing the input-output function of the quantizer as a
stairway Stairs are a structure designed to bridge a large vertical distance between lower and higher levels by dividing it into smaller vertical distances. This is achieved as a diagonal series of horizontal platforms called steps which enable passage ...
. Mid-tread quantizers have a zero-valued reconstruction level (corresponding to a ''tread'' of a stairway), while mid-riser quantizers have a zero-valued classification threshold (corresponding to a '' riser'' of a stairway). Mid-tread quantization involves rounding. The formulas for mid-tread uniform quantization are provided in the previous section. Mid-riser quantization involves truncation. The input-output formula for a mid-riser uniform quantizer is given by: :Q(x) = \Delta\cdot\left(\left\lfloor \frac\right\rfloor + \frac1\right), where the classification rule is given by :k = \left\lfloor \frac \right\rfloor and the reconstruction rule is :y_k = \Delta\cdot\left(k+\tfrac1\right). Note that mid-riser uniform quantizers do not have a zero output value – their minimum output magnitude is half the step size. In contrast, mid-tread quantizers do have a zero output level. For some applications, having a zero output signal representation may be a necessity. In general, a mid-riser or mid-tread quantizer may not actually be a ''uniform'' quantizer – i.e., the size of the quantizer's classification
intervals Interval may refer to: Mathematics and physics * Interval (mathematics), a range of numbers ** Partially ordered set#Intervals, its generalization from numbers to arbitrary partially ordered sets * A statistical level of measurement * Interval e ...
may not all be the same, or the spacing between its possible output values may not all be the same. The distinguishing characteristic of a mid-riser quantizer is that it has a classification threshold value that is exactly zero, and the distinguishing characteristic of a mid-tread quantizer is that is it has a reconstruction value that is exactly zero.


Dead-zone quantizers

A dead-zone quantizer is a type of mid-tread quantizer with symmetric behavior around 0. The region around the zero output value of such a quantizer is referred to as the ''dead zone'' or ''
deadband A deadband or dead-band (also known as a dead zone or a neutral zone) is a band of input values in the domain of a transfer function in a control system or signal processing system where the output is zero (the output is 'dead' - no action occurs) ...
''. The dead zone can sometimes serve the same purpose as a
noise gate A noise gate or gate is an electronic device or software that is used to control the volume of an audio signal. Comparable to a compressor, which attenuates signals ''above'' a threshold, such as loud attacks from the start of musical notes, no ...
or
squelch In telecommunications, squelch is a circuit function that acts to suppress the audio (or video) output of a receiver in the absence of a strong input signal. Essentially, squelch is a specialized type of noise gate designed to suppress weak s ...
function. Especially for compression applications, the dead-zone may be given a different width than that for the other steps. For an otherwise-uniform quantizer, the dead-zone width can be set to any value w by using the forward quantization rule :k = \sgn(x) \cdot \max\left(0, \left\lfloor \frac+1\right\rfloor\right), where the function is the
sign function In mathematics, the sign function or signum function (from '' signum'', Latin for "sign") is an odd mathematical function that extracts the sign of a real number. In mathematical expressions the sign function is often represented as . To avoi ...
(also known as the ''signum'' function). The general reconstruction rule for such a dead-zone quantizer is given by :y_k = \sgn(k) \cdot\left(\frac+\Delta\cdot (, k, -1+r_k)\right), where r_k is a reconstruction offset value in the range of 0 to 1 as a fraction of the step size. Ordinarily, 0 \le r_k \le \tfrac1 when quantizing input data with a typical
probability density function In probability theory, a probability density function (PDF), or density of a continuous random variable, is a function whose value at any given sample (or point) in the sample space (the set of possible values taken by the random variable) can ...
(PDF) that is symmetric around zero and reaches its peak value at zero (such as a
Gaussian Carl Friedrich Gauss (1777–1855) is the eponym of all of the topics listed below. There are over 100 topics all named after this German mathematician and scientist, all in the fields of mathematics, physics, and astronomy. The English eponymo ...
,
Laplacian In mathematics, the Laplace operator or Laplacian is a differential operator given by the divergence of the gradient of a scalar function on Euclidean space. It is usually denoted by the symbols \nabla\cdot\nabla, \nabla^2 (where \nabla is the ...
, or generalized Gaussian PDF). Although r_k may depend on k in general, and can be chosen to fulfill the optimality condition described below, it is often simply set to a constant, such as \tfrac1. (Note that in this definition, y_0 = 0 due to the definition of the function, so r_0 has no effect.) A very commonly used special case (e.g., the scheme typically used in financial accounting and elementary mathematics) is to set w=\Delta and r_k=\tfrac1 for all k. In this case, the dead-zone quantizer is also a uniform quantizer, since the central dead-zone of this quantizer has the same width as all of its other steps, and all of its reconstruction values are equally spaced as well.


Noise and error characteristics


Additive noise model

A common assumption for the analysis of
quantization error Quantization, in mathematics and digital signal processing, is the process of mapping input values from a large set (often a continuous set) to output values in a (countable) smaller set, often with a finite number of elements. Rounding and ...
is that it affects a signal processing system in a similar manner to that of additive
white noise In signal processing, white noise is a random signal having equal intensity at different frequencies, giving it a constant power spectral density. The term is used, with this or similar meanings, in many scientific and technical disciplines, ...
– having negligible correlation with the signal and an approximately flat
power spectral density The power spectrum S_(f) of a time series x(t) describes the distribution of power into frequency components composing that signal. According to Fourier analysis, any physical signal can be decomposed into a number of discrete frequencies, o ...
.
Bernard Widrow Bernard Widrow (born December 24, 1929) is a U.S. professor of electrical engineering at Stanford University. He is the co-inventor of the Widrow–Hoff least mean squares filter (LMS) adaptive algorithm with his then doctoral student Ted Hoff. ...
,
Statistical analysis of amplitude quantized sampled data systems
, ''Trans. AIEE Pt. II: Appl. Ind.'', Vol. 79, pp. 555–568, Jan. 1961.
The additive noise model is commonly used for the analysis of quantization error effects in digital filtering systems, and it can be very useful in such analysis. It has been shown to be a valid model in cases of high resolution quantization (small \Delta relative to the signal strength) with smooth PDFs. Additive noise behavior is not always a valid assumption. Quantization error (for quantizers defined as described here) is deterministically related to the signal and not entirely independent of it. Thus, periodic signals can create periodic quantization noise. And in some cases it can even cause
limit cycle In mathematics, in the study of dynamical systems with two-dimensional phase space, a limit cycle is a closed trajectory in phase space having the property that at least one other trajectory spirals into it either as time approaches infinity ...
s to appear in digital signal processing systems. One way to ensure effective independence of the quantization error from the source signal is to perform ''
dither Dither is an intentionally applied form of image noise, noise used to randomize quantization error, preventing large-scale patterns such as color banding in images. Dither is routinely used in processing of both digital audio and digital vide ...
ed quantization'' (sometimes with ''
noise shaping Noise shaping is a technique typically used in digital audio, image, and video processing, usually in combination with dithering, as part of the process of quantization or bit-depth reduction of a digital signal. Its purpose is to increase the ap ...
''), which involves adding random (or
pseudo-random A pseudorandom sequence of numbers is one that appears to be statistically random, despite having been produced by a completely deterministic and repeatable process. Background The generation of random numbers has many uses, such as for rando ...
) noise to the signal prior to quantization.


Quantization error models

In the typical case, the original signal is much larger than one
least significant bit In computing, bit numbering is the convention used to identify the bit positions in a binary number. Bit significance and indexing In computing, the least significant bit (LSB) is the bit position in a binary integer representing the binary 1 ...
(LSB). When this is the case, the quantization error is not significantly correlated with the signal, and has an approximately uniform distribution. When rounding is used to quantize, the quantization error has a
mean There are several kinds of mean in mathematics, especially in statistics. Each mean serves to summarize a given group of data, often to better understand the overall value (magnitude and sign) of a given data set. For a data set, the ''arithme ...
of zero and the
root mean square In mathematics and its applications, the root mean square of a set of numbers x_i (abbreviated as RMS, or rms and denoted in formulas as either x_\mathrm or \mathrm_x) is defined as the square root of the mean square (the arithmetic mean of the ...
(RMS) value is the
standard deviation In statistics, the standard deviation is a measure of the amount of variation or dispersion of a set of values. A low standard deviation indicates that the values tend to be close to the mean (also called the expected value) of the set, while ...
of this distribution, given by \scriptstyle \mathrm\ \approx\ 0.289\,\mathrm. When truncation is used, the error has a non-zero mean of \scriptstyle \mathrm and the RMS value is \scriptstyle \mathrm. Although rounding yields less RMS error than truncation, the difference is only due to the static (DC) term of \scriptstyle \mathrm. The RMS values of the AC error are exactly the same in both cases, so there is no special advantage of rounding over truncation in situations where the DC term of the error can be ignored (such as in AC coupled systems). In either case, the standard deviation, as a percentage of the full signal range, changes by a factor of 2 for each 1-bit change in the number of quantization bits. The potential signal-to-quantization-noise power ratio therefore changes by 4, or \scriptstyle 10\cdot \log_(4), approximately 6 dB per bit. At lower amplitudes the quantization error becomes dependent on the input signal, resulting in distortion. This distortion is created after the anti-aliasing filter, and if these distortions are above 1/2 the sample rate they will alias back into the band of interest. In order to make the quantization error independent of the input signal, the signal is dithered by adding noise to the signal. This slightly reduces signal to noise ratio, but can completely eliminate the distortion.


Quantization noise model

Quantization noise is a
model A model is an informative representation of an object, person or system. The term originally denoted the Plan_(drawing), plans of a building in late 16th-century English, and derived via French and Italian ultimately from Latin ''modulus'', a mea ...
of quantization error introduced by quantization in the ADC. It is a rounding error between the analog input voltage to the ADC and the output digitized value. The noise is non-linear and signal-dependent. It can be modelled in several different ways. In an ideal ADC, where the quantization error is uniformly distributed between −1/2 LSB and +1/2 LSB, and the signal has a uniform distribution covering all quantization levels, the
Signal-to-quantization-noise ratio Signal-to-quantization-noise ratio (SQNR or SNqR) is widely used quality measure in analysing digitizing schemes such as pulse-code modulation (PCM). The SQNR reflects the relationship between the maximum nominal signal strength and the quantizati ...
(SQNR) can be calculated from :\mathrm = 20 \log_(2^Q) \approx 6.02 \cdot Q\ \mathrm \,\! where Q is the number of quantization bits. The most common test signals that fulfill this are full amplitude
triangle wave A triangular wave or triangle wave is a non-sinusoidal waveform named for its triangular shape. It is a periodic, piecewise linear, continuous real function. Like a square wave, the triangle wave contains only odd harmonics. However, the ...
s and
sawtooth wave The sawtooth wave (or saw wave) is a kind of non-sinusoidal waveform. It is so named based on its resemblance to the teeth of a plain-toothed saw with a zero rake angle. A single sawtooth, or an intermittently triggered sawtooth, is called a ...
s. For example, a
16-bit 16-bit microcomputers are microcomputers that use 16-bit microprocessors. A 16-bit register can store 216 different values. The range of integer values that can be stored in 16 bits depends on the integer representation used. With the two mos ...
ADC has a maximum signal-to-quantization-noise ratio of 6.02 × 16 = 96.3 dB. When the input signal is a full-amplitude
sine wave A sine wave, sinusoidal wave, or just sinusoid is a curve, mathematical curve defined in terms of the ''sine'' trigonometric function, of which it is the graph of a function, graph. It is a type of continuous wave and also a Smoothness, smooth p ...
the distribution of the signal is no longer uniform, and the corresponding equation is instead : \mathrm \approx 1.761 + 6.02 \cdot Q \ \mathrm \,\! Here, the quantization noise is once again ''assumed'' to be uniformly distributed. When the input signal has a high amplitude and a wide frequency spectrum this is the case. In this case a 16-bit ADC has a maximum signal-to-noise ratio of 98.09 dB. The 1.761 difference in signal-to-noise only occurs due to the signal being a full-scale sine wave instead of a triangle or sawtooth. For complex signals in high-resolution ADCs this is an accurate model. For low-resolution ADCs, low-level signals in high-resolution ADCs, and for simple waveforms the quantization noise is not uniformly distributed, making this model inaccurate. In these cases the quantization noise distribution is strongly affected by the exact amplitude of the signal. The calculations are relative to full-scale input. For smaller signals, the relative quantization distortion can be very large. To circumvent this issue, analog
companding In telecommunication and signal processing, companding (occasionally called compansion) is a method of mitigating the detrimental effects of a channel with limited dynamic range. The name is a portmanteau of the words compressing and expanding, ...
can be used, but this can introduce distortion.


Design


Granular distortion and overload distortion

Often the design of a quantizer involves supporting only a limited range of possible output values and performing clipping to limit the output to this range whenever the input exceeds the supported range. The error introduced by this clipping is referred to as ''overload'' distortion. Within the extreme limits of the supported range, the amount of spacing between the selectable output values of a quantizer is referred to as its ''granularity'', and the error introduced by this spacing is referred to as ''granular'' distortion. It is common for the design of a quantizer to involve determining the proper balance between granular distortion and overload distortion. For a given supported number of possible output values, reducing the average granular distortion may involve increasing the average overload distortion, and vice versa. A technique for controlling the amplitude of the signal (or, equivalently, the quantization step size \Delta) to achieve the appropriate balance is the use of ''
automatic gain control Automatic gain control (AGC) is a closed-loop feedback regulating circuit in an amplifier or chain of amplifiers, the purpose of which is to maintain a suitable signal amplitude at its output, despite variation of the signal amplitude at the inpu ...
'' (AGC). However, in some quantizer designs, the concepts of granular error and overload error may not apply (e.g., for a quantizer with a limited range of input data or with a countably infinite set of selectable output values).


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 M non-overlapping ''
intervals Interval may refer to: Mathematics and physics * Interval (mathematics), a range of numbers ** Partially ordered set#Intervals, its generalization from numbers to arbitrary partially ordered sets * A statistical level of measurement * Interval e ...
'' \_^, by defining M-1 ''decision boundary'' values \_^ , such that I_k = [b_~,~b_k) for k = 1,2,\ldots,M, with the extreme limits defined by b_0 = -\infty and b_M = \infty. All the inputs x that fall in a given interval range I_k are associated with the same quantization index k. ;Reconstruction :Each interval I_k is represented by a ''reconstruction value'' y_k which implements the mapping x \in I_k \Rightarrow y = y_k . These two stages together comprise the mathematical operation of y = Q(x). 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 k with a binary codeword c_k. An important consideration is the number of bits used for each codeword, denoted here by \mathrm(c_k). As a result, the design of an M-level quantizer and an associated set of codewords for communicating its index values requires finding the values of \_^ , \_^ and \_^ which optimally satisfy a selected set of design constraints such as the ''bit rate'' R and ''distortion'' D. Assuming that an information source S produces random variables X with an associated PDF f(x), the probability p_k that the random variable falls within a particular quantization interval I_k is given by: : p_k = P \in I_k= \int_^ f(x)dx . The resulting bit rate R, in units of average bits per quantized value, for this quantizer can be derived as follows: : R = \sum_^ p_k \cdot \mathrm(c_) = \sum_^ \mathrm(c_k) \int_^ f(x)dx . If it is assumed that distortion is measured by mean squared error, the distortion D, is given by: : D = E x-Q(x))^2= \int_^ (x-Q(x))^2f(x)dx = \sum_^ \int_^ (x-y_k)^2 f(x)dx . A key observation is that rate R depends on the decision boundaries \_^ and the codeword lengths \_^, whereas the distortion D depends on the decision boundaries \_^ and the reconstruction levels \_^. 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 D \le D_\max, minimize the bit rate R # Given a maximum bit rate constraint R \le R_\max, minimize the distortion D Often the solution to these problems can be equivalently (or approximately) expressed and solved by converting the formulation to the unconstrained problem \min\left\ where the
Lagrange multiplier In mathematical optimization, the method of Lagrange multipliers is a strategy for finding the local maxima and minima of a function subject to equality constraints (i.e., subject to the condition that one or more equations have to be satisfied ex ...
\lambda 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 In geometry, the convex hull or convex envelope or convex closure of a shape is the smallest convex set that contains it. The convex hull may be defined either as the intersection of all convex sets containing a given subset of a Euclidean space ...
of the family of solutions to an equivalent constrained formulation of the problem. However, finding a solution – especially a 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,
exponential Exponential may refer to any of several mathematical topics related to exponentiation, including: *Exponential function, also: **Matrix exponential, the matrix analogue to the above * Exponential decay, decrease at a rate proportional to value *Exp ...
, and
Laplacian In mathematics, the Laplace operator or Laplacian is a differential operator given by the divergence of the gradient of a scalar function on Euclidean space. It is usually denoted by the symbols \nabla\cdot\nabla, \nabla^2 (where \nabla is the ...
distributions. Iterative optimization approaches can be used to find solutions in other cases. Note that the reconstruction values \_^ affect only the distortion – they do not affect the bit rate – and that each individual y_k makes a separate contribution d_k to the total distortion as shown below: : D = \sum_^ d_k where : d_k = \int_^ (x-y_k)^2 f(x)dx This observation can be used to ease the analysis – given the set of \_^ values, the value of each y_k can be optimized separately to minimize its contribution to the distortion D. For the mean-square error distortion criterion, it can be easily shown that the optimal set of reconstruction values \_^ is given by setting the reconstruction value y_k within each interval I_k to the
conditional expected value In probability theory, the conditional expectation, conditional expected value, or conditional mean of a random variable is its expected value – the value it would take “on average” over an arbitrarily large number of occurrences – given ...
(also referred to as the ''
centroid In mathematics and physics, the centroid, also known as geometric center or center of figure, of a plane figure or solid figure is the arithmetic mean position of all the points in the surface of the figure. The same definition extends to any ob ...
'') within the interval, as given by: :y^*_k = \frac1 \int_^ x f(x)dx. 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 \_^, such that effectively : \mathrm(c_k) \approx -\log_2\left(p_k\right) and therefore : R = \sum_^ -p_k \cdot \log_2\left(p_k\right) . 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 Arithmetic coding (AC) is a form of entropy encoding used in lossless data compression. Normally, a string of characters is represented using a fixed number of bits per character, as in the ASCII code. When a string is converted to arithmetic e ...
can achieve bit rates that are very close to the true entropy of a source, given a set of known (or adaptively estimated) probabilities \_^. In some designs, rather than optimizing for a particular number of classification regions M, the quantizer design problem may include optimization of the value of M as well. For some probabilistic source models, the best performance may be achieved when M approaches infinity.


Neglecting the entropy constraint: Lloyd–Max quantization

In the above formulation, if the bit rate constraint is neglected by setting \lambda equal to 0, or equivalently if it is assumed that a fixed-length code (FLC) will be used to represent the quantized data instead of a
variable-length code In coding theory a variable-length code is a code which maps source symbols to a ''variable'' number of bits. Variable-length codes can allow sources to be compressed and decompressed with ''zero'' error (lossless data compression) and still be ...
(or some other entropy coding technology such as arithmetic coding that is better than an FLC in the rate–distortion sense), the optimization problem reduces to minimization of distortion D alone. The indices produced by an M-level quantizer can be coded using a fixed-length code using R = \lceil \log_2 M \rceil bits/symbol. For example, when M=256 levels, the FLC bit rate R is 8 bits/symbol. For this reason, such a quantizer has sometimes been called an 8-bit quantizer. However using an FLC eliminates the compression improvement that can be obtained by use of better entropy coding. Assuming an FLC with M levels, the rate–distortion minimization problem can be reduced to distortion minimization alone. The reduced problem can be stated as follows: given a source X with PDF f(x) and the constraint that the quantizer must use only M classification regions, find the decision boundaries \_^ and reconstruction levels \_^M to minimize the resulting distortion : D=E x-Q(x))^2= \int_^ (x-Q(x))^2f(x)dx = \sum_^ \int_^ (x-y_k)^2 f(x)dx =\sum_^ d_k . Finding an optimal solution to the above problem results in a quantizer sometimes called a MMSQE (minimum mean-square quantization error) solution, and the resulting PDF-optimized (non-uniform) quantizer is referred to as a ''Lloyd–Max'' quantizer, named after two people who independently developed iterative methods to solve the two sets of simultaneous equations resulting from = 0 and = 0 , as follows: : = 0 \Rightarrow b_k = , which places each threshold at the midpoint between each pair of reconstruction values, and : = 0 \Rightarrow y_k = = \frac1 \int_^ x f(x) dx which places each reconstruction value at the centroid (conditional expected value) of its associated classification interval. Lloyd's Method I algorithm, originally described in 1957, can be generalized in a straightforward way for application to vector data. This generalization results in the Linde–Buzo–Gray (LBG) or
k-means ''k''-means clustering is a method of vector quantization, originally from signal processing, that aims to partition ''n'' observations into ''k'' clusters in which each observation belongs to the cluster with the nearest mean (cluster centers o ...
classifier optimization methods. Moreover, the technique can be further generalized in a straightforward way to also include an entropy constraint for vector data.


Uniform quantization and the 6 dB/bit approximation

The Lloyd–Max quantizer is actually a uniform quantizer when the input PDF is uniformly distributed over the range [y_1-\Delta/2,~y_M+\Delta/2). However, for a source that does not have a uniform distribution, the minimum-distortion quantizer may not be a uniform quantizer. The analysis of a uniform quantizer applied to a uniformly distributed source can be summarized in what follows: A symmetric source X can be modelled with f(x)= \tfrac1, for x \in [-X_ , X_] and 0 elsewhere. The step size \Delta = \tfrac and the ''signal to quantization noise ratio'' (SQNR) of the quantizer is := 10\log_ = 10\log_= 10\log_M^2= 20\log_M. For a fixed-length code using N bits, M=2^N, resulting in = 20\log_ = N\cdot(20\log_2) = N\cdot 6.0206\,\rm, or approximately 6 dB per bit. For example, for N=8 bits, M=256 levels and SQNR = 8×6 = 48 dB; and for N=16 bits, M=65536 and SQNR = 16×6 = 96 dB. The property of 6 dB improvement in SQNR for each extra bit used in quantization is a well-known figure of merit. However, it must be used with care: this derivation is only for a uniform quantizer applied to a uniform source. For other source PDFs and other quantizer designs, the SQNR may be somewhat different from that predicted by 6 dB/bit, depending on the type of PDF, the type of source, the type of quantizer, and the bit rate range of operation. However, it is common to assume that for many sources, the slope of a quantizer SQNR function can be approximated as 6 dB/bit when operating at a sufficiently high bit rate. At asymptotically high bit rates, cutting the step size in half increases the bit rate by approximately 1 bit per sample (because 1 bit is needed to indicate whether the value is in the left or right half of the prior double-sized interval) and reduces the mean squared error by a factor of 4 (i.e., 6 dB) based on the \Delta^2/12 approximation. At asymptotically high bit rates, the 6 dB/bit approximation is supported for many source PDFs by rigorous theoretical analysis. Moreover, the structure of the optimal scalar quantizer (in the rate–distortion sense) approaches that of a uniform quantizer under these conditions.


In other fields

Many physical quantities are actually quantized by physical entities. Examples of fields where this limitation applies include
electronics The field of electronics is a branch of physics and electrical engineering that deals with the emission, behaviour and effects of electrons using electronic devices. Electronics uses active devices to control electron flow by amplification ...
(due to
electrons The electron ( or ) is a subatomic particle with a negative one elementary electric charge. Electrons belong to the first generation of the lepton particle family, and are generally thought to be elementary particles because they have no ...
),
optics Optics is the branch of physics that studies the behaviour and properties of light, including its interactions with matter and the construction of instruments that use or detect it. Optics usually describes the behaviour of visible, ultraviole ...
(due to
photons A photon () is an elementary particle that is a quantum of the electromagnetic field, including electromagnetic radiation such as light and radio waves, and the force carrier for the electromagnetic force. Photons are massless, so they alway ...
),
biology Biology is the scientific study of life. It is a natural science with a broad scope but has several unifying themes that tie it together as a single, coherent field. For instance, all organisms are made up of cells that process hereditary i ...
(due to DNA),
physics Physics is the natural science that studies matter, its fundamental constituents, its motion and behavior through space and time, and the related entities of energy and force. "Physical science is that department of knowledge which r ...
(due to
Planck limits In physics, Planck's law describes the spectral density of electromagnetic radiation emitted by a black body in thermal equilibrium at a given temperature , when there is no net flow of matter or energy between the body and its environment. At ...
) and
chemistry Chemistry is the science, scientific study of the properties and behavior of matter. It is a natural science that covers the Chemical element, elements that make up matter to the chemical compound, compounds made of atoms, molecules and ions ...
(due to
molecules A molecule is a group of two or more atoms held together by attractive forces known as chemical bonds; depending on context, the term may or may not include ions which satisfy this criterion. In quantum physics, organic chemistry, and bioche ...
).


See also

* Beta encoder *
Color quantization In computer graphics, color quantization or color image quantization is quantization applied to color spaces; it is a process that reduces the number of distinct colors used in an image, usually with the intention that the new image should be as v ...
*
Data binning Data binning, also called data discrete binning or data bucketing, is a data pre-processing technique used to reduce the effects of minor observation errors. The original data values which fall into a given small interval, a '' bin'', are replaced b ...
*
Discretization In applied mathematics, discretization is the process of transferring continuous functions, models, variables, and equations into discrete counterparts. This process is usually carried out as a first step toward making them suitable for numerical ...
*
Discretization error In numerical analysis, computational physics, and simulation, discretization error is the error resulting from the fact that a function of a continuous variable is represented in the computer by a finite number of evaluations, for example, on a ...
*
Posterization Posterization or posterisation of an image is the conversion of a continuous gradation of tone to several regions of fewer tones, causing abrupt changes from one tone to another. This was originally done with photographic processes to create p ...
*
Pulse-code modulation Pulse-code modulation (PCM) is a method used to digitally represent sampled analog signals. It is the standard form of digital audio in computers, compact discs, digital telephony and other digital audio applications. In a PCM stream, the ...
*
Quantile In statistics and probability, quantiles are cut points dividing the range of a probability distribution into continuous intervals with equal probabilities, or dividing the observations in a sample in the same way. There is one fewer quantile th ...
*
Quantization (image processing) Quantization, involved in image processing, is a lossy compression technique achieved by compressing a range of values to a single quantum (discrete) value. When the number of discrete symbols in a given stream is reduced, the stream becomes more ...
*
Regression dilution Regression dilution, also known as regression attenuation, is the biasing of the linear regression slope towards zero (the underestimation of its absolute value), caused by errors in the independent variable. Consider fitting a straight line f ...
– a bias in parameter estimates caused by errors such as quantization in the explanatory or independent variable


Notes


References

* * * *


Further reading

* {{DEFAULTSORT:Quantization (Signal Processing) Digital signal processing Computer graphic artifacts Digital audio Noise (electronics) Signal processing Telecommunication theory