Rule 2: Centroid Rule Given a cell R, the best codeword yi for that cell is the average value of all the x's in the cell; i.e., the best codeword yi is the centroid of the cell R. Mathematically, y,=Exxerj (4.39) (4.40) [x px (x)ds (4.41) We'll now use these two rules to come up with an algorithm for building the best quantizer. Basically, the first rule says: "given the codewords { y1 yn }, I tell you how to get the best cells { R1 RN }". The second rule says: "If you give me the cells { R1 ,..., RN }, then I tell you how to get the best codewords{y1,...,Y}. And I say: "Hey, if I put these two rules together, I'll get an iterative algorithm that will allow me to come up with both the best {y1,... YN and the best { (R1,...,1 RN }." It'll work like this: Algorithm for Building the Best Quantizer: Generalized Lloyd Algorithm: 1. a. Set m = 1. b. Choose some initial codebook ym yn Oftentimes a good starting choice is a uniformly (evenly) spaced set of N values. 2. Given the codewords {ym,..., ym compute the best cells using Rule 1, the Nearest Neighbor rule. 3. Given the cells RN }, compute a new set of codewords labeled by using Rule 2, the Centroid rule. 4. a. Compute the mse for the quantizer with codewords b. Compute the mse for the quantizer with the c. If the percent change in the mse is below some small number (e.g. 1%) then STOP; otherwise, replace the value of m by m+1 and return to step 2. Chapter Four Essentially, this algorithm iterates (repeats) Rule 2 to get cells and Rule 1 to get codewords; eventually, the algorithm stops when the codewords and the cells together create such a low mse that even if we update them further the mse really doesn't improve much. It's worth noting from a mathematical standpoint that this algorithm does not, in general, guarantee the very best choice of codewords and cells, but it usually works SO darn well that almost every telecommunications engineer uses it to build their quantizer. The Second Method: Squeezing and Stretching The second method for creating the best quanti