Open access peer-reviewed chapter

Generalized Low-Density Parity-Check Codes: Construction and Decoding Algorithms

By Sherif Elsanadily

Submitted: March 29th 2019Reviewed: June 24th 2019Published: September 23rd 2019

DOI: 10.5772/intechopen.88199

Downloaded: 151

Abstract

Scientists have competed to find codes that can be decoded with optimal decoding algorithms. Generalized LDPC codes were found to compare well with such codes. LDPC codes are well treated with both types of decoding; HDD and SDD. On the other hand GLDPC codes iterative decoding, on both AWGN and BSC channels, was not sufficiently investigated in the literature. This chapter first describes its construction then discusses its iterative decoding algorithms on both channels so far. The SISO decoders, of GLDPC component codes, show excellent error performance with moderate and high code rate. However, the complexities of such decoding algorithms are very high. When the HDD BF algorithm presented to LDPC for its simplicity and speed, it was far from the BSC capacity. Therefore involving LDPC codes in optical systems using such algorithms is a wrong choice. GLDPC codes can be introduced as a good alternative of LDPC codes as their performance under BF algorithm can be improved and they would then be a competitive choice for optical communications. This chapter will discuss the iterative HDD algorithms that improve decoding error performance of GLDPC codes. SDD algorithms that maintain the performance but lowering decoding simplicity are also described.

Keywords

  • channel coding
  • generalized LDPC codes
  • iterative decoding
  • bit-flipping
  • chase algorithm

1. Introduction

Generalized LDPC (GLDPC) block codes were first proposed by Tanner [1] as they internally contain block codes (which are called component codes) and not just single parity check (SPC) as the case in LDPC codes. From this definition, we know that LDPC codes can be regarded as a special class of GLDPC codes. GLDPC block codes possess many desirable features, such as large minimum distance [2], good iterative decoding performance, and low error floor [3]. At the same time, the complexity of the processed operations increases due to the inserted complicated constraints. Therefore, scientists are stirred to find a good GLDPC code with suitable subcodes achieving the desired error performance at fair complication. The methods in [4] by Fossorier and the Bahl-Cocke-Jelinek-Raviv (BCJR) algorithm [5], APP decoding algorithm, are vastly investigated for GLDPC decoding. Both algorithms perform the task with various subcodes, such as Hamming codes [2, 6], BCH codes [6, 7], RS codes [7], and GLDPC code with hybrid subcodes [8, 9]. However, these decoders can be considered highly complicated. In [10], a kind of Hadamard-based GLDPC codes was suggested. The complicated decoding processes were avoided due to the easiness and fastness of the used subcode transform (FHT). On the other hand, this code is not convenient in many communication systems as it is described as low code rate (R0.1). The soft-input/soft-output (SISO) decoders for decoding the component codes in GLDPC codes were considered in [2, 6] and [11] showing very good error performance with moderate and high code rate. Two interesting approaches at GLDPC codes have been presented in [4, 12]. In [12] the proposed construction concentrates on maximizing the girth and the minimum distance of the global code. The generated codes achieved coding gain up to 11 dB over 40 GB/s optical channel. In [4] the authors propose doubly generalized LDPC codes. These codes employ local codes at both variable and check nodes. Back to LDPC codes and since their resurrection, most research efforts were directed toward the implementation of these codes over the additive white Gaussian noise (AWGN) channel. The LDPC codes were proven to perform very close to the Shannon limit of AWGN channel, and much work has been carried out to design optimal codes and improve and simplify iterative decoding of these codes over the AWGN channel. The major drawback is that it exhibits considerable computational complexity. Gallager accurately, on the other hand, analyzed the performance of LDPC codes over the binary symmetric channel (BSC) in his original paper and proposed two HDD bit-flipping (BF) algorithms, for which he provided theoretical limits under iterative decoding. However, BF algorithms did not gain much attention. Most of the work that considered BF decoding used it in conjunction with soft information obtained from AWGN channel to improve decoding performance. However, in some applications, such as optical communications, soft values are not available at the receiver. Therefore, optical channels are an excellent example of the BSC, and only hard decision decoding is possible. Currently, BCH and RS codes are exclusively used in optical communication for error control, since there are simple and efficient algorithms for decoding. With the recent introduction of wavelength division multiple access (WDMA), transmission rates in optical communications reach 40 GB/s per channel/fiber, a standard in modem optical networks, SONET/SDH. Moreover, the concept of signal regeneration was abandoned in optical communication with the advancement in lasers so that optical signal is transmitted over larger distance than before, reaching the receiver very attenuated. These developments in optical communication call for an error control code which is very powerful yet has a simple and fast decoding. Furthermore, very low error rates are needed, say BER of 1015.

The BF algorithm proposed by Gallager is a HDD algorithm and is implemented using modulo-2 logic. Therefore it satisfies the requirement for simplicity and speed. However, the performance of the decoding algorithm is far from the capacity of the BSC, and, more importantly, an error floor is generally observed, which seriously constrains implementation of LDPC codes in optical systems. GLDPC codes can be introduced as a good alternative of LDPC codes as their performance under the BF algorithm can be improved and the observed error floor can be lowered or even removed. GLDPC codes would then be a competitive choice for optical communications.

