Прикладная теория цифровых автоматов

Министерство  образования и науки Украины

Одесский  национальный политехнический университет

Институт  компьютерных систем

 

 

 

 

 

 

Кафедра "Компьютерной интеллектуальной системы и сети"

 

 

 

 

 

 

Курсовая работа

 

по дисциплине

«Прикладная теория цифровых автоматов»

 

 

 

 

 

 

 

 

 

 

 

 

Выполнила студентка

группа ЗАМ-071

Топорок Ольга Павловна

Проверил:

Милейко Игорь Генрихович

 

 

 

Одесса – 2009

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

 

 

Потребность в  вычислениях возникла у  людей  на  самых  ранних  стадиях развития человеческого общества. Причем с самого  начала для облегчения счета люди использовали различные  приспособления. Многие из них были весьма интересными и  остроумными  по  принципу действия, но все они обязательно  требовали,  чтобы  в процессе вычислений активно участвовал человек-оператор. Качественно новый этап развития вычислительной  техники  наступил  с  изобретением и созданием электронных вычислительных машин,  которые работают автоматически, без участия человека, в  соответствии с заранее заданной программой. Появление таких машин вызвано объективными условиями современного развития науки, техники и народного хозяйства. Во многих областях человеческой деятельности уже в середине  ХХ  века  объем  и  сложность  вычислительных работ настолько возросли, что решение  некоторых  задач  без применения вычислительной техники было бы  практически  не  возможным.  В настоящее время электронные вычислительные машины применяются во многих областях науки, техники и народного  хозяйства.  В основном они используются: для решения сложных математических и инженерных задач, в качестве управляющих машин в промышленности и военной технике, в сфере обработки информации.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Задание к курсовой работе

1. Синтезировать комбинационную схему, что реализуется заданной функцией 5 переменных.
2.   По результатом синтеза построить функциональную схему с использованием заданного базиса.
3. Проанализировать работу синтезированной схемы методом p-алгоритма.
4. Спроектировать руководящий автомат Мили по заданной граф-схемой алгоритма. Построить принципиальную схему автомата с использованием элементов КР1533 серии.
5. Спроектировать руководящий автомат Мура по заданной граф-схемой алгоритма. Построить принципиальную схему автомата с использованием элементов КР1533 серии.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Булевы функции

Наиболее простым и наиболее важным классом однородных логических функций является класс двузначных-булевых  функций.

Определение: Буквой функцией называется однородная логическая функция, принимающая значения из двухэлементного булева множества В={0, 1} или В={ложь, истина}.

Так как булева функция - однородна, то любой ее аргумент принимает значения из В={0, 1} или В={ложь, истина}, область определения булевой функции от ²n² переменных (аргументов) множество слов длины ²n². Общее число всевозможных двоичных наборов длины ²n² равно 2ⁿ . Число всевозможных булевых функций от ²n² аргументов равно 2^{2^n} . Любая булева функция может быть задана таблицей истинности (соответствия), в левой части которой перечислены все 2ⁿ наборов значений переменных, а в правой части - значения функции на этих наборах.

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

Табличный способ. Способ предполагает наличие таблицы истинности (соответствия).

Аналитический способ. Нормальные формы.

Определение: Дизъюнктивная нормальная форма (ДНФ) - это дизъюнкция конечного числа различных членов, каждый из которых представляет собой конъюнкцию конечного числа отдельных переменных или их отрицаний, входящих в данный член не более одного раза.

Определение: Конъюнктивная нормальная форма (КНФ) - это конъюнкция конечного числа различных членов, каждый из которых представляет собой дизъюнкцию конечного числа отдельных переменных или их отрицаний, входящих в данный член не более одного раза.

Определение: Члены ДНФ, представляющие собой элементарные конъюнкции из ²k² букв, называются минтермами к-го ранга. Члены КНФ, представляющие собой элементарные дизъюнкции из ²k² букв, называются макстермами к-го ранга.

Совершенные нормальные формы

