バイナリモーメント図

バイナリモーメントダイアグラム（BMD）は、バイナリ決定ダイアグラム（BDD）をブール値などのドメイン上の線形関数（BDDなど）だけでなく、整数や実数にも一般化したものです。 ^{[1] [2]}

これらは、BDD に匹​​敵する複雑さでブール関数を処理できますが、BDD では非常に非効率的に処理される一部の関数、特に乗算も BMD では簡単に処理できます。

BMD の最も重要な特性は、BDD と同様に、各関数には正確に 1 つの標準表現があり、これらの表現に対して多くの操作を効率的に実行できることです。

BMD と BDD を区別する主な特徴は、点ごとの図ではなく線形図を使用し、重み付きエッジを持つことです。

表現の正統性を保証するルールは次のとおりです。

• 順序付けの上位にある変数に関する決定は、順序付けの下位にある変数に関する決定のみを指す場合があります。
• 2 つのノードが同一であってはなりません (正規化では、このようなノードの 1 つへのすべての参照を別のノードへの参照に置き換える必要があります)
• すべての決定部分が 0 に等しいノードは存在しません (そのようなノードへのリンクは、常に一致する部分へのリンクに置き換えられます)
• エッジの重みが 0 であってはなりません (そのようなエッジはすべて 0 への直接リンクに置き換えられます)
• 辺の重みは互いに素でなければなりません。この規則またはそれと同等の規則がなければ、関数が複数の表現を持つ可能性があります。たとえば、2 x + 2 は 2 · (1 + x ) または 1 · (2 + 2 x ) として表すことができます 。

BDD と同様に、点ごとの分解では、各分岐点にすべての分岐の結果を個別に保存します。整数関数 (2 x  +  y ) のこのような分解の例は次のとおりです。

${\displaystyle {\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}}}$

線形分解では、代わりにデフォルト値と差を提供します。

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

後者（線形）表現は加法関数の場合にははるかに効率的であることが容易にわかります。多くの要素を追加すると、後者の表現には O( n ) 個の要素しか含まれませんが、前者（点単位）では、共有しても指数的に多くの要素が含まれるからです。

もう 1 つの拡張は、エッジの重みを使用することです。特定のノードでの関数の値は、その下の実際のノード (常にその下のノード、場合によっては決定されたノード) の合計にエッジの重みを掛けたものです。

たとえば、次のように表すことができます。 ${\displaystyle (4x_{2}+2x_{1}+x_{0})(4y_{2}+2y_{1}+y_{0})}$

1. 結果ノード、常にノード2の1倍の値、ノード4の4倍の値を追加する場合${\displaystyle x_{2}}$
2. 常にノード3の1倍の値、ノード4の2倍の値を追加する場合${\displaystyle x_{1}}$
3. ノード4の1×値を追加すると常に0になります${\displaystyle x_{0}}$
4. 常にノード5の1倍の値、+4を追加する場合${\displaystyle y_{2}}$
5. 常にノード6の1倍の値、+2を追加する場合${\displaystyle y_{1}}$
6. 常に0、+1を追加する場合${\displaystyle y_{0}}$

重み付けされたノードがなければ、はるかに複雑な表現が必要になります。

1. 結果ノード、常にノード2の値、ノード4の値の場合${\displaystyle x_{2}}$
2. ノード7の値の場合は常にノード3の値${\displaystyle x_{1}}$
3. ノードの値が10の場合は常に0${\displaystyle x_{0}}$
4. 常にノード5の値、+16を追加する場合${\displaystyle y_{2}}$
5. 常にノード6の値、+8を追加する場合${\displaystyle y_{1}}$
6. 常に0、+4を追加する場合${\displaystyle y_{0}}$
7. 常にノード8の値、+8を追加する場合${\displaystyle y_{2}}$
8. 常にノード9の値、+4を追加する場合${\displaystyle y_{1}}$
9. 常に0、+2を加える場合${\displaystyle y_{0}}$
10. 常にノード11の値、+4を追加する場合${\displaystyle y_{2}}$
11. 常にノード12の値、+2を追加する場合${\displaystyle y_{1}}$
12. 常に0、+1を追加する場合${\displaystyle y_{0}}$