м

Рис. 4.2. Таблица переходов с однократным изменением выхода (а) (слева); таблица переходов нормального режима (б) (справа).

совершается непосредственно в состояние 3. Изменения на выходе к 01 происходят сразу, как только происходят изменения на выходе. Единственное внешнее различие между этими двумя таблицами заключается в длительности некоторых входных сигналов. Таблицы переходов М и М' можно рассматривать как эквивалентные, если длительность выходных сигналов не является существенной, поскольку они приводят к одной и той же последовательности значений выходных сигналов для всех входных последовательностей.

Таблица ОИВ, в которой каждый переход непосредственно приводит к устойчивому состоянию (как в М' на рис. 4.2,6), называется таблицей переходов нормального режима. Если длительность выходных сигналов не представляет интереса, то любая таблица переходов ОИВ может быть преобразована в таблицу переходов нормального режима.

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

ком-либо изменении входа. Такие таблицы называют таблицами переходов с однократным измерением выхода (ОИВ). На рис. 4.2 показаны две таблицы ОИВ, которые отличаются друг от друга только одним входом (помеченным звездочкой).

В таблице переходов fA изменение входа О-\ при начальном состоянии цепи 1 вызывает переход к состоянию 2, а затем к состоянию 3. Когда автомат достигает состояния 2, изменение выходов происходит от 00 до 01. В таблице переходов М' переход от состояния 1, называемый изменением входа О->-1,

Рис. 4.3. Таблица переходов с многократным изменением выхода {а) (слева); таблица переходов неосновного режима (б) (справа).

достигнет устойчивого состояния, а будет зацикливаться между состояниями 2, 3 и 4. Количество получаемых изменений на выходе и достигаемое конечное состояние будут зависеть от длительности входного сигнала /3. В отличие от таблицы МИВ для Ml в этом случае невозможно получить основной режим функционирования. Таблицы переходов, аналогичные Мг (рис. 4.3), где невозможен основной режим функционирования, называются таблицами переходов неосновного режима. Они характеризуются наличием циклов состояний в одном или большем числе столбцов. Все таблицы нормального режима являются основными, но не все таблицы основного режима являются нормальными. Таблицы ОИВ могут быть нормальными и ненормальными, основного режима и неосновного режима. При неосновном режиме таблицы ОИВ выходы, связанные со всеми полными состояниями, через которые они могут зацикливаться, должны быть теми же самыми.

В таблице переходов М изменение на входе I->-0, когда автомат в состоянии 1 является устойчивым, будет приводить к выходной последовательности 11-10-00-01. Аналогичным образом, когда автомат находится в устойчивом состоянии 3, переход на входе О-1 будет приводить к выходной последовательности 01->-10-11. Автомат, представленный таблицей переходов Мг, будет иметь единственное изменение на выходе при изменениях на входе от /о до h. Однако если используется вход /з при условии, что автомат является устойчивым в полном состоянии (2, II) или (4, /i), то автомат не

Рис. 4.4. Таблица переходов импульсного режима работы

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

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

Если ширина входного импульса не ограничивается тем, что цепь может изменить состояние только один раз в течение каждого входного импульса, то цепь может быть проанализирована с использованием методов, применяемых к цепям с потенциальными входами. На рис. 4.4. показана таблица переходов для той же цепи, что и на рис. 4.1, но при наличии импульсных входов. Столбцы, соответствующие четырем столбцам рис. 4.1, помечены через II - /4, и дополнительно введен столбец Iq. Каждый столбец Ij при / =7 О, представляет импульсный вход, а /о соответствует отсутствию любого импульса. Каждое внутреннее состояние в столбце /о является устойчивым. Поведение цепи, при котором входы изменяются от импульса /, к импульсу 7, может быть проанализировано при рассмотрении переходов от столбца /j к /о и затем от /о к /д. На рис. 4.4 показаны переходы, соответствующие двум переходам, представленным на рис. 4.1. Последовательностная цепь с импульсным входом может быть спроектирована таким образом, чтобы получать импульсные или потенциальные выходы. Показанные на рис. 4.4 выходы в столбце /о таковы, что требуют неизменности своих предыдущих значений (каждый такой выход указывается в таблице символом S). Выходы могут поддерживаться в своих предыдущих значениях триггерами, которые устанавливаются либо в О, либо

4.2. ПОСТРОЕНИЕ ТАБЛИЦЫ ПЕРЕХОДОВ

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

Пример 4.1. Рассмотрим асинхронный счетчик с двумя двоичными выходами х\, х2. Входной сигнал Xi = Xz = О является установочным сигналом, который приводит счетчик в исходное состояние, обеспечивая на выходе состояние 00. При переходе разрешается изменять только одну входную переменную. Счет ведется по приращению на 1, когда на вход поступает Xi, х2 = = 01, и по приращению на 2, когда на вход поступает Хи х2 = = 10. В последнем случае счет ведется по модулю 4. Вход Xi, х2= II не приводит к какому-либо изменению в счете. Выходы Zl, z2 характеризуют текущее состояние счетчика.

Примитивная таблица переходов для описанного выше асинхронного счетчика представлена на рис. 4.5. Для каждой строки qj таблицы следующее состояние указывается для тех состояний входа, которые могут следовать за состоянием входа, содержащим устойчивое состояние в строке qj. Исходное состояние 1 является устойчивым в столбце 00. За этим входом может следовать столбец 01, приводящий к следующему состоянию, которым является состояние 2, и счету 1 (zi, Z2 = 01), или столбец 10, который приводит к следующему состоянию 3 и счету состояний 2 (zj, Z2 = 10). Содержимое строки 1 и столбца 11 является неопределенным. За устойчивым состоянием 2 в столбце 01 при входах 00 или 11 может последовать переход к исходному состоянию 1 или к состоянию 4 без изменения результата счета. Содержимое оставшихся состояний определяется аналогично. Выходы определяются только для устойчивых состояний, причем предполагается, что выходы могут изменяться в любое время в процессе перехода.

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

В 1, когда входом является /о- Таким образом, цепь, представленная на рис. 4.4, будет выдавать потенциальные сигналы на выходе в ответ на воздействие входных импульсов.

Рис. 4.5. Примитивная таблица переходов для примера 4.1.

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

4.3. СОКРАЩЕНИЕ ТАБЛИЦЫ ПЕРЕХОДОВ

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

таблица переходов имеет в строке Два или более устойчивых состояния, то ограничивающее условие, касающееся изменения ОДНОЙ переменной, не может быть точно сформулировано в виде снятия указанного для входов ограничения, поскольку может быть разрешен конкретный вход от одного из столбцов с устойчивым состоянием в пределах строки, а не от другого столбца. Следовательно, сокращенная версия примитивной таблицы может требовать меньшего количества состояний, чем в случае соответствующей непримитивной таблицы, если допускается изменение только одной входной переменной. Рассмотрим таблицу переходов, показанную на рис. 4.6, а, и соответствующую примитивную таблицу (рис. 4.6,6) при допущении, что изменяется одна входная переменная. Таблица, приведенная на рис. 4.6, а, является несокращенной, тогда как примитивная таблица (рис. 4.6,6) может быть сокращена до таблицы с тремя устойчивыми состояниями (рис. 4.6,в). Разумеется, любая таблица ОИВ нормального режима может быть расширена до примитивной таблицы переходов как первый шаг в процедуре минимизации количества состояний.

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

При наличии таблицы переходов с однократным изменением выходов (ОИВ) выход, связанный с неустойчивым состоянием, должен быть таким же, как и вход, связанный с устойчивым состоянием в начале или в конце перехода. Если мы присвоим этим неустойчивым состояниям один и тот же выход, такой же как в конечном устойчивом состоянии, то влияние этого присваивания будет сказываться только во времени изменения выхода. Если не учитывать этот эффект, то получаемую при этом таблицу переходов можно рассматривать как эквивалентную исходную таблицу. Кроме того, если в конкретном столбце состояние оказывается неустойчивым, то следующее состояние и выход могут быть сделаны устойчивыми в том столбце, который будет окончательно достигнут из неустойчивого состояния. Таким образом, если является неустойчивым в столбце h, а qj является устойчивым состоянием, которое будет достигнуто из qi, то мы выполняем преобразование N{qi, h) = 9j и Zquh)

