Lecture 4: Quantization Eytan Modiano AA Dept Eytan Modiano
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 Sample points What are the quantization regions What are the quantization levels Eytan Modiano
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 Q3 Q2 Q1 � � � � � � � � � � Sample points What are the quantization regions What are the quantization levels Eytan Modiano Slide 2
Uniform Quantizer 3△-2△-△ △ 3△ All quantization regions are of equal size(4 Except first and last regions if samples are not finite valued With n quantization regions, use log2(N)bits to represent each quantized value Eytan Modiano
∆ 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 log2(N) bits to represent each quantized value Eytan Modiano Slide 3
Quantization Error e(x=Q(x)-x Squared error: D= E[e(x ]=E[(Q(X)-x 1 SQNR:EⅨ2]/E(Q(x)-×)1] Eytan Modiano
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
Example x is uniformly distributed between-A and a f(x=1/2A,AΔ=2AN Q(x]=quantization level midpoint of quantization region in which x lies D= E[e(x) 2] is the same for quantization regions D=Ee(x)2|x∈ R=2x2(x)s4 12 EIX=I xdx A2/3A2/3 SON N2,(△=2A/N) △2/12(2N2/12 Eytan Modiano
∆ E X Example • X is uniformly distributed between -A and A – f(x) = 1/2A, -A ∆ = 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 D E e x 2 ∈ ∆ / 2 1 ∆ / 2 ∆2 = [( ) | x Ri] = ∫−∆ / 2 x2 f(x)dx = ∆ ∫−∆ / 2 x2 dx = 12 1 A 2 A2 [] = 2 A ∫− Ax dx = 3 A2 / 3 A2 / 3 SQNR= ∆2 /12 = (2 A N)2 /12 = N2 , (∆ = 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 qual Eytan Modiano
∆ 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 a 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 a 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
∆ ∆ 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
Uniform quantizer example N=4,X~N(O,1)f(x)= 2兀o ° From table62,△=0。957,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 -3△2 q2=△293=△2N q4=3△2 R1 R2R Eytan Modiano
∆ f x 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 − ∆ ∆ R1 R2 R3 R4 q1 = -3∆/2 q4 q = 3∆/2 2 =∆/2 q3 =∆/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; 1, a)) Minimize distortion
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 ( ai-1, ai)) – Minimize distortion Eytan Modiano Slide 9
Optimal quantization levels Minimize distortion D 对)f(x Optimal value affects distortion only within its region 220-8(8=0 xf(x a-1sx sa, )dx =EXa sosaI 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 Slide 10
Optimal quantization levels ai • Minimize distortion, D DR = ∫ ( x − x√ i) fx ( x ) dx ai−1 – Optimal value affects distortion only within its region − dDR = ∫ ai 2 (x x√ i)2 fx ( x ) dx = 0 dx√ ai−1 i ai x√ i = ∫ xfx (| ai−1 ≤ x ≤ ai x ) dx ai−1 [| ai−1 ≤ x ≤ ai – 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 10