In this chapter, iterative decoding of GLDPC codes over AWGN and BSC is studied. HDD algorithms that improve decoding performance and error floor behavior of GLDPC codes over BSC channels are discussed. They make GLDPC codes very competitive for high-rate optical communications. Soft decision decoding (SDD) algorithms that maintain the performance but lower decoding simplicity are also presented.

2. GLDPC code construction

The check node in the bipartite graph of the LDPC code, as said before, is connected to a number of variable nodes which satisfy a single parity check. The GLDPC is a more generalized form of LDPC as the bits of the VNs, connected to the same CN, constitute a valid codeword of a (n,k) linear block code (other than the simple SPC code). Therefore this (n,k) code is called a constituent code, component code, or simply subcode. The CN which associates with this generalized code is called a generalized CN (GCN). The GLDPC code is referred to as a (N, J, n) regular and “strict-sense” code, as depicted in Figure 1 , if:

  • The VN degree (denoted as qw) is constant for all VNs (qw=J).

  • The GCN degree (denoted as qc) is constant for all GCNs (qc=n).

  • The same constituent code (other than the simple SPC code) stands for all GCNs.

Figure 1.

The bipartite graph of the strict-sense (32,2,16) regular GLDPC code.

where Jis the column weight in the parity-check matrix of the global LDPC code and Nis the overall code block length. The GLDPC code is otherwise called “hybrid code” (if not all the GCNs has the same constituent code) [8, 13].

The GLDPC code rate is given by R=K/N1J1k/n, where Kdenotes its code dimension and Ndenotes its block length. The GLDPC code, according to the chosen values of its parameters, has multiple wonderful properties such as the better minimum distance (compared to LDPC code with the same code rate) [2]. The GLDPC also converges faster, and it is distinguished by the lower error floor [3]. We are interested here with GLDPC codes based on Hamming codes for simplicity and fast decoding purposes.

Figure 1 elaborates the bipartite graph of a NJnregular Hamming-based GLDPC code with (4 × 32) global LDPC matrix. The extended Hamming (8,4) constituent code is represented in every GCN. Figure 2 depicts the procedures to get the overall parity-check matrix of this code from the global LDPC matrix (or referred to as the graph adjacency matrix). Every “1” in every row in the global matrix is replaced with a column from the columns of the constituent code parity-check matrix, and every “0” is replaced with a zero column. The assignments of the constituent code H columns should be randomly done to generate a code with good characteristics. There are other constructions of GLDPC which can be further discussed in [14, 15, 16].

Figure 2.

The procedure of generating a (32,2,16) Hamming-based GLDPC code from its base matrix.

3. SDD of GLDPC codes

SDD of Hamming-based GLDPC codes was presented in the literature and shows that GLDPC codes are asymptotically good and can achieve the capacity by iterative decoding using soft-input/soft-output subcode decoders [2, 6, 17]. The SISO decoder is typically a sub-optimal erasure decoder extended to deliver soft outputs, e.g., chase-II decoder [18], which is used in this section.

A NJnGLDPC code is constructed from a N.J/nby Nrandom sparse matrix H, with row weights of nand column weights of J, and the parity-check matrix Hcof a nkdsubcode. The resultant GLDPC parity-check matrix is denoted as HGLDPCas discussed in Section 2.

At any GCN c, the input to the chase decoder is Rc=rc,1rc,irc,ncorresponding to the transmitted word Xc=xc,1xc,ixc,nand its hard demodulated values Yc=yc,1yc,iyc,n.

A group of codewords are selected as the most likely ones that hold the transmitted words with the minimum errors. The algorithm operates on the available data (reliability) and flips all possible combinations of p=d/2demodulated symbols with the least-reliable positions (LRPs). Setting the reliability information in [19] in the log-likelihood ratio (LLR) of decision yc,ias

Λyc,i=lnprxc,i=+1/xc,iprxc,i=1/xc,i=2σ2rc,iE1

A set Zc=Zcqof error patterns with all possible errors confined to pLRP positions of Ycis used to modify Ycyielding list of test patterns Tcqq12pTcq=Zcq+Yc. Then every Tcqin the list is decoded using algebraic decoder, and the valid decoded codeword Cqis stored in a list Ωas a candidate codeword. Decision codeword Dc=dc,1dc,idc,nshould be chosen from this list as it is obtained using the rule [20]:

Dc=CqifRcCq2RcCl2for everyClΩE2

Now, every decoded symbol resulting value in the subcode (soft) is to be estimated to be passed back on the edges, linked to symbol nodes with steps as the MP algorithm iteratively to output a final estimate after performing a predefined amount of iterations or satisfying the syndrome check.

In order to calculate the reliability of each bit, dc,i, in the decision Dc(i.e., the ith soft output of the soft-input decoder), two codewords C+1iand C1iare to be selected from two sets of Ωwith minimum Euclidean distance from R. The decision Dcis one of them, and the second one, Bc=bc,1bc,ibc,n, called as competing codeword of D with bc,idc,i, should be found.

The soft outputs are generated in the LLR domain outgoing from GCN cusing the following approximation formula:

rc,i'=RcBc2RcDc24dc,iE3

If the competing codeword Bcis not found, the following alternative and efficient formula is used:

rc,i'=β×dc,iwithβ0E4

