Presentation of Reed-Solomon codes based on automaton theory

Authors

DOI:

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

Keywords:

Reed-Solomon codes, automaton theory, linear finite-state machine (LFSM), decoding, quantum computer

Abstract

 

The object of research is the processes of error-correcting coding in telecommunication and computer systems. The main attention is paid to Reed-Solomon codes, which belong to the very widespread error-correcting codes. Despite the 60-year existence of these codes, the complexity of their decoding still remains a problem. This problem is mainly due to the use of an algebraic approach to their description.

The article proposes to use the theory of linear finite-state machine (LFSM) for RS codes as a mathematical basis, which is a combination of the theory of digital filters and finite automaton over nonbinary Galois fields. In the course of research, 12 types of LFSMs are considered for the first time: the recursive LFSMs of 8 types and the non-recursive LFSMs of 4 types.

The recursive LFSMs are used for systematic encoding and form a circuit for dividing of polynomials, and the non-recursive LFSMs are used for non-systematic encoding and form a circuit for multiplying of polynomials. All types of LFSMs give the same result for encoding and decoding, but with different complexity, which is important for practical implementation.

The automaton representation is the most suitable for PC codes, since it takes into account the cyclicity property and other features of these codes to the maximum. In contrast to algebraic methods, automaton decoding methods have a simple software and hardware implementation and high performance. With the help of automaton-graphical models, it can accurately estimate the corrective capability of the code. Automaton representation combines known methods of representing Reed-Solomon codes (polynomial, matrix, algebraic) and provides mutual transitions between them.

The article attention is spare to the fact that automaton methods for encoding and decoding (n, k)-codes of RS using quantum computers give a gain in time n times.

Author Biography

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

PhD, AssociateProfessor

DepartmentofComputerTechnique

References

  1. Luzhetskyi, V. Semerenko, V. (2019). Automaton Presentations of Reed-Solomon Codes. Advanced Information and Communication Technologies. Lviv, 50–53. doi: http://doi.org/10.1109/aiact.2019.8847892
  2. Sklar, B. (2001). Digital Communications. Fundamentals and Applications. Los Angeles: Prentice Hall PTR.
  3. Morelos-Zaragosa, R. H. (2002). The Art of Error Correcting Coding. Jon Wiley & Sons. doi: http://doi.org/10.1002/0470847824
  4. Semerenko, V. (2018). Automaton Presentations of Cyclic Codes. Herald of Vinnytsia Polytechnical Institute, 2 (137), 89–100.
  5. Ifeachor, E. C., Jervis, B. W. (2002). Digital Signal Proccesing. A practical Approach. Los Angeles: Prentice Hall, 925.
  6. Friedland, B. (1959). Linear Modular Sequential Circuits. IRE Transactions on Circuit Theory, 6 (1), 61–68. doi: http://doi.org/10.1109/tct.1959.1086529
  7. Gill, A. (1967). Linear Sequential Circuits. Analysis, Synthesis and Application. New York, London: McGraw-Hill Book Company, 215.
  8. Milovanovic, E., Stojcev, M., Milovanovic, I., Nikolic, T. (2015). Concurrent Generation of Pseudo Random Numbers with LFSR of Fibonacci and Galois Type. Computing and Informatics, 34, 941–958.
  9. Semerenko, V. P. (2011). Dekodirovanie kodov Rida-Solomona na osnove grafovoi i avtomatnoi modelei. Elektronnoe modelirovanie, 1, 57–72.
  10. Solovyev, V. M. (2015). Quantum Computers and Quantum Algorithms. Part 1. Quantum Computers. Izvestiya of Saratov University. New Series. Series: Mathematics. Mechanics. Informatics, 15 (4), 462–477. doi: http://doi.org/10.18500/1816-9791-2015-15-4-462-477
  11. Calderbank, A. R., Rains, E. M., Shor, P. M., Sloane, N. J. A. (1998). Quantum error correction via codes over GF(4). IEEE Transactions on Information Theory, 44 (4), 1369–1387. doi: http://doi.org/10.1109/18.681315
  12. Häffner, H., Hänsel, W., Roos, C. F., Benhelm, J., Chek-al-kar, D., Chwalla, M. et. al. (2005). Scalable multiparticle entanglement of trapped ions. Nature, 438 (7068), 643–646. doi: http://doi.org/10.1038/nature04279

Downloads

Published

2020-08-31

How to Cite

Semerenko, V. (2020). Presentation of Reed-Solomon codes based on automaton theory. Technology Audit and Production Reserves, 4(2(54), 31–35. https://doi.org/10.15587/2706-5448.2020.210272

Issue

Vol. 4 No. 2(54) (2020): Information and control systems

Section

Reports on research projects

License

Copyright (c) 2020 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.