International Conference on Communications

Systematic Modification of Parity-Check Matrices for Efficient Encoding of LDPC Codes

Mohammad Obaidah Shaqfeh, Norbert Goertz

Published Jun 1, 2007• 3 citations

Abstract

An algorithm for efficient encoding of LDPC codes is presented that does not impose any restrictions on the construction of the parity-check matrices. The algorithm modifies the parity check matrix, without changing the subspace spanned by its rows, by removing linear dependent rows and adding a small number of new rows such that the graph-based message-passing encoder will not get stuck in a stopping set. The added rows are designed by a new algorithm which is based on the notion of the "key set". The encoder exploits the sparseness of the parity-check matrix, and the encoding complexity grows almost linear with the blocksize, because the number of added rows, which may not be sparse, is relatively small.

DOI: 10.1109/icc.2007.160

Related papers

Linear Time Encoding of LDPC Codes

Jin Lu, José M. F. Moura

In this paper, we propose a linear complexity encoding method for arbitrary LDPC codes. We start from a simple graph-based encoding method ¿label-and-decide.¿ We prove that the ¿label-and-decide¿ method is applicable to Tanner graphs with a hierarchical structure-pseudo-trees-and that the resulting encoding complexity is linear with the code block length. Next, we define a second type of Tanner graphs-the encoding stopping set. The encoding stopping set is encoded in linear complexity by a revised label-and-decide algorithm-the ¿label-decide-recompute.¿ Finally, we prove that any Tanner graph can be partitioned into encoding stopping sets and pseudo-trees. By encoding each encoding stopping set or pseudo-tree sequentially, we develop a linear complexity encoding method for general low-density parity-check (LDPC) codes where the encoding complexity is proved to be less than4 ·M·((k¿- 1), whereMis the number of independent rows in the parity-check matrix andk¿represents the mean row weight of the parity-check matrix.

arXiv:0810.2781IEEE Transactions on Information TheoryJan 1, 201019 citations

Linear Time Encoding of LDPC Codes

Lu Jin, José M. F. Moura

Abstract—In this paper, we propose a linear complexity encoding method for arbitrary LDPC codes. We start from a simple graph-based encoding method “label-and-decide. ” We prove that the “label-and-decide ” method is applicable to Tanner graphs with a hierarchical structure—pseudo-trees—and that the resulting encoding complexity is linear with the code block length. Next, we define a second type of Tanner graphs—the encoding stopping set. The encoding stopping set is encoded in linear complexity by a revised label-and-decide algorithm—the “label-decide-recompute.” Finally, we prove that any Tanner graph can be partitioned into encoding stopping sets and pseudo-trees. By encoding each encoding stopping set or pseudo-tree sequentially, we develop a linear complexity encoding method for general low-density parity-check (LDPC) codes where the encoding complexity is proved to be less than 4 1 M 1 (k 0 1), where M is the number of independent rows in the parity-check matrix and k represents the mean row weight of the parity-check matrix. Index Terms—Encoding stopping set, low-density parity-check (LDPC) codes, linear complexity encoding, pseudo-tree, Tanner graphs.

Feb 27, 201029 citations

Quick and Direct Encoding of Low-Density Parity-Check Codes

Wang Yi-ming

LDPC code is a good error correct code which interests telecommunication field recently.However,the performance of LDPC code depends on the girth of its bipartite graph,that is it depends on its sparse parity-check matrices H,especially the complexity of encoding with H.This paper is mainly on how to construct a good matrix H.Based on the extended bit filling algorithm,the paper proposes a new method to construct matrix H which can be encoded directly and quickly.In different length of code,the simulation results show that this quick encoding has good random distribution and it doesn't need to compute the inverse of H and admits linear time encoding.So it can contribute to the LDPC code's application.

Suzhou Daxue xuebao. Faxue banJan 1, 20060 citations

Joint encoding-decoding construction of LDPC codes with reduced complexity

Ming Shan

LDPC codes are now one of intensely studied areas in coding due to their near Shannon limit performance and parallel decoding architecture. Because the LDPC codes parity-check matrices are defined in terms of sparse random graphs, the implementation of the decoding and encoding is of high complexity. A new design methodology of LDPC codes, which are constructed by the cyclic shift matrices, is proposed in order to reduce the decoding complexity under the Sum-Product algorithm. Meanwhile,the encoding problem of LDPC codes is also considered, then a simplified encoding structure is given. A new procedure of removing the short loops from the bipartite graph is demonstrated according to the construction scheme of our LDPC codes. Performance comparisons between our codes and random constructed LDPC codes on BER, loop distributions and minimum distance estimation are given by extensive simulations and numerical analysis.

Journal of China Institute of CommunicationsJan 1, 20051 citation

Efficient Encoding Algorithm of Binary and Non-Binary LDPC Codes Using Block Triangulation

Yuta Iketo, T. Nozaki

We propose an efficient encoding algorithm for the binary and non-binary low-density parity-check codes. This algorithm transforms the parity part of the parity-check matrix into a block triangular matrix with low weight diagonal submatrices by row and column permutations in the preprocessing stage. This algorithm determines the parity part of a codeword by block back-substitution to reduce the encoding complexity in the encoding stage. Numerical experiments show that this algorithm has a lower encoding complexity than existing encoding algorithms. Moreover, we show that this algorithm encodes the non-binary cycle codes in linear time.

arXiv:2103.01560Mar 2, 20211 citation

Efficient Implementation of Linear Programming Decoding

Mohammad Hossein Taghavi, Amin Shokrollahi, Paul H. Siegel

While linear programming (LP) decoding provides more flexibility for finite-length performance analysis than iterative message-passing (IMP) decoding, it is computationally more complex to implement in its original form, due to both the large size of the relaxed LP problem and the inefficiency of using general-purpose LP solvers. This paper explores ideas for fast LP decoding of low-density parity-check (LDPC) codes. By modifying the previously reported Adaptive LP decoding scheme to allow removal of unnecessary constraints, we first prove that LP decoding can be performed by solving a number of LP problems that each contains at most one linear constraint derived from each of the parity-check constraints. By exploiting this property, we study a sparse interior-point implementation for solving this sequence of linear programs. Since the most complex part of each iteration of the interior-point algorithm is the solution of a (usually ill-conditioned) system of linear equations for finding the step direction, we propose a preconditioning algorithm to facilitate solving such systems iteratively. The proposed preconditioning algorithm is similar to the encoding procedure of LDPC codes, and we demonstrate its effectiveness via both analytical methods and computer simulation results.

IEEE Transactions on Information TheorySep 1, 201148 citations