реализации с помощью сдвигового регистра, тогда код вида -101 должен быть присвоен состоянию 5. Из кодирования № 2 таким возможным кодом для состояния 5 является только 5а= = 1101. Аналогичным образом, поскольку iV(5,0) =4, для состояния 4 должен существовать код, который в соответствии с кодированием № 2 является 4а = 1110, и так как N{5, 1)=3, то соответственно для состояния 3 имеем код вида -ПО, откуда (из кодирования № 2) будем иметь За = 0110. Этот процесс продолжаем до тех пор, пока не будет выбран полный код для реализации в виде сдвигового регистра, как показано на

2=10)-

п=ШО 30=0110

ЗЬ=0111 I ~ I

I L I га=!01 1о=РР11

20 1о 5п I 1

lb=000i 5Ь=1001

I I Н-1

lc=DOOO Sc=I0C0 Ah=1100 3c=0t00

Г-Ч Г-Ч з'с Г-Ч

1с Sc lib ЗС 2b=j01D 1d=DOlO

5а I 1

lb 5Ь

Рис. 5.49 Получение реализации многозначного кодирования с помощью сдвигового регистра с обратной связью.;

рис. 5.49, где приведены коды, причем различным состояниям присвоены разные коды. Проверка показывает, что не имеется кода, присвоенного более чем одному состоянию. Таким образом, для реализации с помощью сдвигового регистра из кодирования состояний № 2 может быть получено кодирование № 1.

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

5.6.5. МЕТОДЫ РЕАЛИЗАЦИИ С ИСПОЛЬЗОВАНИЕМ ПАМЯТИ

НА RS-ТРИГГЕРАХ С МИНИМАЛЬНОЙ ОБРАТНОЙ СВЯЗЬЮ

Поскольку 1)-триггер можно реализовать с помощью/-триггеров без дополнительной обратной связи (рис. 5.50), результат реализации с минимальной обратной связью с D-триггером

Синхросигнал

xlt-i]

Рис- 5.50, Реализация й-триггера.

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

Лемма 5.22. Таблица состояний с циклом состояний длины и 2 в любом столбце при использовании цепей с PS-триггерами не может быть реализована без обратной связи.

Доказательство. Пусть имеется таблица состояний с циклом на п состояний в столбце Ij {N {qi,Iq) = q, N {qi, Ij) - qi+u 2г^п-1, N{qn,Ij) =q\), 2, и пусть она реализуется

Ук-Г

Рис. 5.51. Ациклическая цепь с 7?5-триггерами.

цепью с PS-триггерами без обратной связи, как показано на рис. 5.51. В любом исходном состоянии цепь достигает устойчивого состояния при соотношении р> k последовательных входных сигналов Ij после максимум k-то входного сигнала и будет оставаться в этом состоянии при поступлении оставшейся части последовательности, хотя конечное состояние может зависеть от исходного состояния. Однако таблица с циклом состояний длины п 2 в столбце Ij, возможно, останется неустойчивой при поступлении входной последовательности произвольной длины повторяющихся входных сигналов h, и, следовательно, ее нельзя реализовать цепью, изображенной на рис. 5.51.

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

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

Предположим, что цепь С, изображенная на рис. 5.51, реализует М. Рассмотрим реакцию цепи С на входную последовательность Xft = (01)*= 0101 ...01, подающуюся на ав-

k раз

томат М, находящийся в некотором исходном состоянии Qi. Выход первого триггера yi будет либо стабилен, либо будет колебаться с периодом два в фазе со входом х. Тогда г/г также будет колебаться с периодом два в фазе с X или будет стабилен. Это справедливо для всех Уг- Таким образом, состояние С будет либо периодически меняющимся (период равен двум), либо будет стабильным при входной последовательности Х^. Следовательно, конечное состояние С при исходном состоянии qi и входной последовательности совпадает с конечным состоянием С при исходном состоянии qj и входной последовательности XfeOl. Но это не справедливо при исходном состоянии М, равном 2. Следовательно, с помощью С нельзя реализовать М.

