Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

International Symposium on Information Theory and its Applications

Error-trellis state complexity of LDPC convolutional codes based on circulant matrices

Masato Tajima, Koji Okino, Takashi Miyagoshi

Published Oct 1, 2010• 3 citations
Publisher

Abstract

Let H(D) be the parity-check matrix of an LDPC convolutional code corresponding to the parity-check matrix H of a QC code obtained using the method of Tanner et al. We see that the entries in H(D) are all monomials and several rows (columns) have monomial factors. Let us cyclically shift the rows of H. Then the parity-check matrix H'(D) corresponding to the modified matrix H' defines another convolutional code. However, its free distance is lower-bounded by the minimum distance of the original QC code. Also, each row (column) of H'(D) has a factor different from the one in H(D). We show that the statespace complexity of the error-trellis associated with H'(D) can be significantly reduced by controlling the row shifts applied to H with the error-correction capability being preserved.

DOI
10.1109/isita.2010.5648981

Related papers

Error-Trellis State Complexity of LDPC Convolutional Codes Based on Circulant Matrices

Masato Tajima, Koji Okino, Takashi Miyagoshi

Let H(D) be the parity-check matrix of an LDPC convolutional code corresponding to the parity-check matrix H of a QC code obtained using the method of Tanner et al. We see that the entries in H(D) are all monomials and several rows (columns) have monomial factors. Let us cyclically shift the rows of H. Then the parity-check matrix H'(D) corresponding to the modified matrix H' defines another convolutional code. However, its free distance is lower-bounded by the minimum distance of the original QC code. Also, each row (column) of H'(D) has a factor different from the one in H(D). We show that the state-space complexity of the error-trellis associated with H'(D) can be significantly reduced by controlling the row shifts applied to H with the error-correction capability being preserved.

arXiv:0812.4642•Dec 26, 2008•0 citations

Error-Trellis State Complexity of LDPC Convolutional Codes Based on Circulant Matrices

Masato Tajima, Koji Okino, Takashi Miyagoshi

Abstract — Let H(D) be the parity-check matrix of an LDPC convolutional code corresponding to the parity-check matrix H of a QC code obtained using the method of Tanner et al. We see that the entries in H(D) are all monomials and several rows (columns) have monomial factors. Let us cyclically shift the rows of H. Then the parity-check matrix H ′ (D) corresponding to the modified matrix H ′ defines another convolutional code. However, its free distance is lower-bounded by the minimum distance of the original QC code. Also, each row (column) of H ′ (D) has a factor different from the one in H(D). We show that the statespace complexity of the error-trellis associated with H ′ (D) can be significantly reduced by controlling the row shifts applied to H with the error-correction capability being preserved. I.

IEICE Technical Report; IEICE Tech. Rep.•Mar 2, 2009•3 citations

1-State Error-Trellis Decoding of LDPC Convolutional Codes Based on Circulant Matrices

Masato Tajima, Koji Okino, Takashi Miyagoshi

We consider the decoding of convolutional codes using an error trellis constructed based on a submatrix of a given check matrix. In the proposed method, the syndrome-subsequence computed using the remaining submatrix is utilized as auxiliary information for decoding. Then the ML error path is correctly decoded using the degenerate error trellis. We also show that the decoding complexity of the proposed method is basically identical with that of the conventional one based on the original error trellis. Next, we apply the method to check matrices with monomial entries proposed by Tanner et al. By choosing any row of the check matrix as the submatrix for error-trellis construction, a 1-state error trellis is obtained. Noting the fact that a likelihood-concentration on the all-zero state and the states with many 0's occurs in the error trellis, we present a simplified decoding method based on a 1-state error trellis, from which decoding-complexity reduction is realized.

arXiv:0912.4995•Dec 28, 2009•0 citations

Rank Analysis of Parity-Check Matrices for Quasi-Cyclic LDPC Codes

Po‐Chun Yang, Chung-Hsuan Wang, Chi-Chao Chao

Quasi-cyclic low-density parity-check (QC-LDPC) codes are an important class of LDPC codes which can be encoded and decoded with low complexity and suitable for many applications. As the code dimension, which describes the number of protected information bits, is equal to the code length minus the rank of the parity-check matrix and the parity-check matrix for QC-LDPC codes is usually not full-rank, determining the rank of the parity-check matrix is of essential importance. In this paper, we study the rank of the parity-check matrix for QC-LDPC codes based on the associated polynomials for circulant matrices. A formula for the rank of the parity-check matrix with only one row-block is first derived. We then extend the result to matrices with two, three, or more row-blocks. Some bounds are also presented for matrices with arbitrary numbers of row-blocks. Furthermore, the exact rank is determined for a class of algebraically constructed parity-check matrices.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2018•5 citations

QC-LDPC Codes Construction by Concatenating of Circulant Matrices as Block-Columns

Mohammad Hesam Tadayon, Mohammad Mohammadi

In this paper a new low complexity method for constructing binary quasi-cyclic low-density parity-check (QC-LDPC) codes is introduced. In the proposed method, each block-column of the parity check matrix H is made by a circulant matrix in a way that the associated Tanner graph is free of cycle four. Each circulant matrix in H is made by a generator column. The generator columns should be selected in a way that each associated circulant matrix and every two distinct circulant matrices are free of cycle four. The generator columns are made by row distance sets. An algorithm for generating distance sets and obtaining circulant matrices with columns of weight three is presented separately. Simplicity of construction and having a good flexible family of quasi cyclic LDPC codes both in rate and length are the main properties of the proposed method. The performance of the proposed codes is compared with that of the random-like and Array LDPC codes over an AWGN channel. Simulation results show that from the performance perspective, the constructed codes are competitive with random-like and Array LDPC codes.

