# Low-Complexity Voronoi Shaping
for the Gaussian Channel

Shen Li, Ali Mirani, Magnus Karlsson, and Erik Agrell This work will be
presented in part at the IEEE International Symposium on Information Theory
(ISIT), Melbourne, Australia, July 2021.This work was supported by the Swedish
Research Council (VR) under grant no. 2017–03702.S. Li and E. Agrell are with
the Department of Electrical Engineering, Chalmers University of Technology,
412 96 Gothenburg, Sweden. e-mail<EMAIL_ADDRESS>Mirani and M. Karlsson
are with the Department of Microtechnology and Nanoscience, Chalmers
University of Technology, 412 96 Gothenburg, Sweden.

###### Abstract

Voronoi constellations (VCs) are finite sets of vectors of a coding lattice
enclosed by the translated Voronoi region of a shaping lattice, which is a
sublattice of the coding lattice. In conventional VCs, the shaping lattice is
a scaled-up version of the coding lattice. In this paper, we design low-
complexity VCs with a cubic coding lattice of up to $32$ dimensions, in which
pseudo-Gray labeling is applied to minimize the bit error rate. The designed
VCs have considerable shaping gains of up to $1.03$ dB and finer choices of
spectral efficiencies in practice. A mutual information estimation method and
a log-likelihood approximation method based on importance sampling for very
large constellations are proposed and applied to the designed VCs. With error-
control coding, the proposed VCs can have higher achievable information rates
than the conventional scaled VCs because of their inherently good pseudo-Gray
labeling feature, with a lower decoding complexity.

###### Index Terms:

Achievable information rates, geometric shaping, lattices, multidimensional
modulation formats, Voronoi constellation.

##  I Introduction

Power efficiency is important for higher-order modulation formats in
communication systems. For an additive white Gaussian noise (AWGN) channel
with an average power constraint, signal shaping is able to reduce the well-
known asymptotic $1.53$ dB gap [1] between the channel capacity and the
achievable information rate (AIR) with a uniform signal (such as the most
widely used quadrature amplitude modulation (QAM)), by adjusting the
distribution of the transmitted signal alphabet to the capacity-achieving
distribution, which is the Gaussian distribution. There are two flavors of
shaping, geometric shaping by rearranging the positions of equally likely
constellation points [2, 1], and probabilistic shaping by changing the
distribution of a regular constellation [3, 4]. Much work has been devoted to
the design of Gaussian-like constellations with feasible complexity in two [5,
6, 7, 8, 9] and higher dimensions [10] for the AWGN channel.

The concept of Voronoi constellations (VCs) was first proposed in 1983 by
Conway and Sloane, as a finite set of points of a lattice enclosed by a
translated scaled-up version of its Voronoi region [11]. Very fast algorithms
for mapping integers to constellation points and vice versa were presented in
[11, 12]. In [13, 14], Mirani _et al._ designed multidimensional scaled VCs
with up to $10^{28}$ constellation points utilizing this concept for the AWGN
channel and nonlinear fiber channel, and showed high shaping gains and coding
gains, and significant bit error rate (BER) and symbol error rate (SER) gains
over QAM in uncoded system as well.

Forney generalized this concept in 1989 to VCs based on an arbitrary lattice
partition $\Lambda/\Lambda_{\mathrm{s}}$ [15], where $\Lambda$ is referred to
as the coding lattice and $\Lambda_{\mathrm{s}}$ the shaping lattice. They can
be different, as long as the shaping lattice is a sublattice of the coding
lattice. Forney presented encoding and decoding algorithms for certain choices
of the shaping lattice, such as so-called mod-2 or mod-4 binary lattices.

Feng _et al._ presented a more general method to enumerate the points in a VC
based on an arbitrary lattice partition [16], which is reviewed by Zamir in
[17, Ch. 9], [18]. This enumeration admits encoding and decoding algorithms as
fast as Conway and Sloane’s. An equally simple but less general method called
“rectangular encoding” was proposed by Kurkoski in [19] for VCs whose shaping
lattice and coding lattice both have triangular generator matrices. This
method is applicable to a variety of coding lattices and shaping lattices.

Ferdinand _et al._ proposed a two-step VC construction method called
“systematic Voronoi shaping” in [20] based on the concept of “systematic
shaping” proposed by Sommer _et al._ in [21], combining a high-dimensional
coding lattice defined by a lower-triangular parity check matrix and a lower-
dimensional shaping lattice, to achieve high coding gains and high shaping
gains. The SER performance was evaluated when low-density lattice codes [22]
are used as the coding lattice and some common multidimensional lattices with
low-complexity quantization algorithms are used for the shaping lattice. For
the shaping step, algorithms to map the integers to points in VCs with a cubic
coding lattice and vice versa were explicitly described in [23].

In our conference paper [24], we studied VCs with a cubic coding lattice, for
which we compared Feng’s, Ferdinand’s, and Kurkoski’s encoding and decoding
algorithms. To minimize the BER, we applied pseudo-Gray labeling to these
algorithms, and evaluated the performance of the designed VCs in terms of the
Gray penalty [25, 26] and BER performance for some common multidimensional
shaping lattices both in uncoded and coded systems. In our proposed scheme,
coding is completely separated from shaping and performed using error-control
coding, outside the Voronoi shaping.

We study VCs with a cubic coding lattice for the following three reasons.
First, the decoding algorithm is much simpler than for VCs with rescaled
coding and shaping lattices [11, 13], since the search for the closest lattice
point, which dominates the decoding complexity for high-dimensional lattices,
is simple dimension-wise integer rounding for a cubic coding lattice. Second,
although the proposed VCs have no coding gain, the shaping gain is still
achievable, and the lack of coding gain can be compensated by error-correction
coding that is usually performed anyway. After error-correction coding, the
proposed VCs can have better BER performance than the conventional scaled VCs
because of their inherently good pseudo-Gray labeling feature. Third, for
mapping integers to bits, the proposed VCs allow for improved granularity in
spectral efficiencies.

In this paper, we extend our work [24] on the VCs with a cubic coding lattice.
We propose a new method based on the concept of importance sampling to
estimate the mutual information (MI) for very large constellations, and
exemplify it for VCs. This has been considered as a challenging issue for such
large constellations since the exact MI calculation requires enumerating all
constellation points. The MI of VCs is evaluated here for the first time to
our knowledge. The AIR performance of VCs in combination with a low-density
parity-check (LDPC) code is also presented. For mapping integers to bits, we
improve the granularity in spectral efficiencies by rotating the shaping
lattice by $None$ and scaling it by $\sqrt{2}$. We also investigate the trade-
off between shaping gain and decoding complexity in higher dimensions.

_Notation:_ Bold lowercase symbols denote row vectors and bold uppercase
symbols denote matrices or random vectors. The elements of a vector
$\boldsymbol{u}$ are denoted by $u_{i}$, the rows of a matrix $\boldsymbol{P}$
are denoted by $\boldsymbol{p}_{i}$, and the element at row $i$, column $j$ of
a matrix $\boldsymbol{P}$ are denoted by $P_{ij}$. The sets of integer, real,
complex, and natural numbers are denoted by $\mathbb{Z}$, $\mathbb{R}$,
$\mathbb{C}$, and $\mathbb{N}$, respectively. Rounding a vector to its nearest
integer vector is denoted by $\lfloor\cdot\rceil$, in which ties are broken
arbitrarily. The largest integer not greater than a given real number is
denoted by $\lfloor\cdot\rfloor$.

##  II Preliminaries

Given a set of $n$ linearly independent _basis vectors,_ a _lattice_ is the
set of all linear combinations of these vectors with integer coefficients. If
the basis vectors are arranged row-wise into a matrix $\boldsymbol{G}$, then
the lattice is

$\displaystyle\Lambda\triangleq\\{\boldsymbol{u}\boldsymbol{G}:\;\boldsymbol{u}\in\mathbb{Z}^{n}\\}.$
(1)

Without loss of generality, we assume that the generator matrix has dimension
$n\times n$.111The $n$ basis vectors must have dimension at least $n$ in order
to be linearly independent. If $n$ basis vectors are given in more than $n$
dimensions, then an $n$-dimensional lattice, which is equivalent to the
original lattice in Euclidean geometry, can be defined by rotating (e.g., QR-
decomposing) $\boldsymbol{G}$. From the definition, any lattice includes the
all-zero vector $\boldsymbol{0}$. The generator matrix of a given lattice is
not unique. Two generator matrices $\boldsymbol{G}$ and
$\boldsymbol{G}^{\prime}$ generate the same lattice if and only if
$\boldsymbol{G}^{\prime}=\boldsymbol{U}\boldsymbol{G}$, where $\boldsymbol{U}$
is an integer matrix with determinant $\pm 1$ [27, p. 10].

The _closest lattice point quantizer_ $\mathcal{Q}_{\Lambda}(\cdot)$ maps an
arbitrary vector $\boldsymbol{x}\in\mathbb{R}^{n}$ to its closest lattice
point in $\Lambda$

$\displaystyle\mathcal{Q}_{\Lambda}(\boldsymbol{x})=\operatorname*{arg\,min}_{\boldsymbol{\lambda}\in\Lambda}\|\boldsymbol{x}-\boldsymbol{\lambda}\|^{2}.$
(2)

If an affine transformation function $T(\cdot)$ is applied to the lattice
$\Lambda$, e.g., a scaling, rotation, or/and a shift, then it follows that

$\displaystyle\mathcal{Q}_{T(\Lambda)}(\boldsymbol{x})=T(\mathcal{Q}_{\Lambda}(T^{-1}(\boldsymbol{x}))).$
(3)

