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,d_H), where n is the number of coded bits, k is the number of information bits, and d_H 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 = 2^k, d = 2√d_H, 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 2^k.) 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