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

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

§ 4.7. Синтез логических структур в топологических базисах 321

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

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

ных и сравнительно небольшим числом обобщенных состояний

Автомата, определяемых значениями вектора XZ+Z — Y. Напри

мер, автомат управления может иметь 100 элементов из Мх и Мх и

О Совершенная ДНФ

^^Ср^Сокращенная ДНФ

Покрытие импликантной таблицы

Тупиковые ДНФ

Покрытие решетчатой таблицы

. . . ъ 6 - Ъ 6-

Решетчатые ДНФ

Phcj 4.39

только лишь на 500 наборах определен. Но 500 намного меньше,

чем число всевозможных двоичных наборов длины 100, равное

2100: 500 «С 2100. Используя это положение, можно снизить трудо

емкость синтеза автоматов управления путем разбиения большого

числа переменных автоматного оператора на группы с последую

щей заменой переменных каждой группы на одну “новую” пере

менную. Предложим метод такого объединения переменных.

Введем несколько понятий.

Множество букв, взвешивающих только вершины двухинцин-

дентного подграфа структурного графа, называется обобщенной

буквой первого рода.

При структурном синтезе двухинцендентный подграф будем на

зывать ж-структурой (ж-диаграммой).

с-структурой (с-диаграммой) называется подграф структур

ного графа, произвольная пара вершин и, и Vj которого коинци-

дентна только соответственно входящим дугам uf.ufn,...,uf и

*1 *2 *о

«+, ..., имеющим соответственно одно и то же начало,

и которая коинцидентна только исходящим дугам , и~, ..., и~

и и~, ..., «т , имеющим соответственно один и тот же конец

(рис. 4.40).

Множество вершин {и,}, каждая из которых покрывается од

ними и теми же вершинами {Ги,}, при этом ни одна из вершин

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

322

______

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

va, va G {Ги,}, не покрывает вершины vp, vp £ {и,}, и эхо мно

жество вершин {и,} покрывает одни и те же вершины {Г-1и,},

при этом ни одна из вершин G {Г-1и,}, не покрывается

вершиной v$, v$ £ {и,}, называется

а- поддиаграммой.

Множество букв аь а2, ..., ап,

каждая из которых взаимно одно

значно соответствует вершине ст-диа

граммы, называется обобщенной

буквой второго рода.

На рис.4.40 обобщенная буква вто

рого рода взвешивает средний ярус.

Т еорем а 4.2. Множество букв

а\, а2, . . ап образует обобщенную

букву первого рода тогда и только

тогда, когда собственные часто

ты этих букв равны между собой

и равны взаимным частотам:

fi — fj == fij, j — ai, 02, ..., on.

(4.10)

Т еорем а 4.3. Множество букв a i, а2, ..., ап образует обоб

щенную букву второго рода тогда и только тогда, когда

fi — fj) fij = 0) fiiji = fjiji, 1 Ф j, l\ j — al 1 a2i • • an,

Рис. 4.40

и e M\ {ob o2, ..., an}.

(4.11)

В выражениях (4.10) и (4.11) /,, fj — собственные частоты,

fij (i ф j) — взаимная частота, определяемая частотной матрицей

отношений F = [fij], F ~QT X Q

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

мограф. В матрице Q = [g,j] каждой букве взаимно однозначно

сопоставлен столбец, слову — строка и

_ 1, если j-я буква содержится в i-м слове,

Q'i ~ I 0 в противном случае.

Метод выделения обобщенных букв заключается в следующих

преобразованиях.

1. С помощью частотной матрицы отношений, соответствую

щей мографу, согласно (4.10) выделяем обобщенные буквы первого

рода.

2. Согласно (4.11) выделяем обобщенные буквы второго рода.

3. Если были выделены обобщенные буквы второго рода, то

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

4. Конец.

§4.7. Синтез логических структур в топологических базисах 323

Проиллюстрируем предлагаемый метод уменьшения числа пе

ременных на следующем примере.

Пусть задана булева функция /, которая задается матрицей инцидентности

вида

1 1 0 0 1

0 1 0 0

0 0

0 1

0 1 1 1