The _fundamental Voronoi region_ of a lattice $\Lambda$ is the set of vectors
in Euclidean space having the all-zero vector as its closest lattice point,
i.e.,

$\displaystyle\Omega(\Lambda)\triangleq\\{\boldsymbol{x}\in\mathbb{R}^{n}:\;\mathcal{Q}_{\Lambda}(\boldsymbol{x})=\boldsymbol{0}\\}.$
(4)

Given an $n$-dimensional coding lattice $\Lambda$, an $n$-dimensional shaping
lattice $\Lambda_{\mathrm{s}}$, and an _offset vector_
$\boldsymbol{a}\in\mathbb{R}^{n}$, where $\Lambda_{\mathrm{s}}$ is a
sublattice of $\Lambda$, i.e., $\Lambda_{\mathrm{s}}\subset\Lambda$, a VC in
its general form defined by Forney [15] is

$\displaystyle\Gamma\triangleq(\Lambda-\boldsymbol{a})\cap\Omega(\Lambda_{\mathrm{s}}).$
(5)

We assume that no points in $\Lambda-\boldsymbol{a}$ fall on the boundary of
$\Omega(\Lambda_{\mathrm{s}})$.222An arbitrarily small perturbation of the
offset $\boldsymbol{a}$ in a random direction prevents points from falling on
the boundary with probability one. The number of points in the VC is

$\displaystyle
M\triangleq|\Gamma|=\frac{|\\!\det\boldsymbol{G}_{\mathrm{s}}|}{|\\!\det\boldsymbol{G}|},$
(6)

where $\boldsymbol{G}_{\mathrm{s}}$ is a generator matrix of
$\Lambda_{\mathrm{s}}$. This relation can be verified by recognizing
$|\\!\det\boldsymbol{G}|$ and $|\\!\det\boldsymbol{G}_{\mathrm{s}}|$ as the
volumes of $\Omega(\Lambda)$ and $\Omega(\Lambda_{\mathrm{s}})$, respectively
[27, p. 4]. The average symbol energy is

$\displaystyle
E_{\text{s}}=\frac{1}{M}\sum_{\boldsymbol{x}\in\Gamma}\|\boldsymbol{x}\|^{2}.$
(7)

To compare the performance of different constellations, the following relevant
figures of merit were defined and widely used in the literature.

_1)_ The _spectral efficiency_ [10, 4, 28] of a constellation is defined as

$\displaystyle\beta=2\log_{2}(M)/n~{}\text{[bits/symbol/dimension-pair]}.$ (8)

_2)_ The _asymptotic power efficiency_ (APE) [29, Eq. (5.8)],[30] is defined
as

$\displaystyle\gamma=\frac{d_{\text{min}}^{2}\log_{2}(M)}{4E_{\text{s}}},$ (9)

where $d_{\text{min}}$ is the minimum Euclidean distance of the constellation.
Usually, the pulse amplitude modulation (PAM) is chosen as the benchmark [10,
4], which has an APE of

$\displaystyle\gamma_{\text{PAM}}=\frac{3\beta}{2(2^{\beta}-1)}.$ (10)

This also applies to the geometric extension of a PAM, i.e., an
$n$-dimensional cubic constellation constructed by the Cartesian product of
$n$ equal one-dimensional PAM constellations.

_3)_ The _APE gain_ of a constellation over a cubic constellation at the same
spectral efficiencies is quantified as

$\displaystyle g=10\log_{10}\frac{\gamma}{\gamma_{\text{PAM}}}~{}\text{[dB]}.$
(11)

It can be divided into a _coding gain_ $g_{\text{c}}$ obtained by packing the
constellation points in a cubic shape more densely, and a _shaping gain_
$g_{\text{s}}$ obtained by making the boundary of the cubic-packing points
more spherical [10, 28]. For the fundamental Voronoi region of the lattice
$\Lambda_{\mathrm{s}}$, the (asymptotic) shaping gain is defined as
$g_{\text{s}}(\Lambda_{\mathrm{s}})=1/(12G(\Omega(\Lambda_{\mathrm{s}})))$
[10], where $G(\Omega(\Lambda_{\mathrm{s}}))$ is the normalized second moment
of this region [31, Eq. (9)].

##  III Mapping integers to VCs

Feng _et al._ proposed encoding and decoding algorithms, i.e., mapping
integers to constellation points and vice versa, for arbitrary VCs in [16],
which relies on the Smith normal form [32, Ch. 15]. In [23], Ferdinand _et
al._ proposed encoding and decoding algorithms specifically for VCs with a
cubic coding lattice. Kurkoski proposed a “rectangular encoding” method in
[19], which is applicable to VCs with a shaping lattice described by a
triangular generator matrix and a cubic coding lattice. In this section, the
three algorithms are reviewed and compared specifically when they are applied
to VCs with a cubic coding lattice.

Table I summarizes the three algorithms for the special case of the lattice
partition $\mathbb{Z}^{n}/\Lambda_{\mathrm{s}}$, which is the focus of this
paper. The more general versions of Feng’s algorithms for arbitrary $\Lambda$
are described in [16]. In Ferdinand’s algorithms described in [23], the basis
vectors are column vectors and the decoding goes from low to high dimensions.
Here for the convenience of comparison, we describe them using row vectors as
basis vectors, and rewrite the decoding process of [23, Eqs. (19)–(21)], with
a reverse order of decoding, which however does not change the performance of
their algorithms.

The closest lattice point quantizer
$\mathcal{Q}_{\Lambda_{\mathrm{s}}}(\cdot)$ in these algorithms is well-
studied for many common lattices [27, Ch. 20], [12, 33], and other lattices
can be handled by general algorithms [34, 35].