where βis a reliability factor. Due to the variation of sample deviation in the input and in the output of the soft decoders, we put a scaling factor, α, to increase the convergence rate:

Wct+1=Rc+αtWctE5

By subtracting the soft input rc,ifrom the soft output rc,i'for each i12nat GCN c, the extrinsic information during the tth iteration, Wt, is obtained. It is then multiplied by the scaling factor, αt, added to the channel observed values Rc, and the result is considered as a priori information for the decoder at the next t+1th iteration.

Figure 3 shows that a chase rather than optimal SISO decoder can be successfully employed in the decoding of high-rate extended Hamming-based GLDPC codes and the BERs are close to the capacity with the efficient fast chase decoding in [21].

Figure 3.

Performance variation with erasures p for (65,536,2,64) GLD code.

4. HDD of GLDPC codes

The HDD such as BF decoding or any other algebraic decoding scheme can be generalized to GLDPC codes especially over BEC or BSC and can be applied in very high-speed applications such as the 40 GBps optical communications. The error-correcting capability of the subcodes, at the GCNs, is used to more accurately determine the position of least-reliable symbols. The iterative HDD algorithms for decoding GLDPC codes will be described in the next subsections.

4.1 WBFV algorithm

As mentioned before in BF algorithm of LDPC codes, symbols belonging to the maximum number of unsatisfied CNs, in each iteration, have the binary bits inverted before the following iteration. Subsequently, the failed CNs convey their votes of unit weight to the corresponding connected VNs, and the algorithm inverts the LR bits with the highest amount of votes.

The presented iterative weighted bit-flip voting (WBFV) in [22] employs subcode hard decision decoders (HDDs) at the GCNs that have a greater range of vote weights passed to the connected VNs. It passes the high-weight votes to a specific symbol if the HDD, at a given GCN, considers it to be in error.

As the GLDPC codes of Gallager construction, J=2, and Hamming subcode are only concerned, all nonzero syndromes of these subcodes will be error-correctable. The algebraic decoders only allow for two instances:

  • All-zero syndromes imply a valid codeword; in this case a vote Vwill be returned to all connected VNs (symbols) as in GCN 1 in Figure 4 .

  • Nonzero syndromes imply nonvalid codewords; in this case the indicated error position will be sent a vote E, and all other bits a vote eas in GCN 2 in Figure 4 .

Figure 4.

Example votes from subcode decoders.

After votes have been cast, each symbol has received a vote pair: either VV, eV, ee, EV, Ee, or EE. In the example shown, the symbol at the two subcodes’ intersection has a vote pair eV.

The strategy proceeds by passing current bit values from the VNs to the Hamming decoders at GCNs. The HDDs at these GCNs pass back nindividual votes to the symbols they connect.

The magnitude of a vote marks the power of the decision for a GCN about the current symbol (reliable or not). The higher magnitudes mark the unreliable bits, and the lower ones mark the bits of more reliability.

The Jarriving votes to every VN are collected such that all N variable symbols are sorted by the reliability information and the group of LRP bits inverted before the upcoming iteration.

The iterative algorithm proceeds until all symbols become of weight pair VVor the maximum number of iterations is reached. For Hamming subcodes there are only three votes V,e, and Egenerated by the subcode HDDs described before. The vote rules, as sets of vote weights, are defined and listed in Table 1 .

Rule ARule BRule C
V=0,e=2,E=3V=0,e=1,E=2V=0,e=1,E=3
Vote pairTotalVote pairTotalVote pairTotal
EE6EE4EE6
Ee5Ee3Ee4
ee4EV , ee2EV3
eV2VV0eV1
VV0VV0

Table 1.

Vote pair orderings for three vote rules.

Figure 5 shows that there is an obvious coding gain with increasing N. Actually, the BER curve prequired to give Pb=105versus Nshowing a linear relationship between log pand log N.

Figure 5.

Variation in performance with block length for ( N , M ,15,2) GLDPC codes.

4.2 BCH-based Fossorier decoding algorithm

In [6] GLDPC codes with BCH subcodes (instead of Hamming subcodes) were considered, but for AWGN channel and ML soft decoding due to its higher error-correcting capability. The algorithm presented here also uses the high-rate BCH and RS codes, but as HDD algorithm, and can be efficiently applied in very high-speed (40 GBps) optical systems as the soft information is not available due to optical-electrical conversions [7].

The actions of this algorithm are updated as follows: VN iis considered to be connected to the GCNs jand k. Two messages will be sent from GCN jto VN i. First, it outputs uji(the value of VN i) taken out from the sub-decoder. Second, it outputs Uji(represents data about success or failure of GCN decoding). Ujiis then a binary signaling with estimate 1 if there is a valid word or estimate 0 if there is not. W.r.t the arriving messages from node k, the same action is applied.

The VN message vijdepends on the value received from the channel yi, and the messages received from the GCNs other than node j. Since GLDPC codes of high code rate (J=2) is only concerned, there is only one other GCN k). Hence, the updating rule in the symbol node can be expressed as

vij=yiUki¯+ukiUkiE6

where Uki¯is the complement of Uki. The processes of the decoder are carried out until the satisfaction of all GCNs or until reaching a certain amount of iterations. Finally, any symbol (VN) connected to a satisfied GCN will take its proposed value. If the VN connected to two unsatisfied GCNs, it will take the original received value.

