ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 15.06.2025
Просмотров: 4498
Скачиваний: 2
Глава 3. Переключательная алгебра
макстермов определяется числом входных векторов, А^ЛЯ которых функция принимает значение 0. В представленном случае KKNF и KDNF одинаковы по затратам на их формирование.
Для работы с нормальными формами важным является обобще ние законов Де-Моргана, так называемое, «правило Шеннона», ко
торое гласит: |
|
Для любой |
булевой функции |
у = /(xo,:ri,...,x^,A,V,4+>,0,l,0) |
|
существует |
инвертированная функция |
Это означает, что все переменные должны быть проинвертированны, а все операции должны быть заменены на дуальные им. Например, пусть дана функция:
у = {х2У ххУ -i^o) л {х2 V -ij;i V^o).
Тогда имеем инвертированную функцию следующего вида:
-1 у = (-1 :Г2 Л -1 X i Л жо) V (-13^2 Л XI Л -п XQ).
В соответствии с этим правилом KKNF можно сформировать и тогда, когда KDNF определяет инверсную функцию. Для приведен ного выше примера получаем:
-^y={-^ Х2-^ ^Xl ^ Хо) V (-1 Х2 Л XI Л ^ Хо) V
V (х2 л -> X I л -1 хо) V (х2 л Xi л хо)
Затем применяет правило Шеннона и напрямую получает KKNF:
у = (Х2 V X I |
V -п Хо) л |
(Х2 V -^ X I |
V Хо) л |
л (-1Х2 |
V X I V Хо) |
л (-1Х2 V |
-1 x i V -1 Хо) |
3.7.Минимизация с помощью переключательной алгебры
Нормальные формы KKNF и KDNF подходят главным образом для составления булевых уравнений. Но с точки зрения затрат по ко личеству вентилей эти формы не идеальны. Для упрощения очень
3.8. Способ упрощенной записи 45
хорошо подходит уравнение тождества, которое может быть выве дено следующим образом:
{XQ А xi) V (хо Л -I Xi) = жо Л (:ri V -• ^i) |
= |
== Хо Л 1 |
|
= жо |
|
Следовательно, справедливо: |
|
{XQ A^i) V {хо Л --д:!) = Хо |
(3.34) |
В соответствии с правилами дуализма: |
|
(хо V xi) А {XQ V -> xi) — XQ |
(3.35) |
Пример. Пусть необходимо минимизировать следующую функпдю: |
|
у — {XQ А -^ xi А Х2 А хз) V (хо Л XI Л а;2 Л жз) V (а;о Л x i |
Л -> 0^2 Л хз) V |
V (-1 Хо Л ^1 Л Ж2 Л хз) V (-> Хо Л XI Л -> Х2 Л хз) |
|
Мы видим, что могут быть объединены, например, термы 1 и 2, 2 и 3, а также 4 и 5. Сначала объединяют два первых терма, сохранив вто рой, так как он еще понадобится р^ля объединения с третьим термом:
у = (хо Л Х2 Л Хз) V (хо Л x i Л Х2 Л Хз) V (хо Л x i Л -1Х2 Л Хз) V
V (-' Хо Л XI Л Х2 Л Хз) V (-1 Хо Л X i Л -п Х2 Л Хз)
у — (хо л Х2 л Хз) V (хо л xi л Хз) V (-• Хо л xi л хз)
Могут быть объединены также оба последних терма:
у = (хо Л Х2 Л Хз) V ( x i л Хз)
Это представление является минимальным. Для реализации тре буются два вентиля AND и один вентиль OR. Графический метод минимизации представлен в главе 6.
3.8. Способ упрощенной записи
Сложные функции не всегда легко прочитать:
/ ( х з , Х 2 , х ь Х о ) = (-^хо A - nX2)V(x2 Л Х3) V (хо л-1X1 A x 2 ) V ( x i Л х з )
(3.36)
Глава 3. Переключательная алгебра
Для упрощения записи, который можно опустить символ конъюнк ции и скобки. При этом принимается условие, что сначала формиру ется конъюнкция, а в заключении дизъюнкция. На основании этого можно записать уравнение (3.36) следующим образом:
/ (Жз, Х2, XI, XQ) = ^ XQ-^ Х2 V Х2Хз V XQ-^ 0:1X2 V ^10:3 |
(3.37) |
3.9.Символическое обозначение логических элементов
Применяемые символы логических элементов цифровой техники, при веденные в данной книге, соответствуют системе DIN 40900. В соот ветствии с этой системой предписаний, вначале закругленные сим волы логических элементов были заменены на новые прямоуголь ные, так как существовала уверенность в том, что закругленное схемное обозначение не может быть нарисовано с использованием компьютера. Между тем в предписание была введена индексация зависимостей, которая позволяла считывать со структурной схемы поведение цифровых схем. Ниже дано короткое введение в применя емую систематику. В отдельных главах применяемые символы бу дут поясняться при их появлении. В приложении будет приведена объединенная таблица.
3.9.1. Основы структуры символов
Символы имеют обрамление, в котором в верхней части находится знак, показывающий основную функцию схемы (рис. 3.4). В рассмо тренных выше символах ими были знаки &, > 1, = 1, 1. В приложе нии можно найти все возможные символы, сведенные в таблицу.
символ, описывающий схему
входы |
выходы |
символ, описывающий входы и выходы Рис . 3.4. Обобщенная структура символа логического элемента.
3.9. Символическое |
обозначение логических |
элементов |
Как правило, входы находятся слева, выходы размещены справа. При отклонении от правил следует обозначать направление сигналов стрелками.
На рис. 3.4 обозначены также места, в которые с помощью допол нительных обозначений могут быть введены более точные данные о входах и выходах. Внутри обрамления благодаря этому можно за писать замечания о внутреннем логическом состоянии схемы. Вне обрамления стоят такие обозначения как инверсионная петля логи ческих состояний, инверсионный треугольник д^ля уровней (уровни рассматриваются в следующей главе 4), или замечания о виде сиг налов. Таблицы возможных символов приведены в приложении.
Если схема содержит общий управляющий блок, то это обозна чается как на рис. 3.5 а. Общий выходной блок обозначается двумя двойными линиями, как представлено на рис. 3.5 Ь.
общий управляющий блок
-Уо
X |
-Уо |
- Ух |
-У1 |
г |
общий входной блок для |
|
группы одинаковых элементов |
Рис . 3.5. Обобщенная структура символических обозначений логических элементов.
3.9.2. Индексация зависимости
При индексации зависимости с помощью одной буквы описывается влияние одного из входов (или выходов) на другие входы или выхо ды. Эта буква определяет влияние более строго. За буквой следует идентификационное число. То же самое число находим и у входов и выходов, на которые оказывается влияние. Точнее все это разъяс няется на следующих примерах.
3.9.3. Зависимость вида И (G)
Буква G, представленная на одном из входов, может означать за висимость, соответствующая логической функции И. На рис. 3.6 на входе X для более точного описания проставлено обозначение G1. Поскольку вход XQ обозначен через 1, то он оказывается связанным
Глава 3. Переключательная |
алгебра |
с входом ^1, логической функцией И. Вход Х2 обозначен через -il. Исходя из этого, он оказывается связанным функцией И с входом XI в случае выполнения над последним операции НЕ. Индекс отно сится к внутренним состояниям. Возможные инверсионные петли будут обсуждены позже. Они определяют внешнее поведение.
^ 0
"М&1
Р и с . 3.6. Зависимость по типу И (G).
Как показано на рис. 3.7, индексация зависимости может быть применена и ^\ля выходов.
1 |
G1 |
-Уо |
'&\ |
уо |
|
а) |
г |
||||
Ь) |
|||||
1 |
G1 |
-Уо |
& |
Уо |
|
• |
^ |
Рис . 3.7. Зависимость по типу И (G), применяемая на выходе, а) без ин версии; б) с инверсией выхода.
Если два входа имеют одинаковые обозначения (рис. 3.8), то эти входы связаны посредством логического ИЛИ.
'о |
1 |
& |
'l
"2
G1 |
>1 |
G1
Рис. 3.8. Зависимость по типу И (G) для двух входов, которые обозначены
спомощью 01.
3.9.4.Зависимость по типу ИЛИ (V)
Если отмеченный индексом V^ вход или выход имеет внутреннее состояние 1, то в этом случае все входы и выходы, обозначенные числом п, имеют значение 1. Если обозначенный через V^^ входной
3.9. Символическое обозначение логических элементов
или выходной сигнал имеет значение О, то в этом случае сигналы на подвергающихся влиянию входах и выходах имеют нормально определенные значения. Два примера приведены на рис. 3.9.
'0 |
VI |
1 |
•Уо |
>1 |
'Уо |
а) |
|||||
VI |
.Уо |
-Уо |
|||
>1 |
•У\ |
||||
1 |
|||||
Ух |
Ь) |
||||
Рис. 3.9. Зависимость по типу ИЛИ (V).
3.9.5. Зависимость по типу EXOR (N).
Обозначенные через N^^ входы и выходы состоят с подвергаемы ми их влиянию входами и выходами в отношениях, определяемых функцией EXOR. Если на помеченном N^ входе или выходе 1, то на обозначенных через п входах и выходах сигнал инвертируется. В прочих случаях они не подвергаются влиянию.
Уо |
||
N1 |
Уо |
= 1 •У\ |
У\
Рис. 3.10. Зависимость по типу EXOR (N).
3.9.6. Образующая соединение зависимость (Z)
Вход или выход, индексированный буквами Ъ^-, должен оказаться связанным со всеми входами и выходами, обозначенными через п (рис. 3.11).
3.9.7. Зависимость с передачей (X)
Если вход или выход, индексированный буквами Х^, имеет значе ние 1, то все входы и выходы, обозначенные через п, оказываются связанными двунаправлено (рис. 3.12). В других случаях обозначен ные через п входы и выходы изолированны друг от друга.