In this paper, we propose a new encoding method applicable to any linear codes over arbitrary finite field whose computational complexity is O(δ*n) where δ* and n denote the maximum column weight of a parity check matrix of a code and the code length, respectively. This means that if a code has a parity check matrix with the constant maximum column weight, such as LDPC codes, it can be encoded with O(n) computation. We also clarify the relation between the proposed method and conventional methods, and compare the computational complexity of those methods. Then we show that the proposed encoding method is much more efficient than the conventional ones.

Recently, Haley and Grant introduced the concept of reversible codes – a class of binary linear codes that can reuse the decoder architecture as the encoder and encodable by the iterative message-passing algorithm based on the Jacobi method over F2. They also developed a procedure to construct parity check matrices of a class of reversible codes named type-I reversible codes by utilizing properties specific to circulant matrices. In this paper, we refine a mathematical framework for reversible codes based on circulant matrices through a ring theoretic approach. This approach enables us to clarify the necessary and sufficient condition on which type-I reversible codes exist. Moreover, a systematic procedure to construct all circulant matrices that constitute parity check matrices of type-I reversible codes is also presented.