Нояб. 23

Геометрический подход к упрощению логических схем

Об авторе: Денис Морозов, к.ф.-м.н., работает на должности доцента кафедры математики НаУКМА, также является консультантом компании GlobalLogic. Работает над докторской диссертацией, сфера научных интересов — конечные автоматы и группы автоморфизмов деревьев.

Комбинационные логические схемы — альтернатива нейронным сетям при реализации формализованных реакций системы на заданные входные состояния. Естественно, чем проще схема, тем легче она тестируется и тем прозрачнее работа с ней. Геометрическому подходу упрощения комбинационных логических схем и посвящена данная статья.

Методы работы с такими схемами будут полезны инженерам, занимающимся разработкой интеллектуальных систем принятия решений и управления, а также hardware-инженерам, непосредственно занимающимися цифровой схемотехникой.

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

Комбинационно-логические схемы vs нейронные сети

Не так давно нейронные сети пережили второе рождение и сейчас большой процент задач, например, задачи распознавания звука, изображений, проблематики естественного языка, перевода решаются именно при помощи аппарата нейронных сетей. И возникает естественный вопрос: а зачем еще что-то другое? Ведь нейронные сети неплохо решают задачи, которые перед ними ставятся. Но здесь надо понимать, что такое нейронная сеть, каковы ее преимущества и ограничения.

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

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

Возвращаясь к комбинационно-логическим схемам, их преимущество как раз и заключается в том, что если вам удалось среду, с которой вы работаете, разбить на маленькие модули, то уже не нужны нейронные сети. Можно строить логические схемы, а у них есть замечательное свойство — существует достаточное количество прозрачных эффективных методов тестирования таких схем. То есть мы можем фиксировать определенные стандарты безопасности для этих маленьких модулей. Реализовать не просто интеллектуальное поведение, которое является достаточно сложным, но реализовать сложное поведение, отвечающее определенным стандартам безопасности, и это очень важный момент.

Кроме того, комбинационные логические схемы самодокументируемы. Логические связки конъюнкция и дизъюнкция представляются с сохранением контекста в естественном языке союзами «и», «или». Простыми словами, по виду логической схемы вполне возможно понять, как она работает. Нейронные сети не обладают данным преимуществом, являясь в определенном смысле черными ящиками. Понять по матрице нейронной сети особенности ее работы — задача нетривиальная. По этой же причине функциональные требования, записанные на естественном языке, проще реализовывать именно в виде логических схем.

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

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

Далее рассмотрим пример применения данной техники. Пример придуман и написан мной для одной лекции на данную тему.

Генерация и минимизация структурных блоков над бинарным алфавитом

1. Основные определения

Пусть $(x_1,...,x_n)$ булевый вектор входных данных структурного блока $\mathfrak{B}$ , $(y_1,...,y_m)$ — выходных.

Определение 1. Будем обозначать блок $\mathfrak{B}:(x_1,...,x_n)\rightarrow (y_1,...,y_m)$ как $\mathfrak{B}(n,m)$ .

Данный блок можно получить, как декартово произведение блоков $\mathfrak{B_i}:(x_1,...,x_n)\rightarrow y_i$ :

$\mathfrak{B}(n,m) = \mathfrak{B_1}(n,1) \times ... \times \mathfrak{B_m}(n,1)$

Следовательно, без ограничения общности, далее можно рассматривать блоки с одним булевым выходом.

Определение 2. Формализированным требованием к блоку $\mathfrak{B}(n,1)$ будем называть подмножество $\mathfrak{R}_{\mathfrak{B}} = <(x_1,...,x_n) \in bool^n | \mathfrak{B}(x_1,...,x_n) = 1>" src="https://tex.s2cms.ru/svg/%5Cmathfrak%7BR%7D_%7B%5Cmathfrak%7BB%7D%7D%20%3D%20%3C(x_1%2C...%2Cx_n)%20%5Cin%20bool%5En%20%7C%20%5Cmathfrak%7BB%7D(x_1%2C...%2Cx_n)%20%3D%201%3E"> <h4>2. Автоматическая генерация булевой функции, представляющей блок с одним выходом</h4> Лемма 1. Блок <img align=$ представим следующей булевой функцией:

$\lor_{(t_1,...,t_n)\in \mathfrak{R}_{\mathfrak{B}}}(\land_{1\leq i \leq n}x_i^{t_i})$

Доказательство. Согласно представлению булевой функции в совершенной дизъюнктивной нормальной форме.

Пример. Пусть имеется следующее требование к работе блока:

На вход подается значения двух датчиков $A_1, A_2$ и датчика проверки $C$ , в разном ли они состоянии. Схема должна сигнализировать о корректной работе датчика проверки.

Данное требование имеет следующий формализированный вид:

Согласно лемме 1 работа блока описывается функцией:

$(\neg A_1 \land \neg A_2 \land \neg C)\lor (\neg A_1 \land A_2 \land C)\lor (A_1 \land \neg A_2 \land C)\lor ( A_1 \land A_2 \land \neg C)$

