Scalar quantization

A source generates an element from the set {0,1,2,3} with uniform probability. The source encoder needs to describe the source to the decoder, but is allowed to use only a single bit . The decoder's task is to reconstruct the source as the symbol (which must also be in the set {0.1.2.3}) while minimizing the expected distortion. The distortion between two symbols here is defined as the mean-squared error (MSE) between and . Propose a scheme with a distortion that is as small as possible.

We can just  encode both 0 and 1 to '0' and both 2 and 3 to '1', and decode '0' as 0 and '1' as 2, thus the expected distortion computed by expected MSE is

Vector quantization

Now, suppose the source generates two elements i.i.d. from the same source. The encoder encodes this as two bits , and the decoder decodes these as . Propose a scheme with an MSE distortion that is as small as possible.

Since  is drawn from {0,1,2,3}, we can denote 16 different symbols as shown in the image below, with the first bit for  and the last bit for , and we have divided the 16 different symbols into four different groups, with one representitive (13, 32, 01, 20) for each group. We call the different groups different assignment rigions/Voronoi Cells, and the different representitives different reproduction points.