Хотя класс автоматов, реализуемых без обратной связи с помощью PS-триггеров, известен и определить его не представляет труда, однако для этого необходимо знание некоторых элементов теории, выходящих за рамки данной книги. Их можно найти в работе [2]. Этот класс автоматов называют автоматами с несчетными компонентами и свободными от групповых компонентов.

М

Рис. 5.52. Таблица состояний, ие являющаяся ациклической цепью с 7?5-триггерами.

5.7. УНИВЕРСАЛЬНАЯ КАНОНИЧЕСКАЯ

ДЕКОМПОЗИЦИЯ ПОСЛЕДОВАТЕЛЬНОСТНЫХ АВТОМАТОВ

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

Рис. 5.53. Таблица состояний, пример 5.22

Пример 5.22. Легко убедиться, что для таблицы, представленной на рис. 5.53, Ли - {123, 124, 134,234} обладает свойством подстановки.

Автомат Men состояниями является перестановочно-возвратным автоматом (РР-автоматом), если каждый столбец М является либо столбцом перестановок (каждое из п состояний используется только один раз в качестве элемента следующего состояния в этом столбце), либо столбцом возврата (используется только одно состояние для определения следующего состояния в этом столбце).

СОСТОЯНИЙ представляет собой возвратный автомат, если в каждом входном столбце содержится только один элемент следующего состояния (т.е. n {qu h) = n {qj, 1) для всех состояний qu qj и всех входов h). Таблица с п состояниями является перестановочным автоматом, если каждый входной столбец содержит все п элементов следующих состояний (т.е. n{qulk)¥= ф n{qj,Ik), если qi¥=qj; ни один элемент не присутствует дважды в любом столбце).

Воспользуемся понятием системы установок я , определяемой на множестве п элементов. Эта система, которую мы назовем универсальным системным множеством, имеет п блоков, каждый из которых содержит п-1 элементов. (Отметим, что Ли не является правильным системным множеством.) При п - = 4 я = (123, 124,234,134).

Лемма 5.23. Для универсального системного множества я , определенного на множестве п элементов, S(n ) (т.е. системное множество Ли обладает свойством подстановки) для любого последовательностного автомата с п состояниями.

Доказательство. Обозначим п блоков через Bi, в2, ..., В^, и пусть Вг содержит все состояния М, кроме qi. Для любого автомата М и любого входного столбца h автомата А каждый блок СП- 1 состояниями отображается в некоторый блок с qn- 1 состояниями автомата М при входе 4. Следовательно, 5(яи).

Рис. 5.54. РУ?-автомат, определенный таблицей состояний, представленной

иа рис. 5.53.

являться Bi для всех Bj, а автомат Л может оставаться PR-гв-томатом. Автомат Л' с тремя состояниями, соединенный последовательно с автоматом Л для реализации исходной таблицы, может быть получен таким образом, как описано в разд. 5.4.

Декомпозиция, определенная в лемме 5.24, может быть повторена для автомата А'. Повторение этой процедуры п - 2 раза приводит к декомпозиции, определенной в следующей лемме, поскольку все автоматы с двумя состояниями являются РР-автоматами.

Лемма 5.25. Любой автомат М может быть разложен на последовательность из п-1 РР-автоматов Ль Лг,..., Л„ 1 с числом состояний соответственно/г^ п - },п - 2, ... 3,2.

Лемма 5.24. Любой автомат Men состояниями может быть разложен на РР-автоматы с п состояниями и автомат с п-1 состояниями.

Доказательство. Универсальное системное множество Пи может быть использовано для декомпозиции автомата М на автомат А с п состояниями и автомат Л' с п- 1 состояниями (поскольку каждый блок Пи имеет п - 1 состояние). Элементы следующего состояния в автомате А могут быть определены таким образом, чтобы автомат Л являлся РР-автоматом следующего вида. Если столбец автомата М не является столбцом перестановок, то некоторое состояние qi не используется в качестве элемента следующего состояния в столбце h- Определим N{Bj,lk) = Bi для всех Bj, делающих его столбцом возврата. Если столбец 4 автомата М является столбцом перестановок, то соответствующий столбец автомата А будет столбцом перестановок, поскольку N{Bi, Ik) ф N{Bj, Ik), i ф j.

