Компьютерная схемотехника

Форма 1:(3.1.1)

Форма 2:(3.1.2)

Последние два выражения вытекают из принципа двойственности булевой алгебры (раздел 3.5).

Теорема без названия. Существует еще одна теорема без названия, которую представим следующим образом:

(3.1.3)

Два полезных соотношения:

(3.1.4)

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

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

Предположим, логическая функция трех переменных задана таблицей истинности (таблица 3.4).

Таблица 3.4

Эта функция имеет четыре конституенты единицы К1, К4, К5 и К6 (коституента единицы - это единичное значение ПФ на одном конкретном наборе. Всего для ПФ трех переменных может быть восемь конституент единицы, если функция принимает единичное значение на всех наборах). Конституента единицы записывается в виде конъюнкции. Для нашего примера ; .

Булево выражение ПФ в СДНФ представляет сумму конституент единицы:

.(3.2)

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

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

3.9 Дизъюнктивная нормальная форма (ДНФ)

3.10 Совершенная конъюнктивная нормальная форма (СКНФ) записи булевых выражений

Описанная таблицей 3.4 переключательная функция помимо конституент единицы содержит конституенты нуля К0, К2, К3 и К7 (конституента нуля - это нулевое значение ПФ на одном конкретном наборе). Всего для ПФ 3-х переменных может быть восемь конституент нуля, если функция принимает нулевое значение на всех наборах. Конституента нуля записывается в виде дизъюнкции. Для нашего примера (таблица 3.4) это

Булево выражение в СКНФ представляет собой произведение конституент нуля:

.(3.3)

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

Логическая функция имеет единственное булево выражение в СКНФ.

3.11 Конъюнктивная нормальная форма (КНФ)

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

- алгебраический;

- с помощью диаграмм Вейча (карт Карно).

3.12.1 Алгебраический способ минимизации ПФ

Пример 1. Исходное булево выражение:

.(3.4)

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

,(3.5)

которое равносильно (эквивалентно) исходному, но значительно проще его.

Пример 2. Исходное булево выражение:

.(3.6)

Используя тождество А=А+А и теорему склеивания получим более простое выражение

.(3.7)

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

Более наглядным и удобным является минимизация с применением диаграмм Вейча (карт Карно).

3.12.2 Минимизация ПФ с использованием диаграмм Вейча (карт Карно)

3.12.2.1 Минимизация ПФ с помощью диаграмм Вейча

Исходным продуктом для применения диаграмм Вейча является представление ПФ таблицей истинности, в которой возможные наборы переменных упорядочены по возрастанию или по убыванию их десятичных эквивалентов (таблица 3.1). Вид диаграмм Вейча зависит от числа переменных минимизируемой ПФ - n и от того, как упорядочены наборы переменных в таблице. Если наборы упорядочены по возрастанию их десятичных эквивалентов, то диаграммы Вейча для n=2,3,4 имеют вид, приведенный на рисунке 3.1.

Рисунок 3.1

Число клеток диаграммы равно количеству наборов переменных

Nкл=Nнаб=2n.(3.8)

Если n=2, то Nкл=22=4; n=3 - Nкл=8, n=4 - Nкл=16.

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

Строки и столбцы диаграммы, помеченные чертой, определяют наборы, в которых переменные принимают единичные значения (входят в прямой форме). Строки и столбцы, не помеченные чертой, соответствуют наборам, в которых те же переменные принимают нулевые значения (входят в инверсной форме). Например, для n=3 (рисунок 3.1) двум левым столбцам соответствует единичное значение переменной В (в входит в прямой форме), а двум правым - нулевое значение (в входит в инверсной форме).

В клетки записываются значения ПФ на соответствующем наборе (нулевое или единичное). Если на каком-то наборе функция не определена, то в клетке диаграммы ставится прочерк.

ПФ считается неопределенной, если:

1) данный набор переменных в реальном логическом устройстве невозможен;

2) значение функции на данном наборе безразлично.

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

В первом случае результатом минимизации будет булево выражение в ДНФ, а во втором - в КНФ.

3.12.2.1.1 Общие правила минимизации

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

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

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

На рисунке 3.1 показаны диаграммы Вейча при числе логических переменных n=2,3,4. Для n>4 диаграммы содержатся в [18]. Если наборы переменных исходной таблицы истинности упорядочены по убыванию их десятичных эквивалентов, то следует воспользоваться диаграммами Вейча, приведенными в [5, 6]

3.12.2.1.2 Примеры минимизации ПФ с помощью диаграмм Вейча

