Нахождение множества простых импликант

Преобразование исходного покрытия С₀ комплекса К в множество простых импликант Z осуществляется с помощью операции умножения кубов.В результате первого шага (С₀*С₀) (табл. 16) предусматривается выявление как новых кубов С_y (первой и более высокой размерности), так и кубов, которые не образуют новых кубов (включаются в множество Z₀). Из полученных новых кубов образуется множество А₁. Также формируется множество В₁=С₀-Z₀. Для следующего шага получения множества Z формируется множество С₁=А₁U В₁. Для уменьшения мощности множества кубов С₁ выполним операцию поглощения (удаления) кубов, образующих множество С₁, кубами из множества А₁ (А₁ÍС₁).

Таблица 16

	С0*С0	х010	0х10		0х01		1x10
	х010	-
	0х10		-
		00у0	00у0	-
	0х01	ø	ø	000у	-
		1у10	у110	ø	ø	-
	1х01	ø	ø	ø	ух01	ø	-
	А1	00х0	х110	000х	хх01
	1х10

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

00х0

1х10

00х0 000х А₁ 00х0

1х10 х110 1х10

А₁ = х110 хх01 после выполнения 000х

000х С₁= х010 Þ операции Þ С₁= х110

хх01 0х10 поглощения хх01

0000 В₁ х010

Z₀=Ø 0х01 0х10

1х01

Среди кубов С₀, возможно, находятся такие кубы, которые с кубами множества А₁ могут дать новые кубы или оказаться простыми импликантами после второго шага (С₁*С₁). При формировании таблицы для выполнения операции С₁*С₁ (табл. 17) следует учесть, что В₁*В₁ уже выполнялось на шаге С₀*С₀. Следовательно,

С₁*С₁=(А₁UВ₁)*(А₁UВ₁)=(А₁*А₁)U(А₁*В₁)U(В₁*А₁)U(В₁*В₁)=(А₁*А₁)U(А₁*В₁).

Таблица 17

	С1*С1	00х0	1х10	000х	х110	хх01
	00х0	-
	1х10	у010	-
	000х		ø	-
	х110	0у10		ø	-
	хх01	000у	ø		ø	-
	х010			00у0	ху10	Ø
	0х10		ух10	00у0		Ø
	А2	ø	хх10	ø	хх10	Ø

В результате выполнения умножения С₁*С₁ получим:

А₂={хх10},

Z1=

00х0 _.

000х

Необходимо отметить, что куб хх01 не дал нового куба. Но это куб второй размерности и новые кубы может дать на третьем шаге (С₂*С₂). Поэтому его не следует включать в число кубов, образующих множество Z₁.

1х10 хх10

х110 1х10

=

C2=А2UB2=

В₂ = хх01, х110 хх10 _.

х010 х010 хх01

0х10 0х10

хх01

 

Таблица 18

	С2*С2	хх10
	хх10	-
	хх01	Ø
	А3	Ø

Таким образом, получим А₃= Ø, следовательно, новых кубов нет.

Z2=

хх10 _.

хх01

В₃=С₂-Z₂= Ø; C₃=A₃UB₃= Ø.

На этом процесс выявления простых импликант окончен.

,

00х0

- сформированное множество простых импликант.

Z=Z0UZ1UZ2=

000х

хх01

хх10

Необходимо выяснить, не содержатся ли в этом множестве “лишние” простые импликанты.

Определение L-экстремалей

Множество Z может быть избыточным. Прежде всего необходимо выявить обязательные простые импликанты, называемые в алгоритме извлечения L-экстремалями. L-экстремаль – это куб, который (и только он) покрывает некоторую вершину из множества L, не покрываемую никаким другим кубом из множества Z.