Пример 5.23. Автомат Л таблицы состояний из примера 5.22 изображен на рис. 5.54. Отметим, что N{Bi,h) может также

Тождественно-возвратным автоматом является такой автомат, столбцы которого являются столбцами возврата или тождества. Иначе говоря, для любого входа h, Nqulh) - для всех состояний qi или N{qi,Ih) = qi для всех q Конструкция, полученная на основе леммы 5.25, может быть разложена далее, как это показано в следующих леммах.

Лемма. 5.26. Любой Р/?-автомат мол<ет быть реализован последовательным соединением перестановочного автомата Ai и тождественно-возвратного автомата Лг-

Доказательство. Если автомат А является Р/?-автоматом, то входные столбцы А могут быть разделены на два непересекающихся множества:/р - перестановочные входы и/г - возвратные входы. Пусть столбец перестановок /р^ задает отображение 1-1. Покажем, как можно ра.зложить автомат А в последовательное соединение перестановочного автомата Ai и тождественно-возвратного автомата Лг. Определим сначала автомат Ai. Если входы /р^ и 1р. являются столбцами перестановок Л, то входная последовательность IpJpj также определяет отображение 1-1 множества состояний Л. Пусть Р состоит из всех различных отображений, определенных входной последовательностью, полностью состоящей из перестановочных входов и тождественного отображения Р/.

Если отображение pi отображает переход из состояния q в состояние qu, обозначим его как Pi{qj) = qu- Для любого такого отображения pi инверсия р., р- является отображением 1-1, так что формируемое отображение Pi{PT {я,)) = qj ДЛя всех qj. Пусть Р- состоит из множества инверсных отображений для всех отображений Р. Множество состояний А\ будет соответствовать элементам множества Р U Р . Входные столбцы автомата А\ будут теми же, что и входные столбцы автомата Л.

Элементы следующего состояния для автомата А\ определяются таким образом: Np., I = pi, где ри - отображение,

определяемое входом 1р., примененное к отображению, определенному посредством для возвратного входа/ г.) ~

= р.. Таким образом, автомат А\ отрабатывает перестановки, осуществляемые при поступлении входных сигналов /р, и не изменяет состояние при поступлении на автомат А входных сигналов возврата.

Множество состояний автомата Лг является таким же, как и множество состояний автомата Л. Входами в Лг являются состояния Л], Р и Р' и внешние входные сигналы. Обозначим состояние возврата при входе/r через t.. Элементы следующего состояния для состояния qm автомата Лз определяются следую-

щим образом:

(Pi Pi)) = m (тождественность), {Ят, {Pi Kj))=Pk{ti), где Pk = P7 (возврат).

Комбинированное состояние (р^, q) автоматов Ai и А^ отражает состояние ptiqm) автомата Л. Для инициализации автомата А в состояние г установим автомат Ai в состояние pj а автомат Л2 в состояние г (поскольку pjir) = r). Поступление входа /р вызывает переход автомата Л, в состояние р^

а Лг остается в состоянии г, что вызывает установку общего состояния автомата Pj(r). Входная последовательность Irj, которая возвращает автомат Л в состояние 1, заставляет автомат Al оставаться в состоянии pj, а автомат Лг изменить состояние на рг (), что приводит к установке общего состояния Рj {ру{tkj)~k- Таким образом, последовательное соединение автоматов Л] и Лг реализует автомат А.

Пример 5.24. Автомат, представленный на рис. 5.55, а, имеет столбцы перестановок /ь /3, /5. Перестановки в этих столбцах обозначены через ри рг и рз. Входные последовательности /1/3 и /1/5 определяют соответственно перестановки Р4 и ps. На рис. 5.55,6 показаны все шесть возможных перестановок трех состояний, включая тождественную перестановку р/. Таблица, представленная на рис. 5.55, в, задает объединенные отображения pipj - pj(pi) для всех Ри Рг Заметим, что для каждого рг существует р. = рг, так Что p.p. = р^. Например, р- = р^.

