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

Петербургский Государственный Университет Путей Сообщения

Кафедра “Автоматика, телемеханика и связь на железных дорогах”.

Курсовой проект по дисциплине: Теория дискретных устройств.

“Синтез асинхронных конечных автоматов ”.

Вариант №18.

Выполнила:                                                                                           Проверила:

студентка группы АСВ-107

Тромм О.Н.                                                                                  Константинова Т.Ю.

Санкт-Петербург

2003

Содержание:

Часть 1: “ Минимизация таблиц переходов”.

1.  Составление первичной таблицы переходов.

2.  Нахождение максимальных подмножеств совместимых строк.

3.  Нахождение множеств.

4.  Таблица покрытий.

5.  Решение задачи покрытий.

6.  Объединение строк таблицы переходов.

7.  Минимизированная таблица переходов.

8.  Граф переходов.

Часть 2: “ Синтез асинхронных конечных автоматов”.

1.  Нахождение -классов и определение числа разделяющих переменных.

2.  Кодирование столбцов таблицы переходов.

3.  Кодированная таблица переходов.

4.  Нахождение ФАЛ для внутренних реле.

5.  Минимизация ФАЛ для внутренних реле.

6.  Минимизация ФАЛ вторым методом.

7.  Вычисление выходной функции.

8.  Минимизация выходной функции двумя методами.

9.  Реализация.

1. Исходные данные и временные диаграммы.

X1 X2          00        10       00    11      01

Z1 Z2           00       01       11     00      11    

X1 X2          00        10       00    10      11     

Z1 Z2           00        01       11    01      10      

X1 X2          00       10      00      01     10

Z1 Z2           00       01      11      00     01

 

1.  Составление первичной таблицы переходов.

Таблица №1

a	a1	a2	a3	a4
S \ x1x2	00	01	10	11
1	(1),00	~	2,01	~
2	3,11	~	(2),01	~
3	(3),11	8,00	6,01	4,00
4	~	5,11	~	(4),00
5	1,00	(5),11	~	~
6	~	~	(6),01	7,10
7	1,00	~	~	(7),10
8	~	(8),00	9, 01	~
9	1,00	~	(9), 01	~

2.       Нахождение максимальных подмножеств  совместимых строк

2.1     Пары совместимых строк

(1,4) (1,5) (1,7) (2,4) (4,5) (4,9) (5,6) (5,7) (5,9) (6,7) (7,8) (7,9) (8,9)

2.2     Максимальные подмножества совместимых строк

Е_max1=(1,4,5)        E_max2=(1,5,7)        E_max3=(4,5,9)        E_max4=(5,6,7)          E_max5=(5,7,9)        E_max6=(7,8,9)       

3.       Нахождение множеств

Таблица №2

S \ x1x2	00	01	10	11
(1,4,5)	(1),00	(5),11	2,01	(4),00
(1,5,7)	(1),00	(5),11	2,01	(7),10
(4,5,9)	1,00	(5),11	(9), 01	(4),00
(5,6,7)	1,00	(5),11	(6),01	(7),10
(5,7,9)	1,00	(5),11	(9), 01	(7),10
(7,8,9)	1,00	(8),00	(9),01	(7),10

3.       Нахождения максимальных множеств совместимых строк ТП

E¹₁ = {1,4,5,6,7,8,9}        E²₅ = {1,2,4,5,6,7,9}        E³₂ = {1,2,4,5,7}                      E⁴₄ = {1,2,3,4,5,8,9}        E¹₃ = {2,3,4,6,8}             E²₈ = {1,2,3,6,7,8,9}                E³₆ = {3,4,5,6,7}                 E⁴₇={1,2,5,6,7,8,9}            E³₉={4,5,7,8,9}

Нахождение множеств Е_{i1 i2 i3 i4}:

E₁₅₂₄ = {1,4,5}; E₁₅₂₇ = {1,5,7}; E₁₅₆₄ = {4,5}; E₁₅₆₇ = {5,6,7}; E₁₅₉₄ = {4,5,9}

E₁₅₉₇ = {5,7,9}; E₁₈₂₄ = {1}; E₁₈₂₇ = {1,7}; E₁₈₆₄ = {-}; E₁₈₆₇ = {6,7}; E₁₈₉₄ = {8,9};

E₁₈₉₇ = {7,8,9};C;E₃₅₂₇ = {2};E₃₅₆₄ = {4};E₃₅₆₇ = {6};E₃₅₉₄ = {4};E₃₅₉₇ = {-};E₃₈₂₄ = {2};E₃₈₂₇ = {2};E₃₈₆₄ = {3};E₃₈₆₇ = {6};E₃₈₉₄ = {8} ;E₃₈₉₇ = {8};E₃₅₂₄ = {2,4}

E₁₅₂₄ = {1,4,5}=A; E₁₅₂₇ = {1,5,7}=B; E₁₅₆₇ = {5,6,7}=C; E₁₅₉₄ = {4,5,9}= D; E₁₅₉₇ = {5,7,9}=E; E₃₅₂₄ = {2,4}=G; E₃₈₆₄ = {3}=H; E₁₈₉₇ = {7,8,9}=F

4.  Таблица покрытий.