Как видно из рисунка, сигнал на входе х принимает значение «I» в тактах 2, 4, 6, 8, 10, а в остальных тактах-значение «О». После такта 10 вновь наступает такт 7, т. е. цикл состоит из десяти тактов. В момент появления на входе х значения «I» в пятый раз (такт 10} на выходе z возникает значение «I», сигнализирующее о том, что в счетчик поступило пять импульсов.

Пример 3.1. Необходимо составить таблицу включений для автомата с двумя входами Xi, хз и одним выходом z (рис. 3.7), условия работы которого состоят в следующем. Вначале появляется значение «I» сигнала на входе Xi, а затем на .входе х-г. (В дальнейшем для простоты будем говорить, что на входе или выходе появился сигнал.) В момент появления сигнала на входе х автомат вырабатывает значение «I» сигнала на выходе г, которое остается и после пропадания сигнала на входе Л до тех пор, пока не исчезнет сигнал на входе Xi.

Решение. Очевидно, в таблице включении должны быть две строки для входов a-i и х: и одна строка для выхода z. Первый такт является начальным. Поэтому в первой строке наличие сигнала на входе х\ будем указывать, начиная со второго такта (рис. 3.8,а). В третьем такте появляется сигнал на входе Xt, а сигнал на .входе х\ сохраняет свое единичное значение. При этом возникает сигнал на выходе z (рис. 3.8,6). В четвертом такте исчезает сигнал на входе Хг, а сигналы на входе Xi и выходе г сохраняют свое предыдущее значение (рис. 3.8,б). В следующий момеят времени (пятый такт) исчезает сигнал на входе xi, что приводит к исчезновению сигнала на выходе г (рис. 3.8,г). 1ак как после четвертого такта автомат приходит в исходное (начальное) состояние, то .вместо пятого такта целесообразно указывать первый такт (такт 1 на рис. 3.8,г указан в скобках). На этом процесс построения таблицы включений заканчивается. Таким образом, первоначальная таблица включений имеет четыре такта.

Пример 3.2. Необходимо задать условия работы автомата (см. рис. 3.7), который должен реализовать две последовательности «вход-выход». Пусть одна последовательность останется той же, что и в условиях примера 3.1, а вторая последовательность является следующей: первым появляется сигнал на входе х2, а затем на входе х1. При этом в момент наличия сигналов на входах Х1 и Х2 допустимо (но не обязательно) возникновение сигнала на выходе z.

* 1 г з ч- 5(1)

S)

х1

X?

z

Рис. 3.8

Решение. Для двух последовательностей необходимо иметь уже две первоначальных таблицы включений, одна из которых была составлена ранее (см. рис 38 е) Процесс составления второй таблицы включении ясен из рис. 3.9,а-г, где штриховой линией обозначено безразличное значение сигнала на выходе. Таким образом, в данном случае автомат задается двумя таблицами включении, приведенными на рис. 3.8,г и рис. 3.9,г.

1 Z J 4

1 Z J Ч 7

x1

Xz

z

a)

s)

г)

Рис. 3.9

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

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

