# Node-Subset Scheduling with a Subset-Reset Mechanism for the Decoding Algorithm of Nonbinary LDPC Codes

Authors: Wentao Fu; Xilun Luo; Yuanfa Ji; Xiyan Sun
Journal: Mobile Information Systems
 (2021)

---

## Abstract

For the conventional extended min-sum (EMS) algorithm, all check nodes update their check-to-variable (C2V) messages in every iteration. Selected scheduling, which reduces the number of check nodes for message updating in one iteration, can effectively reduce the complexity of the decoding algorithm, but it also lead to some performance degradation. With the introduction of a metric based on node stability, we propose stability-based node-subset scheduling (SNS) for the EMS algorithm, which can improve the performance of node-subset scheduling (NS). Second, to further improve the decoding performance of SNS while maintaining low complexity, we propose the SNS-EMS algorithm with a subset-reset mechanism (RSNS-EMS) based on the abnormal stability found in the processing node subset, which will cause the estimated codeword to fail to converge. The RSNS-EMS algorithm enhances performance through a sliding window detection and reset mechanism, and it resets the elements in the processing node subset to force all check nodes to update new messages when abnormal stability is detected. The simulation results show that the proposed algorithm can reduce complexity by approximately 25% with negligible performance degradation.


---

## Body

## 1. Introduction

Low-density parity-check (LDPC) codes [1] have been shown to achieve performance close to the Shannon limit when using the iterative belief-propagation (BP) algorithm for very long code lengths [2, 3]. LDPC codes have attracted much attention, and novel types of LDPC codes are constantly being proposed, such as root-photograph LDPC codes [4], which were proposed for block-fading channels and were also used to design bit-interleaved coded modulation (BICM) with iterative demapping and decoding under the constraint of limited bandwidth for wireless communication [5]. Moreover, for medium and short code lengths, nonbinary LDPC (NB-LDPC) codes have shown better decoding performance than their binary counterparts because they are able to avoid error floor problems [6]. NB-LDPC codes were originally proposed by Davey and Mackay [7], who considered codes defined in the finite field and correspondingly proposed an implementation of the BP algorithm for these codes, usually referred to as the Q-ary sum-product algorithm (QSPA). The computational complexity of the direct implementation of the QSPA is too high, which makes NB-LDPC codes difficult to apply in practice. To reduce the complexity of the decoding algorithm for NB-LDPC codes, the extended min-sum (EMS) algorithm [8] and its variant version [9] have been proposed. In these algorithms, the calculation amount of check nodes is reduced by using the truncation rule, which can reduce the length of the message vector from field size q to a specific number less than q.In addition, for an iterative algorithm like the BP algorithm, its convergence rate is crucial for its implementation. Recently, different scheduling strategies have been proposed for BP decoders of binary LDPC codes. The conventional BP algorithm has been implemented with a standard flooding scheduling strategy [1], in which all variable nodes and, subsequently, all check nodes update the message and propagate new messages to their neighbors in one iteration. Shuffled [10–12] and layered [13–15] scheduling are two commonly used sequential scheduling strategies to accelerate the convergence speed of flooding scheduling.However, the order of message updating is fixed in these algorithms, which limits the acceleration of convergence. To further speed up convergence and improve the performance of LDPC codes, many informed dynamic strategies (IDSs) have been proposed. Residual belief-propagation decoding [16] is the represented IDS; it prioritizes message updates dynamically based on a metric called a residual. Although the RBP algorithm can achieve faster convergence speed, it is shown to be a greedy algorithm in which some edges and nodes will not be updated throughout the entire iteration process. Such greediness will prevent the RBP algorithm from converging to a low error rate. To solve this problem, different algorithms have recently been proposed, such as variable node-based dynamic scheduling [17], dynamic scheduling based on tabu search [18], and residual-decaying-based residual belief propagation [19].Another subset of scheduling strategies is aimed at reducing the iteration cost of the LDPC decoder. The lazy scheduling strategy [20] was proposed to decide whether a check node should be updated at a given iteration based on its reliability and its update history. The selective-update decoding algorithm [21] uses the stability of variable nodes, in which the outgoing messages are similar or not similar for the last several iterations, to determine which check nodes do not need to be updated. When all variable nodes connected to a given check node are stable and reliable, it is not useful to update them again. Check node reliability-based scheduling [15] led to the creation of a concept called check node reliability, which is associated with the a posteriori probability of the existence of neighboring variable nodes, to determine whether the check node should be updated in the next iteration. Check node reliability-based scheduling also employed a random variable to overcome the high false reliability of the check nodes. Node-subset scheduling for the EMS (NS-EMS) decoding algorithm [22] uses the largest a posteriori probability among all tentatively estimated symbols as the metric to determine whether a variable node is reliable. Then, the check node is divided into two subsets—the processing subset and nonprocessing subset—according to the number of unreliable variable nodes connected to the check nodes. This method can effectively reduce computational complexity.In conclusion, among these scheduling strategies, the most important issue that has a significant impact on the performance and computational complexity of the decoding algorithm is to decide which check nodes should be updated. Therefore, we have carried out research on this issue, and the main contributions of this paper are twofold. First, a scheme called stability-based node-subset scheduling (SNS) based on node-subset (NS) scheduling for the EMS algorithm is proposed to improve the error-correcting performance of the NS-EMS algorithm. In this algorithm, a metric based on node stability is introduced to determine whether a variable node is reliable, and the threshold is heuristically defined to match the iteration and communication channels. Second, to further improve performance while still maintaining low computational complexity, we studied the behavior of the processing subset of error frames in the SNS-EMS algorithm and found abnormal stability in the processing subset of error frames, which would lead to the stagnation of the information transfer between check nodes and variable nodes. When the information transfer between these two nodes gradually stagnates, iterative decoding will no longer play its own role; thus, the errors in the estimated codeword will not be able to be corrected. Then, according to this property of error frames, stability-based node-subset scheduling with a subset-reset mechanism (RSNS) is proposed. The kernel of the RSNS-EMS algorithm is a form of sliding window detection for the processing subset. When it detects that there is such abnormal stability in the decoding process, the elements in the processing subset are reset so that all check nodes will update messages in the next iteration. Hence, abnormal stability will be alleviated, and performance will be improved. The simulation results demonstrate that the proposed algorithm can achieve better decoding performance at lower computational complexity compared to its counterpart.The rest of this paper is organized as follows. Section2 gives a brief introduction of the extended min-sum (EMS) algorithm and node-subset scheduling. Section 3 introduces the proposed algorithms. The performance evaluation of various algorithms is demonstrated and discussed in Section 4. Finally, Section 5 concludes the paper.


## 2. Preliminary Works

### 2.1. Normal Graph of Nonbinary LDPC Codes

LetFq be the finite field with qq=2ℓ elements. A nonbinary LDPC code Cq=n,k over Fq can be defined as the zero space of its parity check matrix H=hi,jm×n with hi,j∈Fq. Message vector v=v0,v1,…,vn−1 is a legal codeword of this NB-LDPC code if and only if it satisfies HvT=0. We define the two following index sets:(1)Ni=j:0≤j≤n−1,hi,j≠0,for each row i of H, and(2)ℳj=i:0≤i≤m−1,hi,j≠0,for each column j of H.For a given parity check matrix, we can use the normal graph shown in Figure1 to describe the decoding progress of NB-LDPC nodes. In a normal graph, edges represent variables, and vertices represent constraints. There are three kinds of vertices in a normal graph: (1) the left vertex is called the variable node, which represents a column of H; (2) the right vertex is called the check node, which represents a row of H; and (3) the middle vertex is called the intermediate node, which represents the nonzero elements hi,j≠0 in H, which bridge the check node and variable node; moreover, (4) all edges connected to the j−th variable node must take identical values, and all edges connected to the i−th check node must add up to zero.Figure 1
Normal graph for nonbinary LDPC codes.


### 2.2. M-EMS Algorithm

In this subsection, we will describe the specific steps of the M-EMS algorithm [5] combined with a normal graph, including initialization, message truncation, and the transfer and processing of information among variable nodes, check nodes and intermediate nodes.


#### 2.2.1. Initialization

Consider an NB-LDPC code,Cq=n,k, defined over Fq, and v=v0,v1,…,vn−1∈Fqn is a codeword, where any of the codeword symbols vi can be represented by a ℓ bit binary vector. For BPSK modulation, the codeword can be mapped to a bipolar sequence x=x00,x01,…,x0ℓ−1,…,xn−10,xn−11,…,xn−1ℓ−1, where xij=1−2vij for 0≤i≤n−1,0≤j≤l−1. Then, the sequence received over the AWGN channel is as follows:(3)y=y00,y01,…,y0ℓ−1,…,yn−10,yn−11,…,yn−1ℓ−1.For a given received sequencey, the channel initialization vector can be calculated in the following manner. First, we calculate the real log-domain message as follows:(4)RVjs=1ℓ∑k=0ℓ−1yik1−2sk,s∈Fq,where sk represents the k−th bit of a binary vector of finite field symbol s.LetΔ>0 and b>1 be the two parameters to be designed. Using these two parameters, we can clip and quantize the real log-domain message to an integer message according to the following equation:(5)LVj|⟶Vjs=−2b−1,ifRVjsΔ≤−2b−1,RVjsΔ,ifRVjsΔ<2b−1,2b−1,ifRVjsΔ≥2b−1,where s∈Fq and ⋅ denotes a rounding operation, that is, taking the nearest integer to it.


