Файл: Баранов, С. И. Синтез микропрограммных автоматов.pdf

8.Дополнить коды состояний автомата одним неопределенным раз­ рядом. Увеличить /• на единицу. Переход к п. 4.

9.Пара переходов (ат, as), (ак, о;) развязана. Конец.

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

Проиллюстрируем алгоритм противогоночного кодирования на примере автомата, функция переходов которого задана табл. 3-1.

Очевидно, что пары должны быть развязаны в каждом из массивов пере­ ходов Ми М2, Л-13, происходящих под действием сигналов zu z2, z3.

Развязывание пар переходов в Mx начнем с первого перехода (alt а2). Со­ гласно сформулированной выше теореме пару (сц, а2) и (а2, а2) развязывать не надо из-за совпадения состояний перехода. Первая пара переходов, которая подлежит развязыванию, есть (аЛ, о2), (о3, о4). Вводим переменную тх и образуем по этой переменной четверку (ООП) для состояний аЛ, а2, а3,а4. Рассматривае­ мая пара переходов развязана (табл. 3-2).

Паре переходов (оц, а2), (а4, а4) соответствует четверка (ООН) (см. табл. 3-2), т е. эта пара тоже развязана.

Пара (oj, а2), (о5, а0) образует четверку (00------). Для развязывания этой пары доопределим эту четверку до (ООП), для чего состояниям а5, а0 ставим в со­ ответствие тх = 1 (табл. 3-3).

44

а,

Из табл. 3-3 видно, что пара (ctj, а.,), (л0, а6) развязана [(четверка (ООП)]. Точно так же развязаны пары, образованные переходом (а.,, а.,) н всеми после­ дующими переходами в М г. Обратимся к паре (а3, а.{), (ог,, о0). Из табл. 3-3 по­ лучаем соответствующую четверку (1111) — пара не развязана. Вводим пере­ менную т2 и полагаем для а3 и аАзначение т2 = 0, а для аъи аат2 = 1 (табл. 3-4).

45

Оказывается, что пара (аъ о2), (яГ), ав) не развязана, в связи с чем добавляем переменную т5 и развязываем эту пару (табл. 3-8).

Все остальные пары развязаны. Далее исключаем переменную т„ и полу­ чаем табл. 3-9 с тремя переменными т3, т4, тГ), в которой после проверки оказы­ ваются развязанными все пары.

Дальнейшая минимизация невозможна, так как для кодиро-' ваимя семи состояний нужно не менее трех переменных. После доопределения прочерков в табл. 3-9 получаем табл. 3-10 протнво­ гоночного кодирования состояний исходного автомата.

ния, связанные дугой на графе автомата, кодируются наборами, отлича­ ющимися состояниями лишь одного элемента памяти. Существует несколько алгоритмов соседнего кодирования, один из которых приве­ ден в [10].

Соседнее кодирование, однако, не всегда возможно. В работе [14] сформулированы требования к графу автомата, допускающего сосед­ нее кодирование:

1..В графе автомата не должно быть циклов с нечетным числом вершин.

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

На рис. 3-3 приведены два графа, которые не удовлетворяют этим требованиям и не могут быть закодированы соседними кодами.

46

3-3. Кодирование состояний и сложность комбинационной схемы

Анализ канонического метода показывает, что различные варианты кодирования состояний автомата приводят к различным выражениям функций возбуждения памяти и функций выходов, в результате чего -оказывается, что сложность комбинационной схемы автомата сущест­ венно зависит от выбранного кодирования. Проиллюстрируем это синтезом на задержках абстрактного автомата 5, таблица переходов которого представлена в табл. 2-4. В рассмотренном во второй главе примере (табл. 2-15) состояния автомата 5 были закодированы следую­ щим образом: К (ах) = 00; К (а2) = 01; К (а3) = 1 1 . В результате синтеза функции возбуждения, приведенные в (2-5), имели вид:

стрелок, входящих в ат при графическом способе задания автомата).

доченном в п. 2 списке кодируются кодами (00 . . . 01), (00 . . . 10), . . . , (10 . . . 00). ѵ

5. Для кодирования следующих I из оставшихся М —/ —1 состоя­ ний используются все коды, содержащие две единицы, затем 3 единицы и т . д., до тех пор пока все состояния не будут закодированы. В ре­ зультате получаем такое кодирование, при котором чем больше имеется переходов в некоторое состояние, тем меньше единиц содержится в его коде.

47