Элементарные автоматы и их свойства.

Определение функций внешних переходов.

Пример 3.3

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

Исходными данными для построения кодированной таблицы переходов и выходов являются:

1) Таблицы переходов и выходов абстрактного автомата.

2) Таблицы кодирования символов алфавита абстрактного автомата.

Таблица кодирования получается путём подстановки двоичных кодов символов в таблицу переходов и выходов абстрактного автомата.

Для описанных выше автоматов S₁ и S₂ кодированные таблицы переходов и выходов изображены на рис.3.23,3.24. Они получаются путём кодирования таблиц на рис. 3.8 и 3.9. с использованием таблиц на рис. 3.20.,3.21. и 3.22.

Таблицы задают переходы элементарных автоматов. По кодированной таблице переходов находят функции внешних переходов элементарных автоматов, а по кодированной таблице выходов - функции выходов.

Функции внешних переходов определяется в следующей последовательности.

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

2) Размножаем (распараллеливаем) таблицу переходов по числу элементарных автоматов и таблицу переходов для каждого автомата представляется в виде диаграммы Карно.

3) По диаграмме Карно определяем функции внешних переходов.

Определяем функции внешних переходов для автоматов S₁ и S₂. Преобразуем кодированные таблицы переходов и выходов на рис. 3.23. и 3.24. автоматов S₁ и S₂ переставив местами два последних столбца. Доопределение запрещённых состояний выполняются таким образом, чтобы в столбце запрещённых состояний получилось хотя бы одно разрешённое состояние.

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

Полнота переходов элементарного автомата определяется наличием хотя бы одного входного сигнала, который переводит автомат из одного состояния в другое. Для любой пары переходов 0®0, 0®1, 1®0, 1®1 найдется входной сигнал, переводящий первый элемент пары во второй. Полнота выходов элементарного автомата означает, что его внутренние состояния должны быть различимы и проявлять себя в выходных сигналах. Другими словами, в элементарном автомате двум разным внутренним состояниям всегда соответствует два разных выхода из сигнала. Это означает, что формирование выходного сигнала осуществляется по внутреннему состоянию, т.е. элементарный автомат является автоматом Мура.

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

а) внутреннее состояние триггера обозначается буквой Q; при Q=1 мы будем говорить о «единичном состоянии триггера», при Q=0 – о «нулевом состоянии триггера»;

б) выходной сигнал триггера повторяет его внутреннее состояние и поэтому обозначается той же буквой Q;

в) триггер имеет парафазный выход, формирующий сигналы Q и ;

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

д) сигнальные входы триггера принято делить на установочные и рабочие. Сигналы на установочных входах переводят триггер с состояние «0» или «1» вне зависимости от его предыдущего состояния. Установочные сигналы подаются помимо комбинационной схемы формирования функций возбуждения, и служат для установки триггера в исходное состоя­ние (нулевое или единичное). Принято установочные сигналы обозначать через R_d (установка в «0») и S_d (установка в «1»).

Под воздействием сигналов на рабочих входах переход в следующее состояние определяется текущим состоянием и входным сигналом. Рабочие сигналы формируются комбинационной схемой формирования функций возбужденияи изменяют состоя­ние триггера в процессе формирования выходного сигнала ав­томата; они обозначаются буквами D, T, R, S, J, K в зависимости от типа триггера. Рабочие сигналы, как правило, тактируются. Входы могут быть статическими и динамическими. В случае статических входов состояний триггера изменение состояния триггера осуществляется по уровню сигнала. Установочные входы являются статическими. В случае динамических входов состояние изменяется по изменению сигнала (по фронту или срезу).

Приняты следующие обозначения для динамических входов.

е) классификацию триггеров осуществляют во числу рабочих сигналов.

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

Рассмотрение триггеров мы начнем с их простейших модификаций - триггеров с одним входом. Таких триггеров два: D - триггер и Т-триггер.

