Реализации последовательностных автоматов 355 ществуют по крайней мере два состояния q=qi,{ Tl и

входной вектор /s, такие, что N[q, 1k){Qb, h){v-довательно, Yj не может определяться только по входу и тому факту, что у г е О-

Пусть {qa, qb\ qc, qd) является разбиением, релевантным для т^. Если условие б) не удовлетворяется, то не существует Уг

е о, которое остается фиксированным при различных значениях в течение двух переходов: qa-qi и qc-qa- Тогда оказывается возможным предположение, что переменные в а имеют одно и то же значение г/j в течение обоих переходов: qa-qb и qc-qa-В случае реализации цепи, заданной таблицей переходов, необходимо одновременное выполнение условий N (у^, 1) = q (т^ и

(У/. h)Qd{y} Но q,Ф Я^{у^- Следовательно, Y

Достаточность. Рассмотрим переход из состояния в состояние qb под воздействием входных сигналов 1. Пусть состояния qa и qb имеют соответственно значения у° и j* из числа переменных множества а. Поскольку условие а) удовлетворяется, все состояния блока П т , к которому относится состоя-

ние qa, имеют свои следующие состояния в том же блоке т ,

т. е. все их следующие состояния кодируются одним и тем же значением г/,-. Вследствие того что выполняется условие б), в течение времени перехода от <? к qb переменные г/ из а не получат какого-либо значения из г/о, которое может быть использовано в течение другого перехода, например от состояния qc к состоянию qd при входе Ik\ здесь состояние qa закодировано значением г/j в отличие от состояния qb. Следовательно, все состояния, для которых переменные г/ из а, с помощью которых кодируется значение, которое может ими быть использовано в течение перехода от qa к qb, имеют свои следующие состояния в том же блоке , что и состояние qb. Следовательно, все булевские векторы, для которых используются переменные у из подмножества а в течение перехода от у° к у*, получат единственное значение г/j. Это справедливо для всех переходов.

Следующая лемма показывает, что выполнение условия б) теоремы 5.6 подразумевает выполнение условия а) той же теоремы.

