В качестве примера, рассмотрим переключательную функцию, заданную диаграммой Карно-Вейча в форме таблицы 4.
Таблица 4
Конституенты, соответствующие горизонтально расположенной паре единиц в левой части таблицы 4, склеиваются по переменной x3 и порождают элементарное произведение, состоящее из двух букв: х1х2/х3 v x1x2x3 = x1x2
То же справедливо и для вертикально расположенной пары единиц в правой части таблицы 4, склеивающихся по переменной x2 и порождающих элементарное произведение из двух букв: /х1х2/х3 v /x1/x2/x 3 = /x1/x3
Важной особенностью диаграмм Карно-Вейча является то, что столбцы и строки, расположенные по краям диаграммы, считаются соседними. Для приведенного выше примера, данное утверждение означает, что имеет место склеивание по переменной x1, в результате которого, следуя указанному правилу, получаем элементарное произведение x2/x3.
Полученные выше элементарные произведения легко было определить сразу по диаграмме Карно-Вейча, поскольку они являются произведениями переменных, принимающих одни и те же значения в обеих клетках.
Из рассмотренных ранее методов известно, что возможно дальнейшее склеивание получаемых элементарных произведений.
На диаграммах Карно-Вейча они тоже располагаются рядом.
Общее правило склеивания на диаграммах Карно-Вейча можно сформулировать следующим образом:
- склеиванию подлежат прямоугольные конфигурации, заполненные единицами и содержащие число клеток, являющееся степенью числа 2;
- новое элементарное произведение определяется как произведение переменных, не меняющих своего значения на всех склеиваемых наборах.
Для переключательной функции от n переменных и при количестве склеиваемых наборов М, число m оставшихся в элементарном произведении переменных определяется из формулы m = n - log2M.
Рассмотрим принцип построения карты Карно-Вейча детальнее для наиболее применимого случая переключательной функции четырех переменных.
Как правило, вдоль границ диаграммы Карно-Вейча по вертикали разме-щают переменные x1 и x2, а по горизонтали ˗ переменные x3 и x4. Пары пере-меных выписываются в порядке (00), (01), (11), (10) (с применением кода Грея). Далее в таблицу заносят значения функции для данных значений переменных.
Для функции обобщенного вида f = (f0000 f0001 f0010 f0011 f0100 f0101 f0110 f0111 f1000 f1001 f1010 f1011 f1100 f1101 f1110 f1111), получим следующий промежуточный результат:
| x3 | ||||||
| x4 | ||||||
| x1 | x2 | |||||
| f0000 | f0001 | f0011 | f0010 | |||
| f0100 | f0101 | f0111 | f0110 | |||
| f1100 | f1101 | f1111 | f1110 | |||
| f1000 | f1001 | f1011 | f1010 |
На полученной карте Карно-Вейча, находим все максимально возможные блоки единиц вида 2k × 2l; где k, l ∈ N, учитывая следующее: карта является закольцованной; блоки могут пересекаться, но не должны включать друг друга.
Для каждого блока, выписываем вектор, в котором размещаем: знак «–», если переменная в пределах блока меняла значение; значение переменной (0 либо 1), если переменная в пределах блока не меняла значения.
Для тех позиций вектора i, в которых стоит знак σ ∈ {0, 1}, в элементарную кон`юнкцию добавляется xiσ.
Дизъюнкция всех полученных элементарных кон`юнкций и является сокращённой ДНФ.
Пдведем итоги рассмотренной информации о методе Карно-Вейча.
Минимизация переключательной функции методом Карно-Вейча заключается в нахождении минимального покрытия всех единиц диаграммы Карно-Вейча блоками из единиц (указанной конфигурации), расположенных в соседних клетках диаграммы.
Считается, что: левый край диаграммы Карно-Bейча примыкает к ее правому краю, а верхний край диаграммы примыкает к ее нижнему краю.
После получения минимального покрытия всех единиц диаграммы Карно-Вейча, минимальная ДНФ булевой функции записывается как дизъюнкция элементарных конъюнкций, соответствующих выделенным блокам единиц в диаграмме.
Рассмотрим пример применения изложенных выше соображений, найдя для функции f = (1010 0110 0111 1101) сокращённую ДНФ.
Для решения задачи, построим следующую карту Карно-Вейча:
На основании карты Карно-Вейча, получим следующие блоки:
(0 0 − 0) = /x1 /x2 /x4; (0 − 1 0) = /x1 x3 /x4; (− 0 1 0) = /x2 x3 /x4;
(− 1 0 1) = x2/x3 x4; (1 1 0 −) = x1 x2 /x3; (1 0 1 −) = x1 /x2 x3;
(1 − − 1) = x1x4
В результате, получаем сокращённую ДНФ следующего вида:
/x1 /x2 /x4 ∨ /x1 x3 /x4 ∨ /x2 x3 /x4 ∨ x2/x3 x4 ∨ x1 x2 /x3 ∨ x1 /x2 x3 ∨ x1x4.