Диаграмма двоичного момента - Википедия - Binary moment diagram

А диаграмма двоичного момента (BMD) является обобщением диаграмма двоичных решений (BDD) в линейные функции в таких областях, как логические (например, BDD), а также в целые или действительные числа.

Они могут иметь дело с логическими функциями со сложностью, сопоставимой с BDD, но также некоторые функции, которые очень неэффективно используются в BDD, легко обрабатываются BMD, в первую очередь умножение.

Наиболее важные свойства BMD заключаются в том, что, как и в случае с BDD, каждая функция имеет ровно одно каноническое представление, и с этими представлениями можно эффективно выполнять множество операций.

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

Правила, обеспечивающие каноничность изображения:

  • Решение по переменным выше по порядку может указывать только на решения по переменным ниже по порядку.
  • Никакие два узла не могут быть идентичными (при нормализации таких узлов все ссылки на один из этих узлов должны быть заменены ссылками на другой)
  • Ни один узел не может иметь все части решения, эквивалентные 0 (ссылки на такие узлы должны быть заменены ссылками на их всегда часть)
  • Ни одно ребро не может иметь нулевой вес (все такие ребра следует заменить прямыми ссылками на 0)
  • Вес краев должен быть совмещать. Без этого правила или его эквивалента функция могла бы иметь много представлений, например 2Икс + 2 можно представить как 2 · (1 +Икс) или 1 · (2 ​​+ 2Икс).

Поточечная и линейная декомпозиция

При поточечной декомпозиции, как и в BDD, в каждой точке ветвления мы сохраняем результат всех ветвей отдельно. Пример такого разложения для целочисленной функции (2Икс + у) является:

В линейной декомпозиции вместо этого мы предоставляем значение по умолчанию и разницу:

Легко видеть, что последнее (линейное) представление намного эффективнее в случае аддитивных функций, так как при добавлении большого количества элементов последнее представление будет иметь только O (п) элементов, а у первых (точечных) даже с разделением экспоненциально много.

Краевые веса

Другое расширение использует утяжелители для краев. Значение функции в данном узле - это сумма истинных узлов ниже него (узел всегда ниже и, возможно, решенный узел), умноженных на веса ребер.

Например, можно представить как:

  1. Узел результата, всегда 1 × значение узла 2, если добавить 4 × значение узла 4
  2. Всегда 1 × значение узла 3, если добавить 2 × значение узла 4
  3. Всегда 0, если добавить 1 × значение узла 4
  4. Всегда 1 × значение узла 5, если добавить +4
  5. Всегда 1 × значение узла 6, если добавить +2
  6. Всегда 0, если добавить +1

Без взвешенных узлов потребовалось бы гораздо более сложное представление:

  1. Узел результата, всегда значение узла 2, если значение узла 4
  2. Всегда значение узла 3, если значение узла 7
  3. Всегда 0, если значение узла 10
  4. Всегда значение узла 5, если добавить +16
  5. Всегда значение узла 6, если добавить +8
  6. Всегда 0, если добавить +4
  7. Всегда значение узла 8, если добавить +8
  8. Всегда значение узла 9, если добавить +4
  9. Всегда 0, если добавить +2
  10. Всегда значение узла 11, если добавить +4
  11. Всегда значение узла 12, если добавить +2
  12. Всегда 0, если добавить +1

Рекомендации