? черговий суміжний вектор? серед векторів, розташованих в списку вище?. У разі відсутності такого вектора, перейти до кроку 5. Інакше узагальнено склеїти вектора? і? і отриманий вектор? приписати до списку останнім;
Якщо вектор? поглинається хоча б одним вектором зі списку, то видалити вектор? (в окремому випадку вектор? може збігатися з одним із векторів списку, в такому випадку слід видалити приписаний вектор?, в іншому випадку відбудеться зациклення алгоритму), повернутися до кроку 2. Якщо вектор? не поглинається, видалити всі вектори, що поглинаються їм;
Якщо вектор? не видалений, то перейти до кроку 2;
Якщо вектор? був не останнім у списку, вибрати в якості нового? наступний за списком вектор і повернутися до кроку 2;
Невидалені вектори задають скорочену нормальну форму функції. Припинення роботи алгоритму.
етап. Табличний.
Перехід від скороченої форми до мінімальної здійснюється за допомогою импликантной матриці, що представляє собою таблицю, стовпці якої відповідають всім конституенте одиниці СДНФ заданої функції, а рядки - всім простим импликанте. У таблиці по рядку кожної імпліканти відзначаються ті минтермов, які нею поглинаються. Імпліканти, що не підлягають виключенню, для яких є хоча б один стовпець, що перекривається тільки цієї импликантой, називаються екстремалів. Безліч всіх екстремалів утворюють ядро ??импликантной матриці.
Висновок. У методі Квайна є істотна незручність - необхідність повного попарного порівняння на етапі знаходження первинних импликант. З ростом числа аргументів функції і визначають її членів СДНФ росте число цих порівнянь. Дане зростання характеризується факторіальною функцією. У цьому зв'язку застосування методу Квайна стає скрутним.
Мінімізація булевих функцій методом Квайна-Мак-Класки
Метод Квайна - Мак-Класки є модернізацією першого етапу методу Квайна. Відмінністю від методу Квайна є запис джерельного?? импликант даної функції у вигляді їх двійкових кодів (кожному члену ставиться у відповідність за відомим правилом його власна вершина). Всі безліч так записаних импликант розбивається по числу одиниць в їх кодах на групи. При цьому в i-у групу увійдуть коди, що мають у своєму записі i одиниць. Попарне порівняння импликант досить робити тільки між сусідніми групами, тому тільки ці групи відрізняються одним знаком в кодах вхідних у них членів. Порівнюючи коди членів сусідніх груп, утворюють члени нижчого рангу. На місці виключеного знака пишуть в них тире. Потім всю сукупність членів нижчого рангу знову розбивають на групи по місцю розташування знака тире.
З метою реалізації пошуку мінімального покриття импликантной матриці використовуються наближені алгоритми. Встановлено, що мінімаксний алгоритм найбільш ефективний для вирішення поставленого завдання. Жодний алгоритм характеризується великою швидкодією, однак результати, отримані протягом його роботи, оптимальні в 100% випадках за умови завданні структури завдання матроід. Точний алгоритм має експоненціальним часом роботи, що зі збільшенням кількість вхідних сигналів значно позначається на швидкодії розроблюваного програмного продукту. Відповідно до мінімаксним алгоритмом включення в мінімізовану форму черговий імпліканти здійснюється за наступним правилом: вибирається стовпець таблиці покриттів з найменшою кількістю міток і серед рядків, які мають в цьому стовпці мітки, вибирається рядок з найбільшим числом міток, яка і визначає необхідну импликанте, причому всі минтермов , що покриваються цієї импликантой, а значить, і відповідні їм стовпці викреслюються. Процедура повторюється до тих пір, поки не будуть викреслені всі стовпці.
Висновок. Метод Квайна-Мак-Класки характеризується наочністю, він відмінний від методу діаграм Вейча простотою алгоритмізації, набагато компактніше і простіше методу невизначених коефіцієнтів і може бути застосовний для проектування пристроїв, що містять необмежену кількість вхідних сигналів. Таким чином, даний метод був обраний для мінімізації булевих функцій в розробляється програмному забезпеченні.
Пошук факторного покриття переключательних функцій
У загальному випадку облік реальних обмежень на навантажувальні здатності джерел вхідних і внутрішніх змінних і на коефіцієнти розгалуження кон'юнктор передує синтезу логічної схеми в булевом базисі і називається факторизації.
В основі алгоритму факторизації (? - алгоритм) лежить? - твір, яке позначається a? b, складається з результатів покоординатно творів (рис. 1.5).
Рис. 1. 5. покоординатно твору? -алгоритми
Таким чином, -твір двох координат дорівнює нулю, якщо обидві координати дорівнюють нулю, дорівнює одиниці, якщо обидві координати дорівнюють одиниці і дорівнює m у всіх інших випадках. Запропонований алгоритм закінчує свою роботу за умови, що ...