RS-based GLDPC code of rate r=0.467and different lengths are examined ( Figure 6 ). It shows that RS(15,11,5) product code performs better than the corresponding GLDPC of length 225, because it possesses a better minimum distance. As Nincreases, the BER is improved particularly in the region of error floor.

Figure 6.

Performance of GLDPC codes with RS(15,11,5) codes.

5. Modified HDD algorithms for improving the error performance

5.1 Two-side state-aided bit-flipping (TSSA-BF) algorithm

A HDD decoder founded on BF algorithm is presented in [23]. The main view depends on taking advantage of the different sub-decoder states. Therefore it adds this data representing these states as a reliability factor to be utilized for the rest of the decoding process. This additional data (in the form of additional bit) is inserted in two sides (VNs and CNs).

The goal is generally to remove all likely produced trapping sets (that generate non-editable errors) from the code construction. This approach is presently still not obtainable due to constraints in the processing speed and implementation. An alternative approach that fulfills the most of this goal is suggested (with reasonable processing speeds). That approach adds resources only operated in unusual circumstances when the previously mentioned trapping sets happen.

Taking commonness into account and due to its simplicity, the extended Hamming code is studied inside the GLDPC codes.

5.1.1 Failure analysis

In the case of using the ext-Hamming code dmin=4, the sub-decoders of GLDPC code may output errors in both cases of decoding success or failure. At GCN failure case, it cannot clearly locate the error place. In the case of GCN decoding success, the errors may be generated from undiscovered errors (when a received word decoded to non-sent valid ones, i.e., e4) or faulty repair (when e>2). Therefore, the errors at a given GCN can be distinguished by the following names:

  1. Plain single error (element P): one error and true correction take place.

  2. Unknown set (U-set): multiple errors (e>1) with decoder failure (detects but can’t mark errors).

  3. Ambiguous set (A-set): multiple errors (e>2) making the decoder flipping an assumed-correct bit (false correction).

  4. Dark set (D-set): multiple errors (e4) not detected by the decoder which produce zero-syndrome vector.

5.1.2 Algorithm description

As GLDPC code with 1B-construction is studied in [22] as in Figure 7 , a further bit is inserted beside the main bit moving between the VN and GCN. For VNs, it acts as the reliability of its bit value (bit 1 if suspect or bit 0 if assumed correct), and it forwards this additional data to be used by GCNs. For GCNs, this additional bit acts as the power of its decision by raising the reliability levels to 4. The GCN decodes the received word, forwards a signal (bit 1 or 0, namely, flip or keep), and appends this additional bit as the power of this signal (in ascending reliability level arrangement, 1+11,110,000and 0+01, corresponding strong flip, weak flip, weak keep, and strong keep, respectively).

Figure 7.

GLDPC bipartite graph example.

5.1.2.1 Horizontal processing

Specifying the ext-Hamming decoder, there are three states at a given GCN as state “0” in the case of zero syndrome, state “1” in the case of one-error repair, and state “2” in the case of decoder failure.

For any GCN c, c=1,2,,M, let dclbe the cth GCN decoder state at the lth iteration. If dcl=0, the decoder forwards a message (0) to all set elements of its connected VNs, Wc=w1w2..wi..wn. The message (0) with reliability level 3 is forwarded assuming Wcmay contain a dark set (D-set). If dcl=1, the decoder forwards (1+) with level 1 on the assumed-error place wand (0) to the remaining set elements W'c. Elements of W'care given 0(not 0+) assuming that they may contain A-set. Finally, If dcl=2, it sends (1) with level 2 to all elements of Wcwhich contains a U-set.

As illustrated in Figure 8 , let Uc,wil=Uc,wil1Uc,wil2be the two bits representing the outgoing flip message and its reliability, respectively, from GCN cto VN wi. Table 2 illustrates the four possible outgoing messages from GCN cto every connected VN wi.

Figure 8.

Incoming and outgoing messages between GCNs and VNs.

Uc,wil1Uc,wil2Alternative denotationReliability gradeMessage meaning
1 11+1Strong flip
1 0l2Weak flip
0 003Weak keep
0 10+4Strong keep

Table 2.

Possible outgoing messages from GCN cto any connected VN.

Let Vc,wil=Vc,wil1Vc,wil2be the two bits representing arriving bit value and its reliability, respectively, at GCN cfrom VN wi. For any GCN c, let initial reliability bit be Vc,wi02=0for all wiWc. As previously mentioned, Vc,wil2=1if a suspect bit and 0 if assumed correct one.

Now a local GCN counter will be introduced to compare the present GCN state with the one of previous iteration. Let αclbe the number of consecutive previous repetitions of the state dcl, and let βclbe the number of incoming suspects among the n bits connected to GCN c. According to αcl,βclvalues and the additional information Vc,wil2, the algorithm can improve its decision, and the horizontal process iteratively continues as illustrated in [23].

For dcl=0, the counter role is to enhance the reliability from 0to 0+if the state remains for two consecutive iterations. For any GCN cand dcl=2, if the message Vc,wil2from the bit wiindicates a suspected bit and the decoder state (dcl=2) remains for three consecutive iterations, the decoder recalculates the syndrome after flipping this suspect. If the syndrome check is satisfied (i.e., valid codeword), the decoder estimates that bit as error and degrades its reliability from 1to 1+.

