On the error-correcting capabilities of iterative error correction codes

Authors

DOI:

https://doi.org/10.15587/1729-4061.2019.157299

Keywords:

cyclic codes, low-density parity-check codes, error-correcting capabilities, iterative decoding, linear finite-state machine, permutations

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

Author Biography

Vasyl Semerenko, Vinnytsia National Technical University Khmelnytske highway, 95, Vinnytsia, Ukraine, 21021

PhD, Associate Professor

Department of Computer Technique

References

  1. Shennon, K. (1963). Raboty po teorii informacii i kibernetike. Moscow, 829.
  2. Ursul, A. D. (1968). Priroda informacii. Filosofskiy ocherk. Moscow: Politizdat, 288.
  3. Hartley, R. V. L. (1928). Transmission of Information. Bell System Technical Journal, 7 (3), 535–563. doi: https://doi.org/10.1002/j.1538-7305.1928.tb01236.x
  4. Kolmogorov, A. N. (1965). Tri podhoda k opredeleniyu ponyatiya “kolichestvo informacii”. Problemy peredachi informacii, 1 (1), 3–11.
  5. Kolmogorov, A. N. (1987). Teoriya informacii i teoriya algoritmov. Moscow: Nauka, 304.
  6. Bulychev, I. I., Soroka, M. Yu. (2016). About the nature and the essense of information. Noosfernye issledovaniya, 1-2 (13-14), 191–207.
  7. Piterson, U., Ueldon, E. (1976). Kody, ispravlyayushchie oshibki. Moscow: Mir, 596.
  8. Sklyar, B. (2004). Cifrovaya svyaz'. Teoreticheskie osnovy i prakticheskoe primenenie. Moscow: Izd. dom «Vil'yams», 1104.
  9. Klark, Dzh. ml., Keyn, Dzh. (1987). Kodirovanie s ispravleniem oshibok v sistemah cifrovoy svyazi. Moscow: Radio i svyaz', 392.
  10. Dumer, I., Micciancio, D., Sudan, M. (2003). Hardness of approximating the minimum distance of a linear code. IEEE Transactions on Information Theory, 49 (1), 22–37. doi: https://doi.org/10.1109/tit.2002.806118
  11. Semerenko, V. (2018). Iterative hard­-decision decoding of combined cyclic codes. Eastern-European Journal of Enterprise Technologies, 1 (9 (91)), 61–72. doi: https://doi.org/10.15587/1729-4061.2018.123207
  12. Garrammone, G., Declercq, D., Fossorier, M. P. C. (2017). Weight Distributions of Non-Binary Multi-Edge Type LDPC Code Ensembles: Analysis and Efficient Evaluation. IEEE Transactions on Information Theory, 63 (3), 1463–1475. doi: https://doi.org/10.1109/tit.2016.2647724
  13. Liu, L., Huang, J., Zhou, W., Zhou, S. (2012). Computing the Minimum Distance of Nonbinary LDPC Codes. IEEE Transactions on Communications, 60 (7), 1753–1758. doi: https://doi.org/10.1109/tcomm.2012.050812.110073a
  14. Uryvskiy, L. A., Osipchuk, S. A.; Bezruk, V. M., Barannik, V. V. (Eds.) (2017). Issledovanie svoystv pomekhoustoychivyh kodov klassa LDPC. Naukoemkie tekhnologii v infokommunikaciyah: obrabotka informacii, kiberbezopasnost', informacionnaya bor'ba. Kharkiv, 137–139.
  15. Tomlinson, M., Tjhai, C. J., Ambroze, M. A., Ahmed, M., Jibril, M. (2017). Error-Correction Coding and Decoding. Bounds, Codes, Decoders, Analysis and Applications. Springer. doi: https://doi.org/10.1007/978-3-319-51103-0
  16. Bocharova, I. E., Kudryashov, B. D., Skachek, V., Yakimenka, Y. (2017). Distance Properties of Short LDPC Codes and Their Impact on the BP, ML and Near-ML Decoding Performance. Lecture Notes in Computer Science, 48–61. doi: https://doi.org/10.1007/978-3-319-66278-7_5
  17. Butler, B. K., Siegel, P. H. (2014). Error Floor Approximation for LDPC Codes in the AWGN Channel. IEEE Transactions on Information Theory, 60 (12), 7416–7441. doi: https://doi.org/10.1109/tit.2014.2363832
  18. Berlekemp, E. (1971). Algebraicheskaya teoriya kodirovaniya. Moscow: Mir, 477.
  19. Semerenko, V. P. (2009). Burst-Error Correction for Cyclic Codes. IEEE EUROCON 2009. doi: https://doi.org/10.1109/eurcon.2009.5167864
  20. Semerenko, V. P. (1998). Parallel Decoding of Bose-Chaudhuri-Hocquenghem Codes. Engineering Simulation, 16 (1), 87–100.
  21. Semerenko, V. P. (2015). Teoriya tsyklichnykh kodiv na osnovi avtomatnykh modelei. Vinnytsia: VNTU, 444.
  22. Gallager, R. (1966). Kody s maloy plotnost'yu proverok na chetnost'. Moscow: Mir, 144.
  23. Semerenko, V. P. (2015). Estimation of the correcting capability of cyclic codes based on their automation models. Eastern-European Journal of Enterprise Technologies, 2 (9 (74)), 16–24. doi: https://doi.org/10.15587/1729-4061.2015.39947

Downloads

Published

2019-02-21

How to Cite

Semerenko, V. (2019). On the error-correcting capabilities of iterative error correction codes. Eastern-European Journal of Enterprise Technologies, 1(4), 31–39. https://doi.org/10.15587/1729-4061.2019.157299

Issue

Vol. 1 No. 4 (2019): Mathematics and Cybernetics - applied aspects

Section

Mathematics and Cybernetics - applied aspects

License

Copyright (c) 2019 Vasyl Semerenko

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

The consolidation and conditions for the transfer of copyright (identification of authorship) is carried out in the License Agreement. In particular, the authors reserve the right to the authorship of their manuscript and transfer the first publication of this work to the journal under the terms of the Creative Commons CC BY license. At the same time, they have the right to conclude on their own additional agreements concerning the non-exclusive distribution of the work in the form in which it was published by this journal, but provided that the link to the first publication of the article in this journal is preserved.

A license agreement is a document in which the author warrants that he/she owns all copyright for the work (manuscript, article, etc.).
The authors, signing the License Agreement with TECHNOLOGY CENTER PC, have all rights to the further use of their work, provided that they link to our edition in which the work was published.
According to the terms of the License Agreement, the Publisher TECHNOLOGY CENTER PC does not take away your copyrights and receives permission from the authors to use and dissemination of the publication through the world's scientific resources (own electronic resources, scientometric databases, repositories, libraries, etc.).
In the absence of a signed License Agreement or in the absence of this agreement of identifiers allowing to identify the identity of the author, the editors have no right to work with the manuscript.
It is important to remember that there is another type of agreement between authors and publishers – when copyright is transferred from the authors to the publisher. In this case, the authors lose ownership of their work and may not use it in any way.