Пример 1. Для контроля за возможной деформацией металлической конструкции из-за перегрева в ее различных критических точках установлены четыре термодатчика, обозначенные ТД1, ТД2, ТД3, ТД4. Экспериментальные исследования конструкции показали, что в процессе ее эксплуатации возможны шесть сочетаний сработавших и не сработавших датчиков. При этом деформация конструкции возникала в следующих случаях:

1) сработали ТД4, ТД3 и не сработали ТД2 и ТД1;

2) сработали ТД4, ТД3, ТД2 и ТД1;

3) сработали ТД2 и не сработали ТД4, ТД3 и ТД1;

4) сработали ТД3, ТД2 и ТД1 и не сработал ТД4;

В случаях, когда:

5) сработали ТД4, ТД3, ТД2 и не сработал ТД1;

6) сработали ТД2, ТД1 и не сработали ТД4, ТД3

деформация конструкции не возникала.

Таблица 3.5

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

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

Обозначим цифровые сигналы на выходе термодатчиков логическими переменными: ТД4>D; ТД3>С; ТД2>В; ТД1>А, а логическую функцию, которую должно реализовать устройство контроля - F.

Составим таблицу истинности, отражающую требуемую логическую функцию (таблица 3.6).

Таблица 3.6

Диаграмма Вейча, отражающая данную таблицу, показана на рисунке 3.2.

Рисунок 3.2

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

Основные единицы накрываем тремя контурами: 1-й контур (1I) образуют клетки первой и последней строки, 2-й (1II) - клетки 2-го столбца и 3-й (1III) - 4-го столбца.

Итоговое булево выражение минимизированной ПФ имеет вид

.(3.9)

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

Рассматриваемую функцию можно минимизировать и по нулевым значениям (нулям). Для этого доопределяем клетки с номерами 1,6,9 и 11 нулями и накрываем два основных нуля двумя прямоугольниками, включающими два и четыре элемента (нуля). Первый прямоугольник (0I) охватывает клетки с номерами 6,14, второй (0II) - 1,3,11 и 9.

Итоговое булево выражение минимизированной ПФ имеет вид

.(3.10)

Оба выражения (3.9) и (3.10) эквивалентны, и применять следует то из них, которое проще реализуется на конкретном наборе логических элементов (базисе). Этот вопрос будет рассмотрен в следующих лекциях.

Пример 2. Необходимо разработать блок приоритетных прерываний от 2-х внешних устройств: ВУ1 и ВУ2. ВУ с меньшим номером соответствует более высокий приоритет. Упрощенная структура проектируемой системы показана на рисунке 3.3.

Рисунок 3.3

На схеме приняты следующие сокращения: МПС - микропроцессорная система; ВУ - внешнее устройство; БПП - блок приоритетных прерываний; ВТП - вектор текущего прерывания, который с помощью логических переменных в1, в2 описывает возможные состояния МП-системы при обслуживании запросов прерываний от ВУ (таблица 3.7); РТП - регистр текущего прерывания (запоминает значения переменных в1, в2); ЗП1, ЗП2 - запросы прерываний от ВУ1, ВУ2 (описываются переменными б1, б2); ТП - требование прерывания (логическая функция F3); ВЗП - вектор запроса прерывания (отображается комбинацией значений логических функций F1 и F2 (таблица 3.8)).

Таблица 3.7

Таблица 3.8

МП-система периодически проверяет значение сигнала ТП (функция F3). Если ТП=0 (запрос на прерывание отсутствует), то значения функций F1, F2 безразличны и МПС продолжает свою работу. Если ТП=1, то МП-система анализирует значение вектора ВЗП (комбинацию функций F1, F2) и определяет номер запроса прерывания. Так как набор переменных в1=в2=1 невозможен (таблица 3.6), то функции F1, F2, F3 в таких случаях неопределены. Таким образом, задача БПП является реализация трех логических функций F1, F2, F3, каждая из которых определяется значениями четырех логических переменных: б1, б2, в1и в2.

Составим таблицу истинности (таблица 3.9) для названных функций.

Таблица 3.9

Представляем функции F1, F2, F3 диаграммами Вейча (рисунок 3.4)

Для F3 Для F1

Для F2

Рисунок 3.4

Булевы выражения минимизированных ПФ имеют вид:

F3=.(3.11)

F1=.(3.12)

F2=.(3.13)

Полученные выражения (3.11-3.13) имеют вполне конкретное логическое толкование и при наличии определенных навыков могли быть получены без составления таблицы истинности и минимизации ПФ.

