(practical) Codes from sphere packings

240 Views Asked by At

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.

2

There are 2 best solutions below

0
On BEST ANSWER

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.

0
On

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