Основы цифровой техники

Расположенная слева вверху ячейка соответствует входному набору (0 0) или

минтерму ([pic]), расположенная ниже ее ячейка соответствует входному

набору (1 0) или минтерму ([pic]) и т.д.

В случае функции трех переменных карта Карно (рис. 2, б) содержит

восемь ячеек, по одной для каждого входного набора, указанного внутри

ячейки.

Поскольку для функции четырех переменных существует 16 входных наборов,

карта Карно разделена на 16 ячеек (рис. 2, в).

Наряду с изложенным применяют и другой способ маркировки размещения

минтермов: столбцы и строки карты Карно, соответствующие переменным в

прямой форме, охватывают скобками и возле них проставляют символы

переменных.

Аналогично поступают для переменных, представленных в инверсной форме.

Пример маркировки строк и столбцов карты Карно для функции трех и четырех

переменных приведен на рис. 3.

| | |[pic] |x2 |

| | | | |

|[pi| | | | | |

|c] | | | | | |

|х1 | | | | | |

| | | | | |

| | |[pic]|x3 |[pic]|

а)

| |[pic] |х3 | |

| | | | |

| | | | | | | |[pi|

|[pi| | | | | | |c] |

|c] | | | | | | | |

| | | | | | | | |

| | | |* | | | |х2 |

| | | | | | | | |

|х1 | | | | | | | |

| | | | | | | |[pi|

| | | | | | | |c] |

| | | | | |

| |[pic]|x4 |[pic]| |

б)

Рис. 3. Альтернативный способ маркировки строк и столбцов карты Карно для

функции трех (а) и четырех (б) переменных

Минтермы, соответствующие определенным ячейкам карты, образуются из

наборов групп переменных (рис. 2) или наборов переменных (рис. 3),

обозначающих строку и столбец, на пересечении которых расположена

рассматриваемая ячейка. Например, ячейке, выделенной на рис. 3,б

соответствует минтерм [pic].

1.5 Алгоритм минимизации логических функций, заданных

в СДНФ при помощи карт Карно

1. Обозначить ячейки карты, соответствующие минтермам упрощаемой

функции. Обозначение состоит в простановке (записи) единиц в

соответствующие ячейки карты. Остальные ячейки остаются не заполненными.

Для обозначения ячеек карты используют либо аналитическое выражение

упрощаемой функции, либо ее таблицу истинности.

2. 2К соседних обозначенных ячеек, расположенных по столбцу или по

строке, либо образующих прямоугольник или квадрат, объединить в контур

(блок).

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

2.1. Одни и те же ячейки могут входить в несколько блоков;

2.2. Блоки должны покрывать все обозначенные ячейки;

2.3. Следует стремиться к тому, чтобы количество блоков было

минимальным, а сами блоки покрывали по возможности большее число ячеек.

3. Для каждого блока записать логическое выражение в виде конъюнкции

тех переменных, значения которых совпадают у всех объединенных в блок

ячеек. Если блок покрывает 2, 4 или более ячеек, то конъюнкции представляют

собой импликанты склеиваемых минтермов. Ранг полученных таким образом

импликант меньше ранга минтермов, объединенных в контур, на К единиц.

4. Логические выражения для блоков объединить значками дизъюнкции.

Полученное выражение представляет собой минимизированную дизъюнктивную

нормальную форму (МДНФ) логической функции.

Пример 3. Минимизировать с помощью карты Карно логическую функцию:

[pic]

Решение. Упрощаемая функция трех переменных задана своей СДНФ. Выбираем

соответствующую карту Карно (рис. 3,а) и обозначаем ее ячейки,

соответствующие минтермам функции. Так как упрощаемая функция содержит пять

минтермов, то и на карте Карно должно быть пять обозначенных ячеек (рис.4).

| |[pic] |[pic] |

| | | |

|[pic| | | | | |

|] | | |1 |1 |1 |

|х1 | | | | | |

| | | |1 |1 | |

| | | | | |

