# 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**_{1}, ...,**x**_{M}are the points in the packing - Second moment
`E` - The mean squared Euclidean norm
`E`= (1/`M`)∑_{i}||**x**_{i}||^{2} - Normalized second moment
`E`_{n} - Using the normalization
`E`_{n}=`E`/`d`^{2}, 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}||^{4}/`E`^{2}. 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`^{2}+4`N`)], 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`_{ij}**b**_{j}for all`i`, where**a**,**b**_{1}, ...,**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_{2}`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_{2}`M`gives the average energy needed to transit one bit of information- Constellation figure of merit
`CFM` - Defined as
`CFM`=`d`^{2}`N`/(2`E`) [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`^{2}/(4`E`_{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_{10}`CFM`, 10log_{10}`γ`, and 10log_{10}`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`/(2`N`_{0}`E`_{n}`R`_{s})]), where `Q` is the Gaussian Q function, `P` is the average transmitted power, `R`_{s} is the symbol rate, and `N`_{0} 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`_{0} 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`/(2`N`_{0}`E`_{n}`R`_{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_{2}`M`, where `R`_{b} is the bit rate, and also, assuming Nyquist signaling, as `R`_{s} = 2`B`/`N`, where `B` is the bandwidth. Hence, the required power is proportional to `E`_{n}`R`_{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`.