D - триггер (от английского delay — задержка) формирует выходной сигнал, логически совпадающий с входным сиг­налом, но задержанный относительно последнего на один период синхроимпульсов. На рис. 3.30 представлено графическое изображение триггера (а) и отображена его работа в виде таблицы переходов (б), графа (в) и матрицы переходов (г). При построении учитывалось свойство D-триггера: последующее состояние триггера Q(t+1) всегда совпадает со значе­нием его входного сигнала D(t). Для определения аналитического выражения функции перехода можно воспользоваться таблицей перехода, представив в виде диаграммы Карно.

Q (t+1) = D(t)

При рациональном кодировании матричной таблицы переходов ее можно интерпретировать как диаграмму Карно и использовать для минимизации функции перехода. Нетрудно видеть, что для нашего случая можно получить минимальную форму искомой функции в виде Q(t+1) = D(t).

Микросхемы D – триггеров входят в состав всех существующих серий интегральных цифровых схем. На рис. 3.29. изображён один из двух триггеров микросхемы К155ТМ2:

Другим одновходовым триггером является Т-триггер (от английского toggle – переключение, переходить между двумя состояниями), в Т-триггере входной сигнал, равный единице, изменяет его предыдущее состояние на противоположное, а нулевое значение входного сигнала сохраняет его предыдущее состояние. Описание Т -триггера представлено на рис. 3.31, функция перехода определилась по таблице переходов как

Отдельно микросхем счётных триггеров не существует, но их можно реализовать на других триггерах. На рис. 3.32. приведены схемы асинхронного и синхронного счётного устройства на D -триггерах: а-асинхронный T-триггер , б-синхронный Т- триггер.

Перейдем теперь к рассмотрению триггеров с двумя входами. Принято обозначать один из входов через S (от английского set - установка) и называть его S - входом или входом установки в «1», а другой - через R (от английского reset - возврат) и называть его R -входом или входом установки в «0».

Общим свойством всех двухвходовых триггеров является их реакция на раздельное единичное воздействие их входных сигналов R и S . Так, при R=1 и S=0 триггер вне зависимости от его предыдущего состояния всегда переводится в нулевое состояние, а при S = 1, R = 0 - в единичное состояние. Условие R = 0, S = 0 соответствует отсутствию каких-либо переключающих сигналов, поэтому триггер сохраняет свое предыдущее состояние. Таким образом, двухвходовые триггеры могут различаться своей реакцией на одновременное единич­ное воздействие их входных сигналов, когда R = 1 и S = 1. Это их свойство и положено в основу классификации двухвходовых триггеров. Мы рассмотрим пять модификаций таких триггеров — триггеры R-S, r, s, e и J -K типа.

В R-S-триггере комбинация входных сигналов R.=1, S=1 считается недопустимой, или запрещённой и переход при такой комбинации не определен. Поэтому R-S - триггер должен рассмат­риваться как частичный ав­томат, функции перехода ко­торого выражаются не пол­ностью определенными логи­ческими функциями.

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

Q(t+1) = (S+Q )_t , RS=0;

Q(t+1) = (t) (S(t)+Q(t)), RS=0.

Матрица переходов (рис.3.33(г)) построена по принципам, изложенным в разделе, описывающем матричное представление абстрактного автомата, однако такое представление не совсем удобно, поскольку оно не определяет значения двоичных входных сигна­лов R и S индивидуально. Поэтому перейдем к табличному представлению матрицы, где каждая строка соответствует од­ному из переходов, а столбцы - значениям двоичных входных сигналов на переходах. В общем виде для двухвходового триггера такая матрица - таблица принимает вид рис.3.34.

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

Табличная форма матрицы перехода R - S - триггера показана на рис.3.33,д. Для переходов 0→0 и 1→1 значения входных сигналов однозначно определены, в то время как для переходов 0→0 и 1→1 появляются неопределенные коэффици­енты. Действительно, сохранение нулевого состояния триггера происходит при любом значении сигнала установки в «0» (R-сигнале), а сохранение единичного состояния - при любом значении сигнала установки в «1» ( S - сигнале).