Так, если F3=1, а в противном случае F1 и F2 безразличны, то запрос от ВУ1 в виде комбинации F1=0, F2=1 поступит лишь тогда, когда б1=1. Значение б2 безразлично, так как даже при б1=б2=1 все равно б1 имеет более высокий приоритет. Если б1=0, а F3=1, то это значит, что требование прерывания вызвано запросом от ВУ2 (б2=1). При записи выражения (3.11) можно было руководствоваться следующими соображениями. F3=1 в двух случаях. Во-первых, если поступил запрос от ВУ1 (б1=1) и при этом МП-система ожидает запроса либо обслуживает прерывание от ВУ2 (в обоих случаях в2=0, см. таблицу 3.8). Во вторых, если поступил запрос от ВУ2 (б2=1) и при этом МП-сиcтема находится в состоянии ожидания (в1=в2=0). Сказанное соответствует двум составляющим выражения (3.11).

На втором примере мы прошли 2 этапа синтеза комбинационных цифровых электронных устройств:

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

2. Получение минимальной ДНФ для каждого выхода комбинационной схемы.

3.12.2.2 Минимизация ПФ с помощью карт Карно

На рисунке 3.5 показан пример карты Карно для ПФ четырех переменных (n=4).

Рисунок 3.5

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

Клетки, помеченные переменными в прямой форме, соответствуют наборам, где эти переменные принимают единичные значения, а клетки, обозначенные переменными в инверсной форме - наборам, где эти переменные равны нулям.

Карты Карно удобно использовать, если ПФ задана в виде булевого выражения в СДНФ.

Например,

(3.14)

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

Булево выражение минимизированной ПФ имеет вид

.(3.15)

Другие примеры использования диаграмм Вейча и карт Карно показаны в [3, 18].

4. ЛОГИЧЕСКИЕ ЭЛЕМЕНТЫ

Для аппаратной реализации булевых выражений используется некоторый набор логических элементов, выпускаемых в виде интегральных микросхем (ИМС). Существуют специализированные ИМС, разработанные методами интегральной технологии специально для получения требуемой логической зависимости. Специализированные ИМС не требуют никаких паяных межсоединений и обладают высокой надежностью. Однако разработка подобных микросхем экономически оправдана лишь при большом объеме выпуска. Примером может служить массовый выпуск специализированных БИС для электронных часов, микрокалькуляторов и т.д.

Помимо специализированных ИМС имеется универсальный набор логических элементов в виде ИМС, обеспечивающий реализацию любых логических функций. К этому набору можно отнести: инвертор; конъюнктор; дизъюнктор; повторитель; И-НЕ; ИЛИ-НЕ; исключающее ИЛИ; сложение по модулю два (нечетность); сложение по модулю два с отрицанием (четность); эквивалентность; неэквивалентность; И-ИЛИ-НЕ; запрет и др.

4.1 Инвертор (логический элемент НЕ)

Инвертор реализует логическую функцию

.(4.1)

Ниже показаны его обозначение на электрических схемах (рисунок 4.1,а) и принципиальная схема (рисунок 4.1,б).

А Б

Рис. 4.1

4.2 Конъюнктор (логический элемент И)

Конъюнктор реализует логическую функцию

.(4.2)

Ниже показаны его обозначение на электрических схемах (рисунок 4.2,а), принципиальная схема (рисунок 4.2,б) и таблица истинности (таблица 4.1).

А Б

Рисунок 4.2

Таблица 4.1

Термин “логический” обычно применяют по отношению к процедуре принятия решения. В таком случае можно сказать, что логический элемент - это такая схема, которая “основываясь” на входных сигналах, “может решать”, что ей ответить на выходе - “да” или “нет”. Схема конъюнктора на рисунке 4.2,б отвечает “да” (на выходе появляется высокий уровень напряжения) только в том случае, когда на оба её входа поданы сигналы “да” (оба входных напряжения имеют высокий уровень).

Рисунок 4.3

На рисунке 4.3 показана схема исследования логического элемента И в лабораторных условиях.

Входы логического элемента подключены к ключам SA1 и SA2. Индикатором выхода служит светодиод. Если на входах А и В возникают сигналы НИЗКОГО логического уровня (земля), то светодиод не излучает. Эту ситуацию отражает первая строка таблицы 4.2.

Таблица 4.2

Помимо значений уровней напряжений и отметки наличия излучения входные и выходные сигналы в таблице 4.2 обозначены двоичными цифрами: 0 и 1. Согласно строке 1, если на оба входа поданы двоичные нули, то на выходе логического элемента также возникает двоичный нуль. Двоичная единица на выходе элемента И появляется только в том случае, когда на оба входа А и В поданы двоичные единицы.

