# Weighted-Bit-Flipping-Based Sequential Scheduling Decoding Algorithms for LDPC Codes

Authors: Qing Zhu; Le-nan Wu
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

Low-density parity-check (LDPC) codes can be applied in a lot of different scenarios such as video broadcasting and satellite communications. LDPC codes are commonly decoded by an iterative algorithm called belief propagation (BP) over the corresponding Tanner graph. The original BP updates all the variable-nodes simultaneously, followed by all the check-nodes simultaneously as well. We propose a sequential scheduling algorithm based on weighted bit-flipping (WBF) algorithm for the sake of improving the convergence speed. Notoriously, WBF is a low-complexity and simple algorithm. We combine it with BP to obtain advantages of these two algorithms. Flipping function used in WBF is borrowed to determine the priority of scheduling. Simulation results show that it can provide a good tradeoff between FER performance and computation complexity for short-length LDPC codes.


---

## Body

## 1. Introduction

Low-density parity-check (LDPC) codes were first invented by Gallager [1] but had been neglected for decades until Mackay brought them back to light in 1996 [2]. Since then, much attention had been attracted for their excellent Shannon limit approaching error-correcting performance through belief propagation (BP) [3] decoding algorithm. This iterative decoding algorithm, sometimes also called sum-product algorithm (SPA) [4], is a powerful algorithm to approximately solve many NP hard problems such as statistical inference in physics [5–7], hypothesis testing, cooperative localization, and channel coding.There are lots of researches with various decoding algorithms. Among existing LDPC decoding algorithms, bit-flipping (BF) algorithms are the simplest. The operations of check-nodes in BF are modulo-two additions while the variable-nodes only need simple comparison operations. BF decoding algorithms are easy to implement, but they usually perform not so well when compared to BP decoding algorithms, so various weighted BF (WBF) [8–12] decoding algorithms were proposed.To improve the standard BP decoding performance, several sequential scheduling strategies in BP have been invented. In sequential scheduling strategies, the messages are computed in a serial manner using the newest updated information. Sequential strategies were introduced as a sequence updates based on check-node (CSBP) [13–15] or variable-node (VSBP) [16, 17]. Simulations demonstrate that sequential strategies converge about twice as fast as the standard parallel BP decoding algorithms (Flood) without any extra computing burden. The kernel steps of sequential updating algorithms focus on finding the order of message updating which converges fastest. To our knowledge, the best decoding algorithms in the sense of performance is informed dynamic scheduling (IDS) [18–24] algorithms, which update messages dynamically. A metric called residual [18] is used in IDS which decides the updating order of propagated messages. Metric computing and selecting operations can cause significant increase in computational complexity in IDS. In order to achieve the tradeoff between decoding performance and computational complexity, a low-complexity sequential WBF-based scheduling algorithm is proposed, in which the priority used in WBF determines the order of scheduling. Simulation results show that it can provide a good tradeoff between block errors performance and complexity for short-length LDPC codes.This paper is organized as follows. Section2 reviews BP (Flood and CSBP) and WBF. Section 3 introduces our WBF-based serial BP (WBFSBP) strategies. Section 4 analyzes the computing complexity of WBFSBP. Section 5 reveals the simulation results. Section 6 draws the conclusions.


## 2. WBF and BP

LetN and K be the block length and the information length of a binary LDPC code; thus the rate of the code is r=K/N. Let M=N-K; an LDPC code is described by an M×N parity-check matrix H. Hmn  presents the entry of row m and column n in H. The set 𝒩(m) denotes the nodes that adjoin m by 𝒩(m)={n:Hmn=1}, similarly for the set 𝒩(n)={m:Hmn=1}. 𝒩(m)/n denotes the set 𝒩(m) excluding n. Binary phase shift keying (BPSK) modulation over an additive white Gauss noise (AWGN) channel is assumed for information transmission, which maps a codeword vector c=(c1,c2,…,cn) into a vector x=(x1,x2,…,xn), where ci=2xi-1, i∈[1,N]. The received vector is y=(y1,y2,…,yn), where yi=xi+ni, i∈[1,N], and ni is the AWGN. Z=(z1,z2,…,zn) denotes the hard-decision vector acquired from y:zi=1 if yi>0 and zi=0 if yi≤0. S=(s1,s2,…,sM)=z·HT denotes the syndrome of hard-decision vector z.


### 2.1. WBF

