Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Канонический метод структурного синтеза автоматов

Читайте также:
  1. I. 2.3. Табличный симплекс-метод.
  2. I. 3.2. Двойственный симплекс-метод.
  3. I. Передача параметров запроса методом GET.
  4. II. Методика работы
  5. II. Методика работы.
  6. II. Методика работы.
  7. II. Методика работы.

 

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

На рис. 36, а и б, приведены обобщённые структурные схемы автоматов на D- и Т- триггерах, где КС – комбинационная схема.

Для обеспечения устойчивой работы автомата при практической реализации необходимо предусмотреть, например, удвоение элементов памяти. (рис. 37).

       
   


а) б)

 

Рис.36

 

 

 


Рис.37

Синтез состоит из двух этапов:

- Кодирование состояний, входных символов автомата;

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

Пример. Выполним структурный синтез автомата Мили

 

Продавец. Этот автомат имеет входной алфавит V=[v1,v2], выходной алфавит W=[w1, w2, w3, w4], алфавит состояний S=[s0, s1, s2] и характеризуется таблицей переходов (табл.1) и таблицей выходов (табл.2)

Для кодирования входных и выходных алфавитов и состояний автомата необходимо [log2|V|]=1, [log2|W|]=2, [log2|S|]=2 разрядов соответственно.

Обозначаем структурное представление входа автомата символом x, выходов y1 и y2, состояний символами q1 и q2.

Тогда можно предложить кодирование V, W и S, представленное в табл. 30, а, б и а.

Таблица 30.

 

а) б) в)


Y X
y1 y2  

 

 

W y1 y2
w1 w2 w3 w4 0 0 0 1 1 0 1 1

 

 

S q1 q2
s0 s1 s2 0 0 0 1 1 1

Используя эти коды построим таблицы переходов и выходов автомата (Табл. 31, а, б)

Табл. 31

а) б)


X q1 q2
00 01 11
  01 11 00 11 00 00

 

 

S q1 q2
00 01 11
  00 01 10 01 10 10

Общую закодированную таблицу выходов (табл. 31 б) можно расщепить на отдельные таблицы для каждого выходного символа структурного автомата, т.е. для у1 и у2 отдельно (табл. 32 и табл. 33)

 

 

Табл. 32 Табл. 33

 


X q1 q2
00 01 11 10
0 0 0 1 - 0 1 1 -

 

 

X q1 q2
00 01 11 10
0 0 1 0 - 1 0 1 -

Рассматривая эти таблицы как карты Карно-Вейча, получим

минимизированные выражения для у1 и у2:

y1=q1\ /x&q2;

_ __ __

y2=x&q1&q2 \ / x&q2 \ / x&q1

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

Для D-триггеров u_1(t) = q_1(t), т.е. таблица возбуждения совпадает с закодированной таблицей переходов автомата.

Для Т-триггеров u_1(t) = q_1(t) Å q_1(t+1), т.е. значение сигнала возбуждения получается суммированием по mod2 текущего состояния триггера и его требуемого нового состояния.

В нашем примере таблица возбуждения для Т-триггеров имеет вид Табл. 34.

Табл. 34

X q1 q2
00 01 11
  01 10 11 11 01 11

 

Расщепим общую таблицу возбуждения на отдельные таблицы для каждой составляющей. (табл. 35 и 36)

 

 


X q1 q2
00 01 11 10
0 0 1 1 - 1 0 1 -

 

 

X q1 q2
00 01 11 10
0 1 0 1 - 1 1 1 -

 

 


Рассматривая эти таблицы как карты Карно-Вейча для частичных функций, получим минимизированные значения функций возбуждения q1 и q2:

_ __

q1=x&q2 \ /x&q2\ / q1;

__

q2=q2 \ / q1 \ /x

 

 

7.2 Асинхронные автоматы

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

Синхронный автомат может изменять своё состояние только в определённые моменты времени, а именно в моменты поступления синхронизирующих импульсов.

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

Входные сигналы асинхронного автомата обладают следующими свойствами (рис.38):

-сигнал присутствует на входе автомата в каждый момент времени;

-длительность входного сигнала не ограничена и превышает некоторую минимальную величину.

- изменения входного сигнала могут происходить в произвольные моменты времени.

 

V(t)

11

 

01

t

 

Функционирование асинхронного автомата можно представить моделью Мура:

S(t+Ti ) = l[S(t), V(t)],

W(t) = m [S(t)],

Где S(t) – состояние автомата;

V(t) – входной символ автомата;

W(t) – выходной символ автомата;

t – непрерывное время;

Ti - время задержки выходного символа по отношению к моменту

изменения входного символа.

Пусть S(t+Ti) = l[S(t), V(1)]=S(1)=Si при некотором V(1)=V. В этом случае состояние Si называется устойчивым при входном сигнале V (рис.39 а)

 

а) б)

V

Si V Si Sj

 

Рис. 39

В противном случае, если S(t+Ti) = l [S(t), V(t)]=Sj, S(t)=Si

Причём Sj =Si при некоторой V(t)=V, состояние называется неустойчивым при входном сигнале V (рис 39 б)

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

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

Поэтому неустойчивые состояния называются транзитными.

На рисунке 40 показан граф иллюстрирующий появление транзитных состояний.

 

 

V1 V1

V Si Sj Sk V1

 

Рис. 40

Вначале автомат находится в устойчивом состоянии Si Под действием входного символа V. При замене входного символа V на V1 переходит в состояние Sk , устойчивое при действии V1.

В асинхронных автоматах возможно явление, называемое генерацией (рис. 41)

 

V1 V1

V Si Sj Sk

 

V1

Рис. 41

Под действием замены входного сигнала V на V1 автомат покидает устойчивое состояние и попадает в замкнутую цепочку (цикл) транзитных состояний Si Sj Sk Вывести автомат из режима генерации можно только путём изменения входного символа.

 


Дата добавления: 2015-10-23; просмотров: 193 | Нарушение авторских прав


Читайте в этой же книге: Способы описания конечных автоматов | Минимизация числа состояний абстрактного автомата | Тестирование абстрактных автоматов | Язык Граф-Схем Алгоритмов | ФОРМАЛЬНЫЕ ГРАММАТИКИ И ЯЗЫКИ | ПРЕДСТАВЛение СИМВОЛЬНОЙ ИНФОРМАЦИИ | Машинное изображение чисел | Выполнение арифметических и логических операций | Микропрограммирование | Элементная база построения комбинационных автоматов |
<== предыдущая страница | следующая страница ==>
Переключательные функции (логика высказываний)| Моделирование дискретных асинхронных процессов и сети Петри

mybiblioteka.su - 2015-2024 год. (0.013 сек.)