Quantization (signal processing)

From Wikipedia, the free encyclopedia

Jump to: navigation, search

Sampled signal (discrete signal): discrete time, continuous values.

Quantized signal: continuous time, discrete values.

Digital signal (sampled, quantized): discrete time, discrete values.

In digital signal processing, quantization is the process of approximating ("mapping") a continuous range of values (or a very large set of possible discrete values) by a relatively small ("finite") set of ("values which can still take on continuous range") discrete symbols or integer values. For example, rounding a real number in the interval $[0,100]$ to an integer $0,1,2\dots,100.$

In other words, quantization can be described as a mapping that represents a finite continuous interval $I = [a, b]$ of the range of a continuous valued signal, with a single number c, which is also on that interval. For example, rounding to the nearest integer (rounding ½ up) replaces the interval $[c - .5, c + .5)$ with the number c, for integer c. After that quantization we produce a finite set of values which can be encoded by say binary techniques.

In signal processing, quantization refers to approximating the output by one of a discrete and finite set of values, while replacing the input by a discrete set is called discretization, and is done by sampling: the resulting sampled signal is called a discrete signal (discrete time), and need not be quantized (it can have continuous values). To produce a digital signal (discrete time and discrete values), one both samples (discrete time) and quantizes the resulting sample values (discrete values).

[edit] Applications

A common use of quantization is in the conversion of a discrete signal (a sampled continuous signal) into a digital signal by quantizing. Both of these steps (sampling and quantizing) are performed in analog-to-digital converters with the quantization level specified in bits. A specific example would be compact disc (CD) audio which is sampled at 44,100 Hz and quantized with 16 bits (2 bytes) which can be one of 65,536 (i.e. $216$ ) possible values per sample.

In electronics, adaptive quantization is a quantization process that varies the step size based on the changes of the input signal, as a means of efficient compression. Two approaches commonly used are forward adaptive quantization and backward adaptive quantization.

[edit] Definition

In signal processing the quantization process is the necessary and natural follower of the sampling operation. It is necessary because in practice the digital computer with is general purpose CPU is used to implement DSP algorithms. And since computers can only process finite word length (finite resolution/precision) quantities, any infinite precision continuous valued signal should be quantized to fit a finite resolution, so that it can be represented (stored) in CPU registers and memory.

We shall be aware of the fact that, it is not the continuous values of the analog function that inhibits its binary encoding, rather it is the existence of infinitely many such values due to the definition of continuity,(which therefore requires infinitely many bits to represent). For example we can design a quantizer such that it represents a signal with a single bit (just two levels) such that, one level is "pi=3,14..." (say encoded with a 1) and the other level is "e=2.7183..." ( say encoded with a 0), as we can see, the quantized values of the signal take on infinite precision, irrational numbers. But there are only two levels. And we can represent the output of the quantizer with a binary symbol. Concluding from this we can see that it is not the discreteness of the quantized values that enable them to be encoded but the finiteness enabling the encoding with finite number of bits.

In theory there is no relation between quantization values and binary code words used to encode them (rather than a table that shows the corresponding mapping, just as examplified above). However due to practical reasons we may tend to use code words such that their binary mathematical values has a relation with the quantization levels that is encoded. And this last option merges the first two paragrahs in such a way that, if we wish to process the output of a quantizer within a DSP/CPU system (which is always the case) then we can not allow the representation levels of the quantizers to take on arbitrary values, but only a restricted range such that they can fit in computer registers.

A quantizer is identified with its number of levels M, the decision boundaries {di} and the corresponding representation values {ri}.

The output of a quantizer has two important properties: 1) a Distortion resulting from the approximation and 2) a Bit-Rate resulting from binary encoding of its levels. Therefore the Quantizer design problem is a Rate-Distortion optimization type.

If we are only allowed to use fixed length code for the output level encoding (the practical case) then the problem reduces into a distortion minimization one.

The design of a quantizer usually means the process to find the sets {di} and {ri} such that a measure of optimality is satisfied (such as MMSEQ (Minimum Mean Squarred Quantization Error))

Given the number of levels M, the optimal quantizer which minimizes the MSQE wrt the given signal statistics is called the Max-Lloyd quantizer, which is a non-uniform type in general.

The most common quantizer type is the uniform one. It is simple to design and implement and for most cases it suffices to get satisfactory results. Indeed by the very inherent nature of the design process, a given quantizer will only produce optimal results for the assumed signal statistics. Since it is very difficult to correctly predict that in advance, any static design will never produce actual optimal performance whenever the input statistics deviates from that of the design assumption. The only solution is to use an adaptive quantizer.

[edit] Mathematical description

Quantization is referred to as scalar quantization, since it operates on scalar (as opposed to multi-dimensional vector) input data. In general, a scalar quantization operator can be represented as

$Q(x) = g(\lfloor f(x) \rfloor)$

whereng an integer result $i = \lfloor f(x) \rfloor$ that is sometimes referred to as the quantization index,

$f (x)$ and $g (i)$ are arbitrary real-valued functions.

The integer-valued quantization index $i$ is the representation that is typically stored or transmitted, and then the final interpretation is constructed using $g (i)$ when the data is later interpreted.

