Математика \ Дискретная математика

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

X* =

0

0

---

1

---

1

---

---

---

0

1

1

1

---

---

---

0

---

1

---

(например, первый из них получается в результате соответствующей операции над столбцами 1 и 4 матрицы X).


Представляя соответствующие множества St вектор столбцами, образуем из них булеву матрицу

Y* =

1

0

0

0

0

1

1

0

0

0

1

1

1

0

0

1

1

1

0

0

0

0

0

1

Полученная в результате система матриц (X*, Y*), интерпретируемая как ДНФ некоторой системы булевых функций F* , реализует исходную систему (X, Y), обладая при этом минимальным числом элементарных конъюнкций. Ее можно упростить далее, применив описанный ранее метод замены значений некоторых элементов матрицы X* с 0 или 1 на «—». В данном случае этот метод приведет к следующему результату:

X* =

---

---

---

1

Y* =

1

0

0

0

---

1

---

---

0

1

1

0

---

0

1

1

0

0

1

1

1

---

---

---

1

0

0

1

0

---

1

---

1

1

0

0

0 

0

0

1

Рис. 55. Реализация системы частичных булевых функций, минимизированная по числу промежуточных полюсов.

На рис. 55 показана непосредственная схемная реализация полученной системы.

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


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

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

Продемонстрируем это на уже знакомом примере. Пусть


Скачать файл