Программирование на JAVA

Реклама :




Так, в группе из четырех квадратов в правом верхнем углу карты функ­ции g2 во всех квадратах x1 = 1 и х3 = 0, поэтому эту группу представляет терм

. Остальные две переменные, х2 и x4 имеют в квадратах этой группы разные значения. Карты Карно можно использовать и для функций пяти переменных. В этом случае для представления функции используются две карты для четырех переменных: одна из них соответствует значению 0 пятой переменной, а другая — ее значению 1.


Рис. 2. 5. Минимизация функций с использованием карт Карно: карта для трех переменных (а); карта для четырех переменных (б)

Общая процедура формирования на карте Карно групп из двух, четырех, вось­ми и т. д. квадратов определяется просто. Две смежные пары квадратов, содержа­щих единицы, можно объединить в группу из четырех квадратов. Две смежные группы по четыре квадрата можно объединить в группу из восьми квадратов. В общем случае количество квадратов в группе должно быть равным 2k, где k — це­лое число.

Теперь давайте рассмотрим процедуру получения с помощью карты Карно ми­нимальной суммы произведений. Как видно на рис. 2.5, большей группе квадратов соответствует произведение меньшего числа переменных. Поэтому для получения минимального выражения нужно объединить все квадраты на карте, содержащие единицы, в как можно меньшее количество групп, выбирая наибольшие из них, так чтобы при этом охватить все единицы. Для примера рассмотрим карту функ­ции g2, приведенную на рис. 2.5, б. Как вы уже знаете, единицы по ее углам со­ставляют группу из четырех квадратов, представляемую термом

. Еще одна группа из четырех квадратов располагается в правом верхнем углу и представле­на термом
. Эти две группы охватывают все единицы на карте, за исключени­ем одной единицы в квадрате (x1, х2, х3, х4) - (0, 1, 0, 1). Наибольшая группа еди­ниц, включающая этот квадрат, — это группа из двух квадратов, представленная термом
.Таким образом, минимальное выражение для функции g2 должно быть следующим:

g2 =

Минимальные выражения для других функций, представленных на рис. 2.5, б, формируются аналогичным образом. Обратите внимание, что в случае функции g4 существует два альтернативных выражения: одно включает терм  

,  а вто­рое — терм
.  Такое случается довольно часто.

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

Безразличные значения

В некоторых случаях определенные наборы входных значений цифровых схем никогда не используются. Для примера рассмотрим двоично-десятичное пред­ставление числа (Binary-Coded Decimal, BCD). Десятичные цифры от 0 до 9 мож­но представить с помощью четырех двоичных переменных, b3, b2, b1 и b0 (рис. 2.6). Эти четыре переменные могут составить 16 разных наборов значений, из которых для представления десятичных цифр используются только 10. Оставшиеся зна­чения не используются. Следовательно, логическая схема, обрабатывающая дан­ные в формате BCD, никогда не получит в качестве входных данных ни один из шести оставшихся наборов значений. Такое представление десятичных цифр называется двоично-кодированным представлением десятичных цифр.

На рис. 2. 6 приведена таблица истинности для конкретной функции, прини­мающей в качестве аргумента двоично-кодированную десятичную цифру. Значе­ния этой функции для неиспользуемых входных наборов нас, естественно, не ин­тересуют. Такие значения называются безразличными (don't care) и в таблице ис­тинности они обозначаются буквой «d». При реализации функции им можно присвоить либо нуль, либо единицу, в зависимости от того, какое из этих двух значений позволит минимизировать результирующую схему. Единица присваи­вается в том случае, если такая замена приводит к расширению группы ячеек с единичными значениями функции. Поскольку большим группам соответствуют меньшие выражения, результат лучше минимизируется.

Функция, приведенная на рис. 2. 6, реализует следующий алгоритм обработки входной десятичной цифры: выходное значение равно 1, если входное значение является любым ненулевым числом, кратным 3. Три единицы на карте Карно рас­положены таким образом, что для их охвата требуются три группы квадратов, а безразличные значения определяются так, чтобы предельно увеличить размеры этих групп


Рис. 2.6. Карта Карно для четырех логических переменных


<< назад вперед >>