Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Основные принципы синтеза конечных автоматов (вариант 14) - файл КП 1 часть.docx


Основные принципы синтеза конечных автоматов (вариант 14)
скачать (251.2 kb.)

Доступные файлы (2):

КП 1 часть.docx182kb.12.04.2009 00:07скачать
КП 2 часть.docx184kb.14.04.2009 00:31скачать

содержание
Загрузка...

КП 1 часть.docx

Реклама MarketGid:
Загрузка...


ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

Государственное образовательное учреждение высшего профессионального образования

Северо-Западный государственный заочный технический университет

Институт информационных систем и вычислительной техники

Кафедра вычислительных машин, комплексов, систем и сетей


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

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

«Теория автоматов»


Студент: Корчагин Ю. И.

Шифр: 7401031997

Специальность: 230101.65 Курс: 3

Дата защиты:

Оценка:

Преподаватель: Иванова И. В.


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

2009



АННОТАЦИЯ


В курсовом проекте представлены и рассмотрены основные принципы синтеза конечных автоматов.

Курсовое проектирование имеет две части:

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

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




СОДЕРЖАНИЕ


Введение …………………………………………………………….……….…….. 4


Основная часть ………………………………………………………….…….….. 5


  1. Минимизация абстрактного автомата, заданного таблицей переходов/выходов ……………………………………………………..…. 5



    1. Минимизирование числа состояний абстрактного автомата ………. 5



    1. Построение реакций исходного автомата и

минимизированного автомата на входное воздействие ……………. 7


    1. Синтезирование автомата на элементах ИЛИ-НЕ и

Т – триггерах и на элементах И-НЕ и JK – триггерах ……………... 7



  1. Синтез микропрограммных управляющих автоматов

на базе логических матриц………………………………………………. 15


    1. Разработка микропрограммного автомата, реализующего микропрограмму ……………………………………………………... 15



    1. Разработка счетчика числа микрокоманд, работающего

в двоично-десятичном коде Грея …………………………………… 18


    1. Синтез таймера для счетчика ………………………………………... 20




  1. Заключение ……………………………………………………………….. 22



  1. Список использованной литературы…………………………………… 23





ВВЕДЕНИЕ


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

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




^ ОСНОВНАЯ ЧАСТЬ


  1. Минимизация абстрактного автомата, заданного таблицей переходов/выходов.


Абстрактный автомат Мили задан таблицей переходов/выходов:



x(t)

S(t)

S1

S2

S3

S4

S5

S6

S7

S8

x1

s4/y3

s8/y1

s5/y1

s6/y3

s8/y1

s5/y1

s4/y3

s1/y1

x2

s2/y2

s4/y3

s1/y3

s8/y2

s4/y3

s7/y3

s5/y2

s6/y3

x3

s3/y1

s1/y2

s8/y2

s2/y1

s7/y2

s8/y2

s3/y1

s4/y2


Эта таблица определяет функцию переходов автомата s(t+1) = П[x(t), s(t)] и функцию выходов y(t) =B[x(t), y(t)]. Здесь s(t) – состояние, x(t) – входной и y(t) – выходной символ автомата в момент времени t.


Требуется:

а) Минимизировать число состояний абстрактного автомата;

б) построить реакции исходного автомата и минимизированного автоматов на входное воздействие х3х1х2х1х2х2х1х3, если начальное состояние автомата s[0]=s1;

в) синтезировать автомат на элементах ИЛИ-НЕ и Т-триггерах;

г) синтезировать автомат на элементах И-НЕ и JK-триггерах;

д) разработать программу, моделирующую работу структурного автомата.


    1. Минимизирование числа состояний абстрактного автомата.


Таблица 1.


x(t)

S(t)

S1

S2

S3

S4

S5

S6

S7

S8

x1

s4/y3

s8/y1

s5/y1

s6/y3

s8/y1

s5/y1

s4/y3

s1/y1

x2

s2/y2

s4/y3

