The simplification of computationals in error correction coding

Authors

DOI:

https://doi.org/10.15587/2706-5448.2021.233656

Keywords:

cyclic codes, NP-completeness, computational complexity, cyclic permutation, iterative decoding

Abstract

The object of research is the processes of error correction transformation of information in automated systems. The research is aimed at reducing the complexity of decoding cyclic codes by combining modern mathematical models and practical tools. The main prerequisite for the complication of computations in deterministic linear error-correcting codes is the use of the algebraic representation as the main mathematical apparatus for these types of codes. Despite the universalism of the algebraic approach, its main drawback is the impossibility of taking into account the characteristic features of all subclasses of linear codes. In particular, the cyclic property is not taken into account at all for cyclic codes. Taking this property into account, one can go to a fundamentally different mathematical representation of cyclic codes – the theory of linear automata in Galois fields (linear finite-state machine).

For the automaton representation of cyclic codes, it is proved that the problem of syndromic decoding of these codes in the general case is an NP-complete problem. However, if to use the proposed hierarchical approach to problems of complexity, then on its basis it is possible to carry out a more accurate analysis of the growth of computational complexity. Correction of single errors during one time interval (one iteration) of decoding has a linear decoding complexity on the length of the codeword, and error correction during m iterations of permutations of codeword bits has a polynomial complexity. According to three subclasses of cyclic codes, depending on the complexity of their decoding: easy decoding (linear complexity), iteratively decoded (polynomial complexity), complicate decoding (exponential complexity). Practical ways to reduce the complexity of computations are considered: alternate use of probabilistic and deterministic linear codes, simplification of software and hardware implementation by increasing the decoding time, use of interleaving. A method of interleaving is proposed, which makes it possible to simultaneously generate the burst errors and replace them with single errors. The mathematical apparatus of linear automata allows solving together the indicated problems of error correction coding.

Author Biographies

Vasyl Semerenko, Vinnytsia National Technical University

PhD, Associate Professor

Department of Computer Technique

Oleksandr Voinalovich, Vinnytsia National Technical University

Postgraduate Student

Department of Computer Technique

References

  1. Shannon, C. E. (1948). A Mathematical Theory of Communication. Bell System Technical Journal, 27 (3), 379–423. doi: http://doi.org/10.1002/j.1538-7305.1948.tb01338.x
  2. Shannon, C. E. (1948). A Mathematical Theory of Communication. Bell System Technical Journal, 27 (4), 623–656. doi: http://doi.org/10.1002/j.1538-7305.1948.tb01338.x
  3. Costello, D. J., Hagenauer, J., Imai, H., Wicker, S. B. (1998). Applications of error-control coding. IEEE Transactions on Information Theory, 44 (6), 2531–2560. doi: http://doi.org/10.1109/18.720548
  4. Morelos-Zaragosa, R. H. (2002). The Art of Error Correcting Coding. Jon Wiley & Sons, 278. doi: http://doi.org/10.1002/0470847824
  5. Berlekamp, E., McEliece, R., van Tilborg, H. (1978). On the inherent intractability of certain coding problems (Corresp.). IEEE Transactions on Information Theory, 24 (3), 384–386. doi: http://doi.org/10.1109/tit.1978.1055873
  6. Melentev, O. G. (2007). Teoreticheskie aspektyi peredachi dannyih po kanalam s gruppiruyuschimisya oshibkami. Moscow: Goryachaya liniya–Telekom, 232.
  7. Vardy, A. (1997). The intractability of computing the minimum distance of a code. IEEE Transactions on Information Theory, 43 (6), 1757–1766. doi: http://doi.org/10.1109/18.641542
  8. 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: http://doi.org/10.15587/1729-4061.2015.39947
  9. Cormen, Т. H., Leiserson, C. E., Rivest R. L., Stain C. (2014). Introduction to Algorithms. London: The MIT Press, 1183.
  10. Semerenko, V. (2016). The theory of parallel crc codes based on automaton models. Eastern-European Journal of Enterprise Technologies, 6 (9 (84)), 45–55. doi: http://doi.org/10.15587/1729-4061.2016.85603
  11. Forney, G. D. (1967). Concatenated Codes. Cambridge: MIT Press.
  12. Wei, Y., Jiang, M., Xia, B., Chen, W., Yang, Y. (2013). A CRC-Aided Hybrid Decoding Algorithm for Turbo Codes. IEEE Wireless Communications Letters, 2 (5), 471–474. doi: http://doi.org/10.1109/wcl.2013.052813.130259
  13. Aho, A. V., Hopcroft, J. T., Ullman, J. D. (1976). The Design and Analysis of computer Algorithms. Addison-Wesley Publishing Company Reading.
  14. Semerenko, V. (2018). Iterative hard­-decision decoding of combined cyclic codes. Eastern-European Journal of Enterprise Technologies, 1 (9 (91)), 61–72. doi: http://doi.org/10.15587/1729-4061.2018.123207
  15. Prange, E. (1962). The use of information sets in decoding cyclic codes. IEEE Transactions on Information Theory, 8 (5), 5–9. doi: http://doi.org/10.1109/tit.1962.1057777
  16. Clark, G. C. Jr., Cain, J. B. (1981). Error-Correction for Digital Communications. New York and London: Plenum Press, 422. doi: http://doi.org/10.1007/978-1-4899-2174-1

Downloads

Published

2021-06-30

How to Cite

Semerenko, V., & Voinalovich, O. (2021). The simplification of computationals in error correction coding. Technology Audit and Production Reserves, 3(2(59), 24–28. https://doi.org/10.15587/2706-5448.2021.233656

Issue

Vol. 3 No. 2(59) (2021): Information and control systems

Section

Information Technologies: Reports on Research Projects

License

Copyright (c) 2021 Vasyl Semerenko, Oleksandr Voinalovich

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.