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

Eastern-European Journal of Enterprise Technologies

On the error-correcting capabilities of iterative error correction codes

Vasyl Semerenko

Published Feb 21, 2019• 1 citation
Publisher

Abstract

The influence of the theory of information on development of the error correcting coding theory has been studied. Main differences between the probabilistic approach and the deterministic approach in the analysis of error-correcting capabilities of different classes of linear codes have been demonstrated.The automaton hierarchical models for analysis of permutation decoding of cyclic codes have been developed and a cyclic permutation generator based on two Moore automata has been proposed.A study has been carried out into the regular and irregular states of linear finite-state machines (LFSM) based on the automaton representation of cyclic codes. A possibility of significant simplification of decoding of cyclic codes based on conversion of irregular LFSM syndromes into regular ones using permutations has been shown.The formalized methods for determination of error-correcting capabilities of iteratively decoded cyclic codes (IDCC) have been devised. They imply the replacementof traditional complete checking of all possible options for comparison of code words to directional search for the solution of the assigned problem, which leads to a significant time saving for calculations. The algorithm for determination of error-correcting capabilities of IDCC with respect to double errors is given.It has been shown that all iterative codes increase their error-correcting capabilities with an increase in the number of iterations and one can set it as a percentage for errors of various multiplicities. A distribution of error syndromes to separate iterations has been performed, which makes it possible to reduce the length of a check word in a code. As a result, this leads to an increase in a rate of iterative codes in comparison with the traditional correction codes.A comparative analysis of IDCC and LDPC codes has been carried out to determine a scope of their optimal use

DOI
10.15587/1729-4061.2019.157299

Related papers

Результати дослідження коректувальної здатності ітеративних завадостійких кодів

Semerenko, Vasyl

The influence of the theory of information on development of the error correcting coding theory has been studied. Main differences between the probabilistic approach and the deterministic approach in the analysis of error-correcting capabilities of different classes of linear codes have been demonstrated.The automaton hierarchical models for analysis of permutation decoding of cyclic codes have been developed and a cyclic permutation generator based on two Moore automata has been proposed.A study has been carried out into the regular and irregular states of linear finite-state machines (LFSM) based on the automaton representation of cyclic codes. A possibility of significant simplification of decoding of cyclic codes based on conversion of irregular LFSM syndromes into regular ones using permutations has been shown.The formalized methods for determination of error-correcting capabilities of iteratively decoded cyclic codes (IDCC) have been devised. They imply the replacementof traditional complete checking of all possible options for comparison of code words to directional search for the solution of the assigned problem, which leads to a significant time saving for calculations. The algorithm for determination of error-correcting capabilities of IDCC with respect to double errors is given.It has been shown that all iterative codes increase their error-correcting capabilities with an increase in the number of iterations and one can set it as a percentage for errors of various multiplicities. A distribution of error syndromes to separate iterations has been performed, which makes it possible to reduce the length of a check word in a code. As a result, this leads to an increase in a rate of iterative codes in comparison with the traditional correction codes.A comparative analysis of IDCC and LDPC codes has been carried out to determine a scope of their optimal use

The Scientific Issues of Ternopil Volodymyr Hnatiuk National Pedagogical University Series pedagogy•Feb 21, 2019•0 citations

Correcting capabilities of binary irregular LDPC code under low-complexity iterative decoding algorithm

Pavel S. Rybin

This paper deals with the irregular binary low-density parity-check (LDPC) codes and two iterative low-complexity decoding algorithms. The first one is the majority error-correcting decoding algorithm, and the second one is iterative erasure-correcting decoding algorithm. The lower bounds on correcting capabilities (the guaranteed corrected error and erasure fraction respectively) of irregular LDPC code under decoding (error and erasure correcting respectively) algorithms with low-complexity were represented. These lower bounds were obtained as a result of analysis of Tanner graph representation of irregular LDPC code. The numerical results, obtained at the end of the paper for proposed lower-bounds achieved similar results for the previously known best lower-bounds for regular LDPC codes and were represented for the first time for the irregular LDPC codes.

Journal of Communications Technology and Electronics•Dec 1, 2016•2 citations

On the error-correcting capabilities of low-complexity decoded irregular LDPC codes

Pavel S. Rybin

This paper deals with the irregular binary low-density parity-check (LDPC) codes with the constituent single parity check (SPC) codes and the error-correcting iterative low-complex decoding algorithm. The lower bound on the error fraction, guaranteed corrected by the considered iterative algorithm, was obtained for the irregular LDPC code for the first time in this paper. This lower bound was obtained as a result of analysis of Tanner graph representation of irregular LDPC code. The number of decoding iterations, required to correct the errors, is a logarithmic function of the code length. The numerical results, obtained at the end of the paper for proposed lower bound achieved similar results for the previously known best lower-bounds for regular LDPC codes and were represented for the first time for the irregular LDPC codes.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2014•9 citations