Algorithms |  Feng’s algorithms[16] |  Ferdinand’s algorithms [23] |  Kurkoski’s algorithms[19]
---|---|---|---
_Preprocessing:_ Given the generator matrix $\boldsymbol{G}_{\mathrm{s}}$ of the shaping lattice $\Lambda_{\mathrm{s}}$ and the generator matrix of the cubic coding lattice is $\boldsymbol{G}=\boldsymbol{I}_{n}$. |  Find two integer matrices $\boldsymbol{S}$ and $\boldsymbol{T}$ with determinant $\pm 1$ such that $\boldsymbol{J}=\boldsymbol{S}\boldsymbol{G}_{\mathrm{s}}\boldsymbol{T}$ is the Smith normal form of $\boldsymbol{G}_{\mathrm{s}}$. Then let $u_{i}\in\\{0,\ldots,J_{ii}-1\\}$ for $i=1,\ldots,n$. |  Find an integer matrix $\boldsymbol{S}$ with determinant $\pm 1$ such that $\boldsymbol{L}=\boldsymbol{S}\boldsymbol{G}_{\mathrm{s}}$ is a lower-triangular matrix with positive diagonal elements. Let $u_{i}\in\\{0,\ldots,L_{ii}-1\\}$ for $i=1,\ldots,n$. |  Find an integer matrix $\boldsymbol{S}$ with determinant $\pm 1$ such that $\boldsymbol{L}=\boldsymbol{S}\boldsymbol{G}_{\mathrm{s}}$ is a lower-triangular matrix with positive diagonal elements. Let $u_{i}\in\\{0,\ldots,L_{ii}-1\\}$ for $i=1,\ldots,n$.
_Encoding:_ Input $\boldsymbol{u}$. Output $\boldsymbol{x}$. |  | 1) Let $\boldsymbol{c}\leftarrow\boldsymbol{u}\boldsymbol{T}^{-1}-\boldsymbol{a}$
---
2) Let
$\boldsymbol{z}\leftarrow\mathcal{Q}_{\Lambda_{\mathrm{s}}}(\boldsymbol{c})$
3) Let $\boldsymbol{x}\leftarrow\boldsymbol{c}-\boldsymbol{z}$
| 1) Let
$\boldsymbol{d}\leftarrow\left(\frac{u_{1}}{L_{11}},\frac{u_{2}}{L_{22}},\ldots,\frac{u_{n}}{L_{nn}}\right)$
---
2) Let $\boldsymbol{c}=\boldsymbol{d}\boldsymbol{L}-\boldsymbol{a}$
3) Let
$\boldsymbol{z}\leftarrow\mathcal{Q}_{\Lambda_{\mathrm{s}}}(\boldsymbol{c})$
4) Let $\boldsymbol{x}\leftarrow\boldsymbol{c}-\boldsymbol{z}$
| 1) Let $\boldsymbol{c}\leftarrow\boldsymbol{u}-\boldsymbol{a}$
---
2) Let
$\boldsymbol{z}\leftarrow\mathcal{Q}_{\Lambda_{\mathrm{s}}}(\boldsymbol{c})$
3) Let $\boldsymbol{x}\leftarrow\boldsymbol{c}-\boldsymbol{z}$
_Decoding:_ Input $\boldsymbol{y}$. Output $\boldsymbol{u}$. |  | 1) Let $\boldsymbol{c}\leftarrow\lfloor\boldsymbol{y}+\boldsymbol{a}\rceil$
---
2) Let $\boldsymbol{u}\leftarrow\boldsymbol{c}\boldsymbol{T}$
3) Let $u_{i}\leftarrow u_{i}\mod J_{ii}$, $\forall i=1,\ldots,n$
| 1) Let $\boldsymbol{u}\leftarrow\lfloor\boldsymbol{y}+\boldsymbol{a}\rceil$
---
2) For $i=n,n-1,\ldots,1,$ do
$\left\\{\begin{matrix}v_{i}\leftarrow\lfloor u_{i}/L_{ii}\rfloor\\\
\boldsymbol{u}\leftarrow\boldsymbol{u}-v_{i}\boldsymbol{l}_{i}\end{matrix}\right.$
| 1) Let $\boldsymbol{u}\leftarrow\lfloor\boldsymbol{y}+\boldsymbol{a}\rceil$
---
2) for $i=n,n-1,\ldots,1,$ do
$\left\\{\begin{matrix}v_{i}\leftarrow\lfloor u_{i}/L_{ii}\rfloor\\\
\boldsymbol{u}\leftarrow\boldsymbol{u}-v_{i}\boldsymbol{l}_{i}\end{matrix}\right.$
TABLE I: A Comparison of different encoding and decoding algorithms for VCs
with a cubic coding lattice.

Every matrix over a principal ideal domain has a Smith normal form, and the
integers form a principal ideal domain [32, 16]. In Feng’s algorithm, given an
integer generator matrix $\boldsymbol{G}_{\mathrm{s}}$, the Smith normal form
is first computed in the preprocessing stage as
$\boldsymbol{J}=\boldsymbol{S}\boldsymbol{G}_{\mathrm{s}}\boldsymbol{T}$,
where $\boldsymbol{J}$ is a diagonal matrix with positive diagonal elements
and $J_{ii}$ divides $J_{ii+1}$ for $i=1,\ldots,n-1.$ Then the integer vectors
$\boldsymbol{u}$ are enumerated according to the diagonal elements of
$\boldsymbol{J}$. The $M=\\!\det\boldsymbol{J}$ possible values of
$\boldsymbol{u}\boldsymbol{T}^{-1}$ can be uniquely mapped to the $M$
constellation points $\boldsymbol{x}\in\Gamma$ by

$\displaystyle\boldsymbol{x}=\boldsymbol{u}\boldsymbol{T}^{-1}+\boldsymbol{v}\boldsymbol{S}\boldsymbol{G}_{\mathrm{s}}-\boldsymbol{a},$
(12)

where $\boldsymbol{v}\in\mathbb{Z}^{n}$. The Smith normal form
$\boldsymbol{J}$ is unique given a $\boldsymbol{G}_{\mathrm{s}}$, whereas
$\boldsymbol{S}$ and $\boldsymbol{T}$ are not unique; thus Feng’s algorithms
can generate different mapping rules for the same
$\boldsymbol{G}_{\mathrm{s}}$.

In Ferdinand’s algorithms, a lower-triangular generator matrix
$\boldsymbol{L}$ for $\Lambda_{\mathrm{s}}$ is first computed (the algorithms
are applicable only if $\boldsymbol{L}$ exists), then the integer vectors
$\boldsymbol{u}$ are enumerated according to the diagonal elements of
$\boldsymbol{L}$. In the encoding process, $\boldsymbol{d}\boldsymbol{L}$ are
defined to be integer vectors in the fundamental parallelotope of
$\Lambda_{\mathrm{s}}$. The constellation points $\boldsymbol{x}\in\Gamma$ can
be labeled by unique values of $\boldsymbol{d}\boldsymbol{L}$ and
$\boldsymbol{v}\in\mathbb{Z}^{n}$ as

$\displaystyle\boldsymbol{x}=\boldsymbol{d}\boldsymbol{L}+\boldsymbol{v}\boldsymbol{L}-\boldsymbol{a}.$
(13)

However, $\boldsymbol{d}\boldsymbol{L}$ are not guaranteed to be integer
vectors for arbitrary shaping lattices, thus making Ferdinand’s algorithms
less general than Kurkoski’s algorithms. The condition for Ferdinand’s
algorithms to be applicable is

$\displaystyle\frac{L_{ij}}{L_{ii}}\in\mathbb{Z},\forall
i={1,\ldots,n},~{}1\leq j<i.$ (14)

The decoding can be done sequentially, beginning from $u_{n}$, thanks to the
triangular structure of $\boldsymbol{L}$.

Kurkoski’s algorithms are also applicable only if the lower-triangular matrix
$\boldsymbol{L}$ exists. Then every point $\boldsymbol{x}\in\Gamma$ can be
uniquely enumerated by vectors $\boldsymbol{u}$ and $\boldsymbol{v}$ such that

$\displaystyle\boldsymbol{x}=\boldsymbol{u}+\boldsymbol{v}\boldsymbol{G}_{\mathrm{s}}-\boldsymbol{a},$
(15)

where $u_{i}\in\\{0,\ldots,L_{ii}-1\\}$ for $i=1,\ldots,n$ and
$\boldsymbol{v}\in\mathbb{Z}^{n}$. There are
$M=\\!\det\boldsymbol{L}=\prod_{i}L_{ii}$ possible values of $\boldsymbol{u}$,
and each of them occurs exactly once among all points
$\boldsymbol{x}\in\Gamma$. The decoding process is the same as Ferdinand’s.

Given the same $\boldsymbol{G}_{\mathrm{s}}$, Feng’s and Ferdinand’s
algorithms can have different mapping rules, and Kurkoski’s algorithms provide
a third mapping rule, see the numerical example in this section. When Feng’s
$\boldsymbol{u}\boldsymbol{T}^{-1}$ and Ferdinand’s
$\boldsymbol{d}\boldsymbol{L}$ are equal, their algorithms are equivalent. For
most commonly used shaping lattices, e.g., $D_{4}$, $E_{8}$, $\Lambda_{16}$,
and $\Lambda_{24}$ [27, Ch. 4], Ferdinand’s algorithms are applicable. Feng’s
algorithms can have the same mapping rule as Ferdinand’s algorithms, when the
generator matrices are written in nice lower-triangular matrices as in [27,
Ch. 4].

Apparently Feng’s algorithms are more general than Kurkoski’s, which are in
turn slightly more general than Ferdinand’s. However, for the case where all
three algorithms are applicable, e.g., for commonly used multidimensional
shaping lattices, Kurkoski’s algorithms generally provide better labelings of
constellation points. When a Gray code is applied to label the integer
coordinates of $\boldsymbol{u}$, i.e., converting $u_{i}$ to a binary
reflected Gray code for $i=1,\ldots,n$, each pair of nearest $\boldsymbol{u}$
in terms of Euclidean distance differs by exactly one bit. Kurkoski’s
algorithms allow for directly mapping $\boldsymbol{u}$ to constellation
points, thus making most of the constellation points have Gray neighbors,
which we call pseudo-Gray labeling. In Feng’s and Ferdinand’s encoding
algorithms, $\boldsymbol{u}$ is multiplied by a matrix, which changes the
neighbor relationships between constellation points. Kurkoski’s algorithms
allow for this pseudo-Gray labeling for VCs, and can thus achieve a smaller
Gray penalty and better BER performance [24] than Feng’s and Ferdinand’s
algorithms. Throughout this paper, we adopt Kurkoski’s encoding and decoding
and this pseudo-Gray labeling scheme.

(a)

(b)

(c)

Figure 1: Example: different integer mapping rules for a two-dimensional VC.
The blue filled points are encoded into points in the shifted Voronoi region
$\boldsymbol{a}+\Omega(\Lambda_{\mathrm{s}})$ (the light blue region) in
encoding.

_Example:_ We consider a two-dimensional VC for which the generator matrices
of $\Lambda_{\mathrm{s}}$ and $\Lambda$ are

$\displaystyle\boldsymbol{G}_{\mathrm{s}}=\begin{pmatrix}6&0\\\
4&4\end{pmatrix},\;\boldsymbol{G}=\begin{pmatrix}1&0\\\ 0&1\end{pmatrix},$
(16)

and the offset vector $\boldsymbol{a}=(-1/2,0)$.

In Feng’s algorithms, the Smith normal form
$\boldsymbol{J}=\boldsymbol{S}\boldsymbol{G}_{\mathrm{s}}\boldsymbol{T}$ is

$\displaystyle\boldsymbol{J}=\begin{pmatrix}2&0\\\
0&12\end{pmatrix},\;\boldsymbol{S}=\begin{pmatrix}1&1\\\
-2&-3\end{pmatrix},\;\boldsymbol{T}=\begin{pmatrix}1&2\\\ -2&-5\end{pmatrix}.$
(17)

Then the integer vectors $\boldsymbol{u}=(u_{1},u_{2})$ are defined as
${u_{1}\in\\{0,1\\}}$ and $u_{2}\in\\{0,\ldots,11\\}$. The vectors
$\boldsymbol{u}\boldsymbol{T}^{-1}$ are calculated as

$\displaystyle\boldsymbol{u}\boldsymbol{T}^{-1}=\begin{pmatrix}u_{1}&u_{2}\end{pmatrix}\begin{pmatrix}5&2\\\
-2&-1\end{pmatrix}=\begin{pmatrix}5u_{1}-2u_{2}&2u_{1}-u_{2}\end{pmatrix}.$
(18)

In Ferdinand’s algorithms, $\boldsymbol{L}=\boldsymbol{G}_{\mathrm{s}}$ and
$\boldsymbol{u}$ are enumerated as $u_{1}\in\\{0,\ldots,5\\}$ and
$u_{2}\in\\{0,\ldots,3\\}$. The vectors $\boldsymbol{d}\boldsymbol{L}$ are
computed by

$\displaystyle\boldsymbol{d}\boldsymbol{L}=\begin{pmatrix}u_{1}/6&u_{2}/4\end{pmatrix}\begin{pmatrix}6&0\\\
4&4\end{pmatrix}=\begin{pmatrix}u_{1}+u_{2}&u_{2}\end{pmatrix}.$ (19)

In Kurkoski’s algorithms, $\boldsymbol{L}=\boldsymbol{G}_{\mathrm{s}}$ and
$\boldsymbol{u}$ are enumerated as $u_{1}\in\\{0,\ldots,5\\}$ and
$u_{2}\in\\{0,\ldots,3\\}$.

Fig. 1 illustrates the three different mapping rules for this example, where
the vectors $\boldsymbol{u}\boldsymbol{T}^{-1}$ in Feng’s algorithms,
$\boldsymbol{d}\boldsymbol{L}$ in Ferdinand’s algorithms, and $\boldsymbol{u}$
in Kurkoski’s algorithms are highlighted. The enumeration of points in a
rectangular shape of Kurkoski’s algorithms help achieve a lower Gray penalty
and a lower BER [24].

##  IV Design of VCs

A VC based on the lattice partition $\Lambda/\Lambda_{\mathrm{s}}$ is defined
by (5). In this section, we discuss the choice of parameters of VCs based on
the lattice partition $\mathbb{Z}^{n}/\Lambda_{\mathrm{s}}$.

To minimize the average symbol energy defined by (7), the offset vector
$\boldsymbol{a}$ is optimized using an iterative algorithm given in [11]. This
algorithm in may converge to a suboptimal vector for $8$ and higher
dimensions, and cannot be exactly calculated when $M$ is very large. However,
as $M$ increases, the performance difference between VCs generated using the
optimal $\boldsymbol{a}$ and a random $\boldsymbol{a}\in\Omega(\Lambda)$
decreases, and can be neglected for large VCs, see [13, Fig. 3]. In this
paper, for a small or moderate-size VC ($M\leq 2^{17}\approx 1.3\times
10^{5}$), $\boldsymbol{a}$ was optimized using the method in [11], whereas for
very large VCs where we can only approximate the average symbol energy by
Monte Carlo simulations, a random $\boldsymbol{a}$ uniformly distributed in
$\Omega(\Lambda)$ was selected.

The shaping lattice $\Lambda_{\mathrm{s}}$ should have a high shaping gain and
low-complexity quantization algorithm. The most commonly-used multidimensional
shaping lattices: the $4$-dimensional checkerboard lattice $D_{4}$,
$8$-dimensional lattice $E_{8}$, $16$-dimensional Barnes–Wall lattice
$\Lambda_{16}$, the $24$-dimensional Leech lattice $\Lambda_{24}$ [27, Ch. 4],
and a suboptimal $32$-dimensional lattice $L_{32}$ are considered in this
paper. The $32$-dimensional lattice $L_{32}$ is constructed by applying
Construction B [27, Ch. 5] to the $(32,6,16)$ first order Reed–Muller code.
This lattice has a sublattice $2D_{32}$ of index $64$, which is beneficial,
since the closest lattice point quantizer dominates the complexity for the
encoding and decoding, especially for high-dimensional lattices. Compared with
$\Lambda_{24}$ which has a sublattice $4D_{24}$ of index $8192$ [33], the
complexity is reduced by a factor of $128$, while the shaping gain is only
$0.091$ dB less. Thus, $L_{32}$ can be considered as a good trade-off between
the shaping gain and decoding complexity. Table II shows the normalized second
moment $G(\Omega(\Lambda_{\mathrm{s}}))$ and shaping gains
$g_{s}(\Lambda_{\mathrm{s}})$ for these considered shaping lattices.

TABLE II: Asymptotic shaping gains and normalized second moments of Voronoi regions of some lattices. $\Lambda_{\mathrm{s}}$ | $D_{4}$ | $E_{8}$ | $\Lambda_{16}$ | $\Lambda_{24}$ | $L_{32}$
---|---|---|---|---|---
$G(\Omega(\Lambda_{\mathrm{s}}))$ | $0.0766$ | $0.0717$ | $0.0683$ | $0.0658$ | $0.0671$
$g_{\text{s}}(\Lambda_{\mathrm{s}})$ [dB] | $0.366$ | $0.653$ | $0.864$ | $1.026$ | $0.935$

A VC based on the lattice partition $\Lambda/\Lambda_{\mathrm{s}}$ with
${M=|\\!\det\boldsymbol{G}_{\mathrm{s}}|/|\\!\det\boldsymbol{G}|}$
constellation points can be scaled by any integer, i.e.,
$\Lambda/m\Lambda_{\mathrm{s}},\;m\in\mathbb{Z}$. The new VC after scaling has
a spectral efficiency of

$\displaystyle\beta$ $\displaystyle=\frac{2\log_{2}(|\\!\det
m^{n}\boldsymbol{G}_{\mathrm{s}}|/|\\!\det\boldsymbol{G}|)}{n}$
$\displaystyle=\frac{2\log_{2}(M)}{n}+2\log_{2}(m).$ (20)

A rotation of $None$ together with a scaling of $\sqrt{2}$ of the shaping
lattice $\Lambda_{\mathrm{s}}$ can provide $1$ more bit/symbol/dimension-pair.
This can be done for an even $n$ by multiplying the generator matrix
$\boldsymbol{G}_{\mathrm{s}}$ from the right side with an $n$-by-$n$ matrix
[36]

$\displaystyle\boldsymbol{R}=\begin{pmatrix}1&1&0&0&0&\cdots&0&0\\\
-1&1&0&0&0&\cdots&0&0\\\ 0&0&1&1&0&\cdots&0&0\\\ 0&0&-1&1&0&\cdots&0&0\\\
0&0&0&0&\ddots&~{}&\vdots&\vdots\\\
\vdots&\vdots&\vdots&\vdots&~{}&\ddots&0&0\\\ 0&0&0&0&\cdots&0&1&1\\\
0&0&0&0&\cdots&0&-1&1\end{pmatrix},$ (21)

which operates on every dimension-pair of $\Lambda_{\mathrm{s}}$, with a
determinant of $2^{n/2}$. The generator matrix of the new shaping lattice
$m\Lambda_{\mathrm{s}}\boldsymbol{R}$ (which remains a sublattice of
$\Lambda$) is $m\boldsymbol{G}_{\mathrm{s}}\boldsymbol{R}$, and the closest
point quantizer becomes

$\displaystyle\mathcal{Q}_{m\Lambda_{\mathrm{s}}\boldsymbol{R}}(\boldsymbol{x})=m\mathcal{Q}_{\Lambda_{\mathrm{s}}}(\frac{1}{m}\boldsymbol{x}\boldsymbol{R}^{-1})\boldsymbol{R}$
(22)

by (3). The new VC based on the lattice partition
$\Lambda/m\Lambda_{\mathrm{s}}\boldsymbol{R}$ has a spectral efficiency of

$\displaystyle\beta$ $\displaystyle=\frac{2\log_{2}(|\\!\det
m^{n}\boldsymbol{G}_{\mathrm{s}}\boldsymbol{R}|/|\\!\det\boldsymbol{G}|)}{n}$
$\displaystyle=\frac{2\log_{2}(M)}{n}+2\log_{2}(m)+1.$ (23)

In order to make bit mapping possible, both $M$ and $m$ must be powers of $2$.
With $m$ an arbitrary power of $2$, $\Lambda/m\Lambda_{s}$ gives a resolution
of $2$ bits/symbol/dimension-pair according to (20). However,
$\Lambda/m\Lambda_{s}\boldsymbol{R}$ offers the intermediate spectral
efficiencies as in (23), which decreases the overall resolution to $1$
bit/symbol/dimension-pair. Also, the combination of different shaping and
coding lattices can lead to a more granular set of possible spectral
efficiencies, which allows us to have more flexibility in choosing data rates
as needed. In Fig. 2, the shaping gain $g_{\text{s}}$ as a function of $\beta$
is presented for VCs with a cubic coding lattice and the considered shaping
lattices in Table II. Larger markers show the spectral efficiencies for bit
mapping; smaller markers show the finer-grained granularity of spectral
efficiencies without considering bit mapping, where $m$ does not have to be a
power of $2$.

$0$$2$$4$$6$$8$$10$$12$$0.2$$0.4$$0.6$$0.8$$1$$1.2$$\beta$
[bits/symbol/dimension-pair]APE gain $g$
[dB]$\mathbb{Z}^{4}/D_{4}$$\mathbb{Z}^{8}/E_{8}$$\mathbb{Z}^{16}/\Lambda_{16}$$\mathbb{Z}^{24}/\Lambda_{24}$$\mathbb{Z}^{32}/L_{32}$$g_{\text{s}}(\Lambda_{\mathrm{s}})$
Figure 2: The APE gain $g$ as a function of $\beta$ for VCs with a cubic
coding lattice. The smaller markers on top of the lines represent the cases in
which the scaling factor is not a power of $2$. The black dashed lines are the
asymptotic shaping gains $g_{\text{s}}(\Lambda_{\mathrm{s}})$ for these
shaping lattices stated in Table II.

##  V Achievable Information Rates

AIRs indicate the maximum amount of information that can be transmitted
reliably over the underlying channel. It assumes a perfect channel code with
an infinite blocklength, thus can be used as an upper bound of the performance
of coded modulation [37]. For very large VCs, the calculation of MI is
challenging, since it requires the coordinates of all constellation points. In
this section, we propose an MI estimation method and a log-likelihood (LLR)
estimation method for very large constellations and apply these methods to VCs
with a cubic coding lattice. The MI of our designed VCs is investigated, and
their AIRs are compared with conventional scaled VCs when an LDPC code is
applied.

###  V-A MI estimation method for very large constellations

For a memoryless discrete channel, the MI between the equally probable
transmitted symbols $\boldsymbol{X}$ and the received noisy symbols
$\boldsymbol{Y}$ can be written as

$\displaystyle
I(\boldsymbol{X};\boldsymbol{Y})\triangleq\frac{1}{M}\sum_{i=1}^{M}\int_{\mathbb{C}^{n}}f_{\boldsymbol{Y}|\boldsymbol{X}}(\boldsymbol{y}|\boldsymbol{x}_{i})\log\frac{f_{\boldsymbol{Y}|\boldsymbol{X}}(\boldsymbol{y}|\boldsymbol{x}_{i})}{f_{\boldsymbol{Y}}(\boldsymbol{y})}d\boldsymbol{y},$
(24)

where $\boldsymbol{x}_{i}$ for $i=1,\ldots,M$ form the constellation
$\mathcal{X}$. By applying Monte Carlo integration, the MI can be approximated
as

$\displaystyle I(\boldsymbol{X};\boldsymbol{Y})$
$\displaystyle\approx\frac{1}{N_{\text{s}}}\sum_{i=1}^{N_{\text{s}}}\int_{\mathbb{C}^{n}}f_{\boldsymbol{Y}|\boldsymbol{X}}(\boldsymbol{y}|\boldsymbol{x}_{i})\log\frac{f_{\boldsymbol{Y}|\boldsymbol{X}}(\boldsymbol{y}|\boldsymbol{x}_{i})}{f_{\boldsymbol{Y}}(\boldsymbol{y})}d\boldsymbol{y}$
(25)
$\displaystyle\approx\frac{1}{N_{\text{s}}}\sum_{i=1}^{N_{\text{s}}}\log\frac{f_{\boldsymbol{Y}|\boldsymbol{X}}(\boldsymbol{y}_{i}|\boldsymbol{x}_{i})}{f_{\boldsymbol{Y}}(\boldsymbol{y}_{i})},$
(26)

where $\boldsymbol{x}_{i}$ for $i=1,2,\ldots,N_{\text{s}}$ are $N_{\text{s}}$
symbols drawn uniformly from $\mathcal{X}$, and given a certain
$\boldsymbol{x}_{i}$, $\boldsymbol{y}_{i}$ is drawn from the conditional
distribution of the channel
$f_{\boldsymbol{Y}|\boldsymbol{X}}(\boldsymbol{y}_{i}|\boldsymbol{x}_{i})$.

To numerically estimate (26), the key point is to calculate the marginal
distribution of $\boldsymbol{y}$

$\displaystyle f_{\boldsymbol{Y}}(\boldsymbol{y})$
$\displaystyle=\frac{1}{M}\sum_{\boldsymbol{x}\in\mathcal{X}}f_{\boldsymbol{Y}|\boldsymbol{X}}(\boldsymbol{y}|\boldsymbol{x}).$
(27)

The exact calculation of $f_{\boldsymbol{Y}}(\boldsymbol{y})$ using (27)
requires storing all $M$ constellation points, which is infeasible when $M$ is
very large. Furthermore, approximating $f_{\boldsymbol{Y}}(\boldsymbol{y})$ by
standard Monte-Carlo techniques is very inaccurate, because for most realistic
channel laws
$f_{\boldsymbol{Y}|\boldsymbol{X}}(\boldsymbol{y}|\boldsymbol{x})$, only a
tiny fraction of all constellation points $\boldsymbol{x}$ contribute
significantly to the sum in (27).

To approximate (27), we propose a method based on _importance sampling_ ,
which is a weighted sampling method that oversamples from the important region
we are interested in, thus making Monte Carlo feasible [38, Ch. 9]. This
concept has been used in the machine learning field to estimated the MI
between the original data and the learned representation [39], but as far as
we know never to estimate the MI of a communication channel. The classic
importance sampling approach is to sample from a new importance distribution
that is proportional to the product of the distribution of the integral
variable and the integrand [38, Eq. (9.3)], to resemble the true expectation.
For example, to simulate (27) in our case, the importance distribution of
$\boldsymbol{x}\in\mathcal{X}$ should be proportional to
$(1/M)f_{\boldsymbol{Y}|\boldsymbol{X}}(\boldsymbol{y}|\boldsymbol{x})$. For
the MI estimation problem, we refine this concept by using a step-wise
sampling rule, in which we only sample symbols from an important set
$\mathcal{I}(\boldsymbol{y})$ which contains points that have an important
contribution to $f_{\boldsymbol{Y}}(\boldsymbol{y})$, and no samples are
sampled from the complementary set $\mathcal{X}-\mathcal{I}(\boldsymbol{y})$
since their contribution to $f_{\boldsymbol{Y}}(\boldsymbol{y})$ is negligible
compared with $\mathcal{I}(\boldsymbol{y})$. The important set
$\mathcal{I}(\boldsymbol{y})$ is divided into $D$ disjoint subsets
$\mathcal{I}_{d}(\boldsymbol{y})$ for $d=1,\ldots,D$. The contribution to
$f_{\boldsymbol{Y}}(\boldsymbol{y})$ from each subset
$\mathcal{I}_{d}(\boldsymbol{y})$ can be either calculated by enumerating
every symbol in $\mathcal{I}_{d}(\boldsymbol{y})$, or estimated by performing
a uniform Monte Carlo sampling in $\mathcal{I}_{d}(\boldsymbol{y})$. Thus, the
sum in (27) can be approximated as

$\displaystyle f_{\boldsymbol{Y}}(\boldsymbol{y})$
$\displaystyle\approx\frac{1}{M}\sum_{\boldsymbol{x}\in\mathcal{I}(\boldsymbol{y})}f_{\boldsymbol{Y}|\boldsymbol{X}}(\boldsymbol{y}|\boldsymbol{x})$
(28)
$\displaystyle\approx\frac{1}{M}\sum_{d=1}^{D}\frac{|\mathcal{I}_{d}(\boldsymbol{y})|}{K_{d}}\sum_{j=1}^{K_{d}}f_{\boldsymbol{Y}|\boldsymbol{X}}(\boldsymbol{y}|\boldsymbol{x}_{d,j}),$
(29)

where $\boldsymbol{x}_{d,j}$ for $j=1,\ldots,K_{d}$ are all points from
$\mathcal{I}_{d}(\boldsymbol{y})$ if
${K_{d}=|\mathcal{I}_{d}(\boldsymbol{y})|}$, or $K_{d}$ uniform random samples
from $\mathcal{I}_{d}(\boldsymbol{y})$ if
${K_{d}<|\mathcal{I}_{d}(\boldsymbol{y})|}$. For accurate results, the
sampling sets $\mathcal{I}(\boldsymbol{y})$ and
$\mathcal{I}_{d}(\boldsymbol{y})$, but not necessarily their sizes $K_{d}$,
should be chosen as functions of $\boldsymbol{y}$.

We propose (29) as a very general way to estimate
$f_{\boldsymbol{Y}}(\boldsymbol{y})$ and thereby the MI and related
quantities. The proposed MI estimation method is a special case of importance
sampling. Unlike the importance distribution in classical importance sampling,
which should be more “continuous”, our refined step-wise sampling rule makes
random generation of $\boldsymbol{x}$ easier. As the number of the elements in
$\mathcal{I}(\boldsymbol{y})$ increases, the estimated distribution
$f_{\boldsymbol{Y}}(\boldsymbol{y})$ in (28) should converge to the exact
value. As a special case, setting $\mathcal{I}(\boldsymbol{y})=\mathcal{X}$
and $D=1$ in (29) yields the exact expression (27) if $K_{1}=M$ and a standard
Monte Carlo estimate thereof if $K_{1}<M$. The same idea can be applied to
other structured constellations, or other similar problems. The readers can
derive their own estimation rules from (29) for a specific channel and
constellation.

###  V-B MI estimation for the designed VCs

We consider an $n$-dimensional real AWGN channel, which has the conditional
distribution

$\displaystyle
f_{\boldsymbol{Y}|\boldsymbol{X}}(\boldsymbol{y}|\boldsymbol{x})=\frac{1}{(2\pi\sigma^{2}/n)^{n/2}}\exp{(-\frac{\left\|\boldsymbol{y}-\boldsymbol{x}\right\|^{2}}{2\sigma^{2}/n})},$
(30)

where $\sigma^{2}$ is the total noise power. We define the signal-to-noise
ratio (SNR) as $E_{\text{s}}/\sigma^{2}$.

For estimating the MI of our VCs with a cubic coding lattice, first, given a
received noisy symbol $\boldsymbol{y}$, we define a Euclidean ball
$\mathcal{B}(\boldsymbol{y},R)$ containing all $n$-dimensional points in the
translated cubic coding lattice having a Euclidean distance within $R$ from
the nearest integer vector of $\boldsymbol{y}+$, i.e.,

$\displaystyle\mathcal{B}(\boldsymbol{y},R)\triangleq\\{\boldsymbol{x}:\|\boldsymbol{x}+\left\lfloor\boldsymbol{y}+\right\rceil\|\leq
R,~{}\boldsymbol{x}+\in\mathbb{Z}^{n}\\},$ (31)

where the squared radius $R^{2}\in\mathbb{N}$. The Euclidean ball
$\mathcal{B}(\boldsymbol{y},R)$ consists of $R^{2}+1$ Euclidean “shells”, each
of which contains all $n$-dimensional points in the translated cubic coding
lattice having a Euclidean distance of $r$ from
$\left\lfloor\boldsymbol{y}+\right\rceil$, i.e.,

$\displaystyle\mathcal{S}(\boldsymbol{y},r)\triangleq\\{\boldsymbol{x}:\|\boldsymbol{x}+\left\lfloor\boldsymbol{y}+\rceil\right\|=r,~{}\boldsymbol{x}+\in\mathbb{Z}^{n}\\},$
(32)

for $r^{2}=0,1,\ldots,R^{2}$. The number of points in each shell
$\mathcal{S}(\boldsymbol{y},r)$ of a Euclidean ball
$\mathcal{B}(\boldsymbol{y},R)$ are listed in Table III.

TABLE III: The number of points in each shell $\mathcal{S}(\boldsymbol{y},r)$ of the Euclidean ball $\mathcal{B}(\boldsymbol{y},R)$ ($n\geq 4$ in this table). $r^{2}$ | $0$ | $1$ | $2$ | $3$ | $4$ | $\ldots$
---|---|---|---|---|---|---
$|\mathcal{S}(\boldsymbol{y},r)|$ | $1$ | $2n$ | $2^{2}{n\choose 2}$ | $2^{3}{n\choose 3}$ | $2^{4}{n\choose 4}+2{n\choose 1}$ | $\ldots$

The important set is defined as all points in $\mathcal{B}(\boldsymbol{y},R)$
that belong to $\Gamma$ at the same time, i.e.,

$\displaystyle\mathcal{I}(\boldsymbol{y},R)=\mathcal{B}(\boldsymbol{y},R)\cap\Gamma,$
(33)

which consists of $D=R^{2}+1$ disjoint subsets
$\mathcal{I}_{d}(\boldsymbol{y})$ for $d=1,\ldots,D$. Each subset
$\mathcal{I}_{d}(\boldsymbol{y})$ contains all points in
$\mathcal{S}(\boldsymbol{y},\sqrt{d-1})$ that also belong to $\Gamma$, i.e.,
${\mathcal{I}_{d}(\boldsymbol{y})=\mathcal{S}(\boldsymbol{y},\sqrt{d-1})\cap\Gamma}$.

How should $K_{d}$ and $D$ be chosen for accurate estimation? Heuristically,
we have found that $K_{d}=\min\\{|\mathcal{I}_{d}(\boldsymbol{y})|,10^{4}\\}$
works well for all $d=1,\ldots,D$, which means that the contributions to (29)
from small enough subsets are computed exactly, whereas large subsets are
sampled using $10^{4}$ random points. To determine $D$, we evaluate (29) for
increasing values of $D$ until the relative increase is less than $0.5\%$.
More precisely, denoting the estimated $f_{\boldsymbol{Y}}(\boldsymbol{y})$
using (29) for a certain $D$ by $f_{\boldsymbol{Y}}^{(D)}(\boldsymbol{y})$, we
choose the smallest integer $D$ for which

$\displaystyle\max\left(\frac{f_{\boldsymbol{Y}}^{(D+1)}(\boldsymbol{y})-f_{\boldsymbol{Y}}^{(D)}(\boldsymbol{y})}{f_{\boldsymbol{Y}}^{(D)}(\boldsymbol{y})}\right)<0.5\%,$
(34)

where the maximum is taken over multiple random vectors $\boldsymbol{y}$ and
multiple Monte-Carlo realizations of (29). If a range of SNRs is being
considered, we usually apply the criterion (34) to the lowest SNR, which
intuitively needs the largest number of subsets, and then use the obtained
value of $D$ throughout the SNR range. Alternatively, (34) can be evaluated
separately for each SNR to save complexity. With these parameters, (29) is
able to estimate $f_{\boldsymbol{Y}}(\boldsymbol{y})$ accurately for VCs with
up to $M=16777216$ points for all SNRs. For larger constellations where we
have no benchmarks to compare with, we conjecture that this method is still
valid. After having reliable estimated values of
$f_{\boldsymbol{Y}}(\boldsymbol{y})$, the MI can be estimated accurately by
(26).

_Example 1:_ We consider a moderate-size VC based on the lattice partition
$\mathbb{Z}^{4}/16D_{4}$ with $M=131072$ constellation points. For better
visualization, we show $pf_{\boldsymbol{Y}}^{(D)}(\boldsymbol{y})$ as a
function of $D$ upon receiving a noisy symbol $\boldsymbol{y}$ in Fig. 3,
where $p=(2\pi\sigma^{2}/n)^{n/2}$ is a constant for a given $\sigma^{2}$. The
benchmark values $pf_{\boldsymbol{Y}}(\boldsymbol{y})$ are calculated using
(27). As $D$ increases, the estimated values all converge to the exact values
for different SNRs in Fig. 3.

$1/1$$5/89$$9/321$$13/761$$17/1281$$21/4785$$10^{-7}$$10^{-6}$$10^{-5}$$10^{-4}$$10^{-3}$SNR
$=14\;$dBSNR $=16\;$dBSNR $=18\;$dBSNR $=20\;$dBSNR $=22\;$dBSNR $=24\;$dBSNR
$=26\;$dBSNR $=28\;$dB$D$ and
$|\mathcal{B}(\boldsymbol{y},\sqrt{D-1})|$$pf_{\boldsymbol{Y}}^{(D)}(\boldsymbol{y})$
Figure 3: The estimated value $pf_{\boldsymbol{Y}}^{(D)}(\boldsymbol{y})$ as a
function of $D$ for different SNRs (solid curves with markers). The black
dashed lines are the corresponding benchmark values
$pf_{\boldsymbol{Y}}(\boldsymbol{y})$. The number after the ‘/’ is the
corresponding $|\mathcal{B}(\boldsymbol{y},\sqrt{D-1})|$.

_Example 2:_ We consider a larger-size VC of the lattice partition
$\mathbb{Z}^{8}/8E_{8}$ with $M=16777216$ constellation points. Table IV lists
the minimum required $D$ found by (34) and the corresponding number of symbols
in $\mathcal{B}(\boldsymbol{y},\sqrt{D-1}))$ at different SNRs, which shows
that $|\mathcal{B}(\boldsymbol{y},\sqrt{D-1})|$ grows fast as the SNR
decreases. Fig. 4 shows the convergence of
$pf_{\boldsymbol{Y}}^{(D)}(\boldsymbol{y})$ to
$pf_{\boldsymbol{Y}}(\boldsymbol{y})$ at medium SNR range. We observe from
Fig. 4 that the chosen values of $D$ in Table IV are sufficient to approach
$f_{\boldsymbol{Y}}(\boldsymbol{y})$ correctly for these SNR values.

