Encoding of Linear Codes Based on the Rearrangement of Block-Triangularized Parity-Check Matrices

摘要

Efficient algorithms to solve a system of linear equations have been extensively and deeply investi­gated in a large number of researches. Among them, the block-triangularization is one of the well-know approaches effective for linear systems defined by matrices with particular characteristics, especially by sparse matrices. In this paper, we propose an encoding algorithm that can be applied to arbitrary linear codes over any finite field and executed with complexity O(w(H)) where w(H) denotes the number of non-zero elements of the parity check matrix H under consideration. By giving our attention to the fact that encoding of a linear code is equivalent to solving a system of linear equations, we propose an encoding algorithm based on the block-triangularization of the part of parity check matrices combining rearrangement of subblocks of them. As the result, any linear codes defined by sparse parity check matrices, such as LDPC codes, can be encoded by the proposed algorithm with complexity O(n) where n denotes the code length.