| | |[pic|[pic] |[pic|

| | |] | |] |

Рис. 4. Пример минимизации функции [pic]

После заполнения карты образуем контуры, покрывающие все обозначенные

ячейки (в соответствии с правилами, изложенными выше). Для рассматриваемой

функции достаточно образовать два контура. В первый входят четыре ячейки,

находящиеся в средней части карты; во второй – две крайние ячейки верхней

строки карты.

Логическое выражение для первого контура - [pic] (так как только по

[pic] совпадают обозначения ячеек, входящих в первый блок); для второго

контура - [pic]. В результате получаем МДНФ функции: [pic].

1.6 Минимизация частично определенных

и инверсных логических функций

Частично (не полностью) определенными называют функции, значения

которых заданы лишь для части множества возможных наборов их переменных.

Такие функции достаточно часто встречаются в задачах проектирования КЦУ,

где их происхождение обусловлено тем, что некоторые сочетания (комбинации)

входных переменных при работе КЦУ не имеют места.

Наборы переменных, для которых функция не определена, называют

избыточными или запрещенными. Например, избыточные наборы будут иметь место

при реализации двоично-десятичного кода, т.е. при представлении десятичных

цифр от 0 до 9 двоичным кодом. Действительно, для такого представления

необходимо использовать четыре двоичные переменные (четыре двоичных

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

первые 10. Следовательно, 6 наборов оказываются избыточными.

При минимизации частично определенных функций производят их

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

соответствующих избыточным наборам. Эти значения можно выбирать равными 0

или 1. Доопределение выполняют таким образом, чтобы результирующая МДНФ

функции была наиболее простой (при этом учитывается возможность выполнения

дополнительных склеиваний при доопределении функции).

Пример 4. Минимизировать логическую функцию, заданную своей таблицей

истинности (рис. 5, а). Значения функции, соответствующие трем последним

наборам входных переменных, не определены (что отмечено * в столбце yисх).

На карте Карно рассматриваемой функции (рис. 5, б) ячейки для избыточных

наборов также отмечены звездочками. Доопределение функции единицами для

всех избыточных наборов позволяет представить ее МДНФ в виде:

[pic]

Для сравнения приведем выражение исходной функции:

[pic],

которую без приема доопределения упростить невозможно.

В пределах определения (на допустимых наборах входных переменных)

значения функций уисх и удоопр совпадают. Выяснение тождественности этих

функций на запрещенных наборах не представляет интереса, так как при работе

КЦУ они не будут иметь места.

Сократить трудоемкость минимизации иногда можно за счет работы не с

самой заданной функцией, а с ее инверсией. Если число единиц в таблице

истинности превышает половину числа наборов переменных, то СДНФ для

инверсии функции будет содержать меньше конъюнкций, чем СДНФ для прямой

функции.

|х1 |х2 |х3 |уисх |удоопр|

|0 |0 |0 |0 |0 |

|0 |0 |1 |0 |0 |

|0 |1 |0 |0 |0 |

|0 |1 |1 |1 |1 |

|1 |0 |0 |1 |1 |

|1 |0 |1 |* |1 |

|1 |1 |0 |* |1 |

|1 |1 |1 |* |1 |

а)

| |[pic] |х1 |

| | | |

|[pic| | | | | |

|] | | | |* |1 |

|х3 | | | | | |

| | | |1 |* | |

| | | | |

| | |х2 |[pic] |

| |[pic| | |

| |] | | |

б)

Рис. 5. Таблица истинности (а) и карта Карно (б)

частично определенной функции

Пример 5. Упростить функцию, заданную таблицей истинности (рис. 6).

Решение. СДНФ требуемой (прямой) функции

[pic]

|х1 |х2 |х3 |y |[pic] |

|0 |0 |0 |1 |0 |

|0 |0 |1 |1 |0 |

|0 |1 |0 |1 |0 |

|0 |1 |1 |1 |0 |

|1 |0 |0 |1 |0 |

|1 |0 |1 |0 |1 |

|1 |1 |0 |1 |0 |

