# Analysis of Low-Density Parity-Check Codes over Finite Integer Rings for the
Lee Channel

Jessica Bariffi  German Aerospace Center
Wessling, Germany
<EMAIL_ADDRESS>Hannes Bartz  German Aerospace Center
Wessling, Germany
<EMAIL_ADDRESS>Gianluigi Liva  German Aerospace Center
Wessling, Germany
<EMAIL_ADDRESS>Joachim Rosenthal J. Rosenthal has been supported in
part by the Swiss National Science Foundation under the grant No. 188430. J.
Bariffi, H. Bartz and G. Liva acknowledge the financial support by the Federal
Ministry of Education and Research of Germany in the programme of ”Souverän.
Digital. Vernetzt.” Joint project 6G-RIC, project identification number:
16KISK022. University of Zurich
Zurich, Switzerland
<EMAIL_ADDRESS>
###### Abstract

We study the performance of nonbinary low-density parity-check (LDPC) codes
over finite integer rings over two channels that arise from the Lee metric.
The first channel is a discrete memory-less channel (DMC) matched to the Lee
metric. The second channel adds to each codeword an error vector of constant
Lee weight, where the error vector is picked uniformly at random from the set
of vectors of constant Lee weight. It is shown that the marginal conditional
distributions of the two channels coincide, in the limit of large block
length. Random coding union bounds on the block error probability are derived
for both channels. Moreover, the performance of selected LDPC code ensembles
is analyzed by means of density evolution and finite-length simulations, with
belief propagation decoding and with a low-complexity symbol message passing
algorithm and it is compared to the derived bounds.

††publicationid: pubid:  978-1-6654-3540-6/22/$31.00 © 2022 IEEE

BP

    belief propagation
VN

    variable node
CN

    check node
DE

    density evolution
EXIT

    extrinsic information transfer
i.i.d.

    independent and identically distributed
LDPC

    low-density parity-check
MAP

    maximum a posteriori probability
MCM

    Monte Carlo method
r.v.

    random variable
p.m.f.

    probability mass function
ML

    maximum likelihood
WEF

    weight enumerating function
MDS

    maximum distance separable
AWE

    average weight enumerator
DMC

    discrete memory-less channel
w.r.t.

    with respect to
BSC

    binary symmetric channel
SMP

    symbol message-passing
RV

    random variable
PMF

    probability mass function
$q$-SC

     $q$-ary symmetric channel
RCU

    random coding union
BMP

    binary message-passing
PEG

    progressive edge growth
LSF

    Lee Symbol Flipping
TV

    total variation

##  I Introduction

The construction of channel codes for the Lee metric [1, 2] attracted some
attention in the past [3, 4, 5, 6, 7]. Currently, codes for the Lee metric are
considered for cryptographic applications [8, 9] thanks to their potential in
decreasing the public key size in code-based public-key cryptosystems.
Furthermore, codes for the Lee metric have potential applications in the
context of magnetic [10] and DNA [11] storage systems.

In this paper, we analyze the performance of certain code classes in the
context of Lee metric decoding. In particular, we consider two channel models.
The first model is a discrete memory-less channel (DMC) _matched_ to the Lee
metric [12, 6], i.e., the DMC whose maximum likelihood (ML) decoding rule
reduces to finding the codeword at minimum Lee distance from the channel
output. The second model is a channel that adds to each codeword an error
vector of constant Lee weight, where the error vector is picked uniformly at
random from the set of length-$n$ vectors of constant Lee weight (here, $n$ is
the block length). The first model will be referred to as the _Lee channel_ ,
whereas the second model will be dubbed _constant-weight Lee channel_. It will
be shown that the marginal conditional distribution of the constant-weight Lee
channel reduces to the conditional distribution of a suitably-defined (memory-
less) Lee channel, as $n$ grows large. Random coding bounds are derived for
both channels, providing a finite-length performance benchmark to evaluate the
block error probability of practical coding schemes. We then study the
performance of nonbinary low-density parity-check (LDPC) codes [13] over
finite rings [14], in the context of Lee-metric decoding. The codes will be
analyzed, from a code ensemble viewpoint, via density evolution. Two decoding
algorithms will be considered, namely the well-known (nonbinary) belief
propagation (BP) algorithm [15, 14] and the recently-introduced low-complexity
symbol message-passing (SMP) algorithm [16], where the latter will be adapted
to the Lee channel (the SMP was originally defined for $q$ary symmetric
channels only). We will compare the performance of the two decoding algorithms
to the Lee Symbol Flipping (LSF) presented in [17, Algorithm 2] for LDPC Codes
in the Lee metric. The SMP decoding algorithm, thanks to its low complexity,
is of practical interest for code-based cryptosystems [17]. To simplify the
exposition, the analysis will be limited to regular LDPC code ensembles (that
are mainly considered for code-based cryptography). The extension of the
analysis to irregular and protograph-based LDPC code ensembles is
straightforward. Finite-length simulation results will be provided for both
the Lee and the constant-weight Lee channels, and will be compared with
finite-length benchmarks.

The paper is organized as follows. Section II provides some definitions and
useful results. The channel models are introduced in Section III, together
with finite-length performance bounds. In Section IV we analyse the
performance of LDPC codes over Lee channels. Conclusions follow in Section V.

##  II Preliminaries

Let $\mathbb{Z}_{q}$ be the ring of integers modulo $q$. In the following, all
logarithms are in the natural base. The set of units of a ring
$\mathbb{Z}_{q}$ is indicated by $\mathbb{Z}_{q}^{\times}$. We denote random
variables by uppercase letters, and their realizations with lower case
letters. Moreover, we use the shorthand $[x]^{+}$ to denote $\max(0,x)$.

The Lee weight [2] of a scalar $a\in\mathbb{Z}_{q}$ is

