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

2.1.2. Записать логические выражения, реализуемые ЛЭ;

2.1.3. Изобразить временные диаграммы, характеризущие работу ЛЭ.

Таблица 3

|№ бригады |Исследуемые логические элементы |

|(варианта)| |

|1 |а) [pic] |4И-НЕ |

| |б) [pic] |2М2 |

|2 |а) [pic] |4И-НЕ |

| |б) [pic] |2М2 |

|3 |а) [pic] |2И-НЕ |

| |б) [pic] |2М2 |

|4 |а) [pic] |2И |

| |б) [pic] |2М2 |

|5 |а) [pic] |4ИЛИ |

| |б) [pic] |2М2 |

3. Контрольные вопросы

1. Объясните, как на УЛС можно проверить исправность соединительных

проводников (отсутствие обрывов)?

2. Что такое таблица истинности ЛЭ или устройства, осуществляющего

некоторое логическое преобразование?

3. Укажите размерность таблицы истинности (число строк и число

столбцов) ЛЭ: 4И и 2 ИЛИ.

4. Объясните, почему неиспользуемые входы ЛЭ “ИЛИ”, “ИЛИ-НЕ” соединяют

с корпусом (уровнем логического “0”), а на неиспользуемые входы ЛЭ

“И”, “И-НЕ” подается напряжение уровня логической “1”?

5. ЛЭ каких типов соответствуют приведенным таблицам истинности?

а) б)

6. Используя ЛЭ наборного поля получите три различных варианта схем,

реализующих логическую функцию “5И-НЕ”. Который из них является

наиболее оптимальным (рациональным)?

7. Какую логическую функцию реализует цепочка из К последовательно

соединенных инверторов, если К – нечетное число, К – четное число?

Чему эквивалентны такие цепочки?

8. Изобразите временные диаграммы, характеризующие функционирование

ЛЭ: НЕ, 3И, 3ИЛИ, 3И-НЕ, 3М2.

9. Записать логические выражения и составить таблицы истинности ЛЭ,

которым соответствуют приведенные временные диаграммы:

Лабораторная работа 2

Проектирование комбинационных цифровых

устройств в заданном базисе логических элементов

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

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

элементов (ЛЭ):

- основном функционально полном наборе (ОФПН), включающем ЛЭ «И»,

«ИЛИ», «НЕ»;

- монофункциональных наборах ЛЭ, «И- НЕ» или «ИЛИ НЕ».

1. Теоретические основы лабораторной работы

Комбинационным цифровым устройством (КЦУ) называется устройство,

выходные сигналы которого в некоторый момент времени работы однозначно

определяются лишь сигналами, действующими в тот же момент времени на его

входах. В КЦУ отсутствуют элементы памяти, поэтому выходные сигналы таких

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

КЦУ применяются для выполнения целого ряда логических и арифметических

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

дешифраторов, сумматоров, мультиплексоров и других функциональных узлов.

В общем случае проектируемое КЦУ может быть представлено в виде черного

ящика (ЧЯ), имеющего n входов и m выходов. Единственно, что изначально

известно об этом ЧЯ – это требуемый алгоритм его функционирования, т.е.

характер связи между входными воздействиями и выходными сигналами

(реакциями). Проектирование сводится к определению оптимальной (в некотором

смысле) структуры (схемы) КЦУ (ЧЯ), реализуемой в заданном базисе ЛЭ.

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

удовлетворяющей требуемому алгоритму функционирования при двух следующих

ограничениях: во-первых, схема КЦУ должна быть реализована с помощью ЛЭ

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

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

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

определенном смысле, наилучшая (оптимальная) схема, например, схема,

отличающаяся минимумом аппаратурных затрат, т.е. минимальным числом ЛЭ или

ИС.

Процесс проектирования КЦУ в общем случае включает следующие этапы:

1. Словесное описание алгоритма функционирования КЦУ, т.е. описание работы

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

2. Оценка размерности задачи и решение вопроса о проектировании КЦУ в целом

или по частям, чему предшествует разделение (условное) КЦУ на составные

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

задачи проектирования КЦУ разбивается на ряд более простых устройств

(узлов), в совокупности реализующих требуемый алгоритм функционирования,

проектирование которых не составляет особых сложностей.

3. Переход от словесного к формализованному заданию алгоритма

функционирования КЦУ с помощью логических (булевых) функций.

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

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

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

6. Построение схемы КЦУ по полученным (этапы 1-5) логическим функциям.

1.1 Формы представления алгоритмов функционирования КЦУ

Алгоритм функционирования любого КЦУ может быть представлен в виде

словесного описания.

Например, алгоритм функционирования КЦУ, фиксирующего совпадение

(эквивалентность) двух двоичных переменных может быть задан следующим

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

(у=1) тогда и только тогда, когда совпадают двоичные переменные х1 и х2 на

его входах, в иных случаях сигнал на выходе КЦУ должен быть уровня

логического нуля (у=0).

Условно сказанное можно записать в виде y = x1 ~ x2; запись следует

читать: «у равно х1 эквивалентно (или равнозначно) х2». Эту же функцию

можно представить в табличной форме (рис. 1).

Таблица показывает, чему равен выходной сигнал схемы у при различных

