Сучкова Л.И. Абстрактный и структурный синтез автоматов

Подождите немного. Документ загружается.

дом t ингибиторной дугой (ее кратность всегда равна 1), име-

ет нулевую разметку.

В приоритетных сетях вводят приоритеты срабатыва-

ния переходов. Если несколько переходов являются разре-

шенными, то срабатывает тот из них, который имеет наи-

высший приоритет. Такие сети используются для моделиро-

вания систем на уровне задач.

В структурированных сетях некоторые из переходов

являются сложными. При их срабатывании запускается сеть

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

делирования модульных вычислительных систем.

В цветных сетях вводится понятие цвета для фишек. В

общем случае может быть n цветов. В вычислительной тех-

нике используются трехцветные сети (n = 3). Такие сети ис-

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

В сетях

с изменяемой структурой кратность ребер не

является постоянной. В самомодифицируемых сетях крат-

ность ребра может задаваться либо натуральным числом N,

либо определяться количеством фишек, находящихся во

входных позициях некоторого перехода.

Качественными характеристиками могут быть: отсутст-

вие зацикливаний в системе, достижение некоторого состоя-

ния системы (например, конечного). Количественными ха-

рактеристиками являются: время работы

некоторого маршру-

та в программе, время прохождения сигнала в схеме и т. д.

Во временных сетях переходам ставятся в соответствие

их времена срабатывания, либо позициям ставится в соответ-

ствие времена нахождения фишек в позициях. В стохасти-

ческих сетях указанные характеристики являются вероятно-

стными, т. е. вводится функция плотности вероятности вре-

мен срабатывания переходов или времен нахождения фишек

в позициях.

5 СТРУКТУРНЫЙ СИНТЕЗ АВТОМАТОВ

5.1 Понятие структурного синтеза. Теорема о струк-

турной полноте

Процесс построения схемы автомата обычно разделяют

на две стадии: абстрактный и структурный синтез. На стадии

абстрактного синтеза выполняется построение таблиц пере-

ходов и выходов автомата. На стадии структурного синтеза

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

есть строится структурный

автомат из более простых автома-

тов, называемых элементарными автоматами.

Элементарные автоматы бывают двух видов – автома-

ты с памятью, имеющие более одного состояния, и авто-

маты без памяти с одним состоянием. Автоматы с памятью

называются элементами памяти (запоминающими элемента-

ми), автоматы без памяти – комбинационными или логиче-

скими элементами. Элементы памяти соединяются

между

собой с помощью логических элементов, например, элемен-

тов «И», «ИЛИ».

При структурном синтезе автомата необходимо выбрать

систему элементов, из которых строится автомат. Для того,

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

мата, эта система элементов должна быть структурно полной.

Сформулируем теорему о структурной полноте.

Система элементарных автоматов, содержащая

функционально

полную систему логических элементов,

хотя бы 1 автомат Мура с памятью, обладающая полной

системой переходов и полной системой выходов, является

структурно полной.

Полнота переходов в автомате означает, что для любой

пары состояний a

и a

существует хотя бы один входной сиг-

нал, который переводит автомат из состояния a

в состояние

. В автомате, обладающем полной системой переходов, в

каждом столбце таблицы переходов должны встречаться все

состояния.

Полнота выходов автомата означает, что в каждом со-

стоянии автомат выдает выходной сигнал, отличный от сиг-

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

ты системы выходов связано с необходимостью различать

внутренние состояния элементарных автоматов, т.к. в авто-

мате, не обладающем полной системой выходов, различить

состояния невозможно и, следовательно, невозможно обес

печить заданные условия функционирования схемы, постро-

енной на его основе. Автомат Мура удовлетворяет требова-

ниям к полноте системы переходов и выходов.

Цель структурного синтеза автомата – построение циф-

ровой схемы автомата на основе системы логических уравне-

ний (называются каноническими уравнениями), в которых

записываются зависимости выходных сигналов автомата и

сигналов, подаваемых на

входы запоминающих элементов, от

входных сигналов автомата и сигналов с выходов элементов

памяти.

5.2 Типы элементарных автоматов памяти

Рассмотрим конкретные типы элементарных автоматов,

имеющих полную систему переходов и выходов и нашедших

применение в вычислительной технике.

В настоящее время в вычислительной технике, как пра-

