-Поиск по дневнику

Поиск сообщений в zhurnalist

 -Подписка по e-mail

 

 -Статистика

Статистика LiveInternet.ru: показано количество хитов и посетителей
Создан: 26.11.2010
Записей:
Комментариев:
Написано: 18

Кодирование состояний асинхронного автомата

Дневник

Вторник, 04 Января 2011 г. 20:28 + в цитатник
Рассмотрим процесс перехода из состояния в состояние для асинхронного автомата, поведение которого представлено в табл. 22.1 с выделенными устойчивыми состояниями, где крайний правый столбец представляет произвольно выполненное кодирование состояний. Переход из одного состояния в другое в реальной схеме реализуется как смена набора состояний элементов памяти. Пусть сначала действует входной сигнал а1 и автомат находится в устойчивом состоянии q1 (код 000). Затем входной сигнал меняется на а3, и автомат согласно заданному поведению должен пойти в состояние q4 (код 011). В зависимости от того, какой из двух элементов памяти, z2 или z3, меняет свое состояние первым, автомат может оказаться на какое-то время в промежуточном состоянии, представленном набором состояний элементов памяти 010 либо 001. Если первым меняет свое состояние элемент z3, то автомат окажется в состоянии q2 (код 001), которое является устойчивым для входного сигнала а3, т. е. вместо того, чтобы идти в состояние q4, автомат остается в состоянии q2.

Таблица 22.1
Таблица переходов асинхронного автомата
а1 а2 а3 z1 z2 z3
q1 q1 q3 q4 0 0 0
q2 q1 q3 q2 0 0 1
q3 q1 q3 0 1 0
q4 q5 – q4 0 1 1
q5 q5 q3 q2 1 0 0

Рассмотренное явление носит название состязаний или гонок элементов памяти. Принято называть состязания неопасными, если все промежуточные состояния, в которых автомат может оказаться при переходе из одного состояния в другое под воздействием некоторого входного сигнала а, являются неустойчивыми для сигнала а, т. е. при любом порядке переключений элементов памяти автомат из некоторого состояния qi под воздействием входного сигнала а переходит всегда в состояние qj (a, qi). Если же при этом автомат может оказаться в некотором устойчивом состоянии qk, отличном от qj, то состязания называются опасными.

Метки:  

Автомат Мура и Мили. Описание

Дневник

Среда, 22 Декабря 2010 г. 21:16 + в цитатник
Если заменить внутреннюю переменную q на соответствующий булев вектор z (z1, z2, … , zk), то получится система уравнений, в которой все переменные и все функции оказываются булевыми:

z1+ = 1х1, х2, … , хп; z1, z2, … , zk;
z2+ = 2х1, х2, … , хп; z1, z2, … , zk;

zk+ = kх1, х2, … , хп; z1, z2, … , zk;
y1 = 1х1, х2, … , хп; z1, z2, … , zk;
y2 = 2х1, х2, … , хп; z1, z2, … , zk;

ym = mх1, х2, … , хп; z1, z2, … , zk.

Эта модель называется булевым автоматом. Ее также можно представить в компактной векторной форме:

z+ = х, z;
y = х, z.

Булев автомат в определенном смысле ближе к реальным дискретным устройствам, поскольку его переменные непосредственно реализуются физическими переменными устройства, в частности, на типичных для современной техники элементах с двумя устойчивыми состояниями. Векторы х, у и z показывают структуру абстрактных символов а и b и состояния q. Приведенная выше система функций соответствует структуре, изображенной на рис. 18.2, где КС – комбинационная схема, реализующая приведенную выше систему, а П – блок памяти, осуществляющий задержку на период между соседними моментами времени.
Переменная zi представляет состояние i-го двоичного элемента памяти, а выражение

zi+ = iх1, х2, … , хп; z1, z2, … , zk

Метки:  

Автоматы мили и мура

Дневник

Среда, 22 Декабря 2010 г. 20:57 + в цитатник
Автомат Мура представляется одной таблицей переходов, к которой добавлен один столбец со значениями функции выходов (табл. 18.4).

Можно свести таблицу переходов и таблицу выходов автомата Мили в одну таблицу, которую называют таблицей переходов и выходов. Такая таблица для автомата, заданного в виде табл. 18.2 и табл. 18.3, имеет вид табл. 18.5.

