Прикладная теория цифровых автоматов
Министерство образования и науки Украины
Одесский национальный политехнический университет
Институт компьютерных систем
Кафедра "Компьютерной интеллектуальной системы и сети"
Курсовая работа
по дисциплине
«Прикладная теория цифровых автоматов»
Выполнила студентка
группа ЗАМ-071
Топорок Ольга Павловна
Проверил:
Милейко Игорь Генрихович
Одесса – 2009
Введение
Потребность в вычислениях возникла у людей на самых ранних стадиях развития человеческого общества. Причем с самого начала для облегчения счета люди использовали различные приспособления. Многие из них были весьма интересными и остроумными по принципу действия, но все они обязательно требовали, чтобы в процессе вычислений активно участвовал человек-оператор. Качественно новый этап развития вычислительной техники наступил с изобретением и созданием электронных вычислительных машин, которые работают автоматически, без участия человека, в соответствии с заранее заданной программой. Появление таких машин вызвано объективными условиями современного развития науки, техники и народного хозяйства. Во многих областях человеческой деятельности уже в середине ХХ века объем и сложность вычислительных работ настолько возросли, что решение некоторых задач без применения вычислительной техники было бы практически не возможным. В настоящее время электронные вычислительные машины применяются во многих областях науки, техники и народного хозяйства. В основном они используются: для решения сложных математических и инженерных задач, в качестве управляющих машин в промышленности и военной технике, в сфере обработки информации.
Задание к курсовой работе
- Синтезировать комбинационную схему, что реализуется заданной функцией 5 переменных.
- По результатом синтеза построить функциональную схему с использованием заданного базиса.
- Проанализировать работу синтезированной схемы методом p-алгоритма.
- Спроектировать руководящий автомат Мили по заданной граф-схемой алгоритма. Построить принципиальную схему автомата с использованием элементов КР1533 серии.
- Спроектировать руководящий автомат Мура по заданной граф-схемой алгоритма. Построить принципиальную схему автомата с использованием элементов КР1533 серии.
Булевы функции
Наиболее простым и наиболее важным классом однородных логических функций является класс двузначных-булевых функций.
Определение: Буквой функцией называется однородная логическая функция, принимающая значения из двухэлементного булева множества В={0, 1} или В={ложь, истина}.
Так как булева функция - однородна, то любой ее аргумент принимает значения из В={0, 1} или В={ложь, истина}, область определения булевой функции от ²n² переменных (аргументов) множество слов длины ²n². Общее число всевозможных двоичных наборов длины ²n² равно 2n . Число всевозможных булевых функций от ²n² аргументов равно 22^n . Любая булева функция может быть задана таблицей истинности (соответствия), в левой части которой перечислены все 2n наборов значений переменных, а в правой части - значения функции на этих наборах.
Существуют три способа
Табличный способ. Способ предполагает наличие таблицы истинности (соответствия).
Аналитический способ. Нормальные формы.
Определение: Дизъюнктивная нормальная форма (ДНФ) - это дизъюнкция конечного числа различных членов, каждый из которых представляет собой конъюнкцию конечного числа отдельных переменных или их отрицаний, входящих в данный член не более одного раза.
Определение: Конъюнктивная нормальная форма (КНФ) - это конъюнкция конечного числа различных членов, каждый из которых представляет собой дизъюнкцию конечного числа отдельных переменных или их отрицаний, входящих в данный член не более одного раза.
Определение: Члены ДНФ, представляющие собой элементарные конъюнкции из ²k² букв, называются минтермами к-го ранга. Члены КНФ, представляющие собой элементарные дизъюнкции из ²k² букв, называются макстермами к-го ранга.
Совершенные нормальные формы
Определение: Если в каждом члене нормальной дизъюнктивной или конъюнктивной формы представлены все ²n² переменных (в прямом или инверсном виде) от которых зависит булева функция, то такая форма называется совершенной дизъюнктивной или конъюнктивной нормальной формой (СДНФ или СКНФ).
Лемма: Любая булева функция, не являющаяся тождественно равной нулю, имеет одну и только одну СДНФ. Любая булева функция, не являющаяся тождественно равной единице, имеет одну и только одну СКНФ.
Минтермы СДНФ называют конституентами единицы. Макстермы СКНФ называют конституентами нуля. Конституента ²1² обращается в единицу только при одном соответствующем ей наборе значений переменных, который получается, если все переменные конститунты принять равными единице, а для всех инверсий конституенты переменные принять равными нулю. Конституента ²0² обращается в нуль только при одном соответствующем ей наборе значений переменных, который получается, если все переменные конституенты принять равными нулю, а для всех инверсий конституенты переменные принять равными единице.
Так как СДНФ является дизъюнкцией конституент ²1², то можно утверждать, что представляющая ее булева функция f(x1, x2,..., xn) обращается в единицу только при наборах значений переменных, соответствующих хотя бы одной единице этих конституент. На остальных наборах эта функция обращается в нуль.
Аналогично, так как СКНФ является конъюнкцией конституент ²0², можно утверждать, что ее булева функция f(x1, x2,..., xn) обращается в нуль только при наборах значений переменных, соответствующих хотя бы одному нулю этих конституент. На остальных наборах эта функция обращается в единицу.
Правила задания булевой функции в виде СДНФ, СКНФ
Для задания любой булевой функции в виде СДНФ необходимо записать дизъюнкцию конституент ²1² для всех наборов переменных, на которых функция принимает единичное значение.
Для задания любой булевой функции в виде СКНФ необходимо записать конъюнкцию конституент ²0² для всех наборов переменных, на которых функция принимает нулевое значение.
Такое представление булевой функции называют аналитическим представлением в виде СДНФ или СКНФ.
Пример: Таблица истинности (см. табл. 1.), СДНФ и СКНФ булевой функции от трех переменных
Таблица 1
X1 |
X2 |
X3 |
Y |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
у =`х1`х2`х3Ú`х1х2`х3Ú`х1х2х3Úх1
у =(х1Úх2Ú`х3)(`х1Úх2Ú`х3)(`х1Ú`
Очевидно, что для всюду определенной булевой функции СДНФ и СКНФ равносильны, т.е. БФ(СДНФ)=БФ(СКНФ). Аналитическое задание булевой функции возможно и в ДНФ и КНФ, в тупиковых, минимальных и др. формах.
Определяем булеву функцию.
Булева функция 5 переменных y = f(Х1, Х2, Х3, Х4, Х5) задается своими значениями, что определяется 7-розрядными двоичными эквивалентами чисел, которые выбираем из таблицы по числу(А=19=>39) и месяцу (В=08=>42) рождения студента и двум последним цифрам номера зачетной книжки (С=12=>07). Значения функции на конкретных наборах выбираем по правилу:
-на наборах 0…6 по значению А;
-на наборах 7…13 по значению В;
-на наборах 14…20 по значению С;
-на наборах 21…27 по значению А+В+С;
-на наборах
28…31 функция принимает не
Кроме того, для всех двоичных эквивалентов в разрядах слева от старшей значимой единицы необходимо поставить символ не определенного положения Х и считать, что функция на таких наборах также имеет не определенной положение.
Значения, принимаемые булевой функцией, представлены в табличном виде (см. таблица 2), где
y= Ú (1,4,5,6,8,10,12,18,19,20,21,
y= Ù (2,3,9,11,13,22,25,26,27);
у= х (0,7,14,15,16,17,28,29,30,31).
16 |
8 |
4 |
2 |
1 |
f |
||
№ набора |
Х1 |
Х2 |
Х3 |
Х4 |
Х5 | ||
0 |
0 |
0 |
0 |
0 |
0 |
X |
А |
1 |
0 |
0 |
0 |
0 |
1 |
1 | |
2 |
0 |
0 |
0 |
1 |
0 |
0 | |
3 |
0 |
0 |
0 |
1 |
1 |
0 | |
4 |
0 |
0 |
1 |
0 |
0 |
1 | |
5 |
0 |
0 |
1 |
0 |
1 |
1 | |
6 |
0 |
0 |
1 |
1 |
0 |
1 | |
7 |
0 |
0 |
1 |
1 |
1 |
X |
В |
8 |
0 |
1 |
0 |
0 |
0 |
1 | |
9 |
0 |
1 |
0 |
0 |
1 |
0 | |
10 |
0 |
1 |
0 |
1 |
0 |
1 | |
11 |
0 |
1 |
0 |
1 |
1 |
0 | |
12 |
0 |
1 |
1 |
0 |
0 |
1 | |
13 |
0 |
1 |
1 |
0 |
1 |
0 | |
14 |
0 |
1 |
1 |
1 |
0 |
X |
С |
15 |
0 |
1 |
1 |
1 |
1 |
X | |
16 |
1 |
0 |
0 |
0 |
0 |
X | |
17 |
1 |
0 |
0 |
0 |
1 |
X | |
18 |
1 |
0 |
0 |
1 |
0 |
1 | |
19 |
1 |
0 |
0 |
1 |
1 |
1 | |
20 |
1 |
0 |
1 |
0 |
0 |
1 | |
21 |
1 |
0 |
1 |
0 |
1 |
1 |
А+В+С |
22 |
1 |
0 |
1 |
1 |
0 |
0 | |
23 |
1 |
0 |
1 |
1 |
1 |
1 | |
24 |
1 |
1 |
0 |
0 |
0 |
1 | |
25 |
1 |
1 |
0 |
0 |
1 |
0 | |
26 |
1 |
1 |
0 |
1 |
0 |
0 | |
27 |
1 |
1 |
0 |
1 |
1 |
0 | |
28 |
1 |
1 |
1 |
0 |
0 |
X |
Х |
29 |
1 |
1 |
1 |
0 |
1 |
X | |
30 |
1 |
1 |
1 |
1 |
0 |
X | |
31 |
1 |
1 |
1 |
1 |
1 |
X |
Минимизация заданной булевой функции методом Квайна-МакКласки.
Минимизация схем в булевом базисе сводится к поиску минимальной ДНФ, которой соответствует минимальное покрытие. Для оценки сложности булевой функции используется критерий Квайна, формулируемый следующим образом:
Утверждение: Минимальной функции соответствует минимальная цена по Квайну, определяемая как С=åqs(n-s), где qs - число S-кубов, образующих покрытие данной функции от n-переменных, s - размерность кубов.
Минимальное покрытие характеризуется минимальной ценой.
Задача минимизации решается в два шага:
На первом шаге находится сокращенное покрытие, включающее все S-кубы максимальной размерности и не содержащее ни одного куба, который покрывается каким-либо кубом этого покрытия.
Соответствующую сокращенному покрытию ДНФ называют сокращенной ДНФ а ее минтермы - простыми импликантами. Для любой булевой функции сокращенное покрытие является единственным, но оно может быть избыточным вследствие того, что некоторые из кубов покрываются совокупностями других кубов.
На втором шаге осуществляется переход от сокращенной ДНФ к тупиковой ДНФ, образуемой из сокращенной ДНФ исключением всех избыточных кубов, без которых оставшаяся совокупность кубов еще образует покрытие данной функции, но при дальнейшем исключении любого из кубов получаемая совокупность кубов не покрывает заданную функцию, т.е. перестает быть покрытием.
Куб сокращенного покрытия, который покрывает вершины данной функции, не покрываемые никакими другими кубами сокращенного покрытия не может оказаться избыточным и всегда войдет в минимальное покрытие. Такой куб, как и соответствующая ему импликанта, называется экстремалью или существенной импликантой, а покрываемые ими вершины - отмеченными вершинами. Множество экстремалей образуют ядро покрытия.
При переходе от сокращенного покрытия к минимальному сначала выделяется ядро покрытия. Если множество экстремалей не образует покрытия, то оно дополняется тем или иным способом до покрытия кубами из сокращенного покрытия. На множестве полученных таким образом тупиковых покрытий выбирается минимальное.
СДНФ Þ СкДНФ Þ {ТДНФ} Þ {МДНФ}
Метод Квайна
В качестве исходной формы булевой
функции для минимизации
аxiÚa`xi=a
Множеству конституент «1» соответствует совокупность 0-кубов К0, операции склеивания соответствует объединение двух 0-кубов, отличающихся только одной координатой. Результатом такого объединения является 1-куб, в котором различные координаты исходных 0-кубов замещены символом ´.
Сравнивая попарно все 0-кубы, получаем множество 1-кубов К1. Применяя таким же образом к множеству К1 операцию склеивания, находим множество 2-кубов К2 и т.д. Этот процесс продолжается до тех пор, пока полученное из множества КS очередное множество КS+1 не окажется пустым (или не будет получен n-куб, представляющий функцию – константу «1»). В результате получается комплекс кубов, состоящий из множеств КS:
К={К0, К1,..., КS}, где s£n-1.
Для выделения из К множества простых импликант ZÌK при каждой операции склеивания тем или иным способом отмечаются те кубы, которые объединяются в кубы высшей размерности. Очевидно, что неотмеченные кубы и образуют множество простых импликант Z, именуемое сокращенной ДНФ.
На следующем шаге при извлечении экстремалей используется таблица покрытий. Ее строки соответствуют простым импликантам, а столбцы - конституентам «1» (0-кубам) данной функции. В клетке таблицы ставится метка, если простая импликанта, соответствующая данной строке, покрывает вершину, соответствующую данному столбцу клетки. Экстремалям соответствуют те строки таблицы, которые содержат единственную метку в каком-либо столбце. Удаляя строки экстремалей и все столбцы, в которых данные строки имеют метки, получаем сокращенную таблицу покрытий.
Из сокращенной таблицы покрытий тем или иным способом выбираются простые импликанты, дополняющие выделенное множество экстремалей до тупиковых покрытий. Метод Квайна не формализует этот шаг в виде какой-либо процедуры. На множестве всех тупиковых покрытий определяется минимальные покрытия, которых может быть несколько.
Алгебраический метод получения минимального покрытия (алгоритм Петрика)Выбор минимального покрытия на заключительном этапе формализуется с помощью алгебраического метода, предложенного Петриком. Исходная форма для алгоритма – таблица покрытий. Простые импликанты обозначаются символами, например, буквами латинского алфавита. В каждом столбце таблицы записывается дизъюнкция простых импликант, покрывающих соответствующий 0-куб. Покрытию функции соответствует конъюнкция всех записанных дизъюнкций векторов. Упрощая полученное выражение с помощью тождеств булевой алгебры, получаем некоторую ДНФ, каждый член которой соответствует некоторому тупиковому покрытию. Выбирая те из них, которые содержат минимальное количество букв, находим минимальные покрытия.
Алгебраические преобразования упрощаются, если исходить из сокращенной таблицы покрытий, получаемой после выделения экстремалей. Тогда результатом таких преобразований являются множества простых импликант, дополняющих совокупность экстремалей до тупиковых покрытий. Минимальное из этих дополнений совместно с ядром образует минимальное покрытие булевой функции.
Метод Квайна-МакКласки
Недостатком метода Квайна является большое число сравнений, проводимое между импликантами каждого из кубов КS. Метод Квайна-МакКласки является модификацией метода Квайна, позволяющей уменьшить число сравнений. Для этого каждое множество КS разбивается на классы, в каждом из которых содержатся S-кубы с одинаковым числом единиц. Классы упорядочиваются, например, по возрастанию числа единиц. Так как, склеиваться могут только такие два S-куба, число единиц в которых отличается на одну единицу, то достаточно ограничиться по парным сравнением S-кубов некоторого класса с S-кубами соседнего класса. В остальном модификация работает, как и метод Квайна.
Найдем минимальную
K0= |
Х1 |
Х2 |
Х3 |
Х4 |
Х5 |
f |
0 |
0 |
0 |
0 |
0 |
0 |
X |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
4 |
0 |
0 |
1 |
0 |
0 |
1 |
5 |
0 |
0 |
1 |
0 |
1 |
1 |
6 |
0 |
0 |
1 |
1 |
0 |
1 |
7 |
0 |
0 |
1 |
1 |
1 |
X |
8 |
0 |
1 |
0 |
0 |
0 |
1 |
10 |
0 |
1 |
0 |
1 |
0 |
1 |
12 |
0 |
1 |
1 |
0 |
0 |
1 |
14 |
0 |
1 |
1 |
1 |
0 |
X |
15 |
0 |
1 |
1 |
1 |
1 |
X |
16 |
1 |
0 |
0 |
0 |
0 |
X |
17 |
1 |
0 |
0 |
0 |
1 |
X |
18 |
1 |
0 |
0 |
1 |
0 |
1 |
19 |
1 |
0 |
0 |
1 |
1 |
1 |
20 |
1 |
0 |
1 |
0 |
0 |
1 |
21 |
1 |
0 |
1 |
0 |
1 |
1 |
23 |
1 |
0 |
1 |
1 |
1 |
1 |
24 |
1 |
1 |
0 |
0 |
0 |
1 |
28 |
1 |
1 |
1 |
0 |
0 |
X |
29 |
1 |
1 |
1 |
0 |
1 |
X |
30 |
1 |
1 |
1 |
1 |
0 |
X |
31 |
1 |
1 |
1 |
1 |
1 |
X |
Находим сокращенную ДНФ.
K'0= |
K'1= |
K'2= |
K'3= |
K'4= |
Æ | ||||
~ |
00000 |
0000x |
00x0x |
x0x0x |
|||||
00001 |
00x00 |
x000x |
xxx00 |
||||||
00100 |
0x000 |
0xx00 |
|||||||
01000 |
x0000 |
x0x00 |
|||||||
~ |
10000 |
00x01 |
xx000 |
||||||
00101 |
x0001 |
x0x01 |
|||||||
00110 |
001x0 |
10x0x |
|||||||
01010 |
0x100 |
001xx |
|||||||
01100 |
x0100 |
0x1x0 |
|||||||
~ |
10001 |
010x0 |
xx100 |
||||||
10010 |
01x00 |
x010x |
|||||||
10100 |
x1000 |
01xx0 |
|||||||
11000 |
1000x |
100xx |
|||||||
~ |
00111 |
100x0 |
1xx00 |
||||||
~ |
01110 |
10x00 |
x01x1 |
||||||
10011 |
1x000 |
0x11x |
|||||||
10101 |
001x1 |
x11x0 |
|||||||
~ |
11100 |
x0101 |
10xx1 |
||||||
~ |
01111 |
0x110 |
1x10x |
||||||
10111 |
0011x |
xx111 |
|||||||
~ |
11101 |
01x10 |
x111x |
||||||
~ |
11110 |
011x0 |
1x1x1 |
||||||
~ |
11111 |
100x1 |
111xx |
||||||
10x01 |
|||||||||
1001x |
|||||||||
1010x |
|||||||||
1x100 |
|||||||||
11x00 |
|||||||||
0x111 |
|||||||||
x0111 |
|||||||||
0111x |
|||||||||
x1110 |
|||||||||
10x11 |
|||||||||
1x101 |
|||||||||
1110x |
|||||||||
111x0 |
|||||||||
x1111 |
|||||||||
1x111 |
|||||||||
111x1 |
|||||||||
1111x |
Строим таблицу покрытия (см. таблица 3.) и определяем ядро булевой функции.
00001 |
00100 |
01000 |
00101 |
00110 |
01010 |
01100 |
10010 |
10100 |
11000 |
10011 |
10101 |
10111 |
||
x0x0x |
~ |
~ |
~ |
~ |
~ |
A | ||||||||
xxx00 |
~ |
~ |
~ |
~ |
~ |
B | ||||||||
001xx |
~ |
~ |
~ |
C | ||||||||||
0x1x0 |
~ |
~ |
~ |
D | ||||||||||
01xx0 |
~ |
~ |
~ |
E | ||||||||||
100xx |
~ |
~ |
F | |||||||||||
x01x1 |
~ |
~ |
~ |
G | ||||||||||
0x11x |
~ |
H | ||||||||||||
x11x0 |
~ |
I | ||||||||||||
10xx1 |
~ |
~ |
~ |
J | ||||||||||
1x10x |
~ |
~ |
K | |||||||||||
xx111 |
~ |
L | ||||||||||||
x111x |
M | |||||||||||||
1x1x1 |
~ |
~ |
N | |||||||||||
111xx |
O | |||||||||||||
CDH |
E |
F |
FJ |
GJLN |
Строим сокращенную таблицу покрытия (см. таблица 4)
00110 |
01010 |
10010 |
10011 |
10111 |
||
001xx |
~ |
C | ||||
0x1x0 |
~ |
D | ||||
01xx0 |
~ |
E | ||||
100xx |
~ |
~ |
F | |||
x01x1 |
~ |
G | ||||
0x11x |
~ |
H | ||||
10xx1 |
~ |
~ |
J | |||
xx111 |
~ |
L | ||||
1x1x1 |
~ |
N | ||||
CDH |
E |
F |
FJ |
GJLN |
Существует две экстремали – х0х0х и ххх00. Из сокращенной таблицы покрытий, включающей 6, 7, 9, 12, 14 столбцы и 3-8, 10, 12, 14 строки, следует:
(CÚDÚH) (GÚJÚLÚN)(FÚJ)ÙFÙE = (CGÚCJÚCLÚCNÚDGÚDJÚDLÚDNÚHGÚHJ
Таким образом, существует двенадцать тупиковых покрытий:
ТДНФ1 |
= |
x0x0x |
ТДНФ2 |
= |
x0x0x |
ТДНФ3 |
= |
x0x0x |
ТДНФ4 |
= |
x0x0x | |||
xxx00 |
xxx00 |
xxx00 |
xxx00 | |||||||||||
01xx0 |
01xx0 |
01xx0 |
01xx0 | |||||||||||
100xx |
100xx |
100xx |
100xx | |||||||||||
001xx |
001xx |
001xx |
001xx | |||||||||||
x01x1 |
10xx1 |
xx111 |
1x1x1 | |||||||||||
ТДНФ5 |
= |
x0x0x |
ТДНФ6 |
= |
x0x0x |
ТДНФ7 |
= |
x0x0x |
ТДНФ8 |
= |
x0x0x | |||
xxx00 |
xxx00 |
xxx00 |
xxx00 | |||||||||||
01xx0 |
01xx0 |
01xx0 |
01xx0 | |||||||||||
100xx |
100xx |
100xx |
100xx | |||||||||||
0x1x0 |
0x1x0 |
0x1x0 |
0x1x0 | |||||||||||
x01x1 |
10xx1 |
xx111 |
1x1x1 | |||||||||||
ТДНФ9 |
= |
x0x0x |
ТДНФ10 |
= |
x0x0x |
ТДНФ11 |
= |
x0x0x |
ТДНФ12 |
= |
x0x0x | |||
xxx00 |
xxx00 |
xxx00 |
xxx00 | |||||||||||
01xx0 |
01xx0 |
01xx0 |
01xx0 | |||||||||||
100xx |
100xx |
100xx |
100xx | |||||||||||
0x11x |
0x11x |
0x11x |
0x11x | |||||||||||
x01x1 |
10xx1 |
xx111 |
1x1x1 |
