Lattice-based code


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\).


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].


Lattice codes with minimal-distance decoding achieve the capacity of the AGWN channel [4][5][6][7].


See books [8][9] for introductions and overviews of lattices.See Catalogue of Lattices [10] for more information.Tables of bounds on kissing numbers [11].See Refs. [12][13][14] for various examples and implementations in Magma.





van Emde, Boas P. "Another NP-complete partition problem and the complexity of computing short vectors in lattices." TR (1981).
P. L. Zador, Development and evaluation of procedures for quantiZing multivariate distributions, Ph.D. Dissertation, Stanford Univ., 1963
P. Zador, “Asymptotic quantization error of continuous signals and the quantization dimension”, IEEE Transactions on Information Theory 28, 139 (1982) DOI
R. Urbanke and B. Rimoldi, “Lattice codes can achieve capacity on the AWGN channel”, IEEE Transactions on Information Theory 44, 273 (1998) DOI
R. de Buda, “The upper error bound of a new near-optimal code”, IEEE Transactions on Information Theory 21, 441 (1975) DOI
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
W. Kassem, Optimal Lattice Codes for the Gaussian Channel, Ph.D Thesis, McMaster Univ., Hamilton, Ontario, 1981
J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups (Springer New York, 1999) DOI
J. Talbot, editor , Sphere Packings (Springer New York, 1999) DOI
G. Nebe and N. J. A. Sloane. "Catalogue of Lattices." Gabriele.Nebe/LATTICES/index.html
H. Cohn. "Kissing numbers."
Cannon, J., Bosma, W., Fieker, C., & Steel, A. (2008). HANDBOOK OF MAGMA FUNCTIONS.
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
W. BOSMA, J. CANNON, and C. PLAYOUST, “The Magma Algebra System I: The User Language”, Journal of Symbolic Computation 24, 235 (1997) DOI
T. Ericson, and V. Zinoviev, eds. Codes on Euclidean spheres. Elsevier, 2001.
Page edit log

Your contribution is welcome!

on (edit & pull request)

edit on this site

Zoo Code ID: points_into_lattices

Cite as:
“Lattice-based code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022.
@incollection{eczoo_points_into_lattices, title={Lattice-based code}, booktitle={The Error Correction Zoo}, year={2022}, editor={Albert, Victor V. and Faist, Philippe}, url={} }
Share via:
Twitter | Mastodon |  | E-mail
Permanent link:

Cite as:

“Lattice-based code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022.