Горбатов В.А. Фундаментальные Основы Дискретной Математики. Информационная Математика

Подождите немного. Документ загружается.

§4.4. Абстрактное проектирование автоматов 291

При восстановлении детерминированности автомата с помо

щью введения счетчиков возникает задача минимизации числа

счетчиков, которая сводится к задаче раскраски графа затира

ния G3T. Каждому счетчику взаимно однозначно сопоставляется

вершина графа G3T: две вершины графа G3T смежны, если под

графы работы соответствующих счетчиков имеют хотя бы одну об

щую вершину (подграф Ga является подграфом работы счетчика

а, если для реализации в этом подграфе правильных переходов

необходимо знать состояние счетчика а).

Для рассматриваемого случая счетчикам СчЦ, СчДЦ, Сч(5а) и Сч(5^)

соответствуют подграфы, носители которых имеют соответственно следующий

вид: {Sc, Sd}, {S2, Sc, Sd, Sa SpS23}, {£„} и {Sp}. Граф затирания G3T для

рассматриваемого случая изображен иа рис. 4.21, в.

Очевидно, два счетчика, соответствующие несмежным верши

нам в графе затирания, можно рассматривать как один физиче

ский счетчик, так как не найдется ни одного состояния, в котором

для правильного функционирования автомата необходимо было бы

знать состояние обоих счетчиков. Таким образом, минимизация

числа счетчиков сводится к раскраске вершин графов затирания.

292

Гл. 4. Теория формальных грамматик и автоматов

В данном случае согласно минимальной раскраске вершин графа затира

ния (рис. 4.21, в) достаточно наличия двух счетчиков: счетчика СчДц и счет

чика СчЦК, который включается в моменты работы счетчиков СчЦ, Cu(Sa)

и Сч(5,в) (рис. 4.21,г).

Применение счетчиков в цепи обратной связи автоматов управ

ления позволяет использовать стандартные узлы ЭВМ, выполнен

ные в виде интегральных микросхем.

В результате поиска оптимальной декомпозиции автоматов по

лучаем несколько эквивалентных вариантов, из которых выбираем

окончательный вариант, имеющий минимальное значение p(GM):

( - )

где \U\ — количество слов в мографе, каждое из которых соот

ветствует автоматному переходу и представляет собой X S +S~Y;

I — число букв (термов), образующих слово X S +S~Y; под внеш

ним знаком ^2 находится выражение, являющееся средним значе

нием производной dGM/dS , вычисленной на парах букв, образую

щих слово X S +S~Y. Этому варианту соответствует более простая

структурная реализация.

§ 4.5. Кодирование внутренних состояний

На этапе кодирования внутренних состояний отображение

X S +S~Y, полученное на этапе абстрактного проектирования, пре

образуется в отображение X Z + —► Z~Y, где S+, S~ — идентифи

каторы внутренних состояний, рассматриваемых соответственно

в моменты времени t и t + г; Z+, Z~ — коды этих состояний,

элементами которых являются буквы используемого структурного

алфавита; для случая булевой логики это 0 и 1.

Кодирование внутренних состояний автомата можно осуще

ствлять, исходя из требований уменьшения аппаратурных затрат

либо увеличения надежности функционирования автомата, либо

удовлетворения обоих требований одновременно.

Рассмотрим метод кодирования, удовлетворяющий первому

требованию. Число способов кодирования N вершин графа пе

реходов G = (V, U.) увеличивается с ростом |V| как

(2Р°*21^1) - 1)!

