Текст книги "Лекции по схемотехнике"

Автор книги: Автор Неизвестен

сообщить о нарушении

Текущая страница: 1 (всего у книги 7 страниц)

Элементы схемотехники цифровых устройств обработки информации
Екатеринбург 2008

Введение

Электронные вычислительные машины выполняют арифметические и логические операции, при этом используется два класса переменных: числа и логические переменные.

Числа несут информацию о количественных характеристиках системы; над ними производятся арифметические действия.

Логические переменные  определяют состояние системы или принадлежность её к определённому классу состояний (коммутация каналов, управление работой ЭВМ по программе и т.п.).

Логические переменные могут принимать только два значения: истина и ложь. В устройствах цифровой обработки информации этим двум значениям переменных ставится в соответствие два уровня напряжения: высокий – (логическая «1») и низкий – (логический 0»). Однако в эти значения не вкладывается смысл количества.

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

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

1 Арифметические и логические основы ЭВМ

1.1  Арифметические  основы  ЭВМ

В настоящее время в обыденной жизни для кодирования числовой информации используется десятичная система счисления с основанием 10, в которой используется 10 элементов обозначения: числа 0, 1, 2, … 8, 9. В первом (младшем) разряде указывается число единиц, во втором – десятков, в третьем – сотен и т.д.; иными словами, в каждом следующем разряде вес разрядного коэффициента увеличивается в 10 раз.

В цифровых устройствах обработки информации используется двоичная система счисления с основанием 2, в которой используется два элемента обозначения: 0 и 1. Веса разрядов слева направо от младших разрядов к старшим увеличиваются в 2 раза, то есть имеют такую последовательность: 8421. В общем виде эта последовательность имеет вид:

…2⁵2⁴2³2²2¹2⁰,2^-12^-22^-3…

и используется для перевода двоичного числа в десятичное. Например, двоичное число 101011 эквивалентно десятичному числу 43:

 2⁵·1+2⁴·0+2³·1+2²·0+2¹·1+2⁰·1=43

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

Бит или двоичный разряд определяет значение одного какого-либо знака в двоичном числе. Например, двоичное число 101 имеет три бита или три разряда. Крайний справа разряд, с наименьшим весом, называется младшим, а крайний слева, с наибольшим весом, – старшим.

Байт определяет 8-разрядную единицу информацию, 1 байт=23 бит, например, 10110011 или 01010111 и т.д., 1 кбайт = 2¹⁰ байт, 1 Мбайт = 2¹⁰ кбайт = 2²⁰ байт.

Для представления многоразрядных чисел в двоичной системе счисления требуется большое число двоичных разрядов. Запись облегчается, если использовать шестнадцатеричную систему счисления.

Основанием шестнадцатеричной системы счисления является число 16=2⁴, в которой используется 16 элементов обозначения: числа от 0 до 9 и буквы A, B, C, D, E, F. Для перевода двоичного  числа в шестнадцатеричное достаточно двоичное число разделить на четырёхбитовые группы: целую часть справа налево, дробную – слева направо от запятой. Крайние группы могут быть неполными.

Каждая двоичная группа представляется соответствующим шестнадцатеричным символом (таблица 1). Например, двоичное число 0101110000111001 в шестнадцатеричной системе выражается числом 5C39.

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

Двоично-десятичный код образуется заменой каждой десятичной цифры числа четырёхразрядным двоичным представлением этой цифры в двоичном коде (См. таблицу 1). Например, число 15 представляется как 00010101 BCD (Binary Coded Decimal). При этом в каждом байте располагаются две десятичные цифры. Заметим, что двоично-десятичный код при таком преобразовании не является двоичным числом, эквивалентным десятичному числу.

1.2  Логические  основы  ЭВМ

Раздел математической логики, изучающий связи между логическими переменными, имеющими только два значения, называется алгеброй логики. Алгебра логики разработана английским математиком Дж. Булем и часто называется булевой алгеброй. Алгебра логики является теоретической базой для построения систем цифровой обработки информации. Вначале на основе законов алгебры логики разрабатывается логическое уравнение устройства, которое позволяет соединить логические элементы таким образом, чтобы схема выполняла заданную логическую функцию.

Таблица 1 – Коды чисел от 0 до 15

0	0000	0	000
1	0001	1	0001
2	0010	2	0010
3	0011	3	0011
4	0100	4	0100
5	0101	5	0101
6	0110	6	0110
7	0111	7	0111
8	1000	8	1000
9	1001	9	1001
10	1010	A	00010000
11	1011	B	00010001
12	1100	C	00010010
13	1101	D	00010011
14	1110	E	00010100
15	1111	F	00010101

1.2.1 Основные положения алгебры логики

     Различные логические переменные могут быть связаны функциональными зависимостями. Функциональные зависимости между логическими переменными могут быть описаны логическими формулами или таблицами истинности.

