Minimum entropy quantizers and permutation codes

Amplitude quantization and permutation encoding are two approaches to efficient digitization of analog data. It has been proven that they are equivalent in the sense that their optimum rate versus distortion performances are identical. Reviews of the aforementioned results and of work performed in the interim by several investigators are presented. Equations which must be satisfied by the thresholds of the minimum entropy quantizer that achieves a prescribed mean r th power distortion are derived, and an iterative procedure for solving them is developed. It is shown that these equations often have many families of solutions. In the case of the Laplacian distribution, for which we had previously shown that quantizers with uniformly spaced thresholds satisfy the equations when r=2 , other families of solutions with nonuniform spacing are exhibited. What had appeared to be a discrepancy between the performances of optimum permutation codes and minimum entropy quantizers is resolved by the resulting optimum quantizers, which span all entropy rates from zero to infinity.