вило, используются элементарные автоматы, имеющие сле-

дующие

особенности:

1. Элементарные автоматы являются автоматами Мура с

двумя внутренними состояниями;

2. Автомат выдает два различных выходных сигнала,

соответствующих двум его внутренним состояниям. В даль-

нейшем состояния автомата и его выходные сигналы будем

обозначать одной буквой Q и кодировать цифрами 0 и 1;

3. Элементарные автоматы могут иметь в общем случае

несколько физических входов

, на каждый из которых могут

подаваться сигналы, закодированные цифрами 0 и 1 (рисунок

5.1).

В качестве элементарных автоматов в вычислительной

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

Определение. Триггер – это устройство, имеющее два

устойчивых состояния, в которые он переходит под действи-

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

Рисунок 5.1 – Пример элементарного автомата

В триггерах выделяют два вида входных сигналов: ин-

формационные и синхросигналы. Информационные сигналы

определяют новое состояние

триггера и присутствуют в лю-

бых триггерах. По типу информационных сигналов осущест-

вляется классификация триггеров: D, T, RS, JK, RST, DV и

т.д.

Синхросигнал С не является обязательным и вводится в

триггерах с целью фиксации момента перехода триггера в

новое состояние. На синхровход триггера поступают такти-

рующие импульсы задающего генератора, синхронизирую-

щего работу цифрового

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

пульсов соответствует одному такту автоматного времени.

Рассмотрим основные типы триггеров, используемые

для структурного синтеза: D, T, RS, JK.

1. Т-триггер.

Т-триггером называют автомат Мура с двумя устойчи-

выми состояниями и одним входом Т, который изменяет свое

состояние на противоположное всякий раз, когда на вход Т

поступает входной сигнал

. T-триггер называется триггером

со счетным входом.

Условное обозначение и таблица переходов T-триггера

имеют вид:

T Q

0 0 0

0 1 1

1 0 1

1 1 0

Если сигнала на входе нет (T=0), то состояние, которое

было, то и осталось. При поступлении сигнала (T=1) состоя-

ние меняется.

На практике более удобно вместо таблиц переходов

пользоваться так называемыми матрицами переходов или

таблицами функций входов элементарных автоматов. Мат-

рица переходов определяет значения сигналов на входах эле-

ментарного автомата, обеспечивающие каждый из

четырех

возможных переходов. Здесь Q(t) и Q(t+1) – состояния авто-

мата в моменты времени t и t+1 соответственно. Поскольку

Т-триггер имеет один вход, а число возможных переходов

равно четырем, то матрица переходов имеет четыре строки.

Таблица функций входов триггера T

= f(Q

, Q

t+1

) име-

ет вид:

0 0 0

0 1 1

1 0 1

1 1 0

Закон изменения состояния Т-триггера в зависимости

от времени: Q(t+1)=T(t)⊕Q(t)

На практике кроме асинхронного Т-триггера, рассмот-

ренного нами, используют синхронный Т-триггер, который

меняет свои состояния только при Т = 1 и С = 1. Если хотя бы

один из этих сигналов равен нулю, то триггер сохраняет свое

состояние.

2. D-триггер (триггер задержки)

Триггером D-типа (триггером задержки) называют эле-

ментарный автомат Мура с двумя устойчивыми состояниями

и одним входом D таким, что Q(t+1) = D(t). Название D-

триггера происходит от слова “delay” – задержка. Из опреде-

ления следует, что состояние триггера в момент времени t+1

повторяет значение входного сигнала D(t) в момент времени t

(отсюда и название триггера задержки).

Таблица переходов D-триггера

имеет вид:

D Q

0 0 0

0 1 0

1 0 1

1 1 1

Из приведенной таблицы переходов для данного

триггера Q

t+1

= f(Q

) можно получить таблицу функций

его входов D

= ϕ(Q

, Q

t+1

0 0 0

0 1 1

1 0 0

1 1 1

3. R-S – триггер с разделенными входами

R-S триггером называют автомат Мура с двумя устойчи-

выми состояниями, имеющий два входа R и S такие, что при

S=1 и R=0 триггер принимает состояния 1, а при R=1 и S=0

состояние 0. В соответствии с состоянием, принимаемым

триггером, вход S называется единичным входом, а вход R

нулевым. Комбинация сигналов R=1 и S=1 является запре-

щенной и поэтому переход в триггере при таких значениях

входных сигналов не определен. Таблицы переходов RS-

триггера имеют вид:

R S Q

t+1

а)