#### 2.2.2. Variable Node Update

In the iterative decoding process, variable nodeVj receives message LXijCi⟶Vj,s∈Fq passed by check node Ci connected thereto and updates the a posteriori message according to(6)LVjs=LVj|⟶Vjs+∑i∈MjLXijCi⟶Vjs,s∈Fq.The variable-to-check (V2C) message that needs to be passed to the check nodes is calculated as follows:(7)LXijVj⟶Cis=LVjs−LXijCi⟶Vjs,s∈Fq.


#### 2.2.3. Check Node Update

We can use the forward-backward algorithm [23] based on the trellis diagram [9] to represent message processing at check nodes.Letαt=αt0,αt1,…,αtq−1 and βt=βt0,βt1,…,βtq−1 denote the forward and backward recursion vectors, respectively.Setα0=0,−∞,…,−∞, and let dr denote the degree of the i−th check node. Then, for 0≤t<dr and ∀s∈Fq, compute the forward recursion vector and its truncated version:(8)αt+1s=maxz∈Fqαts−z+LXijVj⟶Ciz,s∈Fq.Setβdr=0,−∞,…,−∞, and then, for dr≥t>1 and ∀s∈Fq, recursively compute the backward recursion vectors and its truncated version:(9)βt−1s=maxz∈Fqβts−z+LXijVj⟶Ciz,s∈Fq.Next, for0≤t≤dr−1 and ∀s∈Fq, compute the extrinsic message:(10)LYijCi⟶Vjs=maxa∈Fqαta+βt+1s+a,s∈Fq.Finally, for0≤t≤dr−1, postprocess the extrinsic message:(11)LYijCi⟶Hijs=ξLYijCi⟶Vjs,ifLYijCi⟶Hijs≠−∞,0,others,where ξ is a scaling factor and ⋅ denotes a rounding operation.


#### 2.2.4. Node-Subset Scheduling

Letv^|v^jl∈Fq,j∈Ni be the set of estimated symbols of variable nodes which is connected to the i−th check node at the l−th iteration. The syndrome of this check node can be computed by(12)cil=∑j∈Nihi,j⋅v^jl.For a check node, if its syndrome is nonzero, then it means that the tentatively estimated symbols of variable nodes connected to the check node has not converged to the correct symbols. Therefore, these check nodes need to be updated in the next iteration. When the syndrome of a check node is zero, it does not always mean that the variable nodes connected to it have converged, it may be caused by the existence of two or more error symbols.To distinguish which kind of situation occurs when the syndrome is zero, node-subset (NS) scheduling [22] is based on the reliability of the variable node. If the reliability of the variable node is large enough, then the current decoding symbol is considered reliable. When the number of unreliable variable nodes connected to a check node with zero syndrome is less than two, the check node will be divided into a nonprocessing subset. These check nodes in the nonprocessing subset will not update their C2V messages in the next iteration.NS scheduling can be described as follows. Letfjl denote the mark of the j−th variable node at the l−th iteration. If the reliability of the current estimated symbol exceeds predefined threshold Tc, then this variable node is considered reliable and marked as 0; otherwise, it is marked as 1:(13)fjl=0,maxLVjlz≥Tc1,maxLVjlz<Tc,z∈Fq,where 0≤j≤n−1.LetM0 be the set of all check nodes and let Ml⊆M0 be the processing subset during the l−th decoding iteration. The check nodes contained in Ml can be determined by the following equation:(14)Ml=Ci|cil≠0∪Ci|∑j∈Nifjl≥2|cil=0,where 0≤i≤m−1 and cildenotes the syndrome of the i−th check node at the l−th iteration.


## 2.1. Normal Graph of Nonbinary LDPC Codes

LetFq be the finite field with qq=2ℓ elements. A nonbinary LDPC code Cq=n,k over Fq can be defined as the zero space of its parity check matrix H=hi,jm×n with hi,j∈Fq. Message vector v=v0,v1,…,vn−1 is a legal codeword of this NB-LDPC code if and only if it satisfies HvT=0. We define the two following index sets:(1)Ni=j:0≤j≤n−1,hi,j≠0,for each row i of H, and(2)ℳj=i:0≤i≤m−1,hi,j≠0,for each column j of H.For a given parity check matrix, we can use the normal graph shown in Figure1 to describe the decoding progress of NB-LDPC nodes. In a normal graph, edges represent variables, and vertices represent constraints. There are three kinds of vertices in a normal graph: (1) the left vertex is called the variable node, which represents a column of H; (2) the right vertex is called the check node, which represents a row of H; and (3) the middle vertex is called the intermediate node, which represents the nonzero elements hi,j≠0 in H, which bridge the check node and variable node; moreover, (4) all edges connected to the j−th variable node must take identical values, and all edges connected to the i−th check node must add up to zero.Figure 1
Normal graph for nonbinary LDPC codes.


## 2.2. M-EMS Algorithm

In this subsection, we will describe the specific steps of the M-EMS algorithm [5] combined with a normal graph, including initialization, message truncation, and the transfer and processing of information among variable nodes, check nodes and intermediate nodes.


### 2.2.1. Initialization

Consider an NB-LDPC code,Cq=n,k, defined over Fq, and v=v0,v1,…,vn−1∈Fqn is a codeword, where any of the codeword symbols vi can be represented by a ℓ bit binary vector. For BPSK modulation, the codeword can be mapped to a bipolar sequence x=x00,x01,…,x0ℓ−1,…,xn−10,xn−11,…,xn−1ℓ−1, where xij=1−2vij for 0≤i≤n−1,0≤j≤l−1. Then, the sequence received over the AWGN channel is as follows:(3)y=y00,y01,…,y0ℓ−1,…,yn−10,yn−11,…,yn−1ℓ−1.For a given received sequencey, the channel initialization vector can be calculated in the following manner. First, we calculate the real log-domain message as follows:(4)RVjs=1ℓ∑k=0ℓ−1yik1−2sk,s∈Fq,where sk represents the k−th bit of a binary vector of finite field symbol s.LetΔ>0 and b>1 be the two parameters to be designed. Using these two parameters, we can clip and quantize the real log-domain message to an integer message according to the following equation:(5)LVj|⟶Vjs=−2b−1,ifRVjsΔ≤−2b−1,RVjsΔ,ifRVjsΔ<2b−1,2b−1,ifRVjsΔ≥2b−1,where s∈Fq and ⋅ denotes a rounding operation, that is, taking the nearest integer to it.


### 2.2.2. Variable Node Update

In the iterative decoding process, variable nodeVj receives message LXijCi⟶Vj,s∈Fq passed by check node Ci connected thereto and updates the a posteriori message according to(6)LVjs=LVj|⟶Vjs+∑i∈MjLXijCi⟶Vjs,s∈Fq.The variable-to-check (V2C) message that needs to be passed to the check nodes is calculated as follows:(7)LXijVj⟶Cis=LVjs−LXijCi⟶Vjs,s∈Fq.


### 2.2.3. Check Node Update

We can use the forward-backward algorithm [23] based on the trellis diagram [9] to represent message processing at check nodes.Letαt=αt0,αt1,…,αtq−1 and βt=βt0,βt1,…,βtq−1 denote the forward and backward recursion vectors, respectively.Setα0=0,−∞,…,−∞, and let dr denote the degree of the i−th check node. Then, for 0≤t<dr and ∀s∈Fq, compute the forward recursion vector and its truncated version:(8)αt+1s=maxz∈Fqαts−z+LXijVj⟶Ciz,s∈Fq.Setβdr=0,−∞,…,−∞, and then, for dr≥t>1 and ∀s∈Fq, recursively compute the backward recursion vectors and its truncated version:(9)βt−1s=maxz∈Fqβts−z+LXijVj⟶Ciz,s∈Fq.Next, for0≤t≤dr−1 and ∀s∈Fq, compute the extrinsic message:(10)LYijCi⟶Vjs=maxa∈Fqαta+βt+1s+a,s∈Fq.Finally, for0≤t≤dr−1, postprocess the extrinsic message:(11)LYijCi⟶Hijs=ξLYijCi⟶Vjs,ifLYijCi⟶Hijs≠−∞,0,others,where ξ is a scaling factor and ⋅ denotes a rounding operation.


### 2.2.4. Node-Subset Scheduling

