Рис. 5.19 Ведомый автомат из последовательной декомпозиции, пример 5.10.

рассмотрим системные множества х' - (13,45,35) для таблицы, представленной на рис. 5.18, для которой п-х' ф 0. Если мы выделим два появления 3 в т' и л с помощью индексов, как напри-

Рис. 5.20. Ведомый автомат, определяемый с помощью другой декомпозиции

пример 5.10

мер п= (123а, Зь45) и т'= (136,24,35), то т' отделяет все элементы один от другого в пределах одного и того же блока л из М и, следовательно, лит' могут быть использованы для определения кодов состояний, показанных на рис. 5.20, а. Системные

МНОГОКОДОВОГО присваивания состояний, то системные множества п, X, которые определяют последовательную декомпозицию, недостаточны для удовлетворения условия л-т = 0. Например,

множества лих' определяют также последовательную декомпозицию. Ведомый автомат /Щ показан на рис. 5.20, б.

В этой таблице звездочка соответствует состоянию 3 автомата М, и, следовательно, это состояние представляется возможным для содержимого следующего состояния в А' (соответствующего Зь) или С (соответствующего SJ. Однако в данном примере это не является справедливым. Рассмотрим, например, содержимое (В\ В, Is). Комбинированное состояние (В, В') из Ml и Мг представляет состояние 4 из М (поскольку В f) В' = 4). Следовательно, комбинированное следующее состояние из Mi и Mg для текущего состояния (В, В') и входа должно представлять За или Зь (поскольку для автомата М имеет место /з) = 3). Но Л^(В, /з) для Ml уже было определено как Л, которое представляет 3 (рис. 5.18). Следовательно, следующее состояние из М' должно также представлять З^иМ (В', (В, /3) =--= С Заметим, что если (Б', В, /3)) определяется как А', то при композиции текущего состояния {В, В'), представляющего 4, и входа /з композиция следующего состояния должна бы-ть {А, Л'), которая представляет собой 1 вместо 3. Так как (Л, С) представляет состояние Зд и (3, /]) = 3, то (С, (Л, Ii)) должно представлять 3 или 3;,. Но Л' (Л, Ii) должно быть определено в Ml как Л. Поскольку 3;, представляется посредством (В, Л'), то (С, (Л, /])) = С, так что Mi и Мг совместно представляют За-

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

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

я1 = (12, 34, 56, 78), % = (14, 23, 58, 67), пз = (1278, 3456), - . - - .. 3t4=(1234, 5678),

я5 = (34, 56, 1, 2.7, 8),

Рис. 5.21. Таблица состояний из при- Рис. 5.22. Решетка разбиений со свой-мера 5.11. ством подстановки.

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

Рис. 5.23. Комплексная декомпозиция.

Для декомпозиции, представленной на рис. 5.23, а, предположим, что Ml определяется с помощью системных множеств Tj, г. М' с помощью системных множеств т' = Тг Tj, где тг определяет Mg, а Тз определяет М^. Так как Мг является независимым от Мз (и наоборот), то отсюда следует, что S (ti Тг) и 5(т,-Тз). Если Tj = Tj-t2 и т2==:т,-Тд, то мы можем использовать решетку разбиений, обладающих свойством подстановки, для того чтобы найти три разбиения Tj, х\ т^, таких, что

Эти разбиения могут быть представлены в виде решетки соответствующего размера, как показано на рис. 5.22.

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

Т] > Тр t, > Tg и т:.т2 = 0. Из рис. 5.22 видно, что разбиения Л4, П] и Л2 удовлетворяют этим условиям. Следовательно, Ml определяется посредством Л4 = (1234, 5678); определяется любым системным множеством х^, таким, что Т2-Л4 = Я1. Существует более чем одно такое системное множество. Одним из возможных выборов является Т2==(1256, 3478). Аналогичным образом, Mj определяется Тз, таким, что т:з-Л4 = Я2, которое удовлетворяется посредством Тз==(1458, 2367).

