Курсовой проект


МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное автономное образовательное учреждение высшего профессионального образования
«САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ АЭРОКОСМИЧЕСКОГО ПРИБОРОСТРОЕНИЯ»
ИНСТИТУТ ДОВУЗОВСКОГО И ВЫСШЕГО ДИСТАНЦИОННОГО ОБРАЗОВАНИЯ
Кафедра вычислительных систем и сетей
ОЦЕНКА
ПРЕПОДАВАТЕЛЬ
Иванов Н. М.
должность, уч. степень, звание подпись, дата инициалы, фамилия
Курсовой проект на тему
“Проектирование цифрового аппарата,
заданного в форме оператора соответствия”
по дисциплине: Теория автоматов
РАБОТУ ВЫПОЛНИЛ
СТУДЕНТ ГР. В4441 К.А. Тихомиров
номер группы подпись, дата инициалы, фамилия
Студенческий билет № 2014/0810 Санкт-Петербург
2016
Постановка задачи
Данный курсовой проект посвящен проектированию цифрового автомата, заданного в виде оператора соответствия, согласно варианту № 14
0 0 0 1 0 1
0 0 1 1 0 1
0 1 0 0 1 0
0 1 1 1 1 1
1 0 0 0 0 1
1 0 1 1 1 0
1 1 0 0 1 0
1 1 1 1 1 1
Вариант
задания Модель автомата Тип элемента
памяти Вид логического базиса
Мили Мура D T J-K штрих Шеффера стрелка Пирса
0 + + + 1 + + + 2 + + +
3 + + + +
4 + + + 5 + + + 6 + + +
7 + + +
8 + + + 9 + + + 10 + + +
11 + + +
Примечание к таблице: Число в левом столбце таблицы образуется как остаток от целочисленного деления N на 12, где N- порядковый номер в групповом журнале.
Для варианта 14 остаток от целочисленного деления на 12 будет 2.
1. Абстрактный синтез
1.1 Приведение ОС к автоматному виду.
Z0 Z1 Z2 Z3 Z4 W0 W1 W2 W3 W4
0 0 0 α β 1 0 1
0 0 1 α β 1 0 1
0 1 0 α α β β 0 1 0
0 1 1 α α β β 1 1 1
1 0 0 α α β β 0 0 1
1 0 1 α α β β 1 1 0
1 1 0 α α β β 0 1 0
1 1 1 α α β β 1 1 1
1.2 Построение графа автомата

