Database of sphere packings
Chalmers University of Technology, Sweden
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.
- 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 ||xi−xj||, 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.
- Normalized fourth moment κ
- The normalized fourth moment is here defined as κ = (1/M)∑i ||xi||4/E2. 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/(N2+4N)], which is the normalized fourth moment of uniform spherical distributions. Multivariate Gaussian distributions have κ = 1+2/N.
- 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.)
- 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.
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 (high signal-to-noise ratio). In this case, the symbol error probability is 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 En, for fixed N0 and Rs. Having the lowest En 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/(2N0EnRs)]) and hence minimized by minimizing En, 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 En [Alvarado14].
The symbol rate can be written as Rs = Rb/log2M, 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.
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.
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.