состоянию входа автомата. Клетке таблицы переходов соответствует состояние автомата, определяющее внутреннее состояние, в которое автомат должен перейти в следующий момент времени. Если в автомате какое-либо состояние не определено, т. е. является неиспользуемым*, то в соответствующей клетке ставится черточка. Например, в табл. 3.1, задающей недоопределенный синхронный автомат, состояния (лЛ, (аз, (л4 являются неиспользуемыми. (Через лг будем обозначать состояние автомата, соответствующее внутреннему состоянию Хг и состоянию входа pj.)**

Таблица 3.1 Из табл. 3.1 видно, что автомат имеет два состояния входа (pi и рг) и четыре внутренних состояния (xi, кг, кз и К4). Если автомат находится во внутреннем состоянии •n.i, то при воздействии на него состояния входа pi он не изменит своего внутреннего состояния, а при воздействии состояния входа ра он перейдет во внутреннее состояние кг.

Неиспользуемые состояния в автомате обычно возникают из-за ограничения входных последовательностей. Например, в табл. 3.1 не могут быть два одинаковых состояния входа, следующих один за другим. Однако возможны и другие причины возникновения неиспользуемых состояний входа, например когда безразлично, в какое внутреннее состояние перейдет автомат.

* Иногда такое такое состояние называют запрещенным

** Здесь и в дальнейшем для простоты в клетках таблицы переходов вместо символа внутреннего состояния х, будем указывать только один его номер i.

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

В таблице переходов вместо состояний входа и выхода часто указывают значения кодирующих их переменных (значения отдельных входных и выходных сигналов).

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

Состояния входа синхронного автомата, указанные в таблице переходов, соответствуют тем моментам, в которые на входе автомата присутствует сигнал от тактового генератора. В таблице переходов с целью упрощения данный сигнал обычно не указывается и только предполагается (табл. 3.2), что имеется еще столбец N который соответствует нулевому значению этого сигнала. Напомним, что при нулевом значении синхронизирующего сигнала синхронный автомат не воспринимает состояния входа, поэтому они все равны нулю. Заметим, что в столбце N все выходные сигналы могут иметь любые значения, так как предполагается, что в синхронном автомате они появляются лишь в моменты присутствия на входе автомата синхронизирующего сигнала.

Рассмотрим теперь особенности таблицы переходов, задающей асинхронные автоматы различного вида. Каждая строка таблицы соответствует определенному внутреннему состоянию автомата, каждый столбец - определенному состоянию входа автомата. Клетка таблицы, определяемая состоянием входа и внутренним состоянием автомата, соответствует полному состоянию автомата. Устойчивое состояние автомата, т. е. состояние, соответствующее устойчивому такту, обозначается цифрой в круглых скобках, а неустойчивое состояние (соответствующее неустойчивому такту), предшествующее данному устойчивому состоянию, - той же цифрой без скобок. Переход автомата из одного внутреннего состояния в другое всегда связан с переходом его в неустойчивое состояние.

Если состояние входа рк вызывает переход автомата из внутреннего состояния к, во внутреннее состояние к„ то автомат перейдет сначала в неустойчивое состояние лг, соответствующее внутреннему состоянию и, и состоянию входа рк, и только после этого он может перейти в устойчивое состояние соответствующее внутреннему состоянию к, и тому же состоянию входа ря. В табл. 3.3 приведен пример таблицы переходов, задающей функции переходов и выходов асинхронного автомата. Если, напри мер, автомат находится в состоянии (2) и состояние входа его меняется с pa на рз, то он перейдет в состояние (4) и внутреннее состояние его при этом не изменится. Если автомат находится в том же состоянии (2), но состояние входа его меняется с ра на pi, то он вначале перейдет в неустойчивое состояние 1, а затем в устойчивое состояние (1), при этом внутреннее состояние его изменится с иг на Hi.

Таблица 3.2

Nр!р2

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

Таблицы переходов и выходов, задающие функции переходов и выходов асинхронного автомата, полностью определяют его функционирование.

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

Если состояние выхода автомата сопоставляется не с полным, а с внутренним состоянием, то таблица переходов будет такой, как указано в табл. 3.4.

Таблица 3.4

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

Пример 3.3. Условия работы автомата сформулированы в примере 3.1.

Решение. Поскольку имеются два входа (два входных сигнала): х\ я х-г, - таблица переходов, вообще говоря, должна содержать 22=4 столбца-по числу возможных состояний входа. Однако из условии работы следует, что из числа возможных состояний входа pi-00, рг-Ю, рз-11, р4-01) состояние р4-01, когда только на одном входе х<г имеется сигнал, недопустимо (это же видно из рис. 3.8,г). Поэтому для рассматриваемого примера таблица переходов имеет три столбца. Число строк заранее неизвестно.

Вначале вводим одно внутреннее состояние, в котором указываем начальное устойчивое полное состояние (1) автомата с указанием состояния 0 аа выходе г (табл 35) Далее из условий работы следует, что после состояния входа pi наступает состояние входа ра (появляется входной сигнал х,}. Поэтому вводим новое внутреннее состояние (яа), причем в столбце ра в строке и, (т е во внутреннем состоянии Xi) указываем неустойчивое состояние 2, а в строке Яа -устойчивое состояние (2) с указанием соответствующего значения выходного сигнала z (табл. 3.6).

Дальнейший процесс построения первоначальной таблицы переходов легко проследить по табл. 3.7-3.9, которые даются в упрощенном виде.

Таблица 39 является первоначальной таблицей переходов, описывающей заданные условия .работы автомата. В ней четыре строки, соответствуют четырем ВНУТрОННИМ СОСТОЯНИЯМ Я]-Х4.

Пример 3.4. Необходимо построить первоначальную таблицу переходов по условиям работы автомата, указанным в примере

3.2.

Решение Вначале таблицу переходов построим исходя только из одно» первой последовательности (т. е. получим табл. 3.9), атем добавим переходы, соответствующие второй последовательности. При этом таблица переходов будет иметь уже четыре столбца. Процесс дальнейшего построения первоначаль ной таблицы переходов для данного примера легко проследить из рассмотрения табл. 3.10-3.13.