बाइनरी निर्णय आरेख

कंप्यूटर विज्ञान में, बाइनरी निर्णय आरेख (BDD) या ब्रांचिंग प्रोग्राम एक डेटा संरचना है जिसका उपयोग बूलियन फ़ंक्शन का प्रतिनिधित्व करने के लिए किया जाता है। अधिक सार स्तर पर, BDD को समुच्चय या संबंधों के एक सघन प्रतिनिधित्व के रूप में माना जा सकता है। अन्य संपीड़ित अभ्यावेदन के विपरीत, संचालन सीधे संपीड़ित प्रतिनिधित्व पर किया जाता है, अर्थात बिना विघटन के।

इसी तरह की डेटा संरचनाओं में नकारात्मक सामान्य रूप (NNF), ज़ेगल्किन बहुपद, और प्रस्तावक निर्देशित विश्वकोश रेखांकन (PDAG) शामिल हैं।

परिभाषा

एक बूलियन फ़ंक्शन को एक रूटेड, निर्देशित, एसाइक्लिक ग्राफ के रूप में दर्शाया जा सकता है, जिसमें कई (निर्णय) नोड्स और दो टर्मिनल नोड होते हैं। दो टर्मिनल नोड्स को 0 (FALSE) और 1 (TRUE) के रूप में लेबल किया गया है। प्रत्येक (निर्णय) नोड $u$ को एक बूलियन चर $x_{i}$ द्वारा लेबल किया गया है और इसमें दो चाइल्ड नोड्स हैं जिन्हें लो चाइल्ड और हाई चाइल्ड कहा जाता है। नोड $u$ से निम्न (या उच्च) बच्चे तक का किनारा चर $x_{i}$के मान FALSE (या TRUE, क्रमशः) के एक असाइनमेंट को दर्शाता है। ऐसे BDD को 'आदेशित' कहा जाता है यदि मूल से सभी पथों पर विभिन्न चर एक ही क्रम में प्रकट होते हैं। एक बीडीडी को 'कम' कहा जाता है यदि निम्नलिखित दो नियमों को इसके ग्राफ पर लागू किया गया है:

• किसी भी समरूपी उप-अनुच्छेदों को मिलाइए।
• ऐसे किसी भी नोड को हटा दें जिसके दो बच्चे समरूपी हों।

लोकप्रिय उपयोग में, बीडीडी शब्द लगभग हमेशा एक कम आदेशित द्विआधारी निर्णय आरेख होता है (साहित्य में आरओबीबीडी का उपयोग तब किया जाता है जब आदेश और कमी के पहलुओं पर जोर दिया जाना चाहिए)। ROBDD का लाभ यह है कि यह किसी विशेष कार्य और परिवर्तनशील क्रम के लिए विहित (अद्वितीय) है। यह गुण इसे कार्यात्मक तुल्यता जाँच और कार्यात्मक प्रौद्योगिकी मानचित्रण जैसे अन्य कार्यों में उपयोगी बनाता है।

रूट नोड से 1-टर्मिनल तक का पथ एक (संभवतः आंशिक) वैरिएबल असाइनमेंट का प्रतिनिधित्व करता है जिसके लिए प्रतिनिधित्व एक बूलियन फ़ंक्शन सत्य है। चूंकि पथ एक नोड से निचले (या उच्चतर) बच्चे तक जाता है, उस नोड का चर 0 (क्रमशः) नियत किया जाता है।

उदाहरण

