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

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

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

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

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

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

буквой Q;

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

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

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

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

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

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

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

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

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

Q (t+1) = D(t)

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

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

Рис. 3.29.

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

Т-триггера представлено на рис. 3.31, функция перехода определилась по таблице переходов как

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

а) б)

Рис. 3.32.

Перейдем теперь к рассмотрению триггеров с двумя входами. Принято обозначать один из входов через 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.

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

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

Рис. 3.34. Табличное представление матрицы переходов

Табличная форма матрицы перехода R - S - триггера показана на рис. 3,д. Для переходов 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₁₁ должно оставаться равным единице, имеем

В 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₁₁ .

Q(t)→Q(t+1)	Rтр	Eтр
R(t)	S(t)	R(t)	S(t)
0→0		b1		b1
0→1
1→0		b2
1→1		b3	b2

Рис. 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. J-K — триггер:

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

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

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

В теории автоматов часто рассматривают трёхвходовый триггер R-S-Т - типа. Однако в связи с разработкой и внедрением J-K - триггеров применение R-S-Т - триггера в реальных схемах практически сведено к нулю.