= Z(9,-, fk). Эту процедуру будем называть нормализованным .преобразованием таблицы ОИВ в таблицу переходов нормального режима.

Лемма 4.1. Если пара состояний qi и qj таблицы переходов М с однократным изменением выходов является совместимой, то qi и qj являются совместимыми в таблице переходов М' нормального режима, получаемой посредством нормализации таблицы М.

Доказательство. Допустим, что устойчивыми состояниями, достигаемыми из qi и q, при входе являются соответственно q-m и qn- Поскольку qi и qj являются совместимыми в таблице М, то qm и qn должны быть совместимыми. В таблице М' имеет место N{qi, h) = qm а N(qj, 4) = 9 . Следовательно, qt и qj будут совместимыми в таблице М', если qi и qj являются совместимыми выходами. При построении таблицы М' Z{qi, h) = = Z(qm, Ih) и Z{qj, Ih) =Z{qn, h), но Z{qm, h) = Z{qn, h), так как qm. и (? являются совместимыми. Следовательно, Ziqu Ik) - Z{qj, Ih) и qi и qj являются совместимыми в таблице М'.

Нормализация таблицы ОИВ не приводит к разрушению каких-либо совместимых пар, но может создать, новые совместимые пары. Метод сокращения таблицы состояний, который обсуждался в гл. 3, может быть применен к получаемой таким образом таблице переходов нормального режима. Как следует из леммы 4.1, таблица переходов, получаемая при минимизации количества состояний в нормализованной таблице переходов, не будет содержать большего количества состояний, чем получаемое при сокращении исходной таблицы.