International Journal of Information & Communication Technology Research•Jun 15, 2016•0 citations

A Method for Computing the Weight Spectrum of LDPC Convolutional Codes Based on Circulant Matrices

Masanori Hirotomo, Masakatu Morii

In this paper, we propose an efficient method for computing the weight spectrum of LDPC convolutional codes based on circulant matrices of quasi-cyclic codes. In the proposed method, we reduce the memory size of their parity-check matrices with the same distance profile as the original codes, and apply a forward and backward tree search algorithm to the parity-check matrices of reduced memory. We show numerical results of computing the free distance and the low-part weight spectrum of LDPC convolutional codes of memory about 130.

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•Jan 1, 2014•0 citations
Let H(D) be the parity-check matrix of an LDPC convolutional code corresponding to the parity-check matrix H of a QC code obtained using the method of Tanner et al. We see that the entries in H(D) are all monomials and several rows (columns) have monomial factors. Let us cyclically shift the rows of H. Then the parity-check matrix H'(D) corresponding to the modified matrix H' defines another convolutional code. However, its free distance is lower-bounded by the minimum distance of the original QC code. Also, each row (column) of H'(D) has a factor different from the one in H(D). We show that the statespace complexity of the error-trellis associated with H'(D) can be significantly reduced by controlling the row shifts applied to H with the error-correction capability being preserved.
Let H(D) be the parity-check matrix of an LDPC convolutional code corresponding to the parity-check matrix H of a QC code obtained using the method of Tanner et al. We see that the entries in H(D) are all monomials and several rows (columns) have monomial factors. Let us cyclically shift the rows of H. Then the parity-check matrix H'(D) corresponding to the modified matrix H' defines another convolutional code. However, its free distance is lower-bounded by the minimum distance of the original QC code. Also, each row (column) of H'(D) has a factor different from the one in H(D). We show that the state-space complexity of the error-trellis associated with H'(D) can be significantly reduced by controlling the row shifts applied to H with the error-correction capability being preserved.
Abstract — Let H(D) be the parity-check matrix of an LDPC convolutional code corresponding to the parity-check matrix H of a QC code obtained using the method of Tanner et al. We see that the entries in H(D) are all monomials and several rows (columns) have monomial factors. Let us cyclically shift the rows of H. Then the parity-check matrix H ′ (D) corresponding to the modified matrix H ′ defines another convolutional code. However, its free distance is lower-bounded by the minimum distance of the original QC code. Also, each row (column) of H ′ (D) has a factor different from the one in H(D). We show that the statespace complexity of the error-trellis associated with H ′ (D) can be significantly reduced by controlling the row shifts applied to H with the error-correction capability being preserved. I.
We consider the decoding of convolutional codes using an error trellis constructed based on a submatrix of a given check matrix. In the proposed method, the syndrome-subsequence computed using the remaining submatrix is utilized as auxiliary information for decoding. Then the ML error path is correctly decoded using the degenerate error trellis. We also show that the decoding complexity of the proposed method is basically identical with that of the conventional one based on the original error trellis. Next, we apply the method to check matrices with monomial entries proposed by Tanner et al. By choosing any row of the check matrix as the submatrix for error-trellis construction, a 1-state error trellis is obtained. Noting the fact that a likelihood-concentration on the all-zero state and the states with many 0's occurs in the error trellis, we present a simplified decoding method based on a 1-state error trellis, from which decoding-complexity reduction is realized.
Quasi-cyclic low-density parity-check (QC-LDPC) codes are an important class of LDPC codes which can be encoded and decoded with low complexity and suitable for many applications. As the code dimension, which describes the number of protected information bits, is equal to the code length minus the rank of the parity-check matrix and the parity-check matrix for QC-LDPC codes is usually not full-rank, determining the rank of the parity-check matrix is of essential importance. In this paper, we study the rank of the parity-check matrix for QC-LDPC codes based on the associated polynomials for circulant matrices. A formula for the rank of the parity-check matrix with only one row-block is first derived. We then extend the result to matrices with two, three, or more row-blocks. Some bounds are also presented for matrices with arbitrary numbers of row-blocks. Furthermore, the exact rank is determined for a class of algebraically constructed parity-check matrices.
In this paper a new low complexity method for constructing binary quasi-cyclic low-density parity-check (QC-LDPC) codes is introduced. In the proposed method, each block-column of the parity check matrix H is made by a circulant matrix in a way that the associated Tanner graph is free of cycle four. Each circulant matrix in H is made by a generator column. The generator columns should be selected in a way that each associated circulant matrix and every two distinct circulant matrices are free of cycle four. The generator columns are made by row distance sets. An algorithm for generating distance sets and obtaining circulant matrices with columns of weight three is presented separately. Simplicity of construction and having a good flexible family of quasi cyclic LDPC codes both in rate and length are the main properties of the proposed method. The performance of the proposed codes is compared with that of the random-like and Array LDPC codes over an AWGN channel. Simulation results show that from the performance perspective, the constructed codes are competitive with random-like and Array LDPC codes.
In this paper, we propose an efficient method for computing the weight spectrum of LDPC convolutional codes based on circulant matrices of quasi-cyclic codes. In the proposed method, we reduce the memory size of their parity-check matrices with the same distance profile as the original codes, and apply a forward and backward tree search algorithm to the parity-check matrices of reduced memory. We show numerical results of computing the free distance and the low-part weight spectrum of LDPC convolutional codes of memory about 130.