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

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

§ 5.3. Характеризация выходной связности структур

______

421

данной системы:

F i ( X ) = x 4x 5 / i V x 2x 5 / i V Г 3Г 4/2 V Х 3Х 5/3 V x i x 2 / i V * 1X 2 / 4 V X 2 Z 3/4 ,

F 2 ( X ) = Г 4Х 5 / 1 V Г 2Х 5/1 V X3X 4/2 V X3X5/3 V Х 1Г 2/4 V * 1 x 2 / 4 V X 1X 3 / 4.

Рассмотрим первую из ТДНФ, представляя ее в виде модели Ф|,:

М а = { * 1 , X I, Хг, Х2, Х з , Х4 , Xs, / 1 , /2, /3 , / 4 },

p ( * i ) = p ( x i ) = р(х2) = р(х2) = р (х 3) = р (х 4) = р (х 5) = 0 ,

. р(/0 = р(/г) = р(/з) = р (Л ) = 1.

Слова модели соответствуют конъюнкциям функции Fi(X). Построим

Рис. 5.27

модельный граф GM (рнс. 5.27,а). Перечислим запрещенные фнгуры, содержа

щиеся в GM :

Qa\ = {x s(l, 4), 14 (1 , 3), гз(3, 4 )}, Q a 2 = {xs(2, 4), хз(4, 7), x2(2, 7)},

<?B4 Э {xs(1, 4), X3(3, 4)},

Qb6 D {xs(1, 4), Хз(4, 7)},

Qeв D {xs(2, 4), x2(2, 5)},

Qbio D {x4(1, 3), хз(3, 4)},

Qbi2 D {хг(2, 7), x3(3, 7)},

Я ез D {xs(1, 4), x4(l, 3)},

Q bs D {x5(2, 4), x3(3, 4)},

Q&r D {a?s(2, 4), x3(4, 7)},

Q e9 D {x 5(2, 4), хг(2, 7)},

Qfin D { x4(1i 3), хз(3, 7)},

Qbi3 D {хг(2, 7), хз(4, 7)}.

Покрытиями семантической таблицы (табл. 5.9) являются множества строк:

|1, 2, 3, 8}, {1, 2, 3, 5, 6}, {1, 2, 4, 5, 6}, {1, 2, 4, 5, 8}, (3, 4, 6, 7, 8},

{1, 4, 5, 6, 7, 8}.

Построим для лексикографически одинаковых букв графы на множестве

слов, в которые входят эти буквы. Раскраска их определяет необходимое рас

ширение (Д М а) носителя М а в каждом конкретном случае.

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

Таблиц а 5.9

Буквы

Запрещенные фигуры

4 5

7 8 9 10

*5(1,4)

1 0 1 0 0 0 0 0 0

*5(2,4)

0 0

* 4(1 ,3) 1

1 0

0 0 0 1

2:з(3, 4)

1 0 0 1

*з(3, 7)

0 0 0

*з(4, 7)

0 1

0 0

*2(2,5)

0 0 0

0 0 0 0

*2(2,7) 0 1 0

0 0

0 1 0 0

1 1

Мощность расширения носителя |ЛМа| для каждого из покрытий соответ

ственно равна 3, 3, 3, 3, 3, 4. Следовательно, минимальная сложность L струк

турного графа Н равна 14 (рис. 5.27,6): L = \Ма\ + |ДМа| = 14.

Рассмотрим модель , соответствующую второй ТДНФ:

М а = {*1, *1, Хг, хг, хз, Xi, Xi, fi, /2, /з, /4},

p (*i) = P (* i) =p{x2) =р{хг) =р (х3) =р(х4) = р(х5) = О,

,p(fi)=p(f2)=p(h)=p(fi) = l.

Мограф GM (рис. 5.28, а), определяющий эту модель, содержит запрещенные

Рис. 5.28

фигуры следующего вида:

Qai = { * 5( 1, 4), 2:4(1 , 3), г3(3, 4)},

Qb2 Э {*s(1, 4)i *«(!> 3)i *3(3, 4)}, Qe3 Э { * 5( 1, 4), *з(3, 4)},

Qb< D { * 5(2, 4), 2:3(3, 4)}, Qb5 D {*s (l, 4), 2:3(4, 7)},

Qbs D { * 4( 1, 3), 2:3(3, 7)}, Qes D {хъ(2, 4), 2:2(2, 5)}.

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