In computer audio and most other applications, a method known as uniform quantization is the most common. There are two common variations of uniform quantization, called mid-rise and mid-tread uniform quantizers.

If $x$ is a real-valued number between -1 and 1, a mid-rise uniform quantization operator that uses M bits of precision to represent each quantization index can be expressed as

$Q(x) = \frac{\left\lfloor 2^{M-1}x \right\rfloor+0.5}{2^{M-1}}$ .

In this case the $f (x)$ and $g (i)$ operators are just multiplying scale factors (one multiplier being the inverse of the other) along with an offset in g(i) function to place the representation value in the middle of the input region for each quantization index. The value $2 - (M - 1)$ is often referred to as the quantization step size. Using this quantization law and assuming that quantization noise is approximately uniformly distributed over the quantization step size (an assumption typically accurate for rapidly varying $x$ or high $M$ ) and further assuming that the input signal $x$ to be quantized is approximately uniformly distributed over the entire interval from -1 to 1, the signal to noise ratio (SNR) of the quantization can be computed via the 20 log rule as

$\frac{S}{N_q} \approx 20 \log_{10}(2^M) = 6.0206 M \ \operatorname{dB}$ .

From this equation, it is often said that the SNR is approximately 6 dB per bit.

For mid-tread uniform quantization, the offset of 0.5 would be added within the floor function instead of outside of it.

Sometimes, mid-rise quantization is used without adding the offset of 0.5. This reduces the signal to noise ratio by approximately 6.02 dB, but may be acceptable for the sake of simplicity when the step size is small.

In digital telephony, two popular quantization schemes are the 'A-law' (dominant in Europe) and 'μ-law' (dominant in North America and Japan). These schemes map discrete analog values to an 8-bit scale that is nearly linear for small values and then increases logarithmically as amplitude grows. Because the human ear's perception of loudness is roughly logarithmic, this provides a higher signal to noise ratio over the range of audible sound intensities for a given number of bits.

[edit] Quantization and data compression

Quantization plays a major part in lossy data compression. In many cases, quantization can be viewed as the fundamental element that distinguishes lossy data compression from lossless data compression, and the use of quantization is nearly always motivated by the need to reduce the amount of data needed to represent a signal. In some compression schemes, like MP3 or Vorbis, compression is also achieved by selectively discarding some data, an action that can be analyzed as a quantization process (e.g., a vector quantization process) or can be considered a different kind of lossy process.

One example of a lossy compression scheme that uses quantization is JPEG image compression. During JPEG encoding, the data representing an image (typically 8-bits for each of three color components per pixel) is processed using a discrete cosine transform and is then quantized and entropy coded. By reducing the precision of the transformed values using quantization, the number of bits needed to represent the image can be reduced substantially. For example, images can often be represented with acceptable quality using JPEG at less than 3 bits per pixel (as opposed to the typical 24 bits per pixel needed prior to JPEG compression). Even the original representation using 24 bits per pixel requires quantization for its PCM sampling structure.

In modern compression technology, the entropy of the output of a quantizer matters more than the number of possible values of its output (the number of values being $2 M$ in the above example).

In order to determine how many bits are necessary to effect a given precision, algorithms are used. Suppose, for example, that it is necessary to record six significant digits, that is to say, millions. The number of values that can be expressed by N bits is equal to two to the Nth power. To express six decimal digits, the required number of bits is determined by rounding (6 / log 2)—where log refers to the base ten, or common, logarithm—up to the nearest integer. Since the logarithm of 2, base ten, is approximately 0.30102, the required number of bits is then given by (6 / 0.30102), or 19.932, rounded up to the nearest integer, viz., 20 bits.

This type of quantization—where a set of binary digits, e.g., an arithmetic register in a CPU, are used to represent a quantity—is called Vernier quantization. It is also possible, although rather less efficient, to rely upon equally spaced quantization levels. This is only practical when a small range of values is expected to be captured: for example, a set of eight possible values requires eight equally spaced quantization levels—which is not unreasonable, although obviously less efficient than a mere trio of binary digits (bits)—but a set of, say, sixty-four possible values, requiring sixty-four equally spaced quantization levels, can be expressed using only six bits, which is obviously far more efficient.

[edit] Relation to quantization in nature

At the most fundamental level, some physical quantities are quantized. This is a result of quantum mechanics (see Quantization (physics)). Signals may be treated as continuous for mathematical simplicity by considering the small quantizations as negligible.

In any practical application, this inherent quantization is irrelevant for two reasons. First, it is overshadowed by signal noise, the intrusion of extraneous phenomena present in the system upon the signal of interest. The second, which appears only in measurement applications, is the inaccuracy of instruments. Thus, although all physical signals are intrinsically quantized, the error introduced by modeling them as continuous is vanishingly small.

[edit] See also

[edit] External links

Quantization threads in Comp.DSP
Signal to quantization noise in quantized sinusoidal - Analysis of quantization error on a sine wave

Quantization (signal processing)

From Wikipedia, the free encyclopedia

Contents

[edit] Applications

[edit] Definition

[edit] Mathematical description

[edit] Quantization and data compression

[edit] Relation to quantization in nature

[edit] See also

[edit] External links

Views

Personal tools

Navigation

Search

Interaction

Toolbox

Languages