बाइनरी मोमेंट डायग्राम

एक बाइनरी पल आरेख (बीएमडी) बाइनरी निर्णय आरेख (बीडीडी) का एक सामान्यीकरण है जो बूलियन (जैसे बीडीडी) जैसे डोमेन पर रैखिक कार्यों के लिए होता है, लेकिन पूर्णांक या वास्तविक संख्याओं के लिए भी। वे BDDs की तुलना में जटिलता के साथ बूलियन समारोह से निपट सकते हैं, लेकिन BDD में बहुत ही अक्षमता से निपटाए जाने वाले कुछ कार्यों को BMD द्वारा आसानी से नियंत्रित किया जाता है, विशेष रूप से गुणन।

BMD का सबसे महत्वपूर्ण गुण यह है कि, BDDs की तरह, प्रत्येक फ़ंक्शन में बिल्कुल एक विहित प्रतिनिधित्व होता है, और इन अभ्यावेदन पर कई ऑपरेशन कुशलता से किए जा सकते हैं।

बीडीडी से बीएमडी को अलग करने वाली मुख्य विशेषताएं बिंदुवार आरेखों के बजाय रैखिक का उपयोग कर रही हैं, और भारित किनारों वाले हैं।

प्रतिनिधित्व की प्रामाणिकता सुनिश्चित करने वाले नियम हैं:

• क्रम में उच्च चर पर निर्णय केवल क्रम में कम चर पर निर्णय की ओर इशारा कर सकता है।
• कोई भी दो नोड समान नहीं हो सकते हैं (सामान्यीकरण में ऐसे नोड्स में से किसी एक नोड के सभी संदर्भों को दूसरे के संदर्भ में प्रतिस्थापित किया जाना चाहिए)
• किसी भी नोड में सभी निर्णय भाग 0 के समतुल्य नहीं हो सकते हैं (ऐसे नोड्स के लिंक को उनके हमेशा भाग के लिंक द्वारा प्रतिस्थापित किया जाना चाहिए)
• किसी भी किनारे का भार शून्य नहीं हो सकता है (ऐसे सभी किनारों को 0 के सीधे लिंक द्वारा प्रतिस्थापित किया जाना चाहिए)
• किनारों का वजन सह अभाज्य होना चाहिए। इस नियम या इसके समकक्ष के बिना, एक फ़ंक्शन के लिए कई प्रतिनिधित्व करना संभव होगा, उदाहरण के लिए 2x + 2 को 2·· (1 + x) या 1 · (2 + 2x) के रूप में दर्शाया जा सकता है।

बिंदुवार और रैखिक अपघटन

बिंदुवार अपघटन में, बीडीडी की तरह, प्रत्येक शाखा बिंदु पर हम सभी शाखाओं के परिणाम अलग-अलग संग्रहीत करते हैं। पूर्णांक फ़ंक्शन (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}}$

यह आसानी से देखा जा सकता है कि योगात्मक कार्यों के मामले में बाद वाला (रैखिक) प्रतिनिधित्व बहुत अधिक कुशल है, क्योंकि जब हम कई तत्वों को जोड़ते हैं तो बाद वाले प्रतिनिधित्व में केवल O(n) तत्व होंगे, जबकि पूर्व (बिंदुवार), साझा करने के साथ भी , घातीय रूप से कई।

एज वेट

एक अन्य एक्सटेंशन किनारों के लिए वज़न का उपयोग कर रहा है। दिए गए नोड पर फ़ंक्शन का मान इसके नीचे सही नोड्स का योग है (नोड हमेशा के तहत, और संभवतः तय नोड) किनारों के वजन के गुणा।

उदाहरण के लिए, $(4x_{2}+2x_{1}+x_{0})(4y_{2}+2y_{1}+y_{0})$ के रूप में प्रतिनिधित्व किया जा सकता है:

1. परिणाम नोड, हमेशा 1 × नोड 2 का मान, यदि $x_{2}$ नोड 4 का 4× मान जोड़ें
2. नोड 3 का हमेशा 1× मान, यदि $x_{1}$ नोड 4 का 2× मान जोड़ें
3. हमेशा 0, अगर $x_{0}$ नोड 4 का 1× मान जोड़ें
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 जोड़ें