расширение носителя | ДМ| равно 2. Оно и порождает минимальный структур-

§ 5.4. Теоретико-структурная минимизация булевых функций 423

Таблица 5.10

Буквы

Запрещенные фигуры

1 2

3 4 5 6 7

8 9

*5(1,4)

0 1 0 0

0 0

*5(2,4) 0 0 0

0 0 1

*<(1|з)

0 0 0

0 1 1 0

*в(3,4)

1 0 1

0 0

*в(3,7)

0 0

0 0 1

*8(4,7)

0 0 0 0 1 1 0

*2(2,5)

0 0 0 0 0 0

0 1

ный граф (рис. 5.28,6), определяющий данную систему булевых функций F(X ).

§ 5.4. Теоретике-структурная минимизация

булевых функций

Рассмотрим оптимизирующие функционалы усечения вариан

тов, построенные на основании учета структуры запрещенных фи-

гур. Исследуем более подробно процесс приведения произвольного

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

Количество меток каждой вершины и,- мографа равно собствен

ной частоте соответствующей буквы модели, а количество общих

Меток для пары вершин и,- и Vj (ребра (г, j )) — значению взаим

ной частоты соответствующих букв. Следовательно, ребро (г, j)

мографа можно характеризовать тремя величинами: fj и Д,,

где /,• — собственная частота буквы t; fj — собственная частота

буквы fij — взаимная частота букв i и j j).

Прослеживая процесс образования запрещенных фигур Q\,

Qb, Oei замечаем, что чем больше сумма /,• + fj собственных ча

стот букв i и j при данной взаимной частоте fij или чем меньше

взаимная частота fij букв i и j при данной сумме их собственных

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

&ида Qa , Qb, Qe "

Охарактеризуем каждое ребро (г, j) мографа Ф(/) значением

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

%кв:

— (i j) — /»' ~ У Н + fi

dS(h3)~ fij

Тогда чем больше значение производной, тем выше степень

Неодинакового участия букв в словах; чем больше неоднородность

|ографа, тем больше вероятность образования подмоделей вида

7аI Qb, Qe в Этой модели, тем более сложный (в смысле числа

цементов) синтезируемый граф соответствует этой модели. По

тому максимальный интервал I функции /, которому соответ

ствует полный подграф, будем оценивать средним значением р(1)

424

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

производной, вычисленной для каждого ребра этого подграфа, т.

выражением

И/) = Г7т Ч т ( £ £

....

Т (5-1)

fi ~ % fjj + fj \

r(r -i)v tri^ 1 & у

где г — ранг простой импликанты I (он равен числу первич

ных терминов, образующих импликанту). Следовательно, оценка

(5.1) позволяет синтезировать оптимальные ДНФ булевой функ

ции, учитывая ее теоретико-структурные свойства.

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

виде оценки (5.1), приведем приближенный алгоритм теоретико

структурной минимизации булевой функции.

1. Заданную ДНФ функции / определяем в виде матрицы ин

цидентности Q.

2. Выделяем простые импликанты функции / и записываем

их в список /.

3. Строим ядро функции /. Если оно пустое, то переходим к

п. 6, в противном случае из списка I вычеркиваем элементы ядра

и переходим к п. 4.

4. В матрице Q заменяем единичные интервалы функции /, по

крываемые вычеркнутыми из списка I простыми импликантами,

на эти простые импликанты.

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

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

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

= QT X Q.

7. Согласно (5.1) оцениваем каждую простую импликанту из

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

вычеркиваем ее из списка I и переходим к п. 4.

8. Определяем, задаст ли построенная матрица Q тупиковую

форму. Если нет, удаляем избыточные простые импликанты. По

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

с учетом ее теоретико-структурных свойств.

Пример 5.3. Минимизируем с учетом теоретико-структурных свойств бу

леву функцию f(x 1, хг, хз, * 4)^ = V(2, 3, 4, 5, 8, 9, 11, 12, 14, 15); на осталь

ных наборах она равна нулю.

1. Матрица Q имеет вид

Q =

х2

Х‘2

Хз

хз

ха

х4

0 1 1 0 0

1 0 1 1 0 1

0 1 1

0 1

1 4

0 1 1 0 0 1 1 0 5

1 0

0 1 0 1 0 1 8

1 0

1 0 1

1 0 9

1 0

0 1 1 0 1 0 11

0 1 0

1 0

1 12

1 б 1 0

1 14

1 0 1

1 0 1 0 15

§ 5.4. Теоретико-структурная минимизация булевых функций 425

2. Список I простых импликант булевой функции следующий:

001—, 100-, 11- 0, 010-, - 011, 1- 11, - 100, 10- 1, 111- .

3. Функция / имеет ядро, состоящее из обязательных простых импликант

010-, 001— и 100-. После вычеркивания элементов ядра список I принимает

вид

-100, 11-0, -011, 1-11, 10-1,

111- .

4. В результате соответствующей замены строк матрица Q принимает вид

*1 *1 *2 *2 *3 Хз *4 Х\

0 1 0 1 1 0 0 0

001-

0 1 1 0 0 1 0 0 010-

Q ' =

10010100

100-

1 0 0 1 1 0 1 0

10100101 12

10101001

10101010

5. Строки матрицы Q ' с четвертой по седьмую не соответствуют простым

нмпликантам, поэтому переходим к п. 6.

6. Частотная матрица отношения F ' (F ' = (Q ')’

r х Q'), соответствующая

Матрице Q , такова:

*1 *1 *2 *2 х3 Х3 х* *4

50323222

* i

02111100

31402212

F ' =

2 1 0 3 2 1 1 0

хг.

3 1 2 2 4 0 2 1

2 1 2 1 0 3 0 1

Хз

20112020

2 0 2 0 1 1 0 2

Х4

7. Оцениваем каждую простую импликаиту из списка, полученного в п. 3.

Согласно (5.1) имеем

JK-100) = р(х2хзи) =

= — (

3-2 V

4 - 2 -2 + 3 4 - 2

2 + 2 3 21 + 2

р(-011) и 0,91, р(10-1) « 1,98, р(1 —11) и О, 58,

р(11-0) яв0,58, р(111-) «0 ,67.

аем простую импликаиту 11 — 0 и переходим к п. 4.

4. В матрице Q' заменяем конституенты единицы функции /, покрываемые

ликантой 11—0, на эту простую импликаиту. В результате получаем матрицу

Q" =

х *

0 1 0 1 1 0 0 0 001-

1 1 0 0 1 0 0 010-

0 0

1 0

100-

1 0 1 0 0 0 0

11-0

1 0 0 1 1 0 1 0 11

1 0 1 0 1 0

0 15

5. Матрица Q содержит конституенты единицы функции, не являющиеся

Простыми импликантами. Переходим к п. 6.

426

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

6. Частотная матрица отношений F", соответствующая Q", имеет вид

*1 *1 Х1 *2 *3 Хз *4 *4

4 0 2 2 2

2 1

0 2 1

1 1

x i

2 1

0 1

3 2 1 1 0

х2

2 1 1 2 3 0 2 0 Х3

1 1 1 1 0

2 0

х3

2 0 1 1 2

ХА

1 0 1

0 0

0 1

7. По формуле (5.1) оцениваем простые импликанты из списка /, покрываю

щие оставшиеся конституенты единицы функции /. Имеем

р(-011) «0,75, р(1-11) « 0,5, р (1 0 -1 )« 0,91, р(111—) « 1,16.

Выбираем простую импликанту 1 — 11 и переходим к п. 4.

4. После соответствующей замены строк, получаем матрицу

x i Х\

х2

Хз

хз

1 1 0 0 0 001-

1 1

0 1 0 0

010-

1 0

1 0 1

0 100-

1 0 1 0 0 0 0 1

11-0

1 0

0 1

0 1-11

5. Любая строка матрицы Q'" соответствует простой импликанте. Переходим

к п. 8.

8. Матрица Q'" задает булеву функцию /, минимизированную с учетом ее

теоретико-структурных свойств.

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

удалена полученная ТДНФ функции /(*i, * 2, Хз, ха) от ТДНФ функции /, соот

ветствующей минимальному структурному графу. Найдем все тупиковые ДНФ

функции /. Для этогб построим импликаитную таблицу и определим ее покры

тия. Каждую ТДНФ функции / задаем в виде мографа. Выделим запрещенные

фигуры типов А и Б и построим семантические таблицы. Затем найдем и оце

ним их покрытия. В результате окажется, что тупиковая ДНФ, полученная с

помощью предложенного алгоритма минимизации, свободного от перебора всех

тупиковых ДНФ, соответствует абсолютно минимальному решению.

Рассмотрим теоретико-структурную минимизацию системы бу

левых функций F(X). В этом случае каждой многовыходной про

стой импликанте, как и простой импликанте при минимизации

одной булевой функции, соответствует полный подграф, вершины

которого взвешены идентификатором этой МПИ в мографе GM.

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

чае может быть оценен выражением (5.1). При этом производные

вычисляют только для дуг, соединяющих вершины, взвешенные

буквами тп,- и mj, для которых p(m,) = p(mj) = 0. Для простоты

опустим в выражении (5.1) постоянную частотную составляющую

и будем оценивать МПИ по формуле

г-1 г

§ 5.4. Теоретико-структурная минимизация булевых функций 427

Предложим следующую процедуру минимизации системы бу

левых функций с учетом их теоретико-структурных свойств, осно

ванную на применении оптимизирующего функционала.

1. Задаем систему булевых функций

р (х ) = {м х ),/2(х ),...,л (х )}

множествами М/, Mf. При этом

. . _ Г1 на элементах М},

\ 0 на элементах М°.

2. Находим одним из известных способов все МПИ булевых

функций и заносим их в список 7.

3. Строим матрицу Q, каждому столбцу которой соответствует

Первичный терм, строке — конституента единицы (импликанта)

/функции fi(X ) € F (X ) и

Г 1, если Xk входит в l-ю конституенту (импликаиту),

^к1 ~ \ 0 в противном случае.

4. Определяем обязательные МПИ в списке 7. Если они име-

||отся, то переходим к п. 5, вычеркивая обязательные импликанты

ИЗ списка 7. В противном случае переходим к п. 7.

5. Корректируем матрицу Q, заменяя конституенты единицы,

Покрываемые вычеркнутыми МПИ, этими МПИ.

6. Если любая строка матрицы Q представляет собой МПИ, то

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

7. По матрице Q строим частотную матрицу отношений

F = QT X Q. Таблица

8. Оцениваем каждую

МПИ, вычисляя значение

е(1). Выбираем МПИ с

Минимальным значением

^мииОО’ Выбранную МПИ

Вычеркиваем из списка 7

‘И переходим к п. 5.

9. Устраняем избыточ

ность строк в матрице Q.

^Матрица Q задает мини

мизированную систему

рулевых функций F(X ) с

учетом теоретико-струк-

турных свойств.

Пример 5.4. Задана система булевых функций F (X ) = (/ i(X ), f2(X),

:/а(Х)} (табл. 5.11).

ха Хз

Х2

Х\

h h h

0 0 0 0

1 0 1

0 1

0 0

1 0 0

0 1

0 0

1 1 1 0 1

0 1

0 0

0 1 0

0 0 1

0 0

1 1 1

1 0 0

1 0

0 1 1 0

1 0

0 1

0 0

1 1

1 0

1 1 1 0 1

1 0 0

1 1

1 1 0

1 1

0 0 1 1

1 1 1 1

428

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

2. Слисок I многовыходных простых импликант системы F(x) следующий:

/, = 0 0 —

(з),

h = 0 - 0

(3),

h - — оо

(!),

h = -0 1 -

3 ,

h = -1 0 -

(3 ,

/б = 1 -0 -

(1),

h = 1— 0

2),

h = — u

О-

h = 1— 1

u),

ho = 1 - 1 -

3),

In = 11

-----

3),

/12 = 1 1 - 1

a , 3),

/,з = 1-11

а , 3),

hi = 11-0

(2,3),

hi = 110-

I1,3),

1,в = 1-10 2,3,

I\t — -O il

1,3,

hi = 1-0 0

1,2),

(1,2,3).

1,9 = -100

(1.3),

(1,3),

/21 = 1100

В скобках указаны номера функций, рабочие точки которых покрывает со

ответствующий интервал.

3. Составляем матрицу Q, в которой каждая коясштуента единицы повто

ряется столько раз, сколько она входит в булевы функции.

4. Обязательной МПИ является имшшкаита /».

5. Заменяема матрице Q строки ООН, 0111, 1011, 1111, соответствующие

констнтуентам булевой функции fi, на многовыходную простую импликанту Д.

В результате получаем матрицу

