2.2. Использование скобочных преобразований днф при синтезе кс из элементов типа и, или, не.
Рассмотрим алгоритм построения КС с помощью скобочных преобразований.
Преобразуем исходную ДНФ многократно вынося за скобки переменные.
Пример.
Выделяем одинаковые подфункции в скобочной форме F и получаем совокупность функций для F.
Пример.
F
= XY(Ф
W)
WФ
Ф = Z PQ
Выделяем конъюнкции или их части общие для нескольких мест (одинаковые) и расширяем совокупность функций.
Пример.
F
=
XY(W)
W
Z MNP
F
=
XY(W)
W
Z P
При поиске и выделении общих частей конъюнкций учитывается, что выделение k букв из L конъюнкций дает выигрыш W = k(L-1).
Выделяя общие части с максимумом W при W > 0, мы обеспечиваем упрощение схемы.
Далее по совокупности БФ строится КС, например, моделированием полученных выражений.
Действия по п.2 и 3 ясны. Действия по п.1 рассмотрим подробнее, полагая, что исходное выражение для F - ДНФ.
Исходную ДНФ, рассматриваемой БФ F, обозначим как D0.
Делая вынесение за скобки переменных, получим
D
0
= K0&(D
01)
D02
Конъюнкция ДНФ
Поиск выносимых за скобки переменных (конъюнкции) рассмотрим далее.
«Убираем» на время из рассмотрения внутри-скобочное выражение для D 01 и получаем ДНФ D 1 .
D 1 = K0&(F 01) D02 .
Переменная, заменяющая ДНФ D 01 .
D 1 обрабатываем как исходную ДНФ D0 , если возможно вынесение за скобки K1 и представление ее в виде
D 1 = K1&( D 11) D12 .
Затем аналогично получаем D 2 , D 3 и т.д.
Если в Dj уже нельзя выделить Кj , то берем
D j = Kj-1&(F j-11) Dj-12
и подставляем туда последовательно (D j-11) вместо F j-11, (D j-21) вместо F j-21 и т.д. до (D 01) вместо F 01.
При этом мы получаем выражение, в котором в скобки заключены ДНФ D 01, D 11, …D j-11.
Каждую из этих ДНФ будем обрабатывать как исходную, продолжая до тех пор, пока это возможно.
В результате получим искомую форму.
Рассмотрим пример.
К0 D 01 D02
К1 D11 D12
Дальнейшее вынесение за скобки невозможно.
Подставляя всюду D q1 вместо F q1, получаем
Преобразуя каждую ДНФ из скобок, получим
Полученные здесь в скобках ДНФ уже не допускают дальнейших скобочных преобразований.
Заменив преобразованные ДНФ на скобочные выражения, получим
На этом скобочные преобразования завершены.
Выделив одинаковые подфункции, мы получим
В результате, получаем схему.
Замечание о многовыходных схемах.
Для системы БФ, каждая функция приводится к скобочной форме отдельно. Затем во всех функциях находятся одинаковые части формул и конъюнкций и формируется общая совокупность функций.
Следует отметить, что при большом числе «похожих» конъюнкций в разных БФ, лучшие результаты может дать другой подход.
В совокупности всех БФ выделяются общие части и заменяются новыми переменными;
БФ (с новыми переменными, если они введены) раздельно обрабатываются описанным ранее способом;
Введенные в 1) переменные реализуются схемами.
При синтезе многовыходных схем удобно строить схемы, используя поочередно оба подхода, и выбирать лучшую.
Выясним теперь, как в днф D j найти конъюнкцию Kj , чтобы, вынеся ее за скобки, получить D j = Kj&( D j 1) Dj2
Обозначим (Ki)J совокупность первых j букв в Ki.
Весом W(Ki)J для (Ki)J назовем
W[(Ki)J ] = j. (Lk-1),
где Lk - число конъюнкций в D i, содержащих (Ki)J.
Ki строим, последовательно находя (Ki)1, (Ki)2, …так, чтобы вес W для (Ki)J всякий раз был наибольшим и больше нуля.
Переходя к (Ki)J нужно подобрать к (Ki)J-1 такую переменную, чтобы вес (Ki)J был наибольшим.
Отбор переменных к (Ki) идет до тех пор, пока вес (Ki)J не начнет убывать.
Рассмотрим пример.
Di = X1X2X3X1X2X4X1X5X2X5
|
X1 |
W=2 - max |
i)1 = x1 |
|
X2 |
W=2 |
|
i)1 = |
X3 |
W=0 |
|
|
X4 |
W=0 |
|
|
X5 |
W=1 |
|
|
X1X2 |
W=2 - max |
i)2 = X1X2 |
i)2 = |
X1X3 |
W=0 |
|
|
X1X4 |
W=0 |
|
|
X1X5 |
W=0 |
|
|
X1X2X3 |
W=0 |
|
i)3 = |
X1X2X4 |
W=0 |
|
|
X1X2X5 |
W=0 |
В итоге получаем
Di = X1X2(X3X4)X1X5X2X5
Кi Di1 Di2
Схема, построенная по этому выражению, будет содержать 4 двухвходовых конъюнктора.
Схема для исходной ДНФ содержит 6 двухвходовых конъюнкторов.
Вес W для Ki равен числу конъюнкторов, которые могут быть удалены из КС для ДНФ D i после перехода к КС для D i в виде
D i = Ki&( D i1) Di2