Исходный РР-автомат может быть разложен на перестановочный автомат Ль изображенный на рис. 5.55,г, и тождественно-возвратный автомат Лг (рис. 5.55, <Э). Элементами следующего состояния автомата Ai в строке pi и столбцах /ь /3 и /5 являются перестановки, определяемые соответственно как р^рь РгР2 и ргРз- Столбцы возвратов /г и Ii автомата Л задают столбцы тождественности в автомате Ль Тождественно-возвратный автомат Лг содержит 30 столбцов, каждый из которых, кроме показанных на рис. 5.55, <Э, является столбцом тождественности. Типичный элемент, скажем 2-й (рг, h), определяется следующим образом: состоянием возврата в столбце /г автомата А является 2. Из таблицы, представленной на рис. 5.55, в, видно, что р^ - р. и р^ (2) = 3. Остальные элементы определяются таким же образом.

Лемма 5.27. Любой тождественно-возвратный автомат может быть реализован последовательным или параллельным соединением возвратных автоматов с двумя состояниями.

д

Рис. 5.55. Таблицы состояний, пример 5.24.

Пример 5.25. Тождественно-возвратный автомат М, представленный на рис. 5.56, а, разложен в параллельное соединение автоматов А и В, как показано на рис. 5.56,6-г.

Теорема 5.5. Любой последовательностный автомат с конечным числом состояний может быть реализован последовательно-параллельным соединением перестановочных автоматов и тождественно-возвратных автоматов с двумя состояниями.

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

Доказательство. Вытекает непосредственно из лемм 5.25- 5.27. Как видно из рис. 5.57, результатом реализации является

Рнс. 5.56 Декомпозиция тождественно-возвратного автомата. I

Pl Н 1

-----P 2

Рнс. 5.57. Каноническая декомпозиция автомата с конечным числом состояний

последовательная декомпозиция на различные перестановочные автоматы и тождественно-возвратные автоматы.

5.8. УМЕНЬШЕННАЯ ЗАВИСИМОСТЬ

В АСИНХРОННЫХ ПОСЛЕДОВАТЕЛЬНОСТНЫХ ЦЕПЯХ

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

Рис. 5.58. Таблица переходов асинхронной цепи.

быть не определены слева. Однако в случае асинхронных цепей может оказаться необходимым определение этого кодирования для обеспечения должных операций в соответствии с пояснениями, имеющимися в гл. 4. Таким образом, условие пар множеств теоремы 5.1 не является достаточным при уменьшенной зависимости в асинхронных цепях. (Можно показать, что это справедливо для всех типов кодирования состояний на асинхронных цепях). Выводы теоремы 5.1 распространяются на асинхронные цепи с однозначным ОВП-кодированием в соответствии с теоремой 5.6. Разбиение {qi, qy, q, qi), связанное с переходами состояний qiqj и qhqi, является релевантным для разбиения т в том и только в том случае, если Ф qi {%).

Теорема 5.6. Пусть заданное однозначное ОВП-кодирование для таблицы переходов М, обозначенное как а, будет подмножеством переменных состояний. Тогда для любой переменной состояний г/j Уз =/з(а,/ft) в том и только в том случае, если

а) РГ П т,. .Л' б) любое разбиение, релевантное для раз-

биения Гу, покрывается некоторым yt е а.

Доказательство. Необходимость. Необходимость условия а) следует из того факта, что если оно не удовлетворяется, то су-

следует из рассмотрения автомата, изображенного на рис. 5.58. Показанное кодирование состояний является правильным однозначным ОВП-кодированием.

По таблице переходов можно убедиться, что Р (т^ т^, )

где Tj, = (13,24), Ту = (12,34) и =(1,234). Тогда, следуя теории уменьшенной зависимости в синхронных цепях, можно было бы ожидать, что Кз не будет зависеть от уз,. Однако это не так. Дело заключается в том, что в случае синхронных цепей все коды в матрице У, которые не присвоены состояниям, могут