#  Efficient ADMM Decoder for Non-binary LDPC Codes with Codeword-Independent
Performance

Xiaomeng Guo, Yongchao Wang
State Key Laboratory of Intergrated Services Networks
Xidian University, Xi’an, China
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

In this paper, we devote to devise a non-binary low-density parity-check
(LDPC) decoder in Galois fields of characteristic two ($\mathbb{F}_{2^{q}}$)
via the alternating direction method of multipliers (ADMM) technique. Through
the proposed bit embedding technique and the decomposition technique of the
three-variables parity-check equation, an efficient ADMM decoding algorithm
for non-binary LDPC codes is proposed. The computation complexity in each ADMM
iteration is roughly $\mathcal{O}(nq)$, which is significantly lower than the
existing LDPC decoders. Moreover, we prove that the proposed decoder satisfies
the favorable property of the codeword-independent. Simulation results
demonstrate the outstanding performance of the proposed decoder in contrast
with state-of-the-art LDPC decoders.

###### Index Terms:

Non-binary Low-density Parity-check (LDPC) codes, Galois Fields of
Characteristic Two, Bit Embedding, Alternating Direction Method of Multipliers
(ADMM), Quadratic Programming (QP).

##  I Introduction

Since the high-data-rate requirement in the 5G [1] wireless communication
system, non-binary low-density parity-check (LDPC) codes [2] in Galois fields
of characteristic 2 ($\mathbb{F}_{2^{q}}$) are more favorable than binary
codes in bandwidth-efficient schemes when integrated with higher order
modulation [3]. Moreover, non-binary LDPC codes are competent to eliminate
short cycles [4] and resist burst errors [5], hence they can achieve superior
error correction performance than binary codes.

Recently, linear programming (LP) is applied to decode binary LDPC codes by
Feldman _et al_. [6] for the first time. In [6], the objective is designed as
the same to maximum likelihood (ML) decoding problem. Since then, many
researchers pay a lot of attention to the LP decoding techniques and the
analyzable decoding guarantees, i.e., convergence and codeword-independent
property. In contrast with the classical belief propagation (BP) decoders, the
general LP solving algorithms still face a difficult challenge, computational
complexity, especially when general solvers, such as interior point [7] method
or simplex method [8], is used. Then many works aiming to reduce the decoding
complexity have emerged. In [9], Barman _et al_. firstly introduced the
alternating direction method of multipliers (ADMM) [10] to the LP decoding
problem [6]. The complexity of this ADMM-based decoder is reduced sharply and
comparable to the BP decoder, however the time-consuming projection operations
onto parity polytopes in each iteration are still included. In [11], Bai _et
al_. utilized the three-variables parity-check equations decomposition
technique to construct an efficient ADMM-based decoder. Besides the efforts on
reducing the complexity, many works focus on the error correction performance
in low SNR regions. Taagavi and Siegel in [12] employed requisite parity-check
constraints adaptively to the proposed LP decoder to improve the decoding
performance. To eliminate the undesired pseudo-codewords, a series of cut-
generating algorithms [13]-[15] were proposed to improved the error correction
performance of the LP decoders. Moreover, Liu _et al_. in [16] and Bai _et
al_. in [17] constructed an ADMM-based variable node penalized decoder, Wei
_et al_. in [18] proposed an ADMM-based check node penalized decoder. These
decoders all added a non-convex term to the LP decoding objective, which
promoted the error correction performance of LP decoding in low SNR region and
did not suffer from the error-floor like BP decoders.

LP techniques were first introduced to non-binary LDPC codes by Flanagan in
[19]. As the same challenge the binary LP decoding encountered when used
general LP solvers, the non-binary LP decoding also faces the complexity
problem. To resolve this problem, a coordinate ascent method was applied in
[20] and [21] to solve the dual problem of the original LP problem [22] and
[23]. In [24], Rosnes proposed adaptive linear programming decoding of linear
codes over prime fields and dynamic programming was used in the separation
algorithm of the decoding polytopes described by the resulting inequalities.
Besides, Honda _et al_. in [25] proposed a constant-weight embedding which
used a binary vector to represent the element in $\mathbb{F}_{2^{q}}$, however
no further efficient algorithm was presented to tackle the resulting LP
problem. Furthermore, Liu and Draper in [26] proposed (non)penalized LP
decoding algorithms for non-binary LDPC codes in $\mathbb{F}_{2^{q}}$ based on
ADMM technique. Especially, the parity-check constraints are equivalently
transformed to a series of binary constraints through a factor graph
representation. Then the ADMM algorithm was applied to solve the resulting
decoding problem. However, the time-consuming Euclidean projections onto high
dimensional simplex polytopes are still required in each iteration of the
proposed ADMM decoder. Lately, Wang and Bai in [27] proposed a proximal-ADMM
decoder for non-binary LDPC codes. The three variables parity-check equations
decomposition technique was implemented together with the same equivalent
transform of the constraints in [26]. Then the proximal-ADMM algorithm was
used to generate a block-parallel updating scheme. To date, there are two
techniques, named as Flanagan embedding and Constant-Weight embedding
[19][26], which can map element in $\mathbb{F}_{2^{q}}$ one-to-one
correspondent to a length $2^{q}-1$ or length $2^{q}$ binary vector in real
space. Either results in computational complexity of the corresponding
decoding algorithms is proportional to $2^{q}$, i.e., the size of the
considered Galois fields [26][27].

In this paper, our main concern is devising a novel non-binary LDPC decoder
with competitive error correction performance and lower decoding complexity,
meanwhile the codeword-independent performance has to be theoretically-
guaranteed. The main contents of this paper are summarized as follows:

  * •

Different from the embedding techniques in [19] and [25], we propose a new
embedding method, named bit embedding, to represent the elements in finite
fields by a binary vector of dimension $q$ in real space, under which the
decoding complexity grows linearly instead of grows exponentially ([26][27])
as the considered length $q$ grows. We also introduce a equivalent transform
of the non-binary parity-check constraints to a series of binary parity-check
constraints under the bit embedding.

  * •

Based on the three variables parity-check equations decomposition technique
and its equivalent binary inequalities formulation, we decompose the multi-
variables binary parity-check constraints and transform the non-binary ML
decoding problem to an equivalent linear integer program. Then we relax the
binary constraints to box constraints and add a quadratic penalty term to the
objective, a new quadratic programming (QP) decoding model is built for non-
binary LDPC codes in $\mathbb{F}_{2^{q}}$.

  * •

We exploit the ADMM algorithm to solve the resulting QP decoding model.
Utilizing the special intrinsic structure of the QP problem, all the variables
in one ADMM iteration can be updated in a full-parallel pattern.

  * •

The performance of the proposed ADMM decoding algorithm satisfies the
favorable property of the codeword-independent. Moreover, its complexity in
each iteration is roughly $\mathcal{O}(nq)$.

  * •

We show through numerical simulations that the proposed ADMM decoder
outperforms state-of-the-art decoders in error correction performance and
complexity.

To facilitate reading of this paper, notations are explained explicitly in
Table I. The operator “$\otimes$” are specifically defined as follows.

  * •

For matrices $\mathbf{A}\in\mathbb{R}^{m\times n}$ and
$\mathbf{B}\in\mathbb{R}^{p\times q}$,
$\mathbf{A}\otimes\mathbf{B}=\begin{bmatrix}a_{11}\mathbf{B}&\cdots&a_{1n}\mathbf{B}\\\
\vdots&\ddots&\vdots\\\
a_{m1}\mathbf{B}&\cdots&a_{mn}\mathbf{B}\end{bmatrix}\in\mathbb{R}^{mp\times
nq}$.

  * •

For column vectors $\mathbf{a}=[a_{1},\ldots,a_{m}]^{T}$ and
$\mathbf{b}=(b_{1},\ldots,b_{n})^{T}$,
$\mathbf{a}\otimes\mathbf{b}=[a_{1}\mathbf{b};\ldots;a_{m}\mathbf{b}]\in\mathbb{R}^{mn}$.

  * •

For column vector $\mathbf{a}=[a_{1},\ldots,a_{m}]^{T}$ and matrix
$\mathbf{B}\in\mathbb{R}^{p\times q}$,
$\mathbf{a}\otimes\mathbf{B}=[a_{1}\mathbf{B},\ldots,a_{m}\mathbf{B}]\in\mathbb{R}^{mp\times
n}$.

TABLE I: Notations and Descriptions. Notations |  Descriptions
---|---
$\mathbb{F}_{2^{q}}$ | Galois field of characteristic two
$\mathbb{R}$ | The set of real numbers
$\mathbf{A}$ | Matrix
$\mathbf{a}$ | Column vector
$a$ | Scalar
$\\{0,1\\}^{a}$ | a-length binary column vector
$\\{0,1\\}^{a\times b}$ | a-by-b binary matrix
$[\mathbf{a};\mathbf{b}]$ or $[\mathbf{A};\mathbf{B}]$ | Vectors or matrices are concatenated in column-wise
$[\mathbf{a},\mathbf{b}]$ or $[\mathbf{A},\mathbf{B}]$ | Vectors or matrices are concatenated in row-wise
$\mathbf{1}_{a}$ or $\mathbf{1}_{a\times b}$ | Length-$a$ all-ones vector or $a$-by-$b$ all-ones matrix
$\mathbf{0}_{a}$ or $\mathbf{0}_{a\times b}$ | Length-$a$ all-zeros vector or $a$-by-$b$ all-zeros matrix
$\mathbf{I}_{a}$ |  $a\times a$ identity matrix
$(\cdot)^{T}$ | Transpose operator
$\|\cdot\|_{2}$ |  $\ell_{2}$-norm
$\preceq$ | Generalized inequality
$\otimes$ | Kronecker product
$\delta_{\mathbf{A}}$ | Spectral norm of matrix $\mathbf{A}$
$\lambda_{\min}(\mathbf{A}^{T}\\!\mathbf{A})$ | Minimum eigenvalue of matrix $\mathbf{A}^{T}\mathbf{A}$
$\underset{\mathcal{X}}{\Pi}$ | Euclidean projection onto set $\mathcal{X}$

The rest of this paper is organized as follows. In Section II, we transform
the non-binary ML decoding problem to an equivalent linear integer program
based on the decomposition technique and the proposed bit embedding technique.
In Section III, we establish a relaxed QP decoding problem for non-binary LDPC
codes. Then an efficient ADMM decoding algorithm is proposed to solve the
resulting relaxed QP problem. Section IV presents the codeword-independent and
the complexity analysis of the proposed ADMM decoding algorithm. Simulation
results show the effectiveness of our proposed ADMM decoder in Section V.
Section VI concludes this paper.

##  II ML Decoding problem formulation and its equivalent lineal integer
program

Consider a non-binary LDPC codeword defined by an $m$-by-$n$ parity-check
matrix $\mathbf{H}$ in $\mathbb{F}_{2^{q}}$. Its feasible codeword set
$\mathcal{C}$ can be denoted by

$\mathcal{C}=\\{\mathbf{c}|\mathbf{h}^{T}_{j}\mathbf{c}=0,j\in\mathcal{J},\mathbf{c}\in\mathbb{F}_{2^{q}}^{n}\\},$
(1)

where $\mathbf{h}^{T}_{j}$, $j\in\mathcal{J}=\\{1,2,\cdots,m\\}$ denotes the
$j$-th row vector of the parity-check matrix $\mathbf{H}$.

Pass the codeword $\mathbf{c}\in\mathcal{C}$ through an additional white
Gaussian noise (AWGN) channel and denote its output as $\mathbf{r}$. In the
receiver, the aim of ML decoding is to determine which codeword has the
largest a priori probability $p(\mathbf{r}|\mathbf{c})$ throughout the
codeword set $\mathcal{C}$. So the ML decoding problem can be described as

$\displaystyle\underset{\mathbf{c}}{\rm max}\ $ $\displaystyle
p(\mathbf{r}|\mathbf{c}),$ (2a) $\displaystyle{\rm s.t.}\ $
$\displaystyle\mathbf{h}^{T}_{j}\mathbf{c}=0,\
j\in\mathcal{J},\mathbf{c}\in\mathbb{F}_{2^{q}}^{n}.$ (2b)

For any integer $c_{i}\in\mathbf{c}$, we introduce a new mapping that embeds
elements in $\mathbb{F}_{2^{q}}$ into the Euclidean space of dimension $q$.

######  Definition 1.

Bit embedding: Let $f:\mathbb{F}_{2^{q}}\mapsto\\{0,1\\}^{q}$ be a mapping
such that for $c_{i}\in\mathbb{F}_{2^{q}}$,

$f(c_{i}):=\mathbf{x}_{i}=[x_{i,1},\cdots,x_{i,\sigma},\cdots,x_{i,q}]^{T},$

where $x_{i,\sigma}$ comes from the polynomial representation of
$c_{i}\in\mathbb{F}_{2^{q}}$

$p(2)=\sum^{q}_{\sigma=1}2^{\sigma-1}x_{i,\sigma}.$ (3)

Under this embedding rule, any codeword $\mathbf{c}$ can be mapped to a binary
vector $\mathbf{x}=[\mathbf{x}_{1};\cdots;\mathbf{x}_{n}]\in\\{0,1\\}^{nq}$.
We name the new embedding technique as the bit embedding, since the embedding
vector $\mathbf{x}_{i}$ is the bit representation of
$c_{i}\in\mathbb{F}_{2^{q}}$. We call $\mathbf{x}$ as an equivalent binary
codeword of the non-binary codeword $\mathbf{c}$.

