В предыдущем статья Я рассказал, как симметричные отображения позволяют достаточно просто и быстро минимизировать булевы функции, но не осветил два момента: получение разных вариантов минимального решения и автоматизацию самого алгоритма минимизации.
Подробнее об этом я расскажу здесь.
Напомню, что задача минимизации состоит в том, чтобы найти наибольшее покрытие для каждой единицы.
Если такое покрытие найдено и оно единственное, то оно записывается в так называемое ядро функции, а все покрытые им единицы исключаются из дальнейшего рассмотрения.
Однако если максимальное покрытие не является единственным, возникают варианты решения, которые можно использовать, например, для учета каких-либо дополнительных требований.
Кроме того, как я покажу ниже, отбрасывание вариантов приводит к тому, что полученное решение может быть не минимальным.
Итак, в примере из предыдущей статьи можно найти ядро функции для следующего симметричного отображения: 
Оно равно:
!X1*X5 В X2*X3*X4 В X1*!X2*!X5
Можно обнаружить, что индекс строки 0 и индекс столбца 4 можно покрыть двумя способами:
!X1*X3*!X4 (1)
Х3*!Х4*!Х5 (2)
Аналогично, индекс 1 в строке 10 и индекс столбца 4 могут быть покрыты четырьмя способами:
!X1*X3*!X4 (1)
Х3*!Х4*!Х5 (2)
!Х1*Х2*Х3 (3)
Х2*Х3*!Х5 (4)
Обратите внимание, что при охвате разных единиц встречаются одинаковые импликанты, обозначенные здесь одинаковыми номерами.
Далее, индекс строки 1 30 и индекс столбца 4 можно покрыть тремя способами: Х3*!Х4*!Х5 (2) Х1*Х3*!Х5 (5) Х2*Х3*!Х5 (4) А индекс строки 20 и индекс столбца 1 можно покрыть двумя способами: Х1*!Х2*!Х3*!Х4 (6) !X2*!X3*!X4*X5 (7) Поскольку в окончательном решении должны быть охвачены все единицы, мы запишем следующее выражение как произведение вариантов для каждой единицы: (1 В 2)(1 В 2 В 3 В 4)(2 В 5 В 4)(6 В 7) Раскроем первые две скобки: (1*1 В 1*2 В 1*3 В 1*4 В 2*1 В 2*2 В 2*3 В 2*4)(2 В 5 В 4)(6 В 7) Поскольку импликанта при умножении сама на себя дает ту же импликанту, первую скобку можно переписать следующим образом: (1 В 1*2 В 1*3 В 1*4 В 2*1 В 2 В 2*3 В 2*4)(2 В 5 В 4)(6 В 7) Далее, поскольку вариант с одной импликантой дает лучшее решение, чем с двумя, можно переписать решение в виде: (1 В 2)(2 В 5 В 4)(6 В 7) Раскрыв скобки дальше и используя аналогичные сокращения, получим окончательное решение, которое уже нельзя сокращать: 2(6 В 7) Первый фактор 2 является единственным импликантом в группе и должен быть добавлен к ядру функции (так называемое ядро расширенной функции): X3*!X4*!X5 И кронштейн дает два варианта: X1*!X2*!X3*!X4 И !X2*!X3*!X4*X5 Вы можете выбрать любой из них.
Естественно, возникает вопрос об автоматизации этого алгоритма.
Для этого я написал программу apssymmap, которую можно найти на моем сайте: http://andyplekhanov.narod.ru/soft/soft.htm Представляет интерес сравнить результаты применения этого метода с другими известными методами.
Давайте сравним результаты работы программы apssymmap с известной программой эспрессо на примере, представленном ниже: 
Результат программы эспрессо:
эспрессо -Dexact -oeqntott test.txt 
Результат работы программы apssymmap: 
Видно, что программа apssymmap выдает 8 различных вариантов вместо одного эспрессо.
Однако более интересный факт заключается в том, что результат приготовления эспрессо не является оптимальным.
Если мы отбросим все общие части в этих решениях, мы увидим, что у эспрессо осталось два компонента: !X7*!X5*!X4*X2*X1 И X7*!X6*X5*X4*X3*X1 содержащий 5 и 6 переменных соответственно, а решение apssymmap будет содержать импликанты !X5*X3*X2*X1 И X7*!X6*X3*X2*X1 содержащие 4 и 5 переменных, то есть на две меньше.
В качестве вывода можно сделать вывод, что симметричные карты являются не только более удобным методом минимизации булевых функций вручную, но и превосходят другие методы при решении этой задачи на компьютере.
Теги: #минимизация булевых функций #автоматизация проектирования #Алгоритмы #CAD/CAM
-
Что Такое 1С? 1С Франчайзинг. Часть 2
19 Oct, 24 -
Дата И Время Или Временная Метка
19 Oct, 24 -
Украсьте Свое Рабочее Место По Своему Вкусу
19 Oct, 24
