Spherical code 

Description

Code whose codewords are points on an \(n\)-dimensional sphere \(S^{n}\) with radius one.

A spherical code is typically denoted by parameters \((n,M,\rho)\), where \(n\) is the code dimension, \(M\) is the size or number of codewords, and \(\rho\) is the squared minimum distance, i.e., the smallest Euclidean distance between pairs of distinct codewords, \begin{align} \rho=\min\left\{ \left\Vert x-y\right\Vert ^{2}\,\text{s.t.}\,x,y\in C,\,\,x\neq y\right\}~. \tag*{(1)}\end{align}

A spherical code can be defined using the Gram matrix \(G = XX^T\), where the rows of \(X\) are the codeword vectors. The Gram matrix is symmetric, positive-definite, and has all diagonal elements equal to one. The code dimension is equal to the rank of \(G\), which can be less than the dimension of the codeword vectors.

Spherical codeword components are often taken from a discrete set of real values called an alphabet. For example, codewords of any length-\(n\) binary code can be mapped into spherical codewords with alphabet \(\{\pm 1/\sqrt{n} \}\) via the antipodal mapping \(0\to +1\) and \(1 \to -1\) [1; Example 1.2.1].

Protection

The Euclidean distance between two points is related to the dot product as \begin{align} \left\Vert x-y\right\Vert^{2} = 2-2x \cdot y~, \tag*{(2)}\end{align} where \(x\cdot y\) is the Euclidean inner product. As a result, the angular distance, \begin{align} \theta=\arccos(x\cdot y) \in[0,\pi]~, \tag*{(3)}\end{align} can be equivalently used to quantify code performance.

The size of an \((n,M,\rho)\) spherical code with \(d\) distances between distinct points satisfies the absolute bound, [2] \begin{align} M\leq{n+d-1 \choose d}+{n+d-2 \choose d-1}~. \tag*{(4)}\end{align} The parameter \(d\) is sometimes called the \(degree\) of the code. For antipodal codes, i.e., codes that are invariant under \(x\to-x\), the bound is \begin{align} M\leq2{n+d-2 \choose d-1}~. \tag*{(5)}\end{align}

Denote \(A_n(\rho)\) to be the largest possible size of a spherical code with distance \(\rho\). Spherical code parameters \((n,M,\rho)\) as well as \(A_n(\rho)\) satisfy the following three Rankin bounds [3–5] \begin{align} \begin{split} \rho & \leq\frac{2M}{M-1}\\ A_{n}\left(\rho\right) & \leq n+1\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,2<\rho\leq4\\ A_{n}\left(2\right) & \leq2n~. \end{split} \tag*{(6)}\end{align} See [6; Ch. 1.2] for other bounds on \(A_n(\rho)\).

Other bounds on spherical codes include the Fejes Toth bound [7], the Wyner bound [8] and the apple-picking bound [9].

Rate

The Kabatiansky-Levenshtein bound [10] is the best known upper bound on the rate of a spherical code with fixed Euclidean distance.

Realizations

Spherical codes are relevant to modern Hopfield networks [11,12]

Notes

See [1,13] for more details and tables of optimal codes.See article [14] for relations of spherical codes to other fields.

Parent

Children

Cousin

  • Quantum spherical code (QSC) — QSCs are quantum analogues of spherical and constant-energy codes because they store information in quantum superpositions of points on a sphere in quantum phase space.

References

[1]
T. Ericson, and V. Zinoviev, eds. Codes on Euclidean spheres. Elsevier, 2001.
[2]
P. Delsarte, J. M. Goethals, and J. J. Seidel, “Spherical codes and designs”, Geometriae Dedicata 6, 363 (1977) DOI
[3]
R. A. Rankin, “On the Closest Packing of Spheres in n Dimensions”, The Annals of Mathematics 48, 1062 (1947) DOI
[4]
Davenport, H., & Hajos, G. (1951). Aufgabe 35. Math. Lapok, 58.
[5]
R. A. Rankin, “The Closest Packing of Spherical Caps in n Dimensions”, Proceedings of the Glasgow Mathematical Association 2, 139 (1955) DOI
[6]
J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups (Springer New York, 1999) DOI
[7]
L. Fejes Toth, Uber die Abschatzung des kiirzesten Abstandes zweier Punkte eines auf einer Kugelflache liegenden Punktsystemes, Jber. Deut. Math. Verein., Vol. 53, pp. 66-68, 1943.
[8]
A. D. Wyner, “Capabilities of Bounded Discrepancy Decoding”, Bell System Technical Journal 44, 1061 (1965) DOI
[9]
A. E. Gamal, L. Hemachandra, I. Shperling, and V. Wei, “Using simulated annealing to design good codes”, IEEE Transactions on Information Theory 33, 116 (1987) DOI
[10]
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
[11]
J. Y.-C. Hu, D. Wu, and H. Liu, “Provably Optimal Memory Capacity for Modern Hopfield Models: Transformer-Compatible Dense Associative Memories as Spherical Codes”, (2024) arXiv:2410.23126
[12]
S. Santos, V. Niculae, D. McNamee, and A. F. T. Martins, “Sparse and Structured Hopfield Networks”, (2024) arXiv:2402.13725
[13]
Sloane, N. J. A., R. H. Hardin, and W. D. Smith. "Tables of spherical codes." collaboration with RH Hardin, WD Smith and others. Published electronically at https://neilsloane.com/packings/ (2004).
[14]
E. B. Saff and A. B. J. Kuijlaars, “Distributing many points on a sphere”, The Mathematical Intelligencer 19, 5 (1997) DOI
Page edit log

Your contribution is welcome!

on github.com (edit & pull request)— see instructions

edit on this site

Zoo Code ID: spherical

Cite as:
“Spherical code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/spherical
BibTeX:
@incollection{eczoo_spherical, title={Spherical code}, booktitle={The Error Correction Zoo}, year={2022}, editor={Albert, Victor V. and Faist, Philippe}, url={https://errorcorrectionzoo.org/c/spherical} }
Share via:
Twitter | Mastodon |  | E-mail
Permanent link:
https://errorcorrectionzoo.org/c/spherical

Cite as:

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

Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/classical/spherical/spherical.yml.