The log-volume of optimal constant-composition codes for memoryless channels, within O(1) bits
Pierre Moulin · 2012
This paper derives a tight asymptotic upper bound on the maximum volume M*cc(n, ϵ) of length-n constant-composition codes subject to an average decoding error probability ϵ: Mbb(n, ϵ) = exp{nC - √nV Φ-(1 - ϵ) + 1/2 log n + An, ϵ+ o(1)} where Φ is the cdf of the standard normal distribution, and An, ϵis a bounded sequence that can be explicitly identified and reduces to a constant in the nonlattice case. A lower bound is presented, differing from the upper bound by an easily computable multiplying constant. These expressions hold under certain regularity assumptions on the channel.