Letv^|v^jl∈Fq,j∈Ni be the set of estimated symbols of variable nodes which is connected to the i−th check node at the l−th iteration. The syndrome of this check node can be computed by(12)cil=∑j∈Nihi,j⋅v^jl.For a check node, if its syndrome is nonzero, then it means that the tentatively estimated symbols of variable nodes connected to the check node has not converged to the correct symbols. Therefore, these check nodes need to be updated in the next iteration. When the syndrome of a check node is zero, it does not always mean that the variable nodes connected to it have converged, it may be caused by the existence of two or more error symbols.To distinguish which kind of situation occurs when the syndrome is zero, node-subset (NS) scheduling [22] is based on the reliability of the variable node. If the reliability of the variable node is large enough, then the current decoding symbol is considered reliable. When the number of unreliable variable nodes connected to a check node with zero syndrome is less than two, the check node will be divided into a nonprocessing subset. These check nodes in the nonprocessing subset will not update their C2V messages in the next iteration.NS scheduling can be described as follows. Letfjl denote the mark of the j−th variable node at the l−th iteration. If the reliability of the current estimated symbol exceeds predefined threshold Tc, then this variable node is considered reliable and marked as 0; otherwise, it is marked as 1:(13)fjl=0,maxLVjlz≥Tc1,maxLVjlz<Tc,z∈Fq,where 0≤j≤n−1.LetM0 be the set of all check nodes and let Ml⊆M0 be the processing subset during the l−th decoding iteration. The check nodes contained in Ml can be determined by the following equation:(14)Ml=Ci|cil≠0∪Ci|∑j∈Nifjl≥2|cil=0,where 0≤i≤m−1 and cildenotes the syndrome of the i−th check node at the l−th iteration.


## 2.2.1. Initialization

Consider an NB-LDPC code,Cq=n,k, defined over Fq, and v=v0,v1,…,vn−1∈Fqn is a codeword, where any of the codeword symbols vi can be represented by a ℓ bit binary vector. For BPSK modulation, the codeword can be mapped to a bipolar sequence x=x00,x01,…,x0ℓ−1,…,xn−10,xn−11,…,xn−1ℓ−1, where xij=1−2vij for 0≤i≤n−1,0≤j≤l−1. Then, the sequence received over the AWGN channel is as follows:(3)y=y00,y01,…,y0ℓ−1,…,yn−10,yn−11,…,yn−1ℓ−1.For a given received sequencey, the channel initialization vector can be calculated in the following manner. First, we calculate the real log-domain message as follows:(4)RVjs=1ℓ∑k=0ℓ−1yik1−2sk,s∈Fq,where sk represents the k−th bit of a binary vector of finite field symbol s.LetΔ>0 and b>1 be the two parameters to be designed. Using these two parameters, we can clip and quantize the real log-domain message to an integer message according to the following equation:(5)LVj|⟶Vjs=−2b−1,ifRVjsΔ≤−2b−1,RVjsΔ,ifRVjsΔ<2b−1,2b−1,ifRVjsΔ≥2b−1,where s∈Fq and ⋅ denotes a rounding operation, that is, taking the nearest integer to it.


## 2.2.2. Variable Node Update

In the iterative decoding process, variable nodeVj receives message LXijCi⟶Vj,s∈Fq passed by check node Ci connected thereto and updates the a posteriori message according to(6)LVjs=LVj|⟶Vjs+∑i∈MjLXijCi⟶Vjs,s∈Fq.The variable-to-check (V2C) message that needs to be passed to the check nodes is calculated as follows:(7)LXijVj⟶Cis=LVjs−LXijCi⟶Vjs,s∈Fq.


## 2.2.3. Check Node Update

We can use the forward-backward algorithm [23] based on the trellis diagram [9] to represent message processing at check nodes.Letαt=αt0,αt1,…,αtq−1 and βt=βt0,βt1,…,βtq−1 denote the forward and backward recursion vectors, respectively.Setα0=0,−∞,…,−∞, and let dr denote the degree of the i−th check node. Then, for 0≤t<dr and ∀s∈Fq, compute the forward recursion vector and its truncated version:(8)αt+1s=maxz∈Fqαts−z+LXijVj⟶Ciz,s∈Fq.Setβdr=0,−∞,…,−∞, and then, for dr≥t>1 and ∀s∈Fq, recursively compute the backward recursion vectors and its truncated version:(9)βt−1s=maxz∈Fqβts−z+LXijVj⟶Ciz,s∈Fq.Next, for0≤t≤dr−1 and ∀s∈Fq, compute the extrinsic message:(10)LYijCi⟶Vjs=maxa∈Fqαta+βt+1s+a,s∈Fq.Finally, for0≤t≤dr−1, postprocess the extrinsic message:(11)LYijCi⟶Hijs=ξLYijCi⟶Vjs,ifLYijCi⟶Hijs≠−∞,0,others,where ξ is a scaling factor and ⋅ denotes a rounding operation.


## 2.2.4. Node-Subset Scheduling

Letv^|v^jl∈Fq,j∈Ni be the set of estimated symbols of variable nodes which is connected to the i−th check node at the l−th iteration. The syndrome of this check node can be computed by(12)cil=∑j∈Nihi,j⋅v^jl.For a check node, if its syndrome is nonzero, then it means that the tentatively estimated symbols of variable nodes connected to the check node has not converged to the correct symbols. Therefore, these check nodes need to be updated in the next iteration. When the syndrome of a check node is zero, it does not always mean that the variable nodes connected to it have converged, it may be caused by the existence of two or more error symbols.To distinguish which kind of situation occurs when the syndrome is zero, node-subset (NS) scheduling [22] is based on the reliability of the variable node. If the reliability of the variable node is large enough, then the current decoding symbol is considered reliable. When the number of unreliable variable nodes connected to a check node with zero syndrome is less than two, the check node will be divided into a nonprocessing subset. These check nodes in the nonprocessing subset will not update their C2V messages in the next iteration.NS scheduling can be described as follows. Letfjl denote the mark of the j−th variable node at the l−th iteration. If the reliability of the current estimated symbol exceeds predefined threshold Tc, then this variable node is considered reliable and marked as 0; otherwise, it is marked as 1:(13)fjl=0,maxLVjlz≥Tc1,maxLVjlz<Tc,z∈Fq,where 0≤j≤n−1.LetM0 be the set of all check nodes and let Ml⊆M0 be the processing subset during the l−th decoding iteration. The check nodes contained in Ml can be determined by the following equation:(14)Ml=Ci|cil≠0∪Ci|∑j∈Nifjl≥2|cil=0,where 0≤i≤m−1 and cildenotes the syndrome of the i−th check node at the l−th iteration.


## 3. Proposed Schemes

### 3.1. Metric for the Stability of Variable Nodes

In this subsection, we propose a metric based on the stability of the variable node to determine whether this node is reliable. First, we define stability metricdj as follows:(15)dj=maxLVjs−max∗LVjs,s∈Fq,where max∗ denotes the second-largest value of the log-domain message of LVjs.In the M-EMS algorithm [9], the value distribution of LVjs is affected by decoding iteration and the channel environment. The current decoding symbol of a variable node will often change between the first few finite field symbols with the highest reliability value. In other words, in theLVjs of a variable node, there will be several symbols with similar reliability values.As shown in Figure2, these two variable nodes have similar values ofmaxLVjs. However, there are several symbols with close values of LVjs in variable node (b), so the estimated symbol of this node is more likely to change compared to variable node (a). However, when using maxLVjs as the metric of reliability, both variable nodes should be considered reliable.Figure 2
Distribution ofLVjs of two variable nodes in the same frame decoding process at one iteration.
(a)(b)With the progress of decoding iteration, the variable nodes gradually converge to the correct symbol and no longer change, which means that they become stable. According to this property, when a variable node is not stable, then we consider it unreliable and in need of being updated in the next iteration.Therefore, we usedj as the metric of the reliability of a variable node. For a variable node, the larger its dj value is, the greater the difference in LVjs between the estimated decoding symbol and the second reliable symbol is; thus, it is less likely for the estimated symbol to change, which means that the variable node will become more stable.The method proposed in this paper for determining which variable nodes are stable is described as follows. Letmjl represent the mark of the j−th variable node at the l−th decoding iteration. If the dj value of this variable node exceeds a designed threshold, Td, then it is considered sufficiently reliable and marked as 0. Otherwise, the variable node is considered unreliable and marked as 1.(16)mjl=0,dj≥Td1,dj<Td,0≤j≤n−1.For thresholdTd, we present a method that can adaptively calculate the threshold based on decoding iteration and channel variation:(17)Td=δ⋅1n∑t=0n−1dt,where δ is a revision factor to be designed.Td depends on the dj value of all variable nodes in one iteration, so it does not need to be redetermined due to the variation in the parity check matrix. Moreover, as the iterative decoding process proceeds, an increasing number of variable nodes will converge to the correct symbol and become stable. Therefore, we use the statistic mean of dj for all variable nodes to determine this threshold, which can reflect the average stability level of the variable nodes in this iteration. The variable nodes with dj values under threshold Td will be considered unreliable. The improved stability-based node-subset schedule for the EMS algorithm (SNS-EMS) can be described by pseudocode, as shown in Algorithm 1.Algorithm 1: SNS-EMS.
(1)
for the given relevant parametersξ,b,Δ, initialize all LVj∣⟶Vjs, and set LXijCi⟶Vjs=0(2)
setitermax, and put all check nodes into Ml(3)
fori=0 to itermaxdo(4)
update the check nodes inMl, compute LXijCi⟶Vjs(5)
computeLVjs, and update V2C message LXijVj⟶Cis for all variable nodes(6)
forj=0 to j=n−1, do(7)
compute the estimated symbolv^j=argmaxs∈FqLVjs(8)
end for(9)
for all variable nodes, do(10)
markmjl according to equation (15)(11)
end for(12)
divide check nodes into two node subsets according to equation (17)(13)
ifHv^T=0 is not satisfied, then(14)
go back to line 3(15)
else return estimated codeword(16)
end if(17)
end for(18)
return estimated codeword