Для декомпозиции, показанной на рис. 5.23, б, Mi вновь порождается системным множеством Т4, обладаю!Цим свойством подстановки. Если Mg порождается системным множеством Tg, то т^= Tg обладает свойством подстановки, поскольку Ml и М2 являются независимыми от М3. Следовательно, решетка системных множеств, обладающих свойством подстановки, должна содержать два элемента т^, т^, таких, что > и S(t), 5(т^). Из рис. 5.22 видно, что М имеет такую пару разбиений Яз, щ (или Я4, Я1; или Я4, Яг , или Яз, Л5). Для получения декомпозиции, определяемой посредством Яз, я М определяется с помощью Яз, Мг - любым системным множеством Тд, таким, что Яз Т5 = Я], а М3 - любым системным множеством Xq, таким, что Тб Я1 = 0. Этим условиям удовлетворяют xs = = (1256, 3478) и Тб = (1357, 2468).

5.5. УМЕНЬШЕННАЯ ЗАВИСИМОСТЬ, ИСПОЛЬЗУЮЩАЯ ДРУГИЕ ТРИГГЕРНЫЕ ЭЛЕМЕНТЫ ПАМЯТИ

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

Рассмотрим таблицу, показанную на рис. 5.24, с, и кодирование состояний, связанное с ней. Для этого кодирования (т^й. Ti/i) не является парой множеств. Однако цепь, реализую-

о о

1 I 1 о

Рис. 5.24. Уменьшенная зависимость при использовании /?5-триггеров.

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

г, = ху, +- ху.

Т, б

Рис- 5.25 Уменьшенная зависимость при использовании Г-триггеров.

мости. Рассмотрим таблицу, приведенную на рис. 5.25, а. Для этой таблицы Pity Ху,). Однако логика возбуждения входа Г-триггера, реализующего Yi, зависит от г/i.

Теперь получим некоторые зависимости, которые могут быть использованы для того, чтобы охарактеризовать уменьшенную зависимость, если память реализуется на RS-, Г- и С-тригге-рах. Определение того, является ли переменная Fj независимой

щая функцию возбуждения для Yi, является независимой от yi. (Заметим, что можно использовать преимущества, связанные с тем, что триггер имеет внутреннюю обратную связь от уи в результате чего нет необходимости иметь г/i в качестве явного входа триггера.)

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

Лемма 5.14. Для автомата М, кодирование состояний которого определяется переменными ух, г/г, . .., Ур, если К, = yfx (г/1, г/2, Ур, >) + yifo{yu Уъ Ур, х), где f, и fo не зависят от г/£, то

1) Если в качестве элементов памяти используются Г-триг-геры, то Ti не зависит от yi тогда и только тогда, когда

2) Если в качестве элементов памяти используются PS-триггеры, то Ri и 5,- не зависят от Yi тогда и только тогда, когда fifo (т. е. каждая 1-точка из fo является также 1-точкой из /]).

3) Если в качестве элементов памяти используются (-триггеры, то Ji и Ki всегда не зависят от yi.

Доказательство. 1) Предположим, что существует реализация Yi, использующая Г-триггер с выходом Г, (г/ь у^, Ур, х). Тогда Yi = Tiyi-\-Tiyi=yifo + yifx. Если f i fo, то это уравнение имеет рещение Ti = fo, которое не зависит от г/-. Если fl Ф fo, то это уравнение не имеет рещения для Г которое было бы независимым от yi (выполните это доказательство в качестве упражнения).

2) Предположим, что существует реализация Yi на основе RS-триггеров с входами S=gx(yi, Ур, х) и P=g2( /i, Ур, х). Тогда Р5=:0 (так как не допускается S = R = \) и Yi - =:S+ Ryi = y.fQ + yj. Если fj = fjj-f f; (т. е. каждая 1-точка из fo является также 1-точкой из fj), тогда Y. = yJ+yi(fQ+f{) =

- fo + ytfi и имеется решение этого уравнения, S-fo, P = fi, в котором S и R не зависят от yi и 5 Р = /о f i = 0. Доказательство необходимости предлагается в качестве упражнения.

3) Выполните в качестве упражнения.

