кандидат технических наук, сотрудник Академии Федеральной службы охраны Российской Федерации
Актуальность. Одной из нерешенных проблем теории помехоустойчивого кодирования остается проблема построения декодеров длинных кодов с низкой вычислительной сложностью. С точки зрения алгебраической теории кодирования краеугольным камнем для этого является операция умножения двух многочленов a и b над полем GF(qk) по модулю третьего многочлена g. С возрастанием q и k применение методов вычисления полевой свертки на основе операций логарифмирования и антилогарифмирования становится малоэффективным ввиду задействования большого объема памяти для построения таблиц. Упрощенные реализации полевой свертки, использующие несимметричность сопровождающей матрицы, и аналитические (не табличные) методы логарифмирования и антилогарифмирования, использующие полиномы Жегалкина, разработаны только для q = 2. Умножители на основе регистров сдвига обладают значительно меньшим быстродействием при больших q и k.
Целью исследования является поиск вариантов снижения вычислительной сложности операции полевой свертки в многозначных расширенных полях Галуа при ее синтезе в логическом базисе «И»‒«ИЛИ»‒«НЕ».
Методы. Проведен анализ однотактных методов умножения элементов многозначного расширенного поля Галуа, заданных в векторном или полиномиальном виде для различных степенных базисов. Приведены примеры вычисления полевых сверток в многозначных полях Галуа различными методами. Изучена структура рассматриваемого типа полей.
Решение. Показано, что операции сложения и умножения в поле GF(q), синтезированные на элементах логического базиса «И»‒«ИЛИ»‒«НЕ», вносят основной вклад в сложность итоговой логической схемы. Выявлено, что использование свойства разложения поля GF(qk) на подмножества по степени примитивного элемента поля GF(q) позволяет сократить число операций умножения. Предложен метод полевой свертки на основе матричного метода и преобразования Ганкеля ‒ Теплица, учитывающий структуру поля, что позволяет сократить общее число логических элементов и повысить быстродействие проектируемого схемотехнического решения, а именно уменьшить цену по Квайну и ранг схемы. Дана сравнительная оценка разработанного метода.
Новизна: впервые предложен метод полевой свертки двух векторов в поле GF(qk), один из которых представлен в индикаторном виде.
Теоретическая значимость. Предложен новый метод вычисления полевой свертки на основе разложения многозначного расширенного поля Галуа. Доказано сокращение общего числа логических операций.
Практическая значимость. Предложенное решение может быть использовано при синтезе кодирующих-декодирующих устройств многозначных (символьных) кодов на элементах двоичной логики.
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(qk) 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(qk) 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(qk) 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.
The authors declare that there are no conflicts of interest present.