### 3.2. SNS Scheduling Combined with a Subset-Reset Mechanism

In the previous section, we described the proposed SNS-EMS algorithm. According to the simulation results, the SNS-EMS algorithm can make a good tradeoff between decoding performance and computational complexity. However, compared with the original M-EMS algorithm, its error correcting performance has a certain degree of degradation.Since SNS scheduling mainly affects which check node will update its C2V message in iterative decoding, we take the processing subset as the point of penetration and study the variation in the processing subset in the iterative decoding process of the SNS-EMS algorithm. Note that, in all experiments in this subsection, theC6488,44 NB-LDPC code of rate 0.5 is used, and the maximum number of iterations is set to 50.In the first experiment, we track the variation in the number of processing nodes for both converged frames and error frames at SNRs of 1.0 dB, 1.4 dB, 1.6 dB, 1.8 dB, 2.2 dB, and 2.4 dB, and their collected error frames total 50, 30, 30, 20, 10, and 10, respectively. Note that when a frame converges, we set the number of processing nodes in the subsequent iterations to 0.Figure3 shows the average number (over frames) of processing nodes in the iterative process of converged frames and error frames of the SNS-EMS algorithm under different SNRs. We can see that there is a clear difference in the variation curves between converged frames and error frames. The number of processing nodes of converged frames decreases greatly and always shows a downward trend until dropping to a very low level, which means that this frame has converged. Moreover, as the SNR continues to increase, the convergence speed also increases. When the SNR is greater than 1.8 dB, the number of processing nodes can be reduced to a very low level after the first several iterations.Figure 3
Average number of processing nodes of error frames and converged frames in the SNS-EMS algorithm with iterations under different SNRs.Conversely, the number of processing nodes in error frames exhibits a gentle downward trend. The number of processing nodes will no longer continue to decline after approximately 10 iterations but will remain at a high value. At this time, the number of processing nodes shows a stable state, where only a small fluctuation occurs.Based on the above experiment, we further studied the changes in elements in the processing subset of error frames. LetSc and Sl denote the processing subset of the current iteration and that of the next iteration, respectively, and let Si denote the intersection of Sc and Sl, which contains the same elements in these two sets. Consequently, the numbers of elements in Si and Sl are ui and ul, respectively. We use the ratio of ui to ul as the metric, which is referred to as repeatability ratio ρR, to intuitively reflect the changes in the elements in the processing node subset. When ρR is close to 1, it means the elements in the processing subset are almost unchanged in two successive iterations.(18)ρR=uiul.In this experiment, we track the variation in the repeatability ratio at SNRs of 1.0 dB, 1.4 dB, 1.6 dB, 1.8 dB, 2.2 dB, and 2.4 dB, and their collected error frames total 50, 30, 30, 20, 10, and 10, respectively.As shown in Figure4, all the ρR values of the processing subset of error frames under different SNRs are at a very high level, and as the iteration continues, the ratio gradually increases. After 20 iterations, ρR under all SNRs is higher than 0.98, which means that the elements in the processing subset will hardly change in the subsequent iterations. These results combined with those in Figure 3 show that when the number of processing nodes of the error frames tends to be stable, almost the same check nodes update their C2V messages. This situation continues until the decoder reaches the maximum number of iterations and stops decoding, but the estimated code has not converged.Figure 4
Average variation in theρR values of error frames in SNS-EMS algorithm at different SNRs.According to the above experiments, we speculate that, after dividing the node subset, some check nodes stop updating their C2V messages. Then, some of the V2C messages of variable nodes cannot be updated correspondingly, according to equations (6) and (7). As a result, LVjs will no longer be updated, which is used to tentatively decide the estimated symbols for variable nodes. Therefore, even though there are many check nodes for C2V message updating in the processing node subset, the errors in the estimated codeword still cannot be corrected.To verify the correctness of the above speculations, we conduct research and analysis on the vectorLVjs of variable nodes during the iteration process. Since the calculation of these vectors is related to both C2V and V2C messages, the changes in this message can reflect the changes in these two messages. We start by defining the vector HVjls as follows:(19)HVjls=LVjls−LVjl−1s,s∈Fq,where j and l are the j−th variable node and the l−th iteration, respectively, and ⋅ is the absolute value. The elements in HVjls denote the magnitude of log-domain message LVjls for each finite field symbol between two consecutive iterations.Then, for each variable node, a metric,evjl, is stored to trace how many finite-field symbols in HVjls vary more than variation threshold Tvar. evjl can approximately reflect the change in vector LVjls in the iteration process: if the value of evjl is larger, then there are a greater number of symbols whose log-domain messages have changed in LVjls.We take the arithmetic mean of theevjl values of all the variable nodes in the l−th iteration as φl and use it to show the overall situation of LVjls for all variable nodes as decoding iterations progress. It is worth noting that there are two situations where LVjls will not change: (1) when the estimated codeword converges and the decoder stops decoding, the calculation of LVjls will stop accordingly, and (2) when C2V messages stop being updated, the LVjls value will not change. To distinguish these two cases, we set the LVjls values of converged frames to q after they have converged, and q denotes the order of finite field Fq.The experimental results are shown in Figure5, where Tvar=3. It is worth noting that the φl value of error frames gradually decreases as the number of iterations increases, especially after 20 iterations, and the value of φl remains at a very low level under all SNRs. This finding means that, during these iterations, LVjs hardly changes. Combined with the above experiments, we know that after “abnormal” stability appears in the processing subset, although there are still a large number of check nodes updating their C2V messages in the subsequent iterative decoding, it does not help with error correction. Since the information transfer between check nodes and variable nodes no longer generates new correction information, LVjs, which is used for deciding the estimated symbol of variable nodes, hardly changes. Therefore, the errors in the estimated codeword cannot be corrected, and thus, it will fail to converge to the correct codeword.Figure 5
Variation in theφl values of error frames and converged frames in the SNS-EMS algorithm with iteration processing at different SNRs.The proposed stability-based node-subset scheduling with a subset-reset mechanism for EMS (RSNS-EMS) algorithm has been developed based on this “abnormal” stability of the processing subset. The main idea of this method is to distinguish the frames with this property during the decoding process. Then, the elements in the processing subset are reset so that all check nodes will update their C2V messages in the next iteration. When new C2V messages are updated, it is expected that the abnormal stability of the processing subset will be alleviated and that the message transfer between the two nodes will be accelerated. Therefore, the estimated codeword can converge, thereby mitigating the degradation of the error-correcting performance of the SNS-EMS algorithm. Note that since only a small number of error frames will be reset and the FER will gradually decrease as the number of SNRs increases, we can expect that this method will not significantly increase overall computational complexity.To implement the previously described method, we design a sliding window detection mechanism. First, because in the first few iterations the number of processing nodes for both error frames and converged frames exhibits a downward trend, we set a threshold of iterationTiter, and the sliding window detection mechanism will only be activated when the number of iterations is greater than Titer. To trace the abnormal stability behavior of the decoding frame, a sliding window mechanism of width ω can be defined as follows: let ni denote the number of processing nodes in each iteration, where i=1,2,…,maxiter. We collect ni for the last ω iterations and define vector dω as follows:(20)dω=nc−ω−nc−ω−1,nc−ω+1−nc−ω,…,nc−nc−1,where nc denotes the number of processing nodes for the current iteration. The elements in dω represent the difference in ni between two consecutive iterations.Finally, we calculate the arithmetic meanD of the value in dω, which denotes the average value of the difference in the number of processing check nodes within ω successive iterations:(21)D=1ω∑k=0ωnc−k−nc−k−1.We use it as the measurement to determine whether the processing subset has abnormal stability. When the value ofD is less than the designed variation tolerance μ, the processing subset of this frame has abnormal stability. Then, the elements of the processing subset are reset, and all check nodes update their C2V messages in the next iteration. It should be noted that the interval within the resetting of these two subsets needs to be greater than window width ω. The proposed RSNS-EMS algorithm can be described by pseudocode, as shown in Algorithm 2.Algorithm 2: RSNS-EMS.
(1)
for the given relevant parametersξ,b,Δ, initialize all LVj∣⟶Vjs, and set LXijCi⟶Vjs=0(2)
setitermax, and put all check nodes into Ml(3)
fori=0 to itermaxdo(4)
update the check nodes inMl, and compute LXijCi⟶Vjs(5)
compute theLVjs, and update V2C message LXijVj⟶Cis(6)
forj=0 to j=n−1, do(7)
compute the estimated symbolv^j=argmaxs∈FqLVjs(8)
end for(9)
for all variable nodes, do(10)
markmjl according to equation (15)(11)
end for(12)
divide check nodes into two node subsets according to equation (15)(13)
collect theni values of the last ω iterations(14)
if current iteration Tc>Titer, then(15)
compute thedω and D(16)
ifD<μ, then(17)
reset the processing subset, and put all check nodes intoMl(18)
end if(19)
end if(20)
ifHv^T=0 is not satisfied, then(21)
go back to line 4(22)
else return estimated codeword(23)
end if(24)
end for(25)
return estimated codeword


