Optimal permutation codes for uniform sources

Permutation codes are vector quantizers whose code vectors are related by permutations and, in one variant, sign changes. Asymptotically, as the vector dimension grows, optimal permutation code design is identical to optimal entropy-constrained scalar quantizer (ECSQ) design. However, contradicting intuition and previously published assertions, 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. Specific counterexamples are created with a memoryless uniform source