Метод диаграмм Карно-Вейча (графический метод минимизации переключательных функций)
ЛАБОРАТОРНА РОБОТА 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) еще одной такой же таблицы для функции трех переменных. Аналогично можно получить диаграмму для функции пяти и более переменных.