5.1.2.2 Vertical processing

With four reliability levels and J=2, there will be a set of 10 possible combinations of incoming messages at VN w, w=1,2,,N. This set can be divided, according to the failure analysis, into three subsets sii=1,2,3. For any VN w, its reliability state rwlis determined based on its incoming messages (from GCNs cj, with j=12) to which subset it belongs:

s1=1+1+1+11+0,s2=11100+1+,s3=000+10+00+0+
rwl=0ifUcjwlj=12s11ifUcjwlj=12s22ifUcjwlj=12s3

The VN wwith least-reliable level, rwl=0, needs to be flipped. For rwl=1, VN state counter is appointed to make a comparison between the VN current reliability state and the one of the previous iteration. Let γwlbe the number of consecutive previous repetitions of the state rwl. With rwl=1and according to γwlvalues, the VN will not be flipped but counted as a suspected bit. It sends such reliability information Vcjwl2=1j=12to GCNs to be taken into account. For rwl=2, the VN is considered a reliable bit and kept with Vcjwl2=0,j=1,2(i.e., assumed correct bit).

Figures 9 11 show the block diagrams of the overall decoder, horizontal process, and vertical process, respectively. Table 3 illustrates an example for ext-Hamming (8,4) constituent decoder employed at GCN cn=8at lth iteration as the shaded parts represent certain conditions satisfied.

Figure 9.

Block diagram of the overall TSSA-BF decoder.

Figure 10.

Block diagram of the horizontal process of the TSSA-BF decoder.

Figure 11.

Block diagram of the vertical process of the TSSA-BF decoder.

Table 3.

Example of ext-Hamming (8,4) constituent decoder employed at GCN cat lth iteration.

5.1.3 Important notes on the algorithm

  • The output messages from VN wto its two connected GCNs cj,j=1,2are the same (i.e., Vc1wl=Vc2wl).

  • The initial incoming message at GCN cVcjw01=yw,Vcjw02=0,j=1,2as the overall demodulated binary sequence Y=yww=12Nyw01.

  • Ucwil=Ucwil1Ucwil2is the outgoing message from GCN cto VN wiconsisting of two bits representing the reliability level (one of four possible values 0+, 0, 1, or 1+).

  • The GCN decoder does not output actual decoded words to its connected VNs. Instead, it sends a reliability signal (taking a value of four possible values) which is represented by two bits Ucwil1and Ucwil2. On the other hand, the VN has to take a decision based on its incoming messages. The decision is (Flip), (Keep but as suspect) or (Keep as assumed correct).

  • The function of GCN state counter αclor VN state counter γwlis to count the number of consecutive iterations with the same state (at this GCN or VN) up to this present iteration l, respectively.

Figure 12 is showing the BER performance of the ext-Hamming-based GLDPC code (with overall rate R=0.625) by the TSSA-BF algorithm compared to HD decoder BF algorithms in [7, 22] and SD chase sub-decoder (number of LRPs p=2). The finite-length 1B-construction-GLDPC codes of block length N = 4096 is used, and the maximum number of iterations (Imax) is set to 20. It is noted that this algorithm outperforms the other HDD ones along various values of Eb/Nowith gain not <0.5 dB at the expense of a little increase in resources used by the algorithm.

Figure 12.

Performance of GLDPC with (32,26) ext-Hamming subcodes.

5.2 Classification-based algorithm for BF decoding with initial soft information

This algorithm is a modern bit-flipping decoding approach [24]. It is established on taking advantage of the fast BF HDD method with the help of the data extracted from the AWGN channel.

However it exploits this data at only the start phase of the decoding intentionally to make a certain classification operation. This algorithm also improves its performance by adding an additional bit in the arriving messages at VNs from CNs as a technique to enhance the decision reliability at both VNs and GCNs. The main role of this additional bit is to benefit from the subcodes states as in [23] but with a distinct fashion. This approach allows for considerable enhancement in BER at the expense of additional resources at only the side of VNs. SDD is characterized by complexity and the need to a large amount of real calculations (according to the channel soft information) all during the whole decoding procedure. However, this algorithm (accounted as HDD) needs them only in the start phase, and all processed data thereafter are hard values. Therefore this technique could reduce a significant part of the computational complexity, which was noticed in [23].

5.2.1 Algorithm description

The trapping sets, producing unrepaired errors, form the major part of the error performance letdown of the bipartite graph-based codes. The goal here is to diminish the damaging effect of most of the generated sets even by inserting supplemental resources which will be discussed below in this section.

The algorithm uses the soft channel values at the beginning of the decoding to classify the received symbols (VNs) by a predetermined threshold. Taking commonness into account and due to its simplicity, the extended Hamming code is studied inside the GLDPC codes. The extended Hamming code with increased dmindmin=4is powerful and suitable for constructing standard-relevant GLDPC codes. The ext-Hamming sub-decoders may produce errors in both cases, decoding success and failure. At the GCN sub-decoder failure, it cannot locate the places of errors. At the GCN sub-decoder success, the decoder errors may emerge from two reasons: the undiscovered errors (as the received word decoded to non-transmitted valid one (e4), where e is the number of errors at the input of the local decoder) and the false repair (e>2).

