Построение не полностью определенного автомата

Учет взаимодействия операционного и управляющего автоматов позволяет получить не полностью определенный (частичный автомат), что дает больше возможностей для упрощения схемы автомата.

При построении графа автомата по ГСА микропрограммы получается полностью определенный автомат, т.е. из каждого состояния существуют переходы по каждому набору значений логических условий. Из рассмотрения работы реальных операционных устройств (например, для сложения двух целых двоичных чисел) можно сделать вывод, что некоторые наборы значений логических условий никогда не поступят на входы управляющего автомата и следовательно, переходы по этим наборам можно исключить из задания автомата. Из учета взаимодействия операционного и управляющего автоматов нужно определить для каждого состояния s_i множество наборов значений логических условий U_i, которые могут поступить на входы управляющего автомата, когда он находится в состоянии s_i.

Для этого необходимо знать:

1. множество наборов U₀, которые могут поступить на входы управляющего автомата, когда он находится в состоянии s₀;

2. каким образом влияет каждая микрооперация y_j на значение логического условия x_i в результате выполнения этой микрооперации в операционном автомате.

Для определения всех множеств U_i необходимо просмотреть все переходы автомата в виде дерева его переходов, одновременно определяя для каждого состояния s_i множество наборов значений логических условий U_i. Просмотр переходов автомата необходимо продолжать до тех пор пока все U_i не станут устойчивыми множествами т.е.пока в них не перестанут появляться новые наборы в множествах U_i.

После получения всех множеств U_i, в исходной таблице переходов и выходов полностью определенного автомата, надо исключить переходы из каждого состояния s_i по наборам не содержащимся в его U_i.

Пример получения частичного автомата Мили.

Ранее по исходной ГСА был построен граф минимального полностью определенного автомата Мили (рис.5.4). Таблица переходов и выходов этого автомата приведена в табл. 5.3.

Таблица 5.3

x1x2 si
s0	s1 / 010	s1 / 010	s1 / 010	s1 / 010
s1	s1 / 010	s4 / 001	s0 / 001	s3 / 011
s3	s0 / 100	s0 / 100	s0 / 100	s0 / 100
s4	s1 / 010	s0 / 100	s0 / 100	s1 / 010

Из исходного задания (табл. 5.3) известно, что перед началом работы автомата на его входы подается набор значений логических условий
x₁ x₂= 11, т.е. U₀ = {11}. Из табл. 5.3 следует, что после выполнения микроопераций значения логических условий меняются следующим образом:

y₀: x₁ := x₁; x₂ := 0;

y₁: x₁ := ₁; x₂ := Z, т.е. значение x₂ может быть любым (0 или 1);

y₂: x₁ := x₁; x₂ := 1.

Просмотр переходов для определения множеств U_i начинается из состояния s₀ по входному набору 11 . В результате перехода в s₁ с выдачей y₁ определяются первые элементы множества U₁ = {00, 01} , так как
x₁ := ₁; , а x₂ := z. По набору 00 автомат останется в s₁ с повторной выдачей y₁. В результате к U₁ добавятся еще два набора, т.е. 11 и 10. U₁ = {00, 01, 11, 10}. Далее из s₁, возможны три различных пути.

Первый путь из s₁ соответствует набору 10, происходит переход из s₁ в s₃ с выдачей y₁ y₂ . В результате влияния y₁ на x₁ эта переменная изменит свое значение на противоположное. На x₂ влияют обе микрооперации, поэтому ее значение может быть любым. Получается U₃ = {01, 00}. Далее переход из s₃ в s_o c выдачей у₀ добавит к U₀ набор 00, т.е. U₀= {11, 00} . Второй путь из s₁ по набору 01: s₁ →s₄ → s₀ определяет U₄ = {01} и не добавляет новых наборов к U₀ . Третий путь из s₁ по набору 11 в s₀ с выдачей у₂ также не приводит к появлению новых входных наборов. Окончательно сформированные множества входных наборов компактно представляются следующими троичными векторами:

U₀ = {11, 00} , U₁ ={ZZ}, U₃ = {0Z}, U₄ = {01}.

Схема просмотренных путей в виде дерева переходов приведена на рис. 5.5.

s0

s1

U1 = {0Z}

11 0Z

y1

s1

s4

U0={11}

U1={ZZ}

U4={01}

