Description
Encodes states (codewords) in coordinates of an \(n\)-dimensional lattice, i.e., a discrete set of points in Euclidean space \(\mathbb{R}^n\) that forms a group under vector addition when the set is translated such that one point is at the origin. The number of codewords may be infinite because the coordinate space is infinite-dimensional, so various restricted versions have to be constructed in practice. Since lattices are closed under addition, lattice-based codes can be thought of as linear codes over the reals.
A \(n\)-dimensional lattice-based code can be defined using a generator matrix \(G\) of rank \(n\), where the rows of \(G\) are the lattice translation vectors \(g_i\). Any lattice point \(x\) is a linear combination of translation vectors with integer coefficients \(c_i\), \(x = c_1 g_1 + c_2 g_2 + \cdots + c_n g_n\). A lattice-based code can also be defined using the Gram matrix \(GG^T\).
The automorphism group of a lattice is the group of all isometries that preserve the origin and map the lattice into itself. This group is a subgroup of the orthogonal group \(O(n)\), which is the group of isometries in Euclidean space. An orthogonal matrix \(U\) leaves the lattice invariant if there exists an integer matrix \(A\) of determinant \(\pm 1\) such that \begin{align} \label{eq:lattice-auto} AG=GU~. \tag*{(1)}\end{align} The affine automorphism group is the group obtained from adding lattice translations to the automorphism group.
Two lattices with generator matrices \(G,G^{\prime}\) are equivalent if one be obtained from the another by the following combination of an orthogonal matrix \(U\) and a change of scale \(c\neq 0\), \begin{align} G^{\prime}=cAGU~, \tag*{(2)}\end{align} where \(A\) is an integer matrix \(A\) of determinant \(\pm 1\).
Protection
Lattices are characterized by the minimum (Euclidean) distance \(d_{\text{min}}\) between two lattice points, the kissing number \(K_{\text{min}}\) of nearest neighbors at each lattice point, and the volume \(V=\det G\), which is the volume of the lattice's fundamental region that can be used to tile all of \(\mathbb{R}^n\).
The minimum Euclidean distance is an analogue of the minimum distance of binary codes. Half of this distance is called the packing radius.
The nominal coding gain \(\gamma_{c}\) (a.k.a. Hermite parameter) of an \(n\)-dimensional lattice is \begin{align} \gamma_{c}=\left(d_{\text{min}}/\sqrt[n]{V}\right)^{2}~, \tag*{(3)}\end{align} characterizing the ratio of the level of protection to the required spatial resources. The density of a lattice is the fraction of the total volume of space that is occupied by spheres of packing radius \(\frac{1}{2}d_{\text{min}}\) centered at each point in the lattice, \begin{align} \Delta=\frac{\text{volume of one sphere}}{\sqrt{V}}~. \tag*{(4)}\end{align}
The covering radius of a lattice is defined similarly as above, but with the spheres' covering radius now being the smallest one such that the spheres cover all space. In general, finding the covering radius of lattice is \(NP\)-hard [1].
The lattice quantizer problem is to find a lattice whose fundamental Voronoi cell \(\Pi\), the Voronoi cell at the origin, has the smallest possible normalized second moment, \begin{align} G(\Pi)=\frac{\frac{1}{n}\int_{\Pi}x\cdot x\,\textnormal{d}x}{\text{Vol}(\Pi)^{1+2/n}}\,. \tag*{(5)}\end{align} Higher-dimensional lattices yield quantizers with lower normalized second moments than the 1D integer lattice [2,3].
The shortest vector problem (SVP) asks for the shortest nonzero vector in a given lattice and is related to cryptographic protocols. Solving SVP up to an error independent of lattice dimension is NP-complete [4,5]. The Lenstra-Lenstra-Lovasz (LLL) algorithm solves SVP in polynomial time, but up to an error exponential in the dimension [6]; see the book [7].
Rate
Decoding
Notes
Parents
- Sphere packing
- Linear code over \(G\) — Lattice-based codes are linear codes over \(G=\mathbb{R}^n\). Because any orthogonal matrix leaving the lattice invariant has a corresponding integer matrix (see lattice code description), integer representations of groups can be used to obtain lattices [14; Ch. 3, Sec. 4.2].
Children
Cousins
- \(\mathbb{Z}^n\) hypercubic lattice — The generator matrix of a lattice-based code serves as a linear transformation that can be applied to the hypercubic lattice to obtain said code [22; Ch. 10].
- Quadrature-amplitude modulation (QAM) code — QAM encodings often consist of lattice constellations, i.e., finite sets of points scooped out of an infinite 2D lattice.
- Lexicographic code — Lexicographic codes are \(q\)-ary analogues of laminated lattices [24][23; pg. 162].
- Lattice-shell code — Lattice-shell codes consists of lattice points that have been normalized.
- Quantum lattice code — Quantum lattice codes can be thought of as quantum analogues of lattices because they store information in quantum superpositions of points on a lattice in quantum phase space.
References
- [1]
- van Emde, Boas P. "Another NP-complete partition problem and the complexity of computing short vectors in lattices." TR (1981).
- [2]
- P. L. Zador, Development and evaluation of procedures for quantiZing multivariate distributions, Ph.D. Dissertation, Stanford Univ., 1963
- [3]
- P. Zador, “Asymptotic quantization error of continuous signals and the quantization dimension”, IEEE Transactions on Information Theory 28, 139 (1982) DOI
- [4]
- van Emde Boas, P. (1981). Another NP-complete problem and the complexity of computing short vectors in a lattice. Tecnical Report, Department of Mathmatics, University of Amsterdam.
- [5]
- D. Micciancio, “The Shortest Vector in a Lattice is Hard to Approximate to within Some Constant”, SIAM Journal on Computing 30, 2008 (2001) DOI
- [6]
- A. K. Lenstra, H. W. Lenstra Jr., and L. Lovász, “Factoring polynomials with rational coefficients”, Mathematische Annalen 261, 515 (1982) DOI
- [7]
- An Introduction to Mathematical Cryptography (Springer New York, 2008) DOI
- [8]
- R. Urbanke and B. Rimoldi, “Lattice codes can achieve capacity on the AWGN channel”, IEEE Transactions on Information Theory 44, 273 (1998) DOI
- [9]
- R. de Buda, “The upper error bound of a new near-optimal code”, IEEE Transactions on Information Theory 21, 441 (1975) DOI
- [10]
- R. de Budaand W. Kassem, About lattices and the random coding theorem, in Abstracts of Papers, IEEE Inter. Symp. Info. Theory 1981, IEEE Press, NY 1981, p. 145
- [11]
- W. Kassem, Optimal Lattice Codes for the Gaussian Channel, Ph.D Thesis, McMaster Univ., Hamilton, Ontario, 1981,doi:10.1109/18.651040
- [12]
- U. Fincke and M. Pohst, “Improved methods for calculating vectors of short length in a lattice, including a complexity analysis”, Mathematics of Computation 44, 463 (1985) DOI
- [13]
- C. P. Schnorr and M. Euchner, “Lattice basis reduction: Improved practical algorithms and solving subset sum problems”, Mathematical Programming 66, 181 (1994) DOI
- [14]
- J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups (Springer New York, 1999) DOI
- [15]
- J. Talbot, editor , Sphere Packings (Springer New York, 1999) DOI
- [16]
- The LMFDB Collaboration, The L-functions and modular forms database, https://www.lmfdb.org, 2024.
- [17]
- G. Nebe and N. J. A. Sloane. "Catalogue of Lattices." https://www.math.rwth-aachen.de/ Gabriele.Nebe/LATTICES/index.html
- [18]
- H. Cohn. "Kissing numbers." https://cohn.mit.edu/kissing-numbers
- [19]
- Cannon, J., Bosma, W., Fieker, C., & Steel, A. (2008). HANDBOOK OF MAGMA FUNCTIONS.
- [20]
- W. Bosma, J. Cannon, and G. Matthews, “Programming with algebraic structures”, Proceedings of the international symposium on Symbolic and algebraic computation - ISSAC ’94 52 (1994) DOI
- [21]
- W. BOSMA, J. CANNON, and C. PLAYOUST, “The Magma Algebra System I: The User Language”, Journal of Symbolic Computation 24, 235 (1997) DOI
- [22]
- T. Ericson, and V. Zinoviev, eds. Codes on Euclidean spheres. Elsevier, 2001.
- [23]
- F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier, 1977.
- [24]
- G. Hoehn, “Self-dual Codes over the Kleinian Four Group”, (2000) arXiv:math/0005266
Page edit log
- Victor V. Albert (2022-11-02) — most recent
- Victor V. Albert (2022-02-16)
Cite as:
“Lattice-based code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/points_into_lattices