|1 |1 |1 |0 |1 |

Рис. 6. Таблица истинности функции [pic]

Поскольку столбец у содержит шесть единиц из восьми возможных, то

столбец для [pic] содержит лишь две единицы, что и отражено в таблице (рис.

6).

Для [pic] СДНФ будет значительно проще:

[pic]

Последнее выражение более обозримо, чем для у, и легко минимизируется:

[pic], откуда [pic].

1.7 Преобразование минимальных форм логических функций к виду, реализуемому

ЛЭ заданного функционально полного набора

Любая логическая функция, как было сказано выше, может быть записана в

виде СДНФ или СКНФ. Следовательно, любую функцию n переменных можно

представить с помощью набора трех элементарных функций: инверсии,

дизъюнкции и конъюнкции. Возможны и другие наборы функций, с помощью

которых может быть выражена произвольная функция.

Набор элементарных булевых функций называют функционально полным (ФПН),

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

суперпозицией функций этого набора.

Набор логических функций инверсия (НЕ), дизъюнкция (ИЛИ) и конъюнкция

(И) получил наименование основного (ОФПН).

Среди других наборов функций, образующих ФПН, особый интерес

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

одну булеву функцию. Таковыми, в частности, являются набор, состоящий

только из функции «штрих Шеффера» (И-НЕ) и набор, состоящий только из

функции «стрелка Пирса» (ИЛИ-НЕ).

1.8 Минимальные формы в монофункциональных базисах

Основой для получения минимальных форм логических функций в базисах

функций штрих Шеффера и стрелка Пирса может служить МДНФ, полученная в

результате решения задачи минимизации.

МДНФ представляет собой дизъюнкцию простых импликант и может быть

представлена в обобщенном виде:

[pic] (1)

где Ji – символ импликант, а d - их количество.

Формулы функций штрих Шеффера и стрелка Пирса для случая r переменных

имеют вид:

[pic] (2)

[pic][pic] (3)

Для перехода от МДНФ к минимальной форме в базисе функции штрих Шеффера

конъюнкции и дизъюнкции в выражении (1) должны быть заменены функциями вида

(2). Это достигается двукратным инвертированием (1) и применением теоремы

де Моргана-Шеннона. Первое инвертирование (1) с учетом указанной теоремы

приводит к соотношению:

[pic] (4)

Второе инвертирование с учетом закона двойного отрицания дает:

[pic] (5)

Каждый из членов [pic] соотношения (5) и все это соотношение в целом

представляет собой функции штрих Шеффера.

Следовательно, (5) выражает переход от МДНФ к искомой форме формулы в

базисе функций штрих Шеффера. Формулу (5) называют оптимальной

конъюнктивной инверсной формой логической функции или оптимальным инверсным

произведением.

Переход от МДНФ к минимальной форме в базисе функций стрелка Пирса

осуществляется заменой импликант в (1) функциями вида (3). Обозначим

преобразованную в соответствии с теоремой де Моргана-Шеннона инверсию

импликанты [pic] символом Gi. Тогда (4) можно переписать в виде:

[pic] (6)

Трехкратное инвертирование (6) приводит к искомой форме формулы в

базисе функций стрелка Пирса

[pic] (7)

Каждый член дизъюнкции в (7) и инверсия всей дизъюнкции представляет

собой функции стрелка Пирса; заключительное инвертирование также может быть

выполнено элементами стрелка Пирса (ИЛИ - НЕ). Формулу (7) называют

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

оптимальной инверсной суммой.

Пример. 6. Представить логическую функцию «равнозначность двух

переменных» в базисе функций штрих Шеффера и стрелка Пирса.

Решение. СДНФ функции равнозначность двух переменных (приведена выше)

имеет вид:

[pic] (8)

Первое инвертирование (8) с учетом теоремы де Моргана приводит к

выражению:

[pic].

Второе инвертирование с учетом закона двойного отрицания приводит к

искомой форме в базисе функций штрих Шеффера:

[pic] (8.1)

