Материалы по всему курсу схемотехники (необработанное) (2.1.1.3.10 Минимизация логических функций по картам Карно)

Посмотреть архив целиком

Минимизация логических функций по картам Карно.


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

Если требуется получить карту Карно для какой – либо функции, сначала надо записать эту функцию в СДНФ, – в совершенной дизъюнктивно нормальной форме, или в виде таблицы истинности.

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

Taблица истинности для четырех переменных включает 16 строк, следовательно карта Карно должна состоять из 16 клеток, как показано на рис.2.3.10.1.


АВ А В А В АВ


СD




C D




C D




CD




Рис.2.3.10.1. Форма карты Карно для 4 – х переменных.


У карты Карно для четырех переменных клетки крайнего левого столбца должны рассматриваться как соседние для клеток крайнего правого столбца, а клетки верхней строки, – как соседние для клеток нижней строки. Другими словами можно сказать, что эта карта расположена на поверхности цилиндра (склеили правый край карты с левым ), изогнутого и растянутого так, что его верхний срез соединяется с нижним срезом; при этом цилиндр превращается в тор (бублик).

Правила упрощения заполненной карты Карно для четырех переменных заключаются в следующем :

соседние две, четыре, или восемь единиц обводят общим контуром;

контур должен быть прямоугольным без изгибов или наклонов;

каждый контур превращает все входящие в него единицы в одну, т.е. объединенные таким образом слагаемые СДНФ булева выражения дают одно слагаемое в упрощенном выражении;

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

Примеры упрощения булевых выражений с помощью карты Карно:


1. F1 = А ВСD1 + A BCD2 +A BC D3 + A BC D4 +


+ AB CD5 + A B CD6 .


АВ А В А В АВ

BC

СD 11 12




C D 13 14



A CD

C D




CD 15 16


F1 = B C + A CD


Рис.2.3.10.2. Пример минимизации булевой функции F1 с помощью карты Карно для 4 – х переменных.

В первом примере минимизации булевой функции F1 нижний контур из двух единиц 15 и 16 , соответствующие пятому и шестому слагаемым в исходном булевом выражении, дает возможность опустить B иB. После этого в нем остается произведение A CD. В верхнем контуре из четырех единиц 11, 12, 13 и 14 , соответствующие первым четырем слагаемым в исходном булевом выражении попарно опускаются A иA, D иD, так что в результате этого верхний контур дает произведение B C.


2. F2 =АВСD1 +A BCD2 + A BCD3 +AB CD4 +AB CD5



АВ А В А В АВ

BCD

СD 11 12 13




C D



AD

C D




CD 14 15


F2 =AD + BCD


Рис.2.3.10.3. Пример минимизации булевой функции F2 с помощью карты Карно для 4 – ах переменных.



Во втором примере минимизации булевой функции F2 контур из двух единиц 12 и 13 , соответствующие второму и третьему слагаемым в исходном булевом выражении, дает возможность опустить А иА. После этого в нем остается произведение BCD. В контуре из четырех единиц 11, 12, 14 и 15 , соответствующие другим четырем слагаемым из исходного булева выражения, попарно опускаются В иВ, С иС, так что в результате этого верхний контур дает произведение AD.

Карта Карно представляется в данном случае свернутой в цилиндр, в котором верхний край совмещается с нижним. Этот пример показывает также, что контура могут накладываться друг на друга.



Случайные файлы

Файл
95462.doc
16102.rtf
12764.rtf
145443.rtf
132507.rtf




Чтобы не видеть здесь видео-рекламу достаточно стать зарегистрированным пользователем.
Чтобы не видеть никакую рекламу на сайте, нужно стать VIP-пользователем.
Это можно сделать совершенно бесплатно. Читайте подробности тут.