Sphere packings of dimensions 5 and above (except 8)

Introduction

Multidimensional sphere packings have been studied either as a purely geometric problem or with applications in modulation theory. In the latter case, an arbitrary number of dimensions can be obtained by encoding data simultaneously into several orthogonal quadratures, time slots, frequency bands, or, in optical communications, polarizations.

As the dimension increases, the structure of the packings becomes more and more important. The number of points increases exponentially with the dimension, for a given number of bits per dimension, and the process of storing and searching the packing becomes increasingly impractical. If the packing has a regular structure, however, the coordinates of the points can often be represented by mathematical rules instead of a list, which in turn may admit fast search algorithms.

A trivial way to achieve a structured, multidimensional packing is design it as a Cartesian product of lower-dimensional packings. This essentially means that the N coordinates are split into g groups, and each group is determined independently by an N/g-dimensional packing. The search process (i.e., decoding in communications applications or encoding in quantization) is also done separately for each group of coordinates. There is no need to tabulate multidimensional packings designed in this manner, since their properties can all be derived from the constituent low-dimensional packings.

A more interesting way to design structured, multidimensional sphere packings is to first form the Cartesian product of a low-dimensional sphere packing (typically 1- or 2-dimensional) with itself a number of times, to achieve the desired dimension, and then to select a subset of the obtained point set by algebraic rules, to achieve a good normalized second moment. Low-dimensional examples include parity4_8.txt, which is a hypercube with a single-parity-check code and equivalent to PS-QPSK, and its multilevel generalization SP-QAM, all in 4 dimensions.

In the context of communications, the subset-selection rule can be thought of as channel coding and the encoding of data onto the low-dimensional packing as modulation. The combination of these two steps is called coded modulation. Since the result, in geometric terms, is a multidimensional packing, the whole process can alternatively be viewed as pure (multidimensional) modulation. Indeed, there is no clear-cut distinction between modulation and coding.

For example, consider a binary block code with parameters (n,k,dH), where n is the number of coded bits, k is the number of information bits, and dH is the minimum Hamming distance between codewords. If the bits of the codewords are mapped to ±1, then a sphere packing is obtained with parameters N = n, M = 2k, d = 2√dH, and E = n. (In coding theory, the parameter k is sometimes called the “dimension”, referring to the finite-field dimension for linear block codes, which is not the same as the corresponding dimension in Euclidean space, which is 2k.) Many families of channel codes have been designed since around 1950 [Golay49], [Hamming50] and there exists a rich literature. The most well-known short block codes, which correspond to relatively low-dimensional sphere packings, are included in this database.

When the block code parameters n and k increase, the number of codewords quickly becomes too large to be represented by coordinates in a database of sphere packings. Parameters for a few such codes are listed in the table below, without actually storing the corresponding packings, just to indicate the enormous sizes that are typical for high-dimensional sphere packings designed in this manner. This part of the table is intentionally kept short.

Database

FileNMdEEnκLatβEbCFM [dB]γ [dB]G [dB]Comment
simplex7_8787.3137123.4020.43751Y0.8571437.800679.03092.340830.341991
hamming7_878470.43751Y0.8571432.333339.03092.340830.341991(7,3,4) dual Hamming code, equivalent to the simplex.
hamming7_167163.464170.5833331Y1.142861.757.781512.340830.821313The famous (7,4,3) Hamming code [Golay49], [Hamming50], mapped onto a hypercube. First published in [Shannon48pt1].
sphere7_819278192226.256.56251.05143Y3.714292.01923-2.73001-3.051860.325423A spherical subset of the cubic lattice [Calderbank90].
simplex15_16151616.97061350.468751Y0.53333333.7512.04123.290590.765378
hamming15_1615165.65685150.468751Y0.5333333.7512.04123.290590.765378(15,4,8) Dual Hamming code, equivalent to the simplex.
simplex16_17161718.2107156.0610.4705881Y0.51093338.180312.30453.367530.806573
simplex24_25242528.28433840.481Y0.38698882.689913.97943.835781.0786The 24-dimensional simplex.
biortho16_3216321.4142110.51Y0.6250.212.04123.97941.60137A hyperoctahedron, used in biorthogonal modulation.
RM16_3216325.65685160.51Y0.6253.212.04123.97941.60137(16,5,8) Reed–Muller code, equivalent to biortho16_32.
biortho24_4824481.4142110.51Y0.4654140.17905213.80214.45991.82658A hyperoctahedron, used in biorthogonal modulation.
NR15_256152564.47214150.751N1.066671.875104.259692.611The (15,8,5) Nordstrom–Robinson code, a nonlinear binary code [Nordstrom67], [Goethals71], [Hammons94].
NR16_256162564.89898160.6666671N1210.79184.771213.0103(16,8,6) extended Nordstrom–Robinson code [Goethals71], [Hammons94].
golay11_729117292.236077.333331.466671.04545Y1.729050.7711365.740312.097791.60449The ternary (11,6,5) Golay code, one of the few “perfect” codes [Golay49], mapped onto a sequence of 3-PAM symbols.
golay12_729127292.4494981.333331.04167Y1.584960.841246.532132.511721.76091The ternary (12,6,6) extended Golay code [Conway99, p. 85].
BCH15_3215325.2915150.5357141Y0.666667311.46133.679771.36912(15,5,7) BCH code [Bose60].
BCH15_128151284.47214150.751N0.9333332.14286103.679771.80739(15,7,5) BCH code [Bose60].
hamming15_20481520483.4641151.251Y1.466671.363647.781513.424232.46456(15,11,3) Hamming code [Hamming50].
BCH16_3216325.65685160.51Y0.6253.212.04123.97941.60137(16,5,8) extended BCH code.
BCH16_128161284.89898160.6666671N0.8752.2857110.79184.191292.222(16,7,6) extended BCH code.
4iMDPM-PS-QPSK16_2048162048261.51Y1.3750.5454557.269992.632411.51248A generalized PPM packing [Eriksson14b].
hamming16_204816204841611N1.3751.454559.03094.393333.2734(16,11,4) extended Hamming code [Hamming50]. Also, a Reed–Muller code.
golay23_40962340965.2915230.8214291N1.043481.9166711.46135.625513.9377The binary (23,12,7) Golay code, one of the few “perfect” codes [Golay49].
golay24_40962440965.65685240.751N1212.04126.02064.25969(24,12,8) extended Golay code [Goethals71], [Millar13].
cube24_16777216241677721622461Y213.010300Hypercube.
slepian24_...241.1·10101.414211261N2.780560.3596393.01031.431032.91606A constant-radius packing constructed by Slepian [Gilbert52].
Hamming255_...2552.3·10743.464125521.251Y1.937251.032397.781514.632784.5175The (255,247,3) Hamming code [Golay49], [Hamming50].
RS2040_...20403.7·105758.246212040301Y1.874511.0669515.314812.023111.7931The 256-ary (255,239,17) Reed–Solomon code, which encodes a block of 1912 data bits into 2040 coded bits, has been standardized in many systems for fiber-optical communications [ITU_G.975], [Karlsson16].