МЕТОДЫ СИНТЕЗА АЛГЕБРАИЧЕСКОЙ НОРМАЛЬНОЙ ФОРМЫ ФУНКЦИЙ МНОГОЗНАЧНОЙ ЛОГИКИ

Полный текст:


Аннотация

Стремительное развитие методов помехоустойчивого кодирования, криптографии, теории синтеза сигналов, основанных на принципах многозначной логики, диктуют необходимость более полного изучения форм представления функций многозначной логики. В частности, для булевых функций широкое распространение получила алгебраическая нормальная форма, известная также как полином Жегалкина, которая хорошо описывает многие криптографические свойства булевых функций. В настоящей статье формализуется понятие алгебраической нормальной формы функции многозначной логики. Предложены методы синтеза алгебраической нормальной формы 3-функций и 5-функций, которые работают по аналогии с преобразованием Рида-Маллера для булевых функций: на основе рекуррентно синтезируемых матриц преобразования. Выдвинута гипотеза, определяющая правила синтеза матриц как для перехода от таблицы истинности к коэффициентам алгебраической нормальной формы, так и обратного преобразования для любого, наперед заданного количества переменных 3-функции либо 5-функции. В статье также введено определение алгебраической степени нелинейности функций многозначной логики и S-блока подстановки, основанных на принципах многозначной логики. Так, разработанный метод синтеза алгебраической нормальной формы 3-функций применен к известной конструкции рекуррентного синтеза S-блоков длины N = 3k, в результате чего вычислены их алгебраические степени нелинейности. Полученные результаты могут стать основой как для дальнейших теоретических исследований, так и для практического применения: разработки новых криптографических примитивов, корректирующих кодов, алгоритмов сжатия информации, сигнальных конструкций, алгоритмов блочного и поточного шифрования, основанных на перспективных принципах многозначной логики. Кроме того, методы синтеза алгебраической нормальной формы функций многозначной логики являются основой для их программной и аппаратной имплементации.


Об авторах

А. В. Соколов
Одесский национальный политехнический университет
Украина
Артем Соколов  - кандидат технических наук, старший преподаватель кафедры Информационной безопасности


О. Н. Жданов
Сибирский государственный аэрокосмический университет им. М. Ф. Решетнёва
Россия
Жданов Олег Николаевич кандидат технических наук, доцент кафедры безопасности информационных технологий


О. А. Айвазян
Одесский национальный политехнический университет
Украина
Айвазян Оганнес - аспирант, инженер-программист


Список литературы

1. Мазурков, М. И. О влиянии вида ортогонального преобразования на пик-фактор спектра в системах с CDMA / М. И. Мазурков, А. В. Соколов, Н. А. Барабанов. – Інформатика та математичні методи в моделюванні, 2015. – Т .5, № 1. – С. 28–37.

2. Falkowski, B. J. Application of Sign Hadamard¬Haar Transform in Ternary Communication System / B. J. Falkowski, S. Yan. – International Journal of Electronics, 1995. – Vol. 79(5). – P. 551–559.

3. Кузнецов, В. С. Троичные каскадные коды с модуляцией КАМ-9 и их возможности / В. С. Кузнецов. – «ИнфоЭлектросвязь», 2009. – С. 30–33.

4. Мазурков, М. И. Системы широкополосной радиосвязи / М. И. Мазурков – Одесса: Наука и Техника, 2010, с. 340. – ISBN 978-966-8335-95-2.

5. Петелин, Ю. В. Перспективы использования сигнально-кодовых конструкций типа троичных М-последовательностей в спутниковых каналах связи / Ю. В. Петелин, М. А. Ковалев, А. А. Макаров // Информацион¬ но-управляющие системы. – 2006. – №. 5. – С. 32–35.

6. Жданов, О. Н. Алгоритм построения оптимальных по критерию нулевой корреляции недвоичных блоков за¬ мен / О. Н. Жданов, А. В. Соколов. – Проблемы физики, математики и техники, 2015. – № 3(24). – С. 94–97.

7. Логачев, О. А. Булевы функции в теории кодирования и криптологии / О. А. Логачев, А. А. Сальников, В. В. Ящен¬ ко. – М: Издательство МЦНМО. – 2004. – 472 с.

8. Qingshu, Meng A novel algorithm enumerating bent functions / Qingshu Meng, Min Yang, Huanguo Zhang, Jingsong Cui // Discrete Mathematics, 2008. – Volume 308, Issue 23, 2008. – P. 5576–5584.

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

10. Мазурков, М. И. Генератор ключевых последовательностей на основе дуальных пар бент-функций / М. И. Ма¬ зурков, Н. А. Барабанов, А. В. Соколов. – Труды Одесского политехнического университета, 2013. – Вып. 3 (42). – С. 150–156.

11. Жегалкин, И. И. Арифметизация символической логики / И. И. Жегалкин. – Матем. сб., 1929. – 305–338.

12. Ростовцев, А. Г. Криптография и защита информации / А. Г. Ростовцев. – СПб.: Мир и Семья. – 2002.

13. Кормен, Т. Алгоритмы: построение и анализ / Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн, – М.: Вильямс, 2006. – с. 1328.

14. Соколов, А. В. Новые методы синтеза нелинейных преобразований современных шифров / А. В. Соколов. – Lap Lambert Academic Publishing, Germany, 2015. – 100 с.


Дополнительные файлы

Для цитирования: Соколов А.В., Жданов О.Н., Айвазян О.А. МЕТОДЫ СИНТЕЗА АЛГЕБРАИЧЕСКОЙ НОРМАЛЬНОЙ ФОРМЫ ФУНКЦИЙ МНОГОЗНАЧНОЙ ЛОГИКИ. «Системный анализ и прикладная информатика». 2016;(1):69-76.

For citation: Sokolov A.V., Zhdanov O.N., Ayvazian O.A. SYNTHESIS METHODS OF ALGEBRAIC NORMAL FORM OF MANY-VALUED LOGIC FUNCTIONS. «System analysis and applied information science». 2016;(1):69-76. (In Russ.)

Просмотров: 331

Обратные ссылки

  • Обратные ссылки не определены.


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.

ISSN 2309-4923 (Print)
ISSN 2414-0481 (Online)