возможных сочетаниях входных сигналов х1 и х2. Такая таблица именуется

таблицей истинности. Имея таблицу истинности, легко осуществить переход к

аналитическому выражению функции.

В алгебре логики существуют две основные аналитические формы

представления функций: совершенная дизъюнктивная нормальная форма (СДНФ) и

совершенная конъюнктивная нормальная форма (СКНФ). Каждая из этих форм

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

элементарных функций – минтермов и макстермов.

Минтерм – это конъюнкция (логическое произведение), в которую входят

все n входных переменных в прямой или инверсной форме, а макстерм –

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

инверсной форме все n переменных, образующих функцию.

Количество минтермов и макстермов заданного числа n переменных

совпадает с числом различных наборов переменных – 2n.

СДНФ логической функции – это дизъюнкция минтермов, соответствующих

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

СКНФ логической функции – это конъюнкция макстермов, соответствующих

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

2. Алгоритм перехода от таблицы истинности

логической функции к ее записи в виде СДНФ

1. Выбрать в таблице такие наборы входных переменных, на которых

функция обращается в единицу;

2. Записать минтермы для выбранных наборов входных переменных. При

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

входной переменной в наборе – единичное, то она записывается в

прямой форме, если же значение переменной – нулевое, то – в

инверсной форме;

3. Полученные минтермы объединить между собой знаками дизъюнкции.

Пример 1. Получить СДНФ логической функции y = x1 ~ x2.

Решение. Из таблицы истинности (рис.1.) следует, что функция у=1 на

двух наборах входных переменных: (0 0) и (1 1). Для выбранных наборов

записываем минтермы в соответствии с п.2 приведенного выше алгоритма:

[pic], [pic].

Соединив минтермы знаком дизъюнкции, получим СДНФ функции:

[pic]

1.3 Алгоритм перехода от таблицы истинности

логической функции к ее записи в виде СКНФ

1. Выбрать в таблице истинности такие наборы входных переменных, на которых

функция принимает нулевые значения;

2. Записать макстермы для выбранных наборов. При этом следует

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

наборе нулевое, то она записывается в прямой форме, если значение

переменной единичное, то – в инверсной форме;

3. Полученные макстермы соединить знаками конъюнкции.

Пример 2. Получить СКНФ логической функции y = x1 ~ x2.

Решение. Из таблицы истинности (рис.1.), следует, что функция y=x1~x2=0

на двух наборах входных переменных (0 1) и (1 0). Для указанных наборов

записываем макстермы

[pic] и [pic].

Соединив их знаком конъюнкции, получим СКНФ функции:

[pic]

Нетрудно убедиться, что СДНФ и СКНФ функции эквивалентны.

1.4 Минимизация логических функций

Работа любого КЦУ с одним выходом может быть описана логическим

выражением или системой m логических выражений, если у КЦУ m выходов.

Другими словами, всякому КЦУ с одним выходом или каждому из m выходов

многовыходного КЦУ взаимно однозначно соответствует логическое выражение, в

котором буквы соответствуют входным переменным, а знаки операций – ЛЭ,

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

связи «вход-выход» КЦУ. В этих условиях упрощение схемы КЦУ сводится к

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

СДНФ и СКНФ используются для первоначального представления логических

функций, но эти формы, как правило, неэкономичны для построения схем КЦУ.

Прежде чем строить схему, реализующую логическую функцию, ее необходимо

минимизировать, т.е. найти такую эквивалентную форму представления, при

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

переменных (букв).

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

используя постулаты и законы булевой алгебры.

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

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

операцией упрощения является операция склеивания смежных минтермов.

Смежными принято называть минтермы, отличающиеся формой вхождения в них

лишь одной переменной (в один минтерм переменная входит в прямой форме, а в

другой – в инверсной). Например, смежными являются минтермы [pic] и [pic]

(различаются формой вхождения только переменной х1).

Два смежных минтерма СДНФ могут быть объединены по разнящемуся

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

числом переменных на единицу меньшим, чем в исходных минтермах.

Например, [pic]

Операция объединения смежных минтермов по разнящейся переменной

именуется склеиванием.

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

называется импликантой. Импликанты с одинаковым числом переменных (рангом),

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

склеивание между собой.

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

которые не имеют себе смежных. Такие импликанты называют простыми.

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

Карно. Карты Карно представляют собой прямоугольную таблицу (матрицу),

разбитую горизонтальными и вертикальными линиями на клетки (ячейки). Общее

число ячеек совпадает с числом минтермов и равно 2n, где n – число

переменных упрощаемой функции. Таким образом, каждая ячейка карты

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

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

Соседними считаются ячейки, имеющие общие стороны, а также расположенные на

краях одних и тех же строк или столбцов карты.

Такой порядок размещения минтермов обеспечивается принятым способом

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

Все переменные разбиваются на две группы. Наборам переменных одной группы

ставят в соответствие столбцы, наборам другой группы – строки карты. Для

определенности крайний левый столбец и верхнюю строку карты обозначают

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

обязательным).

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

разделенную на четыре ячейки, по одной на каждый входной набор (рис. 2, а).

Строки карты связаны с переменной [pic], столбцы – с переменной [pic].

Расположенная слева вверху ячейка соответствует входному набору (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 |

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