s1/y3

s8/y2

s4/y3

s7/y3

s5/y2

s6/y3

x3

s3/y1

s1/y2

s8/y2

s2/y1

s7/y2

s8/y2

s3/y1

s4/y2

В1 В2 В2 В1 В2 В2 В1 В2


Разбиение на 1-классы эквивалентности осуществляется путем выявления одинаковых столбцов таблицы 1, при этом получаем:


П={В1, В2}, где

В1={s1, s4, s7},

В2={s2, s3, s5, s6, s8}.


Строим таблицу 1-разбиения и из нее находим разбиение на 2-классы.




Таблица 2.


x(t)

В1

В2

s1

s4

s7

s2

s3

s5

s6

s8

x1

В1

В2

В1

В2

В2

В2

В2

В1

x2

В2

В2

В2

В1

В1

В1

В1

В2

x3

В2

В2

В2

В1

В2

В1

В2

В1

С1 С2 С1 С3 С4 С3 С4 С5


П={С1, С2, С3, С4, С5}, где

С1={s1,s7},

C2={s4},

C3={s2, s5},

C4={s3,s6},

C5={s8}.


Строим таблицу 2-разбиения и из нее находим разбиение на 3-классы.


Таблица 3.


x(t)

C1

C2

C3

C4

C5

s1

s7

s4

s2

s5

s3

s6

s8

x1

C2

C2

C4

C5

C5

C3

C3

C1

x2

C3

C3

C5

C2

C2

C1

C1

C4

x3

C4

C4

C3

C1

C1

C5

C5

C2

D1 D1 D2 D3 D3 D4 D4 D5


П={D1, D2, D3, D4, D5}, где

D1={s1, s7},

D2={s4},

D3={s2, s5},

D4={s3, s6},

D5={s8}.


Таким образом найдены ∞-классы. Оставляем в каждом классе эквивалентности по 1 состоянию. Удаляем в исходной таблице столбы, соответствующие лишним состояниям , переименовываем в оставшихся столбцах удаленные состояния именами представителей и получаем таблицу переходов минимизированного автомата Мили.


Таблица 4.




s1

s4

s2

s3

s8

x1

s4/y3

s3/y3

s8/y1

s2/y1

s1/y1

x2

s2/y2

s8/y2

s4/y3

s1/y3

s3/y3

x3

s3/y1

s2/y1

s1/y2

s8/y2

s4/y2




    1. 

    2. Построение реакций исходного автомата и минимизированного автоматов на входное воздействие.


Построим граф-схему автомата.


Рисунок 1. Синтез схемы конечного автомата.


Составим таблицу реакций исходного и минимизированного автоматов.


Таблица 5.


1 2 3 4 5 6 7 8

Входное воздействие

x3

x1

x2

x1

x2

x2

x1

x3

Не минимизированный

y1

y1

y3

y3

y3

y2

y1

y2

Минимизированный

y1

y1

y3

y3

y3

y2

y1

y2




    1. Cинтезирование автомата на элементах ИЛИ-НЕ и Т-триггерах и на элементах И-НЕ и JK-триггерах


Кодирование внутренних состояний входных, выходных сигналов (кодирование произвольное):




Построение абстрактной и структурной таблицы.


Таблица 6.





sn


Sn+1

Входной

выходной

k(sn)

k(sn+1)

δ

xi

x’

x’’

yi

y’

y’’

Q1

Q2

Q3

Q1

Q2

Q3

V1

V2

V3

1

s1

s4

x1

0

0

y3

0

0

0

0

0

0

1

1

0

+

+

2

s1

s2

x2

0

1

y2

1

1

0

0

0

0

0

1

0

0

+

3

s1

s3

x3

1

1

y1

1

0

0

0

0

0

1

0

0

+

0

4

s2

s8

x1

0

0

y3

0

0

0

0

1

1

0

0

+

0

-

5

s2

s4

x2

0

1

y2

1

1

0

0

1