N = (2tlo«2l^l] - |У|)! ([log2 |V |])!’ (4'9)

где [ ] — ближайшее целое число.

Каждый способ кодирования определяет свои аппаратурные за

траты при реализации автомата.

§4.5. Кодирование внутренних состояний 293

Наиболее интересным является метод кодирования с исполь

зованием подстановочных разбиений, предложенный Хартмани-

сом и Стирнсом. Это метод основан на уменьшении функциональ

ной зависимости функций возбуждения. К сожалению, при ко

дировании состояний реальных автоматов метод подстановочных

разбиений неприменим, так как он не обладает свойством подста

новочных разбиений.

Рассмотрим частотно-матричный метод кодирования со

стояний. Пусть в результате абстрактного синтеза был построен

мограф, определяющий отображение X S + —У S~Y. После коди

рования получим мограф, задающий отображение X Z + —*■ Z~Y,

т. е. в первоначальном мографе вершины, соответствующие иден

тификаторам внутренних состояний 5,-, будут заменены полными

подграфами, соответствующими кодам Z,- внутренних состояний.

Данный метод кодирования можно реализовать с помощью следую

щего алгоритма синтеза кодирующего дерева.

1. Строим двумерную матрицу Q = [g,j], каждой строке ко

торой взаимно однозначно соответствует микрооперация или зна

чение входного канала (элементы вектора У или X), столбцу —

внутреннее состояние:

' 1, если первичный терм, соответствующий г-й строке,

_ I входит в каждую пару векторов (X, У )(^ У), ко-

~ торые взвешивают дуги, исходящие из вершины j,

„ 0 в противном случае.

Каждому внутреннему состоянию (столбцу матрицы) взаимно

однозначно сопоставляем произвольным образом максимальную

вершину синтезируемого кодирующего дерева. Полагаем Q = Q.

2. По матрице Q находим частотную матрицу отношений F =

= QT-Q.

3. Вычислим значения производной от модели, заданной ма

трицей Q.

4. Выбираем пару внутренних состояний, для которой вычи

сленное значение производной минимально.

5. Выбранную пару состояний вычеркиваем и ставим ей в со

ответствие в кодирующем дереве вершину, являющуюся началом

дуг, концами которых являются выбранные состояния. Постро

енной вершине взаимно однозначно сопоставляем столбец строя

щейся матрицы Qc, равный векторному произведению столбцов

матрицы Q, соответствующих выбранным вершинам.

6. Проверяем, остались или нет нерассмотренные внутренние

состояния, для которых вычислялись значения производной. Ес

ли да, то переходим к п. 4, в противном случае — к п. 7.

7. Проверяем, образована ли матрица Qc. Если да, то полагаем

Qc = Q и переходим к п. 2, в противном случае — к п. 8.

294

_______

Гл. 4. Теория формальных грамматик и автоматов

8. Каждым двум дугам, исходящим из вершины построенного

дерева, начиная с дуг, исходящих из корня дерева, ставим в соот

ветствие 0 и 1.

Путь, соединяющий корень дерева и максимальный элемент,

взвешен кодом, который сопоставляется внутреннему состоянию,

соответствующему этому максимальному элементу дерева.

9. Конец.

Проиллюстрируем предлагаемый алгоритм на следующем при

мере.

Пример 4.2. Пусть в результате абстрактного синтеза был получен граф

переходов G (рис. 4.22, а).

Рис. 4.22

Используя предлагаемый алгоритм, закодируем внутренние состояния авто

мата. Матрица Q, соответствующая данному графу, имеет следующий вид:

Si S3

Si ss

0 0 1

1 1

1 0

0 0

0 1 1

0 0

1 1

1 0 0

У1

1 0

0 0

1 0

У2

0 0 1

У2

Частотная матрица отношений, соответствующая матрице Q, имеет следую

щий вид:

Ss s6

3 0

0 2

2 1

2 5 2

1 1

2 4

3 0

5 0

1 2

§4.5. Кодирование внутренних состояний

295

Вычисляем значения производной для каждой пары состояний:

■(Si,St ) =

/ 1 - 2/ 14+ и 3-21+4

dGM(Su Ss) = 3 2^ +-- = 0,67,

= 5,

dGM

(52, Si) =

2-2 + 5

= 1,5,

(52,5 « ) = 2 2 ; 1.+ 4 =4,

(S3 , St) =

(S3

5 - 2- 2 + 4

2,5,

5s)= 5-20 + 5 =8)