00 1Z

y1

01 01

y2

s3

s0

s0

s0

10 0Z

y1 y2

11 11

y2

U3={0Z}

0Z 00

y0

01 00

y0

U0={11,00}

00 1Z

y1

U1={ZZ}

U0={11,00}

s1

s1

U0={11,00}

Рис. 5.5.

После удаления из таблицы 5.3 переходов по наборам не содержащихся в найденных множествах U_i получается таблица переходов и выходов частичного автомата (табл. 5.4).

В полученном не полностью определенном автомате состояние s₃ совместимо с состоянием s₄. После объединения этих состояний и присвоения этому объединенному состоянию символ s₂ получается минимальный частичный автомат Мили (табл. 5.5).

Таблица 5.4

x1x2 si
s0	s1 / 010	---	s1 / 010	---
s1	s1 / 010	s4 / 001	s0 / 001	s3 / 011
s3	s0 / 100	s0 / 100	---	---
s4	---	s0 / 100	---	---

Таблица 5.5

x1x2 si
s0	s1 / 010	---	s1 / 010	---
s1	s1 / 010	s2 / 001	s0 / 001	s2 / 011
s2	s0 / 100	s0 / 100	---	---

Из рассмотренного примера следует, что абстрактный синтез микропрограммного автомата состоит из выполнения следующих этапов:

1. построение графа автомата по микропрограмме, заданной графической схемой алгоритма;

2. минимизация числа состояний полностью определенного автомата;

3. получение не полностью определенного автомата;

4. минимизация числа состояний не полностью определенного автомата

Структурный этап синтеза микропрограммного автомата не отличается от структурного этапа канонического метода синтеза.

АСИНХРОННЫЙ АВТОМАТ

Асинхронным автоматом называется автомат, изменение состояния которого может происходить в произвольный момент времени, и этот моменты времени определяются изменением входного сигнала.

Выбор способа реализации автомата (синхронный или асинхронный) определяется способом представления входного сигнала.

Примеры основных способов представления входных сигналов:

1. потенциальный с синхронизацией;

t

t

c

x1

t

t

V

c

x1

2. импульсный сигнал;

x2

t

V

3. потенциальный сигнал.

x3

t

V

При потенциальном сигнале высокий уровень потенциала соответствует логической единице, низкий – логическому нулю, длительности 1 и 0 могут быть разными.

Первые два способа представления сигнала определяют синхронную реализацию, а третий асинхронную.

s1

x1…xn С

1…xn С

x1…xn

Рис. 6.1

В синхронном автомате сигнал синхронизации C обеспечивает устойчивую работу автомата и учитывается неявно. На рис. 6.1 приведен пример фрагмента графа, с явным учетом сигнала синхронизации, на нем при C = 0 не происходит изменения текущего состояния автомата.

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

Состояние s_i называется устойчивым, если при переходе в это состояние под воздействием входного символа p_k автомат остается в этом состоянии до тех пор, пока на его вход не поступит символ отличный от p_k (рис. 6.1).

si

pk

pi

pk

Рис. 6.2

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

Пример асинхронного автомата (рис. 6.3):

s2/0

s1/0

s3/1

Рис. 6.3

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

Пусть автомат находится в устойчивом состоянии s₁ воздействием входного сигнала 00 и если входной сигнал изменился на 10, то для определения состояния, в которое переходит автомат необходимо:

1. двигаться по строке соответствующей текущему состоянию до столбца, отмеченного новым входным сигналом, определяется состояние, в которое должен перейти автомат;

2. двигаться по этому столбцу до устойчивого нового состояния.

Таблица 6.1

wi	x1x2 si
	s1	(s1)	(s1)	s2	s3
	s2	s1	(s2)	(s2)	(s2)
	s3	s1	s2	s2	(s3)

Двигаясь по строке отмеченной символом текущего состояния s₁ от столбца, отмеченного текущим сигналом 00, до столбца отмеченного новым входным сигналом 10 определяем новое состояние s₃. Далее двигаться по столбцу, отмеченного новым входным сигналом 10, до устойчивого нового состояния (s₃).

6.1. Синтез асинхронного автомата

Синтез асинхронного автомата отличается от синтеза синхронного автомата.

На абстрактном этапе синтеза асинхронного автомата отличие состоит в выполнении следующих дополнительных действий:

