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

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

§ 5.6. Семантическое ослабление функциональной связности 441

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

основе использования найденных запрещенных фигур QM и Q3,

которые соответствуют последовательному и параллельному мето

дам кодирования.

Последовательный метод проиллюстрируем кодированием гра

фа переходов G, представленного на рис. 5.29, а. Выше было най

дено кодирование по внутренней переменной z\. Для определе

ния кодов по второй переменной строим семантическую таблицу.

Столбцам первой подтаблицы взаимно однозначно соответствуют

запрещенные фигуры — циклы нечетной длины, строкам — пара

сцепленных состояний (ребро графа сцепления Gct,i) и на пересе

чении (г, j ) ставится 1, если *-е ребро входит в j -й цикл, 0 — в

противном случае. Представим эту подтаблицу в виде следующей

матрицы:

QmI Qm2

<Э*з

Q]*i QmS

Qm6 Qm7

0 0 0 0

1 1

{Si, S<}

0 0

1 {S<, S10}

1 1

{$!, Se}

0 0

{Se, S „ }.

0 0 1 0 0 0 0

{S 2, S5}

0 0 1

0 0

{s 2, s7}

0 0 0

{S t, S9}

0 0

0 1 {S 10, S12}

Минимальным покрытием является { { 54,5ю}, {Si, Se}, {S 2, S7}}.

Строкам второй подтаблицы взаимно однозначно соответству

ют пары сцепленных состояний, столбцам — входные векторы,

которыми они сцеплены, и на пересечении (i, j ) ставится 1, если

t-я пара сцеплена j-u входным вектором, и 0 в противном случае.

Представим эту подтаблицу в виде следующей матрицы:

1 2 3 4 5

0 0 0

{S i,S «}

0 0

1 0 0

{S*, S10}

0 0 0

{Su S6}

0 0 0

0 {Se, S „ }.

0 0

{S 2, Ss}

0 0 0

{S 2, S7}

0 0

{St, S9}

0 0

1 0 0 {S 10, Si2}

Покрытие {{S4, S10}, {Si, Se}, {S2, S7}} столбцами элементов

покрытия первой подтаблицы указывает, какие входные векторы

необходимо расширить для устранения недетерминированности

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

Такими входными векторами являются 2, 3, 5. После их расшире

ния, которое отметим штриховкой, исходный граф сцепления Gcui

442

Гл. 5. Прикладная теория алгоритмов

преобразуется в граф, представленный на рис. 5.37, а. Раскраши

вая этот граф двумя цветами, кодируем состояния по второй пе

ременной (рис. 5.37, а). После соединения ребром вершин, имею-

Рис. 5.37

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

случае образоваться не могут. Следовательно, существует коди

рование по третьей и четвертой переменным z$, z4 (рис. 5.37,6).

Окончательно коды с минимальной функциональной связностью

элементов памяти имеют следующий вид:

Si — 0001, S2 — ОНО, S3 — 0010, S4 — 1110,

S5 — 1001, S6 — 1010, S7 — 1100, S8 — 1101,

S9 — 0011, Sio — 0111, Su — 0101, Si2 — 1000.

Построим функции возбуждения элементов памяти (для опре

деленности — триггеров с раздельными входами) с соответствую

щей минимальной функциональной связностью.

Разбиение всего множества внутренних состояний на два под

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

табл. 5.15.

Таблица 5.15

zt = 1

Si, S2, S3, Sa, Sio, Su

S4,S5)Se,S7,Se)S12

Si, S3,5s, Se, S9, Su

S2, S4, S7, Sg, Sio, Sn

Si, Ss, S7, Se, Su, Su

2, S3, S4, Se, Sg, Sio

4 S2, S3, S4, Se, St, S12'

Si,Ss,Sg,S9,Sio,Sn

Согласно построенной таблице функции возбуждения единич

ных входов имеют вид

z f ) = zf(xix2xз V xix2x3 V xix2x3),

§5.6. Семантическое ослабление функциональной связности 443

<р12(Х, z + , Z?) -

____

= zf (Х1Х2Х3 V Х1Х2Х3 V Х1Х2Х3 V Х1Х2Х3zf V Х1Х2Х3),

<Р!3(Х, *з+) = z£{xix2x3 V Х1Х2Х3 V Х1Х2Х3 V * 1X2*3),

9 l4(X, z4+) = z/(XiX2*3 V X1X2X3 V X1X2X3 V Х!Х21з)-

Функции возбуждения нулевых входов имеют вид