1 1

0 0

1 1

0 0

0 0 0

0 0

0 1

1 1 0 0

0- 0

0 0

0 0 1

1 1 1

1 1 0 1

0 0

0 1 0 0

1 1 0 0

0 0 1

0 1

1 0 1

0 0

1 1

0 1

1 0 0

0 0

1 1 1

0 0

0 1

Частотная матрица отношений, соответствующая функции /, имеет следую

щий вид:

6 6

2 1

1 2 2

6 6

1 1

2 2 6 3

2 2

4 3

0 с

2 2

4 0 3

1 1

0 5 2

2 е

1 1

2 2

4 5

2 3

0 2

3 к

2 0 3

2 4 3 6

Согласно (4.10) буквы а и b являются обобщенными буквами первого рода.

Заменим их буквой Ь'.

Согласно (4.11) буквы с и т являются обобщенными буквами второго рода;

буквы d и к, е и / также являются обобщенными буквами второго рода. Заме

няем их соответственно на т', к',

После замены букв матрица инцидентности имеет вид

Ъ'

fc'

0 0 1 1

0 1

1 1

Частотная матрица отношений F' (F1 = (Q')T х Q') имеет следующий вид:

S' 9

к'

1 1

Ь'

2 1

2 2 1

2 2

к’

1 1

1 2

2 т'

Согласно (4.10) буквы д' = {/', д} и т" = {к1, т'} являются обобщенными

буквами первого рода. Обобщенных букв второго рода иет, следовательно, выде

ление обобщенных букв окончено. Окончательно имеем матрицу инцидентности,

324

_____

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

задающую в виде булеву функцию в виде

Ь'

д'

т'

1 0 1

0 1 1

1 0

/ =

Такое сжатие информации позволяет существенно уменьшить трудоемкость

при синтезе минимальных автоматов управления.

После сжатия при приведении функции к ре

шетчатому виду необходимо учитывать резуль

таты сжатия при покрытии решетчатых таблиц.

Для рассматриваемого примера заметим, что мо

граф, задающий сжатую функцию, представляет

собой цикл нечетной длины с циклической пе

рестановкой весов, и, следовательно, для приве

дения этой функции к решетчатому виду можно

расщепить либо Ь', либо д', либо т " . Взвесим

каждую букву в сжатой таблице числом букв, ко

торые оиа представляет. При минимальном рас

щеплении выберем букву Ь', так как ее вёс ра

вен 2.

В результате синтеза имеем структурный

граф G(f) (рис. 4.41), реализующий функ

цию /.

Логическая структура в первом топо

логическом базисе задается диаграммой Хассе Н, и ее синтез со

стоит из следующих преобразований.

1. В мографе, задающим реализуемую булеву функцию, выде

ляем запрещенные фигуры типов А и Б (рис. 3.53).

2. Находим пары внешне неустойчивых вершин относительно

носителя каждой запрещенной фигуры.

3. Строим семантическую таблицу, сжимаем ее и определяем

покрытия.

4. Выбираем минимальное покрытие семантической таблицы,

которое порождает мограф GM, эквивалентный заданному, имею

щий минимальное расширение носителя и интерпретируемый в

категориях синтезируемого структурного графа Н.

5. Производим фактическое построение структурного графа по

интерпретируемому мографу GM. Синтезированный структурный

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

эквивалентных графов и построенным без перебора всех эквива

лентных графов.

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

проектированием логической схемы, реализующей ДНФ булевой

функции (см. рис. 3.54, а)

/ (1 1 ,1 2 ,..., 15) =

= Х1Х3Х5 V iii4 Vx2i3 Vxii3x5 V13X4I5 V X2X4X5 •

1 2 3 4 5 6

§4.7. Синтез логических структур в топологических базисах 325

Выделение запрещенных фигур типов А и Б сводится к выде

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

кой распределения идентификаторов на их вершинах. Выделение

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

графа, добавлением хорд с формированием базисных циклов и ге

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

клов по модулю 2.

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

1. Выделяем остов мографа по матрице смежности фиксацией

около диагональных единичных элементов:

*2(3,6)

