Asymptotically good codes have infinite trellis complexity

The trellis complexity s(C) of a block code C is defined as the logarithm of the maximum number of states in the minimal trellis realization of the code. The parameter s(C) governs the complexity of maximum-likelihood decoding, and is considered a fundamental descriptive characteristic of the code in a number of recent works. We derive a new lower bound on s(C) which implies that asymptotically good codes have infinite trellis complexity. More precisely, for i⩾1 let C_i be a code over an alphabet of size q, of length n_i, rate R_i, and minimum distance d_i. The infinite sequence of codes C_, C₂··· such that n_i→∞ when i→∞ is said to be asymptotically good if both R_i and d_i/n_i are bounded away from zero as i→∞. We prove that the complexity s(C_i) increases linearly with n_i in any asymptotically good sequence of codes