Estimation of the correcting capability of cyclic codes based on their automation models

Authors

DOI:

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

Keywords:

cyclic codes, code distance, correction capability of the code, linear finite-state machine (LFSM)

Abstract

We have considered a new method of presenting cyclic codeswith the use of finite automata in binary Galois fields - linear finite-state machine (LFSM). The automatic presentation allows using new positions in the approach to solving the fundamental problem in the theory of error correcting coding, which entails identifyingand correcting the capacity of a given code.

Instead of the conventional minimum code distance, which is not a comprehensive description of the code and is difficult to calculate, we suggest direct identifying of the number of detected and corrected errors by the automatic and graphic models of the cyclic code. The paper proves that the structure of LSS zero cycles gives the most accurate assessment that can be applied for different types of errors (both occasional and error packages) as well as for all subclasses of cyclic codes (Hamming, Bose-Chaudhuri-Hocquenghem, Fire, and others). We have presented an algorithm for building an automatic code mode and evaluating its capacity.

We have introduced new characteristics of error detection and correction  capabilities of cyclic codes. These are ranges of different kinds of errors, with precise indication of the number of random errors and bursts error that are revealed and corrected.

Author Biography

Василий Петрович Семеренко, Vinnytsia National Technical University Khmelnytske shose 95, Vinnytsia, Ukraine, 21021

PhD, Associate Professor

Department of computer technique

References

  1. Sklar, B. (2001). Digital Communications. Fundamentals and Applications. 2nd ed. Los Angeles: Prentice Hall. (Russ. Ed.: Skljar, B. Cifrovaja svjaz'. Teoreticheskie osnovy i prakticheskoe primenenie, second edition. Moscow: Izdatel'skij dom “Vil'jams”, 2004. 1104.)
  2. Blahut, R. E. (1984). Theory and Practice of Error Control Codes. London: Reading, MA: Addison-Wesley Addison-Wesley Publising Company. (Russ. Ed.: Blejhut R. Teorija i praktika kodov, ispravljajushhih oshibki Moscow: Mir, 1986. 576.
  3. Morelos-Zaragosa, R. H. (2002). The Art of Error Correcting Coding. Jon Wiley & Sons. (Russ. Ed.: Morelos-Saragosa R. Iskusstvo pomehoustojchivogo kodirovanija. Metody, algoritmy, primenenie Moscow: Tehnosfera, 2006. 320).
  4. Berlecamp, E., McEliece, R., van Tilborg, H. (1978). Hardness of Approximating the Minimum Distance of a Linear Code. IEEE Trans. Inform. Theory. 21 (5), 384–386.
  5. Vardy, A. (1997). The Intractability of Computing the Minimum Distance of a Code. IEEE Transactions on Information Theory. 43 (6), 1757–1766. doi: 10.1109/18.641542
  6. Dumer, I. Micciancio, D., Sudan,M. (2003). Hardness of Approximating the Minimum Distance of a Linear Code. 2000 IEEE International Symposium on Information Theory, 49 (1), 22–37. doi: 10.1109/isit.2000.866550
  7. Hartmann, C., Tzeng, K. (1972). Generalizations of the BCH Bound. Information and Control, 20 (5), 489–498. doi: 10.1016/s0019-9958(72)90887-x
  8. Roos, C. (1982). A Generalization of the BCH Bound for Cyclic Codes, Including the Hartmann-Tzeng Bound Journal of Combinatorial Theory, Series A. 33 (2), 229–232. doi: 10.1016/0097-3165(82)90014-0
  9. Boston, N. (2001). Bounding Minimum Distances of Cyclic Codes Using Algebraic Geometry. Electronic Notes in Discrete Mathematics, 6 (5), 384–386. doi: 10.1016/s1571-0653(04)00190-8
  10. van Lint, J., Wilson, R. (1986). On The Minimum Distance of Cyclic Codes. IEEE Transactions on Information Theory, 32 (1), 23–40. doi: 10.1109/tit.1986.1057134
  11. Kaida, T., Zheng, J. A. (2015). A Note on the Rank Bounded Distance and Its Algorithms for Cyclic Codes. Pure and Applied Mathematics Journal, 4 (2-1), 36–41. Available at: http://article.sciencepublishinggroup.com/pdf/10.11648.j.pamj.s.2015040201.17.pdf doi: 10.11648/j.pamj.s.2015040201.17
  12. Gill, A. (1967). Linear Sequential Circuits. Analysis, Synthesis and Application. New York, London: McGraw-Hill Book Company. (Russ. Ed.: Gill A. Linejnye Posledovatel'nostnye Mashiny (Linear Sequential Machines). Moscow, USSR: Nauka, 1974. 288.)
  13. Semerenko, V. P. (2010). Vysokoproyzvodytel'nye alhorytmy dlia yspravlenyia nezavysymykh oshybok v tsyklycheskykh kodakh [The High-efficiency Algorithms of Random Errors Correction in Cyclic Codes]. Systemy obrobky informatsii: zb. nauk. prats'. Kharkiv: KhUPS, 3 (84), 80–89. [in Russian]
  14. Clark, Jr. G. C., Cain, J. B. (1982). Error-Correction Coding for Digital Communications. New York, London: Plenum Press. (Russ. Ed.: Skljar, B. Cifrovaja svjaz'. Teoreticheskie osnovy i prakticheskoe primenenie, 2-e izd. Moscow: Izdatel'skij dom “Vil'jams”, 2004. 1104.)
  15. Verner, M. (2002). Information und Codierung. Wiesbaden: Vieweg [In German]. (Russ. Ed.: Verner M. Osnovy kodirovanija Moscow: Tehnosfera, 2004. 288.)
  16. Semerenko, V. P. (2009). Burst-Error Correction for Cyclic Codes. Proceeding of International IEEE Conference EUROCON2009, 1646–1651. doi: 10.1109/eurcon.2009.5167864

Downloads

Published

2015-04-20

How to Cite

Семеренко, В. П. (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. https://doi.org/10.15587/1729-4061.2015.39947

Issue

Vol. 2 No. 9(74) (2015): Information and controlling system

Section

Information and controlling system

License

Copyright (c) 2015 Василий Петрович Семеренко

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.