Диаграмма двоичных моментов

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

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

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

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

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

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

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

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

{\begin{cases}{\text{if }}x{\begin{cases}{\text{if }}y,3\\{\text{if }}\neg y,2\end{cases}}\\{\text{if }}\neg x{\begin{cases}{\text{if }}y{\text{ , }}1\\{\text{if }}\neg y{\text{ , }}0\end{cases}}\end{cases}}

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

{\begin{cases}{\text{always}}{\begin{cases}{\text{always }}0\\{\text{if }}y,+1\end{cases}}\\{\text{if }}x,+2\end{cases}}

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

Краевые веса

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

Например, $(4x_{2}+2x_{1}+x_{0})(4y_{2}+2y_{1}+y_{0})$ можно представить как:

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

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

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

Ссылки

^ Наканиси, Масаки; Хамагути, Киёхару; Касивабара, Тошинобу (25 мая 1999 г.). «Экспоненциальная нижняя граница размера двоичной диаграммы моментов, представляющей целое число» . IEICE Transactions по основам электроники, связи и информатики . Е82-А (5): 756–766. ISSN 0916-8508 .
^ Сасао, Т.; Нагаяма, С. (май 2006 г.). «Представления элементарных функций с помощью двоичных диаграмм моментов» . 36-й Международный симпозиум по многозначной логике (ISMVL'06) . п. 28. дои : 10.1109/ISMVL.2006.37 . ISBN 0-7695-2532-6 . S2CID 11622605 .

[1] Наканиси, Масаки; Хамагути, Киёхару; Касивабара, Тошинобу (25 мая 1999 г.). «Экспоненциальная нижняя граница размера двоичной диаграммы моментов, представляющей целое число» . IEICE Transactions по основам электроники, связи и информатики . Е82-А (5): 756–766. ISSN 0916-8508 .

[2] Сасао, Т.; Нагаяма, С. (май 2006 г.). «Представления элементарных функций с помощью двоичных диаграмм моментов» . 36-й Международный симпозиум по многозначной логике (ISMVL'06) . п. 28. дои : 10.1109/ISMVL.2006.37 . ISBN 0-7695-2532-6 . S2CID 11622605 .

[1]

[2]