Компьютерная схемотехника
Методическое пособие - Компьютеры, программирование
Другие методички по предмету Компьютеры, программирование
используя тождества и теоремы булевой алгебры.
Пример 1. Исходное булево выражение:
.(3.4)
Применяя теорему склеивания, получим булево выражение
,(3.5)
которое равносильно (эквивалентно) исходному, но значительно проще его.
Пример 2. Исходное булево выражение:
.(3.6)
Используя тождество А=А+А и теорему склеивания получим более простое выражение
.(3.7)
Такие элементарные приемы минимизации удается использовать, если исходное булево выражение содержит малое количество членов с небольшим числом переменных.
Более наглядным и удобным является минимизация с применением диаграмм Вейча (карт Карно).
3.12.2 Минимизация ПФ с использованием диаграмм Вейча (карт Карно)
Диаграммы Вейча (карты Карно) [3, 11, 18] построены так, что их соседние клетки содержат члены исходной ПФ, отличающиеся значением одной переменной: один член содержит эту переменную в прямой форме, а другой в инверсной. Благодаря этому возникает наглядное представление о различных вариантах склеивания смежных членов.
3.12.2.1 Минимизация ПФ с помощью диаграмм Вейча
Исходным продуктом для применения диаграмм Вейча является представление ПФ таблицей истинности, в которой возможные наборы переменных упорядочены по возрастанию или по убыванию их десятичных эквивалентов (таблица 3.1). Вид диаграмм Вейча зависит от числа переменных минимизируемой ПФ - n и от того, как упорядочены наборы переменных в таблице. Если наборы упорядочены по возрастанию их десятичных эквивалентов, то диаграммы Вейча для n=2,3,4 имеют вид, приведенный на рисунке 3.1.
Рисунок 3.1
Число клеток диаграммы равно количеству наборов переменных
Nкл=Nнаб=2n.(3.8)
Если n=2, то Nкл=22=4; n=3 Nкл=8, n=4 Nкл=16.
Каждая клетка соответствует определенному набору переменных и имеет номер, одинаковый с номером набора.
Строки и столбцы диаграммы, помеченные чертой, определяют наборы, в которых переменные принимают единичные значения (входят в прямой форме). Строки и столбцы, не помеченные чертой, соответствуют наборам, в которых те же переменные принимают нулевые значения (входят в инверсной форме). Например, для n=3 (рисунок 3.1) двум левым столбцам соответствует единичное значение переменной В (в входит в прямой форме), а двум правым нулевое значение (в входит в инверсной форме).
В клетки записываются значения ПФ на соответствующем наборе (нулевое или единичное). Если на каком-то наборе функция не определена, то в клетке диаграммы ставится прочерк.
ПФ считается неопределенной, если:
1) данный набор переменных в реальном логическом устройстве невозможен;
2) значение функции на данном наборе безразлично.
После заполнения диаграммы можно приступить непосредственно к минимизации, которую производят по единицам или нулям.
В первом случае результатом минимизации будет булево выражение в ДНФ, а во втором в КНФ.
3.12.2.1.1 Общие правила минимизации
Минимизацию можно проводить по единицам (нулям). При этом:
1) Смежные единицы (нули) диаграммы условно охватывают (накрывают) прямоугольными контурами. Каждый контур может содержать 2,4,8,16, ... единиц (нулей).
2) Одним контуром (накрытием) необходимо объединить максимальное количество смежных клеток, содержащих единицы (нули).
3) Необходимо, чтобы каждая единица (нуль) накрывалась хотя бы один раз.
4) Одна и та же единица (нуль) может охватываться несколько раз разными контурами.
5) Верхняя и нижняя строки диаграммы считаются смежными - их можно представить таковыми, если мысленно свернуть диаграмму в горизонтальный цилиндр.
6) Левый и правый столбцы также считаются смежными - диаграмму можно мысленно свернуть в вертикальный цилиндр.
7) Угловые клетки также считаются смежными - диаграмму можно мысленно свернуть в тор.
8) Перед выполнением минимизации в клетки, содержащие прочерки (на данных наборах ПФ неопределена), можно записать дополнительные единицы (нули), что способствует получению более простого конечного булевого выражения. При этом следует помнить, что хотя бы один раз необходимо накрыть лишь основные единицы (нули). Дополнительные единицы (нули) могут увеличивать суммарное число единиц (нулей), входящих в накрытие, а, следовательно, уменьшать число переменных в результирующих конъюнкциях (дизъюнкциях).
9) Результатом минимизации является булево выражение в ДНФ (КНФ). Количество конъюнкций в ДНФ (дизъюнкций в КНФ) соответствует числу контуров (накрытий).
10) В каждую конъюнкцию (дизъюнкцию) войдут только те переменные, значение которых в пределах контура не меняется (переменная принимает в накрытии только единичное или нулевое значение (входит только в прямой или инверсной форме)).
При минимизации по единицам в результирующие конъюнкции переменные входят в прямой форме, если соответствующие им строки и столбцы диаграммы помечены чертой. Переменные, связанные со строками и столбцами, не помеченными чертой, входят в конъюнкции в инверсной форме.
При минимизации по нулям в результирующие дизъюнкции переменные входят в прямой форме, если соответствующие им строки и столбцы не помечены чертой, в противном случае дизъюнкции содержат переменные в инверсном виде.
Целью минимизации является получение минимальной ДНФ или КНФ,