TABLE IV: The minimum required $D$ and number of points in $\mathcal{B}(\boldsymbol{y},\sqrt{D-1})$ for the convergence of $f_{\boldsymbol{Y}}^{(D)}(\boldsymbol{y})$ to $f_{\boldsymbol{Y}}(\boldsymbol{y})$ for the VC of the lattice partition $\mathbb{Z}^{8}/8E_{8}$ at different SNRs. SNR | $16$ | $14$ | $12$ | $10$ | $8$ | $6$
---|---|---|---|---|---|---
$D$ | $5$ | $6$ | $8$ | $11$ | $16$ | $23$
$|\mathcal{B}(8,\sqrt{D-1})|$ | $1713$ | $3729$ | $12369$ | $47921$ | $231185$ | $1025649$
$10$$20$$30$$10^{-9}$$10^{-7}$$10^{-5}$SNR $=6\;$dBSNR $=8\;$dBSNR
$=10\;$dBSNR $=12\;$dBSNR $=14\;$dBSNR $=16\;$dBSNR $=18\;$dBSNR
$=20\;$dB$D$$pf_{\boldsymbol{Y}}^{(D)}(\boldsymbol{y})$ Figure 4: The
estimated value $pf_{\boldsymbol{Y}}^{(D)}(\boldsymbol{y})$ as a function of
$D$ for different SNRs. Solid lines without markers are estimated with
$K_{d}=|\mathcal{I}_{d}(\boldsymbol{y})|$ for all subsets. The markers are
estimated with $K_{d}=10^{4}$ uniform samples from
$\mathcal{I}_{d}(\boldsymbol{y})$ for subsets with $d>8$ and
$K_{r}=|\mathcal{I}_{d}(\boldsymbol{y})|$ for subsets with $1\leq d\leq 8$.
The black dashed lines are the corresponding benchmark values
$pf_{\boldsymbol{Y}}(\boldsymbol{y})$.

