An Exact Spectrum Formula for the Maximum Size of Finite Length Block Codes

Vincent Tan (National University of Singapore)

Abstract:
An exact information spectrum-type formula for the maximum size of finite length block codes subject to a minimum pairwise distance constraint is presented. This formula can be applied to codes for a broad class of distance measures. As revealed by the formula, the largest code size is fully characterized by the information spectrum of the distance between two independent and identically distributed (i.i.d.) random codewords drawn from an optimal distribution. A new family of lower bounds to the maximal code size is thus established, and the well-known Gilbert-Varshamov (GV) lower bound is a special case of this family. By duality, an explicit expression for the largest minimum distance of finite length block codes of a fixed code size is also obtained. Under an arbitrary uniformly bounded symmetric distance measure, the asymptotic largest code rate (in the block length n) attainable for a sequence of (n,M,n\delta)-codes is given exactly by the maximum large deviation rate function of the normalized distance between two i.i.d. random codewords. The exact information spectrum-type formula also yields bounds on the second-order terms in the asymptotic expansion of the optimum finite length rate for block codes with a fixed normalized minimum distance. This is joint work with Ling-Hua Chang, Carol Wang, Po-Ning Chen, and Yunghsiang S. Han and can be found at 1706.04709.