Trellis complexity and minimal trellis diagrams of lattices
- 1 January 1998
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 44 (5) , 1829-1847
- https://doi.org/10.1109/18.705562
Abstract
This paper presents results on trellis complexity and low-complexity trellis diagrams of lattices. We establish constructive upper bounds on the trellis complexity of lattices. These bounds both improve and generalize the similar results of [35]. We also construct trellis diagrams with minimum number of paths for some important lattices. Such trellises are called minimal. The constructed trellises, which are novel in many cases, can be employed to efficiently decode the lattices via the Viterbi algorithm. In particular, a general structure for minimal trellis diagrams of D-n lattices is obtained, This structure corresponds to a new code formula for D-n. Moreover, we develop some important duality results which are used in both deriving the upper bounds, and finding the minimal trellises. All the discussions are based on a universal approach to the construction and analysis of trellis diagrams of lattices using their bases.Keywords
This publication has 30 references indexed in Scilit:
- Lattice codes can achieve capacity on the AWGN channelPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Upper bounds on trellis complexity of latticesIEEE Transactions on Information Theory, 1997
- Proof of a conjecture of McEliece regarding the expansion index of the minimal trellisIEEE Transactions on Information Theory, 1996
- Trellis complexity versus the coding gain of lattices. IIIEEE Transactions on Information Theory, 1996
- Trellis complexity versus the coding gain of lattices. IIEEE Transactions on Information Theory, 1996
- On lattice quantization noiseIEEE Transactions on Information Theory, 1996
- Some optimal codes have structureIEEE Journal on Selected Areas in Communications, 1989
- Integer and Combinatorial OptimizationPublished by Wiley ,1988
- A hierarchy of polynomial time lattice basis reduction algorithmsTheoretical Computer Science, 1987
- Efficient maximum likelihood decoding of linear block codes using a trellisIEEE Transactions on Information Theory, 1978