Lattice-based code
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\).
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*{(1)}\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*{(2)}\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\,dx}{\text{Vol}(\Pi)^{1+2/n}}\,. \tag*{(3)}\end{align} Higher-dimensional lattices yield quantizers with lower normalized second moments than the 1D integer lattice [2][3].
Rate
Notes
Parents
- Sphere packing
- Linear code over \(G\) — Lattice-based codes are linear codes over \(G=\mathbb{R}^n\).
Children
Cousins
- \(\mathbb{Z}^n\) hypercubic lattice code — 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 [15; 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.
- Best code — The Best code yields a dense sphere packing in 10 dimensions via Construction \(A\) [8].
- Lattice-shell code — Lattice-shell codes consists of lattice points that have been normalized.
- Gottesman-Kitaev-Preskill (GKP) code — GKP codes can be thought of as quantum lattice codes 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]
- R. Urbanke and B. Rimoldi, “Lattice codes can achieve capacity on the AWGN channel”, IEEE Transactions on Information Theory 44, 273 (1998) DOI
- [5]
- R. de Buda, “The upper error bound of a new near-optimal code”, IEEE Transactions on Information Theory 21, 441 (1975) DOI
- [6]
- 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
- [7]
- W. Kassem, Optimal Lattice Codes for the Gaussian Channel, Ph.D Thesis, McMaster Univ., Hamilton, Ontario, 1981
- [8]
- J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups (Springer New York, 1999) DOI
- [9]
- J. Talbot, editor , Sphere Packings (Springer New York, 1999) DOI
- [10]
- G. Nebe and N. J. A. Sloane. "Catalogue of Lattices." http://www.math.rwth-aachen.de/ Gabriele.Nebe/LATTICES/index.html
- [11]
- H. Cohn. "Kissing numbers." https://cohn.mit.edu/kissing-numbers
- [12]
- Cannon, J., Bosma, W., Fieker, C., & Steel, A. (2008). HANDBOOK OF MAGMA FUNCTIONS.
- [13]
- W. Bosma, J. Cannon, and G. Matthews, “Programming with algebraic structures”, Proceedings of the international symposium on Symbolic and algebraic computation - ISSAC ’94 (1994) DOI
- [14]
- W. BOSMA, J. CANNON, and C. PLAYOUST, “The Magma Algebra System I: The User Language”, Journal of Symbolic Computation 24, 235 (1997) DOI
- [15]
- T. Ericson, and V. Zinoviev, eds. Codes on Euclidean spheres. Elsevier, 2001.
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