Database of sphere packings

Erik Agrell
Chalmers University of Technology, Sweden
agrell@chalmers.se

Introduction: Sphere packings and their use as modulation formats

A sphere packing, or packing for short, is a set of M points in an N-dimensional space, such that the Euclidean distance between any pair of points is at least a given value. If the points are interpreted as the centers of spheres (i.e., N-dimensional hyperspheres) of a given diameter, the problem is to pack the spheres, without overlap, as densely as possible according to a certain criterion. The most common such criterion is the second moment, which is the average squared Euclidean distance between a point in the packing and the origin of the coordinate system.

Sphere packings are often used as modulation formats, to encode digital information for transmission or storage. The performance of modulation formats is traditionally characterized in terms of spectral efficiency and power efficiency, to be defined below.

If you cite or use the contents of this site, please acknowledge the source.

Geometric parameters

Dimension N
The number of coordinates used to represent each point in the packing
Size M
The number of points
Minimum distance d
The minimum Euclidean distance between any pair of points d = mini≠j ||xixj||, where x1, ..., xM are the points in the packing
Second moment E
The mean squared Euclidean norm E = (1/M)∑i ||xi||2
Normalized second moment En
Using the normalization En = E/d2, a parameter is obtained that is insensitive to scaling and hence useful to compare packing densities.
Lattice
This binary parameter is “Y” if the packing is a subset of a (possibly translated) lattice, otherwise “N”. In other words, it is “Y” if xi = a + ∑j uijbj for all i, where a, b1, ..., bN are real N-dimensional vectors and uij are integers for all i and j. (A heuristic test is applied to check whether the subset is sufficiently “compact”, because otherwise all packings with rational coordinates would count as lattice subsets.)

Modulation parameters

Spectral efficiency β
The spectral efficiency or normalized bit rate is defined as β = (2log2M)/N [Forney89a], [Kschischang93]. It gives the number of bits per channel use, where every (complex) channel use involves two dimensions. It also gives the bitrate per bandwidth, in bit/s/Hz, if Nyquist signaling is applied (sinc pulse shaping). A related quantity is β/2, which gives the number of bits per dimension. This quantity can also be interpreted as the data rate per bandwidth in bit/s/Hz, if rectangular pulse shaping is applied and bandwidth is defined as the width of the spectral main lobe.
Average symbol energy
The same as the second moment E
Average bit energy Eb
Eb = E/log2M gives the average energy needed to transit one bit of information
Constellation figure of merit CFM
Defined as CFM = d2N/(2E) [Forney89a], [Kschischang93]. This is, under some conditions (see “Optimal packings” below), the relevant power metric if modulation formats are compared at the same bandwidth.
Power efficiency γ
The (asymptotic) power efficiency is γ = d2/(4Eb) = βCFM/4 [Benedetto99, eq. (5.8)], [Agrell09]. This is, under some conditions (see “Optimal packings” below), the relevant power metric if modulation formats are compared at the same bit rate.
Gain G
The gain is quantified with respect to a baseline modulation format at the same spectral efficiency β, commonly chosen as pulse-amplitude modulation (PAM) [Forney89a], [Kschischang93]. A PAM packing has CFMPAM = 6/(2β−1) and γPAM = (3/2)β/(2β−1). Multidimensional extensions of PAM such as quadrature-amplitude modulation (QAM) and polarization-multiplexed (PM) QAM have the same CFM and γ. Geometrically, the baseline packings represent cubic subsets of the cubic lattice. The gain is defined as G = CFM/CFMPAM = γ/γPAM, also for β values for which no PAM packing exists. It can be divided into a coding gain, obtained by improving the local arrangement of the points over a rectangular/cubic grid, and a shaping gain, obtained by replacing the cubic boundary with something more spherical [Forney89a], [Karlsson12].

The last three parameters are given in decibels, calculated as 10log10CFM, 10log10γ, and 10log10G, resp. The highest values in each of the three columns are marked with boldface, indicating the best known packing of this dimension, in the senses defined in the next section.

Optimal packings

Sphere packings can be compared in several scenarios. If packings with the same parameters N and M are compared, then the packing with the lowest En is considered the better. If a packing has the lowest En among all possible packings with given N and M, then it is called the optimal packing with these parameters. There are many numerically supported conjectures about optimal packings, but few optimality proofs.

To evaluate the performance of a packing applied as a modulation format, the simplest and most common scenario is to assume additive white Gaussian noise, no coding, optimal detection (maximum likelihood), and asymptotically low error probability. In this case, the bit error probability and symbol error probability are both proportional to Q(√[P/(2N0EnRs)]), where Q is the Gaussian Q function, P is the average transmitted power, Rs is the symbol rate, and N0 is the noise power spectral density. The power needed to achieve a certain (low) error probability is thus proportional to EnRs. This holds regardless of whether bit or symbol error probabilities are considered, and in the case of bit error probability, regardless of the mapping between bits and symbol. (This is the reason why bit mappings are not considered in this database. At nonasymptotic error probabilities, however, the bit mapping would play a significant role.)

The symbol rate can be written as Rs = Rblog2M, where Rb is the bit rate, and also, assuming Nyquist signaling, as Rs = 2B/N, where B is the bandwidth. Hence, the required power is proportional to EnRs = B/CFM = Rb/(4γ). From this relation, we conclude that if modulation formats are compared at the same bandwidth, then the format with the higher CFM is the better, whereas if they are compared at the same bit rate, then the format with the higher γ is the better. In the special case when the compared formats have the same spectral efficiency β, then comparisons in terms of CFM and γ will give the same results, since γ/CFM = β/4.

Sphere packings are also often used as modulation formats under nonideal conditions, e.g., for channels with memory or non-Gaussian noise, in the presence of error-correcting coding, with suboptimal detection, or at high error probability. Some of the packings in this database are popular also under such conditions, but the performance should be quantified using other metrics than those tabulated here.

File format

Each packing is stored as a text file, with M rows and N tab-separated fields per row. Every row gives the coordinates of one point. There is no file header.

Many of the packings have been scaled and rotated into a “nice” coordinate representations. The performance parameters En, CFM, γ, and G are invariant to scaling and rotation. Most of the packings have zero mean. The ordering of the rows is arbitrary.

Example: The four corners of a square give a packing with parameters N = 2, M = 4, which is known as quadrature phase shift keying (QPSK) in modulation theory. Two possible coordinate representations are

-1.	-1.
-1.	1.
1.	-1.
1.	1.

and

1.	0.
0.	1.
-1.	0.
0.	-1.

which in the database are called QAM2_4.txt and QPSK2_4.txt, resp. The two representations are geometrically equivalent, in the sense that they can be transformed into each other by rotation and scaling. They therefore have the same En, CFM, γ, and G.