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 Tarokh and Vardy (see ibid., vol.43, p.1294-1300, 1997). 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 Dn lattices is obtained. This structure corresponds to a new code formula for Dn. 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 |
Year | DOI | Venue |
---|---|---|
1998 | 10.1109/18.705562 | IEEE Transactions on Information Theory |
Keywords | Field | DocType |
general structure,important lattice,trellis complexity,minimal trellis diagram,constructive upper bound,minimal trellis,trellis diagram,dn lattice,important duality result,low-complexity trellis diagram,lattices,block codes,indexing terms,diagrams,upper bound,computational complexity,decoding,information theory,viterbi decoding,encoding,coding,convolutional codes,viterbi algorithm | Discrete mathematics,Combinatorics,Lattice (order),Computer science,Constructive,Viterbi decoder,Duality (optimization),Viterbi algorithm,Encoding (memory),Computational complexity theory | Journal |
Volume | Issue | ISSN |
44 | 5 | 0018-9448 |
Citations | PageRank | References |
13 | 1.97 | 28 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
A. H. Banihashemi | 1 | 336 | 29.01 |
I. F. Blake | 2 | 164 | 29.09 |