М.Ю. Алиев – начальник отдела,  АО «Тайфун» (г. Калуга) E-mail: arls@mail.ru

А.М. Донецков – к.т.н., доцент,  кафедра «Информационные системы и сети», Калужский филиал МГТУ им. Н.Э. Баумана E-mail: dam1358@mail.ru

А.С. Николаев – к.т.н., доцент,  кафедра «Информационные системы и сети», Калужский филиал МГТУ им. Н.Э. Баумана E-mail: nikolanta@yandex.ru

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

Цель. Предложить метод минимизации пороговой и мажоритарной функций, основанный на построении дизъюнктивной нормальной формы.

Результаты. Разработан однозначный алгоритм минимизации, позволяющий получить одинаковые результаты, не зависящие от человека, выполняющего минимизацию. Предложен набор несложных выражений, описывающих процесс получения мажоритарной функции в виде набора несложных формул, что по сравнению с единым выражением, описывающим рассчитываемую функцию, как это делается во всех других алгоритмах минимизации, позволяет уменьшить число механических ошибок, возникающих в процессе минимизации, позволяя легче их обнаружить и исправить. Относительная простота и формализация процесса минимизации позволяет распространить предложенный алгоритм на минимизацию пороговых и мажоритарных функций с бóльшим числом входов, чем доступно для других существующих алгоритмов. Описание алгоритма сопровождается выполнением примера его выполнения для конкретных значений числа входов мажоритарного элемента. Однозначность алгоритма минимизации позволила создать выражение для подсчета числа операций, выполняемых при вычислении функции. Это позволяет оценить сложность создаваемого устройства до создания самого устройства.

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

1. Колесник В.Д., Мирончиков Е.Т. Декодирование циклических кодов. М.: Связь. 1968. 252 с.
2. Месси Дж. Пороговое декодирование: Пер. с англ / Под ред. Э.Л. Блоха. М.: Мир. 1966. 207 с.
3. Карпов Ю.Г. Теория автоматов. СПб.: Питер. 2002. 206 с.
4. Николаев А.С. Минимизация мажоритарного элемента в базисе И-ИЛИ // Сб. статей Междунар. научно-практ. конф. «Современная наука: Теоретический и практический взгляд» 25 декабря 2014 г. Уфа: Аэтерна. 2014. Ч. 2. С. 54−56.
5. Николаев А.С. Минимизация формулы пороговой функции // Символ науки. 2016. № 4. Ч. 3. С. 105−107.
6. Николаев А.С. Сложность пороговой функции и ее инверсии // Символ науки. 2016. № 7. Ч. 2. С. 83−85.
7. Николаев А.С. Минимизация схемы мажоритарного элемента // Электромагнитные волны и электронные системы. 2016. Т. 21. № 7. С. 32−36.
8. Николаев А.С., Аксенов А.Е. Регулярная процедура минимизации мажоритарного элемента // Электромагнитные волны и электронные системы. 2017. Т. 22. № 3. С. 42−46.
9. Николаев А.С., Алиев М.Ю. Упрощение схемы порогового элемента // Электромагнитные волны и электронные системы. 2018. Т. 23. № 3. С. 6−12.
10. Максимов А.В. Оптимальное проектирование ассемблерных программ вычислительных алгоритмов: теория, инженерные методы: Учеб. пособие. СПб.: Лань. 2016. 192 с.