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 = min_i≠j ||x_i−x_j||, where x₁, ..., x_M are the points in the packing
Second moment E: The mean squared Euclidean norm E = (1/M)∑_i ||x_i||²
Normalized second moment E_n: Using the normalization E_n = E/d², a parameter is obtained that is insensitive to scaling and hence useful to compare packing densities.
Normalized fourth moment κ: The normalized fourth moment is here defined as κ = (1/M)∑_i ||x_i||⁴/E². It is sometimes called kurtosis [Gursoy05], although kurtosis is more often defined differently. It is a measure of how much the squared Euclidean norm varies between constellation points. If κ = 1, then all points have the same norm, i.e., they form a spherical code. Optimal sphere packings are spherical codes if the number of points per dimension is small enough (small β, as defined below). As G → ∞, κ → 1+4/(N²+4N)], which is the normalized fourth moment of uniform spherical distributions. Multivariate Gaussian distributions have κ = 1+2/N.
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 x_i = a + ∑_j u_ijb_j for all i, where a, b₁, ..., b_N are real N-dimensional vectors and u_ij 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 β = (2log₂M)/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 E_b: E_b = E/log₂M gives the average energy needed to transit one bit of information
Constellation figure of merit CFM: Defined as CFM = d²N/(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 γ = d²/(4E_b) = β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 CFM_PAM = 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/CFM_PAM = γ/γ_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 10log₁₀CFM, 10log₁₀γ, and 10log₁₀G, 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 E_n is considered the better. If a packing has the lowest E_n 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 (high signal-to-noise ratio). In this case, the symbol error probability is proportional to Q(√[P/(2N₀E_nR_s)]), where Q is the Gaussian Q function, P is the average transmitted power, R_s is the symbol rate, and N₀ is the noise power spectral density. The power needed to achieve a certain (low) error probability is thus proportional to E_n, for fixed N₀ and R_s. Having the lowest E_n means having the highest CFM if N is fixed, the highest γ if M is fixed, and the highest G if β is fixed.

The bit error probability is also asymptotically proportional to Q(√[P/(2N₀E_nR_s)]) and hence minimized by minimizing E_n, regardless of the mapping between bits and symbol. (This is one reason why bit mappings are not considered in this database. At nonasymptotic error probabilities, however, the bit mapping would play a significant role.) Furthermore, the mutual information, which is the relevant performance metric assuming ideal error-correcting coding, behaves analogously at asymptotically high signal-to-noise ratio and is again optimized by minimizing E_n [Alvarado14].

The symbol rate can be written as R_s = R_b/log₂M, where R_b is the bit rate, and also, assuming Nyquist signaling, as R_s = 2B/N, where B is the bandwidth. Hence, the required power is proportional to E_nR_s = B/CFM = R_b/(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 E_n, 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 E_n, CFM, γ, and G.