###  V-C LLR approximation for very large constellations

We propose an LLR approximation method for very large constellations and
exemplify it for our designed VCs and the scaled VCs.

For transmission of a constellation $\mathcal{X}$ through a given channel with
conditional distribution
$f_{\boldsymbol{Y}|\boldsymbol{X}}(\boldsymbol{y}|\boldsymbol{x})$, upon
receiving a noisy symbol $\boldsymbol{y}$, the LLR of a certain bit $b_{i}$,
for $i=1,2,\ldots,\log_{2}(|\mathcal{X}|)$, is defined as

$\displaystyle\text{LLR}(b_{i}|\boldsymbol{y})$
$\displaystyle\triangleq\log{\frac{\text{Pr}(b_{i}=0|\boldsymbol{y})}{\text{Pr}(b_{i}=1|\boldsymbol{y})}}$
$\displaystyle=\log\frac{\sum_{\boldsymbol{x}\in\mathcal{X}^{(i,0)}}f_{\boldsymbol{Y}|\boldsymbol{X}}(\boldsymbol{y}|\boldsymbol{x})}{\sum_{\boldsymbol{x}\in\mathcal{X}^{(i,1)}}f_{\boldsymbol{Y}|\boldsymbol{X}}(\boldsymbol{y}|\boldsymbol{x})},$
(35)

