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

arXiv:1201.4428 · IEICE Technical Report; IEICE Tech. Rep.

Error-Trellis Construction for Tailbiting Convolutional Codes

Masato Tajima, Koji Okino

Published Jan 21, 2012• 3 citations
arXivHTMLPDF

Abstract

In this paper, we present an error-trellis construction for tailbiting convolutional codes. A tailbiting error-trellis is characterized by the condition that the syndrome former starts and ends in the same state. We clarify the correspondence between code subtrellises in the tailbiting code-trellis and error subtrellises in the tailbiting error-trellis. Also, we present a construction of tailbiting backward error-trellises. Moreover, we obtain the scalar parity-check matrix for a tailbiting convolutional code. The proposed construction is based on the adjoint-obvious realization of a syndrome former and its behavior is fully used in the discussion.

DOI
10.48550/arxiv.1201.4428

Related papers

Decoding of codes based on their tailbiting trellises

R.Y. Shao, Shu Wen Lin, M.P.C. Fossorier

A tailbiting trellis for a code is a trellis with multiple starting and multiple ending states. Each starting state corresponds to a unique ending state and they are the same state. A path in a tailbiting trellis represents a valid codeword if and only if it starts from a state and ends at the same state. Such a path is called a tailbiting path. In this paper, two new iterative algorithms for decoding codes based on their tailbiting trellises are presented, one is unidirectional and the other is bidirectional. Both algorithms are computationally efficient and achieves virtually optimum error performance with a small number of decoding iterations.

IEEE International Symposium on Information Theory (ISIT)•Nov 7, 2002•6 citations

Reduction of Error-Trellises for Tail-Biting Convolutional Codes Using Shifted Error-Subsequences

Masato Tajima, Koji Okino, Tatsuto Murayama

In this paper, we discuss the reduction of error-trellises for tail-biting convolutional codes. In the case where some column of a parity-check matrix has a monomial factor (with indeterminate D), we show that the associated tail-biting error-trellis can be reduced by cyclically shifting the corresponding error-subsequence by l (the power of D) time units. We see that the resulting reduced error-trellis is again tail-biting. Moreover, we show that reduction is also possible using backward-shifted error-subsequences.

arXiv:1401.2496•Jan 11, 2014•0 citations

Initial (Final) State Estimation in Error-Trellises for Tail-Biting Convolutional Codes

Masato Tajima, Koji Okino, Tatsuto Murayama

In this paper, we clarify the relationship between an initial (final) state in a tail-biting error-trellis and the obtained syndromes. We show that a final state is dependent on the first M syndromes as well, where M is the memory length of the parity-check matrix. Next, we calculate the probability of an initial (final) state conditioned by the syndromes. We also apply this method to concrete examples. It is shown that the initial (final) state in a tail-biting error-trellis is well estimated using these conditional probabilities.

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•Jan 1, 2014•1 citation

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

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

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
In this paper, we present an error-trellis construction for tailbiting convolutional codes. A tailbiting error-trellis is characterized by the condition that the syndrome former starts and ends in the same state. We clarify the correspondence between code subtrellises in the tailbiting code-trellis and error subtrellises in the tailbiting error-trellis. Also, we present a construction of tailbiting backward error-trellises. Moreover, we obtain the scalar parity-check matrix for a tailbiting convolutional code. The proposed construction is based on the adjoint-obvious realization of a syndrome former and its behavior is fully used in the discussion.
A tailbiting trellis for a code is a trellis with multiple starting and multiple ending states. Each starting state corresponds to a unique ending state and they are the same state. A path in a tailbiting trellis represents a valid codeword if and only if it starts from a state and ends at the same state. Such a path is called a tailbiting path. In this paper, two new iterative algorithms for decoding codes based on their tailbiting trellises are presented, one is unidirectional and the other is bidirectional. Both algorithms are computationally efficient and achieves virtually optimum error performance with a small number of decoding iterations.
In this paper, we discuss the reduction of error-trellises for tail-biting convolutional codes. In the case where some column of a parity-check matrix has a monomial factor (with indeterminate D), we show that the associated tail-biting error-trellis can be reduced by cyclically shifting the corresponding error-subsequence by l (the power of D) time units. We see that the resulting reduced error-trellis is again tail-biting. Moreover, we show that reduction is also possible using backward-shifted error-subsequences.
In this paper, we clarify the relationship between an initial (final) state in a tail-biting error-trellis and the obtained syndromes. We show that a final state is dependent on the first M syndromes as well, where M is the memory length of the parity-check matrix. Next, we calculate the probability of an initial (final) state conditioned by the syndromes. We also apply this method to concrete examples. It is shown that the initial (final) state in a tail-biting error-trellis is well estimated using these conditional probabilities.
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.
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.
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.