При синтезе КС из элементов типа и, или, не.

 

Рассмотрим алгоритм построения КС с помощью скобочных преобразований.

1. Преобразуем исходную ДНФ многократно вынося за скобки переменные.

Пример.

 

 

2. Выделяем одинаковые подфункции в скобочной форме F и получаем совокупность функций для F.

 

Пример.

 

 

F = XY(Ф Ú W) Ú WФ

Ф = Z Ú PQ

 

3. Выделяем конъюнкции или их части общие для нескольких мест (одинаковые) и расширяем совокупность функций.

Пример.

F = XY(F Ú W) Ú WF Ú MN K

F = Z Ú MN P

 

F = XY(F Ú W) Ú WF Ú YK

F = Z Ú YP

Y = MN

 

При поиске и выделении общих частей конъюнкций учитывается, что выделение k букв из L конъюнкций дает выигрыш W = k(L - 1).

 

Выделяя общие части с максимумом W при W > 0, мы обеспечиваем упрощение схемы.

Далее по совокупности БФ строится КС, например, моделированием полученных выражений.

Действия по п.2 и 3 ясны. Действия по п.1 рассмотрим подробнее, полагая, что исходное выражение для F - ДНФ.

Исходную ДНФ, рассматриваемой БФ F, обозначим как D ⁰.

Делая вынесение за скобки переменных, получим

 

D ⁰ = K ⁰ &(D ⁰₁) Ú D ⁰₂

КонъюнкцияДНФ

Поиск выносимых за скобки переменных (конъюнкции) рассмотрим далее.

«Убираем» на время из рассмотрения внутри - скобочное выражение для D ⁰₁ и получаем ДНФ D ¹ .

D ¹ = K ⁰ &(F ⁰₁) Ú D ⁰₂ .

Переменная, заменяющая ДНФ D ⁰₁.

D ¹ обрабатываем как исходную ДНФ D ⁰, если возможно вынесение за скобки K ¹ и представление ее в виде

D ¹ = K ¹ &(D ¹₁) Ú D ¹₂ .

Затем аналогично получаем D ² , D ³ и т.д.

 

Если в D ^j уже нельзя выделить К ^j, то берем

D ^j = K ^j-1 &(F ^j-1₁) Ú D ^j-1₂

и подставляем туда последовательно (D ^j-1₁) вместо F ^j-1₁, (D ^j-2₁) вместо F ^j-2₁ и т.д. до (D ⁰₁) вместо F ⁰₁.

При этом мы получаем выражение, в котором в скобки заключены ДНФ D ⁰₁, D ¹₁, …D ^j-1₁.

Каждую из этих ДНФ будем обрабатывать как исходную, продолжая до тех пор, пока это возможно.

В результате получим искомую форму.

Рассмотрим пример.

К ⁰ D ⁰₁ D ⁰₂

 

К ¹ D ¹₁ D ¹₂

Дальнейшее вынесение за скобки невозможно.

Подставляя всюду D ^q₁ вместо F ^q₁, получаем

Преобразуя каждую ДНФ из скобок, получим

Полученные здесь в скобках ДНФ уже не допускают дальнейших скобочных преобразований.

Заменив преобразованные ДНФ на скобочные выражения, получим

На этом скобочные преобразования завершены.

Выделив одинаковые подфункции, мы получим

 

В результате, получаем схему.

 

Замечание о многовыходных схемах.

 

Для системы БФ, каждая функция приводится к скобочной форме отдельно. Затем во всех функциях находятся одинаковые части формул и конъюнкций и формируется общая совокупность функций.

Следует отметить, что при большом числе «похожих» конъюнкций в разных БФ, лучшие результаты может дать другой подход.

 

1) В совокупности всех БФ выделяются общие части и заменяются новыми переменными;

2) БФ (с новыми переменными, если они введены) раздельно обрабатываются описанным ранее способом;

3) Введенные в 1) переменные реализуются схемами.

 

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

 

Выясним теперь, как в днф D ^j найти конъюнкцию K ^j, чтобы, вынеся ее за скобки, получить D ^j = K ^j &(D ^j ₁) Ú D ^j₂

Обозначим (K ⁱ) _J совокупность первых j букв в K ⁱ.

Весом W(K ⁱ) _J для (K ⁱ) _J назовем

 

W[(K ⁱ) _J ] = j ^. (L _k- 1),

где L _k - число конъюнкций в D ⁱ, содержащих (K ⁱ) _J.

 

K ⁱ строим, последовательно находя (K ⁱ) ₁, (K ⁱ) ₂, …так, чтобы вес W для (K ⁱ) _J всякий раз был наибольшим и больше нуля.

Переходя к (K ⁱ) _J нужно подобрать к (K ⁱ) _J-1 такую переменную, чтобы вес (K ⁱ) _J был наибольшим.

Отбор переменных к (K ⁱ) идет до тех пор, пока вес (K ⁱ) _J не начнет убывать.

 

