complexity of the algorithm Example 4.8.4:[Johnson] 4.8.3 Decoding of LDPC codes In his Ph.D.thesis of 1961,Gallager also presented two iterative decoding algorithms for LDPC codes.One is for hard-decision decoding.and another for soft-decision decoding Since that time,other researchers have independently discovered that algorithm and relate algorithms,albeit sometimes for different applications.Now,there are various methods fo decoding LDPC codes,ranging from low to high decoding complexities and from reasonably good to very good error performance.These methods include One-step majority logic(OSML)decoding. ■Bit.fni :(BF)dec Iterative decoding based on message passing algorithm (IDMPA).(The term "message passing algorithm"usually refers to the sum-product algorithm,the belief propagation algorithm and their approximations.) these me nods.OSML and BF decodings are hard-decision decodings.Weighted liability-ba ed decoding method.IDMPA is a soft-in soft out(SISO) decoding method,which is actually the sum-product algorithm working on the code's Tanner graph,as discussed in Section 4.7.The OSML decoding is the simplest in terms of decoding complexity.IDMPA provides the best performance but requires higher computational complexity.In the following.we will first outline two hard-decis on decoding algorithms. 4.8.3.1 OSML Decoding of regular LDPC codes Consider a (dd)-regular LDPC code C of length n given by the null space of a qxn parity-check matrix H with column and row weights d,and d,respectively.Let h,h2.,h be the rowsof H.For each code bit position,due to the RC-constraint,there are a set A={h”,h,h} of d,rows in H such that:(1)each row in A,has a 1-component at position /and (2)no two rows in A have a common 1-component at any other position.See the figure below. the /th column 「.001107 0011 A1= 1010. Clearly,the rows in A are orthogonal on the bit position/. Suppose a codeword e=(coC)in Cis transmitted and11 complexity of the algorithm. Example 4.8.4: [Johnson] 4.8.3 Decoding of LDPC codes In his Ph.D. thesis of 1961, Gallager also presented two iterative decoding algorithms for LDPC codes. One is for hard-decision decoding, and another for soft-decision decoding. Since that time, other researchers have independently discovered that algorithm and related algorithms, albeit sometimes for different applications. Now, there are various methods for decoding LDPC codes, ranging from low to high decoding complexities and from reasonably good to very good error performance. These methods include: „ One-step majority logic (OSML) decoding; „ Bit-flipping (BF) decoding; „ Weighted BF decoding; „ Iterative decoding based on message passing algorithm (IDMPA). (The term “message passing algorithm” usually refers to the sum-product algorithm, the belief propagation algorithm and their approximations.) Among these methods, OSML and BF decodings are hard-decision decodings. Weighted BF decoding is a reliability-based decoding method. IDMPA is a soft-in soft-out (SISO) decoding method, which is actually the sum-product algorithm working on the code’s Tanner graph, as discussed in Section 4.7. The OSML decoding is the simplest in terms of decoding complexity. IDMPA provides the best performance but requires higher computational complexity. In the following, we will first outline two hard-decision decoding algorithms. 4.8.3.1 OSML Decoding of regular LDPC codes Consider a (dv, dc)-regular LDPC code C of length n given by the null space of a q × n parity-check matrix H with column and row weights dv and dc, respectively. Let h1, h2, ., hq be the rows of H. For each code bit position l, due to the RC-constraint, there are a set { } () () () 1 2 , ,., v ll l A hh h l d = of dv rows in H such that: (1) each row in Al has a 1-component at position l; and (2) no two rows in Al have a common 1-component at any other position. See the figure below. 00110 0011 1010 l ⎡ ⎤ ⎢ ⎥ = ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎣ ⎦ A " " # ### " " Clearly, the rows in Al are orthogonal on the bit position l. Suppose a codeword 01 1 ( , ,., ) n cc c = − c in C is transmitted and the lth column