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 (2x + 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 :

1. Rezultujući čvor, uvek 1× vrednost čvora 2, ako $x_{2}$ dodaj 4× vrednost čvora četiri.
2. Uvek 1× vrednost čvora 3, ako $x_{1}$ dodaj 2× vrednost čvora četiri.
3. Uvek 0, ako $x_{0}$ dodaj 1× vrednost čvora 4.
4. Uvek 1× vrednost čvora 5, ako $y_{2}$ dodaj +4.
5. Uvek 1× vrednost čvora 6, ako $y_{1}$ dodaj +2.
6. Uvek 0, ako $y_{0}$ dodaj +1.

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

1. Rezultujuci čvor, uvek vrednost čvora 2, ako $x_{2}$ vrednost čvora 4.
2. Uvek vrednost čvora 3, ako $x_{1}$ vrednost čvora 7.
3. Uvek 0, ako $x_{0}$ vrednost čvora 10.
4. Uvek vrednost čvora 5, ako $y_{2}$ dodaj +16.
5. Uvek vrednost čvora 6, ako $y_{1}$ dodaj +8.
6. Uvek 0, ako $y_{0}$ dodaj +4.
7. Uvek vrednost čvora 8, ako $y_{2}$ dodaj +8.
8. Uvek vrednost čvora 9, ako $y_{1}$ dodaj +4.
9. Uvek 0, ako $y_{0}$ dodaj +2.
10. Uvek vrednost čvora 11, ako $y_{2}$ dodaj +4.
11. Uvek vrednost čvora 12, ako $y_{1}$ dodaj +2.
12. Uvek 0, ako $y_{0}$ dodaj +1