*з(3,4,5)

*<(2,6)

*5(5,6)

*5(1 , 4)

—

0 0

1 0

—

1 1

—

1 1

—

1 0

—

0 1

0 -

Эту фиксацию будем производить, например, следующим алго

ритмом. Рассматриваем по очереди строки (начиная с первой) и

отмечаем ближайшую от диагонали единицу. Если число отмечен

ных единиц равно п — 1 (п — чи

сло вершин мографа), то остов най

ден. В противном случае, начиная

с последнего столбца, отмечаем в

этом столбце ближайшую единицу,

переходим к столбцу на один но

мер меньше до тех пор, пока не

будет отмечено п — 1 единиц. От

меченные элементы матрицы за

дают остов. В результате рабо

ты этого алгоритма получаем остов мографа, изображенный на

рис. 4.42. Отмеченные около диагональные элементы набраны по

лужирным шрифтом в матрице смежности.

Неотмеченные элементы соответствуют хордам мографа отно

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

скому числу мографа

к е " ) = | ы г - т + к ,

где \М\ — мощность носителя мографа, | {/»;} | — количество ребер

мографе, К — число компонент связности мографа.

В нашем примере v(GM) = 8 - 6 + 1 = 3.

2. Формируем базисную матрицу циклов (базисную циклома-

тическую матрицу) присоединением хорды к выделенному осто

ву. В результате получаем базисную цикломатическую матрицу

относительно остова D (рис. 4.42).

Рис. 4.42

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

Обозначим ребра мографа как

{х 2(3, 6), х4(2, 6)} = а, {15(5, 6), х3(3, 4, 5)} = /,

{х 2(3, 6), 15(5, 6)} = Ь, { x ^ l, 2), i 4(2, 6)} = д,

{ * i(l, 2), х5(1, 4)} = с, {х3(3, 4, 5), х5(1, 4)}=р,

{х 2(3, 6), х3(3, 4, 5)} = d, {х4(2, 6), х5(5, 6)} = е.

Цикломатическая матрица рассматриваемого примера имеет вид

Хорды Остов

a b с

9 p

0 0

1 1 1

0 0

0 1

0 1 1 1 1

3. Применением 2" — v — 1 раз операции сложения по модулю 2

циклов выделяем все циклы мографа. Каждый выделенный цикл

проверяем на условие образования запрещенной фигуры типа А

или Б.

Базисный цикл р2 является запрещенной фигурой Qi, а базис

ный цикл рз — запрещенной фигурой Q3.

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

ими запрещенных фигур:

Р\ .© р2 — р4, Р4 <+110 о 1 О О О,

цикл pi является запрещенной фигурой Qi;

Pi © Рз = Ръ, />5 ^ 1 0 1 1 0 0 1 1 ,

выделенный цикл является запрещенной фигурой Q2;

Р2 © Рз = Рб, Ре ** 0 1 1 1 1 0 1 1,

Pi © Р2 © Рз — Pi © Рв = Pi, Р7^ 1 1 Ю 0 1 1 1 ,

циклы рх, рв к Р7 не являются запрещенными фигурами, так как

они имеют четную длину.

Находим пары внешне неустойчивых вершин относительно но

сителя каждой запрещенной фигуры. В нашем примере такой па

рой относительно носителя запрещенной фигуры

Qi = {x2(з, 6), х5(6, 5), х3(5, 3)}

будут вершины и(х4), и(х4). После добавления слов {х2, х3, 15} и

{х4, is , Х4} фигура Q1 неустойчива, и достаточно будет расщепить

только 14(2, 6) (см. табл. 3.9):

и(хх) < и(х3) < и(х5), u(Xi) < v(Xi),

v(x3) < u(xi) < t>(x5), t>(x3) < v(x2),

v (x3) < 1KX5) < t>(x2), v(x3) < t>(l5) < v(Xi),