## 3.1. Metric for the Stability of Variable Nodes

In this subsection, we propose a metric based on the stability of the variable node to determine whether this node is reliable. First, we define stability metricdj as follows:(15)dj=maxLVjs−max∗LVjs,s∈Fq,where max∗ denotes the second-largest value of the log-domain message of LVjs.In the M-EMS algorithm [9], the value distribution of LVjs is affected by decoding iteration and the channel environment. The current decoding symbol of a variable node will often change between the first few finite field symbols with the highest reliability value. In other words, in theLVjs of a variable node, there will be several symbols with similar reliability values.As shown in Figure2, these two variable nodes have similar values ofmaxLVjs. However, there are several symbols with close values of LVjs in variable node (b), so the estimated symbol of this node is more likely to change compared to variable node (a). However, when using maxLVjs as the metric of reliability, both variable nodes should be considered reliable.Figure 2
Distribution ofLVjs of two variable nodes in the same frame decoding process at one iteration.
(a)(b)With the progress of decoding iteration, the variable nodes gradually converge to the correct symbol and no longer change, which means that they become stable. According to this property, when a variable node is not stable, then we consider it unreliable and in need of being updated in the next iteration.Therefore, we usedj as the metric of the reliability of a variable node. For a variable node, the larger its dj value is, the greater the difference in LVjs between the estimated decoding symbol and the second reliable symbol is; thus, it is less likely for the estimated symbol to change, which means that the variable node will become more stable.The method proposed in this paper for determining which variable nodes are stable is described as follows. Letmjl represent the mark of the j−th variable node at the l−th decoding iteration. If the dj value of this variable node exceeds a designed threshold, Td, then it is considered sufficiently reliable and marked as 0. Otherwise, the variable node is considered unreliable and marked as 1.(16)mjl=0,dj≥Td1,dj<Td,0≤j≤n−1.For thresholdTd, we present a method that can adaptively calculate the threshold based on decoding iteration and channel variation:(17)Td=δ⋅1n∑t=0n−1dt,where δ is a revision factor to be designed.Td depends on the dj value of all variable nodes in one iteration, so it does not need to be redetermined due to the variation in the parity check matrix. Moreover, as the iterative decoding process proceeds, an increasing number of variable nodes will converge to the correct symbol and become stable. Therefore, we use the statistic mean of dj for all variable nodes to determine this threshold, which can reflect the average stability level of the variable nodes in this iteration. The variable nodes with dj values under threshold Td will be considered unreliable. The improved stability-based node-subset schedule for the EMS algorithm (SNS-EMS) can be described by pseudocode, as shown in Algorithm 1.Algorithm 1: SNS-EMS.
(1)
for the given relevant parametersξ,b,Δ, initialize all LVj∣⟶Vjs, and set LXijCi⟶Vjs=0(2)
setitermax, and put all check nodes into Ml(3)
fori=0 to itermaxdo(4)
update the check nodes inMl, compute LXijCi⟶Vjs(5)
computeLVjs, and update V2C message LXijVj⟶Cis for all variable nodes(6)
forj=0 to j=n−1, do(7)
compute the estimated symbolv^j=argmaxs∈FqLVjs(8)
end for(9)
for all variable nodes, do(10)
markmjl according to equation (15)(11)
end for(12)
divide check nodes into two node subsets according to equation (17)(13)
ifHv^T=0 is not satisfied, then(14)
go back to line 3(15)
else return estimated codeword(16)
end if(17)
end for(18)
return estimated codeword


## 3.2. SNS Scheduling Combined with a Subset-Reset Mechanism

In the previous section, we described the proposed SNS-EMS algorithm. According to the simulation results, the SNS-EMS algorithm can make a good tradeoff between decoding performance and computational complexity. However, compared with the original M-EMS algorithm, its error correcting performance has a certain degree of degradation.Since SNS scheduling mainly affects which check node will update its C2V message in iterative decoding, we take the processing subset as the point of penetration and study the variation in the processing subset in the iterative decoding process of the SNS-EMS algorithm. Note that, in all experiments in this subsection, theC6488,44 NB-LDPC code of rate 0.5 is used, and the maximum number of iterations is set to 50.In the first experiment, we track the variation in the number of processing nodes for both converged frames and error frames at SNRs of 1.0 dB, 1.4 dB, 1.6 dB, 1.8 dB, 2.2 dB, and 2.4 dB, and their collected error frames total 50, 30, 30, 20, 10, and 10, respectively. Note that when a frame converges, we set the number of processing nodes in the subsequent iterations to 0.Figure3 shows the average number (over frames) of processing nodes in the iterative process of converged frames and error frames of the SNS-EMS algorithm under different SNRs. We can see that there is a clear difference in the variation curves between converged frames and error frames. The number of processing nodes of converged frames decreases greatly and always shows a downward trend until dropping to a very low level, which means that this frame has converged. Moreover, as the SNR continues to increase, the convergence speed also increases. When the SNR is greater than 1.8 dB, the number of processing nodes can be reduced to a very low level after the first several iterations.Figure 3
Average number of processing nodes of error frames and converged frames in the SNS-EMS algorithm with iterations under different SNRs.Conversely, the number of processing nodes in error frames exhibits a gentle downward trend. The number of processing nodes will no longer continue to decline after approximately 10 iterations but will remain at a high value. At this time, the number of processing nodes shows a stable state, where only a small fluctuation occurs.Based on the above experiment, we further studied the changes in elements in the processing subset of error frames. LetSc and Sl denote the processing subset of the current iteration and that of the next iteration, respectively, and let Si denote the intersection of Sc and Sl, which contains the same elements in these two sets. Consequently, the numbers of elements in Si and Sl are ui and ul, respectively. We use the ratio of ui to ul as the metric, which is referred to as repeatability ratio ρR, to intuitively reflect the changes in the elements in the processing node subset. When ρR is close to 1, it means the elements in the processing subset are almost unchanged in two successive iterations.(18)ρR=uiul.In this experiment, we track the variation in the repeatability ratio at SNRs of 1.0 dB, 1.4 dB, 1.6 dB, 1.8 dB, 2.2 dB, and 2.4 dB, and their collected error frames total 50, 30, 30, 20, 10, and 10, respectively.As shown in Figure4, all the ρR values of the processing subset of error frames under different SNRs are at a very high level, and as the iteration continues, the ratio gradually increases. After 20 iterations, ρR under all SNRs is higher than 0.98, which means that the elements in the processing subset will hardly change in the subsequent iterations. These results combined with those in Figure 3 show that when the number of processing nodes of the error frames tends to be stable, almost the same check nodes update their C2V messages. This situation continues until the decoder reaches the maximum number of iterations and stops decoding, but the estimated code has not converged.Figure 4
Average variation in theρR values of error frames in SNS-EMS algorithm at different SNRs.According to the above experiments, we speculate that, after dividing the node subset, some check nodes stop updating their C2V messages. Then, some of the V2C messages of variable nodes cannot be updated correspondingly, according to equations (6) and (7). As a result, LVjs will no longer be updated, which is used to tentatively decide the estimated symbols for variable nodes. Therefore, even though there are many check nodes for C2V message updating in the processing node subset, the errors in the estimated codeword still cannot be corrected.To verify the correctness of the above speculations, we conduct research and analysis on the vectorLVjs of variable nodes during the iteration process. Since the calculation of these vectors is related to both C2V and V2C messages, the changes in this message can reflect the changes in these two messages. We start by defining the vector HVjls as follows:(19)HVjls=LVjls−LVjl−1s,s∈Fq,where j and l are the j−th variable node and the l−th iteration, respectively, and ⋅ is the absolute value. The elements in HVjls denote the magnitude of log-domain message LVjls for each finite field symbol between two consecutive iterations.Then, for each variable node, a metric,evjl, is stored to trace how many finite-field symbols in HVjls vary more than variation threshold Tvar. evjl can approximately reflect the change in vector LVjls in the iteration process: if the value of evjl is larger, then there are a greater number of symbols whose log-domain messages have changed in LVjls.We take the arithmetic mean of theevjl values of all the variable nodes in the l−th iteration as φl and use it to show the overall situation of LVjls for all variable nodes as decoding iterations progress. It is worth noting that there are two situations where LVjls will not change: (1) when the estimated codeword converges and the decoder stops decoding, the calculation of LVjls will stop accordingly, and (2) when C2V messages stop being updated, the LVjls value will not change. To distinguish these two cases, we set the LVjls values of converged frames to q after they have converged, and q denotes the order of finite field Fq.The experimental results are shown in Figure5, where Tvar=3. It is worth noting that the φl value of error frames gradually decreases as the number of iterations increases, especially after 20 iterations, and the value of φl remains at a very low level under all SNRs. This finding means that, during these iterations, LVjs hardly changes. Combined with the above experiments, we know that after “abnormal” stability appears in the processing subset, although there are still a large number of check nodes updating their C2V messages in the subsequent iterative decoding, it does not help with error correction. Since the information transfer between check nodes and variable nodes no longer generates new correction information, LVjs, which is used for deciding the estimated symbol of variable nodes, hardly changes. Therefore, the errors in the estimated codeword cannot be corrected, and thus, it will fail to converge to the correct codeword.Figure 5
Variation in theφl values of error frames and converged frames in the SNS-EMS algorithm with iteration processing at different SNRs.The proposed stability-based node-subset scheduling with a subset-reset mechanism for EMS (RSNS-EMS) algorithm has been developed based on this “abnormal” stability of the processing subset. The main idea of this method is to distinguish the frames with this property during the decoding process. Then, the elements in the processing subset are reset so that all check nodes will update their C2V messages in the next iteration. When new C2V messages are updated, it is expected that the abnormal stability of the processing subset will be alleviated and that the message transfer between the two nodes will be accelerated. Therefore, the estimated codeword can converge, thereby mitigating the degradation of the error-correcting performance of the SNS-EMS algorithm. Note that since only a small number of error frames will be reset and the FER will gradually decrease as the number of SNRs increases, we can expect that this method will not significantly increase overall computational complexity.To implement the previously described method, we design a sliding window detection mechanism. First, because in the first few iterations the number of processing nodes for both error frames and converged frames exhibits a downward trend, we set a threshold of iterationTiter, and the sliding window detection mechanism will only be activated when the number of iterations is greater than Titer. To trace the abnormal stability behavior of the decoding frame, a sliding window mechanism of width ω can be defined as follows: let ni denote the number of processing nodes in each iteration, where i=1,2,…,maxiter. We collect ni for the last ω iterations and define vector dω as follows:(20)dω=nc−ω−nc−ω−1,nc−ω+1−nc−ω,…,nc−nc−1,where nc denotes the number of processing nodes for the current iteration. The elements in dω represent the difference in ni between two consecutive iterations.Finally, we calculate the arithmetic meanD of the value in dω, which denotes the average value of the difference in the number of processing check nodes within ω successive iterations:(21)D=1ω∑k=0ωnc−k−nc−k−1.We use it as the measurement to determine whether the processing subset has abnormal stability. When the value ofD is less than the designed variation tolerance μ, the processing subset of this frame has abnormal stability. Then, the elements of the processing subset are reset, and all check nodes update their C2V messages in the next iteration. It should be noted that the interval within the resetting of these two subsets needs to be greater than window width ω. The proposed RSNS-EMS algorithm can be described by pseudocode, as shown in Algorithm 2.Algorithm 2: RSNS-EMS.
(1)
for the given relevant parametersξ,b,Δ, initialize all LVj∣⟶Vjs, and set LXijCi⟶Vjs=0(2)
setitermax, and put all check nodes into Ml(3)
fori=0 to itermaxdo(4)
update the check nodes inMl, and compute LXijCi⟶Vjs(5)
compute theLVjs, and update V2C message LXijVj⟶Cis(6)
forj=0 to j=n−1, do(7)
compute the estimated symbolv^j=argmaxs∈FqLVjs(8)
end for(9)
for all variable nodes, do(10)
markmjl according to equation (15)(11)
end for(12)
divide check nodes into two node subsets according to equation (15)(13)
collect theni values of the last ω iterations(14)
if current iteration Tc>Titer, then(15)
compute thedω and D(16)
ifD<μ, then(17)
reset the processing subset, and put all check nodes intoMl(18)
end if(19)
end if(20)
ifHv^T=0 is not satisfied, then(21)
go back to line 4(22)
else return estimated codeword(23)
end if(24)
end for(25)
return estimated codeword


## 4. Performance Evaluation

In this section, we will evaluate the performances of the proposed SNS-EMS and RSNS-EMS algorithms in terms of computational complexity and error-correcting performance through a large number of simulations and compare them with other algorithms, including the QSPA [7], M-EMS [7], SU-EMS [21], and NS-EMS [22] algorithms. In this evaluation, to verify the reliability of the proposed method, we select three NB-LDPC codes with different finite fields and construction methods.The first code,C6488,44, is a regular NB-LDPC code over F64 with a rate of 0.5, which has been designed using optimized rows and optimized short loops according to [24, 25]. The second code, C32200,100, is a regular NB-LDPC code over F32 and it has been constructed by using the progress-edge-grow (PEG) algorithm [26]. The third code, C25672,36, is a regular NB-LDPC code over F256 with a rate of 0.5, which has been constructed using the same method as the first code. All the simulations are performed at BPSK modulation over the AWGN channel. The maximum number of iterations is set to 30.


### 4.1. Complexity Analysis

In this subsection, we will analyze the complexity of the proposed algorithms. The computational complexity of the decoding algorithm of NB-LDPC codes is mainly concentrated on the part of check node update. The check node update can use forward-backward algorithms [23] on the trellis, so computational complexity is determined by the total number of live branches in the trellis. Thus, we will count the total number of live branches of different algorithms on the trellis. Conversely, different decoding algorithms may have different convergence speeds. Therefore, we will find the statistical mean (averaging over frames) of the total number of live branches involved in all the iterations for the decoding of one frame. Because other algorithms are used to reduce the computational complexity of the QSPA, we take the following complexity ratio as the measurement of complexity:(22)ρ=total number of live branches of a given algorithmtotal number of live branches of the QSPA,which can approximately reflect the reduction of complexity compared to the QSPA.In addition, the abovementioned complexity ratio reflects the complexity of each algorithm approximately but intuitively. We think that it is necessary to compare the computational complexity of the M-EMS algorithm and the QSPA more accurately, since all selected scheduling strategies are used in the M-EMS algorithm. The computation of messages in check node updates can use the method proposed in [27]. According to this paper, the complexity of check node updates in one iteration varies on the order of OMdcnmlog2nm and with nm≪q, which is a great computational reduction compared to the QSPA of OMdcq2.Regarding the introduction of various mechanisms for reducing complexity in various selected scheduling strategies, some extra operations have also been introduced. Thus, we will also analyze these newly introduced operations. According to the relevant steps of these algorithms, we divide the operations into five categories: finite-field addition (FA), real addition (RA), real multiplication (RM), comparison (CM), and max operation (Max).The extra operations introduced by different algorithms compared to the M-EMS algorithm in one iteration are shown in Table1. For the NS-EMS algorithm, the newly introduced operation determines whether the variable node is reliable and divides the node subsets. These two steps require drM RAs, M+N CMs, and N Maxs. Compared to the NS-EMS algorithm, the SNS-EMS algorithm additionally needs to compute threshold Td and find the estimated symbol with the second-largest log-domain message in LVjs. Thus, the extra operations required by the SNS-EMS algorithm are drM+2N RAs, 2 RMs, M+N CMs, and N Maxs. Due to the introduction of abnormal stability detection in the RSNS-EMS algorithm, the required extra operations are drM+2N+2ω RAs, 3 RMs, M+N CMs, and N Maxs. The SU-EMS algorithm needs to find the difference in each finite-field symbol in LVjs of two consecutive iterations and determine whether it is greater than threshold ε. Therefore, the extra operations introduced by the SU-EMS algorithm are drM+Nq RAs and M+Nq+1 CMs.Table 1
Analysis of computational complexity per iteration for various algorithms.
SU-EMS [21]NS-EMS [22]SNS-EMS (ours)RSNS-EMS (ours)Reduced operationsFA00003drσq2RAdrM+NqdrMdrM+2NdrM+2N+2ω3drσq2RM00230CMM+Nq+1M+NM+NM+N0Max00NN3drσq2Since these scheduling strategies can reduce the number of check nodes updated in one iteration, we also list the reduction in complexity in Table1. Because in each iteration of the QSPA and the M-EMS algorithm the number of processing check nodes is a fixed value M, and the calculation for the C2V messages of each iteration requires 3drσq2 FAs, 3drσq2 Ras, and 3drσq2 Maxs in forward-backward recursion. All algorithms listed in Table 1 reduce the complexity by reducing the number of processing check nodes in one iteration. Therefore, in each iteration, the reduced operations are the corresponding operations of these nonprocessing check nodes. Let σ denote the number of nonprocessing check nodes in one iteration for various algorithms. Then, the reduction in complexity is 3drrσq2 FAs, RAs, and Maxs.We can notice that the additional complexity is linear and that the reduced complexity is proportional to the square of finite-field orderq. With regard to the case of short and medium code lengths, where NB-LDPC codes have more advantages compared to binary LDPC codes, the additional operations caused by the introduction of a new mechanism are much smaller than the reduced computational complexity.


### 4.2. Simulation Results

