Курсовой проект_Комп_логика_пример_рус
.pdfМИНИСТЕРСТВО ОБРАЗОВАНИЯ УКРАИНЫ
ВОСТОЧНОУКРАИНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СЕВЕРОДОНЕЦКИЙ ТЕХНОЛОГИЧЕСКИЙ ИНСТИТУТ ФАКУЛЬТЕТ КТ
КАФЕДРА ВПМ
Пояснительная записка к курсовому проекту по дисциплине:
«Компьютерная логика» на тему: «Синтез управляющего автомата Мура»
Студент группы КИ-11д:
Руководитель: доц. каф. ВПМ, Лыфарь В. А.
Северодонецк 2012
Факультет КТ Кафедра КИ
Дисциплина “Компьютерная логика”
Специальность |
|
|
Курс |
Группа |
Семестр 2 |
ЗАДАНИЕ НА КУРСОВОЙ ПРОЕКТ
1. Тема проекта:
Разработать управляющий автомат Мура, закон функционирования которого задан совмещенной таблицей переходов и выходов, в запоминающей части автомата используется триггер
(табл.1.2).
2. Срок сдачи студентом законченной работы
17-я неделя
3.Исходные данные к проекту
Кданному проекту исходными данными являются:
-совмещенная таблица переходов и выходов автомата Мура
(табл. 1.1),
-сокращенная таблица переходов асинхронного триггера,
-кодирование входного алфавита – произвольно,
-кодирование выходного алфавита – весовым методом,
-кодирование алфавита состояний – эвристическим методом,
-для устранения гонок используется двухступенчатая память с разделением работы ступеней во времени;
-схема электрическая функциональная строится в базисе И- ИЛИ-НЕ.
2
4. Содержание пояснительной записки (перечень подлежащих разработке вопросов)
Синтез управляющего аппарата Мура осуществлялся в следующей последовательности:
-синтез абстрактного автомата;
-синтез структурного автомата с применением канонического метода структурного синтеза; Исходными данными для начала работы данного метода
является абстрактный цифровой автомат с памятью, заданный таблицей переходов и выходов.
5. Перечень графического материала (с точным указанием общего формата)
Схема электрическая функциональная формата А3 1 ед., граф переходов автомата формата А3 1 ед.
3
КАЛЕНДАРНЫЙ ПЛАН
№ |
Наименование этапов курсового проекта |
Срок выполнения |
Примечание |
п/п |
этапов |
||
1. |
Реферат, введение |
2-я неделя |
|
2. |
Анализ технического задания |
3-я недели |
|
|
|
|
|
3. |
Минимизация числа внутренних |
4-6-я неделя |
|
|
состояний абстрактного автомата МУРА |
|
|
4. |
Кодирование входных, выходных |
7-8-я недели |
|
|
сигналов, состояний автомата |
|
|
5. |
Составление таблиц переходов триггера |
9-11-я недели |
|
|
|
|
|
|
Составление таблицы формирования |
|
|
6. |
функций возбуждения элементов |
12-14-я недели |
|
|
памяти автомата и функций выходов |
|
|
|
Минимизация функций возбуждения |
|
|
7. |
элементов памяти автомата и функций |
15-16-я недели |
|
|
выходов |
|
|
8. |
Проектирование функциональной схемы |
17-я неделя |
|
автомата МУРА |
|
||
9 |
Сдача КР |
17-я неделя |
|
|
|
|
|
Студент
Руководитель
«_____»______________________20____г.
4
РЕФЕРАТ
Полный объем пояснительной записки к курсовому проекту составляет:
*страниц
*таблиц
*2 листа чертежей формата А3
Задачей курсового проекта является синтез цифрового автомата Мура. Основная задача разбивается на ряд этапов, которые выполнялись в определенной последовательности:
-минимизация числа внутренних состояний абстрактного автомата;
-кодирование алфавитов автомата;
-выбор элементов памяти;
-выбор функционально полной системы логических элементов;
-запись и минимизация канонических уравнений;
-построение функциональной схемы автомата.
АБСТАКТНЫЙ ЦИФРОВОЙ АВТОМАТ, СТРУКТУРНЫЙ АВТОМАТ, АВТОМАТ МУРА, КАНОНИЧЕСКИЙ МЕТОД СТРУКТУРНОГО СИНТЕЗА, КАРТЫ КАРНО, ФУНКЦИОНАЛЬНАЯ СХЕМА, ЭВРИСТИЧЕСКИЙ МЕТОД, ВЕСОВОЙ МЕТОД, ГРАФ ПЕРЕХОДОВ АВТОМАТА, ТРИГГЕР, МИНИМИЗАЦИЯ, КОДИРОВАНИЕ.
5
|
СОДЕРЖАНИЕ |
|
ЗАДАНИЕ НА КУРСОВОЙ ПРОЕКТ............................................................................. |
2 |
|
1. |
Тема проекта: ......................................................................................................... |
2 |
2. |
Срок сдачи студентом законченной работы ........................................................ |
2 |
3. |
Исходные данные к проекту.................................................................................. |
2 |
4. |
Содержание пояснительной записки (перечень подлежащих разработке |
|
вопросов) .................................................................................................................... |
3 |
|
5. |
Перечень графического материала (с точным указанием общего формата) ... |
3 |
КАЛЕНДАРНЫЙ ПЛАН .............................................................................................. |
4 |
|
РЕФЕРАТ ....................................................................................................................... |
5 |
|
ВВЕДЕНИЕ................................................................................................................. |
7 |
|
1. |
Анализ технического задания и постановка задачи проектирования.............. |
8 |
2. |
Минимизация числа внутренних состояний автомата с помощью алгоритма |
|
Ауфенкампа – Хона ................................................................................................... |
9 |
|
3. |
Построение графа переходов автомата.......................................................... |
11 |
4. |
Построение матрицы переходов триггера....................................................... |
11 |
5. |
Кодирование входных и выходных алфавитов состояний............................. |
14 |
6. |
Запись канонических уравнений и их минимизация ....................................... |
25 |
Вых.сиг...................................................................................................................... |
28 |
|
7. |
Функциональная схема автомата Мура........................................................... |
32 |
ВЫВОДЫ...................................................................................................................... |
34 |
|
ЛИТЕРАТУРА............................................................................................................... |
35 |
6
ВВЕДЕНИЕ
Общая теория цифровых автоматов подразделяется на абстрактную и структурную.
Абстрактная теория автоматов, не рассматривая его структуры, изучает лишь поведение автомата относительно внешней среды. Абстрактная теория цифровых автоматов является продолжением и детализацией теории алгоритмов. Различие между абстрактной и структурной теориями заключается в том, что абстрактная теория изучает лишь переходы, которые претерпевает автомат под воздействием входных сигналов, и выходные сигналы, которые он при этом выдает, не вдаваясь в вопросы кодирования входных и выходных сигналов и вопросы построения автомата из элементарных схем. Таким образом, в общем случае синтез цифровых автоматов становится сложным многоэтапным процессом [1]. В общем случае задача структурного синтеза автомата с памятью сводится к нахождению общих приёмов построения структурных схем сложных автоматов на основе композиции некоторых элементарных автоматов, т.е. поиску определённых способов их соединения между собой.
Структурная теория автоматов интересуется как структурой самого автомата, так и структурой входных воздействий и реакций автомата на них. В ней изучаются способы кодирования входных воздействий и реакций автомата на них. Эта теория является продолжением и развитием абстрактной теории автоматов. Опираясь на аппарат булевых функций и на абстрактную теорию автоматов, структурная теория дает эффективные рекомендации по разработке реальных устройств вычислительной техники[2].
Настоящий курсовой проект по курсу компьютерной логики предполагает практическое применение теоретических знаний, полученных при изучении курса.
7
1. Анализ технического задания и постановка задачи проектирования
Целью работы является синтез управляющего автомата Мура. Требуется: разработать автомат Мура, закон функционирования которого задан совмещенной таблицей переходов и выходов (Табл.
1.1).
Таблица 1.1 – Совмещенная таблица переходов и выходов
У |
y1 |
y2 |
y3 |
y4 |
y1 |
y2 |
y4 |
y2 |
y1 |
y1 |
|
A |
a1 |
a2 |
а3 |
а4 |
а5 |
a6 |
а7 |
a8 |
a9 |
a10 |
|
Х |
|||||||||||
|
|
|
|
|
|
|
|
|
|
||
x1 |
a1 |
а3 |
a6 |
а4 |
а7 |
а5 |
а4 |
a9 |
а7 |
а10 |
|
x2 |
а5 |
a1 |
а3 |
a6 |
a10 |
a9 |
a8 |
a10 |
a9 |
а5 |
|
x3 |
а7 |
а4 |
а5 |
a2 |
a8 |
a8 |
a1 |
а3 |
a10 |
а7 |
|
В |
запоминающей части автомата использовать триггер |
|||
(табл.1.2). |
|
|
|||
|
Таблица 1.2 – Сокращенная таблица переходов триггера |
||||
|
|
|
t |
t+1 |
|
|
x |
|
y |
Q |
|
|
0 |
|
0 |
Q(t) |
|
|
0 |
|
1 |
1 |
|
|
1 |
|
0 |
0 |
|
|
1 |
|
1 |
1 |
|
Методы кодирования алфавита автомата:
-входной - произвольно;
-выходной - весовым методом;
-алфавит состояний - эвристическим методом. Функциональная схема выполнена в базисе И-ИЛИ-НЕ.
8
2. Минимизация числа внутренних состояний автомата с помощью алгоритма Ауфенкампа – Хона
Необходимо минимизировать число внутренних состояний автомата. Для этого можно использовать алгоритм Ауфенкампа-Хона.
В основу метода минимизации состояний автомата положена идея разбиения всех состояний исходного абстрактного автомата на попарно непересекающиеся классы эквивалентных состояний и замене каждого класса эквивалентности одним состоянием (одним представителем данного класса). Образующийся в результате этих преобразований минимальный автомат имеет столько же состояний, на сколько классов эквивалентности разбивается исходное состояние.
Произведём минимизацию абстрактного автомата Мура, заданного таблицей переходов и выходов (табл. 2.1).
Таблица 2.1 - таблица переходов и выходов
У |
y1 |
y2 |
|
y3 |
y4 |
y1 |
y2 |
y4 |
y2 |
y1 |
|
y1 |
|
|||||||
A |
a1 |
a2 |
|
а3 |
а4 |
а5 |
a6 |
а7 |
a8 |
a9 |
|
a10 |
|
|||||||
Х |
|
|
|
|||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x1 |
a1 |
а3 |
|
a6 |
а4 |
а7 |
а5 |
а4 |
a9 |
а7 |
|
а10 |
|
|||||||
x2 |
а5 |
a1 |
|
а3 |
a6 |
a10 |
a9 |
a8 |
a10 |
a9 |
|
а5 |
|
|||||||
x3 |
а7 |
а4 |
а5 |
a2 |
a8 |
a8 |
a1 |
а3 |
a10 |
|
а7 |
Мура |
||||||||
|
Выполним разбиение 0={B1,B2,B3,B4}. Для автомата |
|||||||||||||||||||
разбиение 0 производится по выходным сигналам. |
|
|
|
|
|
|
||||||||||||||
|
B1={a1, a5, a9, а10}, B2={а2, а6, а8}, B3={а3}, B4={а4, а7}. |
|
|
|
||||||||||||||||
|
Строим таблицу разбиения 0 (таблица 2.2). |
|
|
|
|
|
|
|||||||||||||
Таблица 2.2 – таблица разбиения 0 |
|
|
|
|
|
|
|
|
|
|
||||||||||
|
|
|
B1 |
|
|
|
|
B2 |
|
|
B3 |
|
B4 |
|
|
|
||||
A |
a1 |
a5 |
|
a9 |
a10 |
|
а2 |
|
а6 |
|
a8 |
|
а3 |
|
a4 |
|
а7 |
|
|
|
x1 |
B1 |
B4 |
|
B4 |
B1 |
|
B3 |
|
B1 |
|
B1 |
|
B2 |
|
B4 |
|
|
B4 |
|
|
x2 |
B1 |
B1 |
|
B1 |
B1 |
|
B1 |
|
B1 |
|
B1 |
|
B3 |
|
B2 |
|
|
B2 |
|
|
x3 |
B4 |
B2 |
|
B1 |
B4 |
|
B4 |
|
B2 |
|
B3 |
|
B1 |
|
B2 |
|
|
B1 |
|
|
9
По таблице разбиения 0 (табл. 2.2.) выполним разбиение 1. При выполнении этого разбиения анализ производится только внутри каждого отдельного множества Вi.
1={С1, С2, С3, С4, С5, С6, С7, С8, С9}
С1={ a1, а10}, С2={а5}, С3={а9}, С4={а2}, С5={a6}, С6={а8}, С7={а3}, С8={а4}, С9={a7}.
Построим таблицу разбиения 1(таблица 2.3)
Таблица 2.3 – таблица разбиения 1 |
|
|
|
|
|||||||
|
|
С1 |
С2 |
С3 |
С4 |
С5 |
С6 |
С7 |
С8 |
С9 |
|
A |
a1 |
|
a10 |
a5 |
a9 |
а2 |
а6 |
a8 |
а3 |
a4 |
а7 |
x1 |
С1 |
|
С1 |
С9 |
С9 |
С7 |
С2 |
С3 |
С5 |
С8 |
С8 |
x2 |
С2 |
|
С2 |
С1 |
С3 |
С1 |
С3 |
С1 |
С7 |
С5 |
С6 |
x3 |
С9 |
|
С9 |
С6 |
С1 |
С8 |
С6 |
С7 |
С2 |
С4 |
С1 |
По таблице разбиения 1 (табл. 2.3.) выполним разбиение 2.
2={D1, D2, D3, D4, D5, D6, D7, D8, D9}.
D1={ a1, а10}, D2={а5}, D3={а9}, D4={а2}, D5={a6}, D6={а8}, D7={а3}, D8={а4}, D9={a7}.
Разбиение 2 повторяет разбиение 1 – процедура разбиений может быть завершена. Из каждого класса эквивалентности выбираем по одному представителю этого класса. Из множества D1={ a1, а10} выбираем a1, т.к. a1≡ а10.
В таблице переходов столбец, соответствующий состоянию а10 вычеркиваем, а в оставшейся части таблицы заменяем а10 на а1. Получаем совмещенную таблицу переходов и выходов минимального автомата. (Таблица 2.4.).
Таблица 2.4 – Совмещенная таблица переходов и выходов минимального автомата.
У |
y1 |
y2 |
y3 |
y4 |
y1 |
y2 |
y4 |
y2 |
y1 |
|
A |
a1 |
a2 |
а3 |
а4 |
а5 |
a6 |
а7 |
a8 |
a9 |
|
Х |
||||||||||
|
|
|
|
|
|
|
|
|
||
x1 |
a1 |
а3 |
a6 |
а4 |
а7 |
а5 |
а4 |
a9 |
а7 |
|
x2 |
а5 |
a1 |
а3 |
a6 |
a1 |
a9 |
a8 |
a1 |
a9 |
|
x3 |
а7 |
а4 |
а5 |
a2 |
a8 |
a8 |
a1 |
а3 |
a1 |
10