Минимизация логических функций методом карт Вейча.
Минимизация логических функций методом карт Вейча
Метод Квайна имеет четко сформулированные правила проведения отдельных операций, благодаря чему он может быть использован для минимизации функций с использованием ЭВМ в тех случаях, когда минимизируемая функция достаточно сложна (содержит большое число аргументов и каноническая форма имеет большое число членов). Однако для минимизации функции ручным способом (без использования ЭВМ) этот метод оказывается весьма трудоемким. Трудоемкость метода Квайна связана с необходимостью попарного сравнения всех членов выражения для выявления склеиваемых членов.
Метод минимизации функции с помощью карт Вейча обеспечивает простоту получения результата. Он используется пои минимизации относительно несложных функций (с числом аргументов до 5) ручным способом. В отличие от метода Квайна этот метод требует элементов изобретательности и не может быть использован для решения задачи минимизации с помощью ЭВМ. Карга Вейча прдставляет собой определенную форму таблицы истинности. Табл. 3.10 являются картами Вейча для функций соответственно двух (а), трех (б), четырех (в) аргументов.
Каждая клетка карты соответствует определенному набору значений аргументов. Этот набор аргументов определяется присвоением значения лог. 1 буквам, на пересечении строк и столбцов которых расположена клетка. Так, в карте функций четырех аргументов (табл. 3.10,в) клегки первой строки соответствуют следующим комбинациям аргументов:
· первая клетка
· вторая клетка
· третья клетка
· четвертая клетка
Число клеток карты равно числу всех возможных наборов значений аргументов 2 n (n – число аргументов функций). В каждую из клеток карты записывается значение функции на соответствующем этой клетке наборе значений аргументов.
|
|
Сформулируем правила получения МДНФ функций с помощью карт Вейча.
Все клетки, содержащие 1, объединяются в замкнутые области. При этом каждая область должна представлять собой прямоугольник с числом клеток 2 k, где k = 0, 1, 2,... Таким образом, допустимое число клеток в области – 1, 2, 4, 8,... Области могут пересекаться и одни и те же клетки могут входить в разные области.
Затем проводится запись выражения МДНФ функции. Каждая из областей в МДНФ представляется членом, число букв в котором на k меньше общего числа аргументов функции n (т. е. равно n – k). Каждый член МДНФ составляется лишь из тех аргументов, которые для клеток соответствующей области имеют одинаковое значение (без инверсии либо с инверсией).
Таким образом, при охвате клеток замкнутыми областями следует стремиться, чтобы число областей было минимальным (при этом минимальным будет число членов в МДНФ функции), а каждая область содержала возможно большее число клеток (при этом минимальным будет число букв в членах МДНФ функции).
|
Для минимизации функций с числом аргументов, большим пяти, карты Вейча оказываются неудобными. Минимизация таких функций может быть выполнена методом Квайна.
2. Проектирование КУ на основе дешифраторов.
3. Задача