Firstly, a metric called “reliability” and a function-associated flipping probability of each check-node are calculated via [9]
(1)wn,m=mini∈𝒩(m)∖n|yi|,m∈[1,M],n∈𝒩(m),eWBF,n=∑m∈𝒩(n)(2sm-1)wn,m-α|yn|.
The WBF algorithm is described as follows [9]:(1)
set iteration numberk=0, take kmax as the maximum number of iterations, and pick up wn,m,(2)
calculatesk=zkHT; if sk=0, stop decoding and output zk,(3)
forn=1,2,…,N, calculate eWBF,nk as follows:
(2)eWBF,nk=∑m∈𝒩(n)(2smk-1)wn,m-α|yn|,(4)
zn*=zn*+1 based on
(3)n*=argmaxn∈[1,N]eWBF,nk,(5)
k=k+1 and go to step (3), until stopping rules are satisfied.


### 2.2. Standard BP (Flood) Decoding Algorithm

Commonly, the communication of the nodes in the corresponding Tanner graph comprises the Flood algorithm. For every variable-nodevj and check-node ci, the corresponding message generation functions mci→vj=fci→vj(m) and mvj→ci=fvj→ci(m) are defined as follows [2]:
(4)mvj→ci=∑ca∈𝒩(vj)∖cimca→vj+Cvj,mci→vj=2arctanh(∏vb∈𝒩(ci)∖vjtanh(mvb→ci2)),L(vj)=∑ca∈𝒩(vj)mca→vj+Cvj,
where Cvj=log(p(yj∣vj=0)/p(yj∣vj=1)) is the channel information of vj. L(vj) denotes the LLR of vj.As shown in Figure1, in time slot 1, messages are passed to all of these check-nodes by all variable-nodes that connect to them, and in time slot 2, all of the processed messages are sent back to all variable-nodes. The Flood decoding algorithm is formally described in Pseudocode 1.Pseudocode 1:Pseudocodes of Flood.
1: Set everymc→v=0
2: Set everymvj→ci=Cvj
3:while stop rules unsatisfied do
4: for all ca (a=1,2,…,M)
5:for each vb∈𝒩(ca), compute and generate mvb→ca (a=1,2,…,M) simultaneously
6:for each vb∈𝒩(ca), compute and generate mca→vb (a=1,2,…,M) simultaneously
7:end whileFigure 1
Standard BP algorithm (Flood).


### 2.3. CSBP

The messages calculated in CSBP [15] are the same as those in the Flood decoding algorithms. The only difference between them is the way of messages updating. In every iteration of CSBP, the messages are updated in a sequential way: update every check-node one by one in an ascending order (or descending order) arranged in the corresponding Tanner graph. The passing process of messages in CSBP is shown in Figure 2. Check-nodes are represented by (c1,c2,c3), and (b1,b2,…,b6) for variable-nodes. In time slot 1, messages are passed to c1 by all variable-nodes that connect to c1. In time slot 2, the processed messages are sent back to those variable-nodes. The updating rules of c2 and c3 are identical with those of  c1. The realization of CSBP is described in Pseudocode 2.Pseudocode 2:Pseudocodes of CSBP.
1: Set everymc→v=0
2: Set everymvj→ci=Cvj
3:whilestop rules unsatisfied do
4:for i  do
5:for check-node ci
6:forevery vb∈𝒩(ci)  do
7: compute and generate mvb→ci
8:end for
9:forevery vb∈𝒩(ci)  do
10:compute and generate mci→vb
11:end for
12:end for
13:end whileFigure 2
CSBP algorithm.


## 2.1. WBF

Firstly, a metric called “reliability” and a function-associated flipping probability of each check-node are calculated via [9]
(1)wn,m=mini∈𝒩(m)∖n|yi|,m∈[1,M],n∈𝒩(m),eWBF,n=∑m∈𝒩(n)(2sm-1)wn,m-α|yn|.
The WBF algorithm is described as follows [9]:(1)
set iteration numberk=0, take kmax as the maximum number of iterations, and pick up wn,m,(2)
calculatesk=zkHT; if sk=0, stop decoding and output zk,(3)
forn=1,2,…,N, calculate eWBF,nk as follows:
(2)eWBF,nk=∑m∈𝒩(n)(2smk-1)wn,m-α|yn|,(4)
zn*=zn*+1 based on
(3)n*=argmaxn∈[1,N]eWBF,nk,(5)
k=k+1 and go to step (3), until stopping rules are satisfied.


## 2.2. Standard BP (Flood) Decoding Algorithm

