Лекции.Орг


Поиск:




В качестве примера, рассмотрим переключательную функцию, заданную диаграммой Карно-Вейча в форме таблицы 4.




Таблица 4

Конституенты, соответствующие горизонтально расположенной паре единиц в левой части таблицы 4, склеиваются по переменной x3 и порождают элементарное произведение, состоящее из двух букв: х1х23 v x1x2x3 = x1x2

То же справедливо и для вертикально расположенной пары единиц в правой части таблицы 4, склеивающихся по переменной x2 и порождающих элементарное произведение из двух букв: 1х23 v /x1/x2/x 3 = /x1/x3

Важной особенностью диаграмм Карно-Вейча является то, что столбцы и строки, расположенные по краям диаграммы, считаются соседними. Для приведенного выше примера, данное утверждение означает, что имеет место склеивание по переменной x1, в результате которого, следуя указанному правилу, получаем элементарное произведение x2/x3.

Полученные выше элементарные произведения легко было определить сразу по диаграмме Карно-Вейча, поскольку они являются произведениями переменных, принимающих одни и те же значения в обеих клетках.

Из рассмотренных ранее методов известно, что возможно дальнейшее склеивание получаемых элементарных произведений.

На диаграммах Карно-Вейча они тоже располагаются рядом.

Общее правило склеивания на диаграммах Карно-Вейча можно сформулировать следующим образом:

- склеиванию подлежат прямоугольные конфигурации, заполненные единицами и содержащие число клеток, являющееся степенью числа 2;

- новое элементарное произведение определяется как произведение переменных, не меняющих своего значения на всех склеиваемых наборах.

Для переключательной функции от n переменных и при количестве склеиваемых наборов М, число m оставшихся в элементарном произведении переменных определяется из формулы m = n - log2M.

Рассмотрим принцип построения карты Карно-Вейча детальнее для наиболее применимого случая переключательной функции четырех переменных.

Как правило, вдоль границ диаграммы Карно-Вейча по вертикали разме-щают переменные x 1 и x 2, а по горизонтали ˗ переменные x 3 и x 4. Пары пере-меных выписываются в порядке (00), (01), (11), (10) (с применением кода Грея). Далее в таблицу заносят значения функции для данных значений переменных.

Для функции обобщенного вида f = (f0000 f0001 f0010 f0011 f0100 f0101 f0110 f0111 f1000 f1001 f1010 f1011 f1100 f1101 f1110 f1111), получим следующий промежуточный результат:

 

  x 3        
x 4        
x 1 x 2    
      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 x 3 /x4; (− 0 1 0) = /x2 x 3 /x4;

(− 1 0 1) = x 2/ x 3 x 4; (1 1 0 −) = x 1 x 2 / x 3; (1 0 1 −) = x 1 /x2 x 3;

(1 − − 1) = x 1 x 4

В результате, получаем сокращённую ДНФ следующего вида:

/x1 /x2 /x4 ∨ /x1 x 3 /x4 ∨ /x2 x 3 /x4 x 2/ x 3 x 4 x 1 x 2 / x 3 x 1 /x2 x 3 x 1 x 4.





Поделиться с друзьями:


Дата добавления: 2016-12-06; Мы поможем в написании ваших работ!; просмотров: 773 | Нарушение авторских прав


Поиск на сайте:

Лучшие изречения:

Не будет большим злом, если студент впадет в заблуждение; если же ошибаются великие умы, мир дорого оплачивает их ошибки. © Никола Тесла
==> читать все изречения...

1004 - | 822 -


© 2015-2024 lektsii.org - Контакты - Последнее добавление

Ген: 0.009 с.