(S3 ,

(Si,

Ss)

4-2-1+5

= 7,

(Si, St) = — -V - 2 = 1.

Остальные значения производной равны оо. Производная (dGM/dS)(Si, Sj)

имеет минимальное значение на паре (Si, Ss). Этой паре состояний ставим в

соответствие “пересечение” соответствующих вершин строящегося дерева. Со

гласно алгоритму объединяем в пары состояния Si, Ss к Si, St. В результате

построим следующий ярус дерева.

Матрица Qc, соответствующая вершинам построенного яруса, имеет вид

Q c =

n Ss S2 n S3 S3 n St

1 0 0

0 1

0 0

0 0 0

0 0

У1

0 0

0 0 0

3/2

0 0

У2

Частотная матрица отношений, соответствующая матрице Qc, имеет следую

щий вид:

3 0 0

0 3 0

0 0 3

Значения производной равны оо.

Искомое кодирующе дерево изображено на рис. 4.22,6. Взвешиваем исходя

щие из каждой вершины дуги 0 и 1. Согласно построенному кодирующему де

реву имеем следующие коды внутренних состояний автомата: Si — 010, S2 —

100, Si — 101, Si — 110, Ss — Oil, Se — 111.

296

Гл. 4. Теория формальных грамматик и автоматов

Рассмотрим кодирование внутренних состояний автомата, ис

ходя из удовлетворения требований надежности. Функциониро

вание автомата может нарушаться в результате неодинаковой за

держки в реальной схеме, реализующей автомат из-за явления го

нок, сущность которого можно проиллюстрировать на следующем

примере (рис. 4.23). Пусть в рассматриваемый момент переключа

ются два триггера, А и В (событийное условие), причем функ

ция возбуждения <р одного из триггеров, например, В, содержит в

качестве одной из переменных значение

триггера А: <рв = <р(- • •, • • •) (функ

циональное условие); время задержки в

схемах возбуждения триггеров А к В

определяется неравенством Ава > *А

(Лва — время, в течение которого необ

ходимо наличие “старого” значения триг

гера А в схеме возбуждения триггера В;

Ьа — время задержки сигнала возбужде

ния триггера А) (временное условие).

При выполнении этих трех условий

значение триггера будет вычислено не

правильно (так как для правильного вы

числения значения триггера В необхо

димо, чтобы триггер А сохранял свое

“старое” значение по крайней мере в те

чение времени 3г (после начала перехода

автомата), а триггер А “обновляет” свое значение через т). Это —

так называемое явление гонок. При наличии гонок автомат пе

реходит не в то состояние, которое указано при данном переходе,

что приводит к нарушению автоматного соответствия.

Гонки можно устранить, нарушив одно из трех условий гонок.

Для того чтобы нарушить временное условие, т. е. чтобы выпол

нялось неравенство Aba < ^Ai необходимо иметь схемы возбужде

ния триггеров А и В для определения А в а ^^а - Эти схемы будут

получены только на этапе структурного синтеза, для проведения

которого необходимы результаты кодирования внутренних состоя

ний. Следовательно, при логическом устранении гонок нарушение

этого условия неосуществимо. Технически третье условие можно

нарушить, вводя второй каскад элементов обратной связи или с

помощью синхронного выполнения схемы автомата.

Второе условие наличия гонок, т.е. условие <рв = <р(- • »• ■ •)>

можно нарушить функциональным развязыванием элементов па

мяти, например применяя подстановочные разбиения.

Первое условие (переключение двух и более элементов памяти

при одном переходе автомата) нарушается, если при любом пе

реходе автомата переключается только один элемент памяти. Это

означает: каждому внутреннему состоянию автомата сопоставляет

§4.5. Кодирование внутренних состояний

297

ся такой код, что если существует переход из состояния 5,- в со

стояние Sj (S{ ф Sj), то соответствующие им коды отличаются

только в одном разряде. Другими словами, при реализации ав

томата гонки отсутствуют, если соответствующий граф переходов

можно расположить в n-мерном гиперкубе так, чтобы переходы

из состояния Si в состояние Sj (5,- ф Sj) осуществлялись только

по ребрам гиперкуба и коды соответствующих вершин гиперкуба

были сопоставлены вершинам графа переходов. Такое кодирова

ние называется соседним.

Будем говорить, что для графа переходов возможно соседнее

кодирование кодами длины п, если он вложим в n-мерный куб.

Приведем условие вложимости графа переходов в гиперкуб.

Из анализа гиперкуба следует, что если хроматическое число

h(G) графа переходов G (без учета дуг, являющихся петлями)

больше 2, то для такого графа переходов не существует соседнего

кодирования. Таким образом, чтобы граф переходов G имел со

седнее кодирование, требуется, чтобы он не содержал циклы не

четной длины. Если же он их содержит, то необходимо устранить

все циклы нечетной длины, вводя дополнительные внутренние со

стояния, в которых не реализуется отображение X -> Y. Эти

состояния называют неустойчивыми внутренними состояниями.

Рассмотрим точный алгоритм соседнего кодирования, основан

ный на учете запрещенных фигур, характеризующих вложимость

кодируемого графа в гиперкуб.

Пример 4.3. Пусть задан граф переходов автомата (рис. 4.24), который изо

бражен без отображений X Y, петель, кратных дуг и ориентации (поскольку

это несущественно при решении задачи соседнего кодирования). В соответствии

с выведенными ранее условиями, чтобы соседнее кодирование было возможно,

необходимо и достаточно, чтобы граф ие содержал запрещенных подграфов. При

проектировании автомата необходимо так преобразовать эти графы, чтобы все

они стали вложимыми. Данное преобразование не нарушает функционирования

автомата только в том случае, если каждый новый граф гомеоморфеи предше

ствующему. Практически преобразование сводится к добавлению новых вершин

в некоторые ребра каждого запрещенного графа, являющегося подграфом дан

ного графа переходов. Этим самым вводим неустойчивые внутренние состояния

автомата. При оптимальном проектировании число вводимых неустойчивых со

стояний должно быть минимальным.

298

______Гл. 4. Теория формальных грамматик и автоматов

Таблица 4.7

R i

R 3

Ri Rb

Re Rr

h = {t»l, U2} 1

0 0

0 0 0

h = { f 2, « 3}

0 0

/3 = { и з , « л }

1 1

0 0

0 0 0

li = {t>4, f s }

0 0

/5 = {t>5, « б }

0 0

h = {t»i, f e }

0 0

0 0 0

/7 = {tig, 1)7}

0 0

U = {t>7,

0 0

0 0 0

la = {U 3 ,U 9 >

1 1

0 0 0

ilo = {t>l, f e )

0 0

0 0 0

ill = { f e , l>lo}

0 0 0

0 0

il2 = {l>4 , N10}

0 0

il3 = {f9 , f l o }

0 1

il4 = {t>9, f u )

1 0

il5 = {flO , f i* }

. 0

0 1

0 0

1 1

il6 = {^ 10, « 14}

0 0

il7 = {flO , f l 7 }

1 1

il8 = { f l5 , f ie }

1 0

0 1

il9 = {l>3, f l l }

0 1

0 0

l2Q = { « 1 1 , f i e }

0 0

h i = { f 12, f i e }

l22 = {t>i2 , 1115}

0 1

l23 = {t>i3, f 14}

0 1

1 1

h i = { f 14, f i e }

0 1 1

0 1

h s = { f i s , t>ie}

0 0 1

h e = { fi3 , f i o }

0 0

0 1

h 7 = { f i 3 , « 1 7 }

0 1 1

Двухмерная таблица (табл. 4.7) распределения ребер по запрещенным фигу

рам (рис. 4.25) покрывается двумя строками {fi3, hi }• Добавляя между верши

нами 49, ию и V\2, t>i3 вершнны, соответствующие неустойчивым состояниям,

вкладываем полученный граф в булево пространство (рис. 4.26).

При введении дополнительных вершин в граф разрешенные фигуры (циклы

четной длины) не были нарушены.

Пример 4.4. Построим соседние коды для внутренних состояний автомата,

граф переходов которого изображение рис. 4.27, а. При вложении рассматриваем

граф без петель, без ориентации дуг и кратные ребра заменяем одним ребром. С

учетом этого кодируемый граф содержит запрещенные фигуры вида:

Qi = <Vi, Ui), V, = {5,, S2, S3}, [/, = {{5,, S2}, {5,, S3}, {S2, 53}};

C?2 = {V2, U2), V2 = {S2, Si, S6}, U2 = {{S2, Si}, {S2, S6}, {Si, 56}};

Q3 ={V3,U3), V3 = {Si,Ss,S*}, U3 = {{54, 5s], {54, S6}, {Ss, S6}};

Qi=(Vi,U i), V i= {S ,,S 2,S3,Si,Sb},

Ui = {{Si, S2}, {Su S3}, {S3, 5s}, {54, 5s}, {S2, 54}};

§ 4.5. Кодирование внутренних состояний

299

Qs = (Vs, Us), V s= {S1,S 2,S 3,S s,Se},

Us = {{5,, S2}, {Si, S3}, {S3, S5}, {S5, S6}, {S2, S6}};

Q* = (Vi, !/«>, Ve = {Sa,S3,S «,S,,ft},

U6 = {{S2, 5з } , { 53 , Ss}, {Ss, Se}, {S4, S6}, {S2, S<}};

Qt = (Vr, U7), Vj = {S2, S3, Si, Ss, Se},

U7 = {{S2, St}, {S2, S6}, {S2, S3}, {S4, Ss}, {S5, S6}, {S3, S5}}.

«i

R2:

«9 "ia

—

p ■ <p

------------0

0------------ b

-----------

— ==*0

^0 *^4

OOOOIO

000000

000100

Рис. 4.26

300

Гл. 4. Теория формальных грамматик и автоматов

(4,2»

(101,00) (100,10)

Разрешенными фигурами при вложении графа в гиперкуб являются циклы

четной длины вида:

Ri = (VJ, Ui), Vi = {Sj, S3, S4, S5},

Ui = {{S2, S^, {S2, S3}, {S3, Ss}, {Si, S5}};

R2 = (Vi, U2), Vj = {Sj, Si, Ss, Se},

U2 = {{S2, Si}, {Si, Ss}, {Ss, Se}, {S2, Se}};

Дз = {V3, Щ , Vk = {Sit S3, Ss, S5},

tfs = {{S2, S3}, {S3, S5}, {Ss, S6}, {S2, Se}};

Ri = {Vi,Ui), Vi ={Sifi = l, ...,6},

Di = {{Si, Si}, {Su S3}, {S3, Ss}, {S5, Se}, {S4, S6}, {S2, S<}}.

Таблицу, показывающую распределение компонент в запре

щенных и/или разрешенных фигурах, как и выше, будем назы

вать семантической.

Таблица 4.8

Й 1

я 2 Яз

Ребра

Q i

Q 3

Qs Qe Q r

0 1 а = {Si, S2}

1 0

0 1 Ь — {Si, S3 }

1 0

1 0 0

0 1

с = {S2, S3 } 1 0

1 1

1 d = {S2, S(}

1 0 1 0 1 1

1 1

e = {S2, Se}

0 1

1 0 1

0 1

/ = {S2, S5}

0 0

1 1 1

9 = {Si,Ss}

0 0

0 1

k = {Si,Se} 0

0 1

1 1

m = {Ss,S6}

0 1 0 1 1

Строим семантическую таблицу (табл. 4.8). При введении не

устойчивых состояний в графе переходов возможно преобразова

ние циклов четной длины в циклы нечетной длины, поэтому слева