на тему рефераты
 
Главная | Карта сайта
на тему рефераты
РАЗДЕЛЫ

на тему рефераты
ПАРТНЕРЫ

на тему рефераты
АЛФАВИТ
... А Б В Г Д Е Ж З И К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Э Ю Я

на тему рефераты
ПОИСК
Введите фамилию автора:


Реферат: Синтез комбинацонных схем и конечных автоматов, сети Петри


Реферат: Синтез комбинацонных схем и конечных автоматов, сети Петри

Государственный комитет Российской Федерации по высшему образованию

Кубанский государственный технологический университет

Кафедра ???

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

к курсовой работе по предмету

математические основы теории систем

 

тема курсовой работы:

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

автоматов. Сети Петри ».

                                               

                                                                      Выполнил : студент гр. ??–??–??

                                                                                         ????

                                                                                         номер зачётной книжки  ??–??–???

 

                                                                   Руководитель : ????

                                                                                          ????            

???

1999

Государственный комитет Российской Федерации по высшему образованию

Кубанский государственный технологический университет

ЗАДАНИЕ

На курсовую работу

Студенту гр.

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


Тема курсовой работы


Исходные данные


1 Выполнить расчёты:

  1.1


  1.2


  1.3

  1.4


2 Выполнить графические работы:

  2.1

  2.2

3 Выполнить научные и учебно-исследовательские работы:

  3.1


  3.2


  3.3


  3.4


4 Оформить расчётно-пояснительную записку

5 Основная литература


Задание выдано


Срок сдачи работы


Задание принял


Руководитель


Работа защищена


С оценкой


ЧЛЕНЫ КОМИССИИ :


РЕФЕРАТ

МИНИМИЗАЦИЯ  БУЛЕВЫХ ФУНКЦИЙ,  КОМБИНАЦИОННАЯ СХЕМА,  МИНИМИЗАЦИЯ КОНЕЧНЫХ АВТОМАТОВ, АВТОМАТ МИЛИ,  СЕТЬ  ПЕТРИ.

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

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

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

     Курсовая работа содержит   38 страниц,  11 рисунков,  8 таблиц,    

                                                      4 источника,  1 приложение . 

СОДЕРЖАНИЕ

   Введение ………………………………………………………………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:

i

gi

zi

0

5

0

1

1

6

2

8

2

3

5

9

4

13

6

5

11

14

6

4

12

7

3

5

8

13

4

9

13

14

10

8

14

11

9

9

12

5

10

13

7

6

Неповторяющиеся значения gi: 5, 1, 8, 13, 11, 4, 3, 9, 7. Неповторяющиеся значения zi: 0, 6, 2, 9, 14, 12, 5, 4, 10. Таким образом, для F1  получаем выражение

      ,        (1.3.1)

для  F2:

     .        (1.3.2)

Для минимизации первой функции применяем метод карт Карно.

Карта Карно – прямоугольник с 2n клетками, каждой из которых соответствует своя конъюнкция из n переменных и их отрицаний (дополнений).

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

                                      

                                                               x3x4 

                                                    00         01          11          10

                                           00                     1            1

 

                                           01        1           1             1   

                               

                                  x1x2

                                           11                     1

                                           10        1           1             1

                                                     Рисунок  1.2.1 – карта Карно         

На основании выбранной комбинации покрытий выписываем минимизированное выражение для функции F1:

                         .                     (1.3.3)   

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

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


                                     0    0 0   0 0 1 1 1 1

                                     0    0 1  1 1 0 0 1  1

                   K0  =         0    1 0   0 1 0 1 0  1                                         (1.3.4)

                                     0   0 0  1 0 1 0 0   0     .

Второй этап основан на операции склеивания. Каждый из кубов проверяется на “склеиваемость” со всеми остальными. Склеивающиеся кубы должны различаться не более чем в одном разряде. Склеенный разряд в дальнейшем обозначается как  x. Куб, участвовавший в операции склеивания, соответствующим образом помечается. Поскольку таких кубов мало, будем отмечать не участвовавшие в операции склеивания кубы. В результате получаем комплекс K1-кубов, также упорядоченный по возрастанию количества единиц в разрядах:

 


                                     0 0   0 x 0 0 x   x 1 1

                                     0 x   x 0 1 1 1   1 x 1

                K1  =            x 0    1 1 0 x 0  1 1 x                                          (1.3.5)

                                    0 0    0 0 x 0 0  0 0 0     .

Повторяем вышеописанную операцию для  комплекса    K1-кубов, после чего удаляем из полученного комплекса K2-кубов повторяющиеся:

                     0 0   x x x x                        0   x x

                     x x   x x 1 1                        x   x 1

      K2 =       x x   1 1 x x         =            x   1 x                                      (1.3.6)

                    0 0   0 0 0 0                       0   0 0   

Те кубы, которые не участвовали в операциях склеивания, называются импликантами – это кандидаты на то, чтобы попасть в итоговую ДНФ. Для них составляем таблицу покрытий K0-кубов. Импликанта считается покрывающей K0-куб, если они совпадают при  x, принимающем произвольное значение.


               K0

      z

0

0

0

0

0

0

1

0

0

1

0

0

0

1

0

1

0

1

1

0

1

0

0

1

1

0

1

0

1

1

0

0

1

1

1

0

Импликанты

1001

+

010x

+ +

0xx0

+ + + +

xx10

+ + + +

x1x0

+ + + +

Страницы: 1, 2, 3


на тему рефераты
НОВОСТИ на тему рефераты
на тему рефераты
ВХОД на тему рефераты
Логин:
Пароль:
регистрация
забыли пароль?

на тему рефераты    
на тему рефераты
ТЕГИ на тему рефераты

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


Copyright © 2012 г.
При использовании материалов - ссылка на сайт обязательна.