Modified greedy permutation algorithm for low complexity encoding in LDPC codes

The low-density parity-check (LDPC) codes are used to achieve excellent performance with low encoding and decoding complexity. One major criticism concerning LDPC codes has been their apparent high encoding complexity and memory inefficient nature due to large parity check matrix. More generally, we consider the encoding problem for codes specified by sparse parity-check matrices. We show how to exploit the sparseness of the parity-check matrix to obtain efficient encoders. A new technique for efficient encoding of LDP Codes based on the known concept of approximate lower triangulation (ALT) is introduced. The algorithm computes parity check symbols by solving a set of sparse equations, and the triangular factorization is employed to solve the equations efficiently. The key of the encoding method is to get the systematic approximate lower triangular (SALT) form of the Parity Check Matrix with minimum gap g, because the smaller the gap is, the more efficient encoding will be obtained. The functions are to be coded in MATLAB.