长 目< + = Figure 4.8.4 Normal graph of a regular LDPC code withd=3 andd=6. 4.8.2 Encoding of LDPC Codes 如前所述，LDC码是一种线性分组码，其编码可以按照一般线性分组码的编码原 理进行，即首先通过Gauss-Jordan消去法将给定的校验矩阵H变换为如下形式： H=[P I-] where P is a (nk)xk binary matrix and is the identity matrix of size n-k.Then the generator matrix in systematic form is obtained G=「LP] Thus.the encoding of the code defined by H can be performed via c=uG=u uPT] (4.4) Example 4.8.3:Consider the encoding of the length-10 rate-1/2 LDPC code [Johnson,pp.15] 「1101100100 0110111000 H=0001000111 1100011010 0010010101 First,we put H into row-echelon form(ie.so that in any two successive rows that do no consist entirely of zeros,the leading 1 in the lower row occurs further to the right than the leading I in the higher row). The matrix H is put into this form by applying elementary row operations in GF(2). 6
6 Figure 4.8.4 Normal graph of a regular LDPC code with dv = 3 and dc = 6. 4.8.2 Encoding of LDPC Codes 如前所述，LDPC码是一种线性分组码，其编码可以按照一般线性分组码的编码原 理进行，即首先通过Gauss-Jordan消去法将给定的校验矩阵H变换为如下形式： H PI = [ n k − ] where P is a ( ) nk k − × binary matrix and In-k is the identity matrix of size n-k. Then the generator matrix in systematic form is obtained T k = ⎡ ⎤ GIP ⎣ ⎦ Thus, the encoding of the code defined by H can be performed via T = = ⎡ ⎤ ⎣ ⎦ c uG u uP (4.4) Example 4.8.3: Consider the encoding of the length-10 rate-1/2 LDPC code [Johnson, pp.15] 1101100100 0110111000 0001000111 1100011010 0010010101 ⎡ ⎤ ⎢ ⎥ = ⎣ ⎦ H First, we put H into row-echelon form (i.e. so that in any two successive rows that do not consist entirely of zeros, the leading 1 in the lower row occurs further to the right than the leading 1 in the higher row). The matrix H is put into this form by applying elementary row operations in GF(2)
which are:interchanging two rows or adding one row to another modulo 2.From linear operations the modified parity-check matrix will have the set as the original. The 1-st and 2-nd columns of H already have ones on the diagonal and entries in these columns below the diagonal are removed by replacing the 4-th row with the modulo-2 sum of the 1-st and 4-th rows.The 3-rd column of H does not have a one on the diagonal but this can be obtained by swapping the 3-rd and 5-th rows.Finally,replacing the 5-th row with the modulo-2 sum of the 5-th and 4-th rows gives H,in row-echelon fo 110.1100100 0110111000 H,=0010010101 0001111110 0000111001 Next the parity-check matrix is put into reduced row-echelon form (i.e.so that any column that contains a leading one has zeros everywhere else).The 1-st column is already correct and the entry in the 2-nd column above the diagonal is removed by replacing the 1-st ws.Similarly the er in the 3-nd column and 3-rd rows.To clear the 4-th column the 1-st row is replace with the modulo-2 sum of the 1-st and 4-th rows.Finally,to clear the 5-th column involves adding the 5-th row to the 1-st, 2-nd and 4-th rows gives H,in reduced row-echelon form: [1000001110 0100010100 H,=0010010101 0001000111 000011100 Lastly,using column permutations we put the parity-check matrix into standard form 011 1010000 1000 010 100100 (4.5) 01 1 1 00010 1100100001 from which a generator G for the code (with parity-check matrices H)can be obtained by the relation stated above. In this final step column permutations have been used and so the codewords of Hatd will π=[67891012345] and apply the inverse permutation to each Ha codeword before it is transmitted.这样，在接 收端我们可仍然使用H进行译码
7 which are: interchanging two rows or adding one row to another modulo 2. From linear algebra we know that by using only elementary row operations the modified parity-check matrix will have the same codeword set as the original. The 1-st and 2-nd columns of H already have ones on the diagonal and entries in these columns below the diagonal are removed by replacing the 4-th row with the modulo-2 sum of the 1-st and 4-th rows. The 3-rd column of H does not have a one on the diagonal but this can be obtained by swapping the 3-rd and 5-th rows. Finally, replacing the 5-th row with the modulo-2 sum of the 5-th and 4-th rows gives Hr in row-echelon form: 1101100100 0110111000 0010010101 0001111110 0000111001 r ⎡ ⎤ ⎢ ⎥ = ⎣ ⎦ H Next the parity-check matrix is put into reduced row-echelon form (i.e. so that any column that contains a leading one has zeros everywhere else). The 1-st column is already correct and the entry in the 2-nd column above the diagonal is removed by replacing the 1-st row with the modulo-2 sum of the 1-st and 2-nd rows. Similarly the entry in the 3-nd column above the diagonal is removed by replacing the 2-nd row with the modulo-2 sum of the 2-nd and 3-rd rows. To clear the 4-th column the 1-st row is replace with the modulo-2 sum of the 1-st and 4-th rows. Finally, to clear the 5-th column involves adding the 5-th row to the 1-st, 2-nd and 4-th rows gives Hr in reduced row-echelon form: 1000001110 0100010100 0010010101 0001000111 0000111001 r ⎡ ⎤ ⎢ ⎥ = ⎣ ⎦ H Lastly, using column permutations we put the parity-check matrix into standard form: std 0111010000 1010001000 1010100100 0011100010 1100100001 ⎡ ⎤ ⎢ ⎥ = ⎣ ⎦ H (4.5) from which a generator G for the code (with parity-check matrices Hstd) can be obtained by the relation stated above. In this final step column permutations have been used and so the codewords of Hstd will be permuted versions of the codewords corresponding to H. A solution is to use a permutation vector to keep track of the column permutation used to create Hstd, which in this case is π = [6 7 8 9 10 1 2 3 4 5] and apply the inverse permutation to each Hstd codeword before it is transmitted. 这样，在接 收端我们可仍然使用H进行译码
Alternatively,if the channel is memoryless,and so the order of codeword bits is unimportant,a far easier option is to apply to the original Hto give a parity-check matrix 「00100110117 1100001101 H=0011100010 1101011000 1010100100 with the same properties as H but which shares the same codeword bit ordering as Had.在接 收端，我们使用H'对由G编出的码字进行译码。 All of this processing can be done off-line and just the matrices G and H'provided to the encoder and decoder respectively. The drawback of this approach is that,unlike H,the matrix G will most likely not be sparse and so the matrix multiplication in (4.4)have complexity in the order of noperations. 随着码长n的增加，编码复杂度会变得非常高。Richarson and Urbanke于2001年提出了 一种直接基于H矩阵的编码方法Richarson200L,T,它具有近似线性编码复杂度。另 种降低编码复杂度的方法是基于代数或几何方法构造LDPC码，这种结构化的校验矩阵 通常能够允许编码器采用简单的移位寄存器实现。下面我们首先介绍U的方法，具有 准循环H矩阵结构的QC-LDPC码编码方法见[19，Li-Lin2006]。 4.8.2.1 (Almost)Linear-Time Encoding of LDPC Codes Rather than finding a generator matrix for H,an LDPC code can be encoded using the matrix din 。uer ndinbok ng prior to encoding Firstly,we perform the following preprocessing steps.By row and column permutations, we bring H into the approximate lower triangular form as indicated in Fig.4.8.5,where the upper right comer can be identified as a lower triangular matrix.Because it is obtained only where T is a (m-g)x(m-g)lower triangular matrix with ones along the diagonal and hence is invertible.If H is full rank,the matrix B is of size (m-g)xg and A is of size (m-g)xk.The g rows of H left in C.D.and E are called the gap of this approximate representation.The smaller g the lower the encoding complexity for the LDPC code
8 Alternatively, if the channel is memoryless, and so the order of codeword bits is unimportant, a far easier option is to apply π to the original H to give a parity-check matrix 0010011011 1100001101 0011100010 1101011000 1010100100 ⎡ ⎤ ⎢ ⎥ ′ = ⎣ ⎦ H with the same properties as H but which shares the same codeword bit ordering as Hstd. 在接 收端，我们使用H’对由G编出的码字进行译码。 All of this processing can be done off-line and just the matrices G and H′ provided to the encoder and decoder respectively. The drawback of this approach is that, unlike H, the matrix G will most likely not be sparse and so the matrix multiplication in (4.4) have complexity in the order of n 2 operations. 随着码长n的增加，编码复杂度会变得非常高。Richarson and Urbanke 于2001年提出了 一种直接基于H矩阵的编码方法[Richarson2001, IT]，它具有近似线性编码复杂度。另一 种降低编码复杂度的方法是基于代数或几何方法构造LDPC码，这种结构化的校验矩阵 通常能够允许编码器采用简单的移位寄存器实现。下面我们首先介绍R-U的方法，具有 准循环H矩阵结构的QC-LDPC码编码方法见[19, Li-Lin2006]。 4.8.2.1 (Almost) Linear-Time Encoding of LDPC Codes Rather than finding a generator matrix for H, an LDPC code can be encoded using the parity-check matrix directly by performing some preprocessing prior to encoding (transforming it into upper triangular form and using back substitution). Firstly, we perform the following preprocessing steps. By row and column permutations, we bring H into the approximate lower triangular form as indicated in Fig. 4.8.5, where the upper right comer can be identified as a lower triangular matrix. Because it is obtained only by permutations, the H matrix is still sparse. We denote the permutation decomposition as ⎡ ⎤ = ⎢ ⎥ ⎣ ⎦ ABT H CDE where T is a ( ) ( ) mg mg −× − lower triangular matrix with ones along the diagonal and hence is invertible. If H is full rank, the matrix B is of size ( ) mg g − × and A is of size ( ) mg k − × . The g rows of H left in C, D, and E are called the gap of this approximate representation. The smaller g the lower the encoding complexity for the LDPC code
-m-g- Figure 4.8.5 Then Gauss-Jordan elimination is applied to clear E.which is equivalent to multiplying H on the left by the matrix 「1-g0 -ET-I This gives ft-Lu-r 01「A B T] L-ET 1JH-ETA+C -ETB+D 0 Note that is the parity check To encode a message vector u of length k using H,we write the codeword c as c=u P:P2] where p and p contain the first g parity bits and the remaining parity bits,respectively.The parity-check equation c=0gives rise to two equations. Au+Bp:+Tpz=0 (4.6) and (-ET-A+C)u+(-ET-B+D)p,=0 (4.7) Let C=-ET-A+C and D=-ET-B+D.If D is nonsingular (invertible),we have from (4.7) P:=-D-Cu (4.8) If D is not invertible,the columns of H can be permuted to obtain a non-singular D.The matrix -D-C can be pre-computed and saved,so that Pi can be computed with a complexity of (g(n-m))
9 1 0 A 1 1 1 1 1 1 B C D E T n - m g m - g m - g g m Figure 4.8.5 Then Gauss-Jordan elimination is applied to clear E, which is equivalent to multiplying H on the left by the matrix 1 M g g − − ⎡ ⎤ ⎢ ⎥ −⎣ ⎦ I 0 ET I This gives 1 1 1 M g g − − − − ⎡ ⎤ ⎡ ⎤ = = ⎢ ⎥ ⎢ ⎥ ⎣ ⎦ − ⎣− +− + ⎦ I 0 A BT H H ET I ET A C ET B D 0 Note that H is the parity check matrix for an equivalent code. To encode a message vector u of length k using H , we write the codeword c as c up p = [ 1 2 ] where p1 and p2 contain the first g parity bits and the remaining parity bits, respectively. The parity-check equation T cH 0 = gives rise to two equations, 1 2 Au Bp Tp + + = 0 (4.6) and ( ) ( ) 1 1 1 − − − + +− + = ET A C u ET B D p 0 (4.7) Let −1 C ET A C =− + and −1 D ET B D =− + . If D is nonsingular (invertible), we have from (4.7) 1 1 − p D Cu = − (4.8) If D is not invertible, the columns of H can be permuted to obtain a non-singular D . The matrix −1 −D C can be pre-computed and saved, so that p1 can be computed with a complexity of O gn m ( ) ( ) −
Once Pi is known,p2 can be found from (4.6)by P2=-T-(Au+Bp,) (4.9) Since T is lower triangular.p can be found by using back substitutuin. Note that column permutations were used to obtain approximate lower triangular H from the original parity-check matrix H,so either H,or实施相同列置换之后的H'(H'with the same column permutation applied),will be used at the decoder. The process of computing p and p2 constitutes the encoding process.The steps for the computation as well as their computational complexity are outlined here(assuming that the preprocessing steps have already been accomplished).For the sake of clarity,intermediate variables are used to show the steps which may not be necessary in a final implementation. Steps to compute P:=-D-(-ET-A+C)u Operation Comment Complexity X=Au Multiplication by a sparse matrix O(n) x=T-x Solve Tx2=x by backsubstitution O(n) X;=-Ex2 Multiplication by a sparse matrix x=Cu Multiplication by a sparse matrix O(n) Addition 0() P=-D-x Multiplication by dense gxg matrix 0g) Steps to compute p2 =-T-(Au+Bp,) Operation Comment Complexity x,=Au Multiplication by a sparse matrix (already 0 done) Xo=Bp Multiplication by a sparse matrix O(n) X7=X1+X6 Addition O(n) P:=-T-x. Solve Tp2=x7by backsubstitution On) The overall algorithm is O(n+g).Clearly,the smaller g can be made.the lower the 10
10 Once p1 is known, p2 can be found from (4.6) by 1 2 1 ( ) − p T Au Bp =− + (4.9) Since T-1 is lower triangular, p2 can be found by using back substitutuin. Note that column permutations were used to obtain approximate lower triangular H from the original parity-check matrix H’, so either H, or 实施相同列置换之后的 H’ （H’ with the same column permutation applied）, will be used at the decoder. The process of computing p1 and p2 constitutes the encoding process. The steps for the computation as well as their computational complexity are outlined here (assuming that the preprocessing steps have already been accomplished). For the sake of clarity, intermediate variables are used to show the steps which may not be necessary in a final implementation. z Steps to compute ( ) 1 1 1 − − p D ET A C u =− − + : Operation Comment Complexity x Au 1 = Multiplication by a sparse matrix O(n) 1 2 1 − x Tx = Solve Tx2 = x1 by backsubstitution O(n) x Ex 3 2 = − Multiplication by a sparse matrix O(n) x Cu 4 = Multiplication by a sparse matrix O(n) xxx 5 34 = + Addition O(n) 1 1 5 − p Dx = − Multiplication by dense g×g matrix O(g 2 ) z Steps to compute 1 2 1 ( ) − p T Au Bp =− + : Operation Comment Complexity x Au 1 = Multiplication by a sparse matrix (already done) 0 x Bp 6 1 = Multiplication by a sparse matrix O(n) x xx 7 16 = + Addition O(n) 1 2 7 − p Tx = − Solve Tp2 = x7 by backsubstitution O(n) The overall algorithm is 2 On g ( ) + . Clearly, the smaller g can be made, the lower the