where $\mathcal{X}^{(i,0)}$ and $\mathcal{X}^{(i,1)}$ are the sets of
constellation points with $0$ and $1$ at position $i$, respectively. The exact
LLR calculated using the whole constellation is accurate but too complex to
compute, which can be approximated by only considering the most likely
constellation point with $b_{i}=0$ (or $b_{i}=1$), i.e.,

$\displaystyle\text{LLR}(b_{i}|\boldsymbol{y})\approx\log\frac{\max_{\boldsymbol{x}\in\mathcal{X}^{(i,0)}}f_{\boldsymbol{Y}|\boldsymbol{X}}(\boldsymbol{y}|\boldsymbol{x})}{\max_{\boldsymbol{x}\in\mathcal{X}^{(i,1)}}f_{\boldsymbol{Y}|\boldsymbol{X}}(\boldsymbol{y}|\boldsymbol{x})}.$
(36)

However, for very large constellations, searching for the most likely
constellation point with $b_{i}=0$ and $b_{i}=1$ from the whole constellation
is still infeasible.

We propose a similar technique as our MI estimation method in V-A to further
approximate the LLR. Instead of searching points from $\mathcal{X}$, we only
search the closest point from an important set $\mathcal{I}(\boldsymbol{y})$.
Specifically, the LLR in (36) is further approximated as