В общем виде логическая формула функции двух переменных записывается в виде: y=f(X₁, X₂), где X₁, X₂ – входные переменные.

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

Таблица 2 – Полный набор функций одной переменной

0	1	0	1	0
1	0	1	1	0

Y1 – Инверсия, Y2 – Тождественная функция, Y3 – Абсолютно истинная функция и Y4 – Абсолютно ложная функция.

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

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

Основными логическими функциями двух переменных, используемыми в устройствах цифровой обработки информации являются: дизъюнкция (логическое сложение), конъюнкция (логическое умножение), сумма по модулю 2 (неравнозначность), стрелка Пирса и штрих Шеффера. Условные обозначения логических операций, реализующих указанные выше логические функции одной и двух переменных, приведены в таблице 3.

Таблица 3 Названия и обозначения логических операций

Операцию инверсии можно выполнить чисто арифметически:   и алгебраически:   Из этих выражений следует, что инверсия x, т.е.  дополняет x до 1. Отсюда и возникло ещё одно название этой операции – дополнение. Отсюда же можно сделать вывод, что двойная инверсия приводит к исходному аргументу, т.е.   и это называется законом двойного отрицания.

Таблица 4 – Таблицы истинности основных функций двух переменных

X1	X2	Y	X1	X2	Y	X1	X2	Y	X1	X2	Y	X1	X2	Y
0	0	0	0	0	0	0	0	0	0	0	1	0	0	1
0	1	1	0	1	0	0	1	1	0	1	0	0	1	1
1	0	1	1	0	0	1	0	1	1	0	0	1	0	1
1	1	1	1	1	1	1	1	0	1	1	0	1	1	0

Дизъюнкция. В отличие от обычного арифметического или алгебраического суммирования здесь наличие двух единиц даёт в результате единицу. Поэтому при обозначении логического суммирования предпочтение следует отдать знаку (∨) вместо знака (+) [1].

Первые две строчки таблицы истинности операции дизъюнкции (x₁=0) определяют закон сложения с нулём: x ∨ 0 = x, а вторые две строчки (x₁ = 1) – закон сложения с единицей: x ∨ 1 = 1.

Конъюнкция. Таблица 4 убедительно показывает тождественность операций обычного и логическог  умножений. Поэтому в качестве знака логического умножения возможно использование привычного знака обычного умножения в виде точки [1].

Первые две строчки таблицы истинности операции конъюнкции определяют закон умножения на ноль: x·0 = 0, а вторые две – закон умножения на единицу: x·1 = x.

Исключающее ИЛИ. Под функцией «Исключающее ИЛИ» понимают следующее: единица на выходе появляется тогда, когда только на одном входе присутствует единица. Если единиц на входах две или больше, или если на всех входах нули, то на выходе будет нуль.

Надпись на обозначении элемента ИСКЛЮЧАЮЩЕЕ ИЛИ «=1» (Рисунок 1, г) как раз и обозначает, что выделяется ситуация, когда на входах одна и только одна единица.

Эта операция аналогична операции арифметического суммирования, но, как и другие логические операции, без образования переноса. Поэтому она имеет другое название сумма по модулю 2 и обозначение ⊕, сходное с обозначением арифметического суммирования.

Стрелка Пирса и  штрих Шеффера. Эти операции являются инверсиями операций дизъюнкции и конъюнкции и специального обозначения не имеют.

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

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

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

Например, в сложной логической функции   аргументами являются X₁∨X₂ и .

1.2.2 Логические элементы

Для реализации логических функций в устройствах цифровой обработки информации используются логические элементы. Условные графические обозначения (УГО) логических элементов, реализующих рассмотренные выше функции, приведены на рисунке 1.

Рисунок 1 – УГО логических элементов: а) Инвертор, б) ИЛИ, в) И, г) Исключающее ИЛИ, д) ИЛИ-НЕ, е) И-НЕ.

Сложные логические функции реализуются на основе простых логических элементов, путём их соответствующего соединения для реализации конкретной аналитической функции. Функциональная схема логического устройства, реализующего сложную функцию, , приведённую в предыдущем параграфе, приведена на рисунке 2.

Рисунок 2 – Пример реализации сложной логической функции

Как видно из рисунка 2, логическое уравнение показывает, из каких ЛЭ и какими соединениями можно создать заданное логическое устройство.

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

1.2.3 Законы и тождества алгебры логики

Математический аппарат алгебры логики позволяет преобразовать логическое выражение, заменив его равносильным с целью упрощения, сокращения числа элементов или замены элементной базы.

Законы:

1 Переместительный: X ∨ Y = Y ∨ X; X · Y = Y · X.

2 Cочетательный: X ∨ Y ∨ Z = (X ∨ Y) ∨ Z = X ∨(Y ∨ Z);  X · Y · Z = (X · Y) · Z = X· (Y· Z).

