On Optimal Permutation Codes

Permutation codes are vector quantizers whose codevectors are all related by permutations and, in one variant, sign changes. Those with large block sizes are closely related to entropy-constrained scalar quantizers (ECSQ's). Asymptotically, the optimization problem for permutation codes is identical to the one for optimal ECSQ design. However, as demonstrated in this paper, some key previous assertions about permutation codes are false. Surprisingly, there are finite block length permutation codes that perform better than the best ones with asymptotically large length; thus, there are permutation codes whose performances cannot be matched by ECSQ's. Along similar lines, a new asymptotic relation between Variant I and Variant II codes is established but again demonstrated to not predict the performances of short codes for some sources.