Для определения L-экстремалей воспользуемся операциями вычитания (#) (табл. 19) и пересечения (∩) кубов (табл.20). В табл. 19 z Í Z – некоторая простая импликанта, из которой вычитаются остальные Z-z.

Таблица 19

	z#(Z-z)	00x0	000x	xx01	xx10
	00х0	-	zzz1	11zy xx01	11zz 1x10 x110
	000х	zz1z	-	11zz 1x01 x101	y1yz 1x10 1yyz x110
	xх01	zzyy	zzzz ø	-
	xх10	zzzz ø	ø	zzyy 1x01 zzyy x101	-
	Остаток	ø	ø	1x01 x101	1x10 x110

Таким образом, из таблицы получено множество L-экстремалей.

.

1. Если результат вычисления будет Ø хотя бы в одном, любом случае, то это значит, что среди простых импликант есть такие кубы, которые покрывают уменьшаемый, а следовательно, этот уменьшаемый не может быть L-экстре-малью.

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

3. Что касается простых импликант, ”удаленных” от уменьшаемой, то они с ней дают координаты ”y” и, таким образом, остается уменьшаемый куб при вычитании этих ” удаленных” кубов.

После выявления L-экстремалей следует выяснить, не являются ли некоторые из них простыми импликантами, остатки которых покрывают только некоторое подмножество кубов комплекса N, которое нет необходимости покрывать, вводя в минимальное покрытие соответствующие наборы. Для этого необходимо выполнить операцию пересечения остатков, полученных при выполнении операции z#(Z-z) с кубами из комплекса L. Во множестве E необходимо оставить только те кубы, остатки от которых пересекаются с кубами из комплекса L.

Таблица 20

	z#(Z-z)∩L	1x01	x101	1x10	x110
	x010	ø	ø		ø
	0x10	ø	ø		ø
		ø	ø	ø
	0x01	ø		ø	ø

Из таблицы видно, что куб 1x01 не пересекается с кубами комплекса L. Однако куб x101 имеет с кубом 0x01 (из комплекса L) общую вершину 0101. Оба куба (1x01, x101) входят в куб более высокой размерности xx01 (L-экстремаль). Таким образом, куб 1x01, образованный на комплексе N, позволил уменьшить цену схемы. Выясним далее, какие из вершин комплекса L не покрываются L-экстрема­лями. Для этого из каждого куба комплекса L вычтем (#) элементы множества Е (табл.21). В результате вычитания получим L₁=L#Е.

Таблица 21

	L#Е	x010	0x10		0x01
	xx01	zzyy x010	zzyy 0x10	zzzy	zzzz ø
	xx10	zzzz ø	zzzz ø	zzyz	ø
		ø	ø		ø

Из таблицы видно, что L₁={0000}. Однако не покрытые L-экстремалями кубы должны быть покрыты другими импликантами из множества.

Z=Z-E= .

Теперь из полученного множества Z надо выбрать минимальное число кубов с минимальной ценой (максимальной размерностью), чтобы покрыть непокрытые L-экстремалями элементы комплекса L. Выбор так называемого немаксимального куба осуществляется с помощью операции частичного упорядочивания кубов (табл. 22).

Куб a будет немаксимален по отношению к кубу b, если выполняются одновременно два условия:

1) С^a ≥ C^b, где С^а – цена куба а;

2) a ∩ L₁ Í b ∩ L₁, куб b покрывает не меньше кубов чем куб а.

Z

Таблица 22
		∩
	а	00х0
	b	000х		С^a= C^b

Следовательно, кубы а и b равноценны и для покрытия вершины 0000 можно выбрать любой из них в качестве экстремали второго порядка

Е¢₂={000x} или E¢¢₂={00x0}.

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

- первая тупиковая форма (рис. 30).

 

 

- вторая тупиковая форма.

 

Минимизация ФАЛ методом преобразования логических выражений

Рассмотрим подход к упрощению ФАЛ, заключающийся в применении к ней скобочных преобразований. Пусть имеется функция

f=x₁x₃x₄x₆+x₂x₃x₄x₆ + x₅x₆ + x₇.

Применим к ней скобочные преобразования, в результате чего получим функцию f=((x₁+x₂)x₃x₄ + x₅)x₆ + x₇.

Из выражений видно, что цена схемы до минимизации была равна 14, после стала равна 11. Таким образом, общая стоимость схемы сократилась, однако исходной функции соответствовала схема, имеющая два уровня элементов, а преобразованной − пять уровней. Таким образом, полученная схема будет работать примерно в 2,5 раза медленнее исходной.