Block-triangularization of parity check matrices for efficient encoding of linear codes

In this paper, we propose a new encoding algorithm for linear codes whose computational complexity is O(w(H)) where w(H) denotes the number of non-zero elements in a parity check matrix H of a code. The proposed algorithm is based on the block-triangularization - an efficient technique to solve a system of linear equations - of a parity part of a parity check matrix, combining additional row and column permutations. As a result, the proposed algorithm can encode any linear codes defined by sparse parity check matrices, such as LDPC codes, with O(n) complexity where n denotes the code length.