Для упрощения процедуры определения входных сигналов на переходе d→β можно рекомендовать построение некоторой логической функции X_αβ, единичное значение которой вызывает этот переход. Для триггеров с одним входом эта функ­ция вырождается в переменное, если переход происходит при его единичном значении, и в отрицание переменного - при ну­левом.

Для триггеров с двумя входами функция X_αβ дизъюнктив­но связывает все наборы входных переменных, вызывающих переход α→β

К примеру, для перехода 0→0 имеем X₀₀ = + R = , откуда видно, что переход осуществляется при S = 0 и от переменной R не зависит (R = l₁).

В S - триггере комбинация R = 1; S = 1 переводит триггep в единичное состояние. Отсюда и его название - сигнал установки в единицу (S - сигнал) всегда подавляет сигнал установки в ноль (R - сигнал).

Описание S -триггера приведено на рис. 3.35. Поскольку ГОСТ не предусматривает специального обозначения для триг­геров S-, R- и E - типа, мы будем пользоваться графическим изображением R-S - триггера с соответствующей буквой над ним. Из таблицы переходов получаем

Q(t+1) = (S + Q )_t = ((S + )(S+Q))_t

В отличие от предыдущего случая дизъюнктивная и конъ­юнктивная формы Q(t+1) эквивалентны, поскольку они отображают функцию перехода полностью определенного эле­ментарного автомата.

Для построения матрицы перехода определим значения вспомогательной функции:

переход 0→0; X₀₀ = + R =, откуда S=0; R= b₁; переход 0→1; X₀₁ = + R =, откуда S=1;

R. = b₂; переход 1→1; X₁₁ = + +R S= +S.

Полученное выражение для X₁₁говорит о том, что и R и S могут быть выра­жены неопределенными, но обязательно зависимыми друг от друга коэффициен­тами. Так, сигнал S может принимать произвольное значение при R=0, а сигнал R – при S=1. Поскольку на переходе 1→1 значение X₁₁ должно оставаться равным единице, имеем

X₁₁ = = º1

В R -триггере сигнал R подавляет сигнал S, поэтому комбинация R=1, S=1 переводит триггер в нулевое состоя­ние. Анализ этого типа триггера во многом напоминает ана­лиз S - триггера, поэтому мы его опускаем и приводим функцию перехода сразу в ее аналитической форме:

Q(t+1) = (t) (S(t)+Q(t)).

ВЕ -триггере (от английского equal- равный) комбинация R=1, S=1 сохраняет предыдущее состояние триггера, сигналы R и S эквивалент­ны по силе друг другу и их действие компенсируется, функция перехода

Е - триггера принимает вид

Q(t+1) =( S+Q +QS)_t .

Матрицы переходов R- и Е- триггеров приведены на рис. 3.36., значения неопределенных коэффициентов определены из выражения для X₁₁ .

Рис. 3.36. Матрицы переходов R- и E- триггеров.

В J-К -триггере комбинация R=1, S=1 изменяет его состояние на противоположное. Свое название триггер J-K – типа получил от имени изобретателя счетного триггера Jordan (1919 г.) (нелишне заметить, что идея построения триггера на год раньше была предложена М.А. Бонч-Бруевичем).

Триггер J-K - типа называют еще универсальным тригге­ром, поскольку он совмещает в себе свойства R-S- и Т-триггеров. Учитывая особое положение J-К -триггера среди дру­гих триггеров, принято его R вход обозначать буквой К , а S — буквой J . Соответственно изменяется маркировка входных сигналов. J-K - триггер обладает замечательным свой­ством: все неопределенные коэффициенты его матрицы переходов независимы. Это, как правило, обеспечивает дополнительные резервы минимизации функций возбуждения и приво­дит к наипростейшим схемным реализациям.

Графическое изображение триггера и его задание пред­ставлено на рис. 3.37. По таблице переходов получаем:

Q(t+1)=(Q + J)_t

а- условное обозначение; б- таблица пере­ходов, в—граф переходов; г- матрица пере­ходов.