Quantization

Activity 1: Lloyd Max Quantization

Usually one assumes that the data to be quantized is distributed uniformly, which leads to the uniform quantizer, which has quantization levels spaces equally. However, if the data has a different distribution, Lloyd Max Quantization (LMQ) can be used to find an optimal scheme to minimize mean square error. Of course, performing LQM on uniform distribution gives us the usual uniform quantization.

Here we shall design a Lloyd Max quantization scheme for a truncated Gaussian distribution, whose equation is shown below.

LMQ can be performed with a sequence of iterations using the following equations:

The python code to perform LMQ is shown here:

import numpy as np, scipy.integrate as integrate

def prob(x): #truncated gaussian

    f = lambda x : np.exp(-0.5*x*x)

    return f(x)/integrate.quad(f, -5, 5)[0]

def LMQ(p, L, tmin, tmax, niters=100):

    get_t_from_r = lambda r : [tmin] + [(r[i]+r[i+1])/2.0 for i in range(L-1)] + [tmax]

    get_r_from_t = lambda t : [integrate.quad(lambda x : x*p(x), t[i], t[i+1])[0]/integrate.quad(p, t[i], t[i+1])[0] for i in range(L)]

    #uniform quantization initialization

    width = (tmax-tmin)/L

    r = [tmin+(i-0.5)*width for i in range(1,L+1)]

    t = get_t_from_r(r)

    for i in range(niters):

        r = get_r_from_t(t)

        t = get_t_from_r(r)

    return r,t

r,t = LMQ(prob, 10, -5, 5)

Activity 2: Comparing Uniform and Lloyd Max Quantization

Let us compare the mean square error for the truncated gaussian distributed data for Uniform quantization and Llyod Max quantization. We approximate the truncated gaussian (between -5 to 5) by a normal gaussian.

def mean_sq_err(r, s):

    return np.mean([min([abs(i - j)*abs(i - j) for j in r]) for i in s])

s = np.random.normal(0, 1, 1000)

print mean_sq_err(r_u, s); print mean_sq_err(r_l, s)

s = np.random.uniform(-5, 5, 1000)

print mean_sq_err(r_u, s); print mean_sq_err(r_l, s)

We randomly sample 1000 data points from normal distribution and find its MSE for uniform and LMQ. We do the same for uniformly sampled data. We get the following MSEs:

• Uniform data, uniform quantization: 0.08327
• Uniform data, LQM for Gaussian data: 1.3690
• Gaussian data, uniform quantization: 0.08189
• Gaussian data, LQM for Gaussian data: 0.01995

We observe that for uniform data under uniform quantization, the theoretical value of MSE is q*q/12, where q=A/L, where A = range of data and L is number of levels. For the current data (between -5 to 5) A=10. Given L=10, q=1. Therefore MSE = 1/12 = 0.08333. That is very close to the simulated value of 0.08327.