R S Q

б)

Таблица функций входов RS-триггера представлена ни-

же:

t+1

0 0 X 0

0 1 0 1

1 0 1 0

1 1 0 X

Переход триггера из 0 в 0 возможен при двух комбина-

циях входных сигналов: R=0 и S=0, R=1 и S=0. При этом со-

стояние R является безразличным. Поэтому в первой строке

матрицы переходов R-S триггера в столбце R поставлена пе-

ременная Х, которая может принимать два значения 0 или 1.

Аналогично, переход из состояния 1 в 1 также возможен при

двух комбинациях входных сигналов: R=0, S=0

и R=0, S=1.

Поскольку при таком переходе значения сигнала на входе S

безразлично, то в нижней строке матрицы переходов в

столбце S записана переменная Х:

Q(t) Q(t+1)

Х 0 0 0

0 1 0 1

1 0 1 0

0 Х 1 1

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

ния в другое под действием нескольких комбинаций входных

сигналов, называются автоматами с избыточной системой

переходов. Избыточность можно использовать в процессе

для упрощения схемы, придавая переменной X такие значе-

ния, которые позволяют минимизировать число элементов.

Поэтому, если схемы двух элементарных автоматов равно-

ценны по сложности,

то предпочтение отдают автомату,

имеющему большую избыточность системы переходов.

Закон функционирования R-S триггера в аналитическом

виде: Q (t+1) = S v R*Q (t), при R*S = 0

4. J-K триггер (универсальный триггер)

Триггером J-K типа называют автомат Мура с дву-

мя устойчивыми состояниями и двумя входами J и K,

который при условии J*K = 1 осуществляет инверсию

предыдущего состояния (т.е. при J*K = 1, Q(t+1) =

Q(t)), а в остальных случаях функционируют в соответ-

ствии с таблицей истинности R-S триггера, при этом

вход J эквивалентен входу S (установка в 1), а вход K -

входу R (установка в 0). Этот триггер уже не имеет за-

прещенной комбинации входных сигналов и его табли-

ца истинности, т.е. зависимость Q(t+1) = f [J, K, Q(t)]

имеет вид:

J K Q(t) Q(t+1)

0 0 0 0

0 0 1 1

0 1 0 0

0 1 1 0

1 0 0 1

1 0 1 1

1 1 0 1

1 1 1 0

Триггер J-K типа относится к разряду универсальных

триггеров, поскольку на его основе можно построить RS-, D-

и T- триггера. Например, R-S триггер получается из триггера

J-K типа наложением ограничения на комбинацию входных

сигналов J = K = 1, т.к. эта комбинация является запрещен-

ной для R-S триггера. Счетный триггер на основе J-K тригге-

ра получается путем объединения входов J и K. D- триггер

строится путем

подключения к входу K инвертора, на кото-

рый подается тот же сигнал, что и на вход J. В этом случае

вход J выполняет функцию входа D, а все устройство в це-

лом реализует таблицу переходов D-триггера. В интеграль-

ной схемотехнике применяются только тактируемые (син-

хронные) J-K триггера, которые при C = 0 сохраняют свое

состояние, а при C= 1 работают

как асинхронные J-K тригге-

ра.

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

На стадии абстрактного синтеза обычно пользуются

представлением автомата в виде одного блока, имеющего

один вход и один выход. На стадии структурного синтеза ав-

томат изображают в виде обобщенной структурной схемы, в

ней есть L входных и N выходных каналов, по которым пере-

даются двоичные сигналы x

, x

, ..., x

и y

, y

, ..., y

. Пере-

менные x

, x

, ..., x

называют входными переменными, а y

, ..., y

- выходными переменными или функциями выходов

автомата (рисунок 5.2).

Рисунок 5.2 - Обобщенная структурная схема автома-

та

Рассматриваемая схема состоит из двух частей: комби-

национной схемы (КС) и набора элементов памяти (ЭП). Пе-

ременные Q

, Q

, ..., Q

, соответствующие выходным сигна-

лам элементов памяти, называют внутренними переменными