1. перекодированием входных и выходных символов для обеспечения распознавания соседних одинаковых символов;

2. при переходе от алфавитного оператора и графу автомату необходимо сделать все состояния автомата устойчивыми.

Пример необходимости перекодирования входных и выходных символов абстрактного автомата A.

Пусть P = W = {a, b, c}. Входное слово a a b b автомат перерабатывает в выходное слово b c c a. При переходе к структурному автомату символы кодируются: a = 00, b = 11, c = 10.

b b a a

a c c b

A

A

1 1 0 0 1 1 0 0

0 1 1 1 0 0 0 1

x1

x2

y1

y2

Рис. 6.4

На рис. 6.4 видно, что на уровне сигналов структурного автомата два одинаковых, подряд следующих символа, не различимы.

Необходимо расширить алфавиты: P’ = W’ = {a, a’, b, b’, c, c’}. Теперь входное слово a a’ b b’ автомат перерабатывает в выходное слово b c c’ a’ (Рис. 6.5). При переходе к структурному автомату символы кодируются: a = 000, a’ = 001, b = 110, b’ = 111, c = 100, c’ = 101.

y1

x1

b’ b a’ a

a’ c’ c b

A

A

1 1 0 0 1 1 0 0 1 0 1 0

0 1 1 1 0 0 0 1 1 1 0 0

x2

x3

y2

y3

Рис. 6.5

Расширение алфавита требует введение третьего разряда в код символа, но позволяет различать два одинаковых, подряд следующих символа.

На структурном этапе синтеза асинхронного автомата отличие состоит в следующем:

1. другой целью кодирования состояний автомата;

2. другой целью синтеза комбинационной схемы;

3. элементом памяти, используемым в автомате.

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

Состязание элементов памяти

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

si

sj

x

y1y2 0 1

y1y2 0 1

Рис. 6.6

Пусть во фрагменте графа (рис. 6.6) при переходе из s_i в s_j элементы памяти y₁ и y₂ имеют задержки ∆₁ и ∆₂ , между ними возможны следующие соотношения, т.е. если:

1. ∆₁ = ∆₂ , то 01 10;

2. ∆₁ > ∆₂ , то 01 00 10;

3. ∆₁ < ∆₂ , то 01 11 10.

Таким образом, наличие различных задержек приводит к тому, что при переходе из s_i в s_j автомат может оказаться в некотором промежуточным незапланированном состоянии, что может привести к неправильной работе автомата.

Это явление называется состязанием элементов памяти.

В примере (рис. 6.6) могут быть три варианта соотношений. Первый вариант нереален. Во втором и третьем варианте появляются промежуточные состояния 00 и 11, именно переходы через эти состояния называются состязанием элементов памяти.

Состязания могут быть критическими и не критическими. Если состязание приводит к переходу в незапланированное устойчивое состояние, то такое состязание называется критическим.

Если же состязание приводит к переходу в незапланированное неустойчивое состояние, а затем и к переходу в нужное устойчивое состояние, то такое состязание называется некритическим.

Пример возникновения состязаний в автомате, заданным графом (рис.6.3) и таблицей переходов (табл. 6.1).

Пусть состояния закодированы следующим образом (табл. 6.2) и тогда закодированная таблица переходов имеет вид (табл. 6.3):

Таблица 6.2

si	y1	y2
s1
s2
s3

Таблица 6.3:

z	x1x2 y1y2
		(00)	(00)
			(01)	(01)	(01)
					(11)

Пусть в автомате должен произойти переход по входному сигналу 10 из устойчивого состояния с кодом 00 в устойчивое состояние с кодом 11.

Если ∆₁ > ∆₂ , то 00 01 11.

Состязание критическое, так как из-за такого соотношения между задержками автомат оказывается в промежуточном состоянии 01, - которое для автомата является устойчивым и перехода в состояние 11 не произойдет и это приводит неправильной работе автомата.

Если ∆₁ < ∆₂ , то 00 10 11.

Состязание некритическое, так как из-за такого соотношения между задержками код в блоке памяти становится равный 10, а такой код для кодирования состояний автомата не используется и автомат далее перейдет в устойчивое состояние с кодом 11.

Так как неизвестно соотношение между задержками элементов памяти и невозможно определить тип состязания: критическое или некритическое, то надо вообще исключить состязания.