Lecture 4: Quantization Eytan Modiano AA Dept. Eytan Modiano Slide 1 Sampling ? Sampling provides a discrete-time representation of a continuous waveform – Sample points are real-valued numbers – In order to transmit over a digital system we must first convert into discrete valued numbers Quantization levels Q 3 Q 2 Q 1 ? ? ? ? ? ? ? ? ? ? Sample points What are the quantization regions What are the quantization levels Eytan Modiano Slide 2 ??? Uniform Quantizer ? ? 3 ? ?3? ?2? ?? ? 2 ? All quantization regions are of equal size ( ? ) – Except first and last regions if samples are not finite valued ? With N quantization regions, use log 2 (N) bits to represent each quantized value Eytan Modiano Slide 3 Quantization Error e(x) = Q(x) - x Squared error: D = E[e(x) 2 ] = E[(Q(x)-x) 2 ] SQNR: E[X 2 ]/E[(Q(x)-x) 2 ] Eytan Modiano Slide 4 ??? EX Example ? X is uniformly distributed between -A and A – f(x) = 1/2A, -A<=x<=A and 0 otherwise ? Uniform quantizer with N levels => ? = 2A/N – Q(x) = quantization level = midpoint of quantization region in which x lies ? D = E[e(x) 2 ] is the same for quantization regions DE e x 2 ∈ ? / 2 1 ? / 2 ? 2 = [( ) | xR i ] = ∫ ? ? / 2 x 2 f ( x ) d x = ? ∫ ? ? / 2 x 2 d x = 12 1 A 2 A 2 [] = 2 A ∫ ? A xd x = 3 A 2 / 3 A 2 / 3 SQNR = ? 2 / 12 = ( 2 AN ) 2 / 1 2 = N 2 ,( ? = 2 A / N ) / Eytan Modiano Slide 5 ??? Quantizer design ? Uniform quantizer is good when input is uniformly distributed ? When input is not uniformly distributed – Non-uniform quantization regions Finer regions around more likely values – Optimal quantization values not necessarily the region midpoints ? Approaches – Use uniform quantizer anyway Optimal choice of ? – Use non-uniform quantizer Choice of quantization regions and values – Transform signal into one that looks uniform and use uniform quantizer Eytan Modiano Slide 6 ??? ??? Optimal uniform quantizer ? Given the number of regions, N – Find the optimal value of ? – Find the optimal quantization values within each region – Optimization over N+2 variables ? Simplification: Let quantization levels be the midpoint of the quantization regions (except first and last regions, when input not finite valued) ? Solve for ? to minimize distortion – Solution depends on input pdf and can be done numerically for commonly used pdfs (e.g., Gaussian pdf , table 6.2, p. 296 of text) Eytan Modiano Slide 7 ??? fx Uniform quantizer example ? N=4, X~N(0,1) x () = 2 πσ 1 e ? x 2 / 2 σ 2 , σ 2 = 1 ? From table 6.2, ? =0.9957, D=0.1188, H(Q)= 1.904 – Notice that H(Q) = the entropy of the quantized source is < 2 – Two bits can be used to represent 4 ? quantization levels – Soon we will learn that you only need H(Q) bits ? ? ? R 1 R 2 R 3 R 4 q 1 = -3 ? /2 q 4 = 3 ? /2 q 2 = ? /2 q 3 = ? /2 Eytan Modiano Slide 8 Non-uniform quantizer ? Quantization regions need not be of same length ? Quantization levels need not be at midpoints ? Complex optimization over 2N variables ? Approach: – Given quantization regions, what should the quantization levels be? – What should the quantization regions be? ? Solve for quantization levels first (given region ( a i-1 , a i )) – Minimize distortion Eytan Modiano Slide 9 Optimal quantization levels a i ? Minimize distortion, D D R = ∫ ( x ? x √ i ) f x ( x ) d x a i ? 1 – Optimal value affects distortion ? only within its region dD R = ∫ a i 2 ( xx √ i ) 2 f x ( x ) d x = 0 dx √ a i ? 1 i a i x √ i = ∫ x f x (| a i ? 1 ≤ x ≤ a i ) d x x a i ? 1 [| a i ? 1 ≤ x ≤ a i ] – x √ i = E X ? Quantization values should be the “ centroid ” of their regions – The conditional expected value of that region ? Approach can be used to find optimal quantization values for the uniform quantizer as well Eytan Modiano Slide 1 0 Optimal quantization regions ? Take derivative of D with respect to a i – Take derivative with respect to integral boundaries 2 dD = fa i )[( a i ? x √ i ) 2 ? ( a i ? x √ i + 1 )] = 0 x ( da i √√ x x i + i + 1 a i = 2 – Boundaries of the quantization regions are the midpoint of the quantization values ? Optimality conditions: 1. Quantization values are the “ centroid ” of their region 2. Boundaries of the quantization regions are the midpoint of the quantization values 3. Clearly 1 depends on 2 and visa-versa. The two can be solved iteratively to obtain optimal quantizer Eytan Modiano Slide 1 1 ??? Finding the optimal quantizer ? Start with arbitrary regions (e.g., uniform ? ) A) Find optimal quantization values (“ centroids ” ) B) Use quantization values to get new regions ( “ midpoints ”) – Repeat A & B until convergence is achieved ? Can be done numerically for known distributions – Table 6.3 (p. 299) gives optimal quantizer for Gaussian source ? E.g., N=4, – D = 0.1175, H(x) = 1.911 – Recall: uniform quantizer , D= 0.1188, H(x) = 1.904 (slight improvement) 0.9816 1.51 0.4528 -0.9816 -0.4528 Eytan Modiano Slide 1 2 - 1.51 μμμ μμμμμμ gx Companders ? Non-uniform quantizer can be difficult to design – Requires knowledge of source statistics – Different quantizers for different input types ? Solution: Transfer input signal into one that looks uniform and then use uniform quantizer ? μ -law compander () = Log ( 1 + μ | x | ) sgn( x ) Log ( 1 + μ ) – μ controls the level of compression – μ = 255 typically used for voice Eytan Modiano Slide 1 3 ∈∈∈ ×× Pulse code modulation voice Quantizer μ -law Uniform Q Sampler encoder 011010 ? Uniform PCM: x(t) ∈ [Xmin , Xmax ] – N = 2 V quantization levels, each level encoded using v bits – SQNR: same as uniform quantizer v EX 2 SQNR = [] 2 34 X MAX – Notice that increasing the number of bits by 1 decreases SQNR by a factor of 4 (6 dB) Eytan Modiano Slide 1 4 μμμ μμμ Speech coding ? PCM with μ = 255 ? Uniform quantizer with 128 levels, N = 2 7 , 7 bits per sample ? Speech typically limited to 4KHZ – Sample at 8KHZ => Ts = 1/8000 = 125 μ s 8000 samples per second at 7 bits per sample => 56 Kbps ? Differential PCM – Speech samples are typically correlated – Instead of coding samples independently, code the difference between samples – Result: improved performance, lower bit rate speech Eytan Modiano Slide 1 5