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

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

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

परिभाषा

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

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

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

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

उदाहरण

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

फ़ंक्शन के लिए बाइनरी डिसीजन ट्री और ट्रुथ टेबल$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})$, बूलियन ऑपरेटरों के लिए संकेतन में वर्णित है।

फ़ंक्शन f के लिए बीडीडी

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

पूरक किनारे

पूरक किनारों का उपयोग करके दर्शाए गए द्विआधारी निर्णय आरेख का आरेख।

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

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

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

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

उदाहरण के लिए, मान लीजिए कि एक बूलियन फ़ंक्शन को पूरक किनारों का उपयोग करके दर्शाए गए बीडीडी के साथ दर्शाया गया है। एक चर के लिए दिए गए असाइनमेंट (बूलियन) के लिए एक बूलियन फ़ंक्शन का मान खोजने के लिए, हम संदर्भ किनारे से शुरू करते हैं, जो बीडीडी की जड़ को इंगित करता है और दिए गए चर मानों द्वारा परिभाषित पथ का अनुसरण करता है (बाद में) यदि नोड को लेबल करने वाला चर 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" लेबल द्वारा दर्शाया जाता है। नोड जिसका लेबल @ प्रतीक से शुरू होता है, वह बीडीडी के संदर्भ का प्रतिनिधित्व करता है, अर्थात संदर्भ किनारा वह किनारा है जो इस नोड से शुरू होता है।

इतिहास

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

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

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

अनुप्रयोग

सर्किट (तर्क संश्लेषण) को संश्लेषित करने और औपचारिक सत्यापन में बीडीडी का व्यापक रूप से सीएडी सॉफ्टवेयर में उपयोग किया जाता है। बीडीडी में कई कम-ज्ञात अनुप्रयोग हैं, जिनमें फॉल्ट ट्री विश्लेषण, बायेसियन लॉजिक, उत्पाद विन्यास और निजी सूचना पुनर्प्राप्ति शामिल हैं।

कोई भी मनमाना बीडीडी (भले ही इसे कम किया गया हो या ऑर्डर न किया गया हो) प्रत्येक नोड को 2 से 1 मल्टीप्लेक्सर से बदलकर सीधे हार्डवेयर में लागू किया जा सकता है; प्रत्येक बहुसंकेतक एक FPGA में 4-LUT द्वारा सीधे लागू किया जा सकता है। लॉजिक गेट्स के एक मनमाने नेटवर्क से बीडीडी [उद्धरण वांछित] (AND-इन्वर्टर ग्राफ़ के विपरीत) में परिवर्तित करना इतना आसान नहीं है।

चर आदेश

बीडीडी का आकार प्रतिनिधित्व किए जा रहे फ़ंक्शन और चर के चुने हुए अनुक्रम द्वारा निर्धारित किया जाता है। बूलियन फ़ंक्शन मौजूद हैं $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}$, बीडीडी की जरूरत है $2^{n+1}$ फ़ंक्शन का प्रतिनिधित्व करने के लिए नोड्स। आदेश का उपयोग करना $x_{1}<x_{2}<x_{3}<x_{4}<\cdots <x_{2n-1}<x_{2n}$, बीडीडी में शामिल हैं $2n+2$ नोड्स।

फ़ंक्शन के लिए बीडीडी ƒ(x1, ..., x8) = x1x2 + x3x4 + x5x6 + x7x8 खराब चर क्रम का उपयोग करना

अच्छा परिवर्तन क्रम

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

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

शोधकर्ता बीडीडी डेटा संरचना पर एक शोधन का सुझाव देते हैं, जो बीएमडी (बाइनरी मोमेंट डायग्राम), जेडडीडी (जीरो-सप्रेस्ड डिसीजन डायग्राम), एफडीडी (फ्री बाइनरी डिसीजन डायग्राम), पीडीडी (पैरिटी डिसीजन डायग्राम) जैसे कई संबंधित ग्राफों को रास्ता देता है। ), और एमटीबीडीडी (MTBDDs) 0 (एकाधिक टर्मिनल बीडीडी)।

बीडीडी पर तार्किक संचालन

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

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

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

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

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

यह भी देखें

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

अग्रिम पठन

• 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: Oबीडीडी – 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 बीडीडी software libraries for several programming languages.