книги из ГПНТБ / Караваев, Н. И. Электронные цифровые вычислительные машины и программирование учеб. пособие
.pdf- 50-
Таблица 1.7
Отрицание равнозначности
А |
Б |
Р» А<\ЬВ |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
Следствия: |
АооО |
- А; |
|
A f « l |
= А; |
|
АооА |
= 0; |
|
ДоЗ А = 1 . |
|
Из табл. 1.6 |
и 1.7 следует, что |
|
|
АсЗВ • ( А 0 0 |
В). |
Основные законы алгебры логики
Для установления эквивалентности различных логических выражений в алгебре логики используются следующие основные законы /табл. 1.8/.
|
|
|
Таблица 1.8 |
т |
Наименование |
Для логического |
Для логического |
пп |
закона |
сложения |
умножения |
1 |
Переместительный |
А + В = 3 + А |
АВ = ВА |
2 |
Сочетательный |
А+/В-»-С/*/А+В/+С |
А /ВС/* /АВ/ С |
3 |
Распределительный /А+В/С-АС+ВС |
АВ+С=/А+С//В+С/ |
|
4 |
Инверсии |
А + В = АВ |
АВ = А + В |
Законы переместительный, сочетательный и распредели тельный /для сложения/ имеют место и в обычной алгебре. Распределительный закон для умножения и закон инверсииспециальные законы алгебры логики. Справедливость основ ных законов алгебры логики может быть установлена с по-
- 51 -
мощью таблиц истинности, а качестве примере приведем таб лицу истинности /табл. 1.9/ для закона инверсии.
Таблица 1.9
|
|
|
|
|
|
|
|
|
_ |
А |
В |
А |
В |
А+В |
А+В |
АВ |
АВ |
АВ |
А+В |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
Аналогично могут быть проверены и другие законы ал |
|||||||||
гебры |
логики. |
|
|
|
|
|
|
|
Двоичные функции
При рассмотрении логических связей было установлено, что значение истинности простого высказывания может прини мать значения 0 и 1. Следовательно, простое высказывание можно рассматривать как двоичную переменную. Сложное выска зывание можно рассматривать как двоичную функцию, так как значение истинности его может принимать также только два значения: 0 и 1.
В общем случае переменная величина X, которая может принимать только два значения: 0 и 1, называется двоичной переменной.
Функция двоичных переменных |
|
|
||
5" |
/X j « х 2 |
* а |
|
|
которая может принимать два значения: 0 |
и |
1.называется |
||
двоичной /переключательной/ |
функцией. |
|
|
|
Рассмотренные |
выше логические связи |
являются частными |
||
случаями двоичных |
функций. Если имеется |
П. |
двоичных пере |
менных, то количество различных функций, которые могут быть получены путем комбинации этих переменных, будет рав но
|
|
- |
52 - |
Например, |
при |
П = 1 количество двоичных функций бу |
|
дет 4, а при |
П - |
2-16. |
|
В математической логике |
функции одного и двух перемен |
ных имеют весьма большое значение. Это значение состоит в том, что из них может быть построена любая двоичная функ ция. Средством такого построения является суперпозиция двоичных функций, т . е . подстановка одних двоичных функций вместо аргументов в другие двоичные функции. Возможность такой подстановки обусловлена тем, что области значений двоичных функций и области значений двоичных переменных совпадают между собой.
Двоичные функции одной и двух двоичных переменных пред
ставлены в |
табл. |
1.10 |
и 1.11. |
Таблица 1.10. |
|
|
|
|
|
||
|
Двоичные |
функции одной |
переменной |
||
X |
0 |
1 |
Условное |
|
|
обозначение |
Название |
функции |
|||
|
|
|
функции |
||
|
|
|
|
|
|
Ш) |
0 |
0 |
0 |
Константа |
нуль |
|
0 |
1 |
X |
Переменная X |
|
Ъ(Х) |
1 |
0 |
X |
Отрицание |
|
Ь(Х) |
1 |
1 |
1 |
Константа |
единица |
- аз -
Таблица 1.11
Двоичные функции двух переменных
|
0 |
0 |
1 |
1 |
Условное |
|
обозна |
||||
|
0 |
1 |
0 |
1 |
чение |
|
функции |
||||
|
0 |
0 |
0 |
0 |
0 |
i,(x,,x2 ) |
0 |
0 |
0 |
1 |
X<AXi |
1г(ХьХ2) |
0 |
0 |
1 |
0 |
Х,Д Хг |
5s (Xi,Xi) |
0 |
0 |
1 |
1 |
|
ш м |
0 |
1 |
0 |
0 |
Х2ЛХ< |
5s(x„x*) |
0 |
1 |
0 |
1 |
ч |
1в(Х,,Х.) |
0 |
1 |
1 |
0 |
|
Ш . , Х 2 ) 0 |
1 |
1 |
1 |
Хн v x 2 |
|
5»(х,,хо |
1 |
0 |
0 |
0 |
Х< » X* |
fc(Xi,X.) |
1 |
0 |
0 |
1 |
Х,~ Х2 |
^(о( ХьХг) |
1 |
0 |
1 |
0 |
Хг |
(ХьХа) |
1 |
0 |
1 |
1 |
Xi "*~" Хг |
iiz(Xt,Xa) |
1 |
1 |
0 |
0 |
X, |
"fuC Xf >Ха) |
1 |
1 |
0 |
1 |
X i — X* |
1«(X„X«) |
1 |
1 |
1 |
0 |
Xi/Xe |
t«(x«,xO |
1 |
1 |
1 |
1 |
I |
|
|
|
— — |
• |
|
Название функции
Константа нуль
Логическое произве дение "И"
Операция запрета XV, Переменная Х-j Операция запрета Переменная Х^
Отрицание равнознач ности
Логическое сложение "МИ"
Операция "Г" Равнозначность Отрицание "НЕ" Обратная импликация Отрицание Х1 "hE" Импликация Операция Шеффера
. Константа единица
Минимизация двоичных функций
Двоичная функция, заданная в первоначальном виде, не всегда бывает удобна для схемной реализации. При решении задачи синтеза схем двоичная функция должна быть представ лена в такой форме, которая является наиболее экономичной - для построения сложных схем. Кроме того, при синтезе схем необходимо решить вопрос о выборе системы двоичных функций.
Решение этого вопроса с технической точки зрения эквива лентно выбору типовых логических элементов, из которых могут быть построены сложные схемы цифровых вычислитель ных машин. Следовательно, логические элементы необходимо выбрать так, чтобы из этих элементов молно было построить любую сколь-угодно сложную схему. Это требование равно сильно условию реализации любой логической формулы с по мощью определенных двоичных функций.
Система двоичных функций называется функционально пол
ной, если с |
помощью |
функций, входящих в эту систему, |
мож |
но получить |
сколь-угодно сложную двоичную функцию. |
|
|
Из числа |
функций |
одной и двух двоичных переменных |
мо |
гут быть выбраны несколько функционально полных систем, однако наибольшее распространение при синтезе схем ЭЦВМ получила основная функционально полная система, включаю щая функции "И", "ИЛИ" и "НЕ". Элементы, реализующие эти логические операции, называются основными логическими эле ментами.
Используя функции "И", "ИЛИ" и "НЕ", может быть выра жена любая двоичная функция. Наиболее просто решается эта задача, если функция задана в виде таблицы /таблицы истин ности/.
Пусть двоичная |
функция задана |
в виде |
таблицы |
1.12. |
|
|
|
|
|
Таблица |
1.12 |
Таблица |
задания функции |
|
|
||
строки |
h |
ч |
Ч |
|
|
0 |
0 |
0 |
0 |
0 |
|
1 |
0 |
0 |
1 |
1 |
|
2 |
0 |
1 |
0 |
1 |
|
3 |
0 |
1 |
1 |
0 |
|
4 |
1 |
0 |
0 |
0 |
|
5 |
1 |
0 |
1 |
1 |
|
6 |
1 |
1 |
0 |
0 |
|
7 |
1 |
1 |
1 |
1 |
|
-bo -
Втаблице 1.12 ./кузины значения переменных и соответ ствующие им значения функции. Колонка таблицы "W строки"
введена только для простоты изложения материала; практи чески она не используется и при табличном задании функции этой колонки моает не быть.
Для записи функции в виде' логического выражения может быть использовано одно из двух правил: правило записи функ ции по единицам или правило записи функции по нулям.
Правило записи функции по единицам можно сформулиро вать следующим образом: для каждой строки таблицы, в ко торой значение функции равно 1, составляется произведение переменных /если значение переменной равно нулю, то пере менная берется с отрицанием/; полученные произведения скла дываются.
Врассматриваемом примере значение функции равно 1 в строках 1, 2, 5, 7. Составив произведение переменных для этих строк и суммируя их, получим
Хг,Хз) = Х<Х2Хз+Х<Х2Хз+ Х1Х2Х3 +• Х<Х2Хз .
Для записи функции по нулям необходимо для каждой строки таблицы, в которой значение функции равно 0, произ вести суммирование переменных /если значение переменной равно 1, то переменная берется с отрицанием/; полученные
суммы необходимо |
перемножить. |
|
|
|
В табл. |
1.12 |
значение функции равно 0 |
в строках 0, |
3, |
4 , 6 . Составляя |
суммы переменных для этих |
строк и перемно |
||
жив их, получим |
|
|
|
|
j(Х<,Х2,Х3) |
= (Х,+Х2+ X,) (Х,+ Х > X,)СХ, + Х2 + ХзК Х<+ Х2-ь Х 3 |
) . |
Так, например, используя правило записи функции по единицам, операция запрета, равнозначность и отрицание равнозначности могут быть выражены через операции "И", "ИЛИ" и "НЕ" следующим образом /табл.1.11/:
fz СХ<, Х2 ) = Х<Хг. |
/операция запрета X V ; |
1б (ХьХг.) = Х( Хг + Xi Хг |
/отрицание равнозначности/ ; |
% ( X < , X 2 ) = XiX2 + Х Д г |
/равнозначность/. |
- Ь6 -
Любая двоичная функция, выраженная через логические операции "И", "ИЛИ" и "НЕ", записывается в виде последова тельности букв, соединенных между собой знаками произведе ния или сложения. Очевидно, что чем меньше букв входит в эту формулу, тем меньше потребуется операций, а следова тельно, и элементов для реализации данной двоичной функции. Поэтому задача минимизации двоичных -функций сводится к отысканию таких форм, которые содержат минимальное коли чество букв.
Нахождение минимальной формы может быть проведено раз личными методами. Одним из них является аналитический ме тод. Сущность этого метода заключается в том, что двоичную функцию необходимо выразить через логические операции "И", "ИЛИ" и "НЕ" и, используя основные законы алгебры логики и следствия из таблиц основных двоичных функций, привести к
минимальной |
форме. |
|
|
|
|||
|
При аналитическом методе минимизации двоичных функций |
||||||
очень полезными могут |
оказаться следующие |
соотношения: |
|||||
1. |
X.J + X.jXg - Xj |
|
/операция |
поглощения/; |
|||
2. |
Xt |
( X t |
+ |
Xg) - Х 1 |
; |
|
|
3. |
Cxt |
+ Xg) (X, + X^) = X1 ; |
|
||||
4. |
X1 |
+ X^Xg |
- Xt + |
Xg |
; |
|
|
5. |
x t |
+JC1 X2 |
« x j + |
Xg |
; |
/ l l 9 / |
|
6. |
Xj ( X 1 |
+ Xg) - XtXg ; |
|
||||
7. |
x, ( x t |
+ X 2 ) - x 1 x 2 ; |
|
||||
8. |
X^Xg + XjXg = X-j |
|
/операция |
склеивания/. |
Задача нахождения минимальных форм является достаточ но трудной и значительных результатов можно достичь толь ко в том случае, если будет проявлена большая изобретатель ность.
- 57 - Синтез сложных логических схем
Слоеными логическими схемами будем называть схемы, сос тоящие из элементов, реализующих двоичные функции функцио нально полной системы.
Общий порядок синтеза сложных логических схем может быть следующим:
1. Определить условия работы схемы. Условия ре боты схемы могут быть сформулированы словесно или заданы в виде таблицы двоичной функции /таблицы истинности/.
2. Записать логическое выражение, описывающее работу дан ной схемы.
3.Минимизировать полученное логическое выражение.
4. Построить функциональную схему с указанием основных элементов и связей между ними.
5.На основе функциональной схемы разработать принципиаль ную схему.
Пример.
Минимизировать двоичную функцию
i ( X b X 2 , X 3 ) =X< X i X3 + X 1 X 2 X3+X 1 x 7 x 3 |
/ 1 . 1 0 / |
и построить функциональную схему для ее реализации. Используя основные законы алгебры логики, функция
/ 1 . 1 0 / может быть преобразована следующим образом:
Х( Х2Х3 + Х4Х2 X j +• Х{ ХгХз= Х< Х2Х3 +Х<ХгХз +• Х<СХг + Хз) =
= Х,Х 2 Х 3 + Х 1 Х г Х 3 + Х < Х 2 + Х 4 Х а - Х < ( Х 2 Х 3 + Х 2 ) + Х3 (Х,Х г +%0 .
Применяя соотношения / 1 . 8 / , полученное логическое выражение можно преобразовать к минимальной форме:
Х , ( Х 2 Х з + Х г ) + Х з ( Х 1 Х 2 + Х , ) = Х1СХз + Х г ) + Х 3 С Х 2 + Х < ) =
— Х<Хз+ Х | Х г + Х г Х 3 + X < X j |
=Xi+ X<Xfc •'-ХгХз = Х< + |
Х 2 Х 3 |
Таким образом, после минимизации функция |
/ 1 . 1 0 / |
|
примет вид |
|
|
f ( Х Ь Х 2 , Х 3 ) |
=Х< + X j . X , . |
/ 1 . 1 1 / |
|
|
|
|
- 58 - |
Функциональная схема, |
реализующая двоичную функцию |
|||
/ 1 . 1 1 / , изображена |
на |
рис. |
1.3. Построение схемы следует |
|
начинать от |
ее выхода |
к входам , последовательно ввода |
||
х, |
х2 |
х3 |
|
|
Рис. 1.3. Функциональная схема устройства для реализации функции / 1 . 1 1 /
необходимые логические элементы. Условные обозначения о с новных логических элементов приведены в § 2.2 /рис . 2 . б/ .
Для построения принципиальной схемы устройства необ ходимо знать принципиальные схемы логических элементов. Принципиальные схемы основных элементов, используемых для построения устройств ЭЦВМ, рассматриваются в последую щих главах настоящего пособия.
Г Л А В А П ОСНОВНЫЕ ЭЛЕМЕНТЫ И УЗЛЫ ЭЛЕКТРОННЫХ ЦИФРОВЫХ
ВЫЧИСЛИТЕЛЬНЫХ МАШИН |
|
|
В настоящей главе рассматриваются |
отдельные |
элементы |
и схемы, имеющие широкое применение в |
ЭЦВМ. К ним |
относят |
ся основные логические схемы, триггеры, регистры, |
счетчи |
|
ки, дешифраторы. |
|
|
Для построения этих схем используются электронные лам |
пы, транзисторы, диоды, туннельные диоды, магнитные сердеч
ники с прямоугольной /непрямоугольной/ петлей |
гистерезиса |
с одним и более отверстиями и другие приборы, |
которые в |
сочетании с другими радиотехническими деталями образуют схемы, имеющие два устойчивых состояния.
Такие схемы называются двухпозиционными элементами.
§ 2 . 1 . ДВУХП03ИЦИ0ННЫЕ ЭЛЕМЕНТЫ
Электронные вычислительные машины производят операции с величинами, представляемыми в цифровой форме. Вследствие этого числа необходимо изображать электрическими сигналами, характеризуемыми определенными параметрами. В общем случае число представляет собой совокупность нескольких разрядов, количество которых обычно является постоянным для данной машины.
Каждый разряд числа должен представляться схемой, ко личество устойчивых состояний которой должно соответство вать основанию системы счисления, принятой для представле ния чисел.
Например, для представления одного разряда числа, представленного в десятичной и двоичной системах счисления, необходимы схемы с десятью и двумя различными устойчивыми