Минимизация системы булевых функций. Синтез ПЛМ с заданной выходной матрицей, страница 6

Для каждого из этих миноров находится далее соответствующая пара столбцов матричной системы (X*, У*), реализующей исходную систему (X, Y). В матрицу Y* при этом вводится столбец, задающий строки минора, а в матрицу X* — столбец, представляющий минимальный покрывающий интервал для соответствующих столбцов матрицы X. Так получается решение

X*  =

0

1

---

0

1

Y*  =

1

0

0

0

1

---

---

---

1

2

0

0

1

1

2

---

1

1

0

3

0

1

1

0

3

1

---

---

---

4

1

1

0

0

4

0

---

1

---

5

1

0

0

1

5

0

1

0

0

6


упрощаемое затем описанным выше методом минимизации числа единиц и нулей в матрице X* до следующего ее значения.

---

1

---

---

---

---

---

1

---

1

1

0

1

---

---

---

0

---

1

---

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

Поиск приближений к оптимальному решению. С ростом числа столбцов в матрицах Х и Y нахождение точного решения рассматриваемой задачи может стать практически невозможным из-за огромного числа различных интервальных миноров системы (X, Y). В этом случае приходится отказываться от рассмотрения всех их и переходить к конструированию некоторых приближений к кратчайшей ДНФ.

При оценке качества получаемых при этом решений можно ориентироваться на такой параметр системы, как число элементов в кратчайшем минорном покрытии матрицы Y. Очевидно, что число столбцов в матрицах X* и Y*, реализующих систему (X, Y), не может быть меньше этого параметра.

По аналогии с методами минимизации одной булевой функции методы минимизации системы (X, Y) можно разбить на два класса, включив в первый из них такие, когда интервальные миноры, из которых конструируется решение, находятся последовательно, а во второй — параллельно.

В первом случае в матрице Y выбирается некоторый элемент и рассматривается как элементарный минор, и этот минор расширяется до некоторого максимального интервального минора, покрывающего часть единичных элементов матрицы Y. Затем выбирается один из оставшихся непокрытыми элементов, находится новый минор, и так до тех пор, пока не будет получено некоторое минорное покрытие матрицы Y. Во втором случае параллельно ве-


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

Очевидно, что выбор элементов, миноров и конкретных шагов расширения минора должен производиться каждый раз каким-то «достаточно оптимальным» образом. Используемые с этой целью критерии выбора могут быть весьма разнообразны.

Рассмотрим один из методов минимизации системы (X, Y), относящийся к первому классу, иллюстрируя его по ходу изложения на следующем нетривиальном примере: