Converse bounds for assorted codes in the finite blocklength regime
Yanina Y. Shkel, Vincent Y. F. Tan, Stark C. Draper · 2013
We study converse bounds for unequal error protection codebooks with k > 1 different classes of codewords. We dub these unequal error protection codes “assorted codes”. We extend a finite blocklength converse bound due to Polyanskiy-Poor-Verdú to apply to assorted codes and use this extension to obtain a refined asymptotic expansion for the performance of assorted codes over a discrete memoryless channel. Our main contribution is to demonstrate that there is indeed a loss in the rates of an assorted code compared to equivalent homogeneous (classical) codes. Notably, when the number of codeword classes is polynomial in blocklength n the loss is apparent in the third order O(log n) term of the asymptotic expansion of the logarithm of the maximum number of codewords. This is in sharp contrast to the previous literature which only considers this problem within regimes where no such loss could be observed.