Asymptotically good codes have infinite trellis complexity
A. Lafourcade, Alexander Vardy · IEEE Transactions on Information Theory · 1995
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/spl ges/1 let C/sub i/ be a code over an alphabet of size q, of length n/sub i/, rate R/sub i/, and minimum distance d/sub i/. The infinite sequence of codes C/sub ,/ C/sub 2spl middotspl middotspl middot/ such that n/sub ispl rarrspl infin/ when i/spl rarrspl infin/ is said to be asymptotically good if both R/sub i/ and d/sub in/sub i/ are bounded away from zero as i/spl rarrspl infin/. We prove that the complexity s(C/sub i/) increases linearly with n/sub i/ in any asymptotically good sequence of codes.>