«(14) < u(x5) < u(x2), v(x'4) < u(x5) < v(li).

§4.7. Синтез логических структур в топологических базисах 327

Рассмотрим фактическое построение структурного графа Н по

интерпретируемому мографу GM. В случае несложных могра

фов такое преобразование можно реализовать с помощью операции

взятия двойственной структуры, как это делалось выше. В слож

ных случаях объем вычислений возрастает настолько, что целе

сообразно применять частотный анализ мографов и на его основе

строить Н. Рассмотрим этот метод построения Н по мографу GM.

Буквы, соответствующие минимальным или максимальным

элементам диаграммы, будем называть крайними.

Если количество минимальных (максимальных) элементов,

покрываемых (покрывающих) одними и теми же вершинами (од

ни и те же вершины), не меньше 2, то соответствующие им буквы

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

ними первого рода.

Теорема 4.4. Если буква а является крайней первого рода,

то

fa — ^ ^ fit fai ~ fit fij ~ 0) * Ф ji *j j — d, е, . . ., П,

(4.12)

каждая буква b G {г/ i = d, е, ..., п} соответствует вершине,

покрывающей и(а) (рис. 4.43, а)

Рис. 4.43

Теорема 4.5. Если буквы а\, а2, .■., ап являются крайними

второго рода, то

