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

Keywords: