On optimal permutation codes

Permutation codes are vector quantizers whose codewords are related by perm utations and, in one variant, sign changes. Asymptotically, as the vector d imension grows, optimal Variant I permutation code design is identical to o ptimal entropy-constrained scalar quantizer (ECSQ) design. However, contrad icting intuition and previously published assertions, there are finite bloc k length permutation codes that perform better than the best ones with asym ptotically large length; thus, there are Variant I permutation codes whose performances cannot be matched by any ECSQ. Along similar lines, a new asym ptotic relation between Variant I and Variant II permutation codes is estab lished but again demonstrated to not necessarily predict the performances o f short codes. Simple expressions for permutation code performance are foun d for memoryless uniform and Laplacian sources. The uniform source yields t he aforementioned counterexamples.