(Va,(i € {1, 2, ..., п}))(ЗЬа, Ьр, ..., Ь7(а, /3, ..., 7 €

€{1,2, ..., р})) (/а; = Y1

(V6j(i € {1, 2,..., р}))(Эав, а„, ..., ае(0, 4, ...,£е

€ {1,2,...,п})) (/*.= • J2 М )> (4ЛЗ)

i=6,Tj,...,t

328

_____

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

faka, = 0, к ф I, k,l = 1, 2, П, fbklbl, = О, к' ф V, k',V =

= 1,2,..., р, где каждая буква bj (j € {1, 2, ..., р}) взвеши

вает вершину, покрывающую соответствующие минимальные

элементы диаграммы (рис. 4.43, б).

Замечание. Теоремы, двойственные теоремам 4.4, 4.5, фор

мулируются аналогично: слово “покрывающие” заменяется словом

“покрываемые” и “минимальные” — словами “максимальные”,

остальное остается без изменения.

Здесь топология синтезируемой диаграммы (структурного гра

фа) однозначно с точностью до применения операции взятия двой

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

элементы которых являются элементами частотной матрицы

отношений F = QT(GM) х Q(GM).

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

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

ные соотношения, определяющие топологию синтезируемой под

диаграммы, будут более сложными и элементами их будут частоты

вершин, принадлежащие более чем двум ярусам.

Сечением структурного графа называется множество попар

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

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

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

искомая совокупность букв, покрывающих найденные буквы а1,

02) • • •) °п) так и совокупность букв, сравнимых с аь а2, ..., ап,

но не покрывающих их.

В силу локальности соотношений (4.12), (4.13) поиск крайних

букв необходимо осуществлять локальным перебором по всем се

чениям диаграммы. После нахождения покрывающих вершин по

строенные на этом шаге поддиаграммы представляются в виде

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

щим свертыванием каждой из них в эту вершину.

Известно, что частотная матрица отношений однозначно опре

деляет интерпретируемый в категориях диаграмм мограф GM и

однозначно с точностью до применения операции взятия двой-

ственнрй структуры — проектируемую диаграмму, поэтому при

проведении проектирования на языке частотных матриц отноше

ний свертывание гамака в вершину итах) являющуюся его макси

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

с гп(утлх) (т. е. тех букв т,-, у которых / m,mm„ ф 0), на число

путей, содержащихся в свертываемом гамаке, и вычеркиванием

строк (столбцов), соответствующих буквам свертываемого гамака,

за исключением m(umax). При этом полученная частотная матрица

отношений описывает еще не построенный структурный граф.

Алгоритм преобразования GM —► Н состоит из следующих

шагов.

§ 4.7. Синтез логических структур в топологических базисах 329

1. Определяем все обобщенные буквы первого рода. Стягиваем

гамаки, соответствующие найденным буквам, в вершину.

2. Определяем все обобщенные буквы второго рода. Стягиваем

гамаки, соответствующие этим буквам.

3. Найдена ли хотя бы одна обобщенная буква первого или вто

рого рода? Если да, переходим к выполнению п. 1, в противном

случае — к п. 4.

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

одному из условий (4.12), (4.13). Линейно упорядочиваем найден

ные множества в виде списка.

5. Рассматривая первое множество букв в построенном (по

следнем) списке и полагая, что она взвешивает соответствующую

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

поддиаграмму. Свертываем полученные гамаки.

6. Определяем буквы, соответствующие вершинам, покрываю

щим максимальные элементы построенных поддиаграмм, исполь

зуя пп. 4, 5. Если при выполнении пп. 4, 5 не выполняется ни

одно из соотношений (4.12), (4.13), то последнее наше предположе

ние неверно. Рассматриваемое множество букв и соответствующую

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

стотную матрицу отношений и переходим к п. 5. Если хотя бы

одно из условий (4.12), (4.13) справедливо, то выполняем п. 6. В

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

структурный граф.

Предлагаемый алгоритм эффективно реализуется на ЭВМ в

силу арифметического характера преобразований.

Построим структурный граф Н по мографу GM (рис. 3.54),

используя этот алгоритм.

Матрица инцидентности Q(GM), определяющая мограф GM,

имеет вид

Хз

х<

х5

0 0 0

1 0

0 1

0 0 0

0 0

0 0 0 0

0 1 0 1

0 0

0 1

0 1 0 0 0 0 1

0 0

Частотная матрица отношения F(GM), F = QrxQ, определяю

щая частотные свойства мографа GM, имеет следующую строчную

запись:

F(GM) = 2х\ о (x i)2 oijo 2х\ о (Х3)2 о (хз)2 о х\ о (х'4)2 о

о (х4)2 о 2х2 о 2(х5)2 о хгхз о х\х'А о х\хъ о ^1X3 о Х1Х5 о

О Х2Х3 О Х2Х4 О Х3Х4 О Х3Х5 О Х3Х5 О Х3Х5 О Х4Х5 О Х4Х5,

330

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

где коэффициенты при а2 равны собственным частотам соответ

ствующих букв, коэффициенты при а/3 равны ненулевым взаим

ным частотам между соответствующими буквами а,/? = хi,xi,x2,

хз, Х3, хз, Х4, х'4, Х4, xs, Х5; о — конструктивный разделитель

частот.

Анализ частного разложения мографа GM показывает, что для

множеств {хх, хг, хз} и {ig, Х4, Х5, х5} выполняется частотное со

отношение (4.13):

для множества {xi, х2, хз}

/х 1 fx'fH "b fx3 XI ) }хз — fx 1 ХЗ "Н fx4 хз ) fxt — fx4 Х% "f" fx'3 Х2 >

fГ4

/xjx 1) fx3

fx 1*3) fx1

hi X3 ) fxt fxix 3)

— /x /xi = fx

IX4 JX4X2) Jr j JX'3 X 2’>

fkl = 0, A: ^ k,l = x 1, x2, x3,

/fc'/' = 0) k Ф I t k , I = X i, Х3, X4, X4, X4, X3J

для множества {ig, x4, 15, X5}

fx'3 /xjX2 ) /rj /xjx 1) /Г5 /x5X4 ~Ь /Г5Х4)

/xs — / x 5X3 ~Ь / x 5X1) /хз — /х 3х5) / п — /х 1X5) /х4 — / х 4X5)

/х4 = / х4х5, /ы = 0) к ф1, к, I = Xg, Х4, Х5, Х5.

Отсюда имеем структурный граф Я , реализующий мограф

(рис. 4.13). Заменяя вершины графа Я на ключевые элементы

первого топологического базиса, например, на переключатели све

та, а дуги — на световоды, получаем логическую схему сложности,

равной числу вершин структурного графа Н.

Проводя точное решение для примера, рассмотренного в на

чале этого параграфа, получаем в 2 раза меньше расщеплений

Рис. 4.44

(рис. 4.44) по сравнению с решением, проведенным без учета за

прещенных фигур.

Частотный анализ можно с успехом использовать и при при

ближенном преобразовании мографа GM(f) в структурный граф

" ‘Яведем ряд понятий.