Commonly, the communication of the nodes in the corresponding Tanner graph comprises the Flood algorithm. For every variable-nodevj and check-node ci, the corresponding message generation functions mci→vj=fci→vj(m) and mvj→ci=fvj→ci(m) are defined as follows [2]:
(4)mvj→ci=∑ca∈𝒩(vj)∖cimca→vj+Cvj,mci→vj=2arctanh(∏vb∈𝒩(ci)∖vjtanh(mvb→ci2)),L(vj)=∑ca∈𝒩(vj)mca→vj+Cvj,
where Cvj=log(p(yj∣vj=0)/p(yj∣vj=1)) is the channel information of vj. L(vj) denotes the LLR of vj.As shown in Figure1, in time slot 1, messages are passed to all of these check-nodes by all variable-nodes that connect to them, and in time slot 2, all of the processed messages are sent back to all variable-nodes. The Flood decoding algorithm is formally described in Pseudocode 1.Pseudocode 1:Pseudocodes of Flood.
1: Set everymc→v=0
2: Set everymvj→ci=Cvj
3:while stop rules unsatisfied do
4: for all ca (a=1,2,…,M)
5:for each vb∈𝒩(ca), compute and generate mvb→ca (a=1,2,…,M) simultaneously
6:for each vb∈𝒩(ca), compute and generate mca→vb (a=1,2,…,M) simultaneously
7:end whileFigure 1
Standard BP algorithm (Flood).


## 2.3. CSBP

The messages calculated in CSBP [15] are the same as those in the Flood decoding algorithms. The only difference between them is the way of messages updating. In every iteration of CSBP, the messages are updated in a sequential way: update every check-node one by one in an ascending order (or descending order) arranged in the corresponding Tanner graph. The passing process of messages in CSBP is shown in Figure 2. Check-nodes are represented by (c1,c2,c3), and (b1,b2,…,b6) for variable-nodes. In time slot 1, messages are passed to c1 by all variable-nodes that connect to c1. In time slot 2, the processed messages are sent back to those variable-nodes. The updating rules of c2 and c3 are identical with those of  c1. The realization of CSBP is described in Pseudocode 2.Pseudocode 2:Pseudocodes of CSBP.
1: Set everymc→v=0
2: Set everymvj→ci=Cvj
3:whilestop rules unsatisfied do
4:for i  do
5:for check-node ci
6:forevery vb∈𝒩(ci)  do
7: compute and generate mvb→ci
8:end for
9:forevery vb∈𝒩(ci)  do
10:compute and generate mci→vb
11:end for
12:end for
13:end whileFigure 2
CSBP algorithm.


## 3. WBF-Based Serial BP

We will introduce our WBFSBP algorithm using a new message updating schedule. In general, sequential decoding algorithms are composed of two major steps.Step 1.
Determine the order of nodes to be updated.Step 2.
Compute the messages.In Flood and CSBP, Step1 is skipped. In IDS, these two steps are operated alternately for every node. It means that after updating each single node, “residual” computing and sorting operation is needed, which causes much extra computing complexity. For the sake of getting the tradeoff between performance and computing complexity, a simple sequential decoding algorithm called WBF-based serial BP is proposed. First, let us review the flipping function (eWBF,nk) of a variable-node in WBF decoding algorithm described in Section 2. The larger the eWBF,nk is, the more unreliable the corresponding variable-node is. For each check-node, a new metric is defined as follows:
(5)EWBF,mk=maxn∈𝒩(m)eWBF,nk-submaxn∈𝒩(m)eWBF,nk,
where submax (·) denotes the second maximal value of (·). If there is more than one unreliable variable-node connected to a check-node, the message passing within this check-node is almost nonsense. If all neighbor variable-nodes of a check-node are reliable, the priority of updating this check-node should be very low. So we concentrate on the check-node which has only one unreliable neighbor variable-node. The check-nodes with larger value of EWBF,mk are more likely containing just one unreliable neighbor variable-node. So updating these check-nodes firstly can correct errors in time and speed up convergence, thus reducing the iterations. In contrast to IDS, the sorting operation is not dynamically decided node by node but is simply obtained from sorting the set of EWBF,mk in each iteration. When the sorting is finished, the rest of updating computation is the same as that of CSBP. The detailed steps of WBFSBP are shown in Pseudocode 3.Pseudocode 3:Pseudocodes of WBFSBP.
0: Set iteration numberk=0, take kmax as the maximum number of iteration, pick up wn,m,
Set everymc→v=0, every mvj→ci=Cvj.
1: Computesk=zkHT, if sk=0, stop decoding and output zk.
2: Forn=1,2,…N, compute
eWBF,nk=∑m∈𝒩(n)(2smk-1)wn,m-α|yn|
3: sortEWBF,mk in descending order and put the corresponding check-nodes to U
4:whilestop rules unsatisfied  do
5:fori  do
6:for ith check-node cUi in U
7:forevery  vb∈𝒩(cUi)  do
8:compute and generate mvb→cUi
9:end for
10:forevery  vb∈𝒩(cUi)  do
11:compute and generate mcUi→vb
12:end for
13:end for
14:end while