Iterative Soft-Decision Decoding of Binary Cyclic Codes

Marco Baldi, Giovanni Cancellieri, Franco Chiaraluce

Binary cyclic codes achieve good error correction performance and allow the implementation of very simpleencoder and decoder circuits. Among them, BCH codesrepresent a very important class of t-error correcting codes, with known structural properties and error correction capability. Decoding of binary cyclic codes is often accomplished through hard-decision decoders, although it is recognized that softdecision decoding algorithms can produce significant coding gain with respect to hard-decision techniques. Several approaches have been proposed to implement iterative soft-decision decoding of binary cyclic codes. We study the technique based on “extended parity-check matrices”, and show that such method is not suitable for high rates or long codes. We propose a new approach, based on “reduced parity-check matrices” and “spread parity-check matrices”, that can achieve better correction performance in many practical cases, without increasing the complexity.

Journal of Communications Software and Systems•Jun 22, 2008•3 citations

Error correction capability of irregular LDPC codes under the Gallager a algorithm

Masakatu Morii, Hiroto Tamiya, Masanori Hirotomo

Many researchers have analyzed the error correction capability of LDPC codes for iterative decoding algorithms. However, it is difficult to show the error correction capability of LDPC codes for iterative decoding algorithms based on belief propagation theoretically. Chilappagari et al. reported the error correction capability of column-weight-three regular LDPC codes under the Gallager A algorithm since the behavior of the iterative decoding algorithm is easily analyzed. In this paper, we investigate the error correction capability of irregular LDPC codes. We also show relations between the decoding failures and 2-cycles of irregular LDPC codes under the Gallager A algorithm.

International Symposium on Information Theory and its Applications•Oct 1, 2016•2 citations

Iterative decoding of a class of cyclic codes

Li Guo Zhang, Qin Huang, Shu Lin

Among the classes of LDPC codes that have been constructed and designed, the only class of LDPC codes that are cyclic is the class of codes constructed based on the incidence vectors of lines of finite geometries, called finite geometry LDPC codes. Cyclic finite geometry LDPC codes are known to have large minimum distances and can provide good error performance with very low error-floors using iterative decoding based on belief propagation. Their cyclic structure allows them to be efficiently and systematically encoded with simple shift-registers in linear time with linear complexity. An obvious question is whether, besides cyclic finite geometry LDPC codes, there are other cyclic codes with large minimum distances that can be efficiently decoded iteratively using channel soft information. In this paper, we present one such class of cyclic codes. Codes in this class are two-step majority-logic decodable and they are also constructed based on finite geometries. Two iterative decoding algorithms are devised for this class of cyclic codes and they provide significant coding gain over the two-step majority-logic decoding of codes in this class.

