# Sphere packing

## Description

Encodes states (codewords) into coordinates in the \(n\)-dimensional real coordinate space \(\mathbb{R}^n\). The number of codewords may be infinite because the coordinate space is infinite, so various restricted versions have to be constructed in practice.

Sphere packings provide ways of encoding digital or analog information into the frequency, amplitude, and phase of one or more analog waveforms for transmission through, e.g., an optical fiber or free space. This is due to Kotelnikov's [1] and Shannon's [2] fundamental observation that a discretized electromagnetic signal of finite bandwidth and average power \(P\) can be represented as a vector in \(\mathbb{R}^n\) with norm \(nP\). Questions of capacity of electromagnetic communication channels then translate to packing problems in \(\mathbb{R}^n\) [3].

In the electromagnetic context, the information stored in the code is called the bitstream, coordinates used for encoding are often called signal points and form a constellation, and \(\mathbb{R}^n\) is called the signal space.

## Protection

Sphere packings can be used to transmist information using electromagnetic signals. The primary noise channel for such signals is the additive Gaussian white-noise channel (AGWN), which adds a random Gaussian-distributed displacement with variance \(\sigma^2\) to each signal point. Protection of a constellation thus depends on how far apart its points are in terms of the Euclidean distance. As usual, there is a tradeoff between packing of space and level of protection. For a given \(n,M,P\), the Gaussian channel coding problem asks to find a set of \(M\) codewords of norm \(\leq nP\) that minimizes the error probability during transmission; see [3; Ch. 3].

The minimum distance \(d\) of a constellation is the infimum over distances between any two of it''s points. The density \(\Delta\) is the fraction of the total volume of space that is occupied by spheres of an optimal radius centered at each point in the sphere packing. Defining a density for infinite constellations can be done using a limit [4; pg. 349].

The Kabatiansky-Levenshtein bound [5] says that any sphere packing must satistfy \(\frac{1}{n}\log_{2}\Delta\lesssim-0.5990\) asymptotically with dimension \(n\). Other bounds include the Rogers bound [6]. For more details, see [4; Ch. 10.4][3; Ch. 1].

The covering problem asks how one can cover all of space by overlapping spheres in the most efficient way. The thickness \(\Theta\) (a.k.a. covering density or sparsity) of a covering is defined in the same way as the (packing) density, but with the spheres' covering radius now being the smallest one such that the spheres cover all space.

There is an upper bound on the thickness of a covering in dimensions \(n>3\) [7] as well as an asymptotic lower bound [8], \begin{align} \frac{n}{e\sqrt{e}}\lesssim\Theta\leq n\ln n+n\ln\ln n+5n~. \tag*{(1)}\end{align}

Sphere packings can be used as quantizers or analog-to-digital converters, which perform data compression by rounding a vector of real numbers to the point in the packing that is closest to the vector. The set of all points closest to a point \(x\) is called the Voronoi cell of \(x\). The quantizer problem asks to find a sphere packing that yields that minimizes a dimensionless dimension-dependent quantity proportional to the average mean squared error per dimension; see [3; Sec. 3.2]. For dimension \(n\), this minimum is known as \(G_n\). It is known only for \(n=1,2\) and is attained by the integer and hexagonal lattices, respectively.

## Rate

The rate of a code consisting of \(M\) codewords that represent a signal of bandwidth \(W\) and duration \(T\) is defined as \begin{align} R=\frac{1}{T}\log_{2}M\quad\quad\text{bits/s}~. \tag*{(2)}\end{align}

The Shannon capacity of the AGWN channel for a signal whose power is \(P\) is \begin{align} C=W\log_{2}\left(1+\frac{P}{\sigma^{2}}\right)\,. \tag*{(3)}\end{align} Random sphere packings achieve this capacity [9]; see the book [3] for more details. Tradeoffs between various parameters have been analyzed [10]. Deterministic sets of constellations from quadrature rules can also achieve capacity [11].

## Decoding

## Notes

## Parents

- Block code
- Group-alphabet code — Sphere-packing alphabets \(\mathbb{R}^n\) are infinite fields, which are groups under addition.

## Children

- Construction-\(A\) code
- Lattice-based code
- Modulation scheme
- Universally optimal sphere packing
- Constant-energy code — Constant-energy codes are sphere packings constrained to lie on a sphere.

## Cousins

- Best \((10,40,4)\) code — Using Construction \(A\), the Best code yields \(P_{10c}\), a non-lattice sphere packing in 10 dimensions that is the densest known [13][3; pg. 140].
- Julin-Golay code — Using Construction \(A\), the Julin-Golay codes yield non-lattice sphere-packings that hold records in 9 and 11 dimensions.
- Bosonic c-q code — Bosonic c-q codes are extensions of sphere packings to transmission of classical information over quantum analog channels.
- Coherent-state constellation code — Coherent-state constellation codes are quantum versions of sphere packings in that their codewords are superpositions of points in a constellation. Additionally, analog codes that achieve AGWN capacity [11] can be used to develop capacity-achieving concatenations of coherent-state constellation codes with quantum polar codes [14][15].

## References

- [1]
- V. A. Kotelnikov, “The theory of optimum noise immunity,” PhD Thesis, Molotov Energy Institute, Moscow, Jan. 1947
- [2]
- C. E. Shannon, “Communication in the Presence of Noise”, Proceedings of the IRE 37, 10 (1949) DOI
- [3]
- J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups (Springer New York, 1999) DOI
- [4]
- T. Ericson, and V. Zinoviev, eds. Codes on Euclidean spheres. Elsevier, 2001.
- [5]
- G. A. Kabatiansky, V. I. Levenshtein, “On Bounds for Packings on a Sphere and in Space”, Probl. Peredachi Inf., 14:1 (1978), 3–25; Problems Inform. Transmission, 14:1 (1978), 1–17
- [6]
- C. A. Rogers, “The Packing of Equal Spheres”, Proceedings of the London Mathematical Society s3-8, 609 (1958) DOI
- [7]
- C. A. Rogers, “A note on coverings”, Mathematika 4, 1 (1957) DOI
- [8]
- H. S. M. Coxeter, L. Few, and C. A. Rogers, “Covering space with equal spheres”, Mathematika 6, 147 (1959) DOI
- [9]
- C. E. Shannon, “Probability of Error for Optimal Codes in a Gaussian Channel”, Bell System Technical Journal 38, 611 (1959) DOI
- [10]
- D. Slepian, “Bounds on Communication”, Bell System Technical Journal 42, 681 (1963) DOI
- [11]
- Y. Wu and S. Verdu, “The impact of constellation cardinality on Gaussian channel capacity”, 2010 48th Annual Allerton Conference on Communication, Control, and Computing (Allerton) (2010) DOI
- [12]
- Agrell, E. "Database of sphere packings, 2019." Online: http://codes. se/packings. Accessed (2015).
- [13]
- J. Leech and N. J. A. Sloane, “Sphere Packings and Error-Correcting Codes”, Canadian Journal of Mathematics 23, 718 (1971) DOI
- [14]
- F. Lacerda, J. M. Renes, and V. B. Scholz, “Coherent-state constellations and polar codes for thermal Gaussian channels”, Physical Review A 95, (2017) arXiv:1603.05970 DOI
- [15]
- F. Lacerda, J. M. Renes, and V. B. Scholz, “Coherent state constellations for Bosonic Gaussian channels”, 2016 IEEE International Symposium on Information Theory (ISIT) (2016) DOI

## Page edit log

- Victor V. Albert (2022-11-02) — most recent
- Victor V. Albert (2022-02-16)

## Cite as:

“Sphere packing”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/analog

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