Лемма 5Л8. Пусть 5р является множеством разбиений состояний по два блока таблицы переходов М, функционирующей в нормальном режиме. Если Sp покрывает все разбиения, реле* Байтные для заданного разбиения Ту, то Р ( Yl. и f/Y

Доказательство. Предположим, что sp покрывает все разбиения, релевантные для Tj, но IJ т,-, гЛ не является парой

разбиений. Это означает, что существует по крайней мере одна пара переходов, например Qa-Qb и qc-*Qd, в одном и том же входном столбце, такая, что qa = qc{ti) для всех j/isSp и qb¥= ¥=d{T:j)- Теперь ?6=79d(Tj) означает, что разбиение (qa,qb; qc, qa) является релевантным для tj. Следовательно, в соответствии со сделанным предположением это разбиение покрывается некоторым Xisp. Из этого следует, что qa¥qc{ri) для некоторых Хг е Sp, что является противоречием. Следовательно, каждая пара состояний в одном и том же блоке п для всех Тг е sp должна иметь свои следующие состояния в том же блоке tj. Следовательно, р( П т,-, тЛ.

Следствие 5.2. Если задано однозначное ОВП-кодирование таблицы М и подмножества а множества переменных состояний, то для любой переменной состояний yj выполняется условие yj = fj{g,i) в том и только в том случае, если разбиения, релевантные для т^, покрываются некоторым yi е а.

Ангер [27] показал, что для любой переменной состояний уи используемой для кодирования состояний таблицы переходов в нормальном режиме, У{ всегда является функцией уг или же Уг оказывается излишней. Следовательно, при установке правильного однозначного ОВП-кодирования, если yj = fj{ik, Gj), всегда можно получить yj е oj.

Результат Ангера для случая однозначного ОВП-кодирования легко получить из следствия 5.2, но сначала докажем следующую лемму.

Лемма 5J29. Пусть at и Ог являются двумя подмножествами множества переменных состояний, соответствующих однозначному ОВП-кодированию таблицы М, и Оп = О; U Ог. Если У/ =

= ft {Ik, gt) iiyr = fr {Ik, У и gr) , то yr = fr {Ik, grt)

Доказательство: Из следствия 5.2 вытекает, что У^ = fr {h, Grt в том и только в том случае, если все разбиения, релевантные для , покрываются некоторым у. е а^. Предположим теперь,

что Yr Ф fr {h, Grt)- Это приводит к тому, что существует разбиение, например {q, ql qc, qa), не покрываемое ни одним у1S Grt. Поскольку {qa, qt, qc, Яа> является релевантным для Хуг, а Yr=fr (/, ytGr), оно должно покрываться yt- Следовательно, ь^Яа(у} Тогда (q, q; q, q) также релевантно для т^ и

должно покрываться некоторым у е а^. Из этого следует, что все разбиения, релевантные для Ху, покрываются некоторым yiGt\j Or. Откуда получаем, что У^ = fr (/, Grt).

Рис. 5.59. Таблица переходов, пример 5.26.

бы для некоторого входного столбца Ij все состояния имели тот же код в yi, что и их элементы следующего состояния (т. е. q. = N[q, Ij){y))- Эта переменная будет удовлетворять всем разбиениям, релевантным для нее в столбце Ij. Переменная состояний г/1 на рис. 5.59 удовлетворяет этому условию в случае входного столбца 00.

Из теоремы 5.7 нам известно, что Yi является функцией ух. Составим список всех разбиений, релевантных для т„, но не по-крывающихся г/ь и определим множество переменных для покрытия этих разбиений. Для таблицы, представленной на рис. 5.59, такими разбиениями будут (13,4), (23,4), (1,45) и (2,45), каждое из которых может покрываться единственной переменной.

Теорема 5.7. Если задано правильное однозначное ОВП-кодирование сокращенной таблицы М для всех необходимых переменных состояний Уг И если Yi = fi{Ik,Oi), где Ог является подмножеством множества переменных состояний, то Уг е Ог-

Доказательство. Предположим, что в кодировании участвует такая переменная yt, что Yt = ft{h,Ot) Угф- оь Из леммы 5.29 следует, что можно использовать любую другую переменную, независимую от yt. Более того, если {qa, qt, qc qa) является разбиением, покрываемым yt, то оно релевантно для т^. Следовательно, оно покрывается некоторым г/, о;. Отсюда все разбиения, соответствующие каждой паре переходов, покрываются некоторой переменной состояний, отличной от yt, откуда следует, что yt не является необходимой для обеспечения правильного однозначного ОВП-кодирования.

Пример 5.26. Рассмотрим таблицу переходов, представленную на рис. 5.59. Определим исходную переменную yi так, что-

Если эта переменная определена как г/г (рис. 5.59), то она покрывает эти разбиения и покрывает также все разбиения, релевантные для г/гв столбце 11. Таким образом, Yi=fi(yi,y2,Xi,x2). Разбиениями, релевантными, но не покрывающимися г/г, являются (12,35), (24,35), (1,34) и (2,34), которые для покрытия требуют двух переменных. Если г/з покрывает разбиения (1,34) и (2, 34), то Уг = /2(1, У2; Уг, Хи Xz), поскольку yi покрывает два других разбиения. Переменная г/з (рис. 5.59) покрывает разбиения (1,34), (2,34) и все разбиения столбца 10, релевантные для нее. Разбиениями, которые релевантны, но не покрываются г/з, являются (14,35) и (24,35), причем оба они покрываются г/ь Следовательно, Уз =/3(1, з,- ь-г). Эти три переменные покрывают все разбиения таблицы, кроме разбиения (1,2), покрываемого г/4 (рис. 5.59). Переменная г/4 не имеет релевантных разбиений, не покрывающихся ею. Следовательно, У4 = = fi(yi, Х\, Xz). Это приводит к кодированию состояний (рис. 5.59), которое определяется неполностью, поскольку переменная г/4 необходима только для различения состояний 1 и 2.

В примере 5.26 кодирование определяет параллельную декомпозицию, в которой переменные уи yz и представляют один автомат-компонент, а у^ - другой. Отметим, что системные множества я, = т^, т^ = (12,3, 4, 5) и т^ = (1345, 2345) обладают свойством подстановки и Я|-т^ = 0. Декомпозицию асинхронных цепей рассмотрим в следующем разделе.

5.9. ДЕКОМПОЗИЦИЯ АСИНХРОННЫХ ЦЕПЕЙ

Условиями параллельной декомпозиции асинхронной последовательностной цепи являются те же условия, что и в случае синхронных цепей, как это определено в теореме 5.2. Каждый из автоматов-компонентов при параллельной декомпозиции должен реализовываться с правильным асинхронным кодированием состояний. Отсюда следует, что в отличие от синхронной декомпозиции число переменных состояний, требуемых в подавтомате Мг, может превосходить riog2#nil, где фяг - число блоков в разбиении щ, которое определяет Mj, а \хЛ обозначает наи-меньщее целое, не меньшее чем х.

Пример 5.27. Для таблицы автомата М (рис. 5.60) следующие разбиения обладают свойством подстановки:

Я1 = (123,456); яг= (13,46,2,5); яз = (14,25,36); Я4 = (1346,25); Я5 = (23,54, 1,4); Яе = (2356, 14).

Поскольку ягЯз-о, Я1 и Яз определяют два автомата Mi и.Ж.г, которые при параллельном соединении реализуют автомат М! Таблицы переходов подавтоматов изображены на рис. 5.61. Ис-

пользуя кодирование состояний, показанное справа от таблиц переходов, получаем следующую реализацию автоматов Mi и Mz.

YiIz + yJi, . 2=/4 +г/2/5.

Как и в случае синхронных автоматов, необходимым условием последовательной декомпозиции асинхронного последовательностного автомата М является существование нетривиального разбиения (или системного множества) щ, которое обладает свойством подстановки на множестве состояний автомата. Это разбиение определяет автомат Ми который, будучи последовательно соединенным с автоматом М2, дает реализацию М. Каждое состояние Ml соответствует блоку щ. Следовательно, автомат Ml будет функционировать в нормальном режиме, если автомат М функционирует в нормальном режиме. Основное отличие между последовательной декомпозицией

Рис, 5.60. Таблица переходов, пример 5.27.

синхронных автоматов заключается в методе, по которому определяется автомат Мг.

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

Для получения последовательной декомпозиции, работающей в режиме с одновременными переходами, для автомата Mi осуществляется ОВП-кодирование. Используя кодирование состояний для Mi как часть кодирования автомата М, присваиваем

М-1 а

Рис. 5.61. Подавтоматы декомпозиции, пример 5.27.

ЧТО не существует нетривиальной последовательности ОВП-де-композиции, если переменные состояний для Mi не покрывают любого разбиения М.

Пример 5.28. Двумя разбиениями, обладающими свойством подстановки на множестве состояний автомата М (рис. 5.62,а), являются Я1= (123,45,67,89) и П2= (12367,4589). Автомат Mi, определяемый посредством щ, изображен на рис. 5.62, б вместе с ОВП-кодированием {У1У2) для автомата Mi. Полное кодирование для автомата М получается добавлением переменных уз и У4 к кодированию Mi для того, чтобы покрыть разбиения М, не покрытые переменными г/, и г/а. Разбиение яа = (12367,4589) не может быть использовано для получения нетривиальной

дополнительные переменные состояний для покрытия разбиений М, не покрытых переменными состояний М\. Полученные таким образом переменные состояний могут рассматриваться как переменные состояний Мг в последовательном соединении М1ИМ2. Последовательное соединение автоматов Mi и М2 обладает тем свойством, что все переменные, которые должны измениться в процессе перехода, могут изменяться одновременно. Очевидно,

а

2 3 4 5 6 7 8 9

о

о о I I

о

Рис. 5.62. Таблица переходов, пример 5.28 (а); подавтомат декомпозиции (б).

ОВП-декомпозиции, поскольку оно не удовлетворяет никаким разбиениям автомата М.

Описанная выше последовательная ОБП-декомпозиция допускает одновременное изменение состояний автоматов-компонентов. Путем фиксации порядка, в котором автоматам-компонентам разрешается изменять состояние, часто оказывается воз-

I

Автотт М,

Asmomm Щ

Аетотт 6

Рис. 5.63. Две модели последовательной декомпозиции.

можным получение более простой реализации за счет скорости выполнения операций. Две такие модели декомпозиции представлены на рис. 5.63.

На рис. 5.63, G следующее состояние автомата М2 определено текущим значением входных сигналов и текущим состоянием автомата Mi. Величины задержек Di в автомате Mi должны быть такими, чтобы автомат М2 достигал устойчивого состояния после изменения входного сигнала, но перед тем, как изменятся выходные сигналы задержек в автомате Mi. (Если состояние М2 не зависит от изменяемых переменных Mi, то декомпозиция является ОВП-декомпозицией). Автомат Мг должен быть разрабо-

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

Другая возможная модель показана на рис. 5.63, б. Следующее состояние автомата М2 определяется входными сигналами и следующим состоянием автомата Mi. Поскольку автомат М2 зависит от входных сигналов и переменных состояний автомата Ml, изменяемых в произвольном порядке, автомат М2 должен быть спроектирован таким образом, чтобы он не изменял состояния до тех пор, пока все входные сигналы (т. е. внешние входы и переменные состояния автомата Mi) не достигнут своих новых значений. Это достигается путем использования искусственного метода, допускающего одновременное изменение входных сигналов. Такой тип реализации иногда оказывается более экономичным, чем тот, который представлен на рис. 5.63, а.

В обеих моделях автомат Mi получается из разбиения, обладающего свойством подстановки, или системного множества щ, как и в случае синхронных автоматов. Для получения же автомата М2 строим таблицу переходов М', имеющую столбцы, соответствующие каждой комбинации входного сигнала и внутренних состояний автомата Mi, и строки, соответствующие каждому внутреннему состоянию автомата М. Элементы в М' записываются в соответствии с моделью последовательной декомпозиции, выбранной так, чтобы последовательное соединение Mi и М' реализовало автомат М. Пусть столбец h автомата М содержит переход qi-qj и пусть Bi и Bj являются блоками jii (и, следовательно, состояниями Mi), содержащими состояния qi и qj соответственно. При использовании модели, представленной на рис. 5.63, G,М'строится таким образом, чтобыiV(9j, {Bi,In)) = = N(qj, {Bi, h)) = N{qj, {Bj, 1)) = qj. N{qi, {Bj, h)) является неопределенным слева, поскольку автомат Мг изменяется раньше, чем Ml. Если используется модель, представленная на рис. 5.63,6, то требуется, чтобы N{qi, {Bj, 1))--==N{qj, {Bj,Ik)) = = qj и N{qi, {Bi,IU)) - q Записываются элементы М' для всех переходов в автомате М, удовлетворяющие любым указанным выше условиям, зависящим от вида используемой модели, а оставшиеся элементы М' являются неопределенными слева. М' затем может быть упрощен, но любая пара состояний, находящаяся в одном и том же блоке щ, не может слиться в одно состояние. Можно собрать в один столбец сравнимые столбцы для уменьшения зависимости Мг от входных сигналов или состояний Ml. Сокращенная таблица переходов определяет автомат Мг, который, будучи последовательно соединенным с автоматом Ml в соответствии с моделью, изображенной на рис. 5.63, реализует автомат М. Если М' нельзя упростить, то Мг = М' и

разбиение 3Xi приводит к тривиальной последовательной декомпозиции. Последовательная декомпозиция с неодновременными переходами также может рассматриваться как кодирование состояний автомата М, так чтобы переменные состояний уи уг. ..., Уп могли делиться на два множества: уь ..., и yh+i ... ..., Уп- Первое множество используется для кодирования состояний автомата Mi и не зависит от второго, используемого для кодирования состояний автомата Мг- Второе множество может зависеть от всех переменных. Подбор состава каждого множества выполняется на основании выбора кодирования для двух автоматов-компонентов. Разбиение же переменных на различные множества выполняется на основании фиксации порядка, в котором группы переменных могут изменяться.

5.10. РЕАЛИЗАЦИЯ АСИНХРОННЫХ ЦЕПЕЙ

С ИСПОЛЬЗОВАНИЕМ СДВИГОВЫХ РЕГИСТРОВ

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

При асинхронном функционировании в нормальном режиме продолжительность конкретного входного сигнала (предполагается некоторая минимальная продолжительность) не играет роли, поскольку автомат будет оставаться в определенном устойчивом состоянии до тех пор, пока не изменится состбяние входа. Изменения входного состояния и являются входной последовательностью. Таким образом, можно всегда рассматривать текущее состояние входной последовательности, которое отличается от ее предыдущего состояния Если проектируется цепь, предназначаемая для генерации выходного импульса при возникновении изменений на входе, то этот импульс может с успехом быть использован в качестве тактирующего сигнала и, следовательно, можно создать асинхронную цепь, работающую в синхронном режиме. Цепь, изображенная на рис. 5.64, может быть использована в качестве такого генератора тактовых импульсов. Эта цепь генерирует импульс шириной, большей и равной величине Гмин на шине, обозначенной через q; здесь Гмин является величиной задержки элемента, обладающего минимальной задержкой. Импульс на шине q изменяет значение сигнала 5. Для того чтобы единичное изменение значений нескольких переменных не вызвало генерацию более чем одного выходного