Information Theory and Applications Workshop (ITA)•Jan 1, 2010•4 citations
The influence of the theory of information on development of the error correcting coding theory has been studied. Main differences between the probabilistic approach and the deterministic approach in the analysis of error-correcting capabilities of different classes of linear codes have been demonstrated.The automaton hierarchical models for analysis of permutation decoding of cyclic codes have been developed and a cyclic permutation generator based on two Moore automata has been proposed.A study has been carried out into the regular and irregular states of linear finite-state machines (LFSM) based on the automaton representation of cyclic codes. A possibility of significant simplification of decoding of cyclic codes based on conversion of irregular LFSM syndromes into regular ones using permutations has been shown.The formalized methods for determination of error-correcting capabilities of iteratively decoded cyclic codes (IDCC) have been devised. They imply the replacementof traditional complete checking of all possible options for comparison of code words to directional search for the solution of the assigned problem, which leads to a significant time saving for calculations. The algorithm for determination of error-correcting capabilities of IDCC with respect to double errors is given.It has been shown that all iterative codes increase their error-correcting capabilities with an increase in the number of iterations and one can set it as a percentage for errors of various multiplicities. A distribution of error syndromes to separate iterations has been performed, which makes it possible to reduce the length of a check word in a code. As a result, this leads to an increase in a rate of iterative codes in comparison with the traditional correction codes.A comparative analysis of IDCC and LDPC codes has been carried out to determine a scope of their optimal use
The influence of the theory of information on development of the error correcting coding theory has been studied. Main differences between the probabilistic approach and the deterministic approach in the analysis of error-correcting capabilities of different classes of linear codes have been demonstrated.The automaton hierarchical models for analysis of permutation decoding of cyclic codes have been developed and a cyclic permutation generator based on two Moore automata has been proposed.A study has been carried out into the regular and irregular states of linear finite-state machines (LFSM) based on the automaton representation of cyclic codes. A possibility of significant simplification of decoding of cyclic codes based on conversion of irregular LFSM syndromes into regular ones using permutations has been shown.The formalized methods for determination of error-correcting capabilities of iteratively decoded cyclic codes (IDCC) have been devised. They imply the replacementof traditional complete checking of all possible options for comparison of code words to directional search for the solution of the assigned problem, which leads to a significant time saving for calculations. The algorithm for determination of error-correcting capabilities of IDCC with respect to double errors is given.It has been shown that all iterative codes increase their error-correcting capabilities with an increase in the number of iterations and one can set it as a percentage for errors of various multiplicities. A distribution of error syndromes to separate iterations has been performed, which makes it possible to reduce the length of a check word in a code. As a result, this leads to an increase in a rate of iterative codes in comparison with the traditional correction codes.A comparative analysis of IDCC and LDPC codes has been carried out to determine a scope of their optimal use
This paper deals with the irregular binary low-density parity-check (LDPC) codes and two iterative low-complexity decoding algorithms. The first one is the majority error-correcting decoding algorithm, and the second one is iterative erasure-correcting decoding algorithm. The lower bounds on correcting capabilities (the guaranteed corrected error and erasure fraction respectively) of irregular LDPC code under decoding (error and erasure correcting respectively) algorithms with low-complexity were represented. These lower bounds were obtained as a result of analysis of Tanner graph representation of irregular LDPC code. The numerical results, obtained at the end of the paper for proposed lower-bounds achieved similar results for the previously known best lower-bounds for regular LDPC codes and were represented for the first time for the irregular LDPC codes.
This paper deals with the irregular binary low-density parity-check (LDPC) codes with the constituent single parity check (SPC) codes and the error-correcting iterative low-complex decoding algorithm. The lower bound on the error fraction, guaranteed corrected by the considered iterative algorithm, was obtained for the irregular LDPC code for the first time in this paper. This lower bound was obtained as a result of analysis of Tanner graph representation of irregular LDPC code. The number of decoding iterations, required to correct the errors, is a logarithmic function of the code length. The numerical results, obtained at the end of the paper for proposed lower bound achieved similar results for the previously known best lower-bounds for regular LDPC codes and were represented for the first time for the irregular LDPC codes.
Binary cyclic codes achieve good error correction performance and allow the implementation of very simpleencoder and decoder circuits. Among them, BCH codesrepresent a very important class of t-error correcting codes, with known structural properties and error correction capability. Decoding of binary cyclic codes is often accomplished through hard-decision decoders, although it is recognized that softdecision decoding algorithms can produce significant coding gain with respect to hard-decision techniques. Several approaches have been proposed to implement iterative soft-decision decoding of binary cyclic codes. We study the technique based on “extended parity-check matrices”, and show that such method is not suitable for high rates or long codes. We propose a new approach, based on “reduced parity-check matrices” and “spread parity-check matrices”, that can achieve better correction performance in many practical cases, without increasing the complexity.
Many researchers have analyzed the error correction capability of LDPC codes for iterative decoding algorithms. However, it is difficult to show the error correction capability of LDPC codes for iterative decoding algorithms based on belief propagation theoretically. Chilappagari et al. reported the error correction capability of column-weight-three regular LDPC codes under the Gallager A algorithm since the behavior of the iterative decoding algorithm is easily analyzed. In this paper, we investigate the error correction capability of irregular LDPC codes. We also show relations between the decoding failures and 2-cycles of irregular LDPC codes under the Gallager A algorithm.
Among the classes of LDPC codes that have been constructed and designed, the only class of LDPC codes that are cyclic is the class of codes constructed based on the incidence vectors of lines of finite geometries, called finite geometry LDPC codes. Cyclic finite geometry LDPC codes are known to have large minimum distances and can provide good error performance with very low error-floors using iterative decoding based on belief propagation. Their cyclic structure allows them to be efficiently and systematically encoded with simple shift-registers in linear time with linear complexity. An obvious question is whether, besides cyclic finite geometry LDPC codes, there are other cyclic codes with large minimum distances that can be efficiently decoded iteratively using channel soft information. In this paper, we present one such class of cyclic codes. Codes in this class are two-step majority-logic decodable and they are also constructed based on finite geometries. Two iterative decoding algorithms are devised for this class of cyclic codes and they provide significant coding gain over the two-step majority-logic decoding of codes in this class.