Синтез комбинацонных схем и конечных автоматов

СОДЕРЖАНИЕ

   Введение ………………………………………………………………6

   1 Синтез комбинационных схем

1.1  Постановка задачи ……………………………………………… 7

   1.2  Теоретические сведения …………………………………………7

     1.3  Расчёты и полученные результаты ……………………………..9

   1.4  Выводы по разделу………………………………………………13

2 Синтез конечных автоматов

2.1  Постановка задачи ……………………………………………… 14

   2.2  Теоретические сведения …………………………………………14

     2.3  Расчёты и полученные результаты ……………………………  16

2.4     Выводы по разделу……………………………………………… 20

   3 Сети Петри

3.1  Постановка задачи ……………………………………………… 21

   3.2  Теоретические сведения ………………………………………    21

     3.3  Расчёты и полученные результаты ……………………………  26

   3.4  Выводы по разделу……………………………………………… 31

   Заключение ………………………………………………………….   32

   Литература …………………………………………………………     33

   Приложение А ………………………………………………………   34

ВВЕДЕНИЕ

Работа посвящена синтезу дискретных устройств с “памятью” (конечных автоматов) и “без памяти” (комбинационных схем), а также анализу реально протекающих процессов с помощью сетей Петри.

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

Во второй части заданный по условию в функциональном виде конечный автомат был минимизирован по числу состояний. Для полученного автомата был построен граф состояний. Затем, перейдя к двоичному представлению входных, выходных сигналов и сигналов состояния, в автомате были выделены элементы памяти и комбинационная часть, которая затем была минимизирована по числу переменнных. Автомат был реализован в базисе И – ИЛИ – НЕ с использованием D - триггера и задержки.

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

1 Синтез комбинационных схем

1.1   Постановка задачи

Для двух булевых функций, построенных по варианту задания в виде

           (1.1.1)

,              (1.1.2)

где gi, zi – десятичные числа из диапазона от 0 до 15 в двоичном виде,

сделать следующее:

а)  представить F1 и F2 в виде СДНФ.

б) минимизировать (по количеству переменных в ДНФ) F1 с

помощью карт Карно, F2 – методом Квайна-МакКласки.

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

gi и zi вычислять по выражениям:

                                                                                (1.1.3)

                                                                                (1.1.4)

при g0 = A, z0 = B . Параметр  изменять от 1 до тех пор, пока не будет получено 9 различных значений gi и zi.

1.2   Теоретические сведения.

Булевой алгеброй называется множество S объектов A, B, C…, в котором определены две бинарные операции (логическое сложение – дизъюнкция(+) и логическое умножение – конъюнкция(∙)) и одна унарная операция(логическое отрицание()). Оно обладает следующими свойствами:

а) Для  A, B, C    S 

1)     ,  (замкнутость);

2)           (коммутативные законы);

3)          (ассоциативные законы);

4)           (дистрибутивные законы);

5)         (свойства идемпотентности);

6)      в том и только том случае, если

                     (свойство совместимости);

7)     S  содержит элементы 1 и 0 такие, что для всякого элемента

                        ;

8)     для каждого элемента  A  класс  S  содержит элемент Ã (дополнение элемента A, часто обозначаемое символами Ā  или 1- A ) такой, что

                                      ,    .

В каждой булевой алгебре

                 (законы поглощения),

                (законы склеивания),

                       (двойственность, законы де Моргана).

Если даны n булевых переменных X1, X2,…, Xn, каждая из которых может быть равна любому элементу булевой алгебры, то булевой функцией называется выражение

                                                                               (1.2.1)

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

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

Под критерим минимизации (упрощения) булевых функций будем понимать достижение минимума букв в записи функции.

Введём понятие многомерного куба.

Любую булеву функцию n переменных, заданную в ДНФ или СДНФ, можно отобразиь на n-мерном кубе, построенном в ортогональном базисе n булевых переменных. Каждое слагаемое в ДНФ или СДНФ представляется гиперплоскостью соответствующей размерности: если оно представляет собой конъюнкцию n переменных – точка, n-1 переменных – прямая, n-2 переменных – плоскость и т.д. Элементы n-мерного куба, имеющие s измерений, назовём s-кубами.

Комплекс K(y) кубов функции  y=ƒ(x1,x2,…,xn)  есть объединение Ks(y) множеств всех её кубов. Отсутствующие в конъюнкциях переменные будем обозначать через  x.       

1.3   Расчёты и полученные результаты.

По варианту задания находим  gi  и  zi:

1	2	3	4	5	6	7	8	9	10