Define a new vector
$\hat{\mathbf{h}}^{(j,i)}=h_{j,i}\cdot[2^{q-1},\cdots,2,1]$ with $q$-length,
where all elements in $\hat{\mathbf{h}}^{(j,i)}$ and the multiplication are in
$\mathbb{F}_{2^{q}}$. Map all the elements in $\hat{\mathbf{h}}^{(j,i)}$ to a
column vector by the bit embedding and concatenate all the column vectors in
row-wise, which leads to the embedding result
$\hat{\mathbf{H}}_{j,i}\in\\{0,1\\}^{q\times q}$.222We present an example of
the above procedure. Consider $h_{j,i}=6\in\mathbb{F}_{2^{3}}$, then
$6\cdot[4,2,1]=[5,7,6]$. Embed $5$, $7$, $6$ respectively,
$5\mapsto[1,0,1]^{T}$, $7\mapsto[1,1,1]^{T}$, $6\mapsto[1,1,0]^{T}$. Then
$\hat{\mathbf{H}}_{j,i}=\begin{bmatrix}1\ 1\ 1\\\ 0\ 1\ 1\\\ 1\ 1\
0\end{bmatrix}$. Then, we have the following lemma.

######  Lemma 1.

With $\mathbf{x}_{i}$ as the equivalent binary codeword of the non-binary
codeword $c_{i}$ according to the mapping rule (3). Then,
$\hat{\mathbf{H}}_{j,i}\mathbf{x}_{i}$ is an equivalent binary codeword to
$h_{j,i}c_{i}$ mapped according to the same rule.

###### Proof.

See Appendix A. ∎

Based on Lemma 1, the parity-check equation
$h_{j,1}c_{1}+h_{j,2}c_{2}+\cdots+h_{j,n}c_{n}=0$ in (2b) is equivalent to the
following parity-check equations in $\mathbb{F}_{2}$:

$\hat{\mathbf{H}}_{j,1}\mathbf{x}_{1}+\cdots+\hat{\mathbf{H}}_{j,n}\mathbf{x}_{n}=0,$
(4)

which is equal to

$\hat{\mathbf{H}}_{j}\mathbf{x}=0,$ (5)

where
$\hat{\mathbf{H}}_{j}=[\hat{\mathbf{H}}_{j,1},\cdots,\hat{\mathbf{H}}_{j,n}]\in\\{0,1\\}^{q\times
nq}$.

Figure 1: The graph representation for equivalence between the three-variables
parity-check equation in $\mathbb{F}_{4}$ and the two six-variables parity-
check equations in $\mathbb{F}_{2}$, where
$h_{1},h_{2},h_{3}\in\mathbb{F}_{4}\setminus 0$,
$c_{1},c_{2},c_{3}\in\mathbb{F}_{4}$ and
$\hat{h}_{1,1}^{(1)},\hat{h}_{1,2}^{(1)},\hat{h}_{2,1}^{(1)},\hat{h}_{2,2}^{(1)},\hat{h}_{1,1}^{(2)},\hat{h}_{1,2}^{(2)},\hat{h}_{2,1}^{(2)},\hat{h}_{2,2}^{(2)},\hat{h}_{1,1}^{(3)},\hat{h}_{1,2}^{(3)},\hat{h}_{2,1}^{(3)},\hat{h}_{2,2}^{(3)},x_{1,1},x_{1,2},x_{2,1},x_{2,2},x_{3,1},x_{3,2}\in\mathbb{F}_{2}$.

Assume the degree of $\mathbf{h}_{j}^{T}$ in (2b) is three, then Figure 1
shows an example of equivalence three-variables parity-check equation in
$\mathbb{F}_{4}$ and two six-variables parity-check equations in
$\mathbb{F}_{2}$ following Lemma 1 .

Let $\mathcal{X}$ denotes the set consisting of all equivalent binary
codewords. Then the ML decoding problem (2) can be transformed to

$\displaystyle\underset{\mathbf{x}}{\rm max}\ $ $\displaystyle
p(\mathbf{r}|\mathbf{x}),$ (6a) $\displaystyle{\rm s.t.}\ $
$\displaystyle\hat{\mathbf{H}}_{j}\mathbf{x}=0,\ j\in\mathcal{J},$ (6b)
$\displaystyle\mathbf{x}\in\\{0,1\\}^{nq}.$ (6c)

######  Assumption 1.

The output of the channel is bit-independent, i.e.,
$p(\mathbf{r}|\mathbf{x})=\displaystyle\prod^{n}_{i=1}\displaystyle\prod_{\sigma=1}^{q}p(r_{i}|x_{i,\sigma})$.

Based on the above assumption, we can derive the optimization model (6a) as

$\displaystyle\underset{\mathbf{x}\in\mathcal{X}}{\rm argmax}\
p(\mathbf{r}|\mathbf{x})=$
$\displaystyle\underset{\mathbf{x}\in\mathcal{X}}{\rm
argmax}\prod^{n}_{i=1}\prod_{\sigma=1}^{q}p(r_{i}|x_{i,\sigma})$ (7)
$\displaystyle=$ $\displaystyle\underset{\mathbf{x}\in\mathcal{X}}{\rm
argmin}\sum^{n}_{i=1}\sum^{q}_{\sigma=1}-{\rm{log}}\ p(r_{i}|x_{i,\sigma}).$

Putting the constant
$\displaystyle\sum^{n}_{i=1}\displaystyle\sum^{q}_{\sigma=1}{\rm{log}}\
p(r_{i}|x_{i,\sigma}=0)$ into (7), we get

$\displaystyle\underset{\mathbf{x}\in\mathcal{X}}{\rm argmax}\
p(\mathbf{r}|\mathbf{x})=$
$\displaystyle\underset{\mathbf{x}\in\mathcal{X}}{\rm
argmin}\sum^{n}_{i=1}\sum^{q}_{\sigma=1}{\rm{log}}\
\frac{p(r_{i}|x_{i,\sigma}=0)}{p(r_{i}|x_{i,\sigma})}$ (8) $\displaystyle=$
$\displaystyle\underset{\mathbf{x}\in\mathcal{X}}{\rm
argmin}\sum^{n}_{i=1}\sum^{q}_{\sigma=1}x_{i,t}{\rm{log}}\
\frac{p(r_{i}|x_{i,\sigma}=0)}{p(r_{i}|x_{i,\sigma}=1)}$ $\displaystyle=$
$\displaystyle\underset{\mathbf{x}\in\mathcal{X}}{\rm argmin}\
{\boldsymbol{\gamma}}^{T}\mathbf{x},$

where $\boldsymbol{\gamma}\in\mathbb{R}^{nq}$ is defined by

$\displaystyle\boldsymbol{\gamma}=$
$\displaystyle\left[{\rm{log}}\frac{p(r_{1}|x_{1,1}=0)}{p(r_{1}|x_{1,1}=1)},\cdots,{\rm{log}}\frac{p(r_{1}|x_{1,q}=0)}{p(r_{1}|x_{1,q}=1)},\right.$
(9)
$\displaystyle\left.\cdots,{\rm{log}}\frac{p(r_{n}|x_{n,1}=0)}{p(r_{n}|x_{n,1}=1)},\cdots,{\rm{log}}\frac{p(r_{n}|x_{n,q}=0)}{p(r_{n}|x_{n,q}=1)}\right].$

Then the ML decoding problem (6) can be formulated as the following integer
program

$\displaystyle\underset{\mathbf{x}}{\rm min}\ $
$\displaystyle{\boldsymbol{\gamma}}^{T}\mathbf{x},$ (10a) $\displaystyle{\rm
s.t.}\ $ $\displaystyle\hat{\mathbf{H}}_{j}\mathbf{x}=0,\ j\in\mathcal{J},$
(10b) $\displaystyle\mathbf{x}\in\\{0,1\\}^{nq}.$ (10c)

Observing problem (10), one can see that the difficulty of solving it lies in
how to handle the non-convex binary parity-check constraints (10b) and the
integer constraint (10c). To address these challenges, we first decompose the
parity-check equations in (10b) to a series of three-variables binary ones and
express them by some linear inequalities.

First we consider the three-variables parity-check equation in
$\mathbb{F}_{2}$

$x_{1}+x_{2}+x_{3}=0,x_{i}\in\\{0,1\\},i\in\\{1,2,3\\},$ (11)

which can be equivalent to the following inequality system defined in real
space

$\displaystyle x_{1}\leq x_{2}+x_{3},\quad x_{2}\leq x_{1}+x_{3},$ (12)
$\displaystyle x_{3}\leq x_{1}+x_{2},\quad x_{1}+x_{2}+x_{3}\leq 2,$
$\displaystyle x_{1},x_{2},x_{3}\in\\{0,1\\}$

in the sense that (11) and (12) have the same solutions. Define

$\displaystyle\mathbf{w}=\begin{bmatrix}\ 0\ \\\ \ 0\ \\\ \ 0\ \\\ \ 2\
\end{bmatrix},\mathbf{T}=\begin{bmatrix}~{}~{}1&-1&-1\\\ -1&~{}~{}1&-1\\\
-1&-1&~{}~{}1\\\ ~{}~{}1&~{}~{}1&~{}~{}1\end{bmatrix}.$ (13)

Then, (11) can be rewritten as

$\mathbf{Tx}\preceq\mathbf{w},\mathbf{x}\in\\{0,1\\}^{3},$ (14)

where $\mathbf{x}=[x_{1},x_{2},x_{3}]^{T}$.

This technique can be applied to the general parity-check equation with more
than three variables and formulate its equivalent expression. Especially, we
consider the $t$-th ($t\in\\{1,\cdots,mq\\}$) parity-check equation in (10b).
Without loss of generality, we assume it involves $d_{t}\geq 3$ variables,
which are denoted by $x_{\sigma_{1}},\cdots,x_{\sigma_{d_{t}}}$, the
corresponding coefficients $h_{\sigma_{1}},\cdots,h_{\sigma_{d_{t}}}$ are 1
and others are 0. For the first two variables $x_{\sigma_{1}}$ and
$x_{\sigma_{2}}$, we introduce an auxiliary variable $a_{1}$ and let them
satisfy the three-variables parity-check equation
$a_{1}+h_{\sigma_{1}}x_{\sigma_{1}}+h_{\sigma_{2}}x_{\sigma_{2}}=0$. For the
variables $x_{\sigma_{3}},\cdots,x_{\sigma_{d_{t}-3}}$, we introduce two
auxiliary variables $a_{k-1}$ and $a_{k}$ for one variable and let them
satisfy
$a_{k-1}+h_{\sigma_{k+1}}x_{\sigma_{k+1}}+a_{k}=0,k\in\\{2,\cdots,d_{t}-3\\}$.
Let the auxiliary variable $a_{d_{t}-3}$ and the last two variables satisfy
$a_{d_{t}-3}+h_{\sigma_{d_{t}-1}}x_{\sigma_{d_{t}-1}}+h_{\sigma_{d_{t}}}x_{\sigma_{d_{t}}}=0$.
Following this procedure, we can avoid the special kind of three-variables
parity-check equations that consists of all auxiliaries variables.

Consequently, the multi-variables parity-check equations are decomposed into
finite three-variables ones. Moreover, the numbers of the introduced auxiliary
variables and the corresponding three-variables parity-check equations are
calculated by $d_{t}-3$ and $d_{t}-2$ respectively. Then, the total numbers of
the three-variables parity-check equations and the introduced auxiliary
variables corresponding to the constraints (10b) are

$\Gamma_{c}=\displaystyle\sum_{t=1}^{mq}(d_{t}-2),\
\Gamma_{a}=\displaystyle\sum_{t=1}^{mq}(d_{t}-3),$ (15)

respectively. Define
$\mathbf{v}=[\mathbf{x};\mathbf{u}]\in\\{0,1\\}^{nq+\Gamma_{a}}$, where
auxiliary variables $\mathbf{u}\in\\{0,1\\}^{\Gamma_{a}}$. Define a variable-
selecting matrix $\mathbf{Q}_{\tau}\in\\{0,1\\}^{3\times(nq+\Gamma_{a})}$ of
which very row vector includes only one ”1” and corresponds to the variables
in the $\tau$-th three-variables parity-check equation,
$\tau=1,\cdots,\Gamma_{c}$. Then it can be expressed as
$\mathbf{T}\mathbf{Q}_{\tau}\mathbf{v}\preceq\mathbf{w}$. Furthermore, we
define

$\displaystyle\mathbf{q}$
$\displaystyle=[{\boldsymbol{\gamma}};\mathbf{0}_{\Gamma_{a}}]^{T}\in\mathbb{R}^{N},$
(16a) $\displaystyle\mathbf{A}$
$\displaystyle=[\mathbf{T}\mathbf{Q}_{1};\cdots;\mathbf{T}\mathbf{Q}_{\tau};\cdots;\mathbf{T}\mathbf{Q}_{\Gamma_{c}}]\in\mathbb{R}^{M\times
N},$ (16b) $\displaystyle\mathbf{b}$
$\displaystyle=\mathbf{1}_{\Gamma_{c}}\otimes\mathbf{w}\in\mathbb{R}^{M},$
(16c)

where $M=4\Gamma_{c}$ and $N=nq+\Gamma_{a}$. Then the ML decoding problem (10)
is equivalent to the following linear integer program

