Проектирование элементов ЭВУ, страница 4

Рис.2. Преобразование автомата Мили в автомат Мура

       Автомат Мили задан своим графом (рис.1) и совмещенной таблицей переходов и выходов (табл.17).

Табл.17. Совмещенная таблица переходов и выходов автомата Мили

Сост. входа

a1

a2

a3

a4

Z1

a2/W2

a4/W2

Z2

a1/W3

a1/W3

a4/W4

Z3

a3/W4

Z4

a2/W2

a3/W2

a2/W2

Для перехода к автомату Мура найдем множества BS , определяемые числом различных выходных сигналов на дугах, входящих в данное состояние (см. рис.1).

B1 = {a1W3}={b1}

B2 = {a2W2}={b2}

B3 = {a3W2 , a3W4}={b3 , b4}

B4 = {a4W2 , a4W4}={b5 , b6}

Составим таблицу переходов автомата Мура по таблице переходов автомата Мили и найденных состояний BS (s = 1,2,3,4).

Табл.18. Таблица переходов автомата Мура

                                             a1         a2             a3                     a4


Сост. входа

b1/W3

b2/W2

b3/W2

b4/W4

b5/W2

b6/W4

Z1

b2

b5

b5

Z2

b1

b1

b1

b6

b6

Z3

b4

b4

Z4

b2

b3

b2

b2


 
 


По полученной таблице переходов составляем граф автомата Мура (рис.3).

Рис.3. Граф автомата Мура

       Абстрактные автоматы Мили и Мура эквивалентны. Это можно проверить, подавая на входы автоматов некоторую последовательность Zбукв входного алфавита. При этом выходная последовательность Wобоих автоматов одинакова (начальные состояния автоматов a1 и b1 соответственно).

2.2. Составление схемы алгоритма и программы, реализующей автомат Мура на языке ассемблера микропроцессора К580.

       Программа, моделирующая работу автомата Мура, должна реализовывать алгоритм его работы в соответствии с уравнениями:

,        

       Также она должна занимать, по возможности, наименьшее число ячеек памяти вычислителя. Роль элементов памяти автомата выполняют двоичные разряды ячеек памяти или регистров микропроцессорного устройства.

       Определим число двоичных разрядов, необходимое для представления кодов входных сигналов

;

и всех внутренних состояний (выходных сигналов)

; .


 
 


       Кодируем автомат.

Табл.19. Входные сигналы                             Табл.20. Внутренние состояния и выходные сигналы

Сост. входа

Биты кода

x1

x2

Z1

0

0

Z2

0

1

Z3

1

0

Z4

1

1

Внут. сост.

Биты кода

Биты кода

Вых. сигнал

Q1

Q2

Q3

y1

y2

b1

0

0

0

1

0

w3

b2

0

0

1

0

1

w2

b3

0

1

0

0

1

w2

b4

0

1

1

1

1

w4

b5

1

0

0

0

1

w2

b6

1

0

1

1

1

w4

       Переводим таблицу переходов (выходов) в двоичный алфавит.

Табл.21. Таблица переходов (выходов) в двоичном алфавите

x1 x2

Q1 Q2Q3/y1y2

000/10

001/01

010/01

011/11

100/01

101/11

00

001

100

100

01

000

000

000

101

101

10

011

011

11

001

010

001

001