$\displaystyle\operatorname{wt}_{\scriptscriptstyle\mathsf{L}}(a):=\min(a,q-a).$

The Lee weight of a vector $\bm{x}\in\mathbb{Z}_{q}^{n}$ is defined to be the
sum of the Lee weights of its elements, i.e.,

$\operatorname{wt}_{\scriptscriptstyle\mathsf{L}}(\bm{x})=\sum_{i=1}^{n}\operatorname{wt}_{\scriptscriptstyle\mathsf{L}}(x_{i}).$
(1)

Note that the Lee weight of an element $a\in\mathbb{Z}_{q}$ is upper bounded
by $\lfloor q/2\rfloor$. Hence, the Lee weight of a length-$n$ vector $\bm{x}$
over $\mathbb{Z}_{q}$ is upper bounded by $n\cdot\lfloor q/2\rfloor$. To
simplify the notation, we will always denote $r:=\lfloor q/2\rfloor$. We have
that

$\displaystyle\operatorname{wt}_{\scriptscriptstyle\mathsf{L}}(a)=\operatorname{wt}_{\scriptscriptstyle\mathsf{L}}(q-a)\;\text{
for every }a\in\\{1,\dots,r\\}.$ (2)

The Lee distance of two scalars $a,b\in\mathbb{Z}_{q}$ is
$\operatorname{d}_{\scriptscriptstyle\mathsf{L}}(a,b):=\operatorname{wt}_{\scriptscriptstyle\mathsf{L}}(a-b)$.
The Lee distance between $\bm{x},\bm{y}\in\mathbb{Z}_{q}^{n}$ is

$\displaystyle\operatorname{d}_{\scriptscriptstyle\mathsf{L}}(\bm{x},\bm{y})=\sum_{i=1}^{n}\operatorname{d}_{\scriptscriptstyle\mathsf{L}}(x_{i},y_{i}).$

###  II-A Low-Density Parity-Check Codes over Finite Integer Rings

We will consider $(n,k)$ linear block codes over $\mathbb{Z}_{q}$ and we
denote by $R=k/n$ the code rate. An $(n,k)$ LDPC code over $\mathbb{Z}_{q}$
[14] is defined by a $m\times n$ _sparse_ matrix $\bm{H}$, which can be
described via a bipartite graph $\mathcal{G}$ consisting of a set of $n$
variable nodes $\\{\mathsf{v}_{0},\mathsf{v}_{1},\ldots,\mathsf{v}_{n-1}\\}$
and a set of $m$ check nodes
$\\{\mathsf{c}_{0},\mathsf{c}_{1},\ldots,\mathsf{c}_{m-1}\\}$ where the VN
$\mathsf{v}_{j}$ is connected with an edge to the CN $\mathsf{c}_{i}$ if and
only if the entry $h_{i,j}$ in $\bm{H}$ is nonzero. The degree of a node
refers to the number of edges that are connected to the node. The neighbors of
a VN $\mathsf{v}$ is the set $\mathcal{N}\left(\mathsf{v}\right)$ composed by
CNs that are connected to $\mathsf{v}$ by an edge. Similarly, the neighbors of
a CN $\mathsf{c}$ is the set $\mathcal{N}\left(\mathsf{c}\right)$ composed by
VNs that are connected to $\mathsf{c}$ by an edge. We denote by
$\mathscr{C}_{v,c}^{n}$ the unstructured regular (length-$n$) LDPC code
ensemble, i.e., the set of codes defined by an $m\times n$ matrix $\bm{H}$
whose bipartite graph possesses constant VN degree $v$ and constant CN degree
$c$. We denote the ensemble design rate as $R_{0}=1-m/n$. When sampling an
LDPC code from the given ensemble, we assume the nonzero entries drawn
independently and uniformly from $\mathbb{Z}_{q}^{\times}$ as proposed in
[14].

###  II-B Useful Results and Definitions

Letting $a_{n}$ and $b_{n}\neq 0$ be two real-valued sequences, we say that
$a_{n}$ and $b_{n}$ are exponentially equivalent as $n\rightarrow\infty$,
writing $a_{n}\doteq b_{n}$ if and only if [18, Ch. 3.3]

$\displaystyle\lim_{n\rightarrow\infty}\frac{1}{n}\log\left(\frac{a_{n}}{b_{n}}\right)=0\,.$

We denote by
$\bm{f}(\bm{x})=(f_{0}(\bm{x}),f_{1}(\bm{x}),\ldots,f_{q-1}(\bm{x}))$ the
composition (i.e., empirical distribution) of a vector
$\bm{x}\in\mathbb{Z}_{q}^{n}$, i.e., $f_{i}$ is the relative frequency of $i$
in $\bm{x}$. We introduce the set

$\mathcal{S}_{n\delta}^{n}:=\left\\{\bm{x}\,\big{|}\,\bm{x}\in\mathbb{Z}^{n}_{q},\operatorname{wt}_{\scriptscriptstyle\mathsf{L}}(\bm{x})=n\delta\right\\}.$
(3)

Here, $\mathcal{S}_{n\delta}^{n}$ defines the surface of radius-$n\delta$
$n$-dimensional Lee sphere. The set of vectors in $\mathbb{Z}^{n}_{q}$ with
composition $\bm{\phi}$ is

$\mathcal{T}_{\bm{\phi}}^{n}:=\left\\{\bm{x}\,\big{|}\,\bm{x}\in\mathbb{Z}^{n}_{q},\bm{f}(\bm{x})=\bm{\phi}\right\\}.$
(4)

We have that [18, Ch. 11.1]

$\left|\mathcal{T}_{\bm{\phi}}^{n}\right|\doteq\exp(n\mathrm{H}_{e}(\bm{\phi}))$
(5)

