Вычислительные машины
1) входной алфавит слов X;
2) выходной алфавит слов Y;
3) алфавит внутренних состояний Q;
4) начальное состояние автомата q 40 0;
5) функция переходов A(q,x);
6) функция выходов B(q,x).
2Функция переходов 0 определяет зависимость состояния автомата
q(t+1) в момент времени t+1 от состояния автомата q(t) и входного
сигнала x(t) в момент t.
2Функция выходов 0 определяет зависимость выходного сигнала
y(t) от состояния автомата q(t) и входного сигнала x(t).
Автомат, описываемый системой уравнений
7(
72 0 q(t+1) = A{q(t),x(t)},
7*
72 0 y(t) = B{q(t),x(t)}
79
называется 2автоматом Мили 0.
Автомат, выходной сигнал которого y(t) в тактовый момент t
зависит только от состояния автомата q(t) и не зависит от входно-
го сигнала, называется 2 автоматом Мура 0 и описывается системой:
7(
72 0 q(t+1) = A{q(t),x(t)},
7*
72 0 y(t) = B{q(t)}.
79
ПЕРВЫЙ СЕМЕСТР
ЛЕКЦИЯ N 5
2ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ПОСТРОЕНИЯ УЗЛОВ ЭВМ
Если для двух любых состояний q 4i 0 и q 4j 0 автомата имеется вход-
ной сигнал, переводящий автомат из состояния q 4i 0 в q 4j 0, то такой
автомат называется автоматом с 2полной системой переходов 0. Автомат
Мура имеет 2полную систему выходов 0, если выходные сигналы различны
для всех его состояний.
При построении схем ЭВМ в качестве элементов памяти исполь-
зуются элементарные автоматы. 2Элементарный автомат 0 - это автомат
Мура с двумя внутренними состояниями, двумя различными выходными
сигналами и несколькими входами, обладающий полными системами пе-
реходов и выходов.
2ТЕОРИЯ БУЛЕВЫХ ФУНКЦИЙ
Булевыми функциями называют переключательные функции, кото-
рые так же, как и их аргументы, принимают только два значения:
0 и 1.
Булевы функции могут быть заданы в виде формул или таблиц.
Формулы позволяют представлять функции в более компактном виде,
чем таблицы, так как таблица для функции от n аргументов будет
содержать 2 5n 0 строк (или столбцов, в зависимости от формы табли-
цы). С другой стороны, таблицы дают наглядное представление для
простых функций.
Приведем в качестве примера наиболее часто встречающиеся
функции от одной и двух переменных:
1) Переменная x:
f(x) = x
2) Инверсия переменной x (функция НЕ):
4_
f(x) = x
3) Константа нуля:
f(x) = 0
4) Константа единицы:
f(x) = 1
.
- 2 -
5) Дизъюнкция (функция ИЛИ):
f(x 41 0,x 42 0) = x 41 0 V x 42
Может встречаться другое обозначение: f(x 41 0,x 42 0) = x 41 0 | x 42 0.
Таблица истинности (соответствия) для этой функции имеет вид:
------T-----T---------¬
¦ x 41 0 ¦ x 42 0 ¦ x 41 0 V x 42 0 ¦
+-----+-----+---------+
¦ 0 ¦ 0 ¦ 0 ¦
¦ 0 ¦ 1 ¦ 1 ¦
¦ 1 ¦ 0 ¦ 1 ¦
¦ 1 ¦ 1 ¦ 1 ¦
L-----+-----+----------
6) Конъюнкция (функция И):
f(x 41 0,x 42 0) = x 41 0 5. 0 x 42
Может встречаться другое обозначение: f(x 41 0,x 42 0) = x 41 0 & x 42 0.
Таблица истинности для этой функции имеет вид:
------T-----T---------¬
¦ x 41 0 ¦ x 42 0 ¦ x 41 0 5. 0 x 42 0 ¦
+-----+-----+---------+
¦ 0 ¦ 0 ¦ 0 ¦
¦ 0 ¦ 1 ¦ 0 ¦
¦ 1 ¦ 0 ¦ 0 ¦
¦ 1 ¦ 1 ¦ 1 ¦
L-----+-----+----------
7) Функция ИЛИ-НЕ:
4_______
f(x 41 0,x 42 0) = x 41 0 V x 42
Таблица истинности для этой функции имеет вид:
------T-----T---------¬
¦ x 41 0 ¦ x 42 0 ¦ x 41 0 V x 42 0 ¦
+-----+-----+---------+
¦ 0 ¦ 0 ¦ 1 ¦
¦ 0 ¦ 1 ¦ 0 ¦
¦ 1 ¦ 0 ¦ 0 ¦
¦ 1 ¦ 1 ¦ 0 ¦
L-----+-----+----------
.
- 3 -
8) Функция И-НЕ:
4_______
f(x 41 0,x 42 0) = x 41 0 5. 0 x 42
Таблица истинности для этой функции имеет вид:
------T-----T---------¬
¦ x 41 0 ¦ x 42 0 ¦ x 41 0 V x 42 0 ¦
+-----+-----+---------+
¦ 0 ¦ 0 ¦ 0 ¦
¦ 0 ¦ 1 ¦ 1 ¦
¦ 1 ¦ 0 ¦ 1 ¦
¦ 1 ¦ 1 ¦ 1 ¦
L-----+-----+----------
9) Функция ИСКЛЮЧАЮЩЕЕ ИЛИ (сумма по модулю 2):
f(x 41 0,x 42 0) = mod2(x 41 0,x 42 0)
Таблица истинности для этой функции имеет вид:
------T-----T-------------¬
¦ x 41 0 ¦ x 42 0 ¦ mod2(x1,x2) ¦
+-----+-----+-------------+
¦ 0 ¦ 0 ¦ 0 ¦
¦ 0 ¦ 1 ¦ 1 ¦
¦ 1 ¦ 0 ¦ 1 ¦
¦ 1 ¦ 1 ¦ 0 ¦
L-----+-----+--------------
2Аксиомы алгебры логики
В алгебре логики определено отношение эквивалентности (=) и
три операции: дизъюнкция, конъюнкция и отрицание.
Отношение эквивалентности удовлетворяет следующим свойствам:
x=x - рефлексивность; если x=y, то y=x - симметричность; если x=y
и y=z, то x=z - транзитивность. Из отношения эквивалентности сле-
дует 2 принцип подстановки 0: если x=y, то в любой формуле, содержа-
щей x, вместо x можно подставить y, и будет получена эквивалент-
ная формула.
Алгебра логики определяется следующей системой аксиом:
x = 0, если x 7- 0 1 7 )
78 0 (1)
x = 1, если x 7- 0 0 7 0
1 V 1 = 1 7 )
78 0 (2)
0 5 . 0 0 = 0 7 0
- 4 -
0 V 0 = 0 7 )
78 0 (3)
1 5. 0 1 = 1 7 0
0 V 1 = 1 V 0 = 1 7 )
78 0 (4)
0 5 . 0 1 = 1 5 . 00 = 0 7 0
4_
0 = 1 7 )
4_ 0 78 0 (5)
1 = 0 7 0
Аксиома (1) утверждает, что в алгебре логики рассматриваются
только двоичные переменные, аксиомы (2)-(4) определяют операции
конъюнкции и дизъюнкции, а аксиома 5 - операцию отрицания.
Если в аксиомах (2)-(5), заданных парами утверждений, произ-
вести взаимную замену операций дизъюнкции и конъюнкции, а также
элементов 0 и 1, то из одного утверждения пары будет получено
другое. Это свойство называется принципом двойственности.
2Теоремы алгебры логики
С помощью аксиом алгебры логики можно доказать целый ряд те-
орем и тождеств. Одним из эффективных методов доказательства тео-
рем является 2 метод перебора 0 всех значений переменных: если теоре-
ма истинна, то при подстановке любых значений переменных в обе
части выражения, формулирующего утверждение теоремы, должно полу-
читься тождество.
Методом перебора можно убедиться в справедливости следующих
теорем:
идемпотентные законы
x V x = x 7 )
78
x 5. 0 x = x 7 0
коммутативные законы
x V y = y V x 7 )
78
x 5. 0 y = y 5. 0 x 7 0
ассоциативные законы
(x V y) V z = x V (y V z) 7 )
78
(x 5. 0 y) 5. 0 z = x 5. 0 (y 5. 0 z) 7 0
.
- 5 -
дистрибутивные законы
x 5. 0 (y V z) = x 5. 0 y V x 5. 0 z 7 )
78
x V y 5. 0 z = (x V y) 5. 0(x V z) 7 0
законы отрицания 4 _
x V x = 1 7 )
4_ 0 78
x 5. 0 x = 0 7 0
0 V x = x 7 )
78
1 5. 0 x = x 7 0
1 V x = 1 7 )
78
0 5. 0 x = 0 7 0
законы двойственности (теоремы де Моргана)
4_____ _ _
x V y = x 5. 0y 7 )
4_____ 0 4_ 0 4_ 0 78
x 5. 0 y = x V y 7 0
закон двойного отрицания 4 0 4 _____
7( 0 4_ 7 )
72 0 x 7 2 0 = x
79 0
законы поглощения
x V x 5. 0 y = x 7 )
78
x 5. 0(x V y) = x 7 0
операции склеивания 4 _
x 5. 0 y V x 5. 0 y = x 7 0 7)
4_ 0 78
(x V y) 5. 0(x V y) = 7 0x 70
операции обобщенного склеивания
4_ _
x 5. 0y V x 5. 0z V y 5. 0z = x 5. 0y V x 5. 0z 5 7)
4_ 0 5 4_ 5 0 78
(x V y) 5. 0(x V z) 5. 0(y V z) = 7 0(x V y) 5. 0(x V z) 70
4_
x V x 5. 0 y = x V y 7 )
4_ 0 78
x 5. 0(x V y) = x 7 5. 0 y 70
ПЕРВЫЙ СЕМЕСТР
ЛЕКЦИЯ N 6
2МЕТОДЫ УПРОЩЕНИЯ (МИНИМИЗАЦИИ) БУЛЕВЫХ ФУНКЦИЙ
Сложные булевы функции могут быть построены из более прос-
тых.
2Элементарными функциями 0 называются функции, образованные пу-
тем использования однотипных логических операций: только операции
И, только операции ИЛИ и т.д.
Для представления сложных логических функций можно использо-
вать не все элементарные функции, а только ту или иную часть их,
называемую системой. Система элементарных функций f 41 0, ..., f 4k 0 на-
зывается функционально полной, если любую сложную булеву функцию
можно записать в виде формулы через функции f 41 0, ..., f 4k 0.
Так, любую функцию можно представить с помощью одних только
операций И-НЕ или только операций ИЛИ-НЕ.
В цифровых устройствах часто применяется в качестве базовой
система из трех функций: И, ИЛИ и НЕ.
Используя законы алгебры логики, можно упрощать сложные ло-
гические выражения. Упрощение заключается в уменьшении количества
букв и количества отрицаний в выражении, что позволяет упростить
схему устройства с жесткой логикой или программу устройства с
программируемой логикой. Такое упрощение позволяет уменьшить се-
бестоимость и увеличить быстродействие устройства.
Рассмотрим функцию
4_________
7( 4_ 7 ) 4 _
f(a,b.c) = a 5. 72 0b V a 5. 0c 72 0 V a 5. 0b
79 0
Используя законы алгебры логики, можно привести эту функцию
к виду:
4_ 0 5 0 4_ 0 4 _ 0 4_ __ _ 0 4_ _
f(a,b.c) = a 5. 0(b 5. 0(a 5 0V 5 0c)) V a 5. 0b = ab V abc V ab = ab V ab
4применяем 0 4 0 4 применяем
4законы де Моргана 0 4 закон поглощения
Одной и той же логической функции может быть поставлено в
соответствие неограниченное количество различных эквивалентных
формул. Наиболее удобными для практического использования являют-
ся так называемые 2нормальные формы 0 представления сложных логичес-
ких функций.
2Элементарной конъюнкцией 0 Q называется логическое произведе-
ние переменных и их отрицаний, причем каждая переменная должна
встречаться в произведении только один раз.
.
- 2 -
4_ _
Пример элементарной конъюнкции: Q = x 41 0x 42 0x 43 0x 44 0x 46 0.
Аналогично 2элементарной дизъюнкцией 0 В называется логическая
сумма переменных и их отрицаний, причем каждая переменная должна
встречаться в сумме только один раз.
4_
Пример элементарной дизъюнкции: D = x 41 0 V x 43 0 V x 44 0.
Формула, эквивалентная заданной и представляющая собой логи-
ческую сумму элементарных конъюнкций, называется 2дизъюнктивной
2нормальной формой 0 (ДНФ) заданной формулы. Дизъюнктивная нормаль-
ная форма существует для любой логической функции.
Аналогично считается, что логическая функция задана своей
2конъюнктивной 0 2нормальной формой 0 (КНФ), если она выражена посредс-
твом логического произведения элементарных дизъюнкций. КНФ также
существует для любой логической функции.
Например, для функции 4_________
7( 4_ 7 ) 4 _
f(a,b.c) = a 5. 72 0b V a 5. 0c 72 0 V a 5. 0b
79 0
ДНФ будет иметь вид
4_ _
f(a,b.c) = ab V ab,
КНФ будет иметь вид
4_ _
f(a,b.c) = (a V b)(b V c).
Одна и та же функция путем эквивалентных преобразований мо-
жет быть представлена различными КНФ и ДНФ. Из всей совокупности
нормальных форм, представляющих данную функцию, выделяют одну КНФ
и одну ДНФ, именуемые совершенными.
2Минтермом 0 (m) n аргументов называется логическое произведе-
ние этих аргументов, причем каждый аргумент может входить в про-
изведение в прямой или инверсной форме.
Минтермы могут быть пронумерованы, причем номер минтерма оп-
ределяется как десятичный эквивалент двоичного числа, образован-
ного из значений переменных, входящих в данный набор: если пере-
менная входит в прямой форме, то ей соответствует единица, если в
инверсной - ноль.
2Макстермом 0 (M) n аргументов называется логическая сумма этих
аргументов, причем каждый аргумент может входить в сумму в прямой
или инверсной форме. Номер макстерма задается аналогично номеру
минтерма.
.
- 3 -
Рассмотрим в качестве примера случай двух аргументов:
------T-----T-------------T--------------¬
¦ a ¦ b ¦ минтерм ¦ макстерм ¦
+-----+-----+-------------+--------------+
¦ ¦ ¦ 4_ 0 4_ 0 ¦ 4_ 0 4_ 0 ¦
¦ 0 ¦ 0 ¦ m 40 0 = a 5. 0b ¦ M 40 0 = a V b ¦
¦ ¦ ¦ 4_ 0 ¦ 4_ 0 ¦
¦ 0 ¦ 1 ¦ m 41 0 = a 5. 0b ¦ M 41 0 = a V b ¦
¦ ¦ ¦ 4_ 0 ¦ 4_ 0 ¦
¦ 1 ¦ 0 ¦ m 42 0 = a 5. 0b ¦ M 42 0 = a V b ¦
¦ ¦ ¦ 4 0 ¦ ¦
¦ 1 ¦ 1 ¦ m 43 0 = a 5. 0b ¦ M 43 0 = a V b ¦
L-----+-----+-------------+---------------
Минтермы и макстермы можно геометрически представить на кар-
тах (диаграммах) Вейча. Так, для двух переменных карта Вейча бу-
дет представлять собой квадрат, причем левая половина квадрата
определяется переменной a, а верхняя половина квадрата - перемен-
ной b. Это означает, что левая 4_ 0 половина квадрата соответствует
значению переменной a, правая - a, верхняя половина соответствует
4_
b, нижняя b.
Карта Вейча для двух переменных:
4_
2a a
------T-----¬
¦ ¦ 4_ 0 ¦
2b 0¦ a 5. 0b ¦ a 5. 0b ¦
¦ ¦ ¦
+-----+-----+
4_ 0 ¦ 4_ 0 ¦ 4_ 0 4_ 0 ¦
2b 0¦ a 5. 0b ¦ a 5. 0b ¦
¦ ¦ ¦
L-----+------
.
- 4 -
Карта Вейча для 5 0трех переменных:
4_
2a a
5-------+------¬ -------+------¬
--------T-------T-------T-------¬
¦ 4_ 0 ¦ ¦ 4_ 0 ¦ 4_ 0 4_ 0 ¦
2b 0¦ a 5. 0b 5. 0c ¦ a 5. 0b 5. 0c ¦ a 5. 0b 5. 0c ¦ a 5. 0b 5. 0c ¦
¦ ¦ ¦ ¦ ¦
+-------+-------+-------+-------+
4_ 0 ¦ 4_ 0 4_ 0 ¦ 4_ 0 ¦ 4_ 0 4_ 0 ¦ 4_ 0 4_ 0 4_ 0 ¦
2b 0¦ a 5. 0b 5. 0c ¦ a 5. 0b 5. 0c ¦ a 5. 0b 5. 0c ¦ a 5. 0b 5. 0c ¦
¦ ¦ ¦ ¦ ¦
L-------+-------+-------+--------
4_ 0 5L------T------- 4 _
2c 0 2c c
2Свойства минтермов и макстермов:
1) Минтерм является инверсией некоторого макстерма и наобо-
рот: 4 _
m 4i 0 = M
2 5n 0-1-i
4_
M 4i 0 = m
2 5n 0-1-i
4_
Пример: m 41 0 = 4 0M 42 0 (заштрихованная площадь соответствует макс-
терму, незаштрихованная - минтерму).
1-TTT 0T 1-- 0-¬
1+++++ ¦
1++++ 0L 1TTT 0+
1+++++++++
1L+++++++-
2) Логическая сумма всех минтермов для любого заданного чис-
ла переменных равна 1.
2 5n 0-1
V m 4i 0 = 1.
i=0
3) Логическое произведение всех макстермов для любого задан-
ного числа переменных равно 0.
2 5n 0-1
7L 0 M 4i 0 = 0.
i=0
- 5 -
4) Два неодинаковых минтерма или макстерма имеют хотя бы од-
ну переменную, входящую в один из них в прямой, а в другой - в
инверсной форме, следовательно
m 4i 5. 0m 4j 0 = 0, если i 7- 0 j;
M 4i 0 V M 4j 0 = 1, если i 7- 0 j.
2Основная теорема алгебры логики 0: любую булеву функцию от n
переменных можно выразить логической суммой минтермов, которая
называется 2 совершенной нормальной дизъюнктивной формой 0, или логи-
ческим произведением макстермов, которое называется 2 совершенной
2нормальной конъюнктивной формой 0.
Логические функции отражают не только принцип работы некото-
рых частей ЭВМ, но и их состав, если каждой элементарной функции
соответствует реальный физический элемент. Любая сложная логичес-
кая функция может быть реализована некоторой частью ЭВМ, если эта
часть построена с помощью такого набора элементов, который реали-
зует все функции одной из функционально полных систем. Такой на-
бор называется функционально полным набором логических элементов
Поскольку каждая функция может быть представлена в виде раз-
личных логических уравнений, каждая функция может быть реализова-
на при помощи различных логических схем. Очевидно, что более
простому логическому уравнению соответствует более простая схема.
Упрощение (минимизация) функции сводится к получению ее минималь-
ной дизъюнктивной или конъюнктивной нормальной формы, т.е. такой
формы, при которой функция содержит наименьшее число переменных и
знаков логических операций.
Существует несколько методов минимизации. В дальнейшем мы
рассмотрим метод непосредственных преобразований и метод диаграмм
Вейча.
ПЕРВЫЙ СЕМЕСТР
ЛЕКЦИЯ N 7
2МЕТОДЫ МИНИМИЗАЦИИ БУЛЕВЫХ ФУНКЦИЙ
2Метод непосредственных преобразований
Суть данного метода заключается в том, что минимизация ис-
ходной логической функции производится путем применения к отдель-
ным членам или группам членов формулы, выражающей данную логичес-
кую функцию, основных законов алгебры логики с целью получения
минимальной формы функции, т.е. такой, которая не содержит лишних
переменных или членов.
Лишними переменными или членами являются те, которые не вли-
яют на значение преобразуемой формулы.
Пример:
4_ 5 4_
x 41 5. 0x 42 5. 0x 43 0 V x 41 5. 0x 42 5. 0x 43 0 = x 42 5. 0x 43 5. 0(x 41 5 0V 5 0x 41 0) = x 42 5. 0x 43 5. 01 = x 42 5. 0x 43
т.е. в исходной формуле лишней являлась двоичная переменная x 41 0.
Примечание: произведенная операция называется "склеиванием"
членов формулы.
Действия, отвечающие методу непосредственных преобразований,
обычно проводятся в следующем порядке:
1) Выявляются группы двоичных переменных исходной формулы, к
которым можно применить операцию склеивания или другие законы ал-
гебры логики, приводящие выражение к более простой форме.
2) Упрощение исходной формулы путем применения к выявленным
группам соответствующих законов.
3) Преобразование промежуточной логической формулы с целью
образования таких групп переменных, к которым можно применить уп-
рощающие законы алгебры логики. Здесь могут проводиться:
- группирование членов;
- действия по раскрытию скобок и выносу за скобки;
- добавление фиктивных членов, т.е. таких, совокупность ко-
торых тождественно равна нулю;
- логическое умножение одного или нескольких членов на логи-
ческую сумму переменной и ее отрицания.
4) Упрощение преобразованной промежуточной логической форму-
лы с получением формы, близкой к минимальной, в виде некоторой
ДНФ.
5) Выявление и удаление из полученной предварительной формы
лишних членов, что дает минимальную форму исходной логической
функции.
В качестве примера рассмотрим минимизацию следующей функции:
4_ _ _ _
f(a,b,c) = ab V bc V bc V ab =
- 2 -
(используем метод умножения всех членов формулы на сумму тех пе-
ременных и их отрицаний, которые отсутствуют в данном члене;)
4_ _ _ _ _ _ _ _
= ab(cVc) V bc(aVa) V bc(aVa) V ab(cVc) =
(в результате, отбросив повторяющиеся члены, получаем СДНФ функ-
ции;)
4_ 0 4 __ 0 4_ 0 4 _ _ 0 4 _ 0 4 __ 0 4 _ 0 4 _ _
= abc V abc V abc V abc V abc V abc V abc V abc =
L-- L=- L-- L=-
4_ __ _ _ _ __ _
= abc V abc V abc V abc V abc V abc =
(перегруппировываем члены с целью их упрощения)
4_ 9 4 _ _ _ _ _
= b 9c 0(aVa) V ab(cVc) V ac(bVb) =
(окончательно получим)
4_ _ _
= bc V ab V ac.
Однако группирование членов после умножения можно провести и
несколько иначе:
4_ _ _ _ _ _ _ _ _
f(a,b,c) = ab(cVc) V bc(aVa) V ac(bVb) = ab V bc V ac.
Следовательно, данная функция имеет две минимальные формы.
Недостатком метода непосредственной минимизации является
трудность получения всех минимальных форм, если их несколько.
Кроме того, метод в целом весьма трудоемок, результат минимизации
в сильной степени зависит от квалификации и интуиции человека,
проводящего минимизацию. Поэтому данный метод применяется лишь
для минимизации простых логических формул.
2Метод минимизации с помощью карт Вейча
Данный метод наиболее применим в инженерной практике благо-
даря своей простоте и легкости использования. Однако метод удобен
для упрощения функций, зависящих от небольшого числа переменных
(до 8). Преимущество этого метода состоит в том, что нет необхо-
димости приводить функцию к СДНФ.
Рассмотрим изображение на карте Вейча функции
4__ _ _ _ __ _ __ _
f(a,b,c,d) = cd V abd V abc V abcd V abcd V bcd
- 3 -
При нанесении заданной функции на карту никаких предвари-
тельных преобразований не проводится. Каждый дизъюнктивный член
рассматривается в отдельности, и в соответствующие ему квадратики
вписывается 1 (т.е. дизъюнктивный член развертывается до минтер-
мов).
Например, нанесение на карту вейча заданной функции выполня-
ется в следующей последовательности:
a
----+---¬
-----T---T---T---¬ ----T---T---T---¬ ----T---T---T---¬
¦¦ _1 . ¦ ¦ ¦ _1 . ¦ ¦ _1 . ¦ _1 . ¦ ¦ 1 ¦ ¦ 1 ¦ 1 ¦ ¦ _1 . ¦
b ++---+---+---+---+¬ +---+---+---+---+ +---+---+---+---+
¦¦ ¦ ¦ ¦ ¦¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ _1 . ¦
L+---+---+---+---++ d +---+---+---+---+ +---+---+---+---+
¦ ¦ ¦ ¦ ¦¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦
+---+---+---+---+- +---+---+---+---+ +---+---+---+---+
¦ _1 . ¦ ¦ ¦ _1 . ¦ ¦ 1 ¦ ¦ ¦ 1 ¦ ¦ 1 ¦ ¦ ¦ 1 ¦
L---+---+---+---- L---+---+---+---- L---+---+---+----
L---T----
4__ 0 c 4 0 4 __ _ __ _ _ _
cd cd V abd cd V abd V abc
----T---T---T---¬ ----T---T---T---¬ ----T---T---T---¬
¦ 1 ¦ 1 ¦ ¦ 1 ¦ ¦ 1 ¦ 1 ¦ ¦ 1 ¦ ¦ 1 ¦ 1 ¦ ¦ 1 ¦
+---+---+---+---+ +---+---+---+---+ +---+---+---+---+
¦ ¦ ¦ ¦ 1 ¦ ¦ ¦ ¦ ¦ 1 ¦ ¦ ¦ ¦ ¦ 1 ¦
+---+---+---+---+ +---+---+---+---+ +---+---+---+---+
¦ ¦ ¦ ¦ ¦ ¦ _1 . ¦ ¦ ¦ ¦ ¦ 1 ¦ _1 . ¦ _1 . ¦ ¦
+---+---+---+---+ +---+---+---+---+ +---+---+---+---+
¦ 1 ¦ ¦ _1 . ¦ 1 ¦ ¦ 1 ¦ ¦ 1 ¦ 1 ¦ ¦ 1 ¦ ¦ 1 ¦ 1 ¦
L---+---+---+---- L---+---+---+---- L---+---+---+----
4__ _ _ _ __ _ _ _ __ _ _ _
cd V abd V abc V cd V abd V abc V cd V abd V abc V
4__ _ __ _ __ __ _ __
V abcd V abcd V abcd V abcd V abcd V bcd
Следующий шаг заключается в нахождении на карте простых имп-
ликант, т.е. в склеивании минтермов. Нахождение простых импликант
является результатом последовательного применения теоремы:
4_
x 41 0x 42 0x 43 0...x 4n 0 V x 41 0x 42 0x 43 0...x 4n 0 = x 42 0x 43 0...x 4n
Нахождение простых импликант производится на картах путем
группировки минтермов, отмеченных единицей.
Рассмотрим правила группировки на диаграмме для четырех пе-
ременных, учитывая, что их легко обобщить на случай для любого
- 4 -
числа переменных. Группирование выполняется в следующем порядке:
а) группа из восьми членов может быть представлена одной пе-
ременной, если две смежные строки, либо два смежных столбца, либо
две крайние строки, либо два крайних столбца, соответствующих
этой переменной, заполнены единицами;
б) группа из четырех членов может быть представлена посредс-
твом двух переменных всякий раз, когда единицами заполнены:
- строка диаграммы,
- столбец диаграммы,
- квадрат из двух строк и двух столбцов,
- концы двух смежных строк,
- концы двух смежных столбцов,
- четыре угла диаграммы;
в) группа из двух членов может быть представлена посредством
трех переменных всякий раз, когда единицами заполнены:
- два смежных квадратика,
- два противоположных конца одной строки,
- два противоположных конца одного столбца.
При группировке единиц на диаграмме необходимо попытаться
сначала образовать члены, содержащие одну переменную, затем чле-
ны, содержащие две переменные, и, наконец, члены, содержащие три
переменные. Один и тот же минтерм может входить 2 несколько раз 0 в
выражение функции, не изменяя ее значения. Поэтому единицу или
группу единиц можно несколько раз включать в различные комбина-
ции. В нашем случае минимизированная функция будет иметь вид:
4__ _ _ _ 0 4_ _ 0 ___
f(a,b,c,d) = cd V abd V abc V abd V bcd V abd.
ПЕРВЫЙ СЕМЕСТР
ЛЕКЦИЯ N 8
2МЕТОДЫ МИНИМИЗАЦИИ БУЛЕВЫХ ФУНКЦИЙ
(окончание)
Обычно для проверки правильности результата, полученного с
помощью одного из методов минимизации, либо используют другой ме-
тод (хотя при наличии у функции нескольких минимальных форм могут
быть получены несовпадающие результаты), либо проверяют на тож-
дественность исходную и минимальную формы методом перебора всех
возможных комбинаций значений переменных (однако уже для 20 пере-
менных число возможных комбинаций превышает миллион).
В качестве примера проведем минимизацию рассматривавшейся
ранее функции
4_ _ _ _
f(a,b,c) = ab V bc V bc V ab
с помощью карты Вейча. Как видно из диаграммы, возможны две мини-
мальные дизъюнктивные формы:
a
----+---¬
----T---T---T---¬
b ¦ 1 ¦ ¦ _1 . ¦ _1 . ¦
+---+---+---+---+
¦ 1 ¦ 21 0 ¦ 21 0 ¦ ¦
L---+---+---+----
L---T----
c
4_ _ 0 4_
f(a,b,c) = ac V ab V bc
a
----+---¬
----T---T---T---¬
b ¦ _1 . ¦ ¦ 21 0 ¦ _1 . ¦
+---+---+---+---+
¦ 1 ¦ 1 ¦ 21 0 ¦ ¦
L---+---+---+----
L---T----
c
4_ _ 0 4_
f(a,b,c) = bc V ac V ab
.
- 2 -
2ЭЛЕМЕНТЫ И УЗЛЫ ЭВМ
===================
2ЛОГИЧЕСКИЕ ЭЛЕМЕНТЫ
Системой элементов ЭВМ называется функционально полный набор
логических элементов, использующий одинаковый способ представле-
ния информации и одинаковый тип межэлементных связей.
Система элементов чаще всего избыточна по своему составу,
что позволяет строить схемы с более простой топологией межэле-
ментных связей и более экономные по количеству используемых эле-
ментов.
Классификация логических элементов:
1) По способу представления информации и типу межэлементных
связей различают элементы импульсного, потенциального, импуль-
сно-потенциального и динамического типа.
Примечание: в современных ЭВМ применяются потенциальные и
динамические элементы.
2) По функциональному назначению элементы принято разделять
на 2типовые и элементы специального назначения 0. К 2типовым 0 относят-
ся логические, запоминающие и формирующие элементы. Логические
элементы предназначены для преобразования информации, запоминаю-
щие - для ее хранения, а формирующие элементы - для восстановле-
ния стандартизированных значений физических параметров сигналов,
изменяющихся во время прохождения сигналов по электрическим це-
пям. К элементам 2 специального назначения 0 относятся усилители сла-
бых сигналов, генераторы токов и напряжений специальной формы и
другие элементы, не изменяющие информационного содержания сигна-
лов.
3) В зависимости от используемых физических явлений логичес-
кие элементы подразделяются на полупроводниковые, магнитополупро-
водниковые, электромагнитные и др.
2Основные характеристики логических элементов
Общие технические характеристики:
- температурный диапазон,
- надежность,
- стоимость.
Специфические характеристики:
- функциональные возможности элемента,
- нагрузочная способность,
- быстродействие,
- 3 -
- помехоустойчивость,
- потребляемая мощность.
Функциональные возможности логического элемента характеризу-
ются выполняемой им операцией и коэффициентами разветвления и
объединения, т.е. факторами, влияющими на структуры более сложных
схем, построенных с применением данного элемента.
При этом под 2коэффициентом разветвления 0 2n 0 понимают число
входов последующих ячеек, которые могут управляться от выхода
данной ячейки, а под 2коэффициентом объединения 0 2m 0 - число входов,
которое может иметь ячейка. Величины m и n ограничиваются услови-
ями сохранения нормального электрического режима ячейки.
2Нагрузочная способность 0 в общем случае определяется током,
который может быть отдан ячейкой во внешние цепи (нагрузку). В
случае однородных нагрузок, создаваемых входами идентичных ячеек,
нагрузочная способность оценивается коэффициентом разветвления n.
2Быстродействие 0 логического элемента определяется скоростями
его перехода из состояния "0" в состояние "1" и обратно. Переход-
ные процессы изменения состояния элемента состоят из двух этапов:
задержки и формирования фронта или спада сигнала. Длительность
задержек и фронтов зависит от динамических свойств логического
элемента.
Однако для оценки быстродействия часто используют обобщенную
характеристику - 2 среднее время задержки 0. В этом случае моментом
поступления сигнала на ячейку считают момент достижения входным
сигналом некоторого определенного уровня (например, 0,5 от уста-
новившегося значения). Моментом появления сигнала на выходе также
считают момент достижения выходным сигналом этого уровня.
Так как длительности переходных процессов при включении и
выключении транзистора в общем случае не равны, то проводят обоб-
щение и говорят о среднем времени задержки сигнала на ячейку.
Время задержки при формировании спада
t 4сп
t 5' 4з 5 0= t 4з.сп 0+ 4 0--- ,
2
а время задержки при формировании фронта
t 4фр
t 5" 4з 5 0= t 4з.фр 0+ 4 0--- .
2
Среднее время задержки на один каскад схемы
t 5' 4з 0 + t 5" 4з
t 4з.ср 0 = --------- 5.
2
- 4 -
Одна из важнейших характеристик элемента - его 2помехоустой-
2чивость 0. Различают статическую и динамическую помехоустойчивость.
При определении статической помехоустойчивости помеха рассматри-
вается как длительно действующий уровень потенциала, а при опре-
делении динамической помехоустойчивости - как импульс определен-
ной длительности. Устойчивость элемента к воздействию длительной
помехи меньше, чем к воздействию кратковременной помехи при оди-
наковых амплитудах. Устойчивость к воздействию динамической поме-
хи тем ниже, чем выше быстродействие элемента.
С увеличением степени интеграции элементов ЭВМ все большую
роль начинает играть такой параметр, как 2 рассеиваемая мощность 0.
Следует отметить, что закрытому состоянию соответствует один уро-
вень рассеивания мощности (P 4з 0), а открытому - другой (P 4о 0). Обычно
предполагают, что схема половину времени находится в открытом
состоянии, а половину - в закрытом, и определяют среднюю рассеи-
ваемую мощность следующим образом:
P 4з 0 + P 4о
P 4ср 0 = ------- .
2
Рассеиваемая мощность может зависеть как от нагрузки, так и
от схем, включенных на входе.
1Классификация логических элементов по типу радиокомпонентов,
1на которых реализуются логические функции 2.
Можно выделить следующие наиболее часто употребляемые на
данный момент типы логических элементов:
- транзисторно-транзисторная логика с диодами Шотки (ТТЛШ);
- КМОП-логика (логика на базе комплементарных полевых тран-
зисторов со структурой металл-окисел-полупроводник);
- КМДП-логика (логика на базе комплементарных полевых тран-
зисторов со структурой металл-диэлектрик-полупроводник);
- интегральная инжекционная логика (ИИЛ, И 52 0Л, I 52 0L).
Следует отметить также некоторые типы элементов, которые в
данный момент уже не применяются в новых разработках вследствие
низкого быстродействия или большой рассеиваемой мощности.
- резисторно-транзисторная логика (РТЛ, RTL);
- резисторно - конденсаторная транзисторная логика (РКТЛ,
RCTL);
- диодно-транзисторная логика (ДТЛ, DTL);
- транзисторно-транзисторная логика (ТТЛ, TTL);
- транзисторная логика с эмиттерными связями (ЭСЛ, TECL).
- транзисторная логика с непосредственными связями (DCTL).
- МОП-логика;
- МДП-логика (MDS).
ПЕРВЫЙ СЕМЕСТР
ЛЕКЦИЯ N 9
2ЭЛЕМЕНТЫ И УЗЛЫ ЭВМ
===================
2ЛОГИЧЕСКИЕ ЭЛЕМЕНТЫ
Электронную схему, выполняющую какие либо операции над одним
машинным словом, называют 2узлом 0 ЭВМ. Многие узлы ЭВМ строятся на
базе логических элементов.
Общие требования к проектируемому устройству:
- устройство должно полностью соответствовать своему функци-
ональному назначению, т.е. выполнять заданные в ТЗ функции;
- быстродействие, энергопотребление, надежность, устойчи-
вость к вредному воздействию окружающей среды (температура, влаж-
ность, давление, вибрация, удары, статическое электричество,
внешние магнитные поля, электромагнитные помехи и пр.) должны со-
ответствовать заданным в ТЗ параметрам;
- устройство должно быть максимально простым, чтобы обеспе-
чить высокое быстродействие и надежность, а также низкую себесто-
имость.
Если устройство проектируется на базе нескольких различных
наборов логических элементов, особенно в случае различной техно-
логии изготовления (ТТЛ и ТТЛШ, ТТЛ и КМОП, ТТЛ и ЭСЛ и т.п.),
необходимо тщательно проверить эти наборы на совместимость во
всем рабочем диапазоне температур и на отсутствие состязаний в
спроектированной схеме.
Требуется проверить:
- соответствие по номинальному напряжению питания;
- соответствие по входным и выходным характеристикам логи-
ческих элементов, особенно по уровням 0 и 1;
- соответствие элементов по быстродействию;
- соответствие по переходным процессам.
1Основные характеристики логических элементов
2Амплитудная передаточная характеристика 0 U 4вых 0= 4 0f(U 4вх 0) опре-
деляет формирующие свойства логического элемента, его помехоус-
тойчивость, амплитуду и уровни стандартного сигнала. Вид характе-
ристики зависит от типа логического элемента (ЭСЛ, ТТЛ и т.д.) и
Назад | Следующая страница
В начало реферата
|