Более наглядным при небольшом числе состояний является представление автомата в виде графа поведения автомата, который представляет собой ориентированный граф. Его вершины соответствуют состояниям автомата, а дуги – переходам между состояниями. При этом дуга помечается всеми входными символами, которые вызывают соответствующий переход, и выходными символами, сопровождающими данный переход (в случае автомата Мили). В случае автомата Мура выходными символами помечаются вершины, соответствующие состояниям, в которых находится автомат при выдаче данных символов. На рис. 18.1 изображены графы переходов автоматов, заданных табл. 18.4 и 18.5.
Таблица 18.4 Таблица 18.5
Таблица переходов автомата Мура Таблица переходов и выходов
автомата Мили
a1 a2 a3 a4  a1 a2 a3 a4
q1 q1 q2 q1 q2 b1 q1 q1,b1 q2,b1 q1,b2 q2,b1
q2 q3 q1 q3 q1 b1 q2 q3,b1 q1,b2 q3,b2 q1,b1
q3 q3 q1 q1 q1 b2 q3 q3,b2 q1,b2 q1,b1 q1,b1


a1, a3 a1/b1, a3/b2

q1, b1
a2/b1, a4/b1 q1 a2/b2, a3/b1, a4/b1

a2, a4 a2, a3, a4
a2, a4 a2/b2, a4/b1 a1/b2
a1

q2, b1 a1, а3 q3, b2 q2 a1/b1, а3/b2 q3
а) б)
Рис. 18.1. Примеры графов поведения: а) автомата Мура; б) автомата Мили

Метки:  

Представление автомата

Дневник

Среда, 22 Декабря 2010 г. 20:56 + в цитатник
Конечный автомат удобно представлять таблицей переходов и таблицей выходов. Строкам этих таблиц соответствуют состояния автомата, столбцам – входные символы. На пересечении строки, соответствующей состоянию q, и столбца, соответствующего входному символу а, в таблице переходов записывается значение (a, q), а в таблице выходов – значение (a, q). Другими словами, в первом случае в клетке таблицы указывается состояние, в которое автомат переходит из состояния q при поступлении на его вход символа а, а во втором случае – выходной символ, который при этом выдает автомат. Табл.18.2 и табл.18.3 представляют собой пример описанного представления автомата Мили, у которого А = {a1, a2, a3, a4}, В = {b1, b2} и Q {q1, q2, q3}.
Таблица 18.2 Таблица 18.3
Функция Функция
a1 a2 a3 a4 a1 a2 a3 a4
q1 q1 q2 q1 q2 q1 b1 b1 b2 b1
q2 q3 q1 q3 q1 q2 b1 b2 b2 b1
q3 q3 q1 q1 q1 q3 b2 b2 b1 b1

Зная начальное состояние автомата и входную последовательность, нетрудно получить по этим таблицам соответствующую последовательность выходных символов. Приведем пример такого соответствия для автомата, заданного табл. 18.2 и 18.3, на вход которого поступила последовательность символов а1, а2, а2, а1, а3, а4, а1, а4 при начальном состоянии q1. Покажем также состояния, которые проходит автомат:

а1 а2 а2 а1 а3 а4 а1 а4
q1 q1 q2 q1 q1 q1 q2 q3
b1 b1 b2 b1 b2 b1 b1 b1.

Метки:  

Автомат с памятью

Дневник

Среда, 22 Декабря 2010 г. 20:55 + в цитатник
Таблица 18.1
Пример задания комбинационного автомата
Вход Выход
а1

а2


… …

а


Моделью описанного устройства является конечный автомат, представляющий собой совокупность следующих объектов:
А = {a1, a2, … , a} – множество входных символов, или входной алфавит;
В = {b1, b2, … , b} – множество выходных символов, или выходной алфавит;
Q  {q1, q2, … , q} – множество состояний, или внутренний алфавит;
 : A  Q  Q – функция переходов;
 : A  Q  В – функция выходов.

Для конечного автомата используется обозначение (A, B, Q,  ). Слово «конечный» подчеркивает, что все три множества, входящие в состав данной модели, конечны. В том виде, в каком эта модель здесь представлена, она носит название «автомат Мили». Другой разновидностью данной модели является автомат Мура, отличающийся от автомата Мили только тем, что функция выходов не зависит от входного символа, т. е. представляет собой отображение  : Q  В.

Значением функции (a, q) является состояние q+, в которое переходит автомат из состояния q, если на вход его подан символ а. Значением функции (a, q) является выходной символ, выдаваемый автоматом в состоянии q при поступлении на его вход символа а, а значением функции (q) автомата Мура – выходной символ b, который выдает автомат, находясь в состоянии q. Если значения функций (a, q) и (a, q) определены для любой пары значений аргументов а и q, а в модели Мура функция (q) определена для всех значений q, то автомат является полностью определенным, или полным автоматом. Иногда приходится иметь дело с не полностью определенным, или частичным автоматом, у которого эти функции могут быть определены не везде.

Метки:  

 Страницы: [1]