Asymptotically good codes have infinite trellis complexity

Abstract

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.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>

Keywords

Affiliated Institutions

• University of Illinois Urbana-Champaign US

Related Publications