Четырехкратное инвертирование (8.1) дает искомую форму в базисе функций

стрелка Пирса:

[pic]

[pic]

[pic]

[pic] (8.2)

1.9 Проектирование схемы КЦУ в заданном базисе ЛЭ

Каждая из элементарных логических функций, образующих ОФПН, может быть

воспроизведена (реализована) соответствующими ЛЭ: инверторами (НЕ),

дизъюнкторами (ИЛИ) и конъюнкторами (И), образующими ОФПН ЛЭ.

Аналогичным образом могут быть реализованы функции монофункциональных

наборов: функции штрих Шеффера – с помощью ЛЭ «И-НЕ», функции стрелка Пирса

– с помощью ЛЭ «ИЛИ -НЕ», образующих монофункциональные наборы ЛЭ.

Основой для проектирования КЦУ в ОФПН ЛЭ служит минимальная форма

логической функции – МДНФ или МКНФ. Основой для проектирования КЦУ в

монобазисном наборе ЛЭ служит оптимальное инверсное произведение или

оптимальная инверсная сумма.

Пример 7. Спроектировать схему КЦУ равнозначности двух переменных а) в

ОФПН ЛЭ, б) в монофункциональном наборе ЛЭ «И -НЕ», в) в монофункциональном

наборе ЛЭ «ИЛИ -НЕ».

Решение. Основой для проектирования являются выражения (8), (8.1) и

(8.2) соответственно. Схемы КЦУ, реализующие функцию “равнозначность двух

переменных”, приведены на рис.7.

1.10 Проектирование многовыходных КЦУ

На практике часто встречается необходимость проектирования КЦУ, имеющих

несколько (m) выходов. В этих случаях для синтеза схемы устройства можно

воспользоваться рассмотренной выше последовательностью действий, если

представить устройство в виде совокупности соответствующего числа (m) КЦУ,

имеющих общие входы. Другими словами, проектирование многовыходного КЦУ

сводится к синтезу m одновыходных схем КЦУ, имеющих общие входы х1, х2, …,

хn, выходы которых в совокупности образуют выходы устройства: у1, у2, …,

уm.

Пример 8. Спроектировать схему КЦУ, вычисляющего значения функции

у=х2+3, если х может принимать целые значения в диапазоне от 0 до 3.

Решение. Представим функцию, подлежащую реализации в виде таблицы

(рис.8.)

В проектируемом устройстве как аргумент х, так и функция у должны быть

представлены в виде двоичных кодов. Перевод х и у в двоичные коды

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

двоичные коды. Число разрядов n и m, необходимых для представления х и у в

двоичном коде, определяется согласно соотношениям:

n ? log2(xmax+1), m ? log2(ymax+1). (9)

Из (9) находим число двоичных разрядов, необходимых для представления

аргумента х и функции у в виде ближайших больших целых чисел:

n ? log2(3+1)=2, m ? log2(12+1)=4.

Таким образом, проектируемое устройство должно иметь два входа, на

которые поступают двоичные разряды аргумента х1 и х2 и четыре выхода, на

которых формируются двоичные разряды функции у1, у2, у3, у4 (рис.9, а). Для

получения уравнений связи выходных переменных (реакций) с входными

переменными (воздействиями) изобразим таблицу истинности (функционирования)

устройства (рис. 9, б).

|х2|х1|у4|у3|у2|у1|

|21|20|23|22|21|20|

|0 |0 |0 |0 |1 |1 |

|0 |1 |0 |1 |0 |0 |

|1 |0 |0 |1 |1 |1 |

|1 |1 |1 |1 |0 |0 |

а) б)

Рис. 9. Условное графическое изображение (а)

и таблица функционирования (б) проектируемого устройства

Из таблицы функционирования для каждого выхода уi (i=1, 2, 3, 4)

получим уравнения связи в виде СДНФ:

[pic],

[pic],

[pic].

Упростим (минимизируем) полученные выражения (выражение для у4 не

Страницы: 1, 2, 3, 4, 5