Error-correcting performance is measured by the bit error rate (BER) and frame error rate (FER). First, we consider a regular NB-LDPC codeC6488,44 that has been designed using optimized rows and optimized short loops according to [24, 25]. The parity-check matrix of this code has row weight dr=4 and column weight dc=2. The parameters of the implemented algorithms are listed below.(1) For the M-EMS algorithm,M=32; for the NS-EMS algorithm, M=32,Tc=220; for the SU-EMS algorithm,M=32,ω=3,ε=5; for the SNS-EMS algorithm, M=32,δ=1; and for the RSNS-EMS algorithm, M=32,δ=1,Titer=10,ω=4,μ=3. (2) For all algorithms, the scaling factor ξ=0.9 and b=8,Δ=1/128.The simulation results are shown in Figures6 and 7. Figure 6 shows the BER and FER performance of various algorithms, where the dashed lines represent the FER, and the solid lines represent the BER. Figure 7 shows the complexity ratio of various algorithms compared to the QSPA, and the subwindow shows the complexity ratio compared to the M-EMS algorithm.Figure 6
Decoding performance of BER and FER versusEb/N0 of various algorithms for NB-LDPC code C6488,44.Figure 7
Complexity ratio of various algorithms compared to the QSPA versusEb/N0 for NB-LDPC code C6488,44.The optimal QSPA has the best error-correcting performance, and the EMS algorithm has the second-best performance. We can see that the computational complexity of the other algorithms is much lower than that of the QSPA, almost reducing the complexity by more than 70%. Due to the introduction of the truncation rule, the M-EMS algorithm reduces complexity and brings about some performance degradation. For the proposed algorithms, we can see that there is negligible (nearly no) performance degradation between the proposed RSNS-EMS algorithm and the original M-EMS algorithm. Moreover, it is obvious that the proposed RSNS-EMS algorithm can outperform the NS-EMS and SNS-EMS algorithms. When the SNR is less than 1.8 dB, the complexity of the RSNS-EMS algorithm is slightly higher than that of the SNS-EMS algorithm, and when the SNR is greater than 1.8 dB, the complexity of the RSNS-EMS algorithm is even lower than that of the SNS-EMS algorithm. Compared to the SU-EMS algorithm, the error-correcting performance of the proposed RSNS-EMS algorithm is basically the same, and the complexity of the RSNS-EMS algorithm is much lower than that of the SU-EMS algorithm, which increases with increasing SNR and is basically the same as that of the M-EMS algorithm when the SNR is greater than 2.0 dB.Second, we consider a regular NB-LDPC code,C32200,100. The parity-check matrix of this code has row weight dr=4 and column weight dc=2. The parameters of the implemented algorithms are listed below.(1) For the M-EMS algorithm,M=16; for the NS-EMS algorithm, M=16,Tc=230; for the SU-EMS algorithm, M=16,ω=3,ε=5; for the SNS-EMS algorithm, M=16,δ=1; and for the RSNS-EMS algorithm, M=16,δ=1,Titer=10,ω=4,μ=3. (2) For all algorithms, the scaling factor ξ=0.9 and b=8,Δ=1/128.The simulation results are shown in Figures8 and 9. It can be observed that the QSPA has the best error-correcting performance among all algorithms, but it also has the highest computational complexity. The performance of the EMS algorithm is second-best, and it can reduce complexity by nearly 70% with approximately 0.2 dB degradation. Although the proposed SNS-EMS algorithm has the overall lowest complexity, its performance has a certain degree of degradation compared to the M-EMS algorithm. The proposed RSNS-EMS algorithm can outperform the NS-EMS and NS-EMS algorithms; it has negligible (nearly no BER) degradation with an approximately 25% reduction in complexity compared to the M-EMS algorithm. It is worth noting that the complexity ratio of the SU-EMS algorithm starts from 0.7 and increases to be almost equal to that of the M-EMS algorithm with increasing SNR. Therefore, compared to the SU-EMS algorithm, the RSNS scheduling algorithm proposed in this paper has almost the same error-correcting performance but has lower computational complexity.Figure 8
Decoding performance of BER and FER versusEb/N0 of various algorithms for NB-LDPC code C32200,100.Figure 9
Complexity ratio of various algorithms compared to the QSPA versusEb/N0 for NB-LDPC code C32200,100.Finally, we consider a regular NB-LDPC code,C25672,36. The parity-check matrix of this code has row weight dr=4 and column weight dc=2. The parameters of the implemented algorithms are listed below.(1) For the M-EMS algorithm,M=128; for the NS-EMS algorithm, M=128,Tc=400; for the SU-EMS algorithm, M=128,ω=2,ε=20; for the SNS-EMS algorithm, M=128,δ=1; and for the RSNS-EMS algorithm, M=128,δ=0.9,Titer=10,ω=5,μ=4. (2) For all algorithms, the scaling factor ξ=0.9 and b=8,Δ=1/256.The simulation results are shown in Figures10 and 11. It can be observed that, in these three simulations, the complexity ratio of SU-EMS algorithm increases with increasing SNR, and it is almost the same as the M-EMS algorithm at high SNR. We believe the reason is that the method used by the SU-EMS algorithm to decide whether a variable node is reliable is tracing the message evolution over iterations, where the variable node will be considered reliable only if its outgoing message is stable in ω iterations. The convergence speed of decoder is accelerated under high SNR, and it is possible that all variable nodes have already converged before being considered reliable. Therefore, the SU-EMS algorithm and M-EMS algorithm are basically the same in this situation, so there will be similar computational complexity. Besides, compared with Figures 8 and 9, we set Tc=400 in this simulation, which makes the complexity ratio of NS-EMS algorithm higher than those of the proposed algorithms. In this case, the correcting performance of NS-EMS algorithm is better than that of the SNS-EMS algorithm and it is close to that of the RSNS-EMS algorithm in low-to-moderate SNR, but it still has a certain degradation with the proposed algorithms in moderate-to-high SNR. Conversely, the proposed algorithms, especially the RSNS-EMS algorithm, can reduce the complexity by nearly 25% while keeping the error-correcting performance almost unchanged compared to the original M-EMS algorithm.Figure 10
Decoding performance of BER and FER versusEb/N0 of various algorithms for NB-LDPC code C25672,36.Figure 11
Complexity ratio of various algorithms compared to the QSPA versusEb/N0 for NB-LDPC code C25672,36.


## 4.1. Complexity Analysis

In this subsection, we will analyze the complexity of the proposed algorithms. The computational complexity of the decoding algorithm of NB-LDPC codes is mainly concentrated on the part of check node update. The check node update can use forward-backward algorithms [23] on the trellis, so computational complexity is determined by the total number of live branches in the trellis. Thus, we will count the total number of live branches of different algorithms on the trellis. Conversely, different decoding algorithms may have different convergence speeds. Therefore, we will find the statistical mean (averaging over frames) of the total number of live branches involved in all the iterations for the decoding of one frame. Because other algorithms are used to reduce the computational complexity of the QSPA, we take the following complexity ratio as the measurement of complexity:(22)ρ=total number of live branches of a given algorithmtotal number of live branches of the QSPA,which can approximately reflect the reduction of complexity compared to the QSPA.In addition, the abovementioned complexity ratio reflects the complexity of each algorithm approximately but intuitively. We think that it is necessary to compare the computational complexity of the M-EMS algorithm and the QSPA more accurately, since all selected scheduling strategies are used in the M-EMS algorithm. The computation of messages in check node updates can use the method proposed in [27]. According to this paper, the complexity of check node updates in one iteration varies on the order of OMdcnmlog2nm and with nm≪q, which is a great computational reduction compared to the QSPA of OMdcq2.Regarding the introduction of various mechanisms for reducing complexity in various selected scheduling strategies, some extra operations have also been introduced. Thus, we will also analyze these newly introduced operations. According to the relevant steps of these algorithms, we divide the operations into five categories: finite-field addition (FA), real addition (RA), real multiplication (RM), comparison (CM), and max operation (Max).The extra operations introduced by different algorithms compared to the M-EMS algorithm in one iteration are shown in Table1. For the NS-EMS algorithm, the newly introduced operation determines whether the variable node is reliable and divides the node subsets. These two steps require drM RAs, M+N CMs, and N Maxs. Compared to the NS-EMS algorithm, the SNS-EMS algorithm additionally needs to compute threshold Td and find the estimated symbol with the second-largest log-domain message in LVjs. Thus, the extra operations required by the SNS-EMS algorithm are drM+2N RAs, 2 RMs, M+N CMs, and N Maxs. Due to the introduction of abnormal stability detection in the RSNS-EMS algorithm, the required extra operations are drM+2N+2ω RAs, 3 RMs, M+N CMs, and N Maxs. The SU-EMS algorithm needs to find the difference in each finite-field symbol in LVjs of two consecutive iterations and determine whether it is greater than threshold ε. Therefore, the extra operations introduced by the SU-EMS algorithm are drM+Nq RAs and M+Nq+1 CMs.Table 1
Analysis of computational complexity per iteration for various algorithms.
SU-EMS [21]NS-EMS [22]SNS-EMS (ours)RSNS-EMS (ours)Reduced operationsFA00003drσq2RAdrM+NqdrMdrM+2NdrM+2N+2ω3drσq2RM00230CMM+Nq+1M+NM+NM+N0Max00NN3drσq2Since these scheduling strategies can reduce the number of check nodes updated in one iteration, we also list the reduction in complexity in Table1. Because in each iteration of the QSPA and the M-EMS algorithm the number of processing check nodes is a fixed value M, and the calculation for the C2V messages of each iteration requires 3drσq2 FAs, 3drσq2 Ras, and 3drσq2 Maxs in forward-backward recursion. All algorithms listed in Table 1 reduce the complexity by reducing the number of processing check nodes in one iteration. Therefore, in each iteration, the reduced operations are the corresponding operations of these nonprocessing check nodes. Let σ denote the number of nonprocessing check nodes in one iteration for various algorithms. Then, the reduction in complexity is 3drrσq2 FAs, RAs, and Maxs.We can notice that the additional complexity is linear and that the reduced complexity is proportional to the square of finite-field orderq. With regard to the case of short and medium code lengths, where NB-LDPC codes have more advantages compared to binary LDPC codes, the additional operations caused by the introduction of a new mechanism are much smaller than the reduced computational complexity.