$\displaystyle\text{LLR}(b_{i}|\boldsymbol{y})\approx\log\frac{\max_{\boldsymbol{x}\in\mathcal{I}^{(i,0)}(\boldsymbol{y})}f_{\boldsymbol{Y}|\boldsymbol{X}}(\boldsymbol{y}|\boldsymbol{x})}{\max_{\boldsymbol{x}\in\mathcal{I}^{(i,1)}(\boldsymbol{y})}f_{\boldsymbol{Y}|\boldsymbol{X}}(\boldsymbol{y}|\boldsymbol{x})},$
(37)

where
$\mathcal{I}^{(i,0)}(\boldsymbol{y})=\mathcal{X}^{(i,0)}\cap\mathcal{I}(\boldsymbol{y})$
and
$\mathcal{I}^{(i,1)}(\boldsymbol{y})=\mathcal{X}^{(i,1)}\cap\mathcal{I}(\boldsymbol{y})$.
If there is no constellation point in $\mathcal{I}^{(i,0)}(\boldsymbol{y})$
(or $\mathcal{I}^{(i,1)}(\boldsymbol{y})$), we assume the most likely
constellation point has a small probability, i.e., setting
$\max_{\boldsymbol{x}\in\mathcal{I}^{(i,0)}(\boldsymbol{y})}f_{\boldsymbol{Y}|\boldsymbol{X}}(\boldsymbol{y}|\boldsymbol{x})$
(or
$\max_{\boldsymbol{x}\in\mathcal{I}^{(i,1)}(\boldsymbol{y})}f_{\boldsymbol{Y}|\boldsymbol{X}}(\boldsymbol{y}|\boldsymbol{x})$)
to a small default value.

For the AWGN channel, the widely-used approximate LLR derived from (36) is

$\displaystyle\text{LLR}(b_{i}|\boldsymbol{y})\approx$
$\displaystyle-\frac{1}{2\sigma^{2}/n}\left(\min_{\boldsymbol{x}\in\mathcal{X}^{(i,0)}}(\|\boldsymbol{y}-\boldsymbol{x}\|^{2})-\min_{\boldsymbol{x}\in\mathcal{X}^{(i,1)}}(\|\boldsymbol{y}-\boldsymbol{x}\|^{2})\right),$
(38)

where only the nearest constellation point with $b_{i}=0$ (or $b_{i}=1$) to
$\boldsymbol{y}$ are considered [40, Eq. (6)]. Analogously with (37), we
further approximate (38) as

$\displaystyle\text{LLR}(b_{i}|\boldsymbol{y})\approx$
$\displaystyle-\frac{1}{2\sigma^{2}/n}\left(\min_{\boldsymbol{x}\in\mathcal{I}^{(i,0)}(\boldsymbol{y})}(\|\boldsymbol{y}-\boldsymbol{x}\|^{2})-\min_{\boldsymbol{x}\in\mathcal{I}^{(i,1)}(\boldsymbol{y})}(\|\boldsymbol{y}-\boldsymbol{x}\|^{2})\right),$
(39)

For our designed VCs with a cubic coding lattice, the important set is defined
as in (33) with a radius $R$. This parameter provides a trade-off between low
computational complexity (small $R$) and good decoding performance (high $R$).
If ${\mathcal{I}^{(i,0)}(\boldsymbol{y})=\varnothing}$, then setting
${\max_{\boldsymbol{x}\in\mathcal{I}^{(i,0)}(\boldsymbol{y})}f_{\boldsymbol{Y}|\boldsymbol{X}}(\boldsymbol{y}|\boldsymbol{x})}$
to a small probability is equivalent to setting
${\min_{\boldsymbol{x}\in\mathcal{I}^{(i,0)}(\boldsymbol{y})}\|\boldsymbol{y}-\boldsymbol{x}\|^{2}}$
to a large default value $q$ which is larger than $R^{2}$, and the same rule
applies to $\mathcal{I}^{(i,1)}(\boldsymbol{y})$. A default value close to the
boundary of the important region (e.g., $q=R^{2}+1$) is usually not a good
choice, neither a very large $q$ (e.g., $q=100R^{2}$). The decoding
performance can be roughly optimized by testing different $q$ for a given $R$.

Similarly, for very large scaled VCs, the important set can be generalized as

$\displaystyle\mathcal{I}(\boldsymbol{y})\triangleq\\{\boldsymbol{x}:\|\boldsymbol{x}+\mathcal{Q}_{\Lambda}(\boldsymbol{y}+)\|\leq
R,\boldsymbol{x}\in\Gamma\\}.$ (40)

Then (37) can be used to estimate the LLR for the scaled VCs.

###  V-D Results

Fig. 5 shows the estimated MI for multidimensional VCs using our proposed
estimation method in V-A and parameters are chosen as suggested in V-B. To
validate the correctness of our estimation, the MI simulated with the exact
$f_{\boldsymbol{Y}}(\boldsymbol{y})$ in (27) for some moderate-size VCs are
included as benchmarks. It shows that our estimated MI is consistent with the
benchmark MIs (markers). With $L_{32}$ as the shaping lattice, at SNR $=45$
dB, we can observe the maximum $0.935$ dB shaping gain. At SNR $=25$ dB, the
gap to capacity is reduced from $1.33$ dB to $0.48$ dB compared with the QAM
constellation.

$10$$20$$30$$40$$5$$10$$15$$1.53$ dB$0.48$ dB$0.935$ dBSNR [dB]MI
[bits/symbol/dimension-
pair]AWGNCapacityQAM$\mathbb{Z}^{4}/2^{4}D_{4}$$\mathbb{Z}^{8}/2^{3}E_{8}$$\mathbb{Z}^{32}/2^{4}L_{32}$$\mathbb{Z}^{16}/2^{5}L_{32}$$\mathbb{Z}^{32}/2^{6}L_{32}$$\mathbb{Z}^{32}/2^{7}L_{32}$
Figure 5: The estimated MI as a function of the SNR for multidimensional VCs
(solid curves without markers). The markers are the MI estimated using the
exact $f_{\boldsymbol{Y}}(\boldsymbol{y})$ by (27).

We also investigate the performance of our VCs in coded systems. An LDPC
code333The codeword length is $64800$ and $50$ decoding iterations are used.
from the digital video broadcasting (DVB-S2) standard [41] with multiple code
rates are applied to our designed VCs. Our proposed LLR approximation in (39)
is applied. Fig. 6 shows the estimated required SNRs to achieve a BER below
$10^{-4}$ after LDPC decoding for the VCs based on the lattice partition
$\mathbb{Z}^{4}/2^{6}D_{4}$ ($R^{2}=20,\;q=50$), $\mathbb{Z}^{8}/2^{6}E_{8}$
($R^{2}=6,\;q=20$), $\mathbb{Z}^{16}/2^{6}\Lambda_{16}$ ($R=3,\;q=20$), and
$\mathbb{Z}^{32}/2^{6}L_{32}$ ($R^{2}=2,\;q=13$). The default values $q$ are
not globally optimized for different VCs, since our goal is not to design an
LDPC code to maximize the AIRs. For comparison, we present results for the
scaled VC based on the lattice partition $D_{4}/2^{4}D_{4}$ and our VC based
on the lattice partition $\mathbb{Z}^{4}/2^{4}D_{4}$ simulated using the LLR
in (38), i.e., without the further approximation in (39). The result shows
that our VC with a cubic coding lattice can have slightly higher AIRs than the
scaled VC. In this case, the loss of coding gain due to the cubic coding
lattice is more than compensated by the usage of a lower-rate LDPC code to
obtain the same net AIR, which is consistent with the BER improvements
observed in [24, Fig. 4]. The better AIR performance might come from that a
pseudo-Gray labeling is more efficient for the cubic coding lattice, since our
VC $\mathbb{Z}^{4}/2^{4}D_{4}$ has a Gray penalty of $1.01$, which is half of
that for the scaled VC $D_{4}/2^{4}D_{4}$ ($1.99$).

$20$$30$$40$$50$$0$$5$$10$SNR [dB]AIR [bits/symbol/dimension-pair]AWGN
CapacityMI QAMLDPC $\mathbb{Z}^{4}/2^{4}D_{4}$LDPC $D_{4}/2^{4}D_{4}$LDPC
$\mathbb{Z}^{4}/2^{6}D_{4}$LDPC $\mathbb{Z}^{8}/2^{6}E_{8}$LDPC
$\mathbb{Z}^{16}/2^{6}\Lambda_{16}$LDPC $\mathbb{Z}^{32}/2^{6}L_{32}$ Figure
6: The estimated AIR as a function of the SNR for multidimensional VCs with
the DVB-S2 LDPC codes. The code rate
$R_{\text{c}}\in\\{1/3,1/2,3/5,2/3,3/4,5/6,9/10\\}$.

##  VI Conclusion

