4
$\begingroup$

I know that good codes allow you to construct good sphere packings in Euclidean space, e.g. the binary Golay code is the key feature of the construction of the Leech lattice.

Going in the other direction, I am wondering whether sphere packings in $\mathbf{R}^n$ actually help with designing good codes (for some definition of "code" that is useful in a practical setting). I know that codes on $n$ bits are sphere packings in Hamming space, but I'm wondering specifically about Euclidean sphere packings.

I know that kissing configurations yield spherical codes (by definition). Are these actually useful in practice? Also, do dense (lattice) packings produce any practically useful codes? From searching on Google I found a small section of a paper of H. Cohn (page 6 of https://arxiv.org/pdf/1003.3053.pdf) which gives a simplified example of how one can do coding with noise using good sphere packings, but I am wondering whether this is actually done in practice.

$\endgroup$
3
  • 2
    $\begingroup$ I'm at loss here. I do know that spherical codes have been proposed to be used for quantizing certain practical problems. For example in a cellular feedback channel, where a cell phone can use a few bits to send the base station some information about its measurements of the signal of the base station. Caveats: 1) The quantization problem requires a spherical code only in a specific case (more generally you would want to quantize a Grassmannian instead of a sphere). 2) I don't know if that proposal made its way to any current standard. $\endgroup$ – Jyrki Lahtonen Nov 16 '20 at 5:14
  • 1
    $\begingroup$ Some lattice codes have also been proposed for a cryptographic application in a wiretap channel. The assumption is that an eavesdropper only hears a noisier version of the message in comparison to the intended receiver, and we can design schemes taking advantage of that. Some properties of theta functions of pairs of lattices come to the fore, but I'm not entirely sold on the applicability. $\endgroup$ – Jyrki Lahtonen Nov 16 '20 at 13:11
  • $\begingroup$ @JyrkiLahtonen: thanks! I have found some papers on Google about quantizing a Grassmanian. I shouldn't have been so strict in my question about the applicability -- this kind of thing is very interesting to me. $\endgroup$ – babu_babu Nov 18 '20 at 21:29
1
+50
$\begingroup$

I believe the question was asked in general terms, so this answer expands the scope of the question to include not only sphere packings, but also sphere coverings. Some sphere coverings based on lattices are simultaneously very good coverings and admit highly efficient nearest neighbor quantization algorithms; see for example

JH Convay and NJA Sloane. Fast quantizing and decoding algorithms for lattice quantizers. IEEE Trans Inform Theory, 28(2):227–232, 1982.

and in particular the beautifully simple E8 lattice fast quantization algorithm.

It seems that variants of this lattice construction and associated quantization algorithm have been used in a standard, see

Lattice Vector Quantization Applied to Speech and Audio Coding, Minjie Xie, ZTE Communications, 2012, Vol. 10, Issue (2): 25-33.

$\endgroup$
2
$\begingroup$

The quick answer is no, this approach to code design in not used in practice. Take a look at the codes used in 5G or WiFi for example. Both are large scale projects where code performance and decoder complexity are key...neither use sphere packings in the code design

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.