Определение: Если в каждом члене нормальной дизъюнктивной или конъюнктивной формы представлены все ²n² переменных (в прямом или инверсном виде) от которых зависит булева функция, то такая форма называется совершенной дизъюнктивной или конъюнктивной нормальной формой (СДНФ или СКНФ).

Лемма: Любая булева функция, не являющаяся тождественно равной нулю, имеет одну и только одну СДНФ. Любая булева функция, не являющаяся тождественно равной единице, имеет одну и только одну СКНФ.

Минтермы СДНФ называют конституентами единицы. Макстермы СКНФ называют конституентами нуля. Конституента ²1² обращается в единицу только при одном соответствующем ей наборе значений переменных, который получается, если все переменные конститунты принять равными единице, а для всех инверсий конституенты переменные принять равными нулю. Конституента ²0² обращается в нуль только при одном соответствующем ей наборе значений переменных, который получается, если все переменные конституенты принять равными нулю, а для всех инверсий конституенты переменные принять равными единице.

Так как СДНФ является дизъюнкцией  конституент ²1², то можно утверждать, что представляющая ее булева функция f(x₁, x₂,..., x_n) обращается в единицу только при наборах значений переменных, соответствующих хотя бы одной единице этих конституент. На остальных наборах эта функция обращается в нуль.

Аналогично, так как СКНФ является конъюнкцией конституент ²0², можно утверждать, что ее булева функция f(x₁, x₂,..., x_n) обращается в нуль только при наборах значений переменных, соответствующих хотя бы одному нулю этих конституент. На остальных наборах эта функция обращается в единицу.

Правила задания булевой функции  в виде СДНФ, СКНФ

Для задания любой булевой функции  в виде СДНФ необходимо записать дизъюнкцию конституент ²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

 

у =`х<sub>1</sub>`х₂`х<sub>3</sub>Ú`х₁х₂`х<sub>3</sub>Ú`х₁х₂х₃Úх₁`х<sub>2</sub>`х₃   СДНФ

у =(х₁Úх₂Ú`х<sub>3</sub>)(`х₁Úх₂Ú`х<sub>3</sub>)(`х₁Ú`х<sub>2</sub>Úх<sub>3</sub>)(`х₁Ú`х<sub>2</sub>Ú`х₃) СКНФ

Очевидно, что для всюду определенной булевой функции СДНФ и СКНФ равносильны, т.е. БФ(СДНФ)=БФ(СКНФ). Аналитическое задание булевой функции возможно и в ДНФ и КНФ, в тупиковых, минимальных и др. формах.

Определяем булеву функцию.

Булева функция 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,23,24);

 

y= Ù (2,3,9,11,13,22,25,26,27);

 

у= х (0,7,14,15,16,17,28,29,30,31).

 

                                                   Таблица 2

	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

 

Минимизация заданной булевой функции  методом Квайна-МакКласки.

Минимизация схем в булевом базисе сводится к поиску минимальной ДНФ, которой соответствует минимальное покрытие. Для оценки сложности булевой функции используется критерий Квайна, формулируемый следующим образом:

Утверждение: Минимальной функции  соответствует минимальная цена по Квайну, определяемая как С=åq_s(n-s), где q_s - число S-кубов, образующих покрытие данной функции от n-переменных, s - размерность кубов.

Минимальное покрытие характеризуется  минимальной ценой.

Задача минимизации решается в  два шага:

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

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

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

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

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

СДНФ Þ СкДНФ Þ {ТДНФ} Þ {МДНФ}

Метод Квайна

В качестве исходной формы булевой  функции для минимизации методом  Квайна используется СДНФ или таблица  истинности. Приведение к сокращенной  ДНФ осуществляется применением  свойств дополнения (операции склеивания).

аx_iÚa`x_i=a

Множеству конституент «1» соответствует совокупность 0-кубов К₀, операции склеивания соответствует объединение двух 0-кубов, отличающихся только одной координатой. Результатом такого объединения является 1-куб, в котором различные координаты исходных 0-кубов замещены символом ´.