## 4. Complexity

Letdv and dc represent the degree of any variable-node and check-node, respectively; e is the total number of all edges in the corresponding Tanner graph, so e=dv·N=dc·M, where N is the number of variable-nodes and M is the number of  check-nodes. In Tables 1 and 2, we have listed the computation complexity of check-to-variable phase and variable-to-check phase, respectively. In an iteration of Flood, every edge of the Tanner graph should be updated once for each direction, so the number of updated messages via check-to-variable and variable-to-check is e, respectively. Sequential updating strategies surpass the Flood without any extra cost. We note that the check-to-variable message updating computations in one IDS iteration is the same as reverse message updating computations in one WBFSBP iteration, both equal e. In each iteration, sorting of {EWBF,mk} requires 𝒪(NlogN) operations while dynamic scheduling strategies in IDS need  𝒪(N2).Table 1
Computation complexity from variable-nodes to check-nodes.
Algorithms
Updating
Reliability computation
Sorting
Flood
e
0
0
CSBP
e
0
0
IDS
M
d
c
(
d
v
-
1
)
0
0
WBFSBP
e
0
0Table 2
Computation complexity from check-nodes to variable-nodes.
Algorithms
Updating
Reliability computation
Sorting
Flood
e
0
0
CSBP
e
0
0
IDS
e
M
d
c
(
d
v
-
1
) (dc-1)
𝒪
(
N
2)
WBFSBP
e
M
d
c
d
v
𝒪
(
N log N)


## 5. Simulation Results

The decoding performance of the Flood, CSBP, and WBFSBP over AWGN channels is presented in this part. The LDPC codes are constructed based on Gallager's random method without any 4-cycle.Figures3 and 4 present the FER performance of the (128,256) Gallager LDPC code with BP (Flood), CSBP, and WBFSBP decoding algorithms. The kmax is set to 20 and 50, respectively, and α is set to 1.3 in the computation of EWBF,mk. Figure 3 shows that, at the FER of 1e-4, WBFSBP acquires about 0.2 dB and 0.35 dB promotions over the CSBP and BP in the case of kmax=20, while in Figure 4, the coding gains are 0.25 dB and 0.45 dB in the case of kmax=50. Figure 4 also shows that at Eb/N0=4, WBFSBP-20 can achieve the same FER performance as what BP-50 and CSBP-50 do. In other words, WBFSBP algorithm can reduce more than half of the iterations of that BP algorithm needed at some Eb/N0.Figure 3
FER versusEb/N0 performance of BP (Flood), CSBP, and WBFSBP decoding algorithms with maximal number of iterations of 20 with LDPC code of blocklength of 256 and rate of 0.5. BP algorithm with maximal number of iterations of 20.Figure 4
FER versusEb/N0 performance of BP (Flood), CSBP and WBFSBP decoding algorithms with maximal number of iterations of 50 with LDPC code of blocklength of 256 and rate of 0.5. As compared, performance of max iteration 20 of WBFSBP is given.Figure5 presents the FER performance of the (102,204) Gallager LDPC code with above-mentioned decoding algorithms. The kmax is set to 20 and α is set to 1.3. We see that WBFSBP-20 can beat BP-50 for all  Eb/N0. Compared to CSBP-20, WBFSBP-20 can acquire about 0.15 dB coding gain.Figure 5
FER versusEb/N0 performance of BP (Flood), CSBP and WBFSBP decoding  algorithms with maximal number of iterations of 20 with LDPC code of blocklength of 204 and rate of 0.5. BP-20 denotes BP algorithm with maximal number of iterations of 20. As compared, performance of max iteration 50 of BP is given.


## 6. Conclusion

In this paper, a new sequential scheduling decoding algorithm is proposed, in which the order of message passing is based on the weight factor computed in WBF algorithm. We focus on the check-nodes which have just one unreliable neighbor variable-node. Updating these check-nodes preferentially can avoid errors of propagation, thus speeding up the convergence of decoding algorithm. Compared to IDS, our decoding algorithm gives a good tradeoff between error performance and decoding complexity. As a future work, the scheduling algorithm can be generalized to LDPC codes over GF(q).



---

*Source: 371206-2013-07-10.xml*