Logo GenDocs.ru

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

Загрузка...

Разработка цифрового автомата мили - файл Курсовая.doc


Разработка цифрового автомата мили
скачать (24.2 kb.)

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

Курсовая.doc226kb.27.09.2007 21:40скачать


Курсовая.doc

Агентство по образованию Российской Федерации

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

КУРСОВАЯ РАБОТА
По дисциплине «Математические основы теории систем»


Выполнила: Игонькина Н.С

Курс: 3

Факультет: САА и У

Форма обучения: заочная

Специальность: 220201

Шифр: 6420309032

Вариант: 2

Проверил: Пашкин В.Я.

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

2007 год

Задание на курсовой проект:

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

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

Б) Построить графы исходного минимизированного автомата;

В) Произвести структурный синтез автомата на элементах памяти для D-триггера.

Г) Вычертить логическую схему минимизированного автомата.
A) Автоматом называется дискретный преобразователь информации, способный принимать различные состояния, переходить под воздействием входных сигналов из одного состояния в другое и выдавать выходные сигналы. Если множество состояний автомата, а так же множества входных и выходных сигналов конечны, то автомат называется конечным автоматом.

Применяемые на практике автоматы принято разделять на два класса: - это автоматы Мили и автоматы Мура, названные так по имени американских ученых, которые впервые начали их изучать.

Закон функционирования автоматов Мили описывается следующей системой уравнений:

a(t + 1) = [a(t),x(t)] 

y(t) = [a(t),x(t)]  .

t = 0,1,2,3… 

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

Алгоритм минимизации заключается в следующем:

  1. Все внутренние разбиваются на группы по числу выходных сигналов.

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

  3. Проводят новое разделение внутренних состояний на группы, объединяя в каждой группе состояния, отмеченные одинаковой последовательностью букв. В нашем случае каждая из двух групп распадается на две группы, по числу различных последовательностей букв.

  4. Пользуясь таблицей переходов автомата, вновь отмечают каждое состояние последовательностью букв. Разделение состояний на новые группы продолжают до тех пор, пока новые группы состояний появляться не будут. В курсовом проекте последней таблицей является Таблица 6.

Таблица 1. Таблица переходов.


входные символы

Состояния

S1

S2

S3

S4

S5

S6

S7

S8

X1

S3

S4

S4

S1

S7

S4

S4

S1

X2

S4

S5

S7

S7

S3

S7

S4

S6

X3

S5

S6

S2

S2

S8

S2

S6

S7



Таблица 2. Таблица выходов.


входные символы

Состояния

S1

S2

S3

S4

S5

S6

S7

S8

X1

Y1

Y3

Y2

Y1

Y1

Y1

Y3

Y1

X2

Y1

Y1

Y2

Y2

Y2

Y2

Y1

Y2

X3

Y3

Y1

Y3

Y3

Y2

Y3

Y1

Y2


Таблица3.

входные символы

1-классы

S1

S2

S3

S4

S5

S6

S7

S8

X1

Y1

Y3

Y2

Y1

Y1

Y1

Y3

Y1

X2

Y1

Y1

Y2

Y2

Y2

Y2

Y1

Y2

X3

Y3

Y1

Y3

Y3

Y2

Y3

Y1

Y2

1-классы

А1

A2

A3

A4

А5

А4

А2

А5


Таблица 4.


2-классы

входные символы

A1

A2

A3

A4

A5

S1

S2

S7

S3

S4

S6

S5

S8

X1

A3

A4

A4

A4

A1

A4

A2

A1

X2

A4

A5

A4

A4

A2

A2

A3

A4

X3

A5

A4

A4

A2

A2

A2

A5

A2

2-классы

B1

B2

B3

B4

B5

B6

B7

B8


Таблица 5.

3-классы

входные символы

B1

B2

B3

B4

B5

B6

B7

B8

S1

S2

S7

S3

S4

S6

S5

S8

X1

B4

B5

B5

B5

B1

B5

B3

B1

X2

B5

B7

B5

B3

B3

B3

B4

B6

X3

B7

B6

B6

B2

B2

B2

B8

B3

3-классы

C1

C2

C3

C4

C5

C4

C6

C7

Таблица 6.


4-классы

входные символы

C1

C2

C3

C4

C5

C6

C7

S1

S2

S7

S3

S6

S4

S5

S8

X1

C4

C5

C5