Рассмотрим пример.

D ⁱ = X1X2X3ÚX1X2X4ÚX1X5ÚX2X5

 

	X1	W=2 - max	(Ki)1 = x1
	X2	W=2
(Ki)1 =	X3	W=0
	X4	W=0
	X5	W=1
	X1X2	W=2 - max	(Ki)2 = X1X2
(Ki)2 =	X1X3	W=0
	X1X4	W=0
	X1X5	W=0
	X1X2X3	W=0
(Ki)3 =	X1X2X4	W=0
	X1X2X5	W=0

 

В итоге получаем

D ⁱ = X1X2(X3ÚX4)ÚX1X5ÚX2X5

К ⁱ D ⁱ₁ D ⁱ₂

Схема, построенная по этому выражению, будет содержать 4 двухвходовых конъюнктора.

Схема для исходной ДНФ содержит 6 двухвходовых конъюнкторов.

Вес W для K ⁱ равен числу конъюнкторов, которые могут быть удалены из КС для ДНФ D ⁱ после перехода к КС для D ⁱ в виде

D ⁱ = K ⁱ &(D ⁱ₁) Ú D ⁱ₂

 

СИНТЕЗ КС ИЗ ЭЛЕМЕНТОВ

И-НЕ, ИЛИ-НЕ, И-ИЛИ-НЕ.

КС часто используемых БФ.

 

Наиболее часто используемыми БФ являются конъюнкция, дизъюнкция, сумма «по модулю 2» и инверсия.

 

F = X1&X2& … &Xn

F = X1ÚX2Ú… ÚXn

F = X1 X2 … Xn

F = X1oX2o…oXn

 

где o - либо &, либо Ú, либо .

Существует набор стандартных решений для построения БФ.

Для этого используются следующие правила:

Для &, и имеется свойство ассоциативности:

возможность произвольной расстановки скобок в формуле

F = X1oX2o…oXn

 

Например:

F = X1oX2o…oXn = X1o(X2(o…oXn))= (X1oX2)o(…oXn)

 

В зависимости от того, как расставляются скобки, можно получить выражение, задающее КС последовательной, пирамидальной или смешанной структуры.

Последовательная структура.

 

;

N - число переменных; К - число входов ЛЭ;

Г - глубина КС; S - число ЛЭ в КС.

 

Пирамидальная структура.

,

 

Смешанная структура.

 

Мы увидели, как построить КС с n входами из ЛЭ (либо «блоков») с К входами, реализующими такие же функции, что и вся КС. Обратимся теперь к построению «блоков».

 

 

Рассмотрим типы используемых ЛЭ и их обозначения.

 

 

ЛЭ И - ИЛИ - НЕ таков, что из него путем подстановки констант или отождествления входов можно получать ЛЭ типа И - НЕ либо ИЛИ - НЕ.

Покажем это.

 

 

Рассмотрим способы получения инверторов из элементов И-НЕ, ИЛИ-НЕ, И-ИЛИ-НЕ.

 

 

Рассмотрим способы получения конъюнкции из элементов И-НЕ, ИЛИ-НЕ, И-ИЛИ-НЕ.

Получение конъюнкции из элементов И-НЕ.

 

 

Получение конъюнкции из элементов ИЛИ-НЕ.

 

 

Получение конъюнкции из элементов И-НЕ и ИЛИ-НЕ.

 

Получение конъюнкции из элементов И-ИЛИ-НЕ.

 

Рассмотрим примеры получения конъюнкций.

 

 

 

 

 

 

 

 

Получение дизъюнкции из элементов ИЛИ-НЕ.

 

 

 

Получение дизъюнкции из элементов И-НЕ и ИЛИ-НЕ.

 

Получение дизъюнкции из элементов И-ИЛИ-НЕ.

Рассмотрим примеры получения дизъюнкций.

Теперь рассмотрим схемы для получения суммы по модулю два.

 

X	Y

 

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

Первый способ – на элементах И-НЕ.

 

 

Второй способ – на элементах ИЛИ-НЕ.

 

 

Третий способ – на элементе И-ИЛИ-НЕ.

 

 

 

Рассмотрим использование выражений вида И - ИЛИ.

 

F=(X₁&…&X_P) (Y₁&…&Y_P) … (W₁&…&W_P)

 

 

Рассмотрим примеры реализации выражений И-ИЛИ.

 

 

 

КС ДЛЯ ПРОИЗВОЛЬНЫХ БФ.

Процедура построения КС состоит из трех этапов:

1. Строится схема из элементов И, ИЛИ, НЕ.

2. Отдельные части схемы вида И - ИЛИ, либо И, либо ИЛИ переводятся в схемы из заданных ЛЭ (см. раздел 2.3.1).

3. Полученная КС корректируется с целью устранения возможной избыточности, например, вида

или нахождения общих частей.