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

Актуальность. Одной из нерешенных проблем теории помехоустойчивого кодирования остается проблема построения декодеров длинных кодов с низкой вычислительной сложностью. С точки зрения алгебраической теории кодирования краеугольным камнем для этого является операция умножения двух многочленов a и b над полем GF(q^k) по модулю третьего многочлена g. С возрастанием q и k применение методов вычисления полевой свертки на основе операций логарифмирования и антилогарифмирования становится малоэффективным ввиду задействования большого объема памяти для построения таблиц. Упрощенные реализации полевой свертки, использующие несимметричность сопровождающей матрицы, и аналитические (не табличные) методы логарифмирования и антилогарифмирования, использующие полиномы Жегалкина, разработаны только для q = 2. Умножители на основе регистров сдвига обладают значительно меньшим быстродействием при больших q и k.

Целью исследования является поиск вариантов снижения вычислительной сложности операции полевой свертки в многозначных расширенных полях Галуа при ее синтезе в логическом базисе «И»‒«ИЛИ»‒«НЕ».

Методы. Проведен анализ однотактных методов умножения элементов многозначного расширенного поля Галуа, заданных в векторном или полиномиальном виде для различных степенных базисов. Приведены примеры вычисления полевых сверток в многозначных полях Галуа различными методами. Изучена структура рассматриваемого типа полей.

Решение. Показано, что операции сложения и умножения в поле GF(q), синтезированные на элементах логического базиса «И»‒«ИЛИ»‒«НЕ», вносят основной вклад в сложность итоговой логической схемы. Выявлено, что использование свойства разложения поля GF(q^k) на подмножества по степени примитивного элемента поля GF(q) позволяет сократить число операций умножения. Предложен метод полевой свертки на основе матричного метода и преобразования Ганкеля ‒ Теплица, учитывающий структуру поля, что позволяет сократить общее число логических элементов и повысить быстродействие проектируемого схемотехнического решения, а именно уменьшить цену по Квайну и ранг схемы. Дана сравнительная оценка разработанного метода.

Новизна: впервые предложен метод полевой свертки двух векторов в поле GF(q^k), один из которых представлен в индикаторном виде.

Теоретическая значимость. Предложен новый метод вычисления полевой свертки на основе разложения многозначного расширенного поля Галуа. Доказано сокращение общего числа логических операций.

Практическая значимость. Предложенное решение может быть использовано при синтезе кодирующих-декодирующих устройств многозначных (символьных) кодов на элементах двоичной логики.

1. Рахман П.А. Кодирование информации с применением кодов Рида-Соломона. Уфа: УГНТУ, 2012. 167 с.

2. Когновицкий О.С. Теория, методы и алгоритмы решения задач в телекоммуникациях на основе двойственного базиса и рекуррентных последовательностей. Дис. … докт. техн. наук. СПб.: СПбГУТ, 2011. 427 с. EDN:QFKYXL

3. Муттер В.М. Основы помехоустойчивой телепередачи информации. Л.: Энергоатомиздат. Ленингр. отд-ние, 1990. 288 с.

4. Когновицкий О.С., Сюрин В.Н., Ассанович Б.А. Метод вычисления логарифма в конечном поле GF(2m) // Девятая всесоюзная конференция по теории кодирования и передачи информации. Часть 1. Тезисы докладов. Одесса, 1988. С. 100‒102.

5. Рахман П.А. Рекуррентный алгоритм вычисления усеченной свертки полиномов над полем Галуа и его аппаратная реализация // Международный журнал прикладных и фундаментальных исследований. 2015. № 12-2. С. 231‒235. EDN:SZAEYV

6. Иванова И.В. Научные основы создания автоматизированных систем кодирования данных в конечных полях Галуа методами дискретной алгебры Клини. Дис. … докт. техн. наук. СПб.: СЗТУ, 2005. 276 с. EDN:NNZFPD

7. Берлекэмп Э.Р. Алгебраическая теория кодирования. Пер. с англ. М.: Мир, 1971. 478 с.

8. Мак-Вильяме Ф.Дж., Споэн Н.Дж.А. Теория кодов, исправляющих ошибки. Пер. с англ. М: Связь, 1979. 744 с.

9. Касами Т., Токура Н., Ивадари Е., Ирагаки Я. Теория кодирования. М.: Мир, 1978. 576 с.

10. Рахман П.А. Арифметика двоичного поля Галуа на базе быстрого умножения и инвертирования элементов поля и ее аппаратная реализация // Международный журнал прикладных и фундаментальных исследований. 2015. № 12-3. С. 403‒408. EDN:VBUMBJ

11. Листопад Е.В., Петровский А.А. Особенности реализации операций умножения элементов поля Галуа на FPGA // 53-я научная конференция аспирантов, магистров и студентов БГУИР (Минск, Республика Беларусь, 2‒6 мая 2017 г.). Минск: Белорусский государственный университет информатики и радиоэлектроники, 2017. С. 234‒235.

12. Касперски К. Полиномиальная арифметика и поля Галуа, или информация, воскресшая из пепла II // Системный администратор. 2003;10(11):84‒90. EDN:RDELQN

13. Салимов Г.Ю. Предложения по реализации умножения в поле Галуа над неприводимым многочленом на примере преобразования L в алгоритме ГОСТ Р 34.1 2 2015 // XXII научно-практическая конференция «РусКрипто 2020» (17‒29 марта 2020 г.) 2020. URL: https://ruscrypto.ru/resource/archive/rc2020/files/14_salimov.pdf (дата обращения 17.04.2025)

14. Лидл Р., Нидеррайтер Г. Конечные поля. Пер. с англ. М.: Мир, 1988. 818 с.

15. Габидулин Э.М., Афанасьев В.Б. Кодирование в радиоэлектронике. М.: Радио и связь, 1986. 176 с.

16. Питерсон Ч., Уэлдон Э. Коды, исправляющие ошибки. Пер. с англ. М.: Мир, 1976. 594 с.

17. Кларк Дж., мл., Кейн Дж. Кодирование с исправлением ошибок в системах цифровой связи. Пер. с англ. М.: Радио и связь, 1987. 391 с.

18. Золотарев В.В. Теория и алгоритмы многопорогового декодирования. М.: Радио и связь, 2006. 266 с.

19. Трифонов П.В. Основы помехоустойчивого кодирования. СПб.: Университет ИТМО, 2022. 231 с.

20. Ишмухаметов Ш.Т., Латыпов Р.Х., Столов Е.Л., Рубцова Р.Г. Введение в теорию чисел и теорию кодирования: учебное пособие. Казань: Казанский университет, 2014. 65 с.

21. Ишмухаметов Ш.Т., Рубцова Р.Г. Вычисления в конечных полях: учебно-методическое пособие. Казань: Казанский университет, 2019. 23 с.

22. Назарова А.К., Локтионова О.Е., Спесивцев Г.А. Карты Карно // Международная научно-практическая конференция «Моделирование информационных систем и технологий» (Воронеж, Российская Федерация, 02 апреля 2024 г.). Воронеж: Воронежский государственный лесотехнический университет имени Г.Ф. Морозова, 2024. С. 116‒121. EDN:JPIWIW

23. Исмагилова Е.И. Булевы функции и построение логических схем. М.: МИРЭА, 2015. 160 с.

24. Цирлер Н. Линейные возвратные последовательности // Кибернетический сборник. 1963. № 6. С. 31‒48.