0

1

1

0

+

1

6

s2

s1

x3

1

1

y1

1

0

0

0

1

0

0

0

0

0

-

7

s3

s2

x1

0

0

y1

1

0

0

1

0

0

0

1

0

-

+

8

s3

s1

x2

0

1

y3

0

0

0

1

0

0

0

0

0

-

0

9

s3

s8

x3

1

1

y2

1

1

0

1

0

1

0

0

+

-

0

10

s4

s3

x1

0

0

y1

1

0

0

1

1

0

1

0

0

1

-

11

s4

s8

x2

0

1

y3

0

0

0

1

1

1

0

0

+

-

-

12

s4

s2

x3

1

1

y2

1

1

0

1

1

0

0

1

0

-

1

13

s8

s1

x1

0

0

y1

1

0

1

0

0

0

0

0

-

0

0

14

s8

s3

x2

0

1

y3

0

0

1

0

0

0

1

0

-

+

0

15

s8

s4

x3

1

1

y2

1

1

1

0

0

0

1

1

-

+

+


Составление обобщенных карт Карно.

Т-триггер. Т=∪{+, –, (Ø)}

Для V1




Q1Q2Q3

x’x’’

000

001

011

010

110

111

101

100

00

0

+

0

0

x

x

x

-

01

0

0

+

0

x

x

x

-

11

0

0

0

+

x

x

x

-

10

x

x

x

x

x

x

x

x



T=x''&Q2&Q3∨x'&x''&Q2&Q3∨x'&Q2&Q3∨Q1


ИЛИ-НЕ=x''∨Q2∨Q3∨x'∨x''∨Q2∨Q3∨x'∨Q2∨Q3∨Q1


Для V2.




Q1Q2Q3

x’x’’

000

001

011

010

110

111

101

100

00

+

0

1

-

x

x

x

0

01

0

+

-

-

x

x

x

+

11

+

0

-

-

x

x

x

+

10

x

x

x

x

x

x

x

x





T=x''&Q1&Q3∨x'&x''&Q3∨x'&Q2&Q3∨x''&Q2∨x''&Q1


ИЛИ-НЕ==x''∨Q1∨Q3∨x'∨x''∨Q3∨x'∨Q2∨Q3∨x''∨Q2∨x''∨Q1


Для V3.




Q1Q2Q3

x’x’’

000

001

011

010

110

111

101

100

00

+

-

-

+

x

x

x

0

01

+

1

-

0

x

x

x

0

11

0

-

1

0

x

x

x

+

10

x

x

x

x

x

x

x

x



T=x'&Q1&Q2&Q3∨x''&Q1∨x'&Q2&Q3∨x'&Q2&Q3∨x'&Q1


ИЛИ-НЕ==x'∨Q1∨Q2∨Q3∨x''∨Q1∨x'∨Q2∨Q3∨x'∨Q2∨Q3∨(x'∨Q1)


JK-триггер. J=∪{+, (–), (1), (Ø)}; K=∪{–, (+), (0), (Ø)}


Для V1, J-триггер




Q1Q2Q3

x’x’’

000

001

011

010

110

111

101

100

00

0

+

0

0

x

x

x

-

01

0

0

+

0

x

x

x

-

11

0

0

0

+

x

x

x

-

10

x

x

x

x

x

x

x

x



J=x'&Q2&Q3∨x'&x''&Q2&Q3∨x'&Q2&Q3


И-НЕ=x'&Q2&Q3&x'&x''&Q2&Q3&x'&Q2&Q3


Для V1, K-триггер.




Q1Q2Q3

x’x’’

000

001

011

010

110

111

101

100

00

0

+

0

0

x

x

x

-

01

0

0

+

0

x

x

x

-

11

0

0

0

+

x

x

x

-

10

x

x

x

x

x

x

x

x





K=Q1

И-НЕ=Q1


Для V2, J-триггер.




Q1Q2Q3

x’x’’

000

001

011

