Asymptotically good codes have infinite trellis complexity
- 1 March 1995
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 41 (2) , 555-559
- https://doi.org/10.1109/18.370171
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⩾1 let Ci be a code over an alphabet of size q, of length ni, rate Ri, and minimum distance di. The infinite sequence of codes C, C2··· such that ni→∞ when i→∞ is said to be asymptotically good if both Ri and di/ni are bounded away from zero as i→∞. We prove that the complexity s(Ci) increases linearly with ni in any asymptotically good sequence of codesKeywords
This publication has 14 references indexed in Scilit:
- On the trellis structure of block codesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- The Viterbi decoding complexity of linear block codesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Maximum-likelihood soft decision decoding of BCH codesIEEE Transactions on Information Theory, 1994
- Dimension/length profiles and trellis complexity of linear block codesIEEE Transactions on Information Theory, 1994
- The dynamics of group codes: state spaces, trellis diagrams, and canonical encodersIEEE Transactions on Information Theory, 1993
- Coset codes. II. Binary lattices and related codesIEEE Transactions on Information Theory, 1988
- Minimal trellises for block codesIEEE Transactions on Information Theory, 1988
- New upper bounds on the rate of a code via the Delsarte-MacWilliams inequalitiesIEEE Transactions on Information Theory, 1977
- Class of constructive asymptotically good algebraic codesIEEE Transactions on Information Theory, 1972
- Long BCH codes are badInformation and Control, 1967