An additional bit is inserted next to the main bit in the message from the GCN to a connected VN. It acts as the decision power of GCN by raising the reliability from two to four levels. The GCN sub-decoder decodes the received word and forwards two bits (the main bit and the additional one) to every connected VN. If the main bit is seen as a decision (flip (1) or keep (0)), the additional one is seen as the decision power (strong (1) or weak (0)). The four reliability levels in descending arrangement are 0+(01), 0(00), 1(10), and 1+(11), corresponding to strong keep, weak keep, weak flip, and strong flip, respectively. This decoding contains two processes, the GCN processing and the VN processing, as will be explained below.

5.2.1.1 GCN processing

The three possible states, in which the ext-Hamming sub-decoder at a given GCN can be one of them, are defined as follows:

  1. State 0: when the syndrome gives zero (i.e., the received sequence is a valid codeword).

  2. State 1: is the case of one-error repair when the syndrome vector is one of the subcode parity-check matrix columns (i.e., error discovered and can be corrected). Therefore, it decodes to the right transmitted codeword or decodes to another valid codeword.

  3. State 2: at the decoder failure (errors detected and cannot be corrected).

Using the same notations as in Figure 8 , for any GCN c, c=1,2,,M, let dclbe the decoder state of the cth GCN at the lth iteration. The procedures of the GCN sub-decoder of this algorithm are illustrated below:

  • If dcl=0, it sends 0+to all elements of the connected VNs set, Wc={w1, w2,.., wi,.., wn}. The message 0+is the highest reliability level.

  • If dcl=1, it sends 1+(level 1) on the place b(an assumed-error bit) and 0(level 3) to the rest of set elements W'c. Elements of W'care given 0(not 0+) assuming some errors may be involved (with e>2) making the decoder perform a wrong repair (an assumed-correct bit is flipped).

  • If dcl=2, it sends 1(level 2) to all of Wcelements as they contain a set of errors (with e>1) leading to a decoder failure (errors detected with no repair capability).

Let Uc,wil=[Uc,wil1Uc,wil2]be the two bits which represent the outgoing decision message and its power, respectively, from GCN a to VN wi. Let Vc,wilbe the incoming binary bit value of the constituent codeword at cfrom VN wi.

The overall set of Nhard demodulated sequence bits is Y=yww=12Nyw01as yw=12sgnrw+1and rwis the soft value of the wth bit in the received sequence from AWGN channel. For any VN w, the initial values Vcjw0=ywfor j=1,2. Therefore at any GCN c, the initial values Vc,wi0=ywifor i=1,2,,n. Table 4 illustrates an example for ext-Hamming (8,4) constituent decoder employed at GCN c(with n=8) at lth iteration.

Table 4.

Output messages at GCN cwith ext-Hamming (8,4) decoder.

5.2.1.2 VN processing

For any VN, it is represented by two bits. The main bit is the symbol binary value. The additional bit represents the initial reliability of the symbol value, (1) if a suspect bit or (0) if an assumed-correct bit, and the VN will use this extra information as will be discussed later. The codeword symbols which are represented by VNs are classified into two categories: most-reliable bits (MR) and least-reliable bits (LR). The classification is only initiated according to the soft information received through the channel based on a predetermined threshold.

For any transmitted codeword of length N, the wth code bit vw01are mapped to xw11, respectively, and transmitted over AWGN channel which is characterized by the probability density function (pdf) pr/xgiven by

prw/xw=12πσ2exprwxw2/2σ2E7

where σ2is the variance of the zero-mean Gaussian noise nwthat the channel adds to the transmitted value xw(so that rw=xw+nw) [25].

As illustrated in Figure 13 , let ηobe the standard threshold on which the hard demodulator decision is based. For BPSK over AWGN channel, ηo=0and at this value

Figure 13.

The threshold η c over AWGN channel.

pr/x=1=pr/x=1E8

Let δrbe the absolute difference between the two probabilities as

δr=pr/x=1pr/x=1E9

The received symbol is assumed to be accounted as LR bit if its value rwgets near to the zero point or ηo(δ=0). The value of rwith maximum difference δmaxcan be taken as a second point ηmthat the received symbol is accounted as MR bit if its value rwapproaches it. The absolute of the second point ηmis the same for both ±rwvalues as the two probability density functions are symmetric around the zero point. The equation δ'rr=ηm=0should be solved to get ηm:

δ=12πσ2er12/2σ2er+12/2σ2E10

then

δrr=ηm=12πσ2[1rσ2er12/2σ2E11
1+rσ2er+12/2σ2]=0E12

therefore

1ηmeηmσ2=1+ηmeηmσ2E13

This equation can be solved numerically by Newton-Raphson method and for various values of σ2(0.1–0.9), ηm1.04.

The classification threshold ηcfor this algorithm is set to be in the middle between the two points. Therefore ηc=ηo+ηm2=0+1.042=0.52. Denote the initial reliability of the wth received bit as λw. According to the algorithm, this bit is classified as MR (λw=0) if rwηc; else it is classified as LR (λw=1).

