» Строительство »

Мінімізація функцій алгебри логіки методом карт Карно


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

При виконанні мінімізації здійснюється накриття за допомогою правильних конфігурацій полів карти, що містять одиниці або нулі. Правильними конфігураціями рангу i на карті Карно для ФАЛ від n -змінного є все прямокутники (вертикальні, горизонтальні і квадратні), які мають площу 2n-i (i = 1, 2, ..., n). Отже, правильними конфігураціями на карті Карно для ФАЛ від двох змінних є все прямокутники, які мають площу 22-i (рис. 10.1), від трьох змінних - прямокутники, які мають площу 23-i (рис. 10.2), від чотирьох змінних - прямокутники, які мають площу 24-i (рис. 10.3). Рангом накриття називається сума рангів всіх правильних конфігурацій, що утворюють накриття.

Накриття функції є мінімальним, якщо його ранг не перевищує рангу будь-якого іншого накриття цієї функції за допомогою правильних конфігурацій. Для виконання цієї умови необхідно накрити все одиниці або всі нулі карти за допомогою мінімального числа правильних конфігурацій максимальної площі (рис. 10.1-10.3), при виборі накриття можливе об'єднання крайніх полів, розташованих на протилежних сторонах карти. Конфігурації можуть перекриватися, накладаючись одна на іншу.

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

Малюнок 10.1 Використання карт Карно при мінімізації ФАЛ від двох змінних

Малюнок 10.2 Використання карт Карно при мінімізації ФАЛ від трьох змінних

При об'єднанні полів, в яких записані одиниці, ФАЛ виписується в формі ДНФ, т. Е. У вигляді диз'юнкції творів змінних, які не змінюються в межах кожної конфігурації накриття. При об'єднанні полів, що містять нулі, ФАЛ записується у вигляді твору диз'юнкцій інверсних значень змінних, не змінних при переході з одного поля конфігурації на інше.

Як видно з рис. 10.1-10.3, при об'єднанні двох полів виключається одна змінна, при об'єднанні чотирьох полів - дві змінні, при об'єднанні восьми полів - три змінні.

У поля картки, відповідні наборам аргументів, при яких значення функції нас не цікавить, замість нулів або одиниць проставляється символ «×» (рис. 10.3). Поля, відмічені символом «×», включаються в конфігурації накриття, якщо це сприяє отриманню більш простого вираження для запису функції.

Малюнок 10.3 Використання карт Карно при мінімізації ФАЛ від чотирьох змінних

Карти Карно найбільш доцільно використовувати для мінімізації ФАЛ від двох до шести змінних. При мінімізації ФАЛ від п'яти змінних вона може бути представлена ​​у вигляді двошарового паралелепіпеда, утвореного двома картами по 16 полів (рис. 10.4). Для зручності запису значень, прийнятих функцією на кожному наборі аргументів, замість паралелепіпеда використовують дві наявні поруч карти Карно (рис. 10.4). Однією з карт ставиться відповідність пряме, а інший - інверсне значення п'ятої змінної. Відмінною особливістю мінімізації ФАЛ від п'яти змінних є можливість об'єднання в одну конфігурацію сусідніх полів, розташованих на різних картах. Тому в даному випадку утворені конфігурації можуть розглядатися як деякі виділяються області паралелепіпеда, що характеризуються не тільки площею, але і певним обсягом. Чим більше обсяг утвореною конфігурації, тим менша кількість змінних виписується з неї при мінімізації функції.

При мінімізації ФАЛ шести змінних вона може бути представлена ​​у вигляді куба, утвореного чотирма картами по 16 полів.

Для зручності запису значень, прийнятих функцією на кожному наборі аргументів, замість куба розглядаються чотири наявні поруч карти Карно по 16 полів (рис. 10.5).

Малюнок 10.4 Використання карт Карно при мінімізації ФАЛ від п'яти змінних

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

Малюнок 10.5 Використання карт Карно при мінімізації ФАЛ від п'яти змінних



Date: 2015-12-13; view: 326; Порушення авторських прав

Сподобалася сторінка? Лайкні для друзів:
Посетители рекомендуют:
Полезно знать:
Современные строительные технологии Геология, города и строительство © Все права сохранены.