Геометричний підхід до спрощення логічних схем

Про автора: Денис Морозов, к. ф.-м. н., працює на посаді доцента кафедри математики НаУКМА, також є консультантом компанії GlobalLogic. Працює над докторською дисертацією, сфера наукових інтересів — кінцеві автомати і групи автоморфізмів дерев.

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

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

Дослідження штучного інтелекту (ШІ) вимагає впевненого володіння різними техніками, і не обмежується лише використанням нейронних мереж. Однією з важливих технік є теорія комбінаційних логічних схем. У даної техніки є своя певна ніша.

Комбінаційно-логічні схеми vs нейронні мережі

Не так давно нейронні мережі пережили друге народження і зараз великий відсоток завдань, наприклад, задачі розпізнавання звуку, зображень, проблематики природної мови, перекладу вирішуються саме за допомогою апарату нейронних мереж. І виникає природне запитання: а навіщо ще щось інше? Адже нейронні мережі непогано вирішують завдання, які перед ними ставляться. Але тут треба розуміти, що таке нейронна мережа, які її переваги та обмеження.

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

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

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

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

Як ми вже згадували, чим простіше логічна схема, тим легше вона тестується і тим прозоріше робота з нею. Тому важливо розуміти суть механізмів спрощення подібних схем.

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

Далі розглянемо приклад застосування даної техніки. Приклад придуманий і написаний мною для однієї лекції на дану тему.

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

1. Основні визначення

Нехай булевий вектор вхідних даних структурного блоку $\mathfrak{B}$ , — вихідних.

Визначення 1. Будемо позначати блок $\mathfrak{B}:(x_1,...,x_n) ightarrow (y_1,...,y_m)$ як.

Даний блок можна отримати, як декартовий добуток блоків $\mathfrak{B_i}:(x_1,...,x_n) ightarrow y_i$ :

Отже, без обмеження спільності, далі можна розглядати блоки з одним булевими виходом.

Визначення 2. Формалізованим вимогою до блоку $\mathfrak{B}(n,1)$ будемо називати підмножинапредставимо наступною бульовою функцією:

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

Доказ.Згідно з поданням булевої функції в досконалій диз'юнктивній нормальній формі.

Приклад. Нехай є наступна вимога до роботи блоку:

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

Дана вимога має такий формалізований вигляд:

Згідно лемі 1 робота блоку описується функцією:

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

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

Нехай блок з одним виходом задається наступною таблицею істинності:

Що відповідає булевої формулою:

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

Залишимо значущі для ДДНФ рядки:

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

Побудуємо граф, з'єднавши пари рядків , для яких відстань Хеммінга $ho_H(s_1,s_2) = 1$ :

Виберемо безліч пар, що покривають всі вершини:

Обраним безлічі пар

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

відповідає наступна таблиця:

Згідно отриманої таблиці, мінімізована формула прийме вид:

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

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

отримаємо:

Що відповідає булевої формулою:

Яка містить 5 блоків $AND$ і не є оптимальною за кількістю зв'язок.

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

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

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

Визначення 3. Будемо вважати, що блок A простіше блоку B, якщо:

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

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

Визначення 4. Нехай формула А є дизъюнктивным об'єднанням блоків , а формула B є дизъюнктивным об'єднанням блоків $\lor_{1\leq i \leq m}B_i$ . Будемо говорити, що , якщо:

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

Відношення порядку на множині формул не є лінійним. Наприклад, формули $a \land b$ і — непорівнянні.

Визначення 5. Для формули $F(x_1,...,x_n)$ визначимо як безліч еквівалентних формул F над безліччю змінних $<x_1, ..., x_n>$ як безліч формул:

безліччю спрощень формули F.

Визначення 6. Для формули $F(x_1,...,x_n)$ визначимо як безліч кон'юнктівних блоків над множиною змінних $(x_1,...,x_n)$ , які задовольняють наступним умовам:

Схему різних алгоритмів спрощення булевих формул з одним виходом можна представити у вигляді наступної теореми:

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

Висновки

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

.b-typo img {display:inline-block!important;}position:relative;top:3px;

Опубліковано: 23/11/18 @ 09:08
Розділ Різне

SEO Блог