Дијаграм бинарног момента

Дијаграм бинарног момента је генерализација бинарног дијаграма одлучивања (енг. БДД) на линеарне функције преко домена као што су логичке, али такође на целе бројеве или на реалне бројеве.

Они могу да се баве са Буловим функцијама сложености сличној БДД-у, али такође неке функције се не баве веома ефикасно са БДД, док лако рукују са БМД.

Најважнија карактеристика БМД-а је да као и БДД свака функција има тачно једну канонску репрезентацију и многе операције се могу ефикасно извести на овим репрезентацијама.

Главна могућност која диференцира БМД од БДД-а је коришћење линеарних уместо "pointwise" дијаграма и постојање тежинских ивица.

Правила која обезбеђују каноничност репрезентације су :

• Одлука преко промењивих већих у поретку могу само да показују на одлуке преко промењивих мањих у поретку.
• Ни једна два чвора не смеју бити идентична
• Ни један чвор не може имати све делове одлуке еквивалентне нули.
• Ни једна ивица не сме да има тежину нула. (све такве ивице би требало заменити директим везама у 0 )
• Тежине ивица би требало да се компримују. Без овог правила или неког правила њему еквивалентном , било би могиће за функцију да има висе репрезентација.

Одвојени и линеарна декомпозиција

У одвојеној декомпозицији као у БДД-у , на сваку грану ми чувамо резултат свих грана одвојено. Пример такве декомпозиције за целобројну функцију (2x + 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}}$

Лако се може уочити да је линеарна репрезентација много ефикаснија у случају адитивних функција, као кад додамо многе елементе, репрезентација ће имати само О(н) елемената, док претходна, чак са дељењем експоненцијално много.

Тежине ивица

Још једно продужење је коришћење тежина за ивице. Вредност функције у датом чвору је збир тачних чворова испод њега пута тежина ивица. На пример $(4x_{2}+2x_{1}+x_{0})(4y_{2}+2y_{1}+y_{0})$ се може репрезентовати као :

1. Резултујуци цвор, увек 1× вредност чвора 2 , ако $x_{2}$ додај 4× вредност чвора четири.
2. Увек 1× вредност чвора 3, ако $x_{1}$ додај 2× вредност чвора четири.
3. Увек 0 , ако $x_{0}$ додај 1× вредност чвора 4.
4. Увек 1× вредност чвора 5, ако $y_{2}$ додај +4.
5. Увек 1× вредност чвора 6, ако $y_{1}$ додај +2.
6. Увек 0 , ако $y_{0}$ додај +1.

Без тежинских чворова, много комплекснија репрезентација би била потребна :

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