<Poi(X, z+) = г^ ^ х гх з V хгх2хз V xix2x3 V х ^ х з ),

<Роз(Х, zf, zf) =

= z^ (xix2x3 V X1X2X3 V х!х2хзг^ V X1X2X3 V xix2x3),

<Р03{Х, Zg”) = Zg” (xix2x3 V xix2x3 V x ix2x3),

¥>04(^, zt ) = (Z1X2X3 V X1X2X3 V X1X2X3 V X1X2X3).

Введем понятие противоположных кодов. Два кода называ

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

Очевидно, что если сцепленным состояниям соответствуют

противоположные коды, то элементы памяти являются функ

ционально несвязными.

Рассмотрим противоположное кодирование на следующих при

мерах.

Пусть граф переходов G задан своей таблицей переходов

(табл. 5.16), каждой строке которой взаимно однозначно соответ

ствует входной вектор Xi, столб- Таблица 5.16

ду — внутреннее состояние Sj и

в клетке (*, j) указывается вну

треннее состояние, в которое ав

томат переходит при входном

воздействии Xi из состояния Sj.

Внутренние состояния Si, S2',

S2, S5; S3, S5; S3, Se; S5, S6 и

S4, Sg сцеплены соответственно

входными векторами 1, 1, 3, 4, 4 и 2. Матрица смежности графа

сцепления для заданного случая имеет вид, представленный в

табл. 5.17. Клетка (*, j ) таблицы содержит значения входных век

торов, которыми соответствующие состояния сцеплены.

Таблица 5.17

Внутренние

состояния

Si S3

Si 1

3 4

s 5

1 3 4

Xi Si Si

Si Si

1 Si

Si Si

4 Si Si

444

Гл. 5. Прикладная теория алгоритмов

Строим семантическую таблицу, состоящую из двух подтаблиц.

Столбцам первой подтаблицы взаимно однозначно соответствуют

запрещенные фигуры Q3 — пути длины 2 графа сцепления, стро

кам — ребра и в клетке (г, j ) стоит 1, если г-е ребро содержится в

j -м пути, и 0 в противном случае. Строкам второй подтаблицы вза

имно однозначно соответствуют ребра, столбцам — входные век

торы, взвешивающие эти ребра, и в клетке (г, j) стоит 1, если j -й

входной вектор взвешивает i-e ребро, и 0 в противном случае.

Для устранения недетерминированности переходов необходимо

расширить входные векторы, вошедшие в покрытие семантиче

ской таблицы. Для этого необходимо покрыть столбцы строками

в первой подтаблице и найденное покрытие покрыть столбцами во

второй подтаблице.

Таблица 5.18

Q31

Q32

Q33

Q34 Q35 Язе Q37

<?38

Ребра

1 2 3 4

1 0

0 0 0 0

0 0

{S b S 2)

1 0 0 0

1 1 0 0 0 0

{S2,Ss} 1

0 0 0

0 0 1

1 1 0 0 0

{S3,5s}

0 1 0

0 1 0 1

0 1 1 0 {Ss, Se} 0

0 0

0 0 0

0 1 1 0 1

{S 3,Se}

0 0

0 0 0 0 1 1 {S 4,Se )

0 1 0

Для рассматриваемого примера семантическая таблица

(табл. 5.18) содержит запрещенные фигуры, имеющие следующий

вид:

Q31 = {{Si, S2}, {S2, S5}}, Q32 = {{S2, S5}, {S5, S6}},

Q33 = {{S2, S5}, {S5, S3}}, Q34 = {{S3, S5}, {S5, Se}},

Q,s = {{S5, S3}, {S3, S6}}, Q36 = {{S5, Se}, {S3, S6}},

Q,7 = {{S5, S6}, {S6, S4}}, Q * = {{S3, S6}, {S6, S4}}.

В данном случае покрытие первой подтаблицы образуют вто

рая, четвертая и пятая строки; покрытие этих строк во второй

подтаблице образуют первый и четвертый столбцы. Следовательно,

для противоположного кодирования внутренних состояний необ

ходимо на графе сцепления удалить ребра {S2, S5}, {S5, Se}, {S3,

Se}. После такого сужения сигнатуры графа сцепления он не со

держит запрещенных фигур и, следовательно, возможно противо

положное кодирование:

Si — Oil, S2 — 100, S3 — 101,

S4 — 001, S5 — 010, S6 — 110.

Ребра из графа сцепления удаляются путем расцепления соот

ветствующих внутренних состояний расширением сцепляющего

