Метод вычисления полевой свертки на основе разложения многозначного расширенного поля Галуа

Актуальность. Одной из нерешенных проблем теории помехоустойчивого кодирования остается проблема построения декодеров длинных кодов с низкой вычислительной сложностью. С точки зрения алгебраической теории кодирования краеугольным камнем для этого является операция умножения двух многочленов a и b над полем GF(qk) по модулю третьего многочлена g. С возрастанием q и k применение методов вычисления полевой свертки на основе операций логарифмирования и антилогарифмирования становится малоэффективным ввиду задействования большого объема памяти для построения таблиц. Упрощенные реализации полевой свертки, использующие несимметричность сопровождающей матрицы, и аналитические (не табличные) методы логарифмирования и антилогарифмирования, использующие полиномы Жегалкина, разработаны только для q = 2. Умножители на основе регистров сдвига обладают значительно меньшим быстродействием при больших q и k.Целью исследования является поиск вариантов снижения вычислительной сложности операции полевой свертки в многозначных расширенных полях Галуа при ее синтезе в логическом базисе «И»‒«ИЛИ»‒«НЕ».Методы. Проведен анализ однотактных методов умножения элементов многозначного расширенного поля Галуа, заданных в векторном или полиномиальном виде для различных степенных базисов. Приведены примеры вычисления полевых сверток в многозначных полях Галуа различными методами. Изучена структура рассматриваемого типа полей.Решение. Показано, что операции сложения и умножения в поле GF(q), синтезированные на элементах логического базиса «И»‒«ИЛИ»‒«НЕ», вносят основной вклад в сложность итоговой логической схемы. Выявлено, что использование свойства разложения поля GF(qk) на подмножества по степени примитивного элемента поля GF(q) позволяет сократить число операций умножения. Предложен метод полевой свертки на основе матричного метода и преобразования Ганкеля ‒ Теплица, учитывающий структуру поля, что позволяет сократить общее число логических элементов и повысить быстродействие проектируемого схемотехнического решения, а именно уменьшить цену по Квайну и ранг схемы. Дана сравнительная оценка разработанного метода.Новизна: впервые предложен метод полевой свертки двух векторов в поле GF(qk), один из которых представлен в индикаторном виде.Теоретическая значимость. Предложен новый метод вычисления полевой свертки на основе разложения многозначного расширенного поля Галуа. Доказано сокращение общего числа логических операций.Практическая значимость. Предложенное решение может быть использовано при синтезе кодирующих-декодирующих устройств многозначных (символьных) кодов на элементах двоичной логики.

помехоустойчивое кодирование, полевая свертка, поле Галуа, матричный метод, преобразования Гаккеля ‒ Теплица, цена по Квайну