Определение 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). В результате вычитания получим L1=L#Е.

Таблица 21

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

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

Z=Z-E= .

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

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

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

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

Z

Таблица 22  
     
  а 00х0  
  b 000х Сa = Cb

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

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

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

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

 

 

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

 








Дата добавления: 2016-01-09; просмотров: 628;


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.006 сек.