Dijagram binarnog momenta

**Dijagram binarnog momenta (eng. BMD)** je generalizacija binarnog dijagrama odlučivanja (eng. *BDD*) na linearne funkcije preko domena kao što su logičke, ali takođe na cele brojeve ili na realne brojeve.

Oni mogu da se bave sa Bulovim funkcijama složenosti sličnoj BDD-u, ali takođe neke funkcije se ne bave veoma efikasno sa BDD, dok lako rukuju sa BMD.

Najvažnija karakteristika BMD-a je da kao i BDD svaka funkcija ima tačno jednu kanonsku reprezentaciju, i mnoge operacije se mogu efikasno izvesti na ovim reprezentacijama.

Glavna mogućnost koja diferencira BMD od BDD-a je korišćenje linearnih umesto „*pointwise*” dijagrama, i imanje težinskih ivica.

Pravila koja obezbeđuju kanoničnost reprezentacije su :
* Odluka preko promenjivih većih u poretku mogu samo da pokazuju na odluke preko promenjivih manjih u poretku.
* Ni jedna dva čvora ne smeju biti identična
* Ni jedan čvor ne može imati sve delove odluke ekvivalentne nuli.
* Ni jedna ivica ne sme da ima težinu nula. (sve takve ivice bi trebalo zameniti direktim vezama u 0 )
* Težine ivica bi trebalo da se komprimuju. Bez ovog pravila ili nekog pravila njemu ekvivalentnom, bilo bi mogiće za funkciju da ima vise reprezentacija.

## Odvojeni i linearna dekompozicija
U odvojenoj dekompoziciji kao u BDD-u, na svaku granu mi čuvamo rezultat svih grana odvojeno. Primer takve dekompozicije za celobrojnu funkciju (2*x* + *y*) je :

:\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}

U linearnoj dekompoziciji mi dajemo umesto podrazumevane vrednosti i razlike:

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

Lako se može uočiti da je linearna reprezentacija mnogo efikasnija i slučaju aditivnih funkcija, kao kad dodamo
mnoge elemente, reprezentacija će imati samo O(n) elemenata, dok prethodna, čak sa deljenjem eksponencijalno mnogo.

## Težine ivica

Još jedno produženje je korišćenje težina za ivice. Vrednost funkcije u datom čvoru je zbir tačnih čvorova ispod njega puta težina ivica.
Na primer (4x_2 + 2x_1 + x_0) (4y_2 + 2y_1 + y_0) se može reprezentovati kao :
# Rezultujući čvor, uvek 1&times; vrednost čvora 2, ako x_2 dodaj 4&times; vrednost čvora četiri.
# Uvek 1&times; vrednost čvora 3, ako x_1 dodaj 2&times; vrednost čvora četiri.
# Uvek 0, ako x_0 dodaj 1&times; vrednost čvora 4.
# Uvek 1&times; vrednost čvora 5, ako y_2 dodaj +4.
# Uvek 1&times; vrednost čvora 6, ako y_1 dodaj +2.
# Uvek 0, ako y_0 dodaj +1.

Bez težinskih čvorova, mnogo kompleksnija reprezentacija bi bila potrebna :

# Rezultujuci čvor, uvek vrednost čvora 2, ako x_2 vrednost čvora 4.
# Uvek vrednost čvora 3, ako x_1 vrednost čvora 7.
# Uvek 0, ako x_0 vrednost čvora 10.
# Uvek vrednost čvora 5, ako y_2 dodaj +16.
# Uvek vrednost čvora 6, ako y_1 dodaj +8.
# Uvek 0, ako y_0 dodaj +4.
# Uvek vrednost čvora 8, ako y_2 dodaj +8.
# Uvek vrednost čvora 9, ako y_1 dodaj +4.
# Uvek 0, ako y_0 dodaj +2.
# Uvek vrednost čvora 11, ako y_2 dodaj +4.
# Uvek vrednost čvora 12, ako y_1 dodaj +2.
# Uvek 0, ako y_0 dodaj +1