नीचे दिया गया आंकड़ा एक द्विआधारी निर्णय पेड़ दिखाता है (कमी नियम लागू नहीं होते हैं), और एक सत्य तालिका, प्रत्येक फ़ंक्शन $f(x1,x2,x3)$ का प्रतिनिधित्व करता है। बाईं ओर के पेड़ में, किसी दिए गए चर असाइनमेंट के लिए फ़ंक्शन का मान निर्धारित किया जा सकता है एक टर्मिनल के लिए ग्राफ़ के नीचे पथ का अनुसरण करना। नीचे दिए गए आंकड़ों में, बिंदीदार रेखाएं कम बच्चे के किनारों का प्रतिनिधित्व करती हैं, जबकि ठोस रेखाएं किनारों को उच्च बच्चे को दर्शाती हैं। इसलिए, f(0,1,1) को खोजने के लिए, x1 से शुरू करें, बिंदीदार रेखा को x2 तक ले जाएं (चूंकि x1 में 0 को असाइनमेंट है), और फिर दो ठोस रेखाएं नीचे आती हैं (चूंकि x2 और x3 प्रत्येक में एक को असाइनमेंट होता है)। यह टर्मिनल 1 की ओर जाता है, जो $f(0,1,1)$ का मान है। बायीं आकृति में बाइनरी निर्णय ट्री को दो कमी नियमों के अनुसार अधिकतम को कम करके बाइनरी निर्णय आरेख में बदला जा सकता है। परिणामी BDD को सही आकृति में दिखाया गया है।

Binary decision tree and truth table for the function $f(x_{1},x_{2},x_{3})=(\neg x_{1}\wedge \neg x_{2}\wedge \neg x_{3})\vee (x_{1}\wedge x_{2})\vee (x_{2}\wedge x_{3})$, described in notation for Boolean operators.

BDD for the function f

इस बूलियन फ़ंक्शन को लिखने के लिए एक और संकेतन ${\overline {x}}_{1}{\overline {x}}_{2}{\overline {x}}_{3}+x_{1}x_{2}+x_{2}x_{3}$ है।

पूरक किनारे

एक ROBDD को पूरक किनारों का उपयोग करके और भी अधिक सघन रूप से दर्शाया जा सकता है। पूरक किनारों का निर्माण निम्नलिखित किनारों को पूरक के रूप में व्याख्या करके किया गया है या नहीं। यदि एक किनारे को पूरक किया जाता है, तो यह एक बूलियन फ़ंक्शन की अस्वीकृति को संदर्भित करता है जो एक नोड से मेल खाता है जो एक किनारे की ओर इशारा करता है (बूलियन फ़ंक्शन उस नोड की जड़ के साथ बीडीडी द्वारा दर्शाया गया है)। यह सुनिश्चित करने के लिए कि परिणामी BDD प्रतिनिधित्व एक विहित रूप है, उच्च किनारों को पूरक नहीं किया गया है। इस निरूपण में, बीडीडी में एक एकल पत्ती नोड होता है, नीचे बताए गए कारणों के लिए।

BDDs का प्रतिनिधित्व करते समय पूरक किनारों का उपयोग करने के दो लाभ हैं:

• BDD के निषेध की गणना करने में निरंतर समय लगता है
• स्पेस उपयोग (यानी, आवश्यक मेमोरी) कम हो जाता है

इस प्रतिनिधित्व में, बीडीडी का संदर्भ एक (संभवतः पूरक) "किनारे" है जो बीडीडी की जड़ को इंगित करता है। यह पूरक किनारों के उपयोग के बिना प्रतिनिधित्व में बीडीडी के संदर्भ के विपरीत है, जो बीडीडी के मूल नोड हैं। इस प्रतिनिधित्व में एक संदर्भ बढ़त होने का कारण यह है कि प्रत्येक बूलियन फ़ंक्शन के लिए, फ़ंक्शन और इसके निषेध को एक किनारे से दर्शाया जाता है जो एक BDD की मूल तक जाता है, और एक ही BDD की जड़ के पूरक किनारे का प्रतिनिधित्व करता है। यही कारण है कि नकारने में निरंतर समय लगता है। यह यह भी बताता है कि एक एकल निष्पर्ण पर्याप्त क्यों है: FALSE को एक पूरक किनारे द्वारा दर्शाया जाता है जो एक पत्ती नोड को इंगित करता है, और TRUE को एक साधारण किनारे (अर्थात, पूरक नहीं) द्वारा दर्शाया जाता है जो कि निष्पर्ण को इंगित करता है।

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

