Error correction by Reed–Solomon codes using its automorphisms

The article explores the syndrome invariants of АГ-group of automorphisms of Reed–Solomon codes (RS-codes) that are a joint group of affine and cyclic permutations. The found real invariants are a set of norms of N Г-orbits that make up one or another АГ-orbit. The norms of Г-orbits are vectors with 2 1 Cδ− coordinates from the Galois field, that are determined by all kinds of pairs of components of the error syndromes. In this form, the invariants of the АГ-orbits were cumbersome and difficult to use. Therefore, their replacement by conditional partial invariants is proposed. These quasi-invariants are called norm-projections. Norm-projection uniquely identifies its АГ-orbit and therefore serves as an adequate way for formulating the error correction method by RS-codes based on АГ-orbits. The power of the АГ-orbits is estimated by the value of N2, equal to the square of the length of the RS-code. The search for error vectors in transmitted messages by a new method is reduced to parsing the АГ‑orbits, but actually their norm-projections, with the subsequent search for these errors within a particular АГ-orbit. Therefore, the proposed method works almost N2 times faster than traditional syndrome methods, operating on the basic of the “syndrome – error” principle, that boils down to parsing the entire set of error vectors until a specific vector is found.

1. MacWilliams F. J., Sloan N. J. A. The Theory of Error-Correcting Codes. North Holland, 1977. XII, 762 p. (North- Holland Mathematical Library ; Vol. 16).

2. Blejhut R. Theory and Practice of Error Control Codes. Addison-Wesley, 1983. 500 p.

3. Sklar B. Digital Communication. Fundamentals and Applications. 2nd ed. Prentice Hall PTR, 2001. 1104 p.

4. Kudryashov B. D. Fundamentals of Coding Theory. St. Petersburg, BHV-Petersburg Publ., 2016. 400 p. (in Russian).

5. Marov A. V., Uteshev A. Yu. Matrix formalism of the Reed–Solomon codes. Vestnik Sankt-Peterburgskogo gosudarstvennogo universiteta. Seriya 10, Prikladnaya matematika. Informatika. Protsessy upravleniya = Vestnik of Saint

6. Petersburg University. Applied Mathematics. Computer Science. Control Processes, 2016, issue 4, pp. 3–17. https://doi.org/10.21638/11701%2Fspbu10.2016.401

7. Semyonov S. I., Lipnitsky V. А. Advantages of using Galois field theory for processing RS-codes. Sbornik nauchnyh statei Voennoi academii Respubliki Belarus’ [Collection of Scientific Articles of the Military Academy of the Republic of Belarus], 2019, iss. 36, pp. 84–93 (in Russian).

8. Lipnitsky V. A., Konopel’ko V. K. Norm Decoding of Error-Correcting Codes and Algebraic Equations. Minsk, BSU Publ. Center, 2007. 239 p. (in Russian).

9. Lipnitsky V. А., Semyonov S. I. Norms of syndromes and their properties in Reed-Solomon codes. Vestnik Polotskogo gosudarstvennogo universiteta. Seriya C. Fundamental’nye nauki = Vestnik of Polotsk State University. Part C. Fundamental Sciences, 2020, no. 4, рр. 2–9 (in Russian).

10. Lidl R., Niderrajter G. Finite Fields (Encyclopedia of Mathematics and its Applications). 2nd ed. Cambridge University Press, 2008. 772 p. https://doi.org/10.1017/CBO9780511525926

11. Lipnitsky V. А. Modern Applied Algebra. The Mathematical Foundations of Protecting Information from Interference and Unauthorized Access. Minsk, BSUIR, 2006. 88 p. (in Russian).