Method for Calculating Field Convolution Based on the Decomposition of a Multi-Valued Extended Galois Field

Relevance. One of the unsolved problems of the theory of error-correcting coding is the problem of constructing decoders of long codes with low computational complexity. From the point of view of algebraic coding theory, the cornerstone for this is the operation of multiplying two polynomials a and b over the field GF(q^k) modulo the third polynomial g. As q and k increase, the use of methods for calculating the field convolution based on the logarithm and antilogarithm operations becomes ineffective due to the use of a large amount of memory for constructing tables. Simplified implementations of the field convolution using the asymmetry of the accompanying matrix and analytical (non-tabular) methods of logarithm and antilogarithm using Zhegalkin polynomials have been developed only for q = 2. Multipliers based on shift registers have a significantly lower speed for large q and k.

The aim of the study is to find options for reducing the computational complexity of the field convolution operation in multivalued extended Galois fields during its synthesis in the logical basis "AND"‒"OR"‒"NOT".

Methods. An analysis of single-cycle methods for multiplying elements of a multivalued extended Galois field specified in vector or polynomial form for various power bases is carried out. Examples of calculating field convolutions in multivalued Galois fields by various methods are given. The structure of the considered type of fields is studied.

Results. It is shown that addition and multiplication operations in the field GF(q) synthesized on the elements of the logical basis "AND"‒"OR"‒"NOT" make the main contribution to the complexity of the resulting logical circuit. It is revealed that using the property of decomposition of the field GF(q^k) into subsets by the power of the primitive element of the field GF(q) allows to reduce the number of multiplication operations. A field convolution method based on the matrix method and the Hankel ‒ Toeplitz transform is proposed, taking into account the field structure, which allows to reduce the total number of logical elements and increase the performance of the designed circuit solution, namely, to reduce the Quine price and the circuit rank. A comparative assessment of the developed method is given.

Scientific novelty. For the first time, a method of field convolution of two vectors in the field GF(q^k) is proposed, one of which is presented in the indicator form.

Theoretical / Practical significance. A new method for calculating the field convolution based on the decomposition of a multivalued extended Galois field is proposed. Reduction of the total number of logical operations is proved. The proposed solution can be used in the synthesis of encoding and decoding devices for multi-valued (symbolic) codes on binary logic elements.

1. Rakhman P. Information Coding Using Reed-Solomon Codes. Ufa: Ufa State Petroleum Technical University Publ.; 2012, 167 p. (in Russ.)

2. Kognovitsky O. Theory, Methods and Algorithms for Solving Problems in Telecommunications Based on a Dual Basis and Recurrent Sequences. D.Sc Thesis. St. Petersburg: The Bonch-Bruevich Saint-Petersburg State University of Telecommunications Publ.; 2011. 427 p. (in Russ.) EDN:QFKYXL

3. Mutter V. Fundamentals of Noise-Immune Television Transmission of Information. Leningrad: Energoatomizdat; 1990. 288 p. (in Russ.)

4. Kognovitsky O.S., Syurin V.N., Assanovich B.A. Method for calculating logarithms in the traditional field GF(2m). Proceedings of the 9th All-Union Conference on Theories of Coding and Transmission of Information. Part 1. Odessa; 1988. p.100‒102. (in Russ.)

5. Rakhman P.A. Algorithm for Computing the Truncated Convolution of the Polynomials Over Galois Field and Its Hardware Implementation. Mezhdunarodnyi zhurnal prikladnykh i fundamentalnykh issledovanii. 2015;12-2:231‒235. (in Russ.) EDN:SZAEYV

6. Ivanova I.V. Scientific Foundations for Creating Automated Data Coding Systems in Finite Galois Fields Using Discrete Kleene Algebra Methods. D.Sc Thesis. St. Petersburg: North-West Technical University Publ; 2005. 276 p. (in Russ.) EDN:NNZFPD

7. Berlekamp E. R. Algebraic Coding Theory. 1968.

8. McWilliam F.J., Sloane N.J.A. The theory of error-correcting codes. North-Holland Publishing; 1977.

9. Kasami T., Tokura N., Iwadari E., Iragaki Y. Coding Theory. Moscow: Mir Publ.; 1978. 576 p. (in Russ.)

10. Rahman P.A. Arithmetic of a binary Galois field based on fast multiplication and inversion of field elements and its hardware implementation. Mezhdunarodnyi zhurnal prikladnykh i fundamentalnykh issledovanii. 2015;12-3:403‒408. EDN:VBUMBJ

11. Listopad E.V., Petrovsky A.A. Features of the implementation of operations of multiplication of Galois field elements on FPGA. Proceedings of the 53rd Scientific Conference of Graduate Students, Masters and Students of BSUIR, 2‒6 May 2017, Minsk, Republic of Belarus. Minsk: Belarusian State University of Informatics and Radioelectronics Publ.; 2017. p.234‒235. (in Russ.)

12. Kasperski K. Polynomial arithmetic and Galois fields, or information resurrected from the ashes II. Sistemnyi administrator. 2003;10(11):84‒90. (in Russ.) EDN:RDELQN

13. Salimov G.Yu. Proposals for the implementation of multiplication in a Galois field over an irreducible polynomial using the example of transformation L in the GOST R 34.1 2 2015 algorithm. Proceedings of the XXIInd Scientific and Practical Conference “RusCrypto 2020”, 17‒29 March 2020. 2020. (in Russ.) URL: https://ruscrypto.ru/resource/archive/rc2020/files/14_salimov.pdf [Accessed 17.04.2025]

14. Lidl R., Niederreiter G. Finite fields. London: Addison-Wesley Publishing; 1983.

15. Gabidullin E.M., Afanasyev V.B. Coding in Radio Electronics. Moscow: Radio i sviaz Publ.; 1986. 176 p. (in Russ.)

16. Peterson W.W., Weldon-jr E.J. Error-Correcting Codes. MIT Press; 1972. 575 p.

17. Clark J., Jr., Kane J. Error-Correcting Coding for Digital Communication. New York: Plenum Press; 1981.

18. Zolotarev V.V. Theory and Algorithms of Multithreshold Decoding. Moscow: Radio i sviaz Publ.; 2006. 266 p. (in Russ.)

19. Trifonov P.V. Fundamentals of Noise-Corrective Coding. St. Petersburg: ITMO University Publ.; 2022. 231 p. (in Russ.)

20. Ishmukhametov Sh.T., Latypov R.Kh., Stolov E.L., Rubtsova R.G. Introduction to Number Theory and Coding Theory. Kazan: Kazan University Publ.; 2014. 65 p. (in Russ.)

21. Ishmukhametov Sh.T., Rubtsova R.G. Calculations in Finite Fields. Kazan: Kazan University Publ.; 2019. 23 p. (in Russ.)

22. Nazarova A., Loktionova O., Spesivtsev G. Carnot Cards. Proceedings of the International Scientific and Practical Conference on Modeling of Information Systems and Technologies, 02 April 2024, Voronezh, Russian Federation. Voronezh: Voronezh State Forestry University Publ.; 2024. p.116‒121. (in Russ.) EDN:JPIWIW

23. Ismagilova E.I. Boolean Functions and Construction of Logical Circuits. Moscow: MIREA ‒ Russian Technological University Publ.; 2015. 160 p.

24. Zierler N. Linear vecurring sequences. Journal of the Society for Industrial and Applied Mathematics. 1959;7(1):31‒48. (in Russ.)