इस प्रतिनिधित्व में एक बीडीडी का एक उदाहरण आरेख दाईं ओर दिखाया गया है, और उसी बूलियन अभिव्यक्ति का प्रतिनिधित्व करता है जैसा कि ऊपर के चित्र में दिखाया गया है, अर्थात $(\neg x_{1}\wedge \neg x_{2}\wedge \neg x_{3})\vee (x_{1}\wedge x_{2})\vee (x_{2}\wedge x_{3})$। कम किनारों को धराशायी कर दिया जाता है, उच्च किनारों को ठोस, और पूरक किनारों को "-1" लेबल द्वारा दर्शाया जाता है। नोड जिसका लेबल @ प्रतीक से शुरू होता है, वह BDD के संदर्भ का प्रतिनिधित्व करता है, अर्थात संदर्भ किनारा वह किनारा है जो इस नोड से शुरू होता है।

इतिहास

मूल विचार जिससे डेटा संरचना बनाई गई थी, वह है शैनन विस्तार। एक स्विचिंग फ़ंक्शन को एक चर (cf. if-then-else सामान्य रूप) निर्दिष्ट करके दो उप-फ़ंक्शंस (कॉफ़ैक्टर्स) में विभाजित किया जाता है। यदि इस तरह के उप-फ़ंक्शन को उप-पेड़ के रूप में माना जाता है, तो इसे बाइनरी निर्णय पेड़ द्वारा दर्शाया जा सकता है। बाइनरी डिसीजन डायग्राम (BDDs) को C. Y. Lee द्वारा पेश किया गया था, और आगे अध्ययन किया और शेल्डन बी, एकर्स और रेमंड टी, बाउट द्वारा जाना जाता है। इन लेखकों के स्वतंत्र रूप से, कैनोनिकल ब्रैकेट फॉर्म के नाम से एक बीडीडी को यूयू का एहसास हुआ था।स्पीड-इंडिपेंडेंट सर्किट के विश्लेषण के लिए एक सीएडी में वी। माम्रुकोव। डेटा संरचना के आधार पर कुशल एल्गोरिदम के लिए पूरी क्षमता की जांच कार्नेगी मेलन विश्वविद्यालय में रैंडल ब्रायंट द्वारा की गई थी: उनके प्रमुख एक्सटेंशन एक निश्चित चर ऑर्डर (कैनोनिकल प्रतिनिधित्व के लिए) और साझा उप-ग्राफ (संपीड़न के लिए) का उपयोग करने के लिए थे।इन दो अवधारणाओं को लागू करने से सेट और संबंधों के प्रतिनिधित्व के लिए एक कुशल डेटा संरचना और एल्गोरिदम का परिणाम होता है।कई बीडीडी के लिए साझाकरण का विस्तार करके, यानी एक उप-ग्राफ का उपयोग कई बीडीडी द्वारा किया जाता है, डेटा संरचना साझा किए गए आदेशित बाइनरी निर्णय आरेख को परिभाषित किया गया है।बीडीडी की धारणा अब आम तौर पर उस विशेष डेटा संरचना को संदर्भित करने के लिए उपयोग की जाती है।

बाइनरी निर्णय आरेखों (BDDs) के साथ अपने वीडियो व्याख्यान में,डोनाल्ड नूथ बीडीडी को केवल वास्तव में मौलिक डेटा संरचनाओं में से एक कहता है जो पिछले पच्चीस वर्षों में सामने आया था और उल्लेख किया है कि ब्रायंट का 1986 का पेपर कुछ समय के लिए कंप्यूटर विज्ञान में सबसे अधिक उद्धृत पत्रों में से एक था।

अदनान डार्विच और उनके सहयोगियों ने दिखाया है कि BDDs बूलियन कार्यों के लिए कई सामान्य रूपों में से एक हैं, प्रत्येक आवश्यकताओं के एक अलग संयोजन से प्रेरित है।Darwiche द्वारा पहचानी गई एक और महत्वपूर्ण सामान्य रूप डीकंपोज़ेबल नेगेशन नॉर्मल फॉर्म या DNNF है।

अनुप्रयोग

बीडीडी को सीएडी सॉफ्टवेयर में बड़े पैमाने पर उपयोग किया जाता है ताकि सर्किट (लॉजिक सिंथेसिस) और औपचारिक सत्यापन में संश्लेषित किया जा सके।BDD के कई कम ज्ञात अनुप्रयोग हैं, जिनमें फॉल्ट ट्री एनालिसिस, बायेसियन रीजनिंग, प्रोडक्ट कॉन्फ़िगरेशन और निजी सूचना पुनर्प्राप्ति शामिल हैं। प्रत्येक मनमाना BDD (भले ही यह कम या आदेश नहीं दिया गया हो) को सीधे हार्डवेयर में 2 से 1 मल्टीप्लेक्स के साथ प्रत्येक नोड को बदलकर लागू किया जा सकता है;प्रत्येक मल्टीप्लेक्स को सीधे एक FPGA में 4-lut द्वारा लागू किया जा सकता है।लॉजिक गेट्स के एक मनमाना नेटवर्क से बीडीडी में परिवर्तित करना इतना सरल नहीं है (और इनवर्टर ग्राफ के विपरीत)।

चर आदेश

BDD का आकार फ़ंक्शन का प्रतिनिधित्व किया जा रहा है और चर के चुने हुए क्रम द्वारा निर्धारित किया जाता है।वहाँ बूलियन कार्य मौजूद हैं $f(x_{1},\ldots ,x_{n})$ जिसके लिए चर के आदेश के आधार पर हम एक ग्राफ प्राप्त कर रहे हैं, जिसकी संख्या नोड्स की संख्या रैखिक होगी (सबसे अच्छा और सबसे अच्छा और घातीय रूप से सबसे खराब (जैसे, एक तरंग कैरी एडडर)।बूलियन फ़ंक्शन पर विचार करें $f(x_{1},\ldots ,x_{2n})=x_{1}x_{2}+x_{3}x_{4}+\cdots +x_{2n-1}x_{2n}.$ चर आदेश का उपयोग करना $x_{1}<x_{3}<\cdots <x_{2n-1}<x_{2}<x_{4}<\cdots <x_{2n}$, BDD की जरूरत है $2^{n+1}$ फ़ंक्शन का प्रतिनिधित्व करने के लिए नोड्स।आदेश का उपयोग करना $x_{1}<x_{2}<x_{3}<x_{4}<\cdots <x_{2n-1}<x_{2n}$, BDD में शामिल हैं $2n+2$ नोड्स।

BDD for the function ƒ(x1, ..., x8) = x1x2 + x3x4 + x5x6 + x7x8 using bad variable ordering

Good variable ordering

व्यवहार में इस डेटा संरचना को लागू करते समय चर आदेश के बारे में देखभाल करना महत्वपूर्ण महत्व है।सबसे अच्छा चर आदेश खोजने की समस्या एनपी-हार्ड है।किसी भी निरंतर c & nbsp; & nbsp; 1 के लिए यह एक चर ऑर्डर की गणना करने के लिए एनपी-हार्ड भी है, जिसके परिणामस्वरूप एक आकार के साथ एक OBDD होता है जो कि एक इष्टतम से अधिक सी गुना अधिक होता है।हालांकि, समस्या से निपटने के लिए कुशल हेयूरिस्टिक्स मौजूद हैं।

ऐसे कार्य हैं जिनके लिए ग्राफ का आकार हमेशा घातीय होता है - चर आदेश के स्वतंत्र।यह उदा।गुणन फ़ंक्शन के लिए।वास्तव में, फ़ंक्शन दो के उत्पाद के मध्य बिट की गणना करता है $n$-बिट संख्याओं में एक obdd की तुलना में छोटा नहीं है $2^{\lfloor n/2\rfloor }/61-4$ कोने।(यदि गुणन फ़ंक्शन में बहुपद-आकार के OBDDs थे, तो यह दिखाएगा कि पूर्णांक कारक p/poly में है, जो सच नहीं है। शोधकर्ताओं ने बीएमडी (बाइनरी मोमेंट आरेख), जेडडीडी (शून्य-दमनकारी निर्णय आरेख), एफडीडी (मुक्त द्विआधारी निर्णय आरेख), पीडीडी (समता निर्णय आरेख) जैसे कई संबंधित रेखांकन, जैसे कई संबंधित रेखांकन के लिए बीडीडी डेटा संरचना पर शोधन का सुझाव दिया है।, और MTBDDS (कई टर्मिनल BDDs)।

BDDS पर तार्किक संचालन

BDDs पर कई तार्किक संचालन को बहुपद-समय ग्राफ हेरफेर एल्गोरिदम द्वारा लागू किया जा सकता है:

• संयोजक
• असंतुष्ट
• उपेक्षा

हालांकि, इन कार्यों को कई बार दोहराते हुए, उदाहरण के लिए, BDDs के एक सेट के संयोजन या विघटन का निर्माण, सबसे खराब स्थिति में सबसे बड़े BDD के परिणामस्वरूप हो सकता है।इसका कारण यह है कि दो बीडीडी के लिए पूर्ववर्ती संचालन में से कोई भी बीडीडी के आकार के साथ बीडीडी के आकार के उत्पाद के लिए आनुपातिक हो सकता है, और परिणामस्वरूप कई बीडीडी के लिए आकार संचालन की संख्या में घातीय हो सकता है।परिवर्तनीय आदेश को दूर करने की आवश्यकता है;बीडीडी के सेट के लिए (कुछ) के लिए एक अच्छा आदेश क्या हो सकता है, ऑपरेशन के परिणाम के लिए एक अच्छा आदेश नहीं हो सकता है।इसके अलावा, एक बूलियन फ़ंक्शन के BDD का निर्माण करने से NP- पूर्ण बूलियन संतोषजनक समस्या और CO-NP- पूर्ण टॉटोलॉजी समस्या का समाधान होता है, BDD का निर्माण करने से बूलियन फॉर्मूला के आकार में घातीय समय लग सकता है, जिसके परिणामस्वरूप BDD छोटा होता है।

कम BDDs के कई चर पर अस्तित्व संबंधी अमूर्तता की गणना एनपी-पूर्ण है।

मॉडल-गिनती, एक बूलियन फॉर्मूला के संतोषजनक असाइनमेंट की संख्या की गिनती, बीडीडी के लिए बहुपद समय में किया जा सकता है।सामान्य प्रस्ताव के सूत्रों के लिए समस्या isp-c-पूर्ण है और सबसे अच्छे ज्ञात एल्गोरिदम को सबसे खराब स्थिति में एक घातीय समय की आवश्यकता होती है।

यह भी देखें

• बूलियन संतोषजनक समस्या, कैनोनिकल एनपी-पूर्ण कम्प्यूटेशनल समस्या
• एल/पॉली, एक जटिलता वर्ग जिसमें सख्ती से बहुपद आकार के बीडीडी के साथ समस्याओं का सेट होता है
• मॉडल जाँच
• रेडिक्स ट्री
• नेकां (जटिलता)#बैरिंगटन का प्रमेय | बैरिंगटन का प्रमेय
• हार्डवेयर एक्सिलरेशन
• कर्णघ मैप, बूलियन बीजगणित अभिव्यक्तियों को सरल बनाने की एक विधि

अग्रिम पठन

• R. Ubar, "Test Generation for Digital Circuits Using Alternative Graphs (in Russian)", in Proc. Tallinn Technical University, 1976, No. 409, Tallinn Technical University, Tallinn, Estonia, pp. 75–81.
• D. E. Knuth, "The Art of Computer Programming Volume 4, Fascicle 1: Bitwise tricks & techniques; Binary Decision Diagrams" (Addison–Wesley Professional, March 27, 2009) viii+260pp, ISBN 0-321-58050-8. Draft of Fascicle 1b available for download.
• Ch. Meinel, T. Theobald, "Algorithms and Data Structures in VLSI-Design: OBDD – Foundations and Applications", Springer-Verlag, Berlin, Heidelberg, New York, 1998. Complete textbook available for download.
• Ebendt, Rüdiger; Fey, Görschwin; Drechsler, Rolf (2005). Advanced BDD optimization. Springer. ISBN 978-0-387-25453-1.
• Becker, Bernd; Drechsler, Rolf (1998). Binary Decision Diagrams: Theory and Implementation. Springer. ISBN 978-1-4419-5047-5.

बाहरी संबंध

• Fun With Binary Decision Diagrams (BDDs), lecture by Donald Knuth
• List of BDD software libraries for several programming languages.