3 Идемпотентности: X ∨ X = X; X · X = X.

4 Распределительный: (X ∨ Y)· Z = X· Z ∨ Y· Z.

5 Двойное отрицание: .

6 Закон двойственности (Правило де Моргана):

Для преобразования структурных формул применяется ряд тождеств:

X ∨ X · Y = X; X(X ∨ Y) = X – Правила поглощения.

X· Y ∨ X·  = X, (X ∨ Y)·(X ∨ ) = X – Правила склеивания.

Правила старшинства логических операций.

1 Отрицание – логическое действие первой ступени.

2 Конъюнкция – логическое действие второй ступени.

3 Дизъюнкция – логическое действие третьей ступени.

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

2 Основы синтеза цифровых устройств

2.1 Последовательность операций при синтезе цифровых устройств комбинационного типа

1 Составление таблицы истинности комбинационного цифрового устройства (КЦУ) согласно его определения, назначения, словесного описания принципа работы.

2 Составление логической формулы согласно таблицы истинности.

3 Анализ полученной формулы с целью построения различных вариантов и нахождения наилучшего из них по тем или иным критериям.

4 Составление функциональной схемы КЦУ из элементов И, ИЛИ, НЕ.

2.2 Аналитическая запись логической формулы КЦУ

Запись в форме СДНФ (Совершенная дизъюнктивная нормальная форма).

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

Формула получается в два этапа:

а) Записывается логическая сумма произведений, в каждое из которых входят все независимые переменные. Количество слагаемых равно  числу наборов таблицы истинности, на которых логическая функция равна «1»;

б) ставится знак инверсии над теми независимыми переменными, которые равны «0» в рассматриваемом наборе.

Запись в форме СКНФ (Совершенная конъюнктивная нормальная форма).

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

Как и в предыдущем случае, формула получается в два этапа:

а) Записывается логическое произведение всех сомножителей; количество сомножителей равно числу наборов таблицы истинности, на которых логическая функция равна «0»;

б) ставится знак инверсии над теми независимыми переменными, которые равны «1» в рассматриваемом наборе.

Структурные формулы в виде СДНФ и СКНФ эквивалентны и, с помощью законов алгебры, логики могут быть преобразованы одна в другую.

Пример: Синтезировать мажоритарный логический элемент на три входа.

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

На основании данного словесного описания мажоритарного элемента составлена его таблица истинности (Таблица 5).

Таблица 5 – Таблица истинности мажоритарного элемента

0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1

На основе таблицы истинности записывается СДНФ или СКНФ функции, а затем составляется функциональная схема элемента.

СДНФ:

СКНФ:

Рисунок 3 Функциональная схема мажоритарного элемента

Функциональная схема элемента, составленная на основе функции СДНФ мажоритарного элемента, приведена на рисунке 3. Схема  состоит из 8 элементов, имеющих общее количество входов 19. Количество входов характеризует сложность схемы и называется «Число по Квайну». Схема составленная на основе функции СКНФ, также будет иметь 19 входов.

2.3 Понятие базиса

Любая, сколь угодно сложная логическая функция, представленная таблицей истинности, может быть представлена в форме СДНФ или СКНФ. Каждая из этих формул записана с помощью логического сложения, умножения и отрицания. Поэтому для реализации логических устройств, предназначенных для обработки цифровых сигналов, в общем случае необходимо иметь элементы, выполняющие операции И, ИЛИ, НЕ. Такой набор элементов называется функционально полной системой логических элементов  или логическим базисом. Это означает, что из комбинации логических элементов И, ИЛИ, НЕ, взятых в достаточном количестве, можно построить сколь угодно сложное цифровое устройство. Базис из элементов: И, ИЛИ, НЕ называется основным.

Однако, число необходимых элементов в такой системе можно уменьшить, исключив из неё либо элемент ИЛИ, либо элемент И. Например, в соответствии с теоремой де Моргана, имеем . Отсюда следует, что операцию логического ИЛИ можно заменить операцией И над инверсными значениями переменных, , а затем к результату применить операцию инверсии   и тем самым исключить элемент ИЛИ (Рисунок 4).

Рисунок 4 Реализация элемента ИЛИ на элементах НЕ, И

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

При схемной реализации функционально полных систем с минимальным логическим базисом идут по пути использования универсальных логических элементов: ИЛИ-НЕ, И-НЕ и И-ИЛИ-НЕ (Рисунок 5).

Рисунок 5 Универсальные логические элементы

Элемент ИЛИ-НЕ Рисунок 5,а) осуществляет логическую операцию , называемую также стрелкой Пирса. Элемент И-НЕ (Рисунок 5,б) осуществляет логическую операцию   и называется штрих Шеффера. Элемент И-ИЛИ-НЕ (Рисунок 5,в) осуществляет операцию   и является элементом сложного базиса.

