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

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

Карты Карно были изобретены в 1952 Эдвардом В. Вейчем и усовершенствованы в 1953 Морисом Карно, физиком из «Bell Labs», и были призваны помочь упростить цифровые электронные схемы.

В карту Карно булевы переменные передаются из таблицы истинности и упорядочиваются с помощью кода Грея, в котором каждое следующее число отличается от предыдущего только одним разрядом.

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

Возможность поглощения следует из очевидных равенств

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

Как известно, булевы функции N переменных, представленные в виде СДНФ или СКНФ могут иметь в своём составе 2N различных термов. Все эти члены составляют некоторую структуру, топологически эквивалентную N–мерному кубу, причём любые два терма, соединённые ребром, пригодны для склейки и поглощения.

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

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

Как видно из рисунка, для трёхмерного случая возможны более сложные конфигурации термов. Например, четыре терма, принадлежащие одной грани куба, объединяются в один терм с поглощением двух переменных:

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

Для упрощения работы с булевыми функциями большого числа переменных был предложен следующий удобный приём. Куб, представляющий собой структуру термов, разворачивается на плоскость как показано на рисунке. Таким образом появляется возможность представлять булевы функции с числом переменных больше двух в виде плоской таблицы. При этом следует помнить, что порядок кодов термов в таблице (00 01 11 10) не соответствует порядку следования двоичных чисел, а клетки, находящиеся в крайних столбцах таблицы, соседствуют между собой.

Аналогичным образом можно работать с функциями четырёх, пяти и более переменных. Примеры таблиц для N=4 и N=5 приведены на рисунке. Для этих таблиц следует помнить, что соседними являются клетки, находящиеся в соответственных клетках крайних столбцов и соответственных клетках верхней и нижней строки. Для таблиц 5 и более переменных нужно учитывать также, что квадраты 4х4 виртуально находятся друг над другом в третьем измерении, поэтому соответственные клетки двух соседних квадратов 4х4 являются сосоедними, и соответствующие им термы можно склеивать.

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

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

1. Объединяем смежные клетки содержащие единицы в область, так чтобы одна область содержала 2 ⁿ (n целое число = 0… ) клеток(помним про то что крайние строки и столбцы являются соседними между собой), в области не должно находиться клеток содержащих нули;
2. Область должна располагаться симметрично оси(ей) (оси располагаются через каждые четыре клетки);
3. Не смежные области расположенные симметрично оси(ей) могут объединяться в одну;
4. Область должна быть как можно больше, а кол-во областей как можно меньше;
5. Области могут пересекаться;
6. Возможно несколько вариантов накрытия.

 

Далее берём первую область и смотрим какие переменные не меняются в пределах этой области, выписываем конъюнкцию этих переменных, если неменяющаяся переменная нулевая, проставляем над ней инверсию. Берём следующую область, выполняем то же самое что и для первой, и т. д. для всех областей. Конъюнкции областей объединяем дизъюнкцией.
Например(для Карт на 2-ве переменные):

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

В формате КНФ:

Электронные ключи.

Электронные ключи входят в состав многих импульсных устройств. Основу любого электронного ключа составляет активный элемент (полупроводниковый диод, транзистор), работающий в ключевом режиме. Ключевой режим характеризуется двумя состояниями ключа: "Включено" – "Выключено". На рисунке приведены упрощённая схема и временные диаграммы идеального ключа. При разомкнутом ключе , , при замкнутом ключе , . При этом предполагается, что сопротивление разомкнутого ключа бесконечно велико, а сопротивление равно нулю.

рис. 0.1. Схема, временные диаграммы тока и выходного напряжения идеального ключа.

 

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

падением напряжения на ключе в замкнутом состоянии ;

током через ключ в разомкнутом состоянии ;

временем перехода ключа из одного состояния в другое (временем переключе­ния) .

Чем меньше значения этих величин, тем выше качество ключа.

 

Диодные ключи

 

Простейший тип электронных ключей – диодные ключи. В качестве активных элементов в них используются полупроводниковые или электровакуумные диоды.

При положительном входном напряжении диод открыт и ток через него

,
где - прямое сопротивление диода.

Выходное напряжение

.

Обычно , тогда . При отрицательном входном напряжении ток идет через диод

,

где - обратное сопротивление диода.

При этом выходное напряжение

.

Как правило, и . При изменении полярности включения диода график функции повернется на угол вокруг начала координат.

рис. 0.2. Схема и передаточная характеристика последовательного диодного ключа с нулевым уровнем включения.

 

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

рис. 0.3. Схема и передаточная характеристика последовательного диодного ключа с ненулевым уровнем включения.

 

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

Диодные ключи не позволяют электрически разделить управляющую и управляемые цепи, что часто требуется на практике. В этих случаях используются транзисторные ключи.

⇐ Предыдущая12345Следующая ⇒

Поделиться: Я.Мессенджер ВКонтакте Одноклассники Telegram Twitter Мой Мир

Воспользуйтесь поиском по сайту: