Name
Abstract | ||
|---|---|---|
Upper and lower bounds are derived for the decoding complexity of a general lattice L. The bounds are in terms of the dimension n and the coding gain γ of L, and are obtained based on a decoding algorithm which is an improved version of Kannan's (1983) method. The latter is currently the fastest known method for the decoding of a general lattice. For the decoding of a point x, the proposed algorithm recursively searches inside an, n-dimensional rectangular parallelepiped (cube), centered at x, with its edges along the Gram-Schmidt vectors of a proper basis of L. We call algorithms of this type recursive cube search (RCS) algorithms. It is shown that Kannan's algorithm also belongs to this category. The complexity of RCS algorithms is measured in terms of the number of lattice points that need to be examined before a decision is made. To tighten the upper bound on the complexity, we select a lattice basis which is reduced in the sense of Korkin-Zolotarev (1873). It is shown that for any selected basis, the decoding complexity (using RCS algorithms) of any sequence of lattices with possible application in communications (γ⩾1) grows at least exponentially with n and γ. It is observed that the densest lattices, and almost all of the lattices used in communications, e.g., Barnes-Wall lattices and the Leech lattice, have equal successive minima (ESM). For the decoding complexity of ESM lattices, a tighter upper bound and a stronger lower bound result are derived |
Year | DOI | Venue |
|---|---|---|
1998 | 10.1109/18.651011 | IEEE Transactions on Information Theory |
Keywords | Field | DocType |
lattices,esm lattice,decoding complexity,lattice basis,leech lattice,densest lattices,rcs algorithm,decoding algorithm,successive minima.,decoding lattice,korkin-zolotarev reduction,densest lattice,decoding algorithms,index terms— coding gain,decoding com- plexity,lattice point,general lattice,barnes-wall lattice,upper bound,coding gain,cube,linear programming,computational complexity,geometry,indexing terms,viterbi algorithm,upper and lower bounds,information technology,lattice points,communications,decoding,dimension,lower bound,vector quantization | Discrete mathematics,Combinatorics,Sequential decoding,Lattice (order),Upper and lower bounds,Leech lattice,Lattice (group),Decoding methods,List decoding,Mathematics,Computational complexity theory | Journal |
Volume | Issue | ISSN |
44 | 1 | 0018-9448 |
Citations | PageRank | References |
33 | 4.38 | 18 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| A. H. Banihashemi | 1 | 336 | 29.01 |
| A. K. Khandani | 2 | 297 | 19.65 |