Using column weight of two and four levels of reliability, there are 10 probable combinations of these incoming messages to VN w, w=1,2,,N. These combinations are categorized into three subsets sii=1,2,3. For any VN w, its reliability state gwlis set according to the arriving messages (belong to which subset). Motivated by TSSA-BF in [8] with inserting the new parameter λw

s1=1+1+1+11+0,s2=11100+1+,s3=000+10+00+0+
gwl=0ifUcjwlj=12s11ifUcjwlj=12s22ifUcjwlj=12s3

  • The VN wwith least reliability, gwl=0, needs flipping immediately.

  • For gwl=1, VN state counter is employed to compare the VN present in reliability state gwlwith one of the previous iterations gwl1. Let γwlbe the number of previous successive repetitions of this state gwl. If gwl=1with γwl=2and, in the same time, λw=1(i.e., it is considered as LR bit), the VN will be flipped.

  • Else, the VN is assumed a correct bit and kept without flipping.

By using the previously mentioned rules, the messages are renewed, and the algorithm proceeds until a zero overall syndrome output or it reaches a predefined number of iterations.

It is worth emphasizing that the GCN decoder does not output actual decoded word to its connected VNs. Instead, it sends a reliability signal (taking a value of four possible values) which is represented by two bits Uc,wil1and Uc,wil2. On the other hand, the VN has to take a decision (flip or keep) based on its incoming messages and its initial reliability λw(MR or LR). The function of VN state counter γwlis to count a number of consecutive iterations with the same state gwl(at this VN) up to this present iteration (l).

Figures 14 16 show the block diagrams of the overall decoder, horizontal process, and vertical process, respectively.

Figure 14.

Block diagram of the overall classification-based decoder.

Figure 15.

Block diagram of the horizontal process of the classification-based decoder.

Figure 16.

Block diagram of the vertical process of the classification-based decoder.

5.2.2 Important notes on the algorithm

  • The output messages from VN wto its two connected GCNs cj,j=1,2are the same (i.e., Vc1wl=Vc2wl).

  • The initial incoming message at GCN cVcjw0=yw,j=1,2is the demodulated bit Vw0as the overall demodulated binary sequence Y=yww=12Nyw01.

  • Ucwil=Ucwil1Ucwil2is the outgoing message from GCN cto VN wiconsisting of two bits representing the reliability level (one of four possible values 0+, 0, 1, or 1+). On the other hand, Vcjwlis the outgoing message from VN wto GCN cjcontaining just the decoded symbol bit value.

  • The GCN decoder does not output actual decoded words to its connected VNs. Instead, it sends a reliability signal (taking a value of four possible values) which is represented by two bits Ucwil1and Ucwil2. On the other hand, the VN has to take a decision based on its incoming messages. The decision is flip or keep.

  • The function of VN state counter γwlis to count the number of consecutive iterations with the same state (at this VN) up to this present iteration l.

  • The algorithm manages without the greater portion of the overhead of the algorithm in [23] which was specially located in the horizontal (GCN) process.

Figure 17 shows the GLDPC BER performance using the (32,26,4) extended Hamming subcode by this decoding with respect to the bit-flipping algorithms in [7, 22] and [23]. It is noticed that this algorithm surpasses the other ones at the cost of a slight increase in computational complexity resulting from the comparison operations made at the initial classification step. It is also noticed that as N increases, a slow improvement in the performance is achieved.

Figure 17.

Simulated BER curves of N ,2,32 GLDPC codes.

The predefined number of iterations (20) is found to be very sufficient for good performance as the additional iterations beyond this limit have no considerable difference in the performance and latency in the decoding process which should be avoided for fast decoding purposes.

Not similar to the conventional GLDPC HDD BF decoding, the received sequence soft values are utilized to make appropriate classification of the received bits (variable nodes) into two classes.

The algorithm not only achieves a better error performance but also requires less iterations than the other competent algorithms. In terms of the impacts of the soft information (from AWGN channel) on coding gain of the GLDPC, the algorithm is revealed to exhibit considerable performance to decoder complexity trade-off. The algorithm can be adapted to handle generalized and more robust subcodes with the capability to correct more errors to improve the performance.

As discussed in [24], the computational complexity is provided in terms of the average number of executed operations for this algorithm against the rather comparable TSSA-BF algorithm. It is noticed that the complexity of this decoder is reduced by more than 60%.

6. Simplified SDD algorithm over AWGN channels

The algorithm, in [26], serves to use the chase SD decoders as minimum as possible to lower their complexity and expedites the decoding procedures. This algorithm is a variant approach from a previous one by [27] to lower the complexity of turbo product code (TPC) with multiple-error correction BCH subcodes. The chase decoder at every row or column input sequence in the product code was used as it attempts to decrease the HDD operations executed on the test patterns (TPs) produced in the chase decoder. The algorithm, explained below, will benefit from the algorithm in [27] for more reduction in the complexity.

The introduced algorithm is the MP method for decoding GLDPC with the chase-II algorithm operated as a posteriori probability decoding on GCNs. It will use extended double-error BCH (with high error-correcting capability) as a subcode to obtain a better performance. For simplicity, all GCNs are represented with the same eBCH code of parameters nkd. The overall block diagram of this algorithm is depicted in Figure 18 .

Figure 18.