Пример 4.2. Таблица переходов, показанная на рис. 4.7, а, не имеет совместимых пар состояний. Поскольку эта таблица имеет только одно изменение состояния на выходе, она может быть преобразована в таблицу переходов нормального режима, представленную на рис. 4.7,6, посредством изменения входов, обозначенных звездочками. Теперь (1,3) и (2,4) являются совместимыми парами, которые образуют замкнутое множество, и могут быть объединены для того, чтобы получить сокращенную таблицу, показанную на рис. 4.7, е. Такое сокращение было бы невозможно для исходной таблицы, представляющей синхронный автомат.

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

а

.v.x.

Рис. 4.7. Сокращение нормализованной таблицы переходов.

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

Для ОСНОВНОГО режима последовательностных автоматов с многократным изменением выхода мы предполагаем, что автомат всегда начинает функционирование с устойчивого состояния и что изменения на входе происходят только тогда, когда автомат находится в устойчивом состоянии. В результате для любого неустойчивого полного состояния оказывается необходимым рассмотрение в одном входном столбце в течение любого перехода только следующего состояния и содержимого выходов. Это может привести к тому, что пара состояний, которая не была совместима в предположении синхронного автомата, станет совместимой. Например, рассмотрим сегмент таблицы переходов, показанный на рис. 4.8. Если эта таблица интерпретируется как таблица переходов синхронного автомата, то состояния 1 и 5 являются несовместимыми, так как состояния 2 и 4 будут иметь несовместимые выходы. Однако в предположении, что основной режим функционирования асинхронный, состояния 1 и 5 являются совместимыми, так как они имеют совместимый выход, и оба состояния приводят к устойчивому состоянию 3 с выходной последовательностью 101, если используется вход h-

Влияние ограничения на входные переменные, подразумеваемое при основном режиме функционирования, может быть представлено в таблице переходов в виде следующего ее дополнения. Для каждого неустойчивого полного состояния (г, Ij) в таблицу переходов добавляется строка, обозначаемая qk- Где бы ни появилось qi в качестве следующего содержимого состояния Б столбце Ij, оно заменяется на qk- Следующее состояние и выход от {qk, Ij) должны быть определены таким же образом, как выход от {qk, Ij) в исходной таблице переходов, т. е. N{qk, Ij) = N{qi, Ij) и Z{qk, Ij) =Z{qi, Ij). Следующее состояние и содержимое выходов во всех других столбцах строки q, не определяются.

Пример 4.3. Рассмотрим таблицу переходов, приведенную на рнс. 4.9, а, которая должна быть сокращена исходя из предположения о зависимости от временных параметров. Данная таблица переходов не содержит какой-либо совместимой пары состояний. Таблица расширяется до таблицы, представленной на рис. 4.9, б, добавлением состояний б, 7 и 8, соответствующих полным состояниям (2, 01), (2, 11) и (2, 00) соответственно.

Рис. 4.8. Сегмент таблицы переходов.