Основываясь на лемме 5.14, можно определить зависимости Т(лх,П2) и W(ni, Яг), которые используются для того, чтобы установить соответственно для Т- и Р5-триггеров кодирование состояний с уменьшенной зависимостью для случая, когда Яг представляет собой системное множество с двумя блоками.

Если заданы два системных множества яь яг, определенные на автомате М, где яг имеет два блока, то Г(л1-Я2, я) тогда и только тогда, когда

1) Р {Щ Щ, Яг) и

2) если qiQiini) qi¥= /Ы, то N [qt, 4) фЫ (q,-, /fe) (%)

для всех входов /д,.

Для системных множеств щ, Ла W {щ, тогда и только тогда, когда

1) Р{щ щ, %) и

2) для каждого qi при всех q, таких, что qi = qk{) для всех If, либо

N {qi, ) = Л/ {qk, Ij) (%), либо

9г = iqi, Ij) (Щ) и = iV (fe, Ij) (щ).

Пример 5.12. Для таблицы, показанной на рис. 5.24, если я, = {12, 34), Л2 = (14,23), то 2-1 = 0 и Р{лгщ, щ); 1=4(2), 0) = 2, Л/(4, 0) = 3. Следовательно, 1 = (1, 0) (л,) и 4 = Л/(4, 0) (лО. Для входа х= 1 ACl, 1)=-4, N{4, 1) = 4 и Л/(1, 1) = Л/(4, 1). Аналогичным образом, можно показать, что состояния 2 и 3, которые имеются, в том же самом блоке Лг, удовлетворяют второму условию определения W {щ, щ). Следовательно, W (л2, Л1) справедливо. Не является справедливым 7(л2, л,), так как 1 = 4(л2) и 1=5.4(л1), но iV(l, 1) = = iV(4, 1)(л1). Если лз = (13, 24), то Т {щ, щ).

Теорема 5.3, а. Если задана последовательностная цепь с Г-триггерами в качестве элементов памяти и переменными состояния г/1, г/з, ..., г/ , то Ti не зависит от г/j тогда и только

п

тогда, когда Г(т, т^.), где т = П%й-

Если задана последовательностная цепь с 7?5-триггерами в качестве элементов памяти и переменными состояния Уи У2, , Уп, то Rl и 5, не зависят от t/i тогда и только

п

тогда, когда W (х, Хщ), где т = П%г

Доказательство, а) Необходимость. Hjih условии реализации на основе Т-триггеров YiTyi+fyi. По теореме 5.1 Р П. Ту.. Предположим, что qi = qj{x) и (ту.).

Без потери общности, допустим, что У1 = 0 для и г/ = 1 для (7у. Тогда Yi - l для перехода (qi, h) тогда и только тогда, когда 7= 1, и = 1 для перехода (qj, Ik) тогда и только тогда, когда 7 = 0. Следовательно, N(qi, h) Ф N(q/, Ik){T:yi).

Достаточность. Выполните доказательство в качестве упражнения.

б) Необходимость. При условии реализации на основе PS-триггеров Yi=Si = Ry.. Необходимость условия (1) доказы-

11 Зак. 811 . ,......... ,.

Достаточность. Доказательство выполните в качестве упражнения.

Следующая лемма иллюстрирует взаимосвязь между соотношениями Р, Т Vi W.

Рис. 5.26- Таблица состояний, иллюстрирующая W-зависимость.

Рис. 5.27. Таблица состояний из примера 5.13

Лемма 5.15. Пусть Яг представляет собой разбиение, содержащее два блока для автомата А. Тогда

а) если Р(щ, то W {щ, я),

б) если Р (щ. Яг), то Т (щ, Яг), которое не сохраняется, если не выполняется условие ЯгЯ!.

Доказательство, а) Положим Р{щ, яг), где щ представляет разбиение, содержащее два блока. Тогда тривиально, что Р (я, Яг, Яг). Если qi == q {щ), то {qi, Ij) == N {q, Ij) (яг). Следовательно, W (Яь Яг).