The block diagram of the lowered-complexity chase-based decoding algorithm.

As discussed before in Section 3 and using the same notations and considerations, the soft-output value of every decoded symbol of the subcode should be calculated, by Eqs. (3) or (4), to be sent back on the connected edges to the GLDPC VNs as followed by the MP algorithm in an iterative method to obtain a final decision after a certain number of iterations or a syndrome condition should be satisfied.

W.r.t any given GCN c, the chase-II-based SISO decoder produces 2pTPs by making a perturbation of the pLRPs in the demodulated word with length n(subcode word). Therefore 2pHDDs should be performed to obtain a decided codeword. Therefore algorithm will get the syndromes of Yc.

For extended BCH2 (double-error correction), the algorithm computes two syndromes Sc1and Sc3as follows:

Sc1=yc2yc3xycn1xn3ycnxn2x=α,Sc3=yc2yc3xycn1xn3ycnxn2x=α3E14

where αis the primitive element of GF(2m) that generates the BCH code polynomial.

According to the values of the syndromes as illustrated in Table 5 , the algorithm estimates the number of errors contained in the sequence.

Syndrome of demodulated vector Sa=Ya.HbchNumber of contained errors (e)Action taken (method of estimating the decision Da)Calculation model of extrinsic information ra,i
Sa1=Sa3=00Nothing (the demodulated vector is the decision codeword)ra,i=βxdi
Sa1=0,Sa30>2Apply TP-reduced chase algorithm [12]Pyndiah model [15]
Sa1Sa3=01Apply HDD (Berlekamp-Massey algorithm)ra,i=βxdi
Else2Apply HDD (Berlekamp-Massey algorithm)ra,i=βxdi

Table 5.

The actions of the proposed algorithm.

If there are no errors (e=0), it is likely (with high percentage) that the demodulated word is the valid transmitted one and the decoder will not do its task. If 0<e2, the algorithm may execute the HDD (Berlekamp-Massey algorithm) and outputs the decoding decision. In these two preceding cases, the soft-output values can be estimated as the decision is highly probable to be correct as follows:

rc,i=β×dc,iwithβ0

where βis chosen to be evolved with the decoding iterations, βl=0.4,0.6,0.8,1,1,1.

If e>2, the chase algorithm is needed to extract a decision codeword but will not decode a complete list of 2ptest patterns (TPs). The proposed algorithm in this case will benefit from the lowered-complexity TP-reduced algorithm in [27]. The amount of reduction in HDDs of the algorithm compared to the standard one is listed in Table 6 .

BCH code (n,k)NJCode rateNo. of LRPs(p)Number of HDDs in standard alg. [7]Avg. number of HDDs in proposed alg.Percentage of complexity reduction (%)
eBCH2 (64,51)409620.635120307260
eBCH2 (64,51)409620.6410,240573456
eBCH3 (64,45)409620.41410,240523251.1
e8CH3 (64,45)409620.41520,480901144

Table 6.

The reduction of HDDs in the lowered-complexity chase-based decoding algorithm (SNR = 2 dB at Imax=5).

The computational complexity of this algorithm is estimated by the number of hard decision decoding processes (Berlekamp-Massey algorithm) employed at GCNs. The (64,51) eBCH subcode is chosen with double-error correction capability to exploit the multiple calculated syndroms, while keeping a moderate code rate (R ≅ 0.6). Therefore, for keeping this rate, only GLDPC codes with column weight (j=2) are considered. As shown in Figure 19 , the number of HDDs in the decoder is calculated for two numbers of LRPs (p=3,p=4) and up to five iterations (Im=5). For clarification, the number of HDDs is normalized to the one of the conventional chase decoder. It is shown that a considerable reduction occurs especially after Eb/No=2 dB.

Figure 19.

Comparison of computational complexity of less-complex and conventional SISO decoding algorithms for decoding (64,51) eBCH-based GLDPC codes with length N = 4096 for various values of p and I m .

The results show a significant lowering in the soft decoding operations executed at GCNs compared to conventional chase decoders with little wastage in the BER performance. This scheme is highly required in low error rate applications such as optical communication systems.

How to cite and reference

Link to this chapter Copy to clipboard

Cite this chapter Copy to clipboard

Sherif Elsanadily (September 23rd 2019). Generalized Low-Density Parity-Check Codes: Construction and Decoding Algorithms, Coding Theory, Sudhakar Radhakrishnan and Muhammad Sarfraz, IntechOpen, DOI: 10.5772/intechopen.88199. Available from:

chapter statistics

151total chapter downloads

More statistics for editors and authors

Login to your personal dashboard for more detailed statistics on your publications.

Access personal reporting

Related Content

This Book

Next chapter

Polynomials in Error Detection and Correction in Data Communication System

By Charanarur Panem, Vinaya Gad and Rajendra S. Gad

Related Book

First chapter

Scalable Video Coding

By Z. Shahid, M. Chaumont and W. Puech

We are IntechOpen, the world's leading publisher of Open Access books. Built by scientists, for scientists. Our readership spans scientists, professors, researchers, librarians, and students, as well as business professionals. We share our knowledge and peer-reveiwed research papers with libraries, scientific and engineering societies, and also work with corporate R&D departments and government entities.

More About Us