where

$\mathrm{H}_{e}(\bm{\phi}):=-\\!\\!\sum_{i=0,\phi_{i}\neq
0}^{q-1}\\!\\!\phi_{i}\log\phi_{i}.$ (6)

##  III The Lee Channel

For $x,y,e\in\mathbb{Z}_{q}$ consider the DMC

$y=x+e$ (7)

where $y$ is the channel output, $x$ the channel input, and $e$ is an additive
error term. More specifically, we restrict to the case where $e$ is a
realization of a random variable (RV) $E$, distributed as
$P_{E}(e)\propto\exp(-\beta\operatorname{wt}_{\scriptscriptstyle\mathsf{L}}(e))$,
where $\beta>0$ is a constant that defines (together with the alphabet) the
channel. Defining the normalization constant

$Z(\beta):=\sum_{e=0}^{q-1}\exp(-\beta\operatorname{wt}_{\scriptscriptstyle\mathsf{L}}(e))$
(8)

we get the channel law

$P_{Y|X}(y|x)=\frac{1}{Z}\exp\left(-\beta\operatorname{d}_{\scriptscriptstyle\mathsf{L}}(x,y)\right).$
(9)

We refer next to the channel defined in (9) as the _Lee channel_. We denote
the expectation of $\operatorname{wt}_{\scriptscriptstyle\mathsf{L}}(E)$ as
$\delta$, given by [19]

$\delta=-\frac{\mathrm{d}\log Z(\beta)}{\mathrm{d}\beta}.$ (10)

Our interest in (9) stems from two observations:

  * i.

The channel defined in (9) is the DMC matched to the Lee metric [12, 6], i.e.,
the channel whose ML decoding rule reduces to finding the codeword
$\bm{x}\in\mathcal{C}$ that minimizes the Lee distance from the channel output
$\bm{y}$;

  * ii.

The conditional distribution (9) arises (in the limit of large $n$) as the
marginal distribution of a channel (in the following, referred to as an
_constant-weight Lee channel_) adding to the transmitted codeword an error
pattern drawn uniformly at random from a set of vectors of constant Lee
weight. This is especially interesting for code-based public-key cryptosystems
in the Lee metric [8].

A derivation of the result in ii. is given next.

###  III-A Marginal Distribution of Constant-Weight Lee Channels

Consider a constant-weight Lee channel

$\bm{y}=\bm{x}+\bm{e}$ (11)

with $\bm{y},\bm{x},\bm{e}\in\mathbb{Z}^{n}_{q}$, and where $\bm{e}$ is drawn,
with uniform probability, from the set $\mathcal{S}_{n\delta}^{n}$. We have
$P_{\bm{E}}(\bm{e})=\left|\mathcal{S}_{n\delta}^{n}\right|^{-1}$ for all
$\bm{e}\in\mathcal{S}_{n\delta}^{n}$, with $P_{\bm{E}}(\bm{e})=0$ otherwise.
We are interested the marginal distribution $P_{E}(e)$ in the limit for
$n\rightarrow\infty$. The marginal distribution plays an important role, for
instance, in the initialization of iterative decoders of LDPC codes, when used
over constant-weight Lee channels [17]. While the focus here is in the
asymptotic (in the block length $n$) case, the derived marginal distribution
provides an excellent approximation of the true marginal down to moderate-
length blocks ($n$ in the order of a few hundreds). The derivation follows by
seeking the composition that dominates the set $\mathcal{S}_{n\delta}^{n}$.
More specifically, we should look for the empirical distribution $\bm{\phi}$
that maximizes the cardinality of $\mathcal{T}_{\bm{\phi}}^{n}$ under the
constraint

$\sum_{i=0}^{q-1}\operatorname{wt}_{\scriptscriptstyle\mathsf{L}}(i)\phi_{i}=\delta.$
(12)

The task is closely related to the problem, in statistical mechanics, of
finding the distribution of a systems state by relating it to that states
energy and temperature [20, 21]. Owing to (5), and taking the limit for
$n\rightarrow\infty$, we will look for the empirical distribution maximizing
the entropy (6) under the constraint (12) [18, Ch. 12], i.e.

$\bm{\phi}^{\star}=\arg\max\mathrm{H}_{e}(\bm{\phi})$ (13)

with
$\sum_{i=0}^{q-1}\operatorname{wt}_{\scriptscriptstyle\mathsf{L}}(i)\phi_{i}=\delta$.
By introducing the Lagrange multiplier $\beta$, we aim at finding the maximum
in $\bm{\phi}$ of

$\mathsf{f}(\bm{\phi},\beta):=\mathrm{H}_{e}(\bm{\phi})-\beta\left(\sum_{i=0}^{q-1}\operatorname{wt}_{\scriptscriptstyle\mathsf{L}}(i)\phi_{i}-\delta\right).$
(14)

The result yields the distribution

$\phi_{i}^{\star}=\frac{1}{Z}\exp\left(-\beta\operatorname{wt}_{\scriptscriptstyle\mathsf{L}}(i)\right)$
(15)

with $Z$ given in (8) and $\beta$ obtained by enforcing the condition (12)
(i.e., by solving (10) in $\beta$). The distribution (15) is closely related
to the Boltzmann distribution [20, 18], which may be recovered by interpreting
the Lee weight $\operatorname{wt}_{\scriptscriptstyle\mathsf{L}}(i)$ as an
energy value. Notably, when drawing $\bm{e}$ with uniform probability from the
set $\mathcal{S}_{n\delta}^{n}$, $\bm{e}$ will possess an empirical
distribution close to $\bm{\phi}^{\star}$ with high probability as $n$ grows
large. The result follows by the conditional limit theorem [18, Theorem
11.6.2].

###  III-B Bounds on the Block Error Probability