б) Положим Р(я1, Яг), где Яг является разбиением, содержащим два блока, и ЯгЯр Тогда существуют qi, q, такие, что qiqjii) и qiqjM- Так как Р(я1, Яг), то N{qi, 4) = =N {qj, Ik){2)- Следовательно, Т {щ, ng) не имеет место. Если Щ^Щ, то не имеется состояний qi, q/, таких, что qi - qi(), qi Ф qjiz). Следовательно, Т {щ, Яг). Однако переменная, опре-

вается таким же способом, как для Т-триггеров. Предположим, что qi - qki)- Для обоих переходов {qi, lj) и (д^, Ij) одно из следующих трех условий должно быть удовлетворено для реализации функций возбуждения 5/ и Ri на триггерах при независимости от yi; S£ = l, RjO, S/ = 0, Ri = \, S,- = 0, Ri = 0. Если 5=0, Ri = 0, то qi=N{qt, lj){xy.) и = = ) Если S = l, P = 0 (или S = 0, JR == 1), то

Yi - \ (или 0) для всех этих переходов и, следовательно.

Рис. 5.28. Матрица возЗуж-дения, пример 5.13.

то, вообще говоря, вход при реализации на основе Г-тригеров, У / е U, должен представлять собой функцию всех Уг, iS, и всех уи, kU, а может даже зависеть от у, (в противоположность реализаций с памятью, выполненной на элементах задержки, когда Yj будет зависеть только от уг, tsS), что иллюстрируется следующим примером.

Пример 5.13. Для автомата, представленного на рис. 5.27, (%., (ту т^,)). Однако из матрицы возбуждения, показанной на рис. 5.28, следует, что

Tl = ХУ2У3 -г ХУ1У2 -т У1У2, Т2==ху1-\-уу1Уз, Тз. = ху2 -г У1У2 -г ХУ1У3. Т2 зависит от yi и уз, а Т3 зависит от yi, у2 и уз.

5.6. РЕАЛИЗАЦИЯ ФУНКЦИЙ

С ОСЛАБЛЕННОЙ ОБРАТНОЙ СВЯЗЬЮ

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

1И

деляемая посредством itg, не является необходимой для кодирования состояний. Если попытаться устранить требование, что 2 представляет собой системное множество с двумя блоками с определениями, касающимися соотношений Т [щ, и Win для получения уменьшенной зависимости множества переменных у, то мы встретимся с затруднениями. Соотношения W {яу, Яг) и W 4) не означают, что W ((jti), л^), если мы устраним требование, что т должно быть разбиением, содержащим два блока, для W (я, т). Это положение иллюстрируется таблицей представленной на рис. 5.26. Если Я1 = (12, 34), Я2 = (13,24), % = = (14,23), ToW(jti, Яз) и Г(я лг), но не удовлетворяется W (я Яз Яз)). Следовательно, соотношение W становится достаточным, но не необходимым условием для уменьшенной зависимости, использующей /?5-триггеры.

Для соотношения ГГ(я,. яз), если системное множество л^ не ограничивается системным множеством с двумя блоками и если

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

Однако при современном уровне технологии цепи обратной связи чрезвычайно редко оказываются доступными, если они не являются также выходными линиями цепи. Кроме того, дополнительное введение цепи прерывания увеличивает общую стоимость цепи, так же как увеличение количества возможных ошибок, и тем самым усложняет задачу тестирования цепи. Таким образом, если применять вышеуказанную стратегию тестирования, то желательные цели должны заключаться в том, чтобы: 1) минимизировать число ветвей, которые должны быть прерваны, что в свою очередь ведет к минимальному числу требуемых проверяемых цепей, и 2) минимизировать число сигналов, которые не поступают на выход и к которым требуется обеспечить доступ. Если заданная таблица состояний может быть реализована с помощью выходной функции, как, например, только обратной связи, то такая реализация должна удовлетворять второй цели. Этот случай будет рассмотрен ниже. Если в качестве обратной связи используются сигналы, которые не поступают на выход, то обе эти цели соответствуют реализации заданной таблицы состояний с минимальной обратной связью.

5.6.1. цепи без обратной связи

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