Принцип графической минимизации

В основе метода минимизации лежит правило склеивания АВ v АВ = А(В v В) = А (3.17) и понятие "соседняя клетка". Соседними клетками называют две клетки, номера которых в двоичной системе счисления отличаются лишь цифрой в одном разряде. Для всех карт Карно, приведенных на рис. 3.7, соседними являются клетки, расположенные в одном столбце или строке, включая две противоположные крайние клетки.

Поясним принцип минимизации на конкретном примере, полагая, что исходная функция Y зависит от 4 переменных и задана единичными наборами с номерами: 1, 2, 3, 5, 7, 10 и 12. Заполненная единицами карта Карно для М = 4 изображена на рис. 3.8. На карте выделены следующие области (группы) клеток:

  • • 1 – область из одной клетки с номером 1100 (12);
  • • 2 – область из двух соседних клеток с номерами 0010 (2) и 1010 (10), расположенных на противоположных концах столбца;
  • • 3 – квадрат из четырех клеток с номерами 0001 (1), ООН (3),0101 (5) и 0111 (7).

Для минимизации Y воспользуемся правилом составления структурных формул и формулой склеивания. Единственную

Структура карт Карно для различного числа М входных сигналов

Рис. 3.7. Структура карт Карно для различного числа М входных сигналов

Номера единичных наборов: 1, 2, 3, 5, 7, 10, 12

Пример минимизации полностью определенной логической функции

Рис. 3.8. Пример минимизации полностью определенной логической функции

клетку представим как минтерм , область 2 – как сумму двух минтермов

и область 3 – как сумму четырех минтермов

Представив Y как сумму всех минтермов, получим следующее минимизированное выражение:

Рассмотренный пример показывает, что группа из двух соседних клеток вместо суммы двух минтермов позволяет получить один конъюнктивный член, в котором на одну переменную меньше, чем в минтерме; группа из четырех соседних клеток позволяет получить один конъюнктивный член, в котором на две переменные меньше, чем в минтерме, и т.д.

Таким образом, процедура минимизации выполняется в два этапа.

  • 1. Разметка карты Карно заключается в выделении групп единичных клеток. Группу могут составлять 2, 4, 8, 16 клеток. Объединенные в группу клетки обводятся на карте Карно линией. Объединению подлежат только те заполненные единицами клетки, которые подчинены правилу склеивания. К ним относятся:
    • • две соседние клетки;
    • • клетки, составляющие полные столбцы или строки;
    • • клетки, составляющие квадраты;
    • • две группы клеток, расположенные симметрично относительно центральных вертикальных или горизонтальных осей карты и осей, разделяющих столбцы и строки карты с номерами 001 и 011, 111 и 101 (для М = 5 и 6).

Каждая группа должна охватывать по возможности бо́льшее число клеток и не должна входить в состав другой группы. Одна и та же клетка может входить в состав нескольких групп, но может и не войти ни в одно из объединений. Необходимо стремиться к тому, чтобы общее число выделенных групп было минимальным.

2. Считывание с карты Карно. Процедура получения алгебраического выражения логической функции на основании размеченной карты Карно, т.е. переход от графического представления к алгебраическому описанию, называется считыванием. Необъединенные (одиночные) клетки считываются как минтермы. Каждая группа клеток считывается в виде конъюнктивного члена, представляющего собой произведение переменных. В произведение входят переменные, которые в минитермах выделенной области представлены только в прямой или в инверсной формах.

Для упрощения считывания информации с карты Карно можно выписать номера клеток в двоичной системе счисления и сохранить только те переменные, которые имеют одинаковое значение для всей выделенной области клеток. Если в номере клетки значение переменной Хi. = 1, то она войдет в конъюнктивный член в прямой форме, если X. = 0, то – в инверсной. На рис. 3.8 темным цветом выделены те переменные, которые не входят в коньюнктивный член, так как в рассматриваемой области принимают значения и 0, и 1.

Такой же результат, полученный путем перебора, приведен в табл. 3.5, где прочерк (-) свидетельствует о том, что переменная входит в группу как в прямом, так и в инверсном виде, т.е. принимает значения 0 и 1. Для упрощения этой процедуры по периметру карты Карно (см. рис. 3.7 и 3.8) с помощью толстых линий выделены зоны (в виде одного или нескольких столбцов или строк), в которых та или иная переменная Х0,..., Хм , равна единице. Для остальной части карты значения переменных равны нулю. Например, на рис. 3.8 для области 3 переменные Х2, X, имеют значения и 0, и 1, переменная Х3 имеет значение только 0, переменная X" – только 1. Поэтому область 3 считывается как конъюнктивный член Х3Х0.

Таблица 3.5

№ группы

Х3

Х2

X,

х0

Конъюнктивный член

1

1

1

0

0

2

-

0

1

0

3

0

-

1

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

 
< Пред   СОДЕРЖАНИЕ     След >