Составители:
Метод минимизации логических функций с помощью карт Карно стано-
вится неудобным при количестве аргументов больше 5 … 6. В этом случае
удобнее пользоваться методом Квайна – Мак Класки. Алгоритм минимизации
основан на использовании двух операций: неполного склеивания
A
x
AA
x
x
AA
x
∨∨=∨
и поглощения
.AxAAAxA =∨=∨
Если функция представлена в СДНФ и, если в ней произвести все воз-
можные склеивания, а затем все поглощения, то получим более простое выра-
жение, которое называется сокращенной ДНФ.
Для дальнейших рассуждений важно ввести понятие импликант функции
(конъюнкция переменных с отрицанием или без него), изъятие которого из
структурной формулы приводит к появлению тупиковых вариантов ДНФ. Про-
цедура минимизации при этом имеет много общего с методом Карно и заклю-
чается в следующих действиях.
1. Структурная формула логического устройства, представленная в
СДНФ, записывается в виде столбика двоичных чисел, каждое из которых
(минтерм в методе Карно) здесь называется импликантом, т. е.
i
x заменяется
на 0, а
x
i
− на 1.
1. Двоичные числа разбиваются на группы по количеству единиц (нуле-
вая группа состоит из одного числа). Группы отделяются одна от другой и об-
разуют колонку.
2. Производится склеивание чисел колонки. Результат пишется в сле-
дующей колонке, а при склеивании необходимо учитывать целый ряд условий:
склеиваются только числа из соседних групп;
склеиваются только числа, отличающиеся в одном разряде; например при
склеивании (
a0b) с (a1b) получается число (a-b), которое записывается в но-
вую колонку, а около выражений предыдущей колонки, для которых выпол-
нено склеивание, ставится какая-либо метка (например, знак
∨);
каждое число может участвовать в склеивании произвольное количество раз,
но необходимо перебрать все возможные варианты склеиваний; повторяю-
щиеся склеивания не выписываются.
4.Количество единиц в последующих колонках должно постепенно
уменьшаться, но следует обратить внимание на то, что склеиваются выражения,
в которых черточки стоят в одних и тех же позициях. Например, из (11 – 0
− ) и
(10 – 0
−) получаем (1 − − 0 − ).
5. Образование новых колонок прекращается, если в последней колонке
нельзя выполнить ни одного склеивания.
6. Выражения, для которых оказалось невозможным выполнить склеива-
ние, заменяются буквенными операциями, обратными исходным, при этом чер-
точки опускаются. Например, выражение (10
− 0 −) заменяется на .
4
21
xxx
7. Буквенные выражения – это простые импликанты минимизируемой
функции, а их дизъюнкция – это сокращенная ДНФ.
8. Составляется таблица импликантов, из которой выбираются мини-
мальные тупиковые формы.
21
Страницы
- « первая
- ‹ предыдущая
- …
- 19
- 20
- 21
- 22
- 23
- …
- следующая ›
- последняя »
