Горбатов В.А. Фундаментальные Основы Дискретной Математики. Информационная Математика
Подождите немного. Документ загружается.
§ 4.5. Кодирование внутренних состояний 301
ох собственно семантической таблицы расположим таблицу ци
клов четной длины. Согласно структуре запрещенных фигур вло
жения графа в гиперкуб для соседнего кодирования внутренних
состояний автомата необходимо, чтобы покрытие семантической
таблицы было сформировано с учетом принципа четности: каждое
покрытие включает четное число ребер, принадлежащих каждому
циклу четной длины и нечетное число ребер, принадлежащих ка
ждому циклу нечетной длины. Эта таблица имеет 28 покрытий:
(а + Ь + с) • (d + е + к) ■ (д + А; + т) • (а + b + d + / + д) х
х (a + b + e + f + m)-(c + d + f + k + m)-(c + d + e + f + g + m) —
= adg + bdg + cgdf + aegf + begf + ceg + akc + adk + ake +
-f- akg + акт -f akf + bck + bdk + bek -f bkg -f bkm + bkf -f deck +
-f- dmck -f ckf -f ckgm + adm -f bdm -f- cdm + aem -f bem -f cemf.
Оценим покрытия. Первому покрытию {a, d, д} соответствует
указываю-
0 2 2 2
fi
1 1 1 3 1 1 2вектор
щий частоту вхождения элементов покрытия в разрешенные и
запрещенные фигуры.
Спектр частот удовлетворяет критерию вложимости графа в
гиперкуб. Следовательно, первое покрытие порождает граф
(рис. 4.27,6), гомеоморфный заданному, вложимый в гиперкуб и
имеющий на три вершины больше, чем исходный граф переходов.
Аналогичная проверка остальных 27 покрытий не улучшает реше
ние, полученное по первому покрытию. Следовательно, введение
трех неустойчивых состояний, Sa, Sp, Sy, на переходах Si —> S2,
S2 —> S4, S4 —> Ss позволяет закодировать граф переходов сосед
ними кодами минимальным образом:
Si — 10 10 , S2 — 0000, S3 — 00 10, S4 — 0101, Ss — 0 110 ,
S6 — 0100, Sa — 1000, Sp — 00 01, Ry — 0111.
Граф, гомеоморфный графу переходов (рис. 4.27, а) с введен
ными неустойчивыми состояниями и соседними кодами, предста
влен на рис. 4.27, в.
П ример 4.5. Рассмотрим соседнее кодирование еще одного автомата, за
данного графом переходов G (рис. 4.28, а). Удаляя веса иа дугах и петли, снимая
ориентацию дуг, объединяя параллельные ребра (рис. 4.29, а), находим, что граф
содержит запрещенные фигуры Qi и Qi (рис. 4.29, б)\
Qi(Vu Ux), Vi = {Si/ i = 1, 2, ..., 9},
Ui — {{Si, S3}, {Si, Ss}, {Si, S»}, {Sa, S3}, {Sa, S6}, {Sj, S7},
{S3, Se}, {S<, S5}, {S*, S«}, {S4, S7}, {S«, Sg}, {Sa, Sg}};
Qa(Va, U2), Fa = {Si, S3, S5, S«, Se},
u2 = {{St, S3}, {Si, Ss}, {Si, S.}, {S3, Sg}, {Ss, Se}, {Sg, Sg}}.
302 Гл. 4. Теория формальных грамматик и автоматов
Для их устранения достаточно расщепить одно из ребер, вошедших в пере
сечение этих запрещенных фигур, двумя вершинами (взедение одной вершины
на ребро порождает иовую запрещенную фигуру — цикл нечетной длины). Для
определенности расщепляем ребро {5в, 5д} введением двух неустойчивых состоя
ний, 5а , Sp. В результате получаем граф G, гомеоморфный заданному графу
Рис. 4.28
§4.5. Кодирование внутренних состояний
303
переходов G и вложимый в гиперкуб (см. рис. 4.28,6):
S i — ОНО, Sj — 0 1 0 1 , S 3 — 0 1 1 1, Si — 00 0 0 ,
Ss — 0010, Se — 0001, SV — 0100, St — 1110,
Sg — 0011, Sa — 1010, Sp — 1011.
Зная структуры запрещенных фигур соседнего кодирования
и используя локальные характеристики графа G, мощности мно
жеств вершин |У| и ребер |J7|, плотность графа p(G) и его степень
s(G), предложим алгоритм фактического вложения графа перехо
дов в гиперкуб. По характеристикам графа |F|, \U\, p(G), s(G)
определяем вид запрещенных фигур, которые могут содержаться в
заданном графе переходов и по структуре которых можно оценить
количество вводимых неустойчивых состояний.
У тверж ден и е. Размерность гиперкуба, в который вкла
дывается граф, гомеоморфный графу переходов G, не меньше
степени s((S) графа G.
Используя это утверждение, предложим приближенный алго
ритм соседнего кодирования.
Перед проведением соседнего кодирования введем понятие ок
рестности радиуса R вершины и,.
Окрестностью радиуса R вершины v называется множество
вершин {и,}, для каждой из которых минимальная длина цепи
[и, ..., и,] равна R.
Предлагаемый алгоритм соседнего кодирования состоит из сле
дующих шагов.
1. В графе переходов G находим вершину v0 максимальной
степени smax> причем при подсчете степени вершин параллельные
ребра, т. е. ребра, имеющие одинаковые концы, различные между
собой, условно считаем за одно ребро; петли графа переходов при
подсчете s(v) не учитываем. В дальнейшем будем называть най
денную вершину Vq центром соседнего кодирования. Центр со
седнего кодирования г?о образует окрестность радиуса R (R — 0)
вершины v0. Кодируем произвольным образом вершину v0.
2. Рассматриваем окрестность радиуса Д на 1 больше, чем ра
диус предыдущей закодированной окрестности.
При рассмотрении вершин окрестности радиуса R возможны
три случая, когда необходимо вводить дополнительные вершины,
соответствующие неустойчивым состояниям автомата:
а) к вершин рассматриваемой окрестности попарно смежны,
т. е. образуют полный подграф. В каждое ребро этого полного
подграфа помещаем дополнительную вершину;
б) имеется вершина va, которая смежна с т (т > R, R — ра
диус рассматриваемой окрестности) вершинами окрестности ра
диуса R — 1. В этом случае на каждое из rn — R ребер, выбранных
произвольным образом и соединяющих вершину va с вершинами
окрестности радиуса R — 1, помещаем дополнительную вершину;
304
Гл. 4. Теория формальных грамматик и автоматов
в) число вершин Nr рассматриваемой окрестности радиуса R
больше числа сочетаний из s(G) по R,
где № ) — число вершин s(G)-MepHoro куба, коды которых отли
чаются в R разрядах от кода центра соседнего кодирования. Тогда
введением дополнительных вершин, смежных с одной стороны с
Рис. 4.30
вершинами окрестности радиуса R — 1 и с другой стороны с вер
шинами, наличие которых обусловливает выполнение неравенства
переводим избыток вершин в окрестность радиуса R +1 так, что
бы число вершин окрестности радиуса не превосходило
jj 4.6. Построение выходных функций 305
После введения дополнительных вершин согласно пп. а)-в)
Производим соседнее кодирование вершин окрестности радиуса R.
3. Увеличиваем радиус рассматриваемой окрестности на 1 и пе
реходим к п. 2), и так до тех пор, пока не получим искомое соседнее
кодирование внутренних состояний автомата. При выполнении
п. 2) может возникнуть ситуация, когда размерности гиперкуба не
хватает. В этом случае размерность увеличиваем на 1 и переходим
к п. 1).
Проиллюстрируем этот алгоритм кодированием вершин графа переходов G
(рис. 4.28, а).
Находим вершины максимальной степени. Таких вершин в графе две, S\
и Sg, степень равна 4. За центр соседнего кодирования выбираем эти вершины
по очереди. Сначала выбираем вершину Sx и присваиваем ей код 0000. Тогда
вершины S7, S3, Ss, St образуют окрестность радиуса R = 1 (рис. 4.30,а).
Условия пп. а)-в) для этой окрестности не выполняются, следовательно, имеется
соседнее кодирование. Оно следующее:
S7 — 0001, S3 — 0010, Si — 0100, Si — 1000.
Окрестность радиуса R = 2 образуют вершины Si, Sg, 5*. При кодирова
нии вершин этой окрестности получаем противоречие, соответствующее переходу
St —¥ Sg.
Расстояние по Хэммингу между кодами этих вершин равно 3, следовательно,
введением двух неустойчивых состояний, Sa и Sp, согласуют этот переход. Вво
димая вершина Sp принадлежит окрестности радиуса R = 3, в нее же входит
И вершина Se. В результате получаем коды остальных состояний Sg, S< и
вновь введенных Sa я Sp:
S2 — ООН, Si — 0101, S9 — ОНО, Sa — 1100, Sp — 1110.
При выборе в качестве центра соседнего кодирования вершины Sg, действуя
по этому алгоритму, получаем (рис. 4.30,5) противоречие при переходах Si —► Sj
и St -4 S i. Для устранения этих противоречий необходимо ввести четыре не
устойчивых состояния: Sa, Sb, Sc, Sd. Соседние коды этого способа кодирования
имеют следующий вид;
Si — 1001, S2 — 0101, S3 — 0001, Si — 0110, S5 — 0011,
Se — 0100, S7 — 0 111, S* — 1000, Sg — 0000, S« — 1101,
Sb — 1111, Sc — 1010, Sd — 10 11.
§ 4.6. Построение выходных функций
и функций возбуждения памяти автомата
После абстрактной оптимизации и кодирования внутренних со
стояний автомата автоматный оператор задается системой функ
ций возбуждения и выходных функций. Перед построением этой
системы рассмотрим элементы памяти; триггер с раздельными
входами и триггер со счетным входом.
Триггером с раздельными входами называется автомат, таб
лица состояний и граф переходов которого имеют соответственно
вид табл. 4.9. и рис. 4.31, а.
Рассмотрим реализацию триггера с раздельными входами в
импликативном базисе {-», 0}. Используя метод прямого моде
лирования, получаем
A t+ r == ($t —> £Нулt)
306
Гл. 4. Теория формальных грамматик и автоматов
и ее реализация в имппикативном базисе представлена на
рис. 4.32. Постоянная времени т определяется задержкой сигнала
от входов к выходу в схеме триггера.
Таблица 4.9
*^нул
Рис. 4.31
Яед t
Хну л t St
$t+r
0 0
0 0
0
0
1 1
0 1
0 0
0 1
1 0
1 0
0
1
1 0
1 1
1 1
0
—
1 1 1
-
Триггером со счетным входом называется автомат, таблица
состояний и граф переходов которого имеют соответственно вид
Таблица 4.10
Хсч t St
3t+r
0
0 0
0
1 1
1
0
1
1 1
0
Рис. 4.32
табл. 4.10 и рис. 4.31, <Г. Согласно табл. 4.10 функция триггера со
счетным входом имеет вид
St+T (г сч<> ®t) = XC4fSf V Xc4fSt.
Возбуждение счетного входа переводит триггер в противоположное
состояние. Читателю в качестве упражнения предлагается синте
зировать схему триггера со счетным входом в коимпликативном
базисе.
Рассмотрим построение выходных функций и функций возбу
ждения элементов памяти на примере закодированного автомата
(рис. 4.27). Для определенности в качестве элементов памяти возь
мем триггеры со счетным входом.
Каждый элемент памяти своим значением разбивает все мно
жество состояний на два класса (табл. 4.11).
Таблица 4.11
i
Zi = 0
Zi = 1
1
{Sj/ j = 2,3,4, 5,6,0,y}
{Sj/ j= l,ar}
2
{Sj/ j = 1,2,3,or,/?}
{Sj/ j = 4,5,6, 7}
3 {Sj/ j = 2,4,6,<*,/?}
{Sj/ j = 1,3,5,7}
4
{Sj/ j = 1, 2,3 ,5 ,6, <*}
{Sj/ j = 4 ,/5,7}
§4.6. Построение выходных функций
307
Для уменьшения функциональной связности функций возбуж
дения, используя разбиение множества состояний на классы, по
строим таблицы, указывающие условия переключения элементов
памяти (табл. 4.12).
Таблица 4.12
z\
2Г
z^ = 0
4 = 1
4 = 0
0,2,3
(4
И
t—»
6
7
г 2
4
4 = o
4 = 1
4 = 0
о, 3,6,7,-
0,-
4 = 1
5
4,5,7,-
2Ъ
4
Л
II
о
4 = 1
4 = 0
0, 2,4,5,—
4
zt = 1
7 0,6,-
Zt
4
**
* 1
II
О
4 = 1
2+ = 0
0,2,3,4,5,6,7, —
0
4 = 1
5,-
4,-
Анализ построенных таблиц показывает, что функция возбуж
дения первого элемента памяти зависит от входного вектора и
состояния этого элемента. Таблица переходов второго элемента
памяти противоречива, так как переходы 0 —► 0 и 0 -> 1 проис
ходят при одном и том же значении входного вектора, равном 0,
И переходы 1 —> '0 и 1 -> 1 — при значении входного вектора,
равном 5.
-.j Недетерминированность переходов имеет место в таблицах, со
ответствующих третьему и четвертому элементам памяти: в треть
ей таблице переходы 0 -* 0 и 0 -+ 1 происходят при одном и том же
Значении входного вектора, равном 4, в четвертой таблице— пере
ходы 0 —^ 0 и 0 —^ 1 — при векторе, равном 0. Условия переходов,
'Обозначенные в таблицах прочерком, соответствуют переходам из
Неустойчивых состояний Sa, Sp, Sy, и для устранения недетерми
нированности при этих переходах необходимо учитывать состоя
ния всех элементов памяти. Для определения минимального ко
личества элементов памяти, состояния которых необходимо учи
тывать при ликвидации противоречивых переходов, вызванных
Одним и тем же значением входного вектора в строках таблиц,
Построим табл. 4.13.
308
Гл. 4. Теория формальных грамматик и автоматов
Таблица 4.13
X i
Z2
Z3 Z4
{5а Sp, S3 -*■ S5}
-+ 5g, 5в }
{ -*■ S-y, 5* -*■ 5в }
{^2 -+ Sp , S3 -¥ Sj }
0
1
0
0 1
4
0
0
1 0
5
0
1
0 0
Первые два столбца таблицы соответствуют противоречивым
переходам при переключении второго элемента памяти, осталь
ные два — при переключении третьего и четвертого элементов.
Для устранения этих противоречий достаточно входной вектор 0
расширить внутренней переменной z£ (так как этой переменной
различаются коды состояний 5г, S3), векторы 4 и 5 расширить
внутренней переменной z\ (так как коды состояний S4, Se разли
чаются переменной г*).
Окончательно функции возбуждения элементов памяти имеют
следующий вид: _
zf) = zjxix2x3,
4>Tl(X, Z+, Z+, Z$, Z+) = zf Х{Х2Х3 V Z2+ (X!X2X3Z^ V zfz3+ z+),
<p3(X, 23+, 2 + ) = Z^XiX2X3 V z3+ XlX2X3Z4+,
<^4(X, Z+, z|, z3+, z+) = Z|(X!X2X3 V zfz\z^) V z4+x ix 2x3z3+.
Полученная система функций возбуждения может быть еще бо
лее упрощена, если учесть, что булевы функции, описывающие
работу рассматриваемого автомата, являются частично определен
ными. Рассмотрим это упрощение на примере второй выходной
функции. Рабочая и запрещенная область булевых функций авто
мата определяются его переходами. В рассматриваемом автомате
имеем 14 переходов, которые определяют табл. 4.14.
Таблица 4.14
Sj —> Sj
XI
X2
*3
4 *2 *}
yi
У2
S\
—f So 1
1
1
1
0 1
0
0
0
Si —> S3
1
1 0 1
0 1
0
0 1
Sj - V S2
0
1
0
0
0
0
0
1 1
S2 ~> S/s
0
0
0
0
0
0
0 1 0
S2 -¥ S3
0 1
1
0
0 0
0
1 0
S2 —¥ Ss
0
0
0 0 0 1
0 1
1
S< —> S-y 1 0
0 0 1 0
1
1
0
S< —> Se 1
0
1 0 1 0
1
1 0
S5 —¥ St
1
1
1
0 1 1
0 0
1
Sg —> S2 1
0
1
0
1 0
0
0 0
S* —> Sg 1
0 0 0 1 0
0 1
0
Sa ~¥ S2
— —
—
1
0
0
0
- -
S(j —> S4
— —
—
0 0 0
1 - -
S-, —> Ss
- -
-
0 1
1
1 —
—
§4.6. Построение выходных функций 309
Из 128 точек 7-мерного куба выходная функция у2 определена
на 11 точках, из них на 4 она принимает единичное значение
(рабочая область функции), на остальных 7 — нулевое значение
(запрещенная область функции).
Используя таблицу различий (табл. 4.15), выделим пучки мак
симальных интервалов для каждой точки рабочей области.
Таблица 4.15
Точки работай
области
1111010 00 00000 0110000
1000101 1010101 1010100 1000100
1 0
1
1 0 0 0 0
1 0 1
0 1
1
1 1
0
1 0
1 0 1 1
0
1 0 1
1 1 1
1 1
0 0 0
0
1 0
1 1
1 0
1 1
1
1
1 1
0
0 0
0 1 1 0 0
0 1
0
0 1 1
1
1
1
0 1
0 1 1 1 1
0
1 0
1 0 1
1
0
О 1 0
0 0 0
0 0
0 0 0
0 1 1
1 1
0
1 0 0 0
0 0
0
0
0 0 0 1 1
0
0
0
1 0
0 1 1
1
1
0
1 0
1
0 0
0
0
0 1 0
1 0
1
1 0
0 1 0
0 0 0 0 0
0
0
0
0 1 1 1 1
1
0 1
1 1
1
1
1
0
0 0 0
1
1
0
0
1
0 1
1
0 0
0
0
1
0 1
0
1 1
1 1
1 0 1
0 1 0
0
1
0
1 0
0
0 0
0 0
1 1
1
1
0 0 0 0
1
0 1
1 1
1
1 1
0 0 0
0 1 1
0
0
В результате сжатия таблиц различий и их покрытия получаем,
что первая рабочая точка 1101010 содержится в максимальных ин
тервалах — 01
------
, — 0— 1-, вторая точка 0100000 содержится
в -10
--------
, третья точка 0000010 — в — 0— 1—, четвертая точка
1110110 — в
---------
11-.
Следовательно, выходная функция уг{Х, Z+) имеет следую
щий вид:
у2(Х, Z+) - z£ (*2 V z%) V х2х3.
Минимизация булевой функции была проведена без учета пере
ходов из неустойчивых состояний. В зависимости от назначения
управляющего автомата и физического представления 1 и 0 вход
ные векторы Z+, соответствующие неустойчивым состояниям, от
310
Гл. 4. Теория формальных грамматик и автоматов
носят в запрещенную область при минимизации логического выра
жения, описывающего условия истинности единичного значения
минимизируемой булевой функции, или в запрещенные области
при минимизации логических выражений, описывающих усло
вия истинности единичного и нулевого значения булевой функции.
Для учета переходов, соответствующих неустойчивым состояниям,
необходимо проанализировать в упрощенном логическом выраже
нии конъюнкции, состоящие только из внутренних переменных
z f, и если эта конъюнкция обращает на неустойчивых переходах
логическое выражение в 1, то приписываем отрицания внутрен
них переменных, кодирующих неустойчивые состояния, с целью
устранения истинности на этой конъюнкции.
В нашем случае необходимо к конъюнкции z% z£ приписать
отрицание внутренней переменной zf, так как у2 = 1 при не
устойчивом переходе из состояния Sy.
Если относить входные векторы, соответствующие неустойчи
вым состояниям, в запрещенные области до покрытия таблиц раз
личий, то в общем случае, как нетрудно показать, будет усложне
ние окончательного логического выражения.
В рассматриваемом случае итоговое выражение для у2{Х, Z+)
имеет вид
у2(Х} Z+) = zf (х3 V z+z+) V х2х3.
Определение упрощенного вида первой выходной функции ос
тавляем читателю в качестве упражнения.
§ 4.7. Синтез логических структур
в топологических базисах
Рассмотрим проектирование логической схемы как синтез со
ответствующего булева графа. Разобьем все множество базисов на
три класса: топологические, функциональные, нейронные.
В топологических базисах полнота используемых при синтезе
функций достигается соответствующим физическим моделирова
нием двоичных переменных и определенным соединением задан
ных элементов. Такие базисы образуют все ключевые элементы,
токовые ключи, криотроны, переключатели света, спейсисторы,
деплисторы, унитроны и другие вентильные элементы, которые
используются в вычислительной технике как элементы с высоким
быстродействием.
В функциональных базисах элементы независимо от их соеди
нения и физического моделирования двоичных переменных реа
лизуют функции, образующие полную систему булевых функций.
К таким базисам относятся, например, элементы, которые реали
зуют функции Шеффера, Вебба, импликации и др. Нейронные
элементы обеспечивают полноту путем их индивидуализации.