®1

0 1 0

0 1

0 0 1 1

1 0 1 0 0 1

1 0 0 1

0 1 0

1 0 0 1 1

0 0

1 0

0 1 0

0 1

1 1

0 1 1 0

1 1

0 1 0

0 0 1

0 1

0 1 1

0 1

1 0

0 1

1 0

1 0 1

0 0 0

1 0

6. Строки матрицы с первой по последнюю ие являются МПИ. Переходим к

п. 7.

7. Частотная матрица отношений имеет вид

4 5

5 3

0 14

5 9

7 7

9 0

3 5

5 9 0

14 8 6

4 7

0 8

Хз

4 7 5 6

11 6

Хз

5 9

14 0

0 8

8. Оцениваем каждую МПИ, вычисляя значение с(Г). Для импликанты h =

= — 00 эта оценка минимальна и равна 1,55. Выбираем h = — 00 и переходим

к п. 5.

§ 5.5. Характеризация разложения графа переходов

429

5. В матрице заменяем конституенты единицы, покрытые имллнкантой

/з, этой имлликаитой. В результате получаем матрицу

1 0 1 0 1

0 1

1 0

0 1

1 0

0 1 1 0

1 0

0 1 1

1 1 0 1

0 1 1 0 1

0 0 1

0 1

0 0 1 1

1 1

1 1 0

0 1

0 1 0

0 1

1 0

0 1 0 1 1

1 0

0 1

0 1 0 1 1

0 1

0 1 0 1 1 0

0 1

0 0 0

1 0

0 0

1 0

6. Матрица содержит строки, ие являющиеся МПИ. Переходим к п. 7

и т. д.

В результате получена матрица

*г

ХЗ

Хз

0 0 0

1 О

0 1

0 0

0 1

0 0 0 1 0

0 0 1

0 0

1 О О 1

0 О О 0

которая соответствует решению

F(X) = * 1 * 2 /1 V*i*2/i V * 2 * 4 /1 V i ^ V i 2 * 4 /3 V * 2 * 3 /3 V * 3 * 4 /3 .

Определим удаленность полученного решения от минимального. Для этого

зададим каждую ТДНФ этой системы мографом и определим распределение

запрещенных фигур. Семантически эквивалентируя полученные мографы мо-

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

синтезированная ТДНФ системы булевых функций F (X ) без перебора всех экви

валентных ТДНФ соответствует абсолютно минимальному решению.

§ 5.5. Характеризация разложения графа переходов

в частичное декартово произведение

Сложность и надежность автомата во многом определяются

кодами внутренних состояний. Одной из актуальных является

задача минимизации связей между элементами памяти. Будем

считать два элемента памяти несвязными, если функция возбуж

дения одного из них не зависит от состояния другого элемента

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

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

430

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

ляется состоянием этого элемента и входным вектором:

w = ч>х{4 , х ).

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

t=i

где s — общее количество элементов памяти; а,- — количество

элементов памяти, отличных от i-го элемента, значения которых

необходимы для вычисления функции возбуждения i-го элемента

памяти.

Значение связности памяти 5, равное нулю, означает, что эле

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

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

вектором.

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

в частичное декартово произведение п функционально не связан

ных друг с другом сомножителей, каждый из которых соответ

ствует подавтомату.

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

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

дов G{. Для описания ситуаций нарушения детерминированности

введем граф сцепления Ссц, каждой вершине которого взаимно од

нозначно соответствует внутреннее состояние автомата, ребру —

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

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

автомата.

Два состояния, Sa и Sp, называются сцепленными вектором

Xi, если найдутся: набор Xi, который переводит состояние Sa в

5-у (Sa —^ S7), и набор Xj (Х{ С Xj), который переводит Sp в Ss

(Sp —U Ss), такие, что 57 ф Ss и (Sa, S7) и (Sp, Ss) не образуют

петли одновременно.

Состояние графа переходов G = (V, (U, X )) после его разложе-

нйя в частичное декартово произведение

С = Д ^ . Gi = {Vi,(Ui,X)),

можно охарактеризовать вектором, i-му разряду которого соответ-

ствует состояние г-го подавтомата. При разложении каждый подав

томат характеризуется допустимым количеством состояний |VJ|.

Очевидно, что

П IVS) > |V|.

Сцепленным состояниям должны соответствовать векторы, от

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