Гудилин А.Е., Барбасова Т.А. Теория цифровых автоматов
Подождите немного. Документ загружается.
МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ
ЮЖНО–УРАЛЬСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
681.3(07)
Л561
ТЕОРИЯ ЦИФРОВЫХ АВТОМАТОВ
Челябинск
2005
А.Е.Гудилин, Т.А. Барбасова
Учебное пособие по курсу
«Цифровые автоматы»
Южно-Уральский государственный
университет
Приборостроительный факультет
Кафедра Автоматики и управления
Челябинск
2005
2
3
СОДЕРЖАНИЕ
ÂÂÅÄÅÍÈÅ..................................................................................................................6
Ãëàâà 1..........................................................................................................................8
ËÎÃÈ×ÅÑÊÈÅ ÎÑÍÎÂÛ ÖÈÔÐÎÂÛÕ ÀÂÒÎÌÀÒÎÂ................................................8
1.1 Îñíîâíûå ïîíÿòèÿ àëãåáðû ëîãèêè..........................................................................8
1.2 Áàçèñ È, ÈËÈ, ÍÅ. Ñâîéñòâà ýëåìåíòàðíûõ ôóíêöèé àëãåáðû ëîãèêè.............11
1.3 Ñïîñîáû îïèñàíèÿ áóëåâûõ ôóíêöèé....................................................................14
1.3.1 Òàáëè÷íîå îïèñàíèå áóëåâûõ ôóíêöèé.........................................................14
1.3.2 Àíàëèòè÷åñêîå îïèñàíèå áóëåâûõ ôóíêöèé.................................................16
1.3.3 ×èñëîâàÿ ôîðìà ïðåäñòàâëåíèÿ áóëåâûõ ôóíêöèé.......................................18
1.3.4 Ãðàôè÷åñêàÿ ôîðìà ïðåäñòàâëåíèÿ áóëåâûõ ôóíêöèé...............................18
1.3.5 Ãåîìåòðè÷åñêîå ïðåäñòàâëåíèå áóëåâûõ ôóíêöèé.....................................19
1.4 Ìèíèìèçàöèÿ ôóíêöèé àëãåáðû ëîãèêè.................................................................24
1.4.1 Ìèíèìèçàöèÿ ñ ïîìîùüþ ìèíèìèçèðóþùèõ êàðò................................................24
1.4.2 Ìèíèìèçàöèÿ ôóíêöèé àëãåáðû ëîãèêè ïî ìåòîäó Êâàéíà...............................25
1.4.3 Ìèíèìèçàöèÿ ôóíêöèé àëãåáðû ëîãèêè..........................................................32
ïî ìåòîäó Êâàéíà - Ìàê-Êëàñêè.............................................................................32
1.5 Ýëåìåíòíàÿ áàçà äëÿ ïîñòðîåíèÿ êîìáèíàöèîííûõ ñõåì..........................................36
1.5.1 Ëîãè÷åñêèå ýëåìåíòû È, ÈËÈ, ÍÅ.............................................................37
1.5.2 Ïðèìåðû òåõíè÷åñêîé ðåàëèçàöèè áóëåâûõ ôóíêöèé..................................42
1.5.3 Ïðîãðàììèðóåìûå ëîãè÷åñêèå ìàòðèöû (ÏËÌ)...............................................44
Ãëàâà 2........................................................................................................................53
ÑÈÍÒÅÇ ÖÈÔÐÎÂÛÕ ÀÂÒÎÌÀÒÎÂ......................................................................53
2.1 Îïðåäåëåíèå àáñòðàêòíîãî öèôðîâîãî àâòîìàòà...................................................53
2.2 Ìåòîäû îïèñàíèÿ öèôðîâûõ àâòîìàòîâ..................................................................57
2.3 Ñèíõðîííûå è àñèíõðîííûå öèôðîâûå àâòîìàòû....................................................61
2.4 Ñâÿçü ìåæäó ìàòåìàòè÷åñêèìè ìîäåëÿìè............................................................62
öèôðîâûõ àâòîìàòîâ Ìèëè è Ìóðà...............................................................................62
2.5 Ìèíèìèçàöèÿ àáñòðàêòíûõ öèôðîâûõ àâòîìàòîâ.................................................72
4
2.5.1 Ìèíèìèçàöèÿ àáñòðàêòíîãî àâòîìàòà Ìèëè...................................................72
2.5.2 Ìèíèìèçàöèÿ àáñòðàêòíîãî àâòîìàòà Ìóðà....................................................81
2.6 Ñòðóêòóðíûé ñèíòåç àâòîìàòîâ.........................................................................86
2.6.1 Ýëåìåíòàðíûå àâòîìàòû ïàìÿòè...................................................................86
2.6.2 Ñèíõðîíèçàöèÿ â öèôðîâûõ àâòîìàòàõ........................................................92
2.7 Ñòðóêòóðíûé ñèíòåç öèôðîâûõ àâòîìàòîâ ïî òàáëèöàì.....................................96
2.8 Ñòðóêòóðíûé ñèíòåç öèôðîâîãî àâòîìàòà ïî ãðàôó.........................................109
Ãëàâà 3......................................................................................................................114
ÌÈÊÐÎÏÐÎÃÐÀÌÌÍÛÅ ÀÂÒÎÌÀÒÛ........................................................................114
3.1 Äåêîìïîçèöèÿ óñòðîéñòâ îáðàáîòêè öèôðîâîé èíôîðìàöèè.................................114
3.2 Óïðàâëÿþùèå àâòîìàòû......................................................................................117
3.3 Ïðèíöèï äåéñòâèÿ óïðàâëÿþùåãî àâòîìàòà ñ õðàíèìîé â ïàìÿòè ëîãèêîé è
ìèêðîïðîãðàììíîå óïðàâëåíèå....................................................................................120
3.3.1 Ãîðèçîíòàëüíîå ìèêðîïðîãðàììèðîâàíèå......................................................124
3.3.2 Âåðòèêàëüíîå ìèêðîïðîãðàììèðîâàíèå........................................................125
3.3.3 Ñìåøàííîå ìèêðîïðîãðàììèðîâàíèå...............................................................126
3.4 Óïðàâëÿþùèå àâòîìàòû ñ «æ¸ñòêîé ëîãèêîé»..................................................128
3.5 Ãðàô - ñõåìû ìèêðîïðîãðàììíûõ àâòîìàòîâ.........................................................130
3.6 Ñèíòåç ìèêðîïðîãðàììíûõ àâòîìàòîâ ïî ãðàô - ñõåìå àëãîðèòìà.........................137
3.6.1 Ñèíòåç ìèêðîïðîãðàììíîãî àâòîìàòà Ìèëè.....................................................137
3.6.2 Ñèíòåç ìèêðîïðîãðàììíîãî àâòîìàòà Ìóðà......................................................142
3.6.3 Ìèíèìèçàöèÿ ìèêðîïðîãðàììíûõ àâòîìàòîâ.....................................................147
Çàêëþ÷åíèå................................................................................................................148
ËÈÒÅÐÀÒÓÐÀ......................................................................................................149
5
ВВЕДЕНИЕ
В курсе «Цифровая схемотехника» рассматриваются теоретические основы
построения цифровых автоматов как преобразователей двоичных цифровых
сигналов. Все системы обработки цифровой информации (в том числе и
цифровые вычислительные машины - ЭВМ) могут в общем виде представлены
как кодопреобразователи (рис. 1) .
А
x
n-1
x
n-2
x
n-3
x
0
y
m-1
y
m-2
y
m-3
y
0
x
n-1
x
n-2
x
n-3
..x
0
- входной цифровой n - разрядный двоичный код;
y
m-1
y
m-2
y
m-3
...y
0
- выходной цифровой m - разрядный двоичный код;
А - оператор преобразования.
Рис.1. Обобщённая структура системы переработки
цифровой информации
Особенностью цифрового автомата является зависимость оператора
преобразования А от предыдущих состояний кодопреобразователя, то есть
наличие памяти у цифрового автомата. В частном случае отсутствия памяти у
цифрового автомата, он является логической схемой. Таким образом,
предметами исследования в теории цифровых автоматов являются как
собственно цифровые автоматы (системы с памятью), так и автоматы без
памяти или логические схемы.
Наиболее разработана теория цифровых автоматов применительно к
канонической структуре цифрового автомата, представленной на рис.2. Для
6
дальнейшего рассмотрения используется только эта структура цифрового
автомата.
КС
вх
П
КС
вых
X
B
A
Y
Рис.2.
Каноническая структурная схема цифрового автомата
КС
вх
- входная комбинационная схема;
П - память; Кс
вых
- выходная комбинационная схема;
X - входной цифровой код; В - код возбуждения памяти;
А - код состояния памяти; Y - выходной код.
По структурной схеме цифрового автомата видно, что входные коды
входной и выходной комбинационных схем получаются в результате
конкатенации (объединения) входного кода и кода состояния памяти цифрового
автомата.
7
Глава 1
ЛОГИЧЕСКИЕ ОСНОВЫ ЦИФРОВЫХ АВТОМАТОВ
1.1 Основные понятия алгебры логики
Понятие цифрового автомата было введено как модель для описания
функционирования устройств, предназначенных для переработки цифровой или
дискретной информации.
Для формального описания цифровых автоматов применяется аппарат
алгебры логики, созданной английским математиком Дж. Булем (1815-1864).
Поэтому алгебру логики называют алгеброй Буля или булевой алгеброй.
В алгебре логики применительно к описанию цифровых автоматов,
работающих в двоичном представлении кодов (или цифровой информации)
основными понятиями являются логическая (булева) переменная и логическая
функция (функция алгебры логики - ФАЛ).
Логическая (булева) переменная - такая величина x, которая может
принимать только два значения : x = {0,1}.
Логическая функция (функция алгебры логики - ФАЛ) - функция многих
аргументов f(x
n-1
, x
n-2,
,
..., x
0
), принимающая значения равные нулю или единице
на наборах логических переменных x
n-1
, x
n-2,
,
..., x
0
.
В дальнейшем в формальных описаниях наборов переменных и
логических функций сами наборы переменных интерпретируются как двоичные
коды (числа). В двоичных кодах расположение логических переменных
упорядочено в порядке уменьшения индекса слева направо и каждая логическая
переменная имеет вес в зависимости от позиции в коде, увеличивающийся
справа налево. Вес каждой i - той логической переменной, являющейся
значением разряда двоичного числа равен 2
i
(i = 0, ... , n-1).
Для n - разрядного кода общее количество уникальных наборов
переменных
8
N = 2
n
; (1)
Максимальное числовое значение двоичного кода равно
A
макс
= 2
n
-1; (2)
Значения всех логических функций от одной переменной представлены в
таблице 1.Таблица 1
x f
0
(x) f
1
(x) f
2
(x) f
3
(x)
0 0 0 1 1
1 0 1 0 1
Функция f
0
(x) называется константой нуля, а функция f
3
(x) - константой
единицы. Функция f
1
(x), повторяющая значения логической переменной, -
тождественная функция (f
1
(x) º x), а функция f
2
(x), принимающая значения,
обратные значениям переменной x, - логическое отрицание или инверсия (НЕ)
(f
2
(x) =
x
).
Значения всех логических функций от двух переменных представлены в
таблице 2. Для функции двух переменных, согласно ф.(1), существует четыре
уникальных набора переменных. Функции отличаются друг от друга набором
значений 0 и 1 в четырех разрядах кода значений функции. Общее количество
функций на n - местном или n - разрядном наборе переменных равно
n
2
f
2N
; (3)
В таблице 2 приведены примеры аналитической записи некоторых
булевых функций с использованием других булевых функций, то есть
существует такой набор булевых функций, из которого можно сконструировать
любую булеву функцию, равносильную заданной.
Две функции равносильны друг другу, если они принимают на всех
возможных наборах переменных одни и те же значения.
Аналитически это свойство описывается следующей формулой:
9
f
1
(x
n-1
, x
n-2,
,
..., x
0
) = f
2
(x
n-1
, x
n-2,
,
..., x
0
); (4)
Обе функции в ф.(4) могут иметь разные формы аналитической записи, но
практически наиболее выгодной будет самая простая форма записи.
Таблица 2
Функция
x
2
x
1
Примечания
00
01
10
11
f
0
0 0 0 0 константа нуля
f
1
0 0 0 1 x
2
x
1
- конъюнкция
f
2
0 0 1 0 x
2
1
x
- запрет x
1
f
3
0 0 1 1
2212
xxxx
1
x
f
4
0 1 0 0
12
xx
- запрет x
2
f
5
0 1 0 1
11212
xxxxx
f
6
0 1 1 0
12
xx
- сложение по модулю 2
f
7
0 1 1 1 x
2
x
1
- дизъюнкция
f
8
1 0 0 0 x
2
x
1
- функция Пирса
f
9
1 0 0 1 x
2
º x
1
- равнозначность
f
10
1 0 1 0
11212
xxxxx
f
11
1 0 1 1 x
1
x
2
- импликация
f
12
1 1 0 0
21212
xxxxx
f
13
1 1 0 1 x
2
x
1
- импликация
f
14
1 1 1 0 x
1
/x
2
- функция Шеффера
f
15
1 1 1 1 константа единицы
Система булевых функций W называется функционально полной, если для
любой булевой функции n - переменных f(x
n-1
, x
n-2,
,
..., x
0
) может быть построена
равносильная ей функция комбинированием булевых переменных x
n-1
, x
n-2,
,
..., x
0
10