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

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.

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*{(2)}\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*{(3)}\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*{(4)}\end{align} Higher-dimensional lattices yield quantizers with lower normalized second moments than the 1D integer lattice [2,3].

Rate

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

Notes

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–14] for various examples and implementations in Magma.

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 [8; Ch. 3, Sec. 4.2].

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.
  • 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 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,doi:10.1109/18.651040
[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

Your contribution is welcome!

on github.com (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. https://errorcorrectionzoo.org/c/points_into_lattices
BibTeX:
@incollection{eczoo_points_into_lattices,
  title={Lattice-based code},
  booktitle={The Error Correction Zoo},
  year={2022},
  editor={Albert, Victor V. and Faist, Philippe},
  url={https://errorcorrectionzoo.org/c/points_into_lattices}
}
Share via:
Twitter | Mastodon |  | E-mail
Permanent link:
https://errorcorrectionzoo.org/c/points_into_lattices

Cite as:

“Lattice-based code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/points_into_lattices

Github: https://github.com/errorcorrectionzoo/eczoo_data/tree/main/codes/classical/analog/lattice/points_into_lattices.yml.