We proposed Voronoi constellations with a cubic coding lattice, for which we
follow Kurkoski’s encoding and decoding algorithms and apply pseudo-Gray
labeling to minimize the BER. As a structured geometric shaping method, this
class of VC has high shaping gains of up to $1.03$ dB and low complexity.
Thanks to its cubic coding lattice, an MI estimation method for very large
constellation size based on importance sampling is proposed for the first
time, which enables us to observe an up to $0.85$ dB shaping gain for medium
SNR values. Our proposed LLR approximation method makes the analysis of AIRs
of our VCs in coded systems at high spectral efficiencies possible, which is
infeasible for the scaled VCs. Compared with the conventional scaled VCs, our
designed VCs have the advantages that 1) the decoding algorithm is simpler, 2)
the spectral efficiency for mapping integers to bits is improved to $1$
[bit/symbol/dimension-pair] realized by rotating and scaling the shaping
lattices, 3) the AIRs after combining with an LDPC code can be higher due to
our better pseudo-Gray labeling, and 4) analysing the MI and AIR becomes
feasible for very large constellation sizes.

## References

  * [1] G. D. Forney, Jr., R. G. Gallager, G. R. Lang, F. M. Longstaff, and S. U. Qureshi, “Efficient modulation for band-limited channels,” _IEEE J. Sel. Areas Commun._ , vol. 2, no. 5, pp. 632–647, 1984.
  * [2] F.-W. Sun and H. C. A. van Tilborg, “Approaching capacity by equiprobable signaling on the Gaussian channel,” _IEEE Trans. Inf. Theory_ , vol. 39, no. 5, pp. 1714–1716, 1993.
  * [3] A. R. Calderbank and L. H. Ozarow, “Nonequiprobable signaling on the Gaussian channel,” _IEEE Trans. Inf. Theory_ , vol. 36, no. 4, pp. 726–740, 1990.
  * [4] F. R. Kschischang and S. Pasupathy, “Optimal nonuniform signaling for Gaussian channels,” _IEEE Trans. Inf. Theory_ , vol. 39, no. 3, pp. 913–929, 1993.
  * [5] E. N. Gilbert, “A comparison of signalling alphabets,” _Bell Syst. Tech. J._ , vol. 31, no. 3, pp. 504–522, 1952.
  * [6] C. N. Campopiano and B. G. Glazer, “A coherent digital amplitude and phase modulation scheme,” _IRE Trans. Commun. Sys._ , vol. 10, no. 1, pp. 90–95, 1962.
  * [7] G. J. Foschini, R. D. Gitlin, and S. Weinstein, “Optimization of two-dimensional signal constellations in the presence of Gaussian noise,” _IEEE Trans. Commun._ , vol. 22, no. 1, pp. 28–38, 1974.
  * [8] B. Chen, C. Okonkwo, H. Hafermann, and A. Alvarado, “Increasing achievable information rates via geometric shaping,” in _Proc. Eur. Conf. Opt. Commun. (ECOC)_ , Rome, Italy, Sept. 2018.
  * [9] K. Gümüş, A. Alvarado, B. Chen, C. Häger, and E. Agrell, “End-to-end learning of geometrical shaping maximizing generalized mutual information,” in _Proc. Opt. Fiber Commun. Conf. (OFC)_ , San Diego, CA, Mar. 2020.
  * [10] G. D. Forney, Jr. and L.-F. Wei, “Multidimensional constellations—part I: Introduction, figures of merit, and generalized cross constellations,” _IEEE J. Sel. Areas Commun._ , vol. 7, no. 6, pp. 877–892, 1989.
  * [11] J. H. Conway and N. J. A. Sloane, “A fast encoding method for lattice codes and quantizers,” _IEEE Trans. Inf. Theory_ , vol. IT-29, no. 6, pp. 820–824, 1983.
  * [12] ——, “Fast quantizing and decoding algorithms for lattice quantizers and codes,” _IEEE Trans. Inf. Theory_ , vol. IT-28, no. 2, pp. 227–232, 1982\.
  * [13] A. Mirani, E. Agrell, and M. Karlsson, “Low-complexity geometric shaping,” _J. Lightw. Technol._ , vol. 39, no. 2, pp. 363–371, 2021.
  * [14] ——, “Lattice-based geometric shaping,” in _Proc. Eur. Conf. Opt. Commun. (ECOC)_ , Brussels, Belgium, Dec. 2020.
  * [15] G. D. Forney, Jr., “Multidimensional constellations—part II: Voronoi constellations,” _IEEE J. Sel. Areas Commun._ , vol. 7, no. 6, pp. 941–958, 1989.
  * [16] C. Feng, D. Silva, and F. R. Kschischang, “An algebraic approach to physical-layer network coding,” _IEEE Trans. Inf. Theory_ , vol. 59, no. 11, pp. 7576–7596, 2013.
  * [17] R. Zamir, _Lattice Coding for Signals and Networks_. Cambridge, UK: Cambridge University Press, 2014.
  * [18] ——, “How to design an efficient lattice coding scheme,” in _Proc. IEEE Inf. Theory Workshop (ITW)_ , Hobart, Australia, Nov. 2014.
  * [19] B. M. Kurkoski, “Encoding and indexing of lattice codes,” _IEEE Trans. Inf. Theory_ , vol. 64, no. 9, pp. 6320–6332, 2018.
  * [20] N. S. Ferdinand, B. M. Kurkoski, M. Nokleby, and B. Aazhang, “Low-dimensional shaping for high-dimensional lattice codes,” _IEEE Trans. Wireless Commun._ , vol. 15, no. 11, pp. 7405–7418, 2016.
  * [21] N. Sommer, M. Feder, and O. Shalvi, “Shaping methods for low-density lattice codes,” in _Proc. IEEE Inf. Theory Workshop (ITW)_ , Taormina, Italy, Oct. 2009.
  * [22] ——, “Low-density lattice codes,” _IEEE Trans. Inf. Theory_ , vol. 54, no. 4, pp. 1561–1585, 2008.
  * [23] N. S. Ferdinand, B. M. Kurkoski, B. Aazhang, and M. Latva-aho, “Shaping low-density lattice codes using Voronoi integers,” in _Proc. IEEE Inf. Theory Workshop (ITW)_ , Hobart, Australia, Nov. 2014.
  * [24] S. Li, A. Mirani, M. Karlsson, and E. Agrell, “Designing Voronoi constellations to minimize bit error rates,” in _Proc. IEEE Int. Symp. Inf. Theory (ISIT)_ , Melbourne, Australia, July 2021.
  * [25] M. K. Simon and J. G. Smith, “Hexagonal multiple phase-and-amplitude-shift-keyed signal sets,” _IEEE Trans. Commun._ , vol. 21, no. 10, pp. 1108–1115, 1973.
  * [26] J. G. Smith, “Odd-bit quadrature amplitude-shift keying,” _IEEE Trans. Commun._ , vol. 23, no. 3, pp. 385–389, 1975.
  * [27] J. H. Conway and N. J. A. Sloane, _Sphere Packings, Lattices and Groups_ , 3rd ed. New York, NY: Springer, 1999.
  * [28] M. Karlsson and E. Agrell, “Spectrally efficient four-dimensional modulation,” in _Proc. Opt. Fiber Commun. Conf. (OFC)_ , Los Angeles, CA, 2012.
  * [29] S. Benedetto and E. Biglieri, _Principles of Digital Transmission: With Wireless Applications_. New York, NY: Kluwer Academic, 1999.
  * [30] E. Agrell and M. Karlsson, “Power-efficient modulation formats in coherent transmission systems,” _J. Lightw. Technol._ , vol. 27, no. 22, pp. 5115–5126, 2009.
  * [31] J. H. Conway and N. J. A. Sloane, “Voronoi regions of lattices, second moments of polytopes, and quantization,” _IEEE Trans. Inf. Theory_ , vol. 28, no. 2, pp. 211–226, 1982.
  * [32] W. C. Brown, _Matrices over Commutative Rings_. New York, NY: Marcel Dekker, 1993.
  * [33] J. H. Conway and N. J. A. Sloane, “On the Voronoi regions of certain lattices,” _SIAM J. Alg. Disc. Meth._ , vol. 5, no. 3, pp. 294–305, 1984\.
  * [34] E. Agrell, T. Eriksson, A. Vardy, and K. Zeger, “Closest point search in lattices,” _IEEE Trans. Inf. Theory_ , vol. 48, no. 8, pp. 2201–2214, 2002\.
  * [35] A. Ghasemmehdi and E. Agrell, “Faster recursions in sphere decoding,” _IEEE Trans. Inf. Theory_ , vol. 57, no. 6, pp. 3530–3536, 2011.
  * [36] G. D. Forney, Jr., “Coset codes—part I: Introduction and geometrical classification,” _IEEE Trans. Inf. Theory_ , vol. 34, no. 5, pp. 1123–1151, 1988.
  * [37] A. Alvarado, T. Fehenberger, B. Chen, and F. M. J. Willems, “Achievable information rates for fiber optics: Applications and computations,” _J. Lightw. Technol._ , vol. 36, no. 2, pp. 424–439, 2018\.
  * [38] A. B. Owen, “Monte Carlo theory, methods and examples,” 2013. [Online]. Available: https://statweb.stanford.edu/~owen/mc
  * [39] R. Spring and A. Shrivastava, “Mutual information estimation using LSH sampling,” in _Proc. International Joint Conferences on Artificial Intelligence (IJCAI)_ , Yokohama, Japan, July 2020.
  * [40] A. Viterbi, “An intuitive justification and a simplified implementation of the MAP decoder for convolutional codes,” _IEEE J. Sel. Areas Commun._ , vol. 16, no. 2, pp. 260–264, 1998.
  * [41] “Digital video broadcasting (DVB); Second generation framing structure, channel coding and modulation systems for broadcasting, interactive services, news gathering and other broadband satellite applications (DVBS2),” ETSI, Sophia Antipolis, France, Tech. Rep. ETSIEN 302 307 V1.2.1 (2009-08), Aug. 2009\.