## 4.2. Simulation Results

Error-correcting performance is measured by the bit error rate (BER) and frame error rate (FER). First, we consider a regular NB-LDPC codeC6488,44 that has been designed using optimized rows and optimized short loops according to [24, 25]. The parity-check matrix of this code has row weight dr=4 and column weight dc=2. The parameters of the implemented algorithms are listed below.(1) For the M-EMS algorithm,M=32; for the NS-EMS algorithm, M=32,Tc=220; for the SU-EMS algorithm,M=32,ω=3,ε=5; for the SNS-EMS algorithm, M=32,δ=1; and for the RSNS-EMS algorithm, M=32,δ=1,Titer=10,ω=4,μ=3. (2) For all algorithms, the scaling factor ξ=0.9 and b=8,Δ=1/128.The simulation results are shown in Figures6 and 7. Figure 6 shows the BER and FER performance of various algorithms, where the dashed lines represent the FER, and the solid lines represent the BER. Figure 7 shows the complexity ratio of various algorithms compared to the QSPA, and the subwindow shows the complexity ratio compared to the M-EMS algorithm.Figure 6
Decoding performance of BER and FER versusEb/N0 of various algorithms for NB-LDPC code C6488,44.Figure 7
Complexity ratio of various algorithms compared to the QSPA versusEb/N0 for NB-LDPC code C6488,44.The optimal QSPA has the best error-correcting performance, and the EMS algorithm has the second-best performance. We can see that the computational complexity of the other algorithms is much lower than that of the QSPA, almost reducing the complexity by more than 70%. Due to the introduction of the truncation rule, the M-EMS algorithm reduces complexity and brings about some performance degradation. For the proposed algorithms, we can see that there is negligible (nearly no) performance degradation between the proposed RSNS-EMS algorithm and the original M-EMS algorithm. Moreover, it is obvious that the proposed RSNS-EMS algorithm can outperform the NS-EMS and SNS-EMS algorithms. When the SNR is less than 1.8 dB, the complexity of the RSNS-EMS algorithm is slightly higher than that of the SNS-EMS algorithm, and when the SNR is greater than 1.8 dB, the complexity of the RSNS-EMS algorithm is even lower than that of the SNS-EMS algorithm. Compared to the SU-EMS algorithm, the error-correcting performance of the proposed RSNS-EMS algorithm is basically the same, and the complexity of the RSNS-EMS algorithm is much lower than that of the SU-EMS algorithm, which increases with increasing SNR and is basically the same as that of the M-EMS algorithm when the SNR is greater than 2.0 dB.Second, we consider a regular NB-LDPC code,C32200,100. The parity-check matrix of this code has row weight dr=4 and column weight dc=2. The parameters of the implemented algorithms are listed below.(1) For the M-EMS algorithm,M=16; for the NS-EMS algorithm, M=16,Tc=230; for the SU-EMS algorithm, M=16,ω=3,ε=5; for the SNS-EMS algorithm, M=16,δ=1; and for the RSNS-EMS algorithm, M=16,δ=1,Titer=10,ω=4,μ=3. (2) For all algorithms, the scaling factor ξ=0.9 and b=8,Δ=1/128.The simulation results are shown in Figures8 and 9. It can be observed that the QSPA has the best error-correcting performance among all algorithms, but it also has the highest computational complexity. The performance of the EMS algorithm is second-best, and it can reduce complexity by nearly 70% with approximately 0.2 dB degradation. Although the proposed SNS-EMS algorithm has the overall lowest complexity, its performance has a certain degree of degradation compared to the M-EMS algorithm. The proposed RSNS-EMS algorithm can outperform the NS-EMS and NS-EMS algorithms; it has negligible (nearly no BER) degradation with an approximately 25% reduction in complexity compared to the M-EMS algorithm. It is worth noting that the complexity ratio of the SU-EMS algorithm starts from 0.7 and increases to be almost equal to that of the M-EMS algorithm with increasing SNR. Therefore, compared to the SU-EMS algorithm, the RSNS scheduling algorithm proposed in this paper has almost the same error-correcting performance but has lower computational complexity.Figure 8
Decoding performance of BER and FER versusEb/N0 of various algorithms for NB-LDPC code C32200,100.Figure 9
Complexity ratio of various algorithms compared to the QSPA versusEb/N0 for NB-LDPC code C32200,100.Finally, we consider a regular NB-LDPC code,C25672,36. The parity-check matrix of this code has row weight dr=4 and column weight dc=2. The parameters of the implemented algorithms are listed below.(1) For the M-EMS algorithm,M=128; for the NS-EMS algorithm, M=128,Tc=400; for the SU-EMS algorithm, M=128,ω=2,ε=20; for the SNS-EMS algorithm, M=128,δ=1; and for the RSNS-EMS algorithm, M=128,δ=0.9,Titer=10,ω=5,μ=4. (2) For all algorithms, the scaling factor ξ=0.9 and b=8,Δ=1/256.The simulation results are shown in Figures10 and 11. It can be observed that, in these three simulations, the complexity ratio of SU-EMS algorithm increases with increasing SNR, and it is almost the same as the M-EMS algorithm at high SNR. We believe the reason is that the method used by the SU-EMS algorithm to decide whether a variable node is reliable is tracing the message evolution over iterations, where the variable node will be considered reliable only if its outgoing message is stable in ω iterations. The convergence speed of decoder is accelerated under high SNR, and it is possible that all variable nodes have already converged before being considered reliable. Therefore, the SU-EMS algorithm and M-EMS algorithm are basically the same in this situation, so there will be similar computational complexity. Besides, compared with Figures 8 and 9, we set Tc=400 in this simulation, which makes the complexity ratio of NS-EMS algorithm higher than those of the proposed algorithms. In this case, the correcting performance of NS-EMS algorithm is better than that of the SNS-EMS algorithm and it is close to that of the RSNS-EMS algorithm in low-to-moderate SNR, but it still has a certain degradation with the proposed algorithms in moderate-to-high SNR. Conversely, the proposed algorithms, especially the RSNS-EMS algorithm, can reduce the complexity by nearly 25% while keeping the error-correcting performance almost unchanged compared to the original M-EMS algorithm.Figure 10
Decoding performance of BER and FER versusEb/N0 of various algorithms for NB-LDPC code C25672,36.Figure 11
Complexity ratio of various algorithms compared to the QSPA versusEb/N0 for NB-LDPC code C25672,36.


## 5. Conclusions

In this paper, we propose two innovative scheduling strategies for the EMS algorithm—the SNS-EMS and RSNS-EMS algorithms—to reduce the computational complexity of the decoder. The SNS-EMS algorithm improves the error-correcting performance of the NS-EMS algorithm by using a new metric to judge whether or not a variable node is reliable. More importantly, to further improve the performance of the SNS-EMS algorithm while not significantly increasing its computational complexity, we investigate the variation in the processing node subset of both error frames and converged frames in the SNS-EMS algorithm. According to the experimental results, the RSNS-EMS algorithm is proposed, and it can alleviate performance degradation by employing a subset-reset mechanism. The simulation results show that the RSNS-EMS algorithm can outperform the NS-EMS and SNS-EMS algorithms with similar computational complexity. It not only effectively alleviates the performance degradation compared to the M-EMS algorithm but also reduces the computational complexity by approximately 25%. In conclusion, the proposed method can provide a good tradeoff between BER/FER and decoding complexity compared to other methods.However, this paper only discovers that such abnormal stability in the processing subset will affect decoding performance, as well as why this characteristic occurs has not been deeply discussed. We believe that continuing to study the reasons for this abnormal stability can provide a theoretical basis for the design of this algorithm. Furthermore, when resetting the processing subset, the method in this paper chooses to put all check nodes into subsets. If we continue to study which check nodes will have a greater effect on alleviating abnormal stability and use this to reset the processing subset, then it is expected that the computational complexity of the algorithm will continue to be reduced. Finally, since there are less researches for informed dynamic schedule and selected schedule on the implementation of decoder, combining proposed scheduling with reduced (hardware) complexity decoding [28, 29] is also an interesting topic for the implementation of NB-LDPC codes. We hope that this work will motivate more researches in these areas.



---

*Source: 5548091-2021-05-10.xml*