шпорки) , 1ый семестр (Луцик Ю) / 33 Минизация переключ ф-ций Рота (после L-экстремал)

33 Минизация переключ ф-ций Рота (после L-экстремал)
1.Если результат вычисления будет ? хотя бы в одном, любом случае, то это значит, что среди простых импликант есть такие кубы, которые покрывают уменьшаемый, а следовательно, этот уменьшаемый не может быть L-экстре-малью.
2.Если полученный результат не ?, то в противоположность предыдущему утверждению уменьшаемый куб оказывается кубом большей размерности по отношению к другим простым импликантам.
3.Что касается простых импликант, "удаленных" от уменьшаемой, то они с ней дают координаты "y" и, таким образом, остается уменьшаемый куб при вычитании этих "удаленных" кубов.
После выявления L-экстремалей следует выяснить, не являются ли некоторые из них простыми импликантами, остатки которых покрывают только некоторое подмножество кубов комплекса N, которое нет необходимости покрывать, вводя в минимальное покрытие соответствующие наборы. Для этого необходимо выполнить операцию пересечения остатков, полученных при выполнении операции z#(Z-z) с кубами из комплекса L. Во множестве E необходимо оставить только те кубы, остатки от которых пересекаются с кубами из комплекса L.
z#(Z-z)?L 1x01 x101 1x10 x110
x010 ? ? 1010 ?
0x10 ? ? 1010 ?
0000 ? ? ? 0110
0x01 ? 1101 ? ?
Из таблицы видно, что куб 1x01 не пересекается с кубами комплекса L. Однако куб x101 имеет с кубом 0x01 (из комплекса L) общую вершину 0101. Оба куба (1x01, x101) входят в куб более высокой размерности xx01(L-экстремаль). Таким образом, куб 1x01, образованный на комплексе N, позволил уменьшить цену схемы. Выясним далее, какие из вершин комплекса L не покрываются L-экстремалями. Для этого из каждого куба комплекса L вычтем (#) элементы множества Е В результате вычитания получим L1=L#Е.
L#Е x010 0x10 0000 0x01
xx01 zzyy
x010 zzyy
0x10 zzzy
0000 zzzz
?
xx10 zzzz
? zzzz
? zzyz
0000 ?
? ? 0000 ?
Из таблицы видно, что L1={0000}. Однако не покрытые L-экстремалями кубы должны быть покрыты другими импликантами из множества.
Z=Z-E= .
Теперь из полученного множества Z надо выбрать минимальное число кубов с минимальной ценой (максимальной размерностью), чтобы покрыть непокрытые L-экстремалями элементы комплекса L. Выбор так называемого немах куба осуществляется с помощью операции частичного упорядочивания кубов Куб a будет немах по отношению к кубу b, если выполняются одновременно два условия:
1) Сa ? Cb, где Са - цена куба а;
2) a ? L1 b ? L1, куб b покрывает не меньше кубов чем куб а.Z
? 0000
а 00х0 0000
b 000х 0000 Сa = Cb
Следовательно, кубы а и b равноценны и для покрытия вершины 0000 можно выбрать любой из них в качестве экстремали второго порядка
Е 2={000x} или E 2={00x0}.
Следовательно, могут быть получены две тупиковые формы.
- первая тупиковая форма - вторая тупиковая форма.