C5

C5

C1

C3

C1

X2

C5

C6

C5

C3

C3

C4

C4

C4

X3

C6

C4

C4

C2

C2

C2

C7

C3

4-классы

D1

D2

D3

D4

D4

D5

D6

D7


Б) Граф минимизированного автомата представлен в Приложении 6.

D1 {S1},D2{S2},D3{S7},D4{S3,S6},D5{S4},D6{S5}D7{S8}.

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

Функции переходов элементарных двоичных автоматов Мура, которые будут использоваться в синтезе конечного автомата, приведены в таблице 12., где u-входной двоичный сигнал автомата, v-выходной двоичный сигнал , совпадающий с состоянием автомата. В таблице 12 элемент задержки выполнен в виде D-триггера.

Таблица 7. Таблица выходов.


входные символы

Состояния

S1

S2

S3

S4

S5

S7

S8

X1

S3

S4

S4

S1

S7

S4

S3

X2

S4

S5

S7

S4

S3

S4

S4

X3

S5

S3

S2

S2

S8

S3

S7


Таблица 8. Таблица переходов.

входные символы

Состояния

S1

S2

S3

S4

S5

S7

S8

X1

Y1

Y3

Y2

Y1

Y1

Y3

Y1

X2

Y1

Y1

Y2

Y2

Y2

Y1

Y2

X3

Y3

Y1

Y3

Y3

Y2

Y1

Y2


Закодируем входные и выходные символы и состояния автомата (см. таблица 9,10). Используя эти коды, построим закодированные таблицы переходов и выходов структурного автомата таблица 13,14.


Таблица 10.

Таблица 9.


входные символы

z1

z2

X1

0

0

X2

0

1

X3

1

1

входные символы

z1

z2

Y1

0

1

Y2

1

1

Y3

0

0


Таблица 11.


 

 

V1

V2

V3

S1

0

0

0

S2

0

0

1

S3

0

1

1

S4

0

1

0

S5

1

0

0

S7

1

1

1

S8

1

1

0

u

V1




0

1

0

0

1

1

1

0
Таблица 12.T -триггер
Таблица 13.



Входной ход  z1,z2

Код состояния v1,v2,v3 

000

001

011

010

100

101

111

110

00

 -

 -

 -

 -

 -

 -

 -

 -

01

011

010

010

000

101

 -

010

011

11

010

100

101

010

011

 -

010

010

10

100

011

001

011

111

 -

011

111


Таблица 14.


 

 

000

001

011

010

100

101

111

110

00

 -

 -

 -

 -

 -

-

 -

 -

01

10

01

11

10

10

-

01

10

11

10

10

11

11

11

-

10

11

10

01

10

01

01

11

-

10

11


Находим функции возбуждения для D-триггеров.

Таблица V1.


 z1z2

v1v2v3 

000

001

011

010

100

101

111

110

00

 -

 -

 -

 -

 -

-

 -

 -

01

0

0

0

0

1

-

0

0

11

0

1

1

0

0

-

0

0

10

1

0

0

0

1

-

0

1

U1=

  z1z2

v1v2v3  

000

001

011

010

100

101

111

110

00

 -

 -

 -

 -

 -

-

 -

 -

01

1

1

1

0

0

-

1

1

11

1

0

0

1

1

-

1

1

10

0

1

0

1

1

-

1

1
Таблица V2.

U2=



  z1z2

v1v2v3   

000

001

011

010

100

101

111

110

00

 -

 -

 -

 -

 -

-

 -

 -

01

1

0

0

0

1

-

0

1

11

0

0

1

0

1

-

0

0

10

0

1

1

1

1

-

1

1
Таблица V3

U3=

z1z2 

v1v2v3  

000

001

011

010

100

101

111

110

00

 -

 -

 -

 -

 -

-

 -

 -

01

1

0

1

1

1

-

0

1

11

1

1

1

1

1

-

1

1

10

0

1

0

0

1

-

1

1



Таблица P1

P1=



  z1z2

v1v2v3   

000

001

011

010

100

101

111

110

00

 -

 -

 -

 -

 -

-

 -

 -

01

0

1

1

0

0

-

1

0

11

0

0

1

1

1

-

0

1

10

1

0

1

1

1

-

0

1
Таблица P2

P2=
Г) Логическая схема минимизированного автомата представлена в приложении 1,2,3,4,5.


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

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

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