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], its recent improvement [7], and Cohn-Elkies linear programming bounds [8]. 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\) [9] as well as an asymptotic lower bound [10], \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 [11]; see the book [3] for more details. Tradeoffs between various parameters have been analyzed [12]. Deterministic sets of constellations from quadrature rules can also achieve capacity [13].
Decoding
Notes
Parents
- Block code
- Group-alphabet code — Sphere-packing alphabets \(\mathbb{R}^n\) are infinite fields, which are groups under addition.
Children
- Hyperbolic sphere packing
- Construction-\(A\) code
- Lattice-based code
- Bounded-energy code — Bounded-energy codes are sphere packings constrained to lie on or inside a sphere.
- Universally optimal sphere packing
Cousins
- Hamiltonian-based code — The Cohn-Elkies linear programming bound is related to the conformal bootstrap, which is a way of utilizing symmetry to constrain correlation functions of conformal field theories [17].
- 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 [18][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.
- Locally correctable code (LCC) — LCCs can also be defined over the real or complex numbers, and there are no complex 2-query LCCs [19].
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]
- M. Campos, M. Jenssen, M. Michelen, and J. Sahasrabudhe, “A new lower bound for sphere packing”, (2023) arXiv:2312.10026
- [8]
- H. Cohn and N. Elkies, “New upper bounds on sphere packings I”, Annals of Mathematics 157, 689 (2003) arXiv:math/0110009 DOI
- [9]
- C. A. Rogers, “A note on coverings”, Mathematika 4, 1 (1957) DOI
- [10]
- H. S. M. Coxeter, L. Few, and C. A. Rogers, “Covering space with equal spheres”, Mathematika 6, 147 (1959) DOI
- [11]
- C. E. Shannon, “Probability of Error for Optimal Codes in a Gaussian Channel”, Bell System Technical Journal 38, 611 (1959) DOI
- [12]
- D. Slepian, “Bounds on Communication”, Bell System Technical Journal 42, 681 (1963) DOI
- [13]
- 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) 620 (2010) DOI
- [14]
- Agrell, E. "Database of sphere packings, 2019." Online: https://codes. se/packings. Accessed (2015).
- [15]
- A. R. Calderbank, “The art of signaling: fifty years of coding theory”, IEEE Transactions on Information Theory 44, 2561 (1998) DOI
- [16]
- D. J. Costello Jr. and G. D. Forney Jr, “Channel Coding: The Road to Channel Capacity”, (2006) arXiv:cs/0611112
- [17]
- T. Hartman, D. Mazáč, and L. Rastelli, “Sphere packing and quantum gravity”, Journal of High Energy Physics 2019, (2019) arXiv:1905.01319 DOI
- [18]
- J. Leech and N. J. A. Sloane, “Sphere Packings and Error-Correcting Codes”, Canadian Journal of Mathematics 23, 718 (1971) DOI
- [19]
- B. Barak, Z. Dvir, A. Wigderson, and A. Yehudayoff, “Rank Bounds for Design Matrices with Applications to Combinatorial Geometry and Locally Correctable Codes”, (2011) arXiv:1009.4375
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/edit/main/codes/classical/analog/analog.yml.