Элементы универсальных базисов позволяют реализовать все три основные логические операции (Рисунок 6). Например, для осуществления операции НЕ с помощью элемента И-НЕ достаточно объединить входы   (рисунок 6,а). Аналогично и для элемента ИЛИ-НЕ.

Рисунок 6 Реализация функций НЕ, И и ИЛИ на элементах И-НЕ

При последовательном соединении элемента И-НЕ и инвертора осуществляется операция логического умножения:   (рисунок 6,б). Такое же соединение элементов ИЛИ-НЕ реализует операцию логического сложения: 

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

В общем случае логическая функция Y может зависеть от нескольких переменных X₁,X₂,…,X_n. Говорят, что функция Y определена, если известны её значения для всех возможных наборов переменных. Функция Y не определена, когда некоторые сочетания переменных по условию задачи невозможны. В этом случае её можно доопределить, приписав ей значение «1» либо «0» по соображениям удобства реализации.

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

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

2.4.1 Расчётный метод минимизации

Применение этого метода состоит в последовательном применении к некоторой формуле законов и правил тождественных  преобразований алгебры логики. При этом широко используют следующие приёмы: прибавление одного или нескольких членов, входящих в СДНФ, поскольку X ∨ X ∨ X = X; выделение членов, содержащих множитель ; использование правила склеивания и др. Получающаяся в результате минимизации алгебраическая формула называется тупиковой. Функция может иметь несколько тупиковых форм.

Пример: Минимизировать функцию СДНФ мажоритарного элемента (См. п.2.2) и реализовать его схему на элементах основного базиса.

Склеивая первые три минтерма с четвёртым, получаем ДНФ функции мажоритарного элемента, которая проще СДНФ:

Y = X₁·X₂ ∨ X₁·X₃ ∨ X₂·X₃

Минимизированная функциональная схема мажоритарного элемента приведена на рисунке 7.

Рисунок 7 Функциональная схема мажоритарного элемента, реализованная на основе минимизированной функции ДНФ

Из сравнения схем, приведённых на рисунках 3 и 7 следует, что в минимизированной схеме число по Квайну уменьшилось с 19 до 9.

Метод минимизирующих карт Карно

Карты Карно – это графическое представление таблиц истинности логических функций. Они содержат по 2ⁿ ячеек, где n – число логических переменных. Например, карта Карно для функции трёх переменных содержит 2ⁿ=2³=8 ячеек, для четырёх переменных – 2⁴=16 ячеек.

Карта размечается системой координат, соответствующих значениям входных переменных. Обратим особое внимание на то, что координаты столбцов (а также и строк, если n>3), следуют не в естественном порядке возрастания двоичных кодов, а так: 00 01 11 10. Это делается для того, чтобы соседние наборы (в том числе и столбцов 1 и 4) отличались лишь одной цифрой в каком-либо разряде.

Процесс минимизации заключается в формировании правильных прямоугольников, содержащих по 2^k ячеек, где k – целое число. В прямоугольники объединяются соседние ячейки, которые соответствуют соседним элементарным произведениям (т. е. отличаются только в одном разряде).

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

Пример: Минимизировать функцию трёх переменных, заданную таблицей истинности (таблица 6).

Таблица 6 Таблица истинности функции трёх переменных

0	0	0	0
0	0	1	1
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	0
1	1	1	0

СДНФ функции:

Составляем карту Карно и производим разметку её сторон:

Рисунок 8 Карта Карно функции 3-х переменных.

На карте Карно формируем два прямоугольника. Первый из них объединяет (как бы заключает в скобки) два первых минтерма (слагаемых), а второй – первое и третье слагаемые СДНФ минимизируемой функции, приведённой выше. Минтермы, объединённые в прямоугольники, отличаются только в одном разряде. Их неизменяемая часть, которая при минимизации расчётным методом выносится за скобки, и является минимизированным значением функции:

Таким образом, карта Карно позволяет поместить рядом, то есть в соседних ячейках, соседние элементарные произведения, отличающиеся только одним сомножителем.

Последовательность действий при минимизации:

1 Изображается карта Карно и производится разметка её сторон.

2 Ячейки карты Карно, соответствующие наборам переменных, обращающих функцию в «1», заполняются единицами, остальные – нулями.

3 Выбирается наилучшее покрытие карты прямоугольниками. Наилучшим считается покрытие, образованное минимальным числом прямоугольников, а если таких вариантов несколько, то выбирается тот, который даёт максимальную площадь прямоугольников.

Пример: Минимизировать функцию четырёх переменных, представленную картой Карно: (Рисунок 9).

Рисунок 9 Карта Карно функции 4-х переменных

Из карты Карно записываем минимизированное значение функции: