[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Next Article in Journal
Data-Driven Modeling and Rendering of Force Responses from Elastic Tool Deformation
Next Article in Special Issue
mIoT Slice for 5G Systems: Design and Performance Evaluation
Previous Article in Journal
An Enhanced Method to Estimate Heart Rate from Seismocardiography via Ensemble Averaging of Body Movements at Six Degrees of Freedom
Previous Article in Special Issue
Performance Analysis of Millimeter-Wave Multi-hop Machine-to-Machine Networks Based on Hop Distance Statistics
You seem to have javascript disabled. Please note that many of the page functionalities won't work as expected without javascript enabled.
 
 
Search for Articles:
Title / Keyword
Author / Affiliation / Email
Journal
Article Type
 
 
Advanced Search
 
Section
Special Issue
Volume
Issue
Number
Page
 
Journals
Sensors
Volume 18
Issue 1
10.3390/s18010236
sensors-logo
Submit to this Journal Review for this Journal Propose a Special Issue
► Article Menu

Article Menu

share Share announcement Help format_quote Cite question_answer Discuss in SciProfiles thumb_up
...
Endorse textsms
...
Comment
first_page
settings
Order Article Reprints
Font Type:
Arial Georgia Verdana
Font Size:
Aa Aa Aa
Line Spacing:
Column Width:
Background:
Article

Sum of the Magnitude for Hard Decision Decoding Algorithm Based on Loop Update Detection

by
Jiahui Meng
*,
Danfeng Zhao
,
Hai Tian
and
Liang Zhang
College of Information & Communication Engineering, Harbin Engineering University, Harbin 150001, China
*
Author to whom correspondence should be addressed.
Sensors 2018, 18(1), 236; https://doi.org/10.3390/s18010236
Submission received: 8 November 2017 / Revised: 10 January 2018 / Accepted: 14 January 2018 / Published: 15 January 2018
(This article belongs to the Special Issue Green Wireless Networks in 5G-inspired Applications)
Browse Figures
Figure 1
<p>Flow chart of LUDMSMWSF algorithm.</p> "> Figure 2
<p>The link level simulation block diagram.</p> "> Figure 3
<p>Code 1 weighted factor test.</p> "> Figure 4
<p>Code 2 weighted factor test.</p> "> Figure 5
<p>Comparison of five algorithms under Code 1.</p> "> Figure 6
<p>Comparison of five algorithms under Code 2.</p> "> Figure 7
<p>Comparison of improved algorithms under Code 1.</p> "> Figure 8
<p>Comparison of improved algorithms under Code 2.</p> "> Figure 9
<p>The average number of iterations of five algorithms under Code 1.</p> "> Figure 10
<p>The average number of addition operations of five algorithms under Code 1.</p> ">
Versions Notes

Abstract

:
In order to improve the performance of non-binary low-density parity check codes (LDPC) hard decision decoding algorithm and to reduce the complexity of decoding, a sum of the magnitude for hard decision decoding algorithm based on loop update detection is proposed. This will also ensure the reliability, stability and high transmission rate of 5G mobile communication. The algorithm is based on the hard decision decoding algorithm (HDA) and uses the soft information from the channel to calculate the reliability, while the sum of the variable nodes’ (VN) magnitude is excluded for computing the reliability of the parity checks. At the same time, the reliability information of the variable node is considered and the loop update detection algorithm is introduced. The bit corresponding to the error code word is flipped multiple times, before this is searched in the order of most likely error probability to finally find the correct code word. Simulation results show that the performance of one of the improved schemes is better than the weighted symbol flipping (WSF) algorithm under different hexadecimal numbers by about 2.2 dB and 2.35 dB at the bit error rate (BER) of 10−5 over an additive white Gaussian noise (AWGN) channel, respectively. Furthermore, the average number of decoding iterations is significantly reduced.

1. Introduction

On 14 October 2016, the 3rd generation partnership project radio layer 1 (3GPP RAN1) conference determined the long-code block coding scheme for 5G communication using the low density parity check node (LDPC) code as the data information of the mobile bandwidth enhance mobile broadband (eMBB) service [1,2]. The 5G includes both people-centric and machine-centric communications [3,4]. These two types of scenarios have different needs. People-centric communications pursue high performance and high-speed communications. Corresponding end-user data rates should reach 10 Gbps and base station data rates should reach 1 Tbps. Machine-centric communication pursues low power consumption with the corresponding sensor rate of only 10–100 Bps, while industrial control applications require a particularly high delay of 10−4 s [5].
Gallager proposed the LDPC code [6]. Furthermore, he created the bit flip hard decision decoding algorithm based on the check and statistics as well as proposing the soft decision decoding algorithm based on a posterior probability (APP). The decoding algorithms of multiple LDPC codes are divided into two categories according to the different decision methods [7]: Soft decision algorithm (SDA) and hard decision algorithm (HDA). The representative algorithm of the SDA is the belief propagation (BP) decoding algorithm [8,9]. The error correction performance of the BP algorithm is excellent, but the computational complexity of the BP algorithm is high with a large amount of computation and a large amount of cached data that must be stored in memory during decoding iteration, which is not conducive to engineering implementation [10]. Therefore, the SDA is chosen mainly from the perspective of reducing the decoding complexity of the study [11], with the improved algorithm applied to 5G mobile communications in the human-centric high-speed communications. The representative algorithm in HDA is a bit-flipping (BF) algorithm [12], which has low complexity and computational complexity. The algorithm is simple and easy to implement in hardware, but the decoding performance is not as good as the SDA. Therefore, the HDA is mainly studied from the perspective of improving the decoding performance, with the improved algorithm applied to a machine-centric low-rate, low-latency system in 5G mobile communications.
In the future, the 5G mobile communication system in 2020 will provide higher data transmission rate, more service connections and better user experience while ensuring low cost, transmission security, reliability and stability [13]. Channel coding in 5G mobile communication involves non-binary LDPC codes [14]. Although non-binary LDPC codes have excellent error correction performance, the complexity of high decoding is the main reason that restricts its practical application. Therefore, this paper optimizes the performance of the HDA with low complexity, and optimizes it using the symbol flipping (SF) algorithm. For the hard decision decoding algorithm, the weighting symbol flipping (WSF) algorithm proposed in literature [15] constructs a new flip function by using the minimum value of the variable node amplitude adjacent to the check node (CN) as the reliability of the check equation. On this basis, the reliability information of VN is used as the input of the flip function by the weighting factor and thus, the performance of the modified weighted symbol flipping (MWSF) algorithm will be improved [16]. Based on the belief propagation theory, the decoding algorithm proposed by literature [17] achieves a certain degree of coding gain. In this paper, this is called the improved MWSF (IMWSF) algorithm. Since then, there have been proposals of an average probability and stopping criterion weighted symbol flipping (APSCWSF) algorithm [18,19], multiple-vote symbol flipping (MV-SF) algorithm [20,21,22] and so on [23,24].
Current communication systems need to have faster and more efficient decoders than previous ones. On this basis, many scholars have studied the fast convergence and low complexity decoding algorithm with minimum decoding loss [25,26,27,28]. For the WSF algorithm proposed in literature [19,25], the destruction of the parity relation is attributed to the lowest reliability symbol in the check equation. However, if one check equation is not established, all the symbols involved in the equation may be wrong, but the symbols with lower reliability are more likely to be wrong. Therefore, a new calculation method of reliability is redefined in this paper. When calculating the reliability of variable nodes from each check equation, the reliability information of each variable node participating in the check is taken into account. Furthermore, the sum of the amplitudes of the variable nodes adjacent to the check node is used as the reliability of the check equation. At the same time, when calculating the reliability of participating check symbols, excluding the information carried by the symbol itself, a weighted symbol flipping decoding algorithm based on the magnitude sum (SMWSF) is proposed to obtain more effective soft information for reliability. On this basis, the calculation method of flip function is improved, because the variable node’s own reliability information plays an important role in the construction of the flip function. The weighted value of the symbol itself is added by a weighting factor and a modified weighted symbol flipping decoding algorithm based on the magnitude sum (MSMWSF) is proposed to improve the efficiency of symbol flipping. This is intended to improve the decoding performance and speed up the convergence. As there is a problem of repeatedly flipping the wrong symbols when the symbol is flipped, a new detection algorithm of infinite loops is proposed in this paper. Combined with the MSMWSF algorithm, this paper proposes a sum of the magnitude for weighted symbol flipping decoding algorithm based on loop update detection (LUDMSMWSF) to further speed up the convergence rate and reduce the decoding complexity.

2. Basic Definitions

In the non-binary ( N , K ) LDPC codes, N is the code word length and K is the information bits length. The non-binary LDPC codes are determined by the sparse non-binary parity check matrix H, while the check matrix H has M ≥ N − K rows and N columns. Each row represents a check equation and each column represents a code word. For any hard decision vector y , the check equation is s h ( k ) = y ( k ) H T , where the real numbers involved are carried out under the Galois field. h represents the elements in the checksum matrix. k represents the number of iterations. The number of non-zero elements in each row and each column in the check matrix is equal, which is called the rule code, while the others are called the irregular codes. The row weight of the check matrix H is d c and the column weight is d v . A non-“0” element on the nth column of the Galois field is represented by M ( n ) in the check matrix H. A non-“0” element on the mth row of the Galois field is represented by N ( m ) in the check matrix H. M ( n ) : = { m : h m n ≠ 0 } , N ( m ) : = { n : h m n ≠ 0 } .
We selected any code word c = [ c 0 , c 1 , ⋯ , c N − 1 ] ∈ { GF ( q ) } N , where q = 2 b . Before sending, the code word is mapped to the bipolar vector t = [ t 0 , t 1 , ⋯ , t N − 1 ] according to the transmitted signal constellation Ω , where t n = [ t n b , t n b + 1 , ⋯ , t ( n + 1 ) b − 1 ] , 0 ≤ n < N . Using Binary Phase Shift Keying (BPSK) modulation, ϕ : GF ( q ) → Ω b , where Ω = { − 1 ， 1 } . The specific mapping rule is ϕ ( c n ) = t n = [ t n b , ⋯ , t ( n + 1 ) b − 1 ] , where t i ∈ Ω , 0 ≤ i < N b . After the transmission of the Additive White Gaussian Noise (AWGN), the output is:
r = t + n
where n is the independent white noise real vector with noise power σ 2 = ( 2 R c E b / N 0 ) − 1 ; E b / N 0 is the signal-to-noise ratio of each information bit; and R c = K / N is the bit rate.

3. Algorithm Description

3.1. Sum of the Magnitude of Weighted Symbol Flipping Decoding Algorithm

The WSF decoding algorithm uses the information derived from the channel to calculate the reliability [15,20]. The core idea is to compute the measure of each symbol according to the reliability of the check equation. According to the size of the measured value, the most unreliable symbol is selected to be flipped. It is the simplest SF decoding algorithm based on the hard decision. The flip function E n , α ( k ) of the MWSF algorithm and the IMWSF algorithm takes into account the information carried by the symbol itself, but still neglects the reliability information of a large number of variable nodes when calculating the reliability of the check equation w n , m , α [19,25]. However, the variable node involved in each check equation is a set and the reliability calculation of the check equation should also contain the reliability information for each variable node in the set. Therefore, in this paper, the reliability and flip function are redefined. Based on the hard decision decoding, some soft information from the channel is used to calculate the reliability. The sum of the amplitude of the variable nodes connected to the check node is used as the reliability of the check equation, the influence of all symbols is added into the reliability of the check equation and the weighting factor is introduced. Using | L n , α | as part of the flip function, we obtained the WSF algorithm based on the sum of the magnitude (SMWSF). The specific process of SMWSF decoding algorithm is as follows.
  • Step 1: Initialization parameters
    • Set initial iterations k = 0
    • Calculate the initial hard decision output sequence, before using this sequence as the output of the decoding iteration in k = 0 , which is denoted as y ( 0 )
Firstly, the hard decision sequence x = [ x 0 , x 1 , ⋯ , x N b − 1 ] is obtained by the hard decision of the binary sequence r of channel output. The rules of the decision are as follows: If r i ≥ 0 , the x i is determined to be 1; if r i < 0 , the x i is determined to be 0 ( 0 ≤ i < N b − 1 ). As the hard decision is a binary sequence, so according to the binary and q-ary conversion principle, converted to N length, the sequence becomes y = [ y 0 , y 1 , ⋯ , y N − 1 ] . The sequence of y = [ y 0 , y 1 , ⋯ , y N − 1 ] is the output sequence.
3.
Calculate the probability vector L n ( α )
After the hard decision, it is necessary to calculate the initial likelihood probability of the symbol and to prepare the average likelihood probability of the check equation adjacent to all variable nodes in the subsequent iterative decoding process. The definition GF 0 ( q ) = { α 1 , ⋯ , α q − 1 } to remove the Galois field of zero element, while GF ( q ) does not contain zero elements. Gives the reliability vector α on the nth symbol:
L n = [ L n , α 1 , ⋯ , L n , α , ⋯ , L n , α q − 1 ]
where the symbol probability log likelihood is shown as follows:
L n , α = ln P ( a = α i ) P ( a = 0 ) = 2 δ 2 ∑ j : ϕ ( α ) j = + 1 r n b + j
Obviously, the log likelihood ratio of symbol probability is directly proportional to ∑ j : ϕ ( α ) j = + 1 r n b + j . In this present study, we ignored the coefficient δ 2 2 related to channel noise [29] and used ∑ j : ϕ ( α ) j = + 1 r n b + j approximation as the symbol probability log likelihood ratio, without any effect on performance.
4.
Compute the reliability w n , m , α of the external information of the received symbol y n
We defined L n , α = ∑ j : ϕ ( α ) j = + 1 r n b + j ( 0 ≤ j ≤ b − 1 ) and used Equation (3) to calculate probability matrix L n = [ L n , α ] , 0 ≤ n < N , α 1 ≤ α < α q − 1 . In this, w n , m , α represents the average probability information of the symbol α with all the variable nodes adjacent to the mth check equation. As shown in Equation (4), the formula of w n , m , α is:
w n , m , α = ∑ i ∈ N ( m ) n | L i , α | , 0 ≤ n < N , 0 ≤ m < M , α ∈ GF 0 ( q )
  • Step 2: Calculating check equation s h ( k )
We assume that the symbol vector is y ( k − 1 ) before the k ( k ≥ 1 ) iteration, while the corresponding calibration equation is s h ( k − 1 ) = y ( k − 1 ) H T ≠ 0 . Then, the check equation s h ( k ) is calculated, s h ( k ) = y ( k ) H T . If the check equation s h ( k ) = 0 , the decoding iteration is stopped and the decoding is shown to be successful.
  • Step 3: k ← k + 1 , if the k > k max ( k max is the maximum number of iterations set for the user), the decoding is declared to fail and stop.
The completion of a symbol of the flip need to determine the two parameters: (1) The position of the flip; and (2) the value or amplitude of the flip.
  • Step 4: Determining the position of the flip symbol
We calculated the measured value E n ( k ) , 0 ≤ n < N for each variable node at the kth iteration. The core of the WSF algorithm involves flipping out the symbols that do not satisfy the check equation. To calculate E n ( k ) , we first need to calculate the reliability of variable node n , respectively { α 1 , ⋯ , α q − 1 } .
E n , α ( k ) = ∑ m ∈ M ( n ) ( 2 s h , m ( k ) − 1 ) w n , m , α − β | L n , α |
In Equation (5), β ( β ≥ 0 ) is the weighting factor. At that time, β = 0 , which allows us to integrate the MSMWSF algorithm into SMWSF algorithm. For the given non-binary LDPC codes, the optimal value of the weighting factor can be obtained by Monte Carlo simulation under the specified number of iterations [30].
After this, we update the check equation to get the adjacency value of the hard decision:
s h , m ( k ) = { 0 , s h ( k ) = 0 1 , s h ( k ) ≠ 0
Among them, m is the CN. If s h ( k ) = 0 , a valid code word is obtained and the search is stopped. If s h ( k ) ≠ 0 , the flip function E n ( k + 1 ) , 0 ≤ n < N is calculated and looped accordingly.
In order to estimate the reliability measure of a symbol, the measure of each symbol must be calculated:
E n ( k ) = ∑ α ∈ GF 0 ( q ) E n , α ( k )
We select the location where the symbol is to be flipped, which is n ( k ) , 0 ≤ n < N .
The summation operation in Equation (7) is a weighted method to measure the location possibility of flipping symbols. The sum of the weights of 1 can enhance the measure of the symbol position and provide a more accurate judgment standard. In this way, the symbol corresponding to the maximum value of E n ( k ) is the position of the flip symbol, such as the Equation (8).
n ( k ) = arg max E n ( k ) , n ∈ [ 1 , N ] , n ∉ A
  • Step 5: Determining the value or magnitude of the flip
For the chosen symbol y n ( k ) , flip the bit corresponding to the minimum value of | r n i | , where 0 ≤ i < b , and update y ( k − 1 ) .
  • Step 6: Decoding, according to the results of the flip to get a new hard decision decoding sequence.
Assign the value of y ( k − 1 ) to y ( k ) , y ( k ) ← y ( k − 1 ) , and return to the second step.

3.2. Loop Update Detection Algorithm

Due to the possibility of an infinite loop in the process of symbol flipping, the symbol after the current flipping is still an error symbol and cannot be flipped to correct the symbol. Therefore, this paper proposes a loop update detection algorithm to further improve the decoding performance and speed up the convergence.
Firstly, the output symbol sequence matrix and the infinite loop detection matrix are defined, which involves the sequential traversal of each symbol. After this, sorting them from smallest to largest, we determine the location of the flip symbol. From the second smallest symbol, we re-flip the same error symbol, which is converted to the bit value. The wrong bits are sorted from smallest to largest. According to the definition of small to large index value, the bit is flipped and then converted into a symbol value to replace the previous decoding symbol. The symbol position corresponding to the maximum value is placed in the exclusion sequence. Essentially, after the symbol position corresponding to the maximum value is excluded, the maximum value error symbol is searched again. This process is repeated for decoding the iteration. The specific decoding process is as follows.
●Step 1: Initialization
The excluded sequence A is initialized to an empty set, which is used to store the position corresponding to the symbol that does not satisfy the flipping function. The bit flipping identifier F is defined and initialized to 1, which is used as the counter. The maximum value is b ( 1 b q ) and the value of F determines the number of bits to be flipped in the flip symbol.
●Step 2: Determining the magnitude of symbol flipping
The bit position to be flipped in the symbol position n ( k ) is determined by the binary sequence r = [ r 0 , r 1 , ⋯ , r N b − 1 ] , which is transmitted after the AWGN channel is transmitted. The symbol at position n ( k ) of the symbol in the to-be-flipped state can be converted into b bits, which correspond to [ r n b , r n b + 1 , ⋯ , r ( n + 1 ) b − 1 ] in r. We sort | r i | ( n b ≤ i ≤ ( n + 1 ) b − 1 ) from largest to smallest, with a smaller | r i | indicating lower reliability of the corresponding bit. Therefore, the F bit position with the smallest absolute value in [ r n b , r n b + 1 , ⋯ , r ( n + 1 ) b − 1 ] is selected according to the bit flipping identifier F, while the F bits in the corresponding position are reversed to obtain a new symbol sequence y ( k ) = [ y 0 , y 1 , ⋯ , y N − 1 ] .
●Step 3: Detects whether there is an infinite loop
The loop update detection algorithm (LUD) is as follows. First, the output symbol sequence matrix Y ( k + 1 ) × N is defined, as shown in Equation (9).
Y = [ y ( 0 ) y ( 1 ) ⋮ y ( k ) ]
Following this, an infinite loop detection matrix E k × N is defined, as shown in Equation (10).
E = [ y ( k ) − y ( 0 ) y ( k ) − y ( 1 ) ⋮ y ( k ) − y ( k − 1 ) ]
As long as all the elements of one row in an infinite loop matrix are 0, an infinite loop is detected. Otherwise, an infinite loop is not detected.
(1)
If an infinite loop is detected and F does not reach the maximum b, we increase the value of F by 1. After this, we return to step 2 to re-determine the position of the specific bit to be flipped by the symbol, before flipping the F bits of the corresponding position.
(2)
If an infinite loop is detected but F has reached the maximum b, the currently selected flip symbol position is stored in the exclusion symbol sequence A. F is set to 1 and the flip symbol position is rediscovered.
(3)
If no infinite loop is detected, the exclusion symbol sequence A is set as an empty set, the bit flipping identifier F is 1 and the calibration equation is recalculated.
Combining the loop update detection algorithm with the weighted symbol flipping algorithm based on sum of magnitude, a modified sum of the magnitude for the weighted symbol flipping decoding algorithm based on loop update detection (LUDMSMWSF) is proposed. On the basis of the MSMWSF algorithm, the algorithm repeatedly flips the bits corresponding to the error code word and looks for them in the order of the most probable error probability. Finally, this algorithm finds the correct code word. If this error traverses all the symbols, there is still an infinite loop, which indicates that the current symbol is not an error symbol. Following this, the algorithm adds the current symbol to the excluded symbol set to ensure that the next current position will not be continuously found. The specific decoding algorithm flow chart is shown in Figure 1.

4. Complexity Analysis

In this section, the conditions used to analyze the complexity of the decoding algorithm are: (1) Ignoring a small number of binary calculation and multiplication operations in the algorithm, with the assumption that the comparison operation is equivalent to the addition operation; and (2) taking the regular non-binary LDPC codes as an example to compare the average number of real addition operations in each algorithm. In the past, the computational complexity of the initial stage before the first iteration is often neglected when analyzing the computational complexity [31]. However, the simulation analysis of the decoding algorithm in the next section shows that the highest signal-to-noise ratio (SNR) in the frame occurs through iterative decoding less frequently after convergence. Thus, there is strong complexity of the initialization phase in the decoding process of the high proportion, if the neglect leads to a significant error. Therefore, the computational complexity involved in the initialization stage before the first iteration is taken into account. At the same time, the principle of second sections shows that all WSF algorithms perform symbol flipping in the final stage of each iteration, which is a serial decoding algorithm. After the symbol flipping is completed, the check equation is updated and the flip function is updated. In each iteration, there are three steps involved: (1) Calculating the adjoining vector s h ( k ) ; (2) updating the flip function E n k + 1 ; and (3) searching the flipped bit. Taking the standard WSF algorithm as an example, if the variable node n is flipped during the previous iteration, the adjoining vectors s h ( k ) corresponding to the d v check nodes connected to them need to be updated. After the update of the vector s h ( k ) is completed, the flip function E n k + 1 of d c variable nodes connected to the check node m is calculated. Therefore, for both steps, the total number of operations required is d c ⋅ d v . In Step (3), it is assumed that the node position of the variable corresponding to the maximum flip function E n k + 1 is found in n variable nodes, while further comparison operations are performed for N − 1 times. Therefore, the calculation amount of an iterative process in a standard WSF algorithm is N − 1 + d c ⋅ d v . The specific update process is as follows. First, we calculate s h , m k + 1 = 1 − s h , m k , m ∈ M ( θ ) and update it according to the updated formula of flip function, which is E n k + 1 = E n k + 2 ∑ m ∈ M ( θ ) w n , m , α ( 2 s h , m k + 1 − 1 ) , n ∈ N ( m ) , m ∈ M ( θ ) . The average number of iterations of the five decoding algorithms is A I 1 – A I 6 , while d c represents line weight and d v represents column weight. Table 1 gives the calculation methods of the total number of real operations of each decoding algorithm. From Table 1, it can be concluded that the complexity of the LUDWSF, LUDSMWSF and LUDMSMWSF algorithms is lower than the WSF, SMWSF and MSMWSF algorithms. Taking one algorithm as an example, the computation amount of WSF algorithm and LUDWSF algorithm is the same for each iteration with the difference of the average iteration times. However, the average iterations of LUDWSF algorithm are much less than that of WSF algorithm. From Table 1, the LUDMSMWSF algorithm only requires real additions, complexity is M q ( 2 d c − 1 ) + N q d v + ( N − 1 ) + ( N − 1 + d c d v ) ( A I 5 − 1 ) . However, complexity of the Fast Fourier Transform-based belief propagation decoding algorithm (FFT-BP) [32,33] includes real additions, multiplications and divisions, the complexities of which are A I 6 [ 2 N d v q log 2 q + 2 N d v ( q − 1 ) + M ( d c − 1 ) ] , A I 6 [ N d v q ( d c + 2 d v − 1 ) + M d c ] and A I 6 [ N d v ( q + 2 ) ] , respectively. Real multiplications and divisions are more consumable units than real additions. Although the proposed WSF algorithm with flipping pattern requires more iterations for decoding than FFT-BP, it needs less real additions than FFT-BP and requires no multiplying the iterations with computational requirements in each iteration, the total computational requirement of WSF algorithm is still lower than FFT-BP. Therefore, the computational requirement of WSF algorithm is much lower than FFT-BP.

5. Simulation Results and Statistical Analysis

The simulation parameters used in this section are as follows: 384,192 LDPC codes with a code rate of 0.5 and a column weight of three. The matrix is generated by the progressive edge growth (PEG) algorithm [34,35], divided into 4-ary (Code 1) and 16-ary (Code 2) simulation, which has a maximum number of iterations of 100. Under the AWGN channel conditions and using BPSK modulation, at least 1000 error bits are collected at each SNR. The link level simulation block diagram is shown in Figure 2.

5.1. Weighted Factor Test

For non-binary LDPC codes with given column weights, the decoding performance is different under the same signal-to-noise ratio with different weighting factors. When choosing a constant and optimal weighting factor, the performance loss is negligible and the complexity of the implementation is decreased [36,37]. The optimal value of the weighting factor is generally related to the non-binary LDPC codes and the specific code structure. Figure 3 and Figure 4 show the bit error rate performance of Code 1 and Code 2 with different weighting factors when using MSMWSF algorithm under different SNR conditions. Based on the definition of the optimal value of weighted factor, it can be seen from Figure 3 that the influence of weighting factor on bit error rate (BER) is not obvious at lower SNR as the optimal value of weighting factor varies little with an increase in SNR. As shown in Figure 3 and Figure 4, the optimal value of the weighting factor of the MSMWSF algorithm in Code 1 in this paper is 1.8, while the optimal value of the weighting factor of the MSMWSF algorithm in Code 2 is one.

5.2. Comparison of Algorithm Performance and Average Iteration Numbers

The performance comparison between Code 1 and Code 2 in five different decoding algorithms under the optimal parameters is shown in Figure 5 and Figure 6, respectively. With an increase in SNR, the coding gain of MSMWSF algorithm is gradually increasing compared with other existing algorithms. At a low SNR, the performance of MSMWSF algorithm is almost the same as other algorithms. According to the simulation diagram of reference [34,35,36], a higher number of binary numbers indicates a poorer performance of the WSF algorithm. From Figure 5 and Figure 6, we can see that the performance of Code 1 is better than that of Code 2, which proves the effectiveness of the algorithm proposed in this paper.
Figure 7 and Figure 8 show the performance of Code 1 and Code 2 under the SMWSF algorithm and MSMWSF algorithm, respectively, with the optimal parameters of the weighting factors after introducing the loop update detection algorithm. As seen from Figure 7 and Figure 8, the LUDMSMWSF algorithm improves the decoding performance compared to the MSMWSF algorithm, accelerating the convergence speed. Compared with the WSF algorithm, a coding gain of 2.2 dB is obtained in the case of Code 1 and a coding gain of 2.35 dB in the case of Code 2. Under the same decoding algorithm, the coding gain of about 0.8–1.1 dB can be obtained after introducing the proposed loop update detection algorithm. At the same time, the LUDMSMWSF algorithm is about 0.85–1.05 dB away from FFT-BP decoding at BER of 10−5 with a tremendous reduction of computational requirement. In view of the results on Figure 7 and Figure 8, we argue that the proposed symbol flipping algorithm offer the tradeoff points between performance and computational cost.
Figure 9 and Figure 10 gives the average number of iterations and average number of addition operations of Code 1 under five decoding algorithms. As shown in Figure 9 and Figure 10, the two algorithms proposed in this paper are significantly less than the average number of iterations and the average number of addition operations in the traditional algorithm. Because the algorithm proposed in this paper has more efficient and accurate symbol flipping function, it improves the performance and reduces the complexity of the algorithm to a certain extent. We see that MSMWSF algorithm achieves fast convergence and low complexity.
We set the SNR to be 3.5 dB with the simulation of 10,000 frames under the condition of Code 1. We then combined the statistical five algorithms for decoding failure frames, as shown in Table 2. Table 2 shows that the WSF algorithm has nearly 99% frame failure. Two decoding algorithms are proposed in this paper. The failure of the frame is about 62% and 42%, which is less than traditional algorithms. It can also be seen that the algorithm proposed in this paper does not increase the complexity of the implementation, but has been reduced to a certain extent.
The total computation required for decoding this LDPC codewith three various algorithms at 4.5 dB is shown in Table 3. From Table 3, the FFT-BP algorithm is nearly six times the computational requirement of the MSMWSF algorithm only in real addition. Therefore, we can prove that the computational requirement of MSMWSF algorithm is much lower than FFT-BP with no real multiplication and division. The MSMWSF algorithm has the lowest complexity and does not need to consume hardware resources and multiplication and division operations in software overhead.

6. Conclusions

This paper proposes a sum of the magnitude for hard decision decoding algorithm based on loop update detection. The algorithm combines the magnitude of the sum information of the variable nodes adjacent to the check node and uses it as the reliability information. At the same time, the reliability information of the variable node itself is taken into account and a more effective flip function is obtained, which improves the flip efficiency of the symbol and improves the decoding performance of the algorithm. The loop update detection algorithm is introduced to improve the accuracy of symbol flipping and to further accelerate the convergence rate of decoding. Simulation results show that compared with the WSF algorithm, the proposed LUDMSMWSF algorithm gains about 1.3 dB and 1.8 dB respectively and the decoding complexity is greatly reduced. Therefore, the algorithm proposed in this paper can be better applied to the 5G mobile communication system and meet the requirements of the decoding algorithm. It is a good candidate decoding algorithm for high speed communication devices.

Acknowledgments

This research work was supported by the ZTE Cooperation Forum Project (Grant No. KY10800160020), the National Natural Science Foundation of China (Grant No. 61371099), the Fundamental Research Funds for the Central Universities of China (Grant No.HEUCF150814/150812/150810), the International Exchange Program of Harbin Engineering University for Innovation-Oriented Talents Cultivation.

Author Contributions

Danfeng Zhao and Hai Tian conceived the ideas and concept. Jiahui Meng implemented the software and carried out the experiments and wrote the manuscript. Liang Zhang carried out simulation experiments and further verified the experimental results. Danfeng Zhao critically reviewed the paper.

Conflicts of Interest

The authors declare no conflict of interest.

References

  1. Naga, B.; Li, J.Y.; Durga, P.M. Network densification: The dominant theme for wireless evolution into 5G. IEEE Commun. Mag. 2014, 52, 82–89. [Google Scholar]
  2. Guo, L.; Ning, Z.L.; Song, Q.Y. Joint encoding and grouping multiple node pairs for physical-layer network coding with low-complexity algorithm. IEEE Trans. Veh. Technol. 2017, 66, 9275–9286. [Google Scholar] [CrossRef]
  3. Wang, L.S.; Wang, Y.M.; Ding, Z.Z. Cell selection game for densely-deployed sensors and mobile devices in 5G networks integrating heterogeneous cells and internet of things. Sensors 2015, 15, 24230–24256. [Google Scholar] [CrossRef] [PubMed]
  4. Fortuna, C.; Bekan, A.; Javornik, T. Software interfaces for control, optimization and update of 5G type communication networks. Comput. Netw. 2017, 129, 373–383. [Google Scholar] [CrossRef]
  5. Gao, X.; Ove, E.; Fredrik, R. Massive MIMO performance evaluation based on measured propagation data. IEEE Trans. Wirel. Commun. 2015, 14, 3899–3911. [Google Scholar] [CrossRef]
  6. Cheng, L.; Zhu, H.; Li, G. LDPC encoder design and FPGA implementation in deep space communication. In Proceedings of the International Conference on Logistics, Engineering, Management and Computer Science, Shenyang, China, 24–26 May 2014; pp. 343–346. [Google Scholar]
  7. Wang, C.L.; Chen, X.H.; Li, Z.W. A simplified Min-Sum decoding algorithm for non-binary LDPC codes. IEEE Trans. Commun. 2015, 61, 24–32. [Google Scholar] [CrossRef]
  8. Marc, P.C.F.; Miodrag, J.M.; Hideki, I. Reduced complexity iterative decoding of low-density parity check node based on belief propagation. IEEE Trans. Commun. 1999, 47, 673–680. [Google Scholar]
  9. Aslam, C.A.; Guan, Y.L.; Cai, K. Edge-based dynamic scheduling for belief-propagation decoding of LDPC and R S codes. IEEE Trans. Commun. 2017, 65, 525–535. [Google Scholar] [CrossRef]
  10. Namrata, P.B.; Brijesh, V. Design of hard and soft decision decoding algorithms of LDPC. Int. J. Comput. Appl. 2014, 90, 10–15. [Google Scholar]
  11. Evdal, A.; Najeeb, U.H.; Michael, L. Challenges and some new directions in channel coding. J. Commun. Netw. 2015, 17, 328–338. [Google Scholar] [Green Version]
  12. Balasuriya, N.; Wavegedara, C.B. Improved symbol value selection for symbol flipping-based non-binary LDPC decoding. EURASIP J. Wirel. Commun. Netw. 2017, 2017, 105. [Google Scholar] [CrossRef]
  13. Chen, M.; Hao, Y.X.; Qiu, M.K. Mobility-Aware caching and computation off loading in 5G ultra-dense cellular network. Sensors 2016, 16, 974. [Google Scholar] [CrossRef] [PubMed]
  14. Swapnil, M. High-Throughput FPGA QC-LDPC Decoder Architecture for 5G Wireless; The State University of New Jersey: Rutgers, NJ, USA, 2015. [Google Scholar]
  15. Kou, Y.; Lin, S.; Fossorier, M. Low-density parity-check codes based on finite geometries: A rediscovery and new results. IEEE Trans. Inf. Theory 2001, 47, 2711–2736. [Google Scholar] [CrossRef]
  16. Zhang, J.; Fossorier, M. A modified weighted bit-flipping decoding of low-density parity-check codes. IEEE Commun. Lett. 2004, 8, 165–167. [Google Scholar] [CrossRef]
  17. Jiang, M.; Zhao, C.M.; Shi, Z. An improvement on the modified weighted bit flipping decoding algorithm for LDPC codes. IEEE Commun. Lett. 2005, 9, 814–816. [Google Scholar] [CrossRef]
  18. Guo, R.; Liu, C.; Wang, M. Weighted symbol-flipping decoding for non-binary LDPC codes based on average probability and stopping criterion. J. Commun. 2016, 37, 43–52. [Google Scholar]
  19. Zhang, G.Y.; Zhou, L.; Su, W.W. Average magnitude based weighted bit-flipping decoding algorithm for LDPC codes: Average magnitude based weighted bit-flipping decoding algorithm for LDPC codes. J. Electron. Inf. Technol. 2014, 35, 2572–2578. [Google Scholar] [CrossRef]
  20. Garcia-Herrero, F.; Li, E.B.; Declercq, D. Multiple-Vote Symbol-Flipping Decoder for Nonbinary LDPC Codes. IEEE Trans. Very Large Scale Integr. Syst. 2014, 11, 2256–2267. [Google Scholar] [CrossRef]
  21. Garcia-Herrero, F.; Declercq, D.; Valls, J. Non-binary LDPC decoder based on symbol flipping with multiple votes. IEEE Commun. Lett. 2014, 18, 749–752. [Google Scholar] [CrossRef]
  22. Nhan, N.Q.; Ngatched, T.M.N.; Dobre, O.A. Multiple-votes parallel symbol-flipping decoding algorithm for non-binary LDPC codes. IEEE Commun. Lett. 2015, 19, 905–908. [Google Scholar] [CrossRef]
  23. Ueng, Y.L.; Wang, C.Y.; Li, M.R. An efficient combined bit-flipping and stochastic LDPC decoder using improved probability traces. IEEE Trans. Signal Process. 2017, 65, 5368–5380. [Google Scholar] [CrossRef]
  24. Le, K.; Ghaffari, F.; Declercq, D. Efficient hardware implementation of probabilistic gradient descent bit-flipping. IEEE Trans. Circuits Syst. I Regul. Pap. 2017, 64, 906–917. [Google Scholar] [CrossRef]
  25. Lu, M. Research on Construction and Decoding Algorithm of Nonbinary LDPC Codes; Beijing Jiaotong University: Beijing, China, 2013. [Google Scholar]
  26. Mackay, D.J.; Wilson, S.T.; Davey, M.C. Comparison of constructions of irregular Gallager codes. IEEE Trans. Commun. 1999, 47, 1449–1454. [Google Scholar] [CrossRef]
  27. Garcia-Herrero, F.; Canet, M.J.; Valls, J. Nonbinary LDPC Decoder Based on Simplified Enhanced Generalized Bit-Flipping Algorithm. IEEE Trans. Very Large Scale Integr. Syst. 2014, 22, 1455–1459. [Google Scholar] [CrossRef]
  28. Thi, H.P. Two-Extra-Column Trellis Min-max Decoder Architecture for Nonbinary LDPC Codes. IEEE Trans. Very Large Scale Integr. Syst. 2017, 25, 1781–1791. [Google Scholar] [CrossRef]
  29. Guo, F.; Hanzo, L. Reliability ratio based weighted bit-flipping decoding for low-density parity-check codes. Electron. Lett. 2004, 40, 1356–1358. [Google Scholar] [CrossRef]
  30. Zhang, J.Y. Simplified symbol flipping algorithms for nonbinary low-density parity-check codes. IEEE Trans. Commun. 2017, 65, 4128–4137. [Google Scholar] [CrossRef]
  31. Liu, B.; Tao, W.; Dou, G.Q. Weighted symbol-flipping decoding for nonbinary LDPC codes based on a new stopping criterion. J. Electron. Inf. Technol. 2011, 33, 309–314. [Google Scholar] [CrossRef]
  32. Sulek, W. Non-binary LDPC decoders design for maximizing throughput of an FPGA implementation. Circuits Syst. Signal Process. 2016, 35, 4060–4080. [Google Scholar] [CrossRef]
  33. Kang, J.Y.; Huang, Q.; Zhang, L. Quasi-cyclic LDPC codes: An algebraic construction. IEEE Trans. Commun. 2010, 58, 1383–1396. [Google Scholar] [CrossRef]
  34. Jiang, X.Q.; Hai, H.; Wang, H.M. Constructing large girth QC protograph LDPC codes based on PSD-PEG algorithm. IEEE Access 2017, 5, 13489–13500. [Google Scholar] [CrossRef]
  35. Bai, Z.L.; Wang, X.Y.; Yang, S.S. High-efficiency Gaussian key reconciliation in continuous variable quantum key distribution. Sci. China Phys. Mech. Astron. 2016, 59, 614201. [Google Scholar] [CrossRef]
  36. Chang, T.C.Y.; Su, Y.T. Dynamic weighted bit-flipping decoding algorithm for LDPC codes. IEEE Trans. Commun. 2015, 63, 3950–3963. [Google Scholar] [CrossRef]
  37. Bazzi, L.; Audah, H. Impact of redundant checks on the LP decoding thresholds of LDPC codes. IEEE Trans. Inf. Theory 2015, 61, 2240–2255. [Google Scholar] [CrossRef]
Sensors 18 00236 g001 550
Figure 1. Flow chart of LUDMSMWSF algorithm.
Figure 1. Flow chart of LUDMSMWSF algorithm.
Sensors 18 00236 g001
Sensors 18 00236 g002 550
Figure 2. The link level simulation block diagram.
Figure 2. The link level simulation block diagram.
Sensors 18 00236 g002
Sensors 18 00236 g003 550
Figure 3. Code 1 weighted factor test.
Figure 3. Code 1 weighted factor test.
Sensors 18 00236 g003
Sensors 18 00236 g004 550
Figure 4. Code 2 weighted factor test.
Figure 4. Code 2 weighted factor test.
Sensors 18 00236 g004
Sensors 18 00236 g005 550
Figure 5. Comparison of five algorithms under Code 1.
Figure 5. Comparison of five algorithms under Code 1.
Sensors 18 00236 g005
Sensors 18 00236 g006 550
Figure 6. Comparison of five algorithms under Code 2.
Figure 6. Comparison of five algorithms under Code 2.
Sensors 18 00236 g006
Sensors 18 00236 g007 550
Figure 7. Comparison of improved algorithms under Code 1.
Figure 7. Comparison of improved algorithms under Code 1.
Sensors 18 00236 g007
Sensors 18 00236 g008 550
Figure 8. Comparison of improved algorithms under Code 2.
Figure 8. Comparison of improved algorithms under Code 2.
Sensors 18 00236 g008
Sensors 18 00236 g009 550
Figure 9. The average number of iterations of five algorithms under Code 1.
Figure 9. The average number of iterations of five algorithms under Code 1.
Sensors 18 00236 g009
Sensors 18 00236 g010 550
Figure 10. The average number of addition operations of five algorithms under Code 1.
Figure 10. The average number of addition operations of five algorithms under Code 1.
Sensors 18 00236 g010
Table
Table 1. The average total number of real operations in each algorithm.
Table 1. The average total number of real operations in each algorithm.
SF AlgorithmAddition OperationsMultiplication OperationsDivision Operations
WSF M q ( d c − 1 ) + N q ( d v − 1 ) + ( N − 1 ) + ( N − 1 + d c d v ) ( A I 1 − 1 ) 00
SMWSF M q ( 2 d c − 1 ) + N q ( d v − 1 ) + ( N − 1 ) + ( N − 1 + d c d v ) ( A I 2 − 1 ) 00
MSMWSF M q ( 2 d c − 1 ) + N q d v + ( N − 1 ) + ( N − 1 + d c d v ) ( A I 3 − 1 ) 00
LUDSMWSF M q ( 2 d c − 1 ) + N q ( d v − 1 ) + ( N − 1 ) + ( N − 1 + d c d v ) ( A I 4 − 1 ) 00
LUDMSMWSF M q ( 2 d c − 1 ) + N q d v + ( N − 1 ) + ( N − 1 + d c d v ) ( A I 5 − 1 ) 00
FFT-BP A I 6 [ 2 N d v q log 2 q + 2 N d v ( q − 1 ) + M ( d c − 1 ) ] A I 6 [ N d v q ( d c + 2 d v − 1 ) + M d c ] A I 6 [ N d v ( q + 2 ) ]
Table
Table 2. Five algorithms for decoding failure frames.
Table 2. Five algorithms for decoding failure frames.
SF AlgorithmDecoding Failure Frames
WSF algorithm9915
MWSF algorithm9840
IMWSF algorithm6544
SMWSF algorithm6200
MSMWSF algorithm4184
Table
Table 3. Under the condition of Code 2, Eb/N0 = 4.5 dB, decoding complexity of three algorithms.
Table 3. Under the condition of Code 2, Eb/N0 = 4.5 dB, decoding complexity of three algorithms.
SF AlgorithmAddition OperationsMultiplication OperationsDivision Operations
WSF algorithm20564400
MSMWSF algorithm9271000
FFT-BP algorihtm56772374487066267

Share and Cite

MDPI and ACS Style

Meng, J.; Zhao, D.; Tian, H.; Zhang, L. Sum of the Magnitude for Hard Decision Decoding Algorithm Based on Loop Update Detection. Sensors 2018, 18, 236. https://doi.org/10.3390/s18010236

AMA Style

Meng J, Zhao D, Tian H, Zhang L. Sum of the Magnitude for Hard Decision Decoding Algorithm Based on Loop Update Detection. Sensors. 2018; 18(1):236. https://doi.org/10.3390/s18010236

Chicago/Turabian Style

Meng, Jiahui, Danfeng Zhao, Hai Tian, and Liang Zhang. 2018. "Sum of the Magnitude for Hard Decision Decoding Algorithm Based on Loop Update Detection" Sensors 18, no. 1: 236. https://doi.org/10.3390/s18010236

APA Style

Meng, J., Zhao, D., Tian, H., & Zhang, L. (2018). Sum of the Magnitude for Hard Decision Decoding Algorithm Based on Loop Update Detection. Sensors, 18(1), 236. https://doi.org/10.3390/s18010236

Note that from the first issue of 2016, this journal uses article numbers instead of page numbers. See further details here.

Article Metrics

Back to TopTop