их входного вектора. Расширение осуществляется приписыванием

минимального количества внутренних переменных, которыми от

§ 5.6. Семантическое ослабление функциональной связности 445

личаются расцепляемые состояния, соответствующему входному

вектору.

Для получения покрытия семантической таблицы состояния

52, 5б необходимо расцепить расширением входного вектора

* 1* 2*з, состояния 55, 5б и 5з, 5б — расширением вектора * 1* 2*3.

Первое расцепление можно осуществить двумя способами: при

писать ко входному вектору 2122*3 либо первую внутреннюю пе

ременную Z+, либо вторую Z+, т. е. переход из состояния 5 г в

S3 взвешивается соответственно вектором хххзхзг* либо векто

ром X1X2X3Z2 . Для определенности выберем первый способ рас

ширения входного вектора xix2*3- Обозначим 11X2*3*1' через 1/,

а xix2x3~zf — через 1". Расцепление состояний S5 и Sq осуще

ствляется приписыванием первой внутренней переменной zf ко

входному вектору * 1* 2^3. Переход из состояния S5 в S5 осуще

ствляется под воздействием XiX2*3Z^ (обозначим его 4'), переход

ИЗ состояния Se в S4 — под воздействием вектора х ^ х з г ^ (обо

значим его 4").

Расцепляемые пары внутренних состояний, пересечение кото

рых не пусто, называются связными, если они сцеплены одним

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

производится совместно.

Коды состояний третьей сцепленной пары S3, Se отличаются

Двумя переменными, следовательно, расцепление этих состояний

можно провести двумя способами, используя вторую или третью

переменную.

При первом способе переход из состояния S3 в S5 осуществля

ется под воздействием вектора xi2223Z2+, переход из S6 в S4 —

под воздействием х^хзг^- При втором способе приращениями

вектора xix2*3 являются соответственно zf, Z3 . Пары S3, S6 и

0S5, Se связаны входным вектором Х1Х2Х3. Следовательно, необхо

д и м о произвести их совместное расцепление, которое заключается

в логическом умножении условий расцепления для состояния, во

шедшего в пересечение связных пар. В нашем случае таким со

стоянием является Se-

Согласно условию расцепления связных пар внутренних состоя

ний переход из состояния Se в S4 осуществляется под воздей

ствием вектора xi®2X3Z+z+:

*l*2 *3 * l+ & * 1 * 2X3 Z+ = X1 X2 X3 Z1 Z2 ,

аибо вектора xix2x3z^z^:

XlX2 X3 Z^ & X iX 2X3Z3+ = X1 X2X3 Z+Z3+.

Для определенности выбираем первый способ расцепления, обо

значив при этом вектор X1X2X3Z+z£ как 4'". Окончательно полу-

446

Гл. 5. Прикладная теория алгоритмов

чаем следующую систему функций возбуждения:

h (X , zf, zf) =

= zfx\xix3 V zf (Х1Х2Х3z f V xix2X3zt*2 V * 1* 2* 3))

f2{X, zf,z%) = z£(x 1X2X3 VX1X2X3 V XiX2X3Z^) v

V zf (x 1X2X3 v X1 X2 X3 V xix2x3zf zf),

/з{х, zf, zf, zf) = Jf (xix2x3zf V х ^ х зг? zf V X!X2X3 V

V XiX2X3zf) V zf (ЩХ2Х3 V XlX2*3 V XiX2X3zf),

которой соответствует функционал <p(G), равный 4.

Здесь и ниже для определенности в качестве элементов памяти

взяты триггеры со счетным входом.

Найденные запрещенные фигуры определяют достаточные ус

ловия функциональной несвязности элементов памяти. Следова

тельно, после кодирования возможно уменьшение значения <p(G)

Таблица 5.19 пУтем анализа таблиц смены сос

тояний элементов памяти. Каждый

элемент памяти своим значением

разбивает все множество внутрен

них состояний на два класса.

Для рассматриваемого примера

это разбиение представлено в виде

табл. 5.19.

Таблицы смены состояний для графов переходов элементов па

мяти приведены в табл. 5.20.

Таблица 5.20

0 1 0

i := 1 I == 2 1 == 3

zt = 0

1 V 2 V 3V

V4' V l "

ovi' 2 V 3 V 4" 0 V 2 V 4'

l'vl'V

v3 v

> >

0 V 1 ' V3

0 V 3 V 4'"

1 V 4 'V

V I" V 2

0 V 3 V 4"

1 V2

В результате анализа таблиц смены состояний на детерминиро

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

снята везде, кроме векторов 4' и 4'", которые устраняют недетер

минированность при переходе из единичного состояния второго

элемента памяти и нулевого состояния третьего элемента памяти.

При этом для отличия вектора

4'" от 4' достаточно взять его в виде

a: i *2*3*1" •

Теперь функции возбуждения памяти окончательно имеют вид

fi(X, zf) = zfxix2x3 V zf(x 1X2X3 V x ix2x3),

51, S4, Si

52, S3, S<

S2, Ss, Se

S3, S3, Se

Si,Ss,St

Si, Ss, S*

§ 5.6. Семантическое ослабление функциональной связности 447

/з(Х, zf,z%) = zf(xix2x3 V 11*2*3 V *1*2*3) V

V z% (*i*2*3 V *1*2*3 V *1*2*3^),

f3{X, zf, z£) = z3+ (*1*2*3 v *1*2*3 V *1*2*3*^) V

V zf(xix2*3 V *1*2*3 V *1*2*3)

и <p(G) = 2. .

Таким образом, минимизация перекрестных связей между эле

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

1. Устранение запрещенных фигур путем расширения вход

ных векторов и противоположное кодирование внутренних состоя

ний.

2. Анализ полученного кодирования с целью ликвидации из

быточного расширения входных векторов.

3. Выписывание функций возбуждения элементов памяти и

определение значения <p(G).

В случае автоматов, для которых коэффициент плотности со

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

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

увеличивается, и если для ее реализации проектировщик не обла

дает соответствующими вычислительными мощностями, то пер

вый пункт можно выполнить с меньшими вычислительными за

тратами, для чего предложим следующий алгоритм реализации

п. 1.

1. Выделяем в граф сцепления частичные подграфы, ребра

каждого из которых взвешены одним и тем же входным векто

ром.

2. Производим раскраску вершин каждого из этих графов, ну

меруя краски 1, 2, ..., п. При этом номер краски указывает коли

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

3. Штриховка входных векторов физически реализуется раз

личными состояниями элементов памяти. Раскраска (см. п. 2)

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

определяет коды внутренних состояний.

Проиллюстрируем расширение входных векторов. Таблица пе

реходов автомата — в табл. 5.21.

Таблица 5.21 Таблица 5.22

s4 Ss

a,b

a, с

a,b

a,b a,с a,b

a,с

a, с a, с

s <

a,b a, с a,b

a,b

a, с a,b

Si s3

Si Si

Таблица переходов автомата определяет матрицу смежности

графа сцепления (табл. 5.22) и матрицы смежности частичных

448

Гл. 5. Прикладная теория алгоритмов

подграфов сцепления Gca, Gcь, Gcc (табл. 5.23, а, б, в) по входным

векторам а, Ь, с соответственно.

Таблица 5.23а Таблица 5.236 Таблица 5.23е

S3 Si

s2 1

1 I

Si 1

s 2

S 3

Si Si

1 1

S 3

1 1

1 1.

Si Si

Si 1

1 1

Si 1

Si 1 1

Квазиплотность графов Gca, Gcь, Gcc равна соответственно 3, 2,

2. Следовательно, их хроматические числа равны соответственно

3, 2, 2. Раскрашивая эти графы, получаем разбиение вершин

графов

Gca - К и = {Su S5}, К2а = {S 2, S4}, К3а = {5 3},

Gcb - Ки = {S2, S4}, К 2Ь = {Si, S5>,

Gcc — Kic = {S 3}, K2c — {Si, Sa, S4, S5}.

Раскраска Gca, Gcb, Gcc порождает разбиение множества вну

тренних состояний, которому соответствует кодирующее дерево

{S i,S 2,S3,S4,S6} Л { 5 3}

4.1

{S i,S 2,S4,S5} A { S i , S 5}

4.1

{S2,S4y

в котором на ребрах указаны соответствующие значения внутрен

них переменных.

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

полученной раскраске, будет реализована, если внутренние состоя

ния будут иметь коды

S3 — 0aia2, Si — Юаз, S5 — 10а4,

S2 — 11<*5) S4 — Пае,

где а,- = 0, 1 (г = 1 — 6), причем для однозначности кодирования

полагаем, что аз = а4, as = Щ. Конкретизируя а,-, окончательно

получаем коды

S3 — Oil, Si — 100, S5 — 101,

S2 — 110, S4 — 111.

После получения кодов переходим к п. 2 первого алгоритма:

устраняем избыточную штриховку входных векторов. В резуль

тате получаем, что для расцепления оставшихся пар {S 3, S4),

{S 3, S5}, сцепленных вектором а, пар {Si, S2}, {Si, S4}, {S 2, S5},

§5.6. Семантическое ослабление функциональной связности 449

{ 54, Ss}, сцепленных вектором 6, и пар {5 2, 5з}, {5з, 54}, сцеп

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

zi до о' = аг* и а" = azf, так как краска К$а отличается от

красок К\а, К 2а этой переменной; аналогично вектор b нужно рас

ширить переменной zf до V = bz£, b" = bzf; вектор с расширить

переменной zf до d — c l* , с" = czj*".

С учетом проведенных расширений входных векторов перво

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

табл. 5.24, в которой около расширяемого вектора в круглых скоб-

Таблица 5.24

Внутренние

состояния

s r

S 3-

S s-

s t

S t

a(— '),b

S t

a(— ")

*('--)

S t

ках указан способ расширения при вычислении каждой внутрен

ней переменной (zi, z2, Z3); при этом прочерк означает, что со

ответствующая переменная вычи

сляется без учета расширения Таблица 5.25

входного вектора, т. е. не зави

сит от других внутренних пере

менных.

Полученные коды разбивают

все множество состояний согласно

табл. 5.25.

Эти разбиения определяют таблицу смены состояний элемен

тов памяти (табл. 5.26). Таблица 5.26

2Г

1 0

i :

= 1

1 =

= 2

i == 3

о ]

+•«

a Vb

6 V с

a V 6" V с

z t = l

a V b 'Vc

a V 6 V с"

a" a 'V bV c

Табл. 5.26 задает функции возбуждения элементов памяти вида

fi(X, z+, z+) '= z+cVz+bz+,

f2{X, z+, z+) = z + (Ь V с) V z+ cz + ,

fs(X, z+, z+, z 3+ ) = lJ (a V i2 2+ Vc)V z^ az+,

для которых v?(G) = 4.

15 В. А. Горбатов

0 1

S i, S j

S i , S 2

S i , S2, S4, S5

5 2, S3, S4

53, S<, Ss

450

Гл. 5. Прикладная теория алгоритмов

Рассмотрим этот пример с учетом характера переходов, ана

лизируя при этом возможность раскраски сцепленных состояний

одной краской при их переходах под воздействием сцепляющего

входного вектора в соцветные состояния.

Граф сцепления (табл. 5.22) содержит циклы нечетной длины

вида

Ci = {{5 i,5 3}, {5 3,5 4}, {S i,S 4}},

С2 = {{Su 53}, {S 2, 53}, {SU S2}},

C3 = {{S 2,S3}, {5 3,5 5}, {S 2,S 5}},

С 4 = { { 5 з, 5 4}, { 5 4, Ss}, {S3,Ss}}.

Покрывая семантическую таблицу (табл. 5.27), отметим, что

для получения первого разряда кодов внутренних состояний необ-

Таблица 5.27

{Si, S3}

{S3,54}

{S,,S4>

{5г,5з}

{S,,S2}

{5s, Ss}

{S2,Ss}

{S4,Ss}

C, 1

1 1

c2 1

1 1

c4 1

ходимо расцепить внутренние состояния {Si, S3} и {S 3, Ss}. Пе

ред тем как производить это расцепление путем расширения вход

ных векторов, которыми эти состояния сцеплены, рассмотрим усло

вия их соцветной окраски. Для того чтобы вершины {Si, S3}

были соцветны, необходима соцветность вершин {S4, Ss} и

{S 3, S5}:

*(Si) = k(S3) *- (jfc(S4) = *(S5)) & (*(S3) = *(S5)).

Состояния {S 4, Ss} сцеплены, следовательно, для того чтобы

они были соцветны, необходима соцветность состояний {Si, S2} и

{S 3, S4}:

jfc(S4) = k(Ss) <- (ifc(Si) = *(Sa)) & (*(S3) = jfc(S4)).

Состояния {Si, S2} сцеплены, следовательно, для их соцветно

сти необходима соцветность состояний {S 2, S3} и {S4, S5}:

ib(Si) = *(Sa) <- (ifc(Sa) = k(S3)) k (*(S4) = k(S5)).

To же самое имеем и для вершин {S 2, S3} и {S3, S4} соответ

ственно:

k(S2) = k(S3) <- (*(S4) = k(Ss)) & (*(S3) = *(S4)),

k(S3) = k(S4) (*(S 4) = k(Ss)) & (k(S2) = k(S3)).