Binary moment diagram

Binary moment diagram

A binary moment diagram (BMD) is a generalization of the binary decision diagram (BDD) to linear functions over domains such as booleans (like BDDs), but also to integers or to real numbers.

They can deal with boolean functions with complexity comparable to BDDs, but also some functions that are dealtwith very inefficiently in a BDD are handled easily by BMD, most notably multiplication.

The most important properties of BMD is that, like with BDDs, each function has exactly one canonical representation,and many operations can be efficiently performed on these representations.

The main features that differentiate BMDs from BDDs are using linear instead of pointwise diagrams, and having weighted edges.

The rules that ensure the canonicity of the representation are:
* Decision over variables higher in the ordering may only point to decisions over variables lower in the ordering.
* No two nodes may be identical (in normalization such nodes all references to one of these nodes should be replaced be references to another)
* No node may have all decision parts equivalent to 0 (links to such nodes should be replaced by links to their always part)
* No edge may have weight zero (all such edges should be replaced by direct links to 0)
* Weights of the edges should be coprime. Without this rule or some equivalent of it, it would be possible for a function to have many representations, for example 2x+2 could be represented as 2cdot(1+x) or 1cdot(2 + 2x).

Pointwise and linear decomposition

In pointwise decomposition, like in BDDs, on each branch point we store result of all branches separately.An example of such decomposition for an integer function (2x+y) is::egin{cases} mbox{if } xegin{cases} mbox{if } y mbox{ , } 3\ mbox{if } eg y mbox{ , } 2end{cases}\ mbox{if } eg xegin{cases} mbox{if } y mbox{ , } 1\ mbox{if } eg y mbox{ , } 0end{cases}end{cases}

In linear decomposition we provide instead a default value and a difference:

:egin{cases}mbox{always} egin{cases}mbox{always } 0 \mbox{if } y mbox{ , } +1end{cases}\mbox{if } x mbox{ , } +2end{cases}

It can easily be seen that the latter (linear) representation is much more efficient in case of additive functions,as when we add many elements the latter representation will have only O(n) elements,while the former (pointwise), even with sharing, exponentially many.

Edge weights

Another extension is using weights for edges. A value of function at given node is a sum of the true nodes below it (the node under always, and possibly the decided node) times the edges' weights.

For example (4x_2 + 2x_1 + x_0) (4y_2 + 2y_1 + y_0) can be represented as:
# Result node, always 1× value of node 2, if x_2 add 4× value of node 4
# Always 1× value of node 3, if x_1 add 2× value of node 4
# Always 0, if x_0 add 1× value of node 4
# Always 1× value of node 5, if y_2 add +4
# Always 1× value of node 6, if y_1 add +2
# Always 0, if y_0 add +1

Without weighted nodes a much more complex representation would be required:
# Result node, always value of node 2, if x_2 value of node 4
# Always value of node 3, if x_1 value of node 7
# Always 0, if x_0 value of node 10
# Always value of node 5, if y_2 add +16
# Always value of node 6, if y_1 add +8
# Always 0, if y_0 add +4
# Always value of node 8, if y_2 add +8
# Always value of node 9, if y_1 add +4
# Always 0, if y_0 add +2
# Always value of node 11, if y_2 add +4
# Always value of node 12, if y_1 add +2
# Always 0, if y_0 add +1

References

*Unreferenced|date=January 2007


Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • Binary decision diagram — In the field of computer science, a binary decision diagram (BDD) or branching program, like a negation normal form (NNF) or a propositional directed acyclic graph (PDAG), is a data structure that is used to represent a Boolean function. On a… …   Wikipedia

  • Binary Decision Diagram — Ein Binäres Entscheidungsdiagramm (BED; engl. binary decision diagram, BDD) ist eine Datenstruktur zur Repräsentation Boolescher Funktionen. Binäre Entscheidungsdiagramme werden vor allem im Bereich der Hardwaresynthese und verifikation… …   Deutsch Wikipedia

  • Бинарная диаграмма решений — (БДР) или программа с ветвлением является формой представления булевой функции от переменных в виде направленного ациклического графа, состоящего из внутренних узлов решений (помеченных ), каждый из которых имеет по два потомка, и двух… …   Википедия

  • Binäres Entscheidungsdiagramm — Ein Binäres Entscheidungsdiagramm (BED; engl. binary decision diagram, BDD) ist eine Datenstruktur zur Repräsentation Boolescher Funktionen. Binäre Entscheidungsdiagramme werden vor allem im Bereich der Hardwaresynthese und verifikation… …   Deutsch Wikipedia

  • OBDD — Ein Binäres Entscheidungsdiagramm (BED; engl. binary decision diagram, BDD) ist eine Datenstruktur zur Repräsentation Boolescher Funktionen. Binäre Entscheidungsdiagramme werden vor allem im Bereich der Hardwaresynthese und verifikation… …   Deutsch Wikipedia

  • ROBDD — Ein Binäres Entscheidungsdiagramm (BED; engl. binary decision diagram, BDD) ist eine Datenstruktur zur Repräsentation Boolescher Funktionen. Binäre Entscheidungsdiagramme werden vor allem im Bereich der Hardwaresynthese und verifikation… …   Deutsch Wikipedia

  • Hash table — Not to be confused with Hash list or Hash tree. Unordered map redirects here. For the proposed C++ class, see unordered map (C++). Hash Table Type unsorted dictionary Invented 1953 Time complexity in big O notation Average Worst case Space …   Wikipedia

  • List of pangrams — This is a list of pangrams which are sentences using every letter of the alphabet at least once.= Perfect pangrams in English (26 letters) = Without proper nouns or initialisms * Cwm fjord bank glyphs vext quiz. ( Carved symbols in a mountain… …   Wikipedia

  • liquid — liquidly, adv. liquidness, n. /lik wid/, adj. 1. composed of molecules that move freely among themselves but do not tend to separate like those of gases; neither gaseous nor solid. 2. of, pertaining to, or consisting of liquids: a liquid diet. 3 …   Universalium

  • White dwarf — For other uses, see White dwarf (disambiguation). Image of Sirius A and Sirius B taken by the Hubble Space Telescope. Sirius B, which is a white dwarf, can be seen as a faint pinprick of light to the lower left of the much brighter Sirius A …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”