Denote the natural entropy of a random variable distributed according to
$\bm{\phi}^{\star}$ with mean $\delta$, $\mathrm{H}_{e}(\bm{\phi}^{\star})$,
as $\mathsf{H}_{\delta}$. Moreover, let

$\delta_{q}:=\left\\{\begin{array}[]{ll}(q^{2}-1)/4q&\text{if }q\text{ is
odd}\\\ q/4&\text{if }q\text{ is even}\end{array}\right.$ (16)

and the function

$\mathsf{H}^{+}_{\delta}:=\left\\{\begin{array}[]{ll}\mathsf{H}_{\delta}&\text{if
}\delta\leq\delta_{q}\\\ \log q&\text{otherwise}.\end{array}\right.$ (17)

The following theorem establishes a random coding union (RCU) bound, providing
an upper bound on the error probability, $P_{B}(\mathcal{C})$, achievable by
the best $(n,nR)$ code $\mathcal{C}$ on $\mathbb{Z}_{q}$ over a constant-
weight Lee channel with normalized error vector weight equal to $\delta$.

######  Theorem 1.

The expected error probability of a random $(n,nR)$ code $\mathcal{C}$ on
$\mathbb{Z}_{q}$ when used to communicate over a constant-weight Lee channel
with normalized weight of the error vector equal to $\delta$ satisfies

$\mathbb{E}\left[P_{B}(\mathcal{C})\right]<\exp\left(-n\left[(1-R)\log
q-\mathsf{H}^{+}_{\delta}\right]^{+}\right).$ (18)

###### Proof.

The proof of Theorem 1 is based on [22, Theorem 16], where for the evaluation
of the pair-wise error probability we determine the probability of generating
a random codeword that lies within a Lee sphere of radius $n\delta$. By
noticing that the volume of such a sphere is tightly upper bounded by
$\exp(n\mathsf{H}^{+}_{\delta})$, the result follows. ∎

Note that the bound provided in Theorem 1 can easily be extended to the
memoryless Lee channel by averaging over the distribution of the Lee weight
$D$ of the error pattern, yielding the following corollary.

######  Corollary 1.

The expected error probability of a random $(n,nR)$ code $\mathcal{C}$ on
$\mathbb{Z}_{q}$ when used to communicate over a memoryless Lee channel with
parameter $\delta$ satisfies

$\mathbb{E}\left[P_{B}(\mathcal{C})\right]<\mathbb{E}\left[\exp\left(-n\left[(1-R)\log
q-{\mathsf{H}^{+}_{D/n}}\right]^{+}\right)\right].$ (19)

##  IV LDPC Codes: Analysis over the Lee Channel

We review first two message-passing decoders for nonbinary LDPC codes, i.e.,
the well-known BP algorithm [15, 14] and the SMP algorithm introduced in [16].
We then analyze the performance achievable by the two algorithms in an
asymptotic setting (via density evolution (DE) analysis) and at finite block
length (via Monte Carlo simulations).

###  IV-A Message-Passing Decoders

####  IV-A1 Belief Propagation Decoding

We now consider first BP decoding of nonbinary LDPC codes defined on rings.
The decoding algorithm is outlined below.

  1. 1.

Initialization. Define the likelihood at VN by $\mathsf{v}$
$\bm{m}_{\mathsf{ch}}:=\left(P_{Y|X}(y\mid 0),\dots,P_{Y|X}(y\mid
q-1)\right)$, i.e., $\bm{m}_{\mathsf{ch}}$ is the probability mass function
(PMF) associated with the channel observation for the VN $\mathsf{v}$. Let
$\bm{\Pi}_{\mathsf{c},\mathsf{v}}$ be the permutation matrix induced by the
parity-check matrix element $h_{\mathsf{c},\mathsf{v}}$ (associated with the
edge between CN $\mathsf{c}$ and VN $\mathsf{v}$). In the first iteration,
each VN $\mathsf{v}$ sends to all
$\mathsf{c}\in\mathcal{N}\left(\mathsf{v}\right)$ the message

$\bm{m}_{\mathsf{v}\rightarrow\mathsf{c}}=\bm{m}_{\mathsf{ch}}\bm{\Pi}_{\mathsf{c},\mathsf{v}}$
(20)

  2. 2.

CN-to-VN step. Let $\circledast$ denote the circular convolution of the PMFs.
Then, each CN $\mathsf{c}$ computes

$\bm{u}=\mathop{\vphantom{\sum}\mathchoice{\vbox{\hbox{\huge$\circledast$}}}{\vbox{\hbox{\Large
A}}}{\mathrm{A}}{\mathrm{A}}}\displaylimits_{\mathsf{v}^{\prime}\in\mathcal{N}\left(\mathsf{c}\right)\setminus\\{\mathsf{v}\\}}\bm{m}_{\mathsf{v}^{\prime}\rightarrow\mathsf{c}}$
(21)

Given the $(q\times q)$ inverse permutation matrix,
$\bm{\Pi}_{\mathsf{v},\mathsf{c}}^{-1}$, associated with
$h_{\mathsf{c},\mathsf{v}}^{-1}$ the CN-to-VN message is then

$\bm{m}_{\mathsf{c}\rightarrow\mathsf{v}}=\bm{u}\cdot\bm{\Pi}_{\mathsf{c},\mathsf{v}}^{-1}.$
(22)

  3. 3.

VN-to-CN step. We denote by $\odot$ the element-wise Hadamard (or Schur)
product of the PMFs, and by $K$ a normalization constant enforcing
$\sum_{i=0}^{q-1}v_{i}=1$. Each VN $\mathsf{v}$ then computes

$\bm{v}=K\\!\\!\\!\\!\mathop{\vphantom{\sum}\mathchoice{\vbox{\hbox{\huge$\odot$}}}{\vbox{\hbox{\Large
A}}}{\mathrm{A}}{\mathrm{A}}}\displaylimits_{\mathsf{c}^{\prime}\in\mathcal{N}\left(\mathsf{v}\right)\setminus\\{\mathsf{c}\\}}\\!\\!\\!\\!\bm{m}_{\mathsf{c}^{\prime}\rightarrow\mathsf{v}}$
(23)

and then sends to its neighboring CN $\mathsf{c}$ the message

$\bm{m}_{\mathsf{v}\rightarrow\mathsf{c}}=\bm{v}\cdot\bm{\Pi}_{\mathsf{c},\mathsf{v}}.$
(24)

  4. 4.

Final decision. After iterating steps 2 and 3 at most $\ell_{\text{max}}$
times, the final decision at each VN $\mathsf{v}$ is

$\hat{x}=\underset{x\in\mathbb{Z}_{q}}{\arg\max}\,v_{x}^{\scriptscriptstyle\textsf{APP}}$
(25)

where

$\bm{v}^{\scriptscriptstyle\textsf{APP}}=\mathop{\vphantom{\sum}\mathchoice{\vbox{\hbox{\huge$\odot$}}}{\vbox{\hbox{\Large
A}}}{\mathrm{A}}{\mathrm{A}}}\displaylimits_{\mathsf{c}\in\mathcal{N}\left(\mathsf{v}\right)}\bm{m}_{\mathsf{c}\rightarrow\mathsf{v}}.$
(26)

####  IV-A2 Symbol Message Passing (SMP) Decoding

Under SMP decoding each message exchanged by a VN/CN pair is a symbol, i.e.,
an hard estimate of the codeword symbol associated with the VN. Thanks to
this, SMP allows remarkable savings in the internal decoder data flow,
compared to BP decoding. Following the principle outlined in [23], the
messages from CNs to VNs are modeled as observations at the output a $q$-ary
input, $q$-ary output DMC. By doing so, the messages at the input of each VN
can be combined by multiplying the respective likelihoods (or by summing the
respective log-likelihoods).

Given a DMC $P_{Y|X}(y|x)$ and a channel output $y\in\mathbb{Z}_{q}$, we
define the log-likelihood vector ($\bm{L}$-vector)

$\bm{L}(y):=(L_{0}(y),L_{1}(y),\dots,L_{q-1}(y)))$ (27)

where $L_{x}(y)=\log\left(P_{Y|X}(y\mid x)\right)$.

  1. 1.

Initialization. Each VN $\mathsf{v}$ sends the corresponding Lee channel
observation $m_{\mathsf{v}\rightarrow\mathsf{c}}=y$ to all
$\mathsf{c}\in\mathcal{N}\left(\mathsf{v}\right)$.

  2. 2.

CN-to-VN step. Each CN $\mathsf{c}$ computes

$m_{\mathsf{c}\rightarrow\mathsf{v}}=h_{\mathsf{c},\mathsf{v}}^{-1}\sum_{\mathsf{v}^{\prime}\in\mathcal{N}\left(\mathsf{c}\right)\setminus\\{\mathsf{v}\\}}h_{\mathsf{c},\mathsf{v}^{\prime}}m_{\mathsf{v}^{\prime}\rightarrow\mathsf{c}}.$
(28)

  3. 3.

VN-to-CN step. Define the aggregated extrinsic $\bm{L}$-vector

$\bm{E}=\bm{L}(y)+\sum_{\mathsf{c}^{\prime}\in\mathcal{N}\left(\mathsf{v}\right)\setminus\\{\mathsf{c}\\}}\bm{L}\left(m_{\mathsf{c}^{\prime}\rightarrow\mathsf{v}}\right).$
(29)

Under the $q$-ary symmetric channel ($q$-SC) approximation, each extrinsic
channel from CN $\mathsf{c}^{\prime}$ to VN $\mathsf{v}$ is modeled according
to

$P_{M|X}(m|x)=\begin{cases}1-\xi&\text{if }m=x\\\
\xi/(q-1)&\text{otherwise}\end{cases}$ (30)

where, for the sake of computing
$\bm{L}(m_{\mathsf{c}^{\prime}\rightarrow\mathsf{v}})$, the iteration-
dependent extrinsic channel error probability $\xi$ can be obtained from the
DE analysis (as described in the Section IV-C1). Then the VN-to-CN messages
are

$m_{\mathsf{v}\rightarrow\mathsf{c}}=\underset{x\in\mathbb{Z}_{q}}{\arg\max}\,E_{x}.$
(31)

  4. 4.

Final decision. After iterating steps 2 and 3 at most $\ell_{\text{max}}$
times, the final decision at each VN $\mathsf{v}$ is

$\hat{x}=\underset{x\in\mathbb{Z}_{q}}{\arg\max}\,L_{x}^{\scriptscriptstyle\textsf{FIN}}$
(32)

where

$\bm{L}^{\scriptscriptstyle\textsf{FIN}}=\bm{L}(m_{\mathsf{ch}})+\sum_{\mathsf{c}\in\mathcal{N}\left(\mathsf{v}\right)}\bm{L}\left(m_{\mathsf{c}\rightarrow\mathsf{v}}\right).$
(33)

###  IV-B The $q$SC-Assumption

The choice of the DMC used to model the extrinsic channel plays a crucial role
for the performance of the SMP algorithm. In [23], for the case of binary
message-passing (BMP) decoding, it was suggested to model the VN inbound
messages as observations of a binary symmetric channel (BSC), whose transition
probability was estimated by DE analysis. The approach was generalized in [16]
for SMP, where the VN inbound messages are modelled as observations of a
$q$-SC. We will also model the extrinsic channel as a $q$-SC defined in (30),
although in our setting the model holds only in an approximate sense. The use
of the $q$-SC approximation is particularly useful from a practical viewpoint
since it simplifies the VN processing in SMP decoding. Note moreover that for
LDPC codes over finite fields, the extrinsic channel transition probabilities,
averaged over a uniform distribution of nonzero elements in the parity-check
matrix, yield a $q$-SC [16].

For the case of $\mathbb{Z}_{q}$ where $q$ is non-prime, the average extrinsic
channel transition probabilities do not describe a $q$-SC. Nevertheless, if
the units $x\in\mathbb{Z}_{q}^{\times}$ are used to label the graph edges with
uniform probability, we expect that for an integer ring consisting of
relatively many units the $q$-SC approximation should turn to be accurate. To
provide some empirical evidence of this conjecture, we adopt the methodology
used in [24] to support the use of the Gaussian approximation in the DE
analysis of BP decoding of binary LDPC codes. In particular, we show
numerically that the total variation (TV) distance between the extrinsic
channel distribution and the $q$-SC is generally small, and it vanishes with
the number of iterations. The TV distance of two probability distributions $P$
and $Q$ over the same discrete alphabet $\mathcal{X}$ is defined as [25,
Proposition 4.2]

$\displaystyle\mathsf{TV}(P,Q):=\dfrac{1}{2}\sum_{x\in\mathcal{X}}\left|P(x)-Q(x)\right|.$

In Figure 1 and 2 we show for $\mathbb{Z}_{8}$, $\mathbb{Z}_{9}$ and
$\mathbb{Z}_{12}$, that the TV indeed tends to zero when performing Monte
Carlo simulations for different numbers of iterations of the SMP decoder for
some choices of $\delta$ and different regular LDPC code ensembles. Iterative
decoding thresholds of some regular nonbinary LDPC code ensembles can be found
in Table I. We have chosen these three finite integer rings to cover different
cases for the relative number of unit elements, i.e. the fraction of units
$\mathcal{U}_{q}$ in $\mathbb{Z}_{q}$ are $\mathcal{U}_{8}=1/2$,
$\mathcal{U}_{9}=2/3$ and $\mathcal{U}_{12}=1/3$. The figures support the
statement that, for integer rings with relatively few unit elements, the
approximation is less accurate in the first iterations. Note that the first
few iterations play an important role in determining the iterative decoding
threshold.

Figure 1: Evolution of the TV distance between the extrinsic channel
distribution and the $q$-SC for regular $(3,6)$ LDPC code ensembles in the SMP
decoder. Figure 2: Evolution of the TV distance between the extrinsic channel
distribution and the $q$-SC for regular $(4,8)$ LDPC code ensembles in the SMP
decoder.

###  IV-C Density Evolution Analysis

We analyze next the performance of regular LDPC code ensembles on
$\mathbb{Z}_{q}$, over the Lee channel, from a DE viewpoint. In particular, we
estimate the iterative decoding threshold over the Lee channel (9) under BP
and SMP decoding. The iterative decoding threshold $\delta^{\star}$ is the
largest value of the channel parameter $\delta$ (10) for which, in the limit
of large $n$ and large $\ell_{\text{max}}$, the symbol error probability of
code picked randomly from the ensemble becomes vanishing small [26]. For BP
decoding, we resort to the Monte Carlo method (MCM), while for SMP decoding
the analysis is outlined next.

####  IV-C1 Density Evolution Analysis for SMP

The DE analysis for SMP plays a two-fold role: it allows to estimate the
decoding threshold $\delta^{\star}_{\scriptscriptstyle\mathsf{SMP}}$ and it
provides estimates for the error probabilities $\xi$ of the extrinsic $q$-SC
which have to be used by the decoder in (29), (33). We now briefly sketch the
DE analysis for SMP over a $q$-SC from [16, Sec. IV] and highlight the
respective modifications to estimate the iterative decoding threshold
$\delta^{\star}_{\scriptscriptstyle\mathsf{SMP}}$ as well as the extrinsic
channel error probabilities $\xi$ for transmissions over the Lee channel (9).

Due to the linearity of the code and the symmetry of the Lee channel, for the
analysis we assume the transmission of the all-zero codeword. Let
$M_{\mathsf{v}\rightarrow\mathsf{c}}^{(\ell)}$ denote the messages from VN
$\mathsf{v}$ to CN $\mathsf{c}$ in the $\ell$-th iteration and define

$p_{a}^{(\ell)}:=\Pr\left\\{M_{\mathsf{v}\rightarrow\mathsf{c}}^{(\ell)}=a\mid
X=0\right\\}.$ (34)

For the Lee channel we initialize the DE routine from [16, Sec. IV] with the
probabilities $p_{a}^{(0)}=P_{Y|X}(a\mid 0)$, $\forall a\in\mathbb{Z}_{q}$,
where $P_{Y|X}(y|x)$ is the Lee channel transition probability from (9). The
remaining steps of the DE analysis remain the same as in [16, Sec. IV] except
for the definition of the aggregated extrinsic $\bm{L}$-vector $\bm{E}$ in
(29). For the Lee channel, the entries of $\bm{E}$ in the $\ell$-th iteration
are given by

$E_{b}^{(\ell)}=L_{0}(b)+\mathsf{D}(\xi^{(\ell)})f_{b}^{(\ell-1)}\qquad\forall
b\in\mathbb{Z}_{q}$ (35)

where $\mathsf{D}(\epsilon):=\log(1-\epsilon)-\log(\epsilon/(q-1))$,
$\xi^{(\ell)}$ denotes the extrinsic channel error probability and
$f_{b}^{(\ell)}$ denotes the number of CN-to-VN message taking the value
$b\in\mathbb{Z}_{q}$ in the $\ell$-th iteration. The decoding threshold is
then obtained as the maximum expected normalized Lee weight
$\delta^{\star}_{\scriptscriptstyle\mathsf{SMP}}$ of a Lee channel
distribution (9) such that $p_{0}^{(\ell)}\rightarrow 1$ as
$\ell\rightarrow\infty$. Decoding thresholds for $\mathscr{C}_{3,6}$ and
$\mathscr{C}_{4,8}$ regular LDPC code ensembles with $q$ ranging from $5$ to
$8$ are given in Table I, as well as the Shannon limit
$\delta^{\star}_{\scriptscriptstyle\mathsf{SH}}$ for rate $R=1/2$.

TABLE I: Decoding thresholds for regular nonbinary LDPC code ensembles under BP and SMP decoding. $~{}~{}~{}q~{}~{}~{}$ | $~{}~{}~{}(v,c)~{}~{}~{}$ | $~{}~{}~{}\delta^{\star}_{\scriptscriptstyle\mathsf{BP}}~{}~{}~{}$ | $~{}~{}~{}\delta^{\star}_{\scriptscriptstyle\mathsf{SMP}}~{}~{}~{}$ | $~{}~{}~{}\delta^{\star}_{\scriptscriptstyle\mathsf{SH}}~{}~{}~{}$
---|---|---|---|---
$5$ | $(3,6)$ | $0.2148$ | $0.1039$ | 0.2684
$(4,8)$ | $0.1802$ | $0.1200$
$7$ | $(3,6)$ | $0.3086$ | $0.1261$ | 0.3560
$(4,8)$ | $0.2686$ | $0.1539$
$8$ | $(3,6)$ | $0.3135$ | $0.1374$ | 0.3950
$(4,8)$ | $0.26904$ | $0.1623$

###  IV-D Numerical Results

In the following, we present numerical results for both BP and SMP decoding
and we compare them to the LSF decoder, for which we assumed a decoding
threshold $\tau=\frac{d_{\mathsf{v}}}{2}$, where $d_{\mathsf{v}}$ denotes the
variable nodes degree, as the authors suggest. The results, provided in terms
of block error rates for $(3,6)$ regular nonbinary LDPC codes of length $256$
symbols, are obtained via Monte Carlo simulations. The codes parity-check
matrices have been designed via the progressive edge growth (PEG) algorithm
[27], with the nonzero coefficients drawn independently and uniformly in
$\mathbb{Z}_{q}^{\times}$. For the constant-weight Lee channel, the error
vectors are drawn uniformly at random from the set of vectors with a given
weight. For the case of the (memoryless) Lee channel, we computed a finite-
length performance benchmark via the normal approximation of [22].

Figure 3, shows the block error probability over memoryless Lee channels. The
impact of the order $q$ on the achievable performance is well captured by the
RCU bounds. In particular, for a given target block error rate, a larger
average normalized Lee weight $\delta$ can be supported for larger $q$. The
result applies to the performance of the $(3,6)$ LDPC codes as well, under
both BP and SMP decoding, with one key exception: while under BP decoding a
small gain is achieved by moving from $\mathbb{Z}_{7}$ to $\mathbb{Z}_{8}$,
under SMP decoding no performance gain is observed. The reason for this could
lay in the $q$-SC assumption (30) used by the SMP decoder, which holds only in
an approximate sense for the case of non-prime rings. The effect is visible
over the constant-weight Lee channel too, as depicted in Figure 4. Both
figures show that the SMP outperforms the LSF, even though in the non-field
case for the SMP we used the $q$-SC assumption (30) for the extrinsic channel.
We acknowledge that the LSF decoder from [17] was originally introduced and
designed for a special class on LDPC codes (namely, for low-Lee-density
parity-check codes), and its performance might be enhanced by taking into
account the differences between the two code classes. While this point will be
subject of further investigations, we believe that an important role in the
performance gain under SMP decoding relies on its capability to exploit the
knowledge of the error marginal distribution. The block error rate result
achieved by BP and SMP decoding matches well the DE analysis, with threshold
differences that are reproduced in the finite length results by the gaps among
the block error rate curves. As expected, BP decoding outperforms SMP
decoding. Nevertheless, the SMP algorithm shows a performance that is
appealing for applications demanding low-complexity decoding [17].

Figure 3: Block error rate vs. $\delta$ for regular $(3,6)$ nonbinary LDPC
codes of length $n=256$. Memoryless Lee channel. Figure 4: Block error rate
vs. $\delta$ for regular $(3,6)$ nonbinary LDPC code ensembles of length
$n=256$. Constant-weight Lee channel.

##  V Conclusions

The performance of nonbinary low-density parity-check (LDPC) codes over finite
integer rings has been studied, over two channels that arise from the Lee
metric. The first channel is a discrete memory-less channel matched to the Lee
metric, whereas the second channel adds to each codeword an error vector of
constant Lee weight. It is shown that the marginal conditional distribution of
the two channels coincides, in the limit of large block lengths. The result is
used to provide a suitable marginal distribution to the initialization of the
message-passing decoder of LDPC codes. The performance of selected LDPC code
ensembles, analyzed by means of density evolution and finite-length
simulations under belief propagation (BP) and symbol message passing (SMP)
decoding, shows that BP decoding largely outperforms SMP decoding.
Nevertheless, the SMP algorithm retains a performance that is appealing for
applications (e.g., code-based cryptosystems in the Lee metric) demanding low-
complexity decoding.

## References

  * [1] W. Ulrich, “Non-binary error correction codes,” _The Bell System Technical Journal_ , vol. 36, no. 6, pp. 1341–1388, 1957.
  * [2] C. Lee, “Some properties of nonbinary error-correcting codes,” _IRE Transactions on Information Theory_ , vol. 4, no. 2, pp. 77–82, 1958.
  * [3] E. Prange, “The use of coset equivalene in the analysis and decoding of group codes,” Air Force Cambridge Research Labs, Tech. Rep., 1959.
  * [4] E. R. Berlekamp, “Negacyclic codes for the Lee metric,” North Carolina State University. Dept. of Statistics, Tech. Rep., 1966.
  * [5] S. W. Golomb and L. R. Welch, “Algebraic coding and the Lee metric,” _Error Correcting Codes_ , pp. 175–194, 1968.
  * [6] J. C.-Y. Chiang and J. K. Wolf, “On channels and codes for the Lee metric,” _Information and Control_ , vol. 19, no. 2, pp. 159–173, 1971.
  * [7] T. Etzion, A. Vardy, and E. Yaakobi, “Dense error-correcting codes in the Lee metric,” in _Proc. IEEE Information Theory Workshop_ , Sep. 2010.
  * [8] V. Weger, M. Battaglioni, P. Santini, A.-L. Horlemann-Trautmann, and E. Persichetti, “On the hardness of the lee syndrome decoding problem,” _arXiv preprint arXiv:2002.12785_ , 2020.
  * [9] V. Weger, M. Battaglioni, P. Santini, F. Chiaraluce, M. Baldi, and E. Persichetti, “Information set decoding of Lee-metric codes over finite rings,” _arXiv preprint arXiv:2001.08425_ , 2020.
  * [10] R. M. Roth and P. H. Siegel, “Lee-metric bch codes and their application to constrained and partial-response channels,” _IEEE Trans. Inf. Theory_ , vol. 40, no. 4, pp. 1083–1096, Apr. 1994.
  * [11] R. Gabrys, H. M. Kiah, and O. Milenkovic, “Asymmetric Lee distance codes for DNA-based storage,” _IEEE Trans. Inf. Theory_ , vol. 63, no. 8, pp. 4982–4995, Aug. 2017.
  * [12] J. L. Massey, “Notes on coding theory,” 1967.
  * [13] R. G. Gallager, _Low-Density Parity-Check Codes_. Cambridge, MA: M.I.T. Press, 1963.
  * [14] D. Sridhara and T. Fuja, “LDPC codes over rings for PSK modulation,” _IEEE Trans. Inf. Theory_ , vol. 51, no. 9, pp. 3209–3220, Sep. 2005.
  * [15] M. Davey and D. MacKay, “Low density parity check codes over GF$(q)$,” _IEEE Commun. Lett._ , vol. 2, no. 6, pp. 70–71, Jun. 1998.
  * [16] F. Lazaro, A. Graell i Amat, G. Liva, and B. Matuz, “Symbol message passing decoding of nonbinary low-density parity-check codes,” in _Proc. IEEE Global Commun. Conf._ , Dec. 2019.
  * [17] P. Santini, M. Battaglioni, F. Chiaraluce, M. Baldi, and E. Persichetti, “Low-Lee-Density Parity-Check Codes,” in _Proc. IEEE International Conference on Communications (ICC)_ , Jun. 2020.
  * [18] T. M. Cover and J. A. Thomas, _Elements of information theory_ , 2nd ed. New York: Wiley, 2006.
  * [19] M. Mezard and A. Montanari, _Information, physics, and computation_. Oxford University Press, 2009.
  * [20] L. Boltzmann, “Studien über das gleichgewicht der lebendigen kraft zwischen bewegten materiellen punkten,” _Wien. Ber_ , vol. 58, 1868.
  * [21] J. W. Gibbs, _Elementary principles in statistical mechanics: developed with special reference to the rational foundation of thermodynamics_. Yale Bicentennial Publications. New York, Scribner and Sons., 1902.
  * [22] Y. Polyanskiy, H. Poor, and S. Verdú, “Channel coding rate in the finite blocklength regime,” _IEEE Trans. Inf. Theory_ , vol. 56, no. 5, pp. 2307–2359, May 2010.
  * [23] G. Lechner, T. Pedersen, and G. Kramer, “Analysis and design of binary message passing decoders,” _IEEE Trans. Commun._ , vol. 60, no. 3, pp. 601–607, 2011.
  * [24] K. Xie and J. Li, “On accuracy of Gaussian assumption in iterative analysis for LDPC codes,” in _Proc. IEEE International Symposium on Information Theory_ , Jun. 2006.
  * [25] E. L. Wilmer, D. A. Levin, and Y. Peres, “Markov chains and mixing times,” _American Mathematical Soc., Providence_ , 2009.
  * [26] T. Richardson and R. Urbanke, “The capacity of low-density parity-check codes under message-passing decoding,” _IEEE Trans. Inf. Theory_ , vol. 47, no. 2, pp. 599–618, Feb. 2001.
  * [27] X.-Y. Hu, E. Eleftheriou, and D. Arnold, “Regular and irregular progressive edge-growth Tanner graphs,” _IEEE Trans. Inf. Theory_ , vol. 51, no. 1, pp. 386–398, Jan. 2005.

  *[DMC]: discrete memory-less channel
  *[ML]: maximum likelihood
  *[LDPC]: low-density parity-check
  *[BP]: belief propagation
  *[SMP]: symbol message-passing
  *[LSF]: Lee Symbol Flipping
  *[VN]: variable node
  *[CN]: check node
  *[CNs]: check node
  *[VNs]: variable node
  *[RV]: random variable
  *[RCU]: random coding union
  *[DE]: density evolution
  *[PMF]: probability mass function
  *[PMFs]: probability mass function
  *[$q$-SC]: q-ary symmetric channel
  *[BMP]: binary message-passing
  *[BSC]: binary symmetric channel
  *[TV]: total variation
  *[MCM]: Monte Carlo method
  *[PEG]: progressive edge growth