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