$\displaystyle\min_{\mathbf{v}}\ $ $\displaystyle\mathbf{q}^{T}\mathbf{v},$
(17a) $\displaystyle{\rm s.t.}\ $ $\displaystyle\mathbf{Av}\preceq\mathbf{b},$
(17b) $\displaystyle\mathbf{v}\in\\{0,1\\}^{nq+\Gamma_{a}},.$ (17c)

Due to the discrete binary constraints (17c), problem (17) is non-convex and
difficult to solve. In the following, we relax it to a continuous, non-convex,
but tractable model.

##  III Non-convex QP formulation and its ADMM solving algorithm

###  III-A Non-Convex QP Formulation

A classical way for the binary constraint (17c) is to relax it to a box
constraint $\mathbf{v}\in[0,1]^{nq+\Gamma_{a}}$, which can simplify the non-
convex problem (17) to a convex one. However, the resulting optimization
problem’s solution could be a fractional especially when the decoder works in
the low SNR regions. Therefore we add a quadratic penalty term into the
objective (17a), which leads to the following non-convex QP decoder

$\displaystyle\min_{\mathbf{v}}\ $
$\displaystyle\mathbf{q}^{T}\mathbf{v}-\frac{\alpha}{2}\|\mathbf{v}-0.5\|^{2}_{2},$
(18a) $\displaystyle{\rm s.t.}\ $ $\displaystyle\mathbf{Av}\preceq\mathbf{b},$
(18b) $\displaystyle\mathbf{v}\in[0,1]^{nq+\Gamma_{a}}.$ (18c)

Inspired by the intrinsic structure of model (18), we propose an efficient
solving algorithm via the ADMM technique. In it, the variables in every ADMM
iteration can be solved analytically and in a full-parallel pattern.
Meanwhile, the computational complexity in each iteration scales linearly with
the non-binary LDPC codes length and the considered length $q$.

###  III-B ADMM Algorithm Framework

By introducing auxiliary variable $\mathbf{e}_{1}$ and $\mathbf{e}_{2}$, the
decoding problem (18) can be equivalent to

$\displaystyle\min_{\mathbf{v}}\ $
$\displaystyle\mathbf{q}^{T}\mathbf{v}-\frac{\alpha}{2}\|\mathbf{v}-0.5\|^{2}_{2},$
(19a) $\displaystyle{\rm s.t.}\ $
$\displaystyle\mathbf{Av}+\mathbf{e}_{1}=\mathbf{b},$ (19b)
$\displaystyle\mathbf{v}=\mathbf{e}_{2},$ (19c)
$\displaystyle\mathbf{e}_{1}\succeq\mathbf{0}_{4\Gamma_{c}},\mathbf{e}_{2}\in[0,1]^{nq+\Gamma_{a}}.$
(19d)

Its augment Lagrangian function can be written as

$\displaystyle\mathcal{L}_{\mu}(\mathbf{v},\mathbf{e}_{1},\mathbf{e}_{2},\mathbf{y}_{1},\mathbf{y}_{2})$
$\displaystyle=\mathbf{q}^{T}\mathbf{v}\\!-\\!\frac{\alpha}{2}\|\mathbf{v}-0.5\|^{2}_{2}\\!+\\!\mathbf{y}_{1}^{T}(\mathbf{Av}+\mathbf{e}_{1}-\mathbf{b})$
(20)
$\displaystyle\\!+\\!\mathbf{y}_{2}^{T}(\mathbf{v}\\!-\\!\mathbf{e}_{2})\\!+\\!\frac{\mu}{2}\|\\!\mathbf{Av}\\!+\\!\mathbf{e}_{1}\\!-\\!\mathbf{b}\\!\|^{2}_{2}\\!+\\!\frac{\mu}{2}\|\\!\mathbf{v}\\!-\\!\mathbf{e}_{2}\\!\|^{2}_{2},$

where $\mathbf{y}_{1}\in\mathbb{R}^{4\Gamma_{c}}$ and
$\mathbf{y}_{2}\in\mathbb{R}^{nq+\Gamma_{a}}$ are Lagrangian multipliers and
$\mu>0$ is a preset penalty parameter. Based on the augment Lagrangian (20),
the ADMM solving algorithm for model (19) can be described as

$\displaystyle\mathbf{v}^{k+1}$ $\displaystyle=\underset{\mathbf{v}}{{{\rm
argmin}}}\ \mathcal{L}_{\mu}\
(\mathbf{v},\mathbf{e}_{1}^{k},\mathbf{e}_{2}^{k},\mathbf{y}_{1}^{k},\mathbf{y}_{2}^{k}),$
(21a) $\displaystyle\mathbf{e}_{1}^{k+1}$
$\displaystyle=\underset{\mathbf{e}_{1}\succeq 0}{{\rm argmin}}\
\mathcal{L}_{\mu}\
(\mathbf{v}^{k+1},\mathbf{e}_{1},\mathbf{e}_{2}^{k},\mathbf{y}_{1}^{k},\mathbf{y}_{2}^{k}),$
(21b) $\displaystyle\mathbf{e}_{2}^{k+1}$
$\displaystyle=\underset{0\preceq\mathbf{e}_{2}\preceq 1}{{\rm argmin}}\
\mathcal{L}_{\mu}\
(\mathbf{v}^{k+1},\mathbf{e}_{1}^{k+1},\mathbf{e}_{2},\mathbf{y}_{1}^{k},\mathbf{y}_{2}^{k}),$
(21c) $\displaystyle\mathbf{y}_{1}^{k+1}$
$\displaystyle=\mathbf{y}_{1}^{k}+\mu(\mathbf{Av}^{k+1}+\mathbf{e}_{1}^{k+1}-\mathbf{b}),$
(21d) $\displaystyle\mathbf{y}_{2}^{k+1}$
$\displaystyle=\mathbf{y}_{2}^{k}+\mu(\mathbf{v}^{k+1}-\mathbf{e}_{2}^{k+1}),$
(21e)

where $k$ denotes the iteration number.

In the following we show that the subproblems (21a)-(21c) can be solved
efficiently be exploiting the inherent structure of the model.

####  III-B1 Solving Subproblem (21a)

Based on the fact that matrix $\mathbf{A}$ has the property of orthogonality
in columns333Since $\mathbf{T}$ is column-wise orthogonal matrix, $\mathbf{A}$
is also orthogonal in columns. Besides, it can be found that elements in
$\mathbf{A}$ are either 0,1 or -1., hence $\mathbf{A}^{T}\mathbf{A}$ is a
diagonal matrix, which means that variables in problem (21a) are separable.
Therefore the $nq+\Gamma_{a}$ entries of $\mathbf{v}^{k+1}$ can be obtained by
solving the following $nq+\Gamma_{a}$ subproblems in parallel

$\min_{v_{i}}\frac{1}{2}\\!(\\!\mu
s_{i}-\\!\alpha+\\!\mu\\!)v_{i}^{2}\\!+\\!(\\!q_{i}+y_{2,i}^{k}+\\!\mu
e_{2,i}^{k+1}\\!\\!+\\!\frac{1}{2}\\!\alpha\\!+\mathbf{a}^{T}_{i}\\!(\\!\mathbf{y}_{1}^{k}\\!+\\!\mu(\mathbf{e}_{1}^{k+1}\\!\\!-\\!\mathbf{b})))v_{i},$
(22)

where $\mathbf{s}={\rm
diag}(\mathbf{A}^{T}\mathbf{A})=[s_{1},\cdots,s_{nq+\Gamma_{a}}]^{T}$ and
$\mathbf{a}^{T}_{i}$ denotes the $i$th row vector of matrix $\mathbf{A}$.

To guarantee that (22) is strong convex, we choose proper $\alpha$ and $\mu$
and let them satisfy $\mu(s_{\rm min}+1)>\alpha$, where $s_{\rm min}$ denote
the minimum value of the elements in vector $\mathbf{s}$. Then the solution of
problem (22) can be obtained by setting the gradient of objective (22) to
zero, i.e.,

$v_{i}^{k+1}=\left(\frac{\mathbf{a}_{i}^{T}(\mathbf{b}-\mathbf{e}_{1}^{k}-\frac{\mathbf{y}_{1}^{k}}{\mu})+e_{2,i}^{k}-\frac{y_{2,i}^{k}}{\mu}-\phi_{i}}{\theta_{i}}\right)$
(23)

where $i\in\\{1,\cdots,nq+\Gamma_{a}\\}$,
$\phi_{i}=\frac{2q_{i}+\alpha}{2\mu}$ and
$\theta_{i}=s_{i}-\frac{\alpha}{\mu}+1$.

####  III-B2 Solving Subproblem (21b)

Obviously, all the entries in $\mathbf{e}_{1}$ are separable in both objective
and constraints. Thus the optimal solution of problem (21b) can be obtained by
setting the gradient of the function $\mathcal{L}_{\mu}\
(\mathbf{v}^{k+1},\mathbf{e}_{1},\mathbf{e}_{2}^{k},\mathbf{y}_{1}^{k},\mathbf{y}_{2}^{k})$
to zero, then project the resulting solution of the corresponding linear
equation to region $[0,+\infty]^{4\Gamma_{c}}$, i.e.,

$\mathbf{e}_{1}^{k+1}=\underset{[0,+\infty]^{4\Gamma_{c}}}{\Pi}\left((\mathbf{b}-\mathbf{A}\mathbf{v}^{k+1})-\frac{\mathbf{y}_{1}^{k}}{\mu}\right)$
(24)

Explicitly, all the entries of $\mathbf{e}_{1}$ can also be obtained in
parallel by

$e^{k+1}_{1,j}=\underset{[0,+\infty]}{\Pi}\left((b_{j}-\mathbf{a}^{T}_{j}\mathbf{v}^{k+1})-\frac{y^{k}_{1,j}}{\mu}\right)$
(25)

where $j\in\\{1,\cdots,4\Gamma_{c}\\}$ and
$\underset{[0,+\infty]}{\Pi}(\cdot)$ denotes the projection operator onto the
positive quadrant $[0,+\infty]$.

####  III-B3 Solving Subproblem (21c)

To obtain the solution of $\mathbf{e}_{2}$, similarly, we set the gradient of
the function $\mathcal{L}_{\mu}\
(\mathbf{v}^{k+1},\mathbf{e}_{1}^{k+1},\mathbf{e}_{2},\mathbf{y}_{1}^{k},\mathbf{y}_{2}^{k})$
to zero, then project the resulting solution of the corresponding linear
equation to region $[0,1]^{nq+\Gamma_{a}}$, i.e.,

$\mathbf{e}_{2}^{k+1}=\underset{[0,1]^{nq+\Gamma_{a}}}{\Pi}\left(\mathbf{v}^{k+1}+\frac{\mathbf{y}_{2}^{k}}{\mu}\right)$
(26)

Specially, all the entries of $\mathbf{e}_{2}$ can also be obtained in
parallel by

$e^{k+1}_{2,i}=\underset{[0,1]}{\Pi}\left(v_{i}^{k+1}+\frac{y_{2,i}^{k}}{\mu}\right)$
(27)

where $i\in\\{1,\cdots,nq+\Gamma_{a}\\}$ and $\underset{[0,1]}{\Pi}(\cdot)$
denotes the projection operator onto the interval $[0,1]$.

Since variables $\mathbf{y}_{1}$ and $\mathbf{y}_{2}$ are engaged in (25) and
(27) by its scaled form $\frac{\mathbf{y}_{1}}{\mu}$ and
$\frac{\mathbf{y}_{2}}{\mu}$, thus we update its scaled form to save
multiplications. Therefore, we define
$\tilde{e}^{k+1}_{1,j}=b_{j}-\mathbf{a}^{T}_{j}\mathbf{v}^{k+1}-\frac{y^{k}_{1,j}}{\mu}$
and $\tilde{e}^{k+1}_{2,i}=v_{i}^{k+1}+\frac{y_{2,i}^{k}}{\mu}$. Then, each
element in $\mathbf{y}_{1}$ and $\mathbf{y}_{2}$ can be obtained through