Двоичной единице, или напряжению ВЫСОКОГО уровня, в точках А, В или F соответствует потенциал +5В относительно земли. Двоичный нуль, или напряжение НИЗКОГО уровня, в точках А, В или F соответствует потенциалу земли (точнее, близко к потенциалу земли, т.е. к нулю). Мы применяем здесь так называемую “положительную логику”, поскольку для получения двоичной единицы используется положительное напряжение +5В. При работе с цифровыми электронными устройствами мы чаще всего будем иметь дело с “положительной логикой”.

4.3 Дизъюнктор (логический элемент ИЛИ)

Дизъюнктор реализует логическую функцию

.(4.3)

Ниже показаны его обозначение на электрических схемах (рисунок 4.4,а), принципиальная схема (рисунок 4.4, б) и таблица истинности (таблица 4.3).

А Б

Рисунок 4.4

Таблица 4.3

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

4.4 Повторитель

Реализует логическую функцию

.(4.4)

Его обозначение на электрических схемах показано на рисунке 4.5

Рисунок 4.5

Повторитель не выполняет никаких логических преобразований и используется для повышения нагрузочной способности отдельных выходов ИМС или как элемент задержки, равной времени распространения сигнала через него.

4.5 И-НЕ

Элемент И - НЕ реализует логическую функцию

.(4.5)

Ниже показаны его обозначение на электрических схемах (рисунок 4.6,а), функциональная схема (рисунок 4.6, б) и таблица истинности (таблица 4.4).

Таблица 4.4

А Б

Рисунок 4.6

4.6 ИЛИ-НЕ

Элемент ИЛИ- НЕ реализует логическую функцию

.(4.6)

Ниже показаны его обозначение на электрических схемах (рисунок 4.7,а), функциональная схема (рисунок 4.7, б) и таблица истинности (таблица 4.5).

Таблица 4.5

Рисунок 4.7

4.7 Исключающее ИЛИ

Реализует логическую функцию

.(4.7)

Ниже показаны его обозначение на электрических схемах (рисунок 4.8) и таблица истинности (таблица 4.6).

Рисунок 4.8

Таблица 4.6

Элемент называется исключающее ИЛИ, т.к. его таблица истинности совпадает с таблицей истинности элемента ИЛИ первыми тремя строчками. В четвертой строке элемента ИЛИ, F=1 , а элемента исключающее ИЛИ - нуль.

Ниже приведена таблица истинности ПФ “исключающее ИЛИ” для 3-х логических переменных (таблица 4.6.1).

Таблица 4.6.1

4.8 Сложение по модулю два (нечетность)

Элемент реализует логическую функцию

.(4.8)

Ниже показаны его обозначение на электрических схемах (рисунок 4.9) и таблица истинности (таблица 4.7).

Таблица 4.7

Рисунок 4.9

Элемент суммирует значения переменных по модулю два (символ (псевдоплюс) означает mod2: 0 + 0 = 0; 1 + 1 = 0; 1 + 0 = 1; 0 + 1 = 1).

Если при суммировании число единиц нечетно, то функция равна 1, в противном случае - F=0.

4.9 Сложение по модулю два с отрицанием (четность)

Элемент реализует логическую функцию

.(4.9)

Ниже показаны его обозначение на электрических схемах (рисунок 4.10) и таблица истинности (таблица 4.8).

Рисунок 4.10

Элемент формирует сумму по модулю два, которая затем инвертируется на выходе. Если при суммировании число единиц четно, то функция равна 1, в противном случае - F = 0.

Таблица 4.8

4.10 Эквивалентность

Элемент реализует логическую функцию

.(4.10)

Ниже показаны его обозначение на электрических схемах (рисунок 4.11) и таблица истинности (таблица 4.9).

Рисунок 4.11

Таблица 4.9

Функция равна единице, когда все переменные одинаковы (равны единице или нулю). В противном случае - F = 0.

4.11 Неэквивалентность

Элемент реализует логическую функцию

.(4.11)

Ниже показаны его обозначение на электрических схемах (рисунок 4.12) и таблица истинности (таблица 4.10).

Рисунок 4.12

Таблица 4.10

Функция равна единице, когда переменные неодинаковы. В противном случае - F=0.

Если число логических переменных равно двум, то логическая функция и элемент “неэквивалентность ”совпадают с элементами “сумма по модулю два” и “исключающее ИЛИ” (таблицы 4.6, 4.7). Т. е., если Nпер=2, то

(4.11.1)

4.12 И-ИЛИ-НЕ

Элемент реализует более сложную логическую функцию, булево выражение которой имеет вид

.(4.12)

Ниже показаны его обозначение на электрических схемах (рисунок 4.13) и таблица истинности (таблица 4.11).