Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:

Курсовой проект_Комп_логика_пример_рус

.pdf
Скачиваний:
13
Добавлен:
26.03.2015
Размер:
746.49 Кб
Скачать

МИНИСТЕРСТВО ОБРАЗОВАНИЯ УКРАИНЫ

ВОСТОЧНОУКРАИНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СЕВЕРОДОНЕЦКИЙ ТЕХНОЛОГИЧЕСКИЙ ИНСТИТУТ ФАКУЛЬТЕТ КТ

КАФЕДРА ВПМ

Пояснительная записка к курсовому проекту по дисциплине:

«Компьютерная логика» на тему: «Синтез управляющего автомата Мура»

Студент группы КИ-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

Калькулятор

Сервис бесплатной оценки стоимости работы

  1. Заполните заявку. Специалисты рассчитают стоимость вашей работы
  2. Расчет стоимости придет на почту и по СМС

Нажимая на кнопку, вы соглашаетесь с политикой конфиденциальности и на обработку персональных данных.

Номер вашей заявки

Прямо сейчас на почту придет автоматическое письмо-подтверждение с информацией о заявке.

Оформить еще одну заявку