Метод диаграмм Карно-Вейча (графический метод минимизации переключательных функций)

ЛАБОРАТОРНА РОБОТА 6

Тема: Методи мінімізації перемикальних функцiй. Частина 2. Метод Карно-Вейча (графiчний метод мiнiмiзацiї перемикальних функцій); побудова поліному Жегалкина для заданої перемикальної функції за допомогою методу Карно-Вейча; методи мiнiмiзацiї кон`юнктивних нормальних форм перемикальних функцiй; мiнiмiзацiя частково визначених перемикальних функцiй iсистем перемикальних функцiй, методи факторизації перемикальних функцій.

Мета роботи: опановування особливостей технологiй мінімізації перемикальних функцій за допомогою методу дiаграм Карно-Вейча, побудови поліному Жегалкина заданої перемикальної функції за допомогою методу карт Карно-Вейча, методiв мiнiмiзацiї кон`юнктивних нормальних форм перемикальних функцій, методiв мiнiмiзацiї частково визначених перемикальних функцiй iсистем перемикальних функцій, факторного алгоритму знахождення форми, близької до абсолютно мінімальної.

Базові поняття, що пiдлягають опановуванню:

- особливостi методу дiаграм Карно-Вейча як графiчного методу мiнiмiзацiї перемикальних функцій;

- технологiї роботи з методом дiаграм Карно-Вейча;

- технологія побудови поліному Жегалкина для заданої перемикальної функції за допомогою методу карт Карно-Вейча;

- методи мiнiмiзацiї кон`юнктивних нормальних форм перемикальних функцiй.

- методи мiнiмiзацiї частково визначених перемикальних функцiй;

- методи мiнiмiзацiї систем перемикальних функцiй;

- факторизація перемикальних функцій.

ОСНОВНЫЕ ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ

 

Метод диаграмм Карно-Вейча (графический метод минимизации переключательных функций)

 

Метод диаграмм Карно-Вейча позволяет быстро получать минимальные ДНФ переключательных функций от небольшого числа переменных: в основном, диаграммы Карно-Вейча применяются для функций с числом переменных не более четырех; метод особенно удобен для функций от четырех переменных; указанный метод также можно использовать для функций от трех переменных, но для них обычно используются другие методы.

Метод Карно-Вейча широко используется на практике благодаря простоте и удобству. После небольшой тренировки, формируется навык определения минимальной ДНФ по диаграмме Карно-Вейча с первого взгляда.

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

- диаграмма имеет форму таблицы, каждая клетка которой соответствует некоторому набору переменных таблицы истинности переключательной функции, заданному в коде Грея;

- в клетке диаграммы Карно-Вейча проставляется единица, если переключательная функция принимает на соответствующем наборе значение 1;

- нулевые значения переключательной функции в диаграмме Карно-Вейча не проставляются.

Для диаграмм Карно-Вейча характерно следующее:

- каждой клетке диаграммы соответствует свой набор;

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

Для случая переключательных функций двух, трех и четырех переменных, диаграммы Карно-Вейча имеют обобщенный вид, представленный далее по тексту, в таблицах 1-3. В данных таблицах также представлено соответствие клеток диаграмм Вейча наборам переменных таблиц истинности переключательных функций, сформированных в коде Грея.

 

Таблица 1 – Общий вид диаграммы Карно-Вейча для переключательной функции двух переменных

Таблица 2 – Общий вид диаграммы Карно-Вейча для переключательной функции трех переменных

Таблица 3 – Общий вид диаграммы Карно-Вейча для переключательной функции четырех переменных

 

Представленная в таблице 3 диаграмма Карно-Вейча для переключательной функции четырех переменных была получена путем добавления к диаграмме Карно-Вейча для функции трех переменных (таблица 2) еще одной такой же таблицы для функции трех переменных. Аналогично можно получить диаграмму для функции пяти и более переменных.