010

110

111

101

100

00

+

0

1

-

x

x

x

0

01

0

+

-

-

x

x

x

+

11

+

0

-

-

x

x

x

+

10

x

x

x

x

x

x

x

x



J=x''&Q1&Q3∨x'&Q2&Q3∨x'&x''&Q3∨x''&Q1


И-НЕ=x''&Q1&Q3&x'&Q2&Q3&x'&x''&Q3&x''&Q1


Для V2, К-триггер.




Q1Q2Q3

x’x’’

000

001

011

010

110

111

101

100

00

+

0

1

-

x

x

x

0

01

0

+

-

-

x

x

x

+

11

+

0

-

-

x

x

x

+

10

x

x

x

x

x

x

x

x



K=x''&Q2∨Q2&Q3


И-НЕ=x''&Q2&Q2&Q3


Для V3, J-триггер.




Q1Q2Q3

x’x’’

000

001

011

010

110

111

101

100

00

+

-

-

+

x

x

x

0

01

+

1

-

0

x

x

x

0

11

0

-

1

0

x

x

x

+

10

x

x

x

x

x

x

x

x



J=x'&Q1&Q2∨x''&Q1∨x'&Q1


И-НЕ=x'&Q1&Q2∨x''&Q1∨x'&Q1





Для V3, К-триггер.




Q1Q2Q3

x’x’’

000

001

011

010

110

111

101

100

00

+

-

-

+

x

x

x

0

01

+

1

-

0

x

x

x

0

11

0

-

1

0

x

x

x

+

10

x

x

x

x

x

x

x

x


K=x'&Q1&Q2∨x''&Q1∨x'&Q2


И-НЕ=x'&Q1&Q2&x''&Q1&x'&Q2


Функции выходов.

Для y’, объединение по 1.




Q1Q2Q3

x’x’’

000

001

011

010

110

111

101

100

00

0

0

1

1

x

x

x

1

01

1

1

0

0

x

x

x

0

11

1

1

1

1

x

x

x

1

10

x

x

x

x

x

x

x

x



И-НЕ=x''&Q1&Q2∨x'&Q2∨x''&Q1∨x'=x''&Q1&Q2&x'&Q2&x''&Q1&x'


Для y’, объединение по 0.




Q1Q2Q3

x’x’’

000

001

011

010

110

111

101

100

00

0

0

1

1

x

x

x

1

01

1

1

0

0

x

x

x

0

11

1

1

1

1

x

x

x

1

10

x

x

x

x

x

x

x

x



ИЛИ-НЕ=x''∨Q1∨Q2&x'∨x''∨Q2&x'∨x''∨Q1=x''∨Q1∨Q2∨x'∨x''∨Q2∨x'∨x''∨Q1


Для y’’, объединение по 1.




Q1Q2Q3

x’x’’

000

001

011

010

110

111

101

100

00

0

0

0

0

x

x

x

0

01

1

1

0

0

x

x

x

0

11

0

0

1

1

x

x

x

1

10

x

x

x

x

x

x

x

x



И-НЕ=x'&x''&Q1&Q2∨x'&Q2∨x'&Q1=x'&x''&Q1&Q2&x'&Q2&x'&Q1


Для y’’, объединения по 0.




Q1Q2Q3

x’x’’

000

001

011

010

110

111

101

100

00

0

0

0

0

x

x

x

0

01

1

1

0

0

x

x

x

0

11

0

0

1

1

x

x

x

1

10

x

x

x

x

x

x

x

x


ИЛИ-НЕ=x''&x'∨Q1∨Q2&x'∨Q2&x'∨Q1=x''∨x'∨Q1∨Q2∨x'∨Q2∨x'∨Q1


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





Рисунок 2. Схемная реализация автомата на элементах ИЛИ-НЕ и Т-триггерах.




Рисунок 3. Схемная реализация автомата на элементах И-НЕ и JK-триггерах


Скачать файл (251.2 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации