Лекции по проектированию цифровых устройств
скачать (813.3 kb.)
Доступные файлы (11):
| 1_Основы алгебры логики.doc | 188kb. | 08.07.2004 05:33 |  скачать |
| 2а_минимизация.doc | 519kb. | 08.07.2004 06:16 | скачать |
| 2_Проектиров цифр устр.doc | 174kb. | 08.07.2004 05:41 | скачать |
| 3a_применение мультиплексоров.doc | 287kb. | 01.12.2001 00:22 | скачать |
| 3b_Cумматоры.doc | 176kb. | 08.07.2004 05:53 | скачать |
| 3c_интегральные сумматоры.doc | 202kb. | 08.07.2004 05:59 | скачать |
| 3_Типовые комбинационные устройства.doc | 242kb. | 08.07.2004 06:25 | скачать |
| 4_Интегральные триггеры.doc | 388kb. | 08.07.2004 06:04 | скачать |
| 5_задержки в цифровых цепях.doc | 100kb. | 01.09.2004 20:00 | скачать |
| 6_Проектир последоват схем.doc | 276kb. | 14.01.2007 17:22 | скачать |
| ПЦУ_программа_2002.doc | 111kb. | 01.09.2004 20:07 | скачать |
1_Основы алгебры логики.doc
1.ОСНОВЫ АЛГЕБРЫ ЛОГИКИ
1.1. Понятие о логических функциях
Отличительной особенностью логических функций является то, что они принимают значения в конечных множествах. Иначе говоря, область значений логической функции всегда представляет собой конечную совокупность чисел, символов, понятий, свойств и, вообще, любых объектов.
Если область значений функции содержит k различных элементов, то она называется k-значной функцией. Перечень символов, соответствующих области значений функции, называется алфавитом, а сами символы - буквами этого алфавита: N={a1,a2,...ak}.
Логические функции могут зависеть от одной, двух и, вообще, любого числа переменных (аргументов) - х1,х2..хm. В отличие от самой функции, аргументы могут принимать значения из элементов как конечных, так и бесконечных множеств. В теоретико-множественном смысле логическая функция n переменных
y= f(x1,x2,..xn) (1.1)
представляет собой отображение множества наборов (n- мерных векторов) вида (x1,x2,..xn), являющихся областью ее определения, на множество ее значений N={a1,a2,..ak}, при условии однозначности этого отображения:
f: (x1,x2,..xn)N (1.2)
Логическую функцию можно также рассматривать как операцию, заданную законом композиции X1*X2*..*XnN, где X1,X2,..Xn - множества, на которых определены аргументы.
--------------------------------------------------------------------------------
Бинарное отношение ставит в соответствие паре объектов (a,b) третий объект с. При этом a,b операнды, с - результат операции или композиция объектов a и b. Если a принадлежит А, b принадлежит B, а с принадлежит С, то А*В C - закон композиции.
--------------------------------------------------------------------------------
Логическая функция называется однородной, если она принимает значения из того же множества, что и все ее аргументы, т.е. X1=X2=..=Xn.
Однородная логическая функция рассматривается как закон композиции NnN и определяет некоторую n-местную операцию на конечном множестве N.
Областью определения однородной функции y=f(x1, x2,..xn) служит множество наборов (x1, x2,..xn), называемых словами, где каждый из аргументов xi замещается буквами k-ичного алфавита {0,1,2,..k-1}. Очевидно, число различных слов длины n в k-ичном алфавите равно kn. Т.к. каждому такому слову имеется возможность сопоставить одно из k значений множества N, то общее количество однородных логических функций от n переменных выражается числом k^k^n.
^
Однородные логические функции, определенные на множестве N={0,1} называются двухзначными или булевыми по имени английского математика Дж. Буля (1815-1864). Областью определения булевых функций от n переменных служит множество двоичных векторов длиной n. Число различных булевых функций быстро возрастает с ростом n.
Таблица 1. Зависимость числа булевых функций от числа аргументов
-
^
Число вх. наборов
Число БФ
n
2^n
2^2^n
1
2
4
2
4
16
3
8
256
4
16
65536
5
32
>4 109
Наибольшее значение в теории БФ имеют функции одной и двух переменных.
^
| X | 0 1 | Наименование функции |
| Y0 | 0 0 | const 0 |
| Y1 | 0 1 | x |
| Y2 | 1 0 | /x |
| Y3 | 1 1 | const 1 |
Лишь одна функция этой таблицы нетривиальна - y=/x . Эта функция называется "инверсией" или "отрицанием".
^
Табл.3. Булевы функции двух переменных
-
X1
X2
0 0 1 1
0 1 0 1
Наименование функции
Y0
0 0 0 0
const 0
Y1
0 0 0 1
конъюнкция x1&x2, x1|x2, x1x2, "И"
Y2
0 0 1 0
запрет по х2, х1*/х2
Y3
0 0 1 1
переменная х1
Y4
0 1 0 0
запрет по х1, /х1*х2
Y5
0 1 0 1
переменная х2
Y6
0 1 1 0
сумма по mod2
Y7
0 1 1 1
Дизъюнкция х1 V х2, x1+x2
Y8
1 0 0 0
стрелка Пирса x1x2
Y9
1 0 0 1
равнозначность x1x2
Y10
1 0 1 0
инверсия х2, /х2
Y11
1 0 1 1
импликация х2х1
Y12
1 1 0 0
инверсия х1 /х1
Y13
1 1 0 1
импликация х1х2
Y14
1 1 1 0
штрих Шеффера х1/х2
Y15
1 1 1 1
const 1
Для каждой функции можно сформулировать логические правила формирования ее значений. Например: функция запрета по х1 повторяет единичные значения аргумента х2 всегда, когда х1 не равно 1; функция импликации (следования) х1х2 равна единице, если при переходе от х1 к х2 значения не убывают.
Из таблицы видно, что между БФ двух переменных имеет место соотношение:
yi=/y15-i, (i=0,1,..15) (1.3)
На основании этого можно записать:
0=/1, 1=/0 (0-15);
x=//x (3-12, 5-10);
x1/x2=/(x1x2) (1-14);
x1x2=/(x1+x2) (7-8); (1.4)
x1x2=/(x1~x2) (6-9);
x1/x2=/(x1x2) (2-13);
/x1x2=/(x2x1) (4-11);
Из 1.3 следует, что любая функция двух переменных выражается в аналитической форме через отрицание /x и любую из каждой пары {y0,y15}, {y1,y14}, {y2,y13}, {y6,y9}, {y7,y8}. Например, можно выбрать такой набор БФ: y0, /x, y1(&), y7(+), y9(~), y13(). Можно показать, что такой набор является избыточным, т.к. y9 и y13 можно выразить через остальные функции набора:
y9 = x1~x2 = x1x2+/x1/x2, y13=/x1+x2 (1.5)
Набор из оставшихся 4-х функций широко применяется на практике, но и он может быть сокращен за счет удаления y1 и y7.
Выражения, построенные из конечного числа логических переменных и знаков логических операций - называются булевыми выражениями. Введение каждой новой операции должно сопровождаться введением пары операторных скобок. Для упрощения формы записи выражений, как и в обычной алгебре, вводится понятие старшинства операций, например: отрицание, логическое умножение, логическое сложение (в порядке убывания).
Два выражения, дающие одинаковые значения на одних и тех же наборах переменных - называются тождественными.
^ .
Наглядным способом представления логических функций являются диаграммы Эйлера-Венна. Эти диаграммы приведены ниже для функций НЕ, И, ИЛИ.
а) б) в)
Рис.1.1. Диаграммы Эйлера-Венна для логических
функций НЕ (а), И (в), ИЛИ (б).
Ранее было показано, что одни БФ могут быть выражены через другие. Последние именуют базисными функциями или базисом. Исследование логических функций двух переменных показало, что возможно выделение некоторого подмножества Y' множества Y={y0,y1,..y15}, с помощью которого можно выразить любую БФ от произвольного числа аргументов. Такие подмножества называют функционально полным базисом. Построить функции большего числа переменных, используя только функции двух переменных, можно с помощью операций композиции, под которыми понимается подстановка одних функций вместо переменных в другие функции. Такая подстановка возможна в силу того, что области значений функций и переменных совпадают (0 и 1).
Функции образующие полный базис должны обладать определенными свойствами. Прежде, чем сформулировать эти свойства, рассмотрим классы логических функций.
^
По теореме Жегалкина - любая БФ(n) может быть представлена полиномом степени не выше n. Если БФ представляется полиномом первой степени:
f(x1,x2,..xn)=k0 k1x1 k2x2 .. knxn, (1.6)
где ki принадлежит множеству {0,1}, то такая функция называется линейной. Количество линейных функций n переменных равно 2n+1. Для n=2 количество линейных функций равно 8.
Kл={y0,y3,y5,y6,y9,y10,y12,y15}.
1) y0=0
2) y3=x1
3) y5=x2
4) y6=x1 x2
5) y9=1 x1 x2
6) y10=1 x2
7) y12=1 x1
8) y15=1
^
Это функции равные 0 на нулевом наборе переменных.
K0={y0,y1,y2,y3,y4,y5,y6,y7}.
Это функции равные 1 на единичном наборе переменных.
K1={y1,y3,y5,y7,y9,y11,y13,y15}.
^
Это функции неубывающие при любом возрастании набора аргументов 00011011.
Kм={y0,y1,y3,y7,y15}.
Функция, принимающая противоположные значения на каждой паре противоположных наборов, т.е.
f(x1,x2,..xn)=/f(/x1,/x2,../xn).
Kс={y3,y5,y10,y12}.
Это функции равные 0 на нулевом наборе переменных.
K0={y0,y1,y2,y3,y4,y5,y6,y7}.
Класс функций сохраняющих "1"
Это функции равные 1 на единичном наборе переменных.
K1={y1,y3,y5,y7,y9,y11,y13,y15}.
^
Это функции неубывающие при любом возрастании набора аргументов 00011011.
Kм={y0,y1,y3,y7,y15}.
Класс самодвойственных функций
Функция, принимающая противоположные значения на каждой паре противоположных наборов, т.е.
f(x1,x2,..xn)=/f(/x1,/x2,../xn).
Kс={y3,y5,y10,y12}.
Табл.4. Сводная таблица классов
функций двух переменных
| | Кл | К0 | К1 | Км | Кс |
| Y0 | 1 | 1 | | 1 | |
| Y1 | | 1 | 1 | 1 | |
| Y2 | | 1 | | | |
| Y3 | 1 | 1 | 1 | 1 | 1 |
| Y4 | | 1 | | | |
| Y5 | 1 | 1 | 1 | 1 | 1 |
| Y6 | 1 | 1 | | | |
| Y7 | | 1 | 1 | 1 | |
| Y8 | | | | | |
| Y9 | 1 | | 1 | | |
| Y10 | 1 | | | | 1 |
| Y11 | | | 1 | | |
| Y12 | 1 | | | | 1 |
| Y13 | | | 1 | | |
| Y14 | | | | | |
| Y15 | 1 | | 1 | 1 | |
^
Для того, чтобы базис был полным, необходимо и достаточно, чтобы он содержал хотя бы по одной функции:
не сохраняющей 0;
не сохраняющей 1;
не являющейся линейной;
не являющейся монотонной;
не являющейся самодвойственной.
Существует несколько полных базисов:
B1={y1,y7,y10(y12)} И ИЛИ НЕ,
B2={y1,y10} И НЕ,
B3={y7,y10} ИЛИ НЕ,
B4={y8} функция Пирса,
B5={y14} функция Шеффера.
Функции y8 и y14 не принадлежат ни к одному из рассмотренных классов и, следовательно, в единственном числе составляют полный базис. Алгебра построенная на базисе В1 называется булевой по имени английского математика первого исследовавшего логические функции. Существуют и другие алгебры, например, Жегалкина - построенная на базисе {y1,y6,y15} (И ~ 1).
^
Следует помнить, что для доказательства тождеств алгебры логики можно пользоваться методом подстановки значений.
| //x=x | Ассоциативный закон: | xvyvz=(xvy)vz | x&y&z=(x&y)&z | |
| x&0=0 | xv0=x | Коммутативный закон: | xvy=yvx | x&y=y&x |
| x&1=x | xv1=1 | Дистрибутивный закон: | (xvy) & z=x&z v y&z | x&y v z=(xvz)&(yvz) |
| x&x=x | xvx=x | Законы поглощения: | xvx&y=x | (xvy)&x=x |
| x&/x=0 | xv/x=1 | Законы дуальности (теоремы д-Моргана): | ___ _ _ xvy = x&y | ___ _ _ x&y=xvy |
Клод Шенон предложил обобщение теорем дуальности, позволяющее отыскивать инверсию любой функции f(X), где X=(xn,..x1):
________ _
f(X/v,&)=f(X/&,v). (1.7)
В соответствии с 1.7 инверсию любой функции можно получить взаимной заменой переменных и их инверсий и операций дизъюнкции и конъюнкции.
^
Табличный
Аргументы обычно упорядочивают в порядке убывания величины индексов. Таблица может дополняться колонкой - порядковым номером строки. Удобно соблюдать соответствие между порядковым номером и двоичным кодом соответствующим данному набору значений аргументов. Подобного рода таблицы называют таблицами истинности. Существуют и другие формы таблиц, которые будут рассмотрены в дальнейшем.
Табл.5
| N | x2 x1 x0 | y |
| 0 | 0 0 0 | 0 |
| 1 | 0 0 1 | 1 |
| 2 | 0 1 0 | 1 |
| 3 | 0 1 1 | 0 |
| 4 | 1 0 0 | 1 |
| 5 | 1 0 1 | 0 |
| 6 | 1 1 0 | 1 |
| 7 | 1 1 1 | 0 |
Нулевые значения функции в таблицу можно и не вписывать. Разновидностью табличного метода можно считать способ задания номеров двоичных наборов на которых функция принимает 1 или 0 значения.
^
Логическая функция задается в виде условного графического изображения элемента реализующего эту функцию.
Аналитический
Логическая функция записывается в виде математического выражения. Предпочтительно использование канонических форм записи в виде дизъюнктивной или конъюнктивной форм. Рассмотрим эти формы записи.
^
Минтермом или конституентой единицы называется функция n переменных:
~ ~ ~
mi (xn,xn-1 ..x1)=x1&x2&..&xn, (1.8)
~ __
где xp - т.н. первичный терм, принимающий значение xp или xp, а i - номер терма соответствующий двоичному коду, построенному на значениях первичных термов входящих в выражение 1.7. xp ставится в соответствие 1, а /xp - 0.
Видно, что имеется 2n различных минтермов для n переменных. Минтермы обладают следующими свойствами:
Минтерм принимает единичное значение лишь на наборе соответствующем его номеру;
Минтермы взаимно ортогональны, т.е. произведение любых минтермов с разными номерами равно 0;
Сумма всех минтермов n переменных равна 1.
Макстермом или конституентой 0 называют функцию n переменных:
~ ~ ~
Mi(xn,xn-1,..x1)=xn v xn-1 v..v x1. (1.9)
Свойства макстермов двойственны по отношению к свойствам минтермов. Названия связаны с тем, что макстерм соответствует максимальному из значений входящих в него переменных, а минтерм - минимальному.
^
Одна из важнейших теорем в алгебре логики это теорема разложения. Согласно ей любую функцию f можно разложить по переменной хp в форме
_
f(xn,..xp,..x1)=xp&f(xn,..0,..x1)vxp&f(xn,.1,..x1). (1.10)
Эта теорема легко доказывается методом перебора. Легко получить альтернативный вариант теоремы разложения
_
f(xn,..xp,..x1)=[xpvf(xn,..1,..x1)][xpvf(xn,..0,..x1)]. (1.11)
Совершенная дизъюнктивная нормальная форма (СДНФ)
Применяя последовательно теорему разложения 1.10 к любому логическому выражению, его можно свести к виду
f(X)=Vf(i)&mi, (1.12)
i
где i - порядковый номер двоичного набора, f(i) - значение функции на этом наборе (0 или 1), mi - соответствующий минтерм. Т.е. любая функция может быть представлена в виде логической суммы минтермов, с номерами соответствующими наборам переменных, на которых логическая функция равна единице. Такая форма представления логической функции и носит название совершенной дизъюнктивной нормальной формы (СДНФ).
Для примера проведем разложение функции двух переменных f(x1,x0).
_
f(x1,x0)=x1&f(0,x0)vx1&f(1,x0)=
_ _ _ _
=x1&x0&f(0,0)v x1&x0&f(0,1) v x1&x0&f(1,0) v x1&x0&f(1,1).
^
В полном соответствии с принципом двойственности любую функцию можно представить в совершенной конъюнктивной нормальной форме (СКНФ) как логическое произведение макстермов на которых значение функции равно 0:
f(X)=&(f(i)vMi). (1.13)
i
^
Рассмотренные выше две формы аналитической записи логических функций представляют удобный способ перехода к аналитическому заданию логической функции от табличного.
Для перехода к СДНФ функцию следует представить в виде суммы минтермов записанных для строк таблицы на которых значение функции равно 1. Минтерм формируется по следующему правилу: если значение переменной входящей в набор равно 1, то переменная входит в терм в прямом виде, иначе - в инверсном.
Для перехода к СКНФ функцию следует представить в виде произведения макстермов, записанных для строк таблицы, на которых значение функции равно 0. Макстерм формируется по следующему правилу: если значение переменной входящей в набор равно 0, то переменная входит в терм в прямом виде, иначе - в инверсном.
Пример.
Пусть функция представлена в табличной форме.
-
N
x2
x1
x0
y
0
0
0
0
1
1
0
0
1
1
2
0
1
0
0
3
0
1
1
1
4
1
0
0
0
5
1
0
1
1
6
1
1
0
0
7
1
1
1
1
1.Представим ее вначале в СДНФ. Выпишем все макстермы, для которых значение функции равно 1.
_ _ _ _ _ __
f(X) = x2x1x0 v x2x1x0 v x2x1x0 v
_
x2x1x0 v x2x1x0
2.Запишем функцию в СКНФ. Для этого выпишем минтермы для наборов, где функция принимает 0 значения.
__ __ __ __
f(X) = (x2vx1vx0)&(x2vx1vx0)&(x2vx1vx0)
В заключение заметим, что обратный перевод из аналитической формы записи в табличную форму тривиален и состоит в подстановке значений аргументов и вычислении значений функции.
^
При проектировании цифровых систем интерфейсным методом широко используют метод временных диаграмм. При этом проектировщики не имеют в своем распоряжении строгих математических методов проектирования. Такое положение вещей не должно обескураживать приверженцев строгих методов, т.к. подобное состояние дел наблюдается в химии (таблица Менделеева), а сейчас и в физике (таблицы Феймана и Голдстоуна). Вместо того чтобы детально рассчитывать схемы, опираясь на интегро-дифференциальные уравнения электротехники, используют топологически преобразованные интегральные схемы (ИС) соединенные друг с другом. При этом состояния интересующие проектировщика описываются с помощью булевой алгебры и двоичной арифметики. Временные соотношения заданные временными диаграммами сводятся, обычно, к системам простых неравенств [2].
Временные диаграммы представляют собой совмещенные диаграммы, на которых уровни изображаются условно и соответствуют логическим 0 или 1. На диаграммах отображаются все характерные временные соотношения, такие как: длительности фронтов и спадов сигналов, взаимное расположение сигналов ни временной оси. Семейства временных диаграмм обычно задаются для различных режимов работы устройств и лишь для устройств со сложной логикой работы. Многочисленные примеры временных диаграмм можно найти, например, в [3].
^
БФ можно представлять в виде гиперкубов. При этом каждой вершине гиперкуба ставится в соответствие минтерм. Для функции двух переменных таким представлением является квадрат.
Если число переменных превышает три, то более удобным является представление в виде карт Карно - развертки гиперкубов на плоскости. Вершины гиперкубов представляются при этом клетками карты. По своей сути, карта Карно представляет собой матричную таблицу. Строки и столбцы ее соответствуют значениям аргументов, а значения функции пишутся в местах пересечений.
Особенность разметки карт состоит в том, что соседние термы размещаются в соседних клетках. Соседними именуют термы отличающиеся значением лишь одной переменной. Соседними считаются не только клетки расположенные рядом, но и клетки на противоположных сторонах карты. Ниже приведена разметка карт Карно для функций двух, трех, и четырех переменных.
При заполнении карты в клетках вписываются значения функции. Обычно вписывают лишь единичные значения. Для ускорения процесса заполнения и его ускорения удобно пользоваться трафаретом. Далее приведен такой трафарет для карты на 4 переменные.
При исходной функции заданной таблицей истинности заполнение будет происходить быстро, т.к. нумерация клеток карты Карно будет соответствовать номерам строк таблицы.
Возможно построение карт Карно и для большего числа переменных. Ниже приведена карта для 8 переменных.
^
Ранее были рассмотрены функции, значение которых известно на всех наборах переменных. Такие функции называются полностью определенными. Если значение функции на некоторых наборах неопределенно, то функция называется не полностью определенной. При табличном задании таких функций в соответствующих позициях таблиц вписывают значок неопределенности "х". Особенностью неполностью определенных функций является возможность их произвольного доопределения, что используется при минимизации функций.
Функции многих переменных могут зависеть не от всех входящих в них переменных. Такие функции называются вырожденными.
Далее по тексту "/"будет применяться для обозначения инверсии.
Скачать файл (813.3 kb.)