3. Оптимизация булевого блока с одним выходом

Пусть блок с одним выходом задается следующей таблицей истинности:

Что соответсвует булевой формуле:

$(\neg A_1 \land \neg A_2 \land \neg A_3 \land A_4 )\lor (\neg A_1 \land \neg A_2 \land A_3 \land \neg A_4 )\lor (\neg A_1 \land A_2 \land \neg A_3 \land A_4 )\lor$
$\lor ( A_1 \land \neg A_2 \land \neg A_3 \land A_4 )\lor ( A_1 \land \neg A_2 \land A_3 \land \neg A_4 )\lor ( A_1 \land \neg A_2 \land A_3 \land A_4 )\lor ( A_1 \land A_2 \land A_3 \land \neg A_4 )$

Оставим значащие для ДДНФ строки:

Переставим строки в соответствии с кодом Грея:

Построим граф, соединив пары строк $(s_1, s_2)$ , для которых расстояние Хэмминга $\rho_H(s_1,s_2) = 1$ :

Выберем множество пар, что покрывают все вершины:

Выбранному множеству пар

(2,3)
(4,5)
(5,7)
(1,6)

соответствует следующая таблица:

Согласно полученной таблице, минимизированная формула примет вид:

$(\neg A_2 \land A_3 \land \neg A_4 )\lor ( A_1 \land A_3 \land \neg A_4 )\lor (\neg A_1 \land \neg A_3 \land A_4 )\lor ( A_1 \land \neg A_2 \land A_4 )$

Заметим, что естественное упрощение с использованием сокращений булевой алгебры может привести к неоптимальному результату. Например, применив правило сокращения булевой алгебры $a \lor (\neg a \land b) = a \lor b$ к таблице:

получим:

Что соответствует булевой формуле:

$(\neg A_2 \land \neg A_3 \land A_4 )\lor (\neg A_1 \land \neg A_3 \land A_4 )\lor (\neg A_2 \land A_3 \land \neg A_4 )\lor (A_1 \land \neg A_2 \land A_3 )\lor (A_1 \land A_3 \land \neg A_4 )$

Которая содержит 5 блоков $AND$ и не является оптимальной по количеству связок.

Данному упрощению соотвествует следующий граф, содержащий 5 отмеченных ребер, накрывающих все вершины:

Для полного же накрытия достаточно 4-х ребер. В общем случае, накрывающую систему ребер можно выбрать различными способами, поэтому упрощение по количеству булевых связок не является однозначным.

4. Абстрактная схема алгоритмов упрощения

Определение 3. Будем считать, что блок A проще блока B, если:

$\exists C \in \mathfrak{B}, B = A \land C$

На блоках естественным образом вводится отношение порядка $\preceq_r$ . Будем считать, что $B \preceq_r A$ , если блок А проще блока В.

Определение 4. Пусть формула А является дизъюнктивным объединением блоков $\lor_{1\leq i \leq n}A_i$ , а формула B является дизъюнктивным объединением блоков $\lor_{1\leq i \leq m}B_i$ . Будем говорить, что $B \preceq_r A$ , если:

$\forall i (1\leq i \leq n) \exists j\ B_j \preceq_r A_i$

Отношение порядка $\preceq_r$ на множестве формул не является линейным. Например, формулы $a \land b$ и $b \land c$ — несравнимы.

Определение 5. Для формулы $F(x_1,...,x_n)$ определим $\mathfrak{R}(F)$ как множество эквивалентных F формул над множеством переменных $<x_1, ..., x_n>" src="https://tex.s2cms.ru/svg/%3Cx_1%2C%20...%2C%20x_n%3E">. Определим <img align=$ как множество формул:

$\mathfrak{R}_{\sup}(F) = <X | X \in \mathfrak{R}(F), \nexists Y \in \mathfrak{R}(F), X \preceq_r Y >" src="https://tex.s2cms.ru/svg/%5Cmathfrak%7BR%7D_%7B%5Csup%7D(F)%20%3D%20%3CX%20%7C%20X%20%5Cin%20%5Cmathfrak%7BR%7D(F)%2C%20%5Cnexists%20Y%20%5Cin%20%5Cmathfrak%7BR%7D(F)%2C%20X%20%20%5Cpreceq_r%20Y%20%3E"> Будем называть <img align=$ множеством упрощений формулы F.

Определение 6. Для формулы $F(x_1,...,x_n)$ определим $\mathfrak{C}_F$ как множество конъюнктивных блоков над множеством переменных $(x_1,...,x_n)$ , удовлетворяющих следующему условию:

$B \in \mathfrak{C}_F \Leftrightarrow F \preceq_{semantic} B$

Схему различных алгоритмов упрощения булевых формул с одним выходом можно представить в виде следующей теоремы:

$\forall F'\in \mathfrak{R}_{\sup}(F), \exists n\ F' = \cup_{1 \leq i \leq n} B_i(B_i\in \mathfrak{C}_F )$

Выводы

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