1.3 Построение СТПВ автомата модели Мили
a0 a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 a12 a13 a14 a15 a16 a17 a18 a19 a20
0 a1
/β a3
/1 a11
/β a5
/0 a7
/0 - - - - - - a13/0 a15/0 - - - - - - - -
1 a2
/β a4
/β a12
/ β a6
/0 a8
/1 - - - - - - a14/1 a16/1 - - - - - - - -
α - - - - - a0
/1 a0
/1 a9
/1 a10/1 a0
/0 a0
/1 - - a17/0 a18/1 a19/1 a20/1 a0
/1 a0
/0 a0
/0 a0
/1
Выполнение первого этапа минимизации по графу переходов
b0 a0
b1 a1
b2 a2
b3 a3
b4 a4
b5 a5, a6, a10, a17, a20
b6 a7
b7 a8
b8 a9, a18, a19
b9 a11
b10 a12
b11 a13
b12 a14
b13 a15
b14 a16
b0 b1 b2 b3 b4 b5 b6 b7 b8 b9 b10 b11 b12 b13 b14
0 b1/β b3/1 b9/β b5/0 b6/0 - - - - b11/0 b13/0 - - - -
1 b2/β b4/β b10/β b5/0 b7/1 - - - - b12/1 b14/1 - - - -
α - - - - - b0/1 b8/1 b5/1 b0/0 - - b5/0 b8/1 b8/1 b5/1
1.4 Выполнение минимизации автомата с использованием треугольной таблицы
b1 X b2 b1, b9
b2, b10 X b3 X X X b4 X X X X b5 V V V V V b6 V V V V V b0, b8 b7 V V V V V b0, b5 b8, b5 b8 V V V V V X X X b9 X X X X b6, b11
b7, b12 V V V V b10 X X X X b6, b13
b7, b14 V V V V b11, b13
b12, b14 b11 V V V V V X X X b0, b5 V V b12 V V V V V b0, b8 V b5, b8 X V V X b13 V V V V V b0, b8 V b5, b8 X V V X V b14 V V V V V b0, b5 b8, b5 V X V V X b8, b5 b8, b5
b0 b1 b2 b3 b4 b5 b6 b7 b8 b9 b10 b11 b12 b13
Окончательный вид треугольной таблицы
b1 X b2 b1, b9
b2, b10 X b3 X X X b4 X X X X b5 V V V V V b6 V V V V V b0, b8 b7 V V V V V b0, b5 b8, b5 b8 V V V V V X X X b9 X X X X b6, b11
b7, b12 V V V V b10 X X X X b6, b13
b7, b14 V V V V b11, b13
b12, b14 b11 V V V V V X X X b0, b5 V V b12 V V V V V b0, b8 V b5, b8 X V V X b13 V V V V V b0, b8 V b5, b8 X V V X V b14 V V V V V b0, b5 b8, b5 V X V V X b8, b5 b8, b5
b0 b1 b2 b3 b4 b5 b6 b7 b8 b9 b10 b11 b12 b13
Подбор классов эквивалентности, обладающих свойствами полноты и замкнутости:
С0=(b0,b7,b14), С1=(b1,b6,b13), С2=(b2,b8), С3=(b3,b12), С4=(b4,b5,b10), С5=(b9,b11)
Построение СТПВ минимального автомата
С0 С1 С2 С3 С4 С5
0 С1/β С3/1 С5/β С4/0 С1/0 С5/0
1 С2/β С4/β С4/β С4/0 С0/1 С3/1
α С4/1 С2/1 С0/0 С2/1 С0/1 С4/0
1.5 Проверка правильности минимизации
Входной символ 0 0 0 α
Состояние С0 С1 С3 С4 С0 Выходной символ β 1 0 1 Входной символ 0 0 1 α Состояние С0 С1 С3 С4 С0 Выходной символ β 1 0 1 Входной символ 0 1 0 α α Состояние С0 С1 С4 С1 С2 С0 Выходной символ β β 0 1 0 Входной символ 0 1 1 α α Состояние С0 С1 С4 С0 С4 С0 Выходной символ β β 1 1 1 Входной символ 1 0 0 α α Состояние С0 С2 С5 С5 С4 С0 Выходной символ β β 0 0 1 Входной символ 1 0 1 α α Состояние С0 С2 С5 С3 С2 С0 Выходной символ β β 1 1 0 Входной символ 1 1 0 α α Состояние С0 С2 С4 С1 С2 С0 Выходной символ β β 0 1 0 Входной символ 1 1 1 α α
Состояние С0 С2 С4 С0 С4 С0 Выходной символ β β 1 1 1 2. Структурный синтез
Этап 1. Кодирование входных символов, выходных символов и состояний.
Нахождение количества структурных входных каналов, структурных выходных каналов и элементарных автоматов (триггеров) для хранения состояний структурного автомата.
L = ]log23[=2
N = ]log23[=2
P = ]log26[=3
Пусть x2, x1 – переменные, связанные с входами автомата, y2, y1 – переменные, связанные с выходами автомата, Q3, Q2, Q1 – в переменные, связанные с состояниями автомата.ы триггеров.
Кодировка входных символов, выходных символов и символов состояний:
x2 x1 y2 y1 Q3 Q2 Q1
z1 0 0 w1 0 0 С0 0 0 0
z2 0 1 w2 0 1 С1 0 0 1
z3 1 0 w3 1 0 С2 0 1 0
С3 0 1 1
С4 1 0 0
С5 1 0 1

Этап 2. Формирование кодированной таблицы переходов структурного автомата (КТП).
Создание таблицы переходов (ТП)
С0 С1 С2 С3 С4 С5
0 С1 С3 С5 С4 С1 С5
1 С2 С4 С4 С4 С0 С3
α С4 С2 С0 С2 С0 С4

Формирование таблицы КТП (Таблица 6) на основе ТП и таблиц структурных эквивалентов
Q3,Q2 ,Q2
x2 , x1 000 001 010 011 100 101
00 001 011 101 100 001 101
01 010 100 100 100 000 011
10 100 010 000 010 000 100
Этап 3. Формирование кодированной таблицы функций возбуждения структурного автомата (КТФВ).
На основе таблицы переходов T триггера и КТП
  Q
T 0 1
0 0 1
1 1 0
КТФР
Q3,Q2,Q1
x2 , x1 000 001 010 011 100 101
T3 T2 T1 T3 T2 T1 T3 T2 T1 T3 T2 T1 T3 T2 T1 T3 T2 T1
00 0 0 1 0 1 0 1 1 1 1 1 1 1 0 1 0 0 0
01 0 1 0 1 0 1 1 1 0 1 1 1 1 0 0 1 1 0
10 1 0 0 0 1 1 0 1 0 0 0 1 1 0 0 0 0 1
Этап 4. Построение диаграмм Вейча и логических выражений (ЛВ) для функций возбуждения,
представление ЛВ в заданном базисе.

Функция возбуждения триггера T1 и её перевод в базис ИЛИ-НЕ:
T1=X2Q1v X1Q1Q3v X1 X2Q2v Q1 Q2 X1 X2==X2v Q1v X1vQ1vQ3v X1v X2v Q2v Q1v Q2v X1v X2==X2v Q1v X1vQ1vQ3v X1vX2v Q2v Q1v Q2v X1v X2
Функция возбуждения триггера T2 и её перевод в базис ИЛИ-НЕ:
T2=X1Q1 Q2 Q3v X1Q1Q2 Q3v X1Q2v Q1Q2vX1Q1Q3v X1 X2Q2==X1v Q1v Q2v Q3v X1v Q1 v Q2 v Q3v X1v Q2v Q1v Q2v X1v Q1v Q3v X1v X2v Q2== X1v Q1v Q2v Q3v X1v Q1 v Q2 v Q3v X1v Q2v Q1v Q2v X1v Q1v Q3v X1v X2v Q2 Функция возбуждения триггера T3 и её перевод в базис ИЛИ-НЕ:
T3=X2Q1 Q2v X2Q2v X2X1Q1v Q3Q1 Q2==X2v Q1v Q2v X2v Q2v X2v X1v Q1 v Q3v Q1v Q2==X2v Q1v Q2v X2v Q2v X2v X1v Q1 v Q3v Q1v Q2Этап 5. Построение кодированной таблицы выходов (КТВ).
Создание таблицы выходов (ТВ)
С0 С1 С2 С3 С4 С5
0 β 1 β 0 0 0
1 β β β 0 1 1
α 1 1 0 1 1 0

Формирование таблицы КТВ на основе ТВ и таблиц структурных эквивалентов
Q3,Q2 ,Q2
x2 , x1 000 001 010 011 100 101
00 10 01 10 00 00 00
01 10 10 10 00 01 01
10 01 01 00 01 01 00
Этап 6. Построение диаграмм Вейча и ЛВ для выходных сигналов представление ЛВ в заданном базисе:
Построение ЛВ для выходного сигнала У1 и привидение его к базису ИЛИ-НЕ:

У1= X2Q1 Q2v X2Q1Q3 v X1Q1 Q2 Q3 v X1 Q3==X2v Q1v Q2v X2v Q1v Q3 v X1v Q1v Q2v Q3 v X1v Q3==X2v Q1v Q2v X2v Q1v Q3 v X1v Q1v Q2v Q3 v X1v Q3Построение ЛВ для выходного сигнала У2 и привидение его к базису ИЛИ-НЕ

У2= X1Q2 Q3v X2 Q1 Q2 Q3 v X2 Q1 Q2==X1v Q2v Q3v X2v Q1v Q2v Q3 v X2v Q1v Q2==X1v Q2v Q3v X2v Q1v Q2v Q3 v X2v Q1v Q2 Схема структурного автомата:

Автоматные ленты для проверки переходов структурного автомата.

Слово 1
Входной символ 0 0 0 α Состояние С0 С1 С3 С4 С0
Выходной символ β 1 0 1 Входной символ 00 00 00 10 Состояние 000 001 011 100 000
Выходной символ 10 01 00 01
Слово 2
Входной символ 0 0 1 α Состояние С0 С1 С3 С4 С0
Выходной символ β 1 0 1 Входной символ 00 00 01 10 Состояние 000 001 011 100 000
Выходной символ 10 01 00 01
Слово 3
Входной символ 0 1 0 α α Состояние С0 С1 С4 С1 С2 С0
Выходной символ β β 0 1 0 Входной символ 00 01 00 10 10 Состояние 000 001 100 001 010 000
Выходной символ 10 10 00 01 00
Слово 4
Входной символ 0 1 1 α α Состояние С0 С1 С4 С0 С4 С0
Выходной символ β β 1 1 1 Входной символ 00 01 01 10 10 Состояние 000 001 100 000 100 000
Выходной символ 10 10 01 01 01
Слово 5
Входной символ 1 0 0 α α Состояние С0 С2 С5 С5 С4 С0
Выходной символ β β 0 0 1 Входной символ 01 00 00 10 10 Состояние 000 010 101 101 100 000
Выходной символ 10 10 00 00 01
Слово 6
Входной символ 1 0 1 α α Состояние С0 С2 С5 С3 С2 С0
Выходной символ β β 1 1 0 Входной символ 01 00 01 10 10 Состояние 000 010 101 011 010 000
Выходной символ 10 10 01 01 00
Слово 7
Входной символ 1 1 0 α α Состояние С0 С2 С4 С1 С2 С0
Выходной символ β β 0 1 0 Входной символ 01 01 00 10 10 Состояние 000 010 100 001 010 000
Выходной символ 10 10 00 01 00
Слово 8
Входной символ 1 1 1 α α Состояние С0 С2 С4 С0 С4 С0
Выходной символ β β 1 1 1 Входной символ 01 01 01 10 10 Состояние 000 010 100 000 100 000
Выходной символ 10 10 01 01 01

Приложенные файлы

  • docx 14677660
    Размер файла: 335 kB Загрузок: 0

Добавить комментарий