$\frac{y_{1,j}^{k+1}}{\mu}=\left\\{\begin{array}[]{cc}0,&\text{ if
}\tilde{e}_{1,j}^{k+1}\geq 0,\\\ -\tilde{e}_{1,j}^{k+1},&\text{ otherwise
,}\end{array}\right.$ (28)

$\frac{y_{2,i}^{k+1}}{\mu}=\left\\{\begin{array}[]{cc}0,&\text{ if
}1\geq\tilde{e}_{1,j}^{k+1}\geq 0,\\\ \tilde{e}_{2,i}^{k+1},&\text{ if
}\tilde{e}_{1,j}^{k+1}\leq 0,\\\ \tilde{e}_{2,i}^{k+1}-1,&\text{ if
}\tilde{e}_{1,j}^{k+1}\geq 1.\end{array}\right.$ (29)

In Algorithm 1, we summarize the proposed ADMM decoding algorithm for solving
model (19).

##  IV Performance analysis

###  IV-A Codeword-independent property

In the following, we prove one important characteristic of linear codes, that
under the symmetric channel condition, the failure probability of the decoding
algorithm is independent of the codeword that is transmitted. We prove this
property holds for our proposed non-binary ADMM decoder under the bit
embedding.

######  Theorem 1.

Under the channel symmetry condition in the sense of [19], the probability
that Algorithm 1 fails is independent of the codeword that was transmitted.

###### Proof.

See Appendix B. ∎

###  IV-B Computational complexity

In this subsection, we we focus on analyzing the complexity of the proposed
Algorithm 1 in each iteration. Moreover the presented result only includes
multiplications since they cost the most computational resource in practice.
Now Since all the entries in matrix $\mathbf{A}$ are either 0, 1 or -1, we can
see that all multiplications with regard to $\mathbf{A}$ can be replaced by
addition. Moreover, $\phi_{i}$ and $\theta_{i}$ in (23) can be calculated in
advance before we launch the ADMM iterations.

Consider updating $\mathbf{v}^{k+1}$ first. Based on the analytic solution of
$v_{i}^{k+1}$ in (23), one can find that updating $\mathbf{v}^{k+1}$ costs
$nq+\Gamma_{a}$ multiplications. Moreover, observing (25) and (27), we can
find that it takes no multiplication operation to update
$\mathbf{e}_{1}^{k+1}$ and $\mathbf{e}_{2}^{k+1}$. In addition, observing
variables $\mathbf{y}_{1}$ and $\mathbf{y}_{2}$ in (25), (27) and (23),
apparently their scalded form $\frac{\mathbf{y}_{1}}{\mu}$ and
$\frac{\mathbf{y}_{2}}{\mu}$ are engaged in updating. Hence we conclude that
calculating $\frac{\mathbf{y}_{1}^{k+1}}{\mu}$ and
$\frac{\mathbf{y}_{2}^{k+1}}{\mu}$ only need some addition operations from
(28) and (29). Based on the above analysis, the total multiplications of
Algorithm 1 in each iteration are $nq+\Gamma_{a}$.

Moreover, one can find that $\Gamma_{a}\leq mq(d-3)=nq(1-R)(d-3)$, where $R$
denotes the code rate and $d$ is the largest check node degree. This implies
that $\Gamma_{a}$ is comparable to code length $n$ since $d\ll n$ in the case
of LDPC codes. Hence we conclude that the computational complexity of the
proposed ADMM decoding algorithm in every iteration scales linearly the non-
binary LDPC code length and the considered length $q$, or roughly
$\mathcal{O}(nq)$. Moreover, we should note that the entries in $\mathbf{v}$,
$\mathbf{e}_{1}$, $\mathbf{e}_{2}$, $\mathbf{y}_{1}$ and $\mathbf{y}_{2}$ can
be updated in a full-parallel pattern in contrast with [27], which indicates
it is free of time-consuming Euclidean projection onto high dimensional
parity-check/simplex polytopes ([26]).

Algorithm 1 The proposed ADMM decoding algorithm

1:Construct $\hat{\mathbf{H}}_{j}$ in (5) based on the parity-check matrix
$\mathbf{H}$. Compute log-likelihood ration $\boldsymbol{\gamma}$ via (9).
Construct $\mathbf{q}$, $\mathbf{A}$ and $\mathbf{b}$ via (16a), (16b), (16c)
respectively. Let $\mu(s_{\rm min}+1)>\alpha$. Compute $\phi_{i}$ and
$\theta_{i}$ in (22).

2:Initialize
$\\{\mathbf{v},\mathbf{e}_{1},\mathbf{e}_{2},\mathbf{y}_{1},\mathbf{y}_{2}\\}$
as the all-zeros vectors. Set $k=0$.

3:Repeat

4: Update $\\{v_{i}^{k+1}|i=1,\cdots,nq+\Gamma_{a}\\}$ in parallel by (23).

5: Update $\\{e_{1,j}^{k{}+1}|j=1,\cdots,4\Gamma_{c}\\}$ in parallel by (25).

6: Update $\\{e_{2,i}^{k{}+1}|i=1,\cdots,nq+\Gamma_{a}\\}$ in parallel by
(27).

7: Update $\frac{\mathbf{y}_{1}^{k+1}}{\mu}$ and
$\frac{\mathbf{y}_{2}^{k+1}}{\mu}$ in parallel by (28) and (29) respectively.

8: $k=k+1$.

9:Until $\|\mathbf{Av}^{k}+\mathbf{e}_{1}^{k}-\mathbf{b}\|^{2}_{2}$ or
$\|\mathbf{v}^{k}-\mathbf{e}_{2}^{k}\|$ is less than some preset $\epsilon$.

##  V Simulation results

((a)) Tanner (1055,424)-$\mathcal{C}_{1}$ in $\mathbb{F}_{4}$ with QPSK
modulation.

((b)) PEG (504,252)-$\mathcal{C}_{2}$ in $\mathbb{F}_{4}$ with QPSK
modulation.

((c)) MacKay (204,102)-$\mathcal{C}_{3}$ in $\mathbb{F}_{8}$ with 8PSK
modulation.

((d)) Tanner (155,64)-$\mathcal{C}_{4}$ in $\mathbb{F}_{16}$ with 16QAM.

Figure 2: Comparisons of FER/SER performance for four LDPC codes from [28] and
[29] in different Galois fields with different modulations.

((a)) Tanner (1055,424) code $\mathcal{C}_{1}$ in $\mathbb{F}_{4}$ with QPSK
modulation.

((b)) PEG (504,252) code $\mathcal{C}_{2}$ in $\mathbb{F}_{4}$ with QPSK
modulation.

((c)) MacKay (204,102) code $\mathcal{C}_{3}$ in $\mathbb{F}_{8}$ with 8PSK
modulation.

((d)) Tanner (155,64) code $\mathcal{C}_{4}$ in $\mathbb{F}_{16}$ with 16QAM
modulation.

Figure 3: Comparisons of average number of iterations for four LDPC codes from
[28] and [29] using different decoders with different modulations.

((a)) Tanner (1055,424)-$\mathcal{C}_{1}$ in $\mathbb{F}_{4}$ with QPSK
modulation.

((b)) PEG (504,252)-$\mathcal{C}_{2}$ in $\mathbb{F}_{4}$ with QPSK
modulation.

((c)) MacKay (204,102)-$\mathcal{C}_{3}$ in $\mathbb{F}_{8}$ with 8PSK
modulation.

((d)) Tanner (155,64)-$\mathcal{C}_{4}$ in $\mathbb{F}_{16}$ with 16QAM
modulation.

Figure 4: Comparisons of average decoding time for four LDPC codes from [28]
and [29] using different decoders with different modulations.

In this section, we provide several numerical results to show the error-
correction performance (frame error rate (FER) and symbol error rate (SER))
and the decoding efficiency of the proposed non-binary ADMM decoder, which are
also compared with several state-of-the-art non-binary LDPC decoders.

The four codes we considered are Tanner (1055,424)-$\mathcal{C}_{1}$ from
[29], irregular PEG (504,252)-$\mathcal{C}_{2}$ from [28], rate-0.5 MacKay
(204,102)-$\mathcal{C}_{3}$ from [28] and Tanner (155,64)-$\mathcal{C}_{4}$
from [29]. The same parity-check matrix are used for $\mathcal{C}_{1}$ and
$\mathcal{C}_{2}$, of which all the entries are binary but are settled as
elements in $\mathbb{F}_{4}$. Meanwhile $\mathcal{C}_{1}$ and
$\mathcal{C}_{2}$ are modulated by quadrature phase shift keying (QPSK). For
$\mathcal{C}_{3}$, the first entry to the sixth entry of each row of the
parity-check matrix are set to 1/4/6/5/2/1$\in\mathbb{F}_{8}$, as the same
setting in [21]. The parity-check matrix of $\mathcal{C}_{4}$ are also binary
but all the entries are settled to the elements in $\mathbb{F}_{16}$. 8 phase-
shift keying (8PSK) and sixteen quadrature amplitude modulation (16QAM) are
used to modulate $\mathcal{C}_{3}$ and $\mathcal{C}_{4}$ respectively. The
modulated symbols are transmitted over additive white Gaussian noise (AWGN)
channel. We compare our proposed ADMM decoder to state-of-the-art decoders,
i.e., proximal-ADMM decoder [27], logarithm-domain fast-Fourier-transform-
based Q-ary sum-product algorithm (Log-FFT-QSPA) [5], non-binary non-penalized
decoder and non-binary penalized decoder in [26]. We set the parameters of the
Algorithm 1 as follows: parameter $\alpha$ are set to 0.9 for all four codes,
parameter $\mu$ are set to $1.1,0.9,0.8,0.7$ for all codes respectively. The
randomly generated codewords are used as input. When
$\|\mathbf{Av}^{k}+\mathbf{e}_{1}^{k}-\mathbf{b}\|^{2}_{2}\leq 10^{-5}$ or
$\|\mathbf{v}^{k}-\mathbf{e}_{2}^{k}\|^{2}_{2}$ is satisfied or the maximum
iteration number 500 is reached, we stop the ADMM iteration. The simulation
environment is MATLAB 2019a/Windows 10 on a computer with 3GHz Intel i5-9400
CPU and 16GB RAM.

Figure 2 demonstrates the FER/SER performance of codes
$\mathcal{C}_{1}$-$\mathcal{C}_{4}$ under different decoders. All the data
points are generated based on at least 200 error frames except for the last
two points in each curve, which are generated based on 50 error frames due to
the limited computational resources. From Figure 2(a) to 2(d), we can observe
that the proposed decoder has a better performance than the proximal-ADMM
decoder in [27] and the penalized decoder in [26], and are much better than
the non-penalized decoder in [26]. Especially for the long non-binary LDPC
codes in Figure 2(a), the proposed decoder outperforms the decoder in [27] and
[26] about 0.1dB. Moreover, the proposed decoder shows a better error-
correction performance than the Log-FFT-QSPA decoder [5] in Figure 2(a), 2(b).
In Figure 2(c) and 2(d), the proposed decoder has a similar performance to the
Log-FFT-QSPA decoder in a low SNR region, but performs better in a high SNR
region. In summary, our proposed ADMM decoder exhibits a superior error-
correction performance than state-of-the-art decoders.

TABLE II: Comparison of the number of constraints and variables in different decoding Algorithm. Codeword | CW embedding in [27] | the proposed decoder
---|---|---
constraints | variables | constraints | variables
$\mathcal{C}_{1}$ | 25109 | 9284 | 15192 | 4642
$\mathcal{C}_{2}$ | 19387 | 6092 | 12124 | 3572
$\mathcal{C}_{3}$ | 11934 | 4080 | 8160 | 2346
$\mathcal{C}_{4}$ | 17081 | 5456 | 4464 | 1364

Figure 3 and Figure 4 shows the averaged number of iteration and the averaged
decoding time of four codes for the proposed ADMM decoder, the proximal-ADMM
decoder [27], the non-binary (non)penalized decoder [26] and the logarithm-
domain fast-Fourier-transform-based Q-ary sum-product algorithm (Log-FFT-QSPA)
[5] respectively. All the data points in Figure 3 and Figure 4 are averaged
based on generating one million LDPC frames. In Figure 3, we can observe that
the proposed ADMM decoder takes more averaged number of iteration than the
non-binary (non)penalized decoder in [26] in a high SNR region. This could be
that more auxiliary variables are required in the proposed decoding model
compared to the model in [26]. Moreover, the proposed ADMM decoder takes less
averaged number of iteration and averaged decoding time than the proximal-ADMM
decoder in [27]. This is mainly because that the proposed decoding model
solves much less constraints and variables than the proximal-ADMM decoder
[27]. In Table II, we compare the number of constraints and variables (the
number of rows and columns of $\mathbf{A}$ in the decoding model) in the
proposed ADMM decoding model and the decoding model in [27]. Obviously, our
proposed decoding model solves less constraints and variables, hence our ADMM
decoding algorithm is more efficient.

##  VI Conclusion

In this paper, an efficient decoder is proposed for non-binary LDPC codes in
$\mathbb{F}_{2^{q}}$ through ADMM method based on the proposed bit embedding
technique. We show that the decoding complexity grows linearly as the non-
binary LDPC codes length and the considered length $q$, which outperforms
state-of-the-art ADMM decoders. Moreover the performance of the proposed
decoding algorithm satisfies the codeword-independent property. Numerical
results reveal the outstanding performance in error-correction and complexity
compared with other ADMM decoders.

##  Appendix A Proof of lemma 1

###### Proof.

Replace $c_{i}$, $i=1,\cdots,n$ by its bits representation, then we have

$\displaystyle h_{j,i}c_{i}$
$\displaystyle=h_{j,i}\begin{bmatrix}2^{q-1}&\cdots&2&1\end{bmatrix}\begin{bmatrix}x_{i,1}\\\
\vdots\\\ x_{i,q-1}\\\ x_{i,q}\end{bmatrix}$ (30)
$\displaystyle=\begin{bmatrix}2^{q-1}h_{j,i}&\cdots&2h_{j,i}&h_{j,i}\end{bmatrix}\begin{bmatrix}x_{i,1}\\\
\vdots\\\ x_{i,q-1}\\\ x_{i,q}\end{bmatrix}$
$\displaystyle=\hat{\mathbf{h}}^{(j,i)}\mathbf{x}_{i},$

where
$\hat{\mathbf{h}}^{(j,i)}=\begin{bmatrix}\hat{h}^{(j,i)}_{1}&\cdots&\hat{h}^{(j,i)}_{q-1}&\hat{h}^{(j,i)}_{q}\end{bmatrix}=\begin{bmatrix}2^{q-1}h_{j,i}&\cdots&2h_{j,i}&h_{j,i}\end{bmatrix}$.

Use the bits representation to denote all the entries in
$\hat{\mathbf{h}}^{(j,i)}$, then we get

$\displaystyle\hat{\mathbf{h}}^{(j,i)}$
$\displaystyle=\begin{bmatrix}2^{q-1}&\cdots&2&1\end{bmatrix}\begin{bmatrix}\hat{h}^{(j,i)}_{1,1}&\cdots&\hat{h}^{(j,i)}_{1,q-1}&\hat{h}^{(j,i)}_{1,q}\\\
\vdots&\vdots&\vdots&\vdots\\\
\hat{h}^{(j,i)}_{q-1,1}&\cdots&\hat{h}^{(j,i)}_{q-1,q-1}&\hat{h}^{(j,i)}_{q-1,q}\\\
\hat{h}^{(j,i)}_{q,1}&\cdots&\hat{h}^{(j,i)}_{q,q-1}&\hat{h}^{(j,i)}_{q,q}\end{bmatrix}$
(31)
$\displaystyle=\begin{bmatrix}2^{q-1}&\cdots&2&1\end{bmatrix}\hat{\mathbf{{H}}}_{j,i}.$

Combine (30) with (31), we can obtain

$h_{j,i}c_{i}=\begin{bmatrix}2^{q-1}&\cdots&2&1\end{bmatrix}\hat{\mathbf{{H}}}_{j,i}\mathbf{x}_{i}.$
(32)

Follow the bit embedding rule in (3), we can conclude that
$\hat{\mathbf{{H}}}_{j,i}\mathbf{x}_{i}$ is an equivalent binary codeword to
$h_{j,i}c_{i}$.

∎

##  Appendix B Proof of theorem 1

1) _Sketch of the Proof_ : We need to prove
$\rm{Pr}[\rm{error}|\mathbf{0}]=Pr[\rm{error}|\mathbf{v}]$, where $\mathbf{v}$
is any non-zero codeword. Let

$\mathcal{B}$($\mathbf{v}$):=$\\{\mathbf{r}|$ Decoder fails to recover
$\mathbf{v}$ if $\mathbf{r}$ is received$\\}$.
Then
$\rm{Pr}[\rm{error}|\mathbf{v}]=\sum_{\mathbf{r}\in\mathcal{B}(\mathbf{v})}\rm{Pr}[\mathbf{r}|\mathbf{v}]$.

We use the symmetry condition for fields in [26] (Definition 48, [26]). Let
$\mathbf{r}$ and $\mathbf{r}^{0}$ are received vectors when codeword
$\mathbf{v}$ and the all-zeros codeword $\mathbf{0}$ are transmitted over the
symmetrical channel. This definition indicates a one-to-one mapping from the
received vector $\mathbf{r}$ to a vector $\mathbf{r}^{0}$ such that the
following two statements hold:

  1. (a)

Pr$[\mathbf{r}|\mathbf{v}]$=Pr$[\mathbf{r}^{0}|\mathbf{0}]$,

  2. (b)

$\mathbf{r}\in\mathcal{B}(\mathbf{v})$ if and only if
$\mathbf{r}^{0}\in\mathcal{B}(\mathbf{0})$.

Statement (a) is directly proved according to the definition of the symmetry
condition. In the following, we show that statement (b) also holds once we
proved that

$\displaystyle\rm{Pr}[error|\mathbf{v}]$
$\displaystyle=\sum_{\mathbf{r}\in\mathcal{B}(\mathbf{v})}\rm{Pr}[\mathbf{r}|\mathbf{v}]$
$\displaystyle=\sum_{\mathbf{r}^{0}\in\mathcal{B}(\mathbf{0})}\rm{Pr}[\mathbf{r}^{0}|\mathbf{0}]=\rm{Pr}[error|\mathbf{0}].$

2) _Proof of statement (b):_ We define the concept of relative vector for the
bit embedding.

######  Definition 2.

Define $\mathrm{R}_{\mathbf{v}}(\boldsymbol{\beta})$ is the relative vector of
$\boldsymbol{\beta}$ with respect to the binary vector $\mathbf{v}$ if it
satisfies

$\left(\mathrm{R}_{\mathbf{v}}(\boldsymbol{\beta})\right)_{i}=\left\\{\begin{array}[]{ll}\beta_{i},&v_{i}=0,\\\
1-\beta_{i},&v_{i}=1.\end{array}\right.$ (33)

Vector $\mathbf{v}=[\mathbf{x};\mathbf{u}]$, where $\mathbf{x}$ is the bit
embedding result of the transmitted non-binary LDPC codeword $\mathbf{c}$ and
$\mathbf{u}$ is the corresponding binary auxiliary variables.

In (19), an auxiliary variable $\mathbf{e}_{1}$ is introduced to change the
inequality constraint (18b) to the equality constraint (19b). Moreover,
observing (12), four auxiliary variables are required for one three-variables
inequalities set. Hence we define the following mapping operators
$\mathcal{M}_{\mathbf{v}_{\tau}}(\cdot)$ and $\mathcal{T}_{\mathbf{v}}(\cdot)$
for the introduced auxiliary variables. These two operators can also be
applied to the Lagrangian multiplier $\mathbf{y}_{1}$. Moreover, we also
define a mapping operator $\mathcal{K}_{\mathbf{v}}(\mathbf{y}_{2})$ for
$\mathbf{y}_{2}$.

######  Definition 3.

Let
$\mathbf{e}_{1,\tau}=[e_{1,{\tau}_{1}},e_{1,{\tau}_{2}},e_{1,{\tau}_{3}},e_{1,{\tau}_{4}}]$
be the auxiliary variables which change the inequality constraints
corresponding to the $\tau$th three-variables parity-check equation to the
equality constraints. Denote
$\mathbf{v}_{\tau}=\mathbf{Q}_{\tau}\mathbf{v},\tau=1,\cdots,\Gamma_{c}$, as
the corresponding binary variables. Then we define the following mapping
operator for $\mathbf{e}_{1,\tau}$

$\mathcal{M}_{\mathbf{v}_{\tau}}\left(\mathbf{e}_{1,\tau}\right)\\!=\\!\left\\{\begin{array}[]{llll}{\left[\begin{array}[]{llll}e_{1,\tau_{2}}\\!\\!\\!\\!\\!&e_{1,\tau_{1}}\\!\\!\\!\\!\\!&e_{1,\tau_{4}}\\!\\!\\!\\!\\!&e_{1,\tau_{3}}\end{array}\right]^{T},}&\\!\\!\\!\\!\mathbf{v}_{\tau}\\!=\\!\left[\\!\\!\begin{array}[]{lll}1\\!\\!\\!&\\!\\!\\!1&\\!\\!\\!0\end{array}\\!\\!\right]^{T},\\\
{\left[\begin{array}[]{llll}e_{1,\tau_{3}}\\!\\!\\!\\!\\!&e_{1,\tau_{4}}\\!\\!\\!\\!\\!&e_{1,\tau_{1}}\\!\\!\\!\\!\\!&e_{1,\tau_{2}}\end{array}\right]^{T},}&\\!\\!\\!\\!\mathbf{v}_{\tau}\\!=\\!\left[\\!\\!\begin{array}[]{lll}1\\!\\!\\!&\\!\\!\\!0&\\!\\!\\!1\end{array}\\!\\!\right]^{T},\\\
{\left[\begin{array}[]{llll}e_{1,\tau_{4}}\\!\\!\\!\\!\\!&e_{1,\tau_{3}}\\!\\!\\!\\!\\!&e_{1,\tau_{2}}\\!\\!\\!\\!\\!&e_{1,\tau_{1}}\end{array}\right]^{T},}&\\!\\!\\!\\!\mathbf{v}_{\tau}\\!=\\!\left[\\!\\!\begin{array}[]{lll}0\\!\\!\\!&\\!\\!\\!1&\\!\\!\\!1\end{array}\\!\\!\right]^{T},\\\
\mathbf{e}_{1,\tau},&\\!\\!\\!\\!\mathbf{v}_{\tau}\\!=\\!\left[\\!\\!\begin{array}[]{lll}0\\!\\!\\!&\\!\\!\\!0&\\!\\!\\!0\end{array}\\!\\!\right]^{T}.\end{array}\right.$
(34)

Furthermore, we define

$\mathcal{T}_{\mathbf{v}}(\mathbf{e}_{1})\\!=\\!\left[\mathcal{M}_{\mathbf{v}_{1}}\left(\mathbf{e}_{1,1}\right);\cdots;\mathcal{M}_{\mathbf{v}_{\tau}}\left(\mathbf{e}_{1,\tau}\right);\cdots;\mathcal{M}_{\mathbf{v}_{\Gamma_{c}}}\left(\mathbf{e}_{1,\Gamma_{c}}\right)\right]^{T}.$

Moreover, we define the following mapping operator for $\mathbf{y}_{2}$

$\left(\mathcal{K}_{\mathbf{v}}(\mathbf{y}_{2})\right)_{i}=\left\\{\begin{array}[]{ll}y_{2,i},&v_{i}=0,\\\
-y_{2,i},&v_{i}=1.\end{array}\right.$ (35)

######  Lemma 2.

In Algorithm 1, let
$\\{\mathbf{v}^{k},\mathbf{e}_{1}^{k},\mathbf{e}_{2}^{k},\mathbf{y}_{1}^{k},\mathbf{y}_{2}^{k}\\}$
be the vectors in the $k$th iteration when decoding $\mathbf{r}$. Let
$\\{\mathbf{v}^{0,k},\mathbf{e}_{1}^{0,k},\mathbf{e}_{2}^{0,k},\mathbf{y}_{1}^{0,k},\mathbf{y}_{2}^{0,k}\\}$
be the vectors after the $k$th iteration when decoding $\mathbf{r}^{0}$. If
$\mathbf{v}^{0,k}=\rm{R}_{\mathbf{v}}(\mathbf{v}^{k})$,
$\mathbf{e}_{1}^{0,k}=\mathcal{T}_{\mathbf{v}}(\mathbf{e}_{1}^{k})$,
$\mathbf{e}_{2}^{0,k}=\rm{R}_{\mathbf{v}}(\mathbf{e}_{2}^{k})$,
$\mathbf{y}_{1}^{0,k}=\mathcal{T}_{\mathbf{v}}(\mathbf{y}_{1}^{k})$,
$\mathbf{y}_{2}^{0,k}=\mathcal{K}_{\mathbf{v}}(\mathbf{y}_{2}^{k})$, then
$\mathbf{v}^{0,k+1}=\rm{R}_{\mathbf{v}}(\mathbf{v}^{k+1})$,
$\mathbf{e}_{1}^{0,k+1}=\mathcal{T}_{\mathbf{v}}(\mathbf{e}_{1}^{k+1})$,
$\mathbf{e}_{2}^{0,k+1}=\rm{R}_{\mathbf{v}}(\mathbf{e}_{2}^{k+1})$,
$\mathbf{y}_{1}^{0,k+1}=\mathcal{T}_{\mathbf{v}}(\mathbf{y}_{1}^{k+1})$,
$\mathbf{y}_{2}^{0,k+1}=\mathcal{K}_{\mathbf{v}}(\mathbf{y}_{2}^{k+1})$.

###### Proof.

See Appendix C. ∎

######  Lemma 3.

Let $\hat{\mathbf{v}}$ and $\hat{\mathbf{v}}^{0}$ denote the output of the
Algorithm 1 when $\mathbf{r}$ and $\mathbf{r}^{0}$ are received respectively.
Then there exists
$\hat{\mathbf{v}}^{0}=\rm{R}_{\mathbf{v}}(\hat{\mathbf{v}})$.

###### Proof.

Let
$\\{\mathbf{e}_{1}^{0,0},\mathbf{e}_{2}^{0,0},\mathbf{y}_{1}^{0,0},\mathbf{y}_{2}^{0,0}\\}$
and
$\\{\mathbf{e}_{1}^{0},\mathbf{e}_{2}^{0},\mathbf{y}_{1}^{0},\mathbf{y}_{2}^{0}\\}$
be the initial values when decode the all-zeros codeword and general codeword
$\mathbf{c}$ using Algorithm 1. We setting them to satisfy
$\mathbf{e}_{1}^{0,0}=\mathcal{T}_{\mathbf{v}}(\mathbf{e}_{1}^{0})$,
$\mathbf{e}_{2}^{0,0}=\rm{R}_{\mathbf{v}}(\mathbf{e}_{2}^{0})$,
$\mathbf{y}_{1}^{0,0}=\mathcal{T}_{\mathbf{v}}(\mathbf{y}_{1}^{0})$,
$\mathbf{y}_{2}^{0,0}=\mathcal{K}_{\mathbf{v}}(\mathbf{y}_{2}^{0})$. Then in
the first iteration, by Lemma 2, we have
$\mathbf{v}^{0,1}=\rm{R}_{\mathbf{v}}(\mathbf{v}^{1})$,
$\mathbf{{e}}_{1}^{0,1}=\mathcal{T}_{\mathbf{v}}(\mathbf{e}_{1}^{1})$,
$\mathbf{e}_{2}^{0,1}=\rm{R}_{\mathbf{v}}(\mathbf{e}_{2}^{1})$,
$\mathbf{y}_{1}^{0,1}=\mathcal{T}_{\mathbf{v}}(\mathbf{y}_{1}^{1})$,
$\mathbf{y}_{2}^{0,1}=\mathcal{K}_{\mathbf{v}}(\mathbf{y}_{2}^{1})$.
Continuing with the iteration, we can get
$\mathbf{v}^{0,k}=\rm{R}_{\mathbf{v}}(\mathbf{v}^{k})$,
$\mathbf{{e}}_{1}^{0,k}=\mathcal{T}_{\mathbf{v}}(\mathbf{e}_{1}^{k})$,
$\mathbf{e}_{2}^{0,k}=\rm{R}_{\mathbf{v}}(\mathbf{e}_{2}^{k})$,
$\mathbf{y}_{1}^{0,k}=\mathcal{T}_{\mathbf{v}}(\mathbf{y}_{1}^{k})$,
$\mathbf{y}_{2}^{0,k}=\mathcal{K}_{\mathbf{v}}(\mathbf{y}_{2}^{k})$.

For the termination condition in Algorithm 1, we have the following
derivations

$\displaystyle\|\mathbf{Av}^{k}+\mathbf{e}_{1}^{k}-\mathbf{b}\|^{2}_{2}$
$\displaystyle=\sum^{\Gamma_{c}}_{\tau=1}\|\mathbf{Tv}^{k}_{\tau}+\mathbf{e}_{1,\tau}^{k}-\mathbf{w}\|^{2}_{2}$
(36)
$\displaystyle\overset{a}{=}\sum^{\Gamma_{c}}_{\tau=1}\|\mathbf{Tv}^{0,k}_{\tau}+\mathbf{e}_{1,\tau}^{0,k}-\mathbf{w}\|^{2}_{2}$
$\displaystyle=\|\mathbf{Av}^{0,k}+\mathbf{e}_{1}^{0,k}-\mathbf{b}\|^{2}_{2},$
$\|\mathbf{v}^{k}-\mathbf{e}_{2}^{k}\|^{2}_{2}\overset{b}{=}\|\mathbf{v}^{0,k}-\mathbf{e}_{2}^{0,k}\|^{2}_{2}$
(37)

where the equalities ”a” and ”b” hold since
$\mathbf{v}^{0,k}=\rm{R}_{\mathbf{v}}(\mathbf{v}^{k})$,
$\mathbf{{e}}_{1}^{0,k}=\mathcal{T}_{\mathbf{v}}(\mathbf{e}_{1}^{k})$,
$\mathbf{e}_{2}^{0,k}=\mathcal{K}_{\mathbf{v}}(\mathbf{e}_{2}^{k})$, and we
can find that the vector
$\mathbf{Tv}^{k}_{\tau}+\mathbf{e}_{1,\tau}^{k}-\mathbf{w}$ can be obtained
from the permutation of the vector
$\mathbf{Tv}^{0,k}_{\tau}+\mathbf{e}_{1,\tau}^{0,k}-\mathbf{w}$. This
indicates that both of the decoding procedures in Algorithm 1 for $\mathbf{r}$
and $\mathbf{r}^{0}$ should always be terminated at the same time. Hence we
conclude $\mathbf{v}^{0}=\rm{R}_{\mathbf{v}}(\mathbf{v})$. ∎

Due to Lemma 3, if the decoder recovers a codeword $\mathbf{c}$ from
$\mathbf{r}$, it indicates that the decoded vector $\hat{\mathbf{v}}$ is the
embedding of $\mathbf{c}$ based on Definition 1. Therefore by Definition 2,
$\rm{R}_{\mathbf{v}}(\hat{\mathbf{v}})$ is the embedding of $\mathbf{0}$ from
$\mathbf{r}^{0}$. On the flip side, if the decoder fails to recover codeword
$\mathbf{c}$ from $\mathbf{r}$, then $\rm{R}_{\mathbf{v}}(\hat{\mathbf{v}})$
is not a integral vector. This indicates that the decoder cannot recover
$\mathbf{0}$ from $\mathbf{r}^{0}$. Combine the two augments, we can conclude
that the decoder can recover $\mathbf{c}$ from $\mathbf{r}$ if and only if it
can recover $\mathbf{0}$ from $\mathbf{r}^{0}$, which completes the proof.

##  Appendix C Proof of lemma 2

To prove Lemma 2, we provide the following corollary based on Definition 3.

######  Corollary 1.

The $\tau$th three-variables parity-check equation $\mathbf{e}_{1,\tau}$ and
its mapping operator $\mathcal{M}_{\mathbf{v}_{\tau}}(\mathbf{e}_{1,\tau})$
have the following property

$\mathbf{t}_{\ell}^{T}\mathcal{M}_{\mathbf{v}_{\tau}}\left(\mathbf{e}_{1,\tau}\right)=\left\\{\begin{array}[]{cl}\mathbf{t}_{\ell}^{T}\mathbf{e}_{1,\tau},&v_{\tau_{\ell}}=0\\\
-\mathbf{t}_{\ell}^{T}\mathbf{e}_{1,\tau},&v_{\tau_{\ell}}=1\end{array}\right.{}$
(38)

where $\mathbf{t}_{\ell},\ell=1,2,3$, denotes the $\ell$th column of matrix
$\mathbf{T}$.

###### Proof.

Based on the Definition 3, there are four cases for the relationship between
$\mathbf{e}_{1,\tau}$ and the mapping operator
$\mathcal{M}_{\mathbf{v}_{\tau}}(\mathbf{e}_{1,\tau})$. When
$\mathbf{v}_{\tau}=[1,1,0]^{T}$,
$\mathcal{M}_{\mathbf{v}_{\tau}}(\mathbf{e}_{1,\tau})=[e_{1,\tau_{2}},e_{1,\tau_{1}},e_{1,\tau_{4}},e_{1,\tau_{3}}]^{T}$.
Hence, when $\mathbf{v}_{\tau_{1}}=1$, $\mathbf{v}_{\tau_{2}}=1$ and
$\mathbf{v}_{\tau_{3}}=0$ respectively, we can obtain the following equation

$\mathbf{t}^{T}_{1}{M}_{\mathbf{v}_{\tau}}(\mathbf{e}_{1,\tau})=-e_{1,\tau_{1}}+e_{1,\tau_{2}}+e_{1,\tau_{3}}-e_{1\tau_{4}}=-\mathbf{t}^{T}_{1}\mathbf{e}_{1,\tau},$
$\mathbf{t}^{T}_{2}{M}_{\mathbf{v}_{\tau}}(\mathbf{e}_{1,\tau})=e_{1,\tau_{1}}-e_{1,\tau_{2}}+e_{1,\tau_{3}}-e_{1\tau_{4}}=-\mathbf{t}^{T}_{2}\mathbf{e}_{1,\tau},$
$\mathbf{t}^{T}_{3}{M}_{\mathbf{v}_{\tau}}(\mathbf{e}_{1,\tau})=-e_{1,\tau_{1}}-e_{1,\tau_{2}}+e_{1,\tau_{3}}+e_{1\tau_{4}}=-\mathbf{t}^{T}_{3}\mathbf{e}_{1,\tau},$

which can be further written as

$\mathbf{t}_{\ell}^{T}\mathcal{M}_{\mathbf{v}_{\tau}}\left(\mathbf{e}_{1,\tau}\right)=\left\\{\begin{aligned}
\mathbf{t}_{\ell}^{T}\mathbf{e}_{1,\tau},&\ \ v_{\tau_{\ell}}=0,\\\
-\mathbf{t}_{\ell}^{T}\mathbf{e}_{1,\tau},&\ \
v_{\tau_{\ell}}=1,\end{aligned}\right.$ (39)

where $\ell=1,2,3.$

Therefore, through similar deduction, it can be proved that (38) also holds
when $\mathbf{v}_{\tau}=[1,0,1]^{T},[0,1,1]^{T}$ and $[0,0,0]^{T}$. This
completes the proof. ∎

Now we are ready to prove Lemma 2.

###### Proof.

According to (23), we have

$\displaystyle v_{i}^{k+1}=\frac{1}{s_{i}-\frac{\alpha}{\mu}+1}$
$\displaystyle\left(\mathbf{a}_{i}^{T}(\mathbf{b}-\mathbf{e}_{1}^{k}-\frac{\mathbf{y}_{1}^{k}}{\mu})\right.$
(40)
$\displaystyle\left.+e_{2,i}^{k}-\frac{y_{2,i}^{k}}{\mu}-\frac{2q_{i}+\alpha}{2\mu}\right).$

We first consider the case that $v_{i}=1$ is transmitted. Then we have

$\displaystyle 1-v_{i}^{k+1}\overset{a}{=}$
$\displaystyle\frac{1}{s_{i}-\frac{\alpha}{\mu}+1}\left(\mathbf{a}_{i}^{T}(\mathbf{b}+\mathbf{e}_{1}^{k}+\frac{\mathbf{y}_{1}^{k}}{\mu})\right.$
(41)
$\displaystyle\left.+1-e_{2,i}^{k}+\frac{y_{2,i}^{k}}{\mu}+\frac{2q_{i}-\alpha}{2\mu}\right)$
$\displaystyle\overset{b}{=}$
$\displaystyle\frac{1}{s_{i}-\frac{\alpha}{\mu}+1}\left(\mathbf{a}_{i}^{T}(\mathbf{b}-\mathbf{e}_{1}^{0,k}-\frac{\mathbf{y}_{1}^{0,k}}{\mu})\right.$
$\displaystyle\left.+e_{2,i}^{0,k}-\frac{y_{2,i}^{0,k}}{\mu}-\frac{2q_{i}^{0}+\alpha}{2\mu}\right),$

where $q_{i}^{0}\in\mathbf{q}^{0}=[\boldsymbol{\gamma}^{0};\mathbf{0}]$ and
$\boldsymbol{\gamma}^{0}$ is the LLR vector when the all-zeros codeword is
transmitted.

In (41), the equality ”a” holds since $\mathbf{a}_{i}^{T}\mathbf{b}=2d_{i}$
and $s_{i}=4d_{i}$, where $d_{i}$ denotes the nonzero numbers in the $i$th
column of the parity-check matrix
$[\hat{\mathbf{H}}_{1};\cdots;\hat{\mathbf{H}}_{m}]$. The equality ”b” holds
if $q_{i}^{0}=-q_{i}$,
$\mathbf{a}_{i}^{T}\mathbf{e}_{1}^{k}=-\mathbf{a}_{i}^{T}\mathbf{e}_{1}^{0,k}$,
$\mathbf{a}_{i}^{T}\mathbf{y}_{1}^{k}=-\mathbf{a}_{i}^{T}\mathbf{y}_{1}^{0,k}$.
It is obvious that $q_{i}^{0}=-q_{i}$ when $v_{i}=1$ since the channel is
assumed to be symmetrical. And
$e_{2,i}^{0,k}=\rm{R}_{\mathbf{v}}(e_{2,i}^{k})=1-e_{2,i}^{k}$,
$y_{2,i}^{0,k}=\mathcal{K}_{\mathbf{v}}(y_{2,i}^{k})=-y_{2,i}^{k}$ holds when
$v_{i}=1$. Now we need to verify
$\mathbf{a}_{i}^{T}\mathbf{e}_{1}^{k}=-\mathbf{a}_{i}^{T}\mathbf{e}_{1}^{0,k}$
and
$\mathbf{a}_{i}^{T}\mathbf{y}_{1}^{k}=-\mathbf{a}_{i}^{T}\mathbf{y}_{1}^{0,k}$.
Observing (16b), we can find that there are $\lfloor\mathbf{t}_{\ell}\rfloor$
sub-vectors same as $\mathbf{t}_{\ell}$ in $\mathbf{a}_{i}$, where
$\lfloor\mathbf{t}_{\ell}\rfloor$ is the number of vector same as
$\mathbf{t}_{\ell}$. Moreover, we denote $\mathbf{e}_{1,\kappa_{\ell}}$ as the
length-4 auxiliary variables corresponding to the $\kappa_{\ell}$th sub-
vectors which is the same as $\mathbf{t}_{\ell}$,
$\kappa_{\ell}=1,\cdots,\lfloor\mathbf{t}_{\ell}\rfloor$. Based on the above
augment, when $v_{i}=1$, we have

$\displaystyle\mathbf{a}_{i}^{T}\mathbf{e}_{1}^{k}$
$\displaystyle=\sum_{\kappa_{1}=1}^{\left\lfloor\mathbf{t}_{1}\right\rfloor}\mathbf{t}_{1}^{T}\mathbf{e}_{1,\kappa_{1}}^{k}+\sum_{\kappa_{2}=1}^{\left\lfloor\mathbf{t}_{2}\right\rfloor}\mathbf{t}_{2}^{T}\mathbf{e}_{1,\kappa_{2}}^{k}+\sum_{\kappa_{3}=1}^{\left\lfloor\mathbf{t}_{3}\right\rfloor}\mathbf{t}_{3}^{T}\mathbf{e}_{1,\kappa_{3}}^{k}$
(42)
$\displaystyle=-\sum_{\kappa_{1}=1}^{\left\lfloor\mathbf{t}_{1}\right\rfloor}\mathbf{t}_{1}^{T}\mathbf{e}_{1,\kappa_{1}}^{0,k}-\sum_{\kappa_{2}=1}^{\left\lfloor\mathbf{t}_{2}\right\rfloor}\mathbf{t}_{2}^{T}\mathbf{e}_{1,\kappa_{2}}^{0,k}-\sum_{\kappa_{3}=1}^{\left\lfloor\mathbf{t}_{3}\right\rfloor}\mathbf{t}_{3}^{T}\mathbf{e}_{1,\kappa_{3}}^{0,k}$
$\displaystyle=-\mathbf{a}_{i}^{T}\mathbf{e}_{1}^{0,k}.$

In (42), the second equality hods since
$\mathbf{t}_{\ell}^{T}\mathbf{e}_{1,\kappa_{\ell}}^{k}=-\mathbf{t}_{\ell}^{T}\mathbf{e}_{1,\kappa_{\ell}}^{0,k},\ell=1,2,3$,
when $v_{i}=1$ based on Corollary 1. With similar derivation of 1, we can also
obtain that
$\mathbf{a}_{i}^{T}\mathbf{y}_{1}^{k}=-\mathbf{a}_{i}^{T}\mathbf{y}_{1}^{0,k}$
when $v_{i}=1$. Hence, equation (41) holds, which means that when $v_{i}=1$,
we have

$v_{i}^{0,k+1}=1-v_{i}^{k+1}$ (43)

For the other case when $v_{i}=0$ is transmitted over the channel, we have

$\displaystyle v_{i}^{k+1}=\frac{1}{s_{i}-\frac{\alpha}{\mu}+1}$
$\displaystyle\left(\mathbf{a}_{i}^{T}(\mathbf{b}-\mathbf{e}_{1}^{0,k}-\frac{\mathbf{y}_{1}^{0,k}}{\mu})\right.$
(44)
$\displaystyle\left.+e_{2,i}^{0,k}-\frac{y_{2,i}^{0,k}}{\mu}-\frac{2q_{i}^{0}+\alpha}{2\mu}\right),$

where the equality holds since $q^{0}_{i}=q_{i}$ when $v_{i}=0$ under the
symmetrical channel. And
$e_{2,i}^{0,k}=\rm{R}_{\mathbf{v}}(e_{2,i}^{k})=e_{2,i}^{k}$,
$y_{2,i}^{0,k}=\mathcal{K}_{\mathbf{v}}(y_{2,i}^{k})=y_{2,i}^{k}$ holds when
$v_{i}=0$. Furthermore, base on the Corollary 1, when $v_{i}=0$, we have

$\displaystyle\mathbf{a}_{i}^{T}\mathbf{e}_{1}^{k}$
$\displaystyle=\sum_{\kappa_{1}=1}^{\left\lfloor\mathbf{t}_{1}\right\rfloor}\mathbf{t}_{1}^{T}\mathbf{e}_{1,\kappa_{1}}^{k}+\sum_{\kappa_{2}=1}^{\left\lfloor\mathbf{t}_{2}\right\rfloor}\mathbf{t}_{2}^{T}\mathbf{e}_{1,\kappa_{2}}^{k}+\sum_{\kappa_{3}=1}^{\left\lfloor\mathbf{t}_{3}\right\rfloor}\mathbf{t}_{3}^{T}\mathbf{e}_{1,\kappa_{3}}^{k}$
(45)
$\displaystyle=\sum_{\kappa_{1}=1}^{\left\lfloor\mathbf{t}_{1}\right\rfloor}\mathbf{t}_{1}^{T}\mathbf{e}_{1,\kappa_{1}}^{0,k}+\sum_{\kappa_{2}=1}^{\left\lfloor\mathbf{t}_{2}\right\rfloor}\mathbf{t}_{2}^{T}\mathbf{e}_{1,\kappa_{2}}^{0,k}+\sum_{\kappa_{3}=1}^{\left\lfloor\mathbf{t}_{3}\right\rfloor}\mathbf{t}_{3}^{T}\mathbf{e}_{1,\kappa_{3}}^{0,k}$
$\displaystyle=\mathbf{a}_{i}^{T}\mathbf{e}_{1}^{0,k}.$

Through a similar derivation of (45), we can also get
$\mathbf{a}_{i}^{T}\mathbf{y}_{1}^{k}=\mathbf{a}_{i}^{T}\mathbf{y}_{1}^{0,k}$
when $v_{i}=0$. Hence, equation (44) holds, which means that when $v_{i}=0$,

$v_{i}^{0,k+1}=v_{i}^{k+1}$ (46)

Combine (43) and (46), we get

$\mathbf{v}^{0,k+1}=\rm{R}_{\mathbf{v}}(\mathbf{v}^{k+1})$ (47)

Next, we verify that
$\mathbf{e}_{1}^{0,k+1}=\mathcal{T}_{\mathbf{v}}(\mathbf{e}_{1}^{k+1})$.
Firstly, we consider the relationship between $\mathbf{e}_{1,\tau}^{k+1}$ and
$\mathbf{e}_{1,\tau}^{0,k+1}$. Since
$\mathbf{y}_{1,\tau}^{0,k}=\mathcal{M}_{\mathbf{v}_{\tau}}(\mathbf{y}_{1,\tau}^{k})$,
there exists
$\mathbf{y}_{1,\tau}^{0,k}=[{y}_{1,\tau_{2}}^{k},{y}_{1,\tau_{1}}^{k},{y}_{1,\tau_{4}}^{k},{y}_{1,\tau_{3}}^{k}]^{T}$
when $\mathbf{v}_{\tau}=[1,1,0]^{T}$. Hence, when
$\mathbf{v}_{\tau}=[1,1,0]^{T}$, we have

$\displaystyle\mathbf{e}_{1,\tau}^{0,{k+1}}$
$\displaystyle=\prod_{[0,+\infty)}\left(\mathbf{w}-\mathbf{T}\mathbf{v}_{\tau}^{0,{k+1}}-\frac{\mathbf{y}_{1,\tau}^{0,k}}{\mu}\right)$
(48)
$\displaystyle=\prod_{[0,+\infty)}\left(\mathbf{w}-\mathbf{T}\left[\begin{array}[]{c}1-v_{\tau_{1}}^{k+1}\\\
1-v_{\tau_{2}}^{k+1}\\\
v_{\tau_{3}}^{k+1}\end{array}\right]-\frac{1}{\mu}\left[\begin{array}[]{c}y_{1,\tau_{2}}^{k}\\\
y_{1,\tau_{1}}^{k}\\\ y_{1,\tau_{4}}^{k}\\\
y_{1,\tau_{3}}^{k}\end{array}\right]\right)$
$\displaystyle=\prod_{[0,+\infty)}\left[\begin{array}[]{c}\quad
v_{\tau_{1}}^{k+1}-v_{\tau_{2}}^{k+1}+v_{\tau_{3}}^{k+1}-\frac{y_{1,\tau_{2}}^{k}}{\mu}\\\
-v_{\tau_{1}}^{k+1}+v_{\tau_{2}}^{k+1}+v_{\tau_{3}}^{k+1}-\frac{y_{1,\tau_{1}}^{k}}{\mu}\\\
2-\left(v_{\tau_{1}}^{k+1}+v_{\tau_{2}}^{k+1}+v_{\tau_{3}}^{k+1}\right)-\frac{y_{1,\tau_{4}}^{k}}{\mu}\\\
v_{\tau_{1}}^{k+1}+v_{\tau_{2}}^{k+1}-v_{\tau_{3}}^{k+1}-\frac{y_{1,\tau
3}^{k}}{\mu}\end{array}\right]$

Then, $\mathbf{e}_{1,\tau}^{0,k+1}$ can be further derived as

$\displaystyle\mathbf{e}_{1,\tau}^{0,{k+1}}$
$\displaystyle=\prod_{[0,+\infty)}\left[\begin{array}[]{c}w_{2}-\left(-v_{\tau_{1}}^{k+1}+v_{\tau_{2}}^{k+1}-v_{\tau_{3}}^{k+1}\right)-\frac{y_{1,\tau_{2}}^{k}}{\mu}\\\
w_{1}-\left(v_{\tau_{1}}^{k+1}-v_{\tau_{2}}^{k+1}-v_{\tau_{3}}^{k+1}\right)-\frac{y_{1,\tau_{1}}^{k}}{\mu}\\\
w_{4}-\left(v_{\tau_{1}}^{k+1}+v_{\tau_{2}}^{k+1}+v_{\tau_{3}}^{k+1}\right)-\frac{y_{1,\tau_{4}}^{k}}{\mu}\\\
w_{3}-\left(-v_{\tau_{1}}^{k+1}-v_{\tau_{2}}^{k+1}+v_{\tau_{3}}^{k+1}\right)-\frac{y_{1,\tau_{3}}^{k}}{\mu}\end{array}\right]$
(49)
$\displaystyle=\left[e_{1,\tau_{2}}^{k+1},e_{1,\tau_{1}}^{k+1},e_{1,\tau_{4}}^{k+1},e_{1,\tau_{3}}^{k+1}\right],$

i.e.,

$\mathbf{e}_{1,\tau}^{0,k+1}=\mathcal{M}_{\mathbf{v}_{\tau}}(\mathbf{e}_{1,\tau}^{k+1}).$
(50)

With a similar derivation, we can see (50) also holds when
$\mathbf{v}_{\tau}=[1,0,1]^{T},[0,1,1]^{T},[0,0,0]^{T}$. Since
$\mathbf{e}_{1}^{k+1}$ is cascaded by
$\mathbf{e}_{1,\tau}^{k+1},\tau=1,\cdots,\Gamma_{c}$, and
$\mathbf{e}_{1}^{0,k+1}$ is also cascaded by $\mathbf{e}_{1,\tau}^{0,k+1}$ in
the same way, we have

$\mathbf{e}_{1}^{0,k+1}=\mathcal{T}_{\mathbf{v}}(\mathbf{e}_{1}^{k+1}).$ (51)

Next, we verify that
$\mathbf{e}_{2}^{0,k+1}=\rm{R}_{\mathbf{v}}(\mathbf{e}_{2}^{k+1})$. According
to (27), we denote $e^{k+1}_{2,i}=\prod_{[0,1]}(\bar{e}^{k+1}_{2,i})$, and
$\bar{e}^{k+1}_{2,i}=\left(v_{i}^{k+1}+\frac{y_{2,i}^{k}}{\mu}\right)$. When
$v_{i}=1$, we have

$\bar{e}^{0,k+1}_{2,i}=v_{i}^{0,k+1}+\frac{y_{2,i}^{0,k}}{\mu}=1-\left(v_{i}^{k+1}+\frac{y_{2,i}^{k}}{\mu}\right),$
(52)

where the second equality holds since
$v_{i}^{0,k+1}={\rm{R}}_{\mathbf{v}}(v_{i}^{k+1})=1-v_{i}^{k+1}$ and
$y_{2,i}^{0,k}=\mathcal{K}_{\mathbf{v}}(y_{2,i}^{k})=-y_{2,i}^{k}$ when
$v_{i}=1$. Thus from equation (52) we have
$\bar{e}^{0,k+1}_{2,i}=1-\bar{e}^{k+1}_{2,i}$ when $v_{i}=1$. Moreover, since
$\prod_{[0,1]}(\bar{e}^{0,k+1}_{2,i})=1-\prod_{[0,1]}(\bar{e}^{k+1}_{2,i})$,
we have

$e^{0,k+1}_{2,i}=1-e^{k+1}_{2,i}.$ (53)

For the other case when $v_{i}=0$ is transmitted over the channel, there exist

$\bar{e}^{0,k+1}_{2,i}=v_{i}^{0,k+1}+\frac{y_{2,i}^{0,k}}{\mu}=v_{i}^{k+1}+\frac{y_{2,i}^{k}}{\mu},$
(54)

where the second equality holds since
$v_{i}^{0,k+1}={\rm{R}}_{\mathbf{v}}(v_{i}^{k+1})=v_{i}^{k+1}$ and
$y_{2,i}^{0,k}=\mathcal{K}_{\mathbf{v}}(y_{2,i}^{k})=y_{2,i}^{k}$ when
$v_{i}=0$. With a similar derivation of (53), when $v_{i}=0$, we have

$e^{0,k+1}_{2,i}=e^{k+1}_{2,i}.$ (55)

Combine (53) and (55), we get

$\mathbf{e}^{0,k+1}_{2}={\rm{R}}_{\mathbf{v}}(\mathbf{e}^{k+1}_{2}).$ (56)

Next, we verify that
$\mathbf{y}_{1}^{0,k+1}=\mathcal{T}_{\mathbf{v}}(\mathbf{y}_{1}^{k+1})$. We
first consider the relationship between $\mathbf{y}_{1,\tau}^{k+1}$ and
$\mathbf{y}_{1,\tau}^{0,k+1}$. Since
$\mathbf{e}_{1,\tau}^{0,k+1}=\mathcal{M}_{\mathbf{v}_{\tau}}(\mathbf{e}_{1,\tau}^{k+1})$
based on (50), there are
$\mathbf{e}_{1,\tau}^{0,k+1}=[{e}_{1,\tau_{2}}^{k+1},{e}_{1,\tau_{1}}^{k+1},{e}_{1,\tau_{4}}^{k+1},{e}_{1,\tau_{3}}^{k+1}]^{T}$
when $\mathbf{v}_{\tau}=[1,1,0]^{T}$. Thus, when
$\mathbf{v}_{\tau}=[1,1,0]^{T}$, from (21d) and (47) we have

$\displaystyle\mathbf{y}_{1,\tau}^{0,{k+1}}$
$\displaystyle=\mathbf{y}_{1,\tau}^{0,{k}}+\mu\left(\mathbf{Tv}_{\tau}^{0,{k+1}}+\mathbf{e}_{1,\tau}^{0,{k+1}}-\mathbf{w}\right)$
(57) $\displaystyle=\left[\begin{array}[]{c}y_{1,\tau_{2}}^{k}\\\
y_{1,\tau_{1}}^{k}\\\ y_{1,\tau_{4}}^{k}\\\
y_{1,\tau_{3}}^{k}\end{array}\right]+\mu\left(\mathbf{T}\left[\begin{array}[]{c}1-v_{\tau_{1}}^{k+1}\\\
1-v_{\tau_{2}}^{k+1}\\\
v_{\tau_{3}}^{k+1}\end{array}\right]+\left[\begin{array}[]{c}e_{1,\tau_{2}}^{k+1}\\\
e_{1,\tau_{1}}^{k+1}\\\ e_{1,\tau_{4}}^{k+1}\\\
e_{1,\tau_{3}}^{k+1}\end{array}\right]-\mathbf{w}\right)$
$\displaystyle\left.=\left[\begin{array}[]{l}y_{1,\tau_{2}}^{k}+\mu\left(-v_{\tau_{1}}^{k+1}+v_{\tau_{2}}^{k+1}-v_{\tau_{3}}^{k+1}+e_{1,\tau_{2}}^{k+1}\right)\\\
y_{1,\tau_{1}}^{k}+\mu\left(v_{\tau_{1}}^{k+1}-v_{\tau_{2}}^{k+1}-v_{\tau_{3}}^{k+1}+e_{1,\tau_{1}}^{k+1}\right)\\\
y_{1,\tau_{4}}^{k}+\mu\left(v_{\tau_{1}}^{k+1}+v_{\tau_{2}}^{k+1}+v_{\tau_{3}}^{k+1}+e_{1,\tau_{4}}^{k+1}-2\right)\\\
y_{1,\tau_{3}}^{k}+\mu\left(-v_{\tau_{1}}^{k+1}-v_{\tau_{2}}^{k+1}+v_{\tau_{3}}^{k+1}\right)+e_{1,\tau_{3}}^{k+1}\end{array}\right)\right].$

Since $\mathbf{w}=[0,0,0,2]^{T}$, $\mathbf{y}_{1,\tau}^{0,k+1}$ can be further
derived as

$\displaystyle\mathbf{y}_{1,\tau}^{0^{k+1}}$
$\displaystyle=\left[\begin{array}[]{c}y_{1,\tau_{2}}^{k}+\mu\left(\left(-v_{\tau_{1}}^{k+1}+v_{\tau_{2}}^{k+1}-v_{\tau_{3}}^{k+1}\right)+e_{1,\tau_{2}}^{k+1}-w_{2}\right)\\\
y_{1,\tau_{1}}^{k}+\mu\left(\left(v_{\tau_{1}}^{k+1}-v_{\tau_{2}}^{k+1}-v_{\tau_{3}}^{k+1}\right)+e_{1,\tau_{1}}^{k+1}-w_{1}\right)\\\
y_{1,\tau_{4}}^{k}+\mu\left(\left(v_{\tau_{1}}^{k+1}+v_{\tau_{2}}^{k+1}+v_{\tau_{3}}^{k+1}\right)+e_{1,\tau_{4}}^{k+1}-w_{4}\right)\\\
y_{1,\tau_{3}}^{k}+\mu\left(\left(-v_{\tau_{1}}^{k+1}-v_{\tau_{2}}^{k+1}+v_{\tau_{3}}^{k+1}\right)+e_{1,\tau_{3}}^{k+1}-w_{3}\right)\end{array}\right]$
(58)
$\displaystyle=\left[y_{1,\tau_{2}}^{k+1},y_{1,\tau_{1}}^{k+1},y_{1,\tau_{4}}^{k+1},y_{1,\tau_{3}}^{k+1}\right]^{T},$

i.e.,

$\mathbf{y}_{1,\tau}^{0,k+1}=\mathcal{M}_{\mathbf{v}_{\tau}}(\mathbf{y}_{1,\tau}^{k+1}),$
(59)

when $\mathbf{v}_{\tau}=[1,1,0]^{T}$.

With similar derivation, we can see (59) also holds when
$\mathbf{v}_{\tau}=[1,0,1]^{T},[0,1,1]^{T},[0,0,0]^{T}$. Since
$\mathbf{y}_{1}^{k+1}$ and $\mathbf{y}_{1}^{0,k+1}$ are cascaded by
$\mathbf{y}_{1,\tau}^{k+1}$ and $\mathbf{y}_{1,\tau}^{0,k+1}$ respectively,
$\tau=1,\cdots,\Gamma_{c}$, we can get

$\mathbf{y}_{1}^{0,k+1}=\mathcal{M}_{\mathbf{v}}(\mathbf{y}_{1}^{k+1}).$ (60)

Finally, it remains to verify that
$\mathbf{y}_{2}^{0,k+1}=\mathcal{T}_{\mathbf{v}}(\mathbf{y}_{2}^{k+1})$.
According to $\eqref{subproblems-e}$, when $v_{i}=1$, we have

$\displaystyle y_{2,i}^{0,k+1}$
$\displaystyle=y_{2,i}^{0,k}+\mu(v_{i}^{0,k+1}-e_{2,i}^{0,k+1})$ (61)
$\displaystyle=-(y_{2,i}^{k}+\mu(v_{i}^{k+1}-e_{2,i}^{k+1})),$

where the second equality holds since
$y_{2,i}^{0,k}=\mathcal{K}_{\mathbf{v}}(y_{2,i}^{k})=-y_{2,i}^{k}$,
$v_{i}^{0,k+1}={\rm{R}}_{\mathbf{v}}(v_{i}^{k+1})=1-v_{i}^{k+1}$ and
$e_{2,i}^{0,k+1}={\rm{R}}_{\mathbf{v}}(e_{2,i}^{k+1})=1-e_{2,i}^{k+1}$ when
$v_{i}=1$. Thus from equation (61), when $v_{i}=1$, we have

$y_{2,i}^{0,k+1}=-y_{2,i}^{k+1}.$ (62)

For the other case when $v_{i}=0$ is transmitted over the channel, there exist

$\displaystyle y_{2,i}^{0,k+1}$
$\displaystyle=y_{2,i}^{0,k}+\mu(v_{i}^{0,k+1}-e_{2,i}^{0,k+1})$ (63)
$\displaystyle=y_{2,i}^{k}+\mu(v_{i}^{k+1}-e_{2,i}^{k+1})$
$\displaystyle=y_{2,i}^{k+1},$

where the second equality holds since
$y_{2,i}^{0,k}=\mathcal{K}_{\mathbf{v}}(y_{2,i}^{k})=y_{2,i}^{k}$,
$v_{i}^{0,k+1}={\rm{R}}_{\mathbf{v}}(v_{i}^{k+1})=v_{i}^{k+1}$ and
$e_{2,i}^{0,k+1}={\rm{R}}_{\mathbf{v}}(e_{2,i}^{k+1})=e_{2,i}^{k+1}$ when
$v_{i}=0$.

Combine (62) and (63), we get

$\mathbf{y}_{2}^{0,k+1}=\mathcal{K}_{\mathbf{v}}(\mathbf{y}_{2}^{k+1}),$ (64)

This ends the proof of Lemma 2. ∎

## References

  * [1] M. Agiwal, A. Roy and N. Saxena, “Next generation 5G wireless networks: A comprehensive survey,” _IEEE Communications Surveys and Tutorials_ , vol. 18, no. 3, pp. 1617-1655, Feb, 2016.
  * [2] M. C. Davey and D. J. C. MacKay, “Low density parity check codes over GF(q),” _IEEE Commun. Lett_., vol. 2, no. 6, pp. 165-167, June 1998.
  * [3] B. Rong, T. Jiang, X. Li and M. R. Soleymani, “Combine LDPC codes over GF(q) with q-ary modulations for bandwidth efficient transmission,” _IEEE Trans. Broad._ , vol. 54, no. 1, pp. 78-84, Mar. 2008.
  * [4] R. Peng and R. Chen, “Design of nonbinary quasi-cyclic LDPC cycle codes,” _2007 IEEE Information Theory Workshop_ , Tahoe City, CA, pp. 13-18, Sept. 2007.
  * [5] H. X. Song and J. R. Cruz, “Reduced-complexity decoding of Q-ary LDPC codes for magnetic recording,” _IEEE Trans. Magn._ , vol. 39, no. 2, pp. 1081-1087, Mar. 2003.
  * [6] J. Feldman, M. T. Wainwright, and D. R. Karger, “Using linear progamming to decoding binary linear codes,” _IEEE Trans. Inf. Theory_ , vol. 51, no. 1, pp. 954-972, Jan. 2005.
  * [7] T. Wadayama, “Interior Point Decoding for Linear Vector Channels Based on Convex Optimization,” _IEEE Trans. Inf. Theory_ , vol. 56, no. 10, pp. 4905-4921, Oct. 2010.
  * [8] H. Liu, W. Qu, B. Liu, and J. Chen, “On the decomposition method for linear programming decoding of LDPC codes,” _IEEE Trans. Commu._ , vol. 58, no, 12, pp. 3448-3458, Dec. 2010.
  * [9] S. Barman, X. Liu, S. C. Draper, and B. Recht, “Decomposition method for large scale LP decoding,” _IEEE Trans. Inf. Theory_ , vol. 59, no. 12, pp. 7870-7886, Dec. 2013.
  * [10] S. Boyd, N. Parikh, E. Chu, B. Peleato and J. Eckstein, “Distributed optimization and statistical learning via the alternating direction method of multipliers,”Found. Trends Mach. Learn., vol. 3, no. 1, pp. 1-122, Jan. 2011.
  * [11] J. Bai, Y. Wang and F. C. M. Lau, “Minimum-Polytope-Based linear programming decoder for LDPC codes via ADMM approach,” _IEEE Wireless Commun. Lett_., vol. 8, no. 4, pp. 1032-1035, Aug. 2019.
  * [12] M. H. Taagavi and P. H. Siegel, “Adaptive methods for linear programming decoding,” _IEEE Trans. Inf. Theory_ , vol. 54, no. 12, pp. 5396-5410, Dec. 2008.
  * [13] M. Miwa, T. Wadayama, and I. Takumi, “A cutting-planemethod based on redundant rows for improving fractional distance,” _IEEE J. Sel. Areas Commun_., vol. 27, no. 6, pp. 1012-1105, Aug. 2009.
  * [14] A. Tanatmis, S. Ruzika, H. Hamacher, M. Punekar, F. Kienle, and N. Wehn, “A separation algorithm for improved LP decoding of linear block codes,” _IEEE Trans. Inf. Theory_ , vol. 56, no. 7, pp. 3277-3289, Jul. 2010.
  * [15] X. Zhang and P. Siegel, “Adaptive cut generation algorithm for improved linear programming decoding of binary linear codes,” _IEEE Trans. Inf. Theory_ , vol. 58, no. 10, pp. 6581-6594, Oct. 2012.
  * [16] X. Liu and S. C. Draper, “The ADMM penalized decoder for LDPC codes,” _IEEE Trans. Inf. Theory_ , vol. 62, no. 6, pp. 2966-2984, Jun. 2016.
  * [17] J. Bai, Y. Wang and Q. Shi, “Efficient QP-ADMM decoder for binary LDPC codes and its performance analysis,” _IEEE Trans. Signal Process._(Early Access). DOI: 10.1109/TSP.2020.2964223.
  * [18] H. Wei and A. Banihashemi, “ADMM Check Node Penalized Decoders for LDPC Codes,” _IEEE Transactions on Communications_ , vol. 69, no. 6, pp. 3528-3540, June 2021.
  * [19] M. Flanagan, V. Skachek, E. Byrne, and M. Greferath, “Linear programming decoding of nonbinary linear codes,” _IEEE Trans. Inf. Theory_ , vol. 55, no. 9, pp. 4134-4154, Sept. 2009.
  * [20] D. Goldin and D. Burshtein, “Iterative linear programming decoding of non-binary linear codes with linear complexity,” _IEEE. Trans. Inf. Theory_ , vol. 59, no. 1, pp. 282-300, Jan. 2013.
  * [21] M. Punekar, P. O. Vontobel, and M. F. Flanagan, “Low-complexity LP decoding of nonbinary linear codes,” _IEEE Trans. Commun._ , vol. 61, no. 8, pp. 3073-3085, Aug. 2013.
  * [22] D. Burshtein, “Iterative approximate linear programming decoding of LDPC codes with linear complexity,” _IEEE Trans. Inf. Theory_ , vol. 55, no. 11, pp. 4835-4859, Nov. 2009.
  * [23] P. O. Vontobel and R. Koetter, “Towards low-complexity linear-programming decoding,” in _Proc. Int. Symp. Turbo Codes Related Topics_ , Munich, Germany, Apr. 2006.
  * [24] E. Rosnes and M. Helmling, “Adaptive Linear Programming Decoding of Nonbinary Linear Codes Over Prime Fields,” _IEEE Transactions on Information Theory_ , vol. 66, no. 3, pp. 1281-1317, March 2020.
  * [25] J. Honda and H. Yamamoto, “Fast linear-programming decoding of LDPC codes over GF($2^{m}$),” in _Proc. Int. Symp. Inf. Theory Appl. (ISITA)_ , Honolulu, HI, USA, pp. 754-758, Oct. 2012.
  * [26] X. Liu and S. C. Draper, “ADMM LP Decoding of Non-Binary LDPC Codes in $\mathbb{F}_{2^{m}}$,” _IEEE. Trans. Inf. Theory_ , vol. 62, no. 6, pp. 2985-3010, June 2016.
  * [27] Y. Wang and J.Bai, “Decoding Nonbinary LDPC Codes via Proximal-ADMM Approach,” _IEEE. Trans. Inf. Theory_ , early access.
  * [28] D. J. C. MacKay, Encyclopedia of Sparse Graph Codes [Online]. Available: http://www.inference.phy.cam.ac.uk/mackay/codes/data.html
  * [29] R. M. Tanner, D. Sridhara, and T. Fuja, “A class of group-structured LDPC codes,” in _Proc. 2001 Int. Symp. Commun. Theory Appl._ , pp. 365-370, July 2001.