Signal transition graphs
सिग्नल ट्रांजिशन ग्राफ (एसटीजी) का उपयोग आमतौर पर इलेक्ट्रॉनिक इंजीनियरिंग और कंप्यूटर इंजीनियरिंग में अतुल्यकालिक परिपथों के गतिशील व्यवहार का वर्णन करने के लिए, उनके विश्लेषण या संश्लेषण के उद्देश्यों के लिए किया जाता है। मुख्य परिभाषाएँ और अनुप्रयोग अनौपचारिक रूप से, एक एस. टी. जी. एक अतुल्यकालिक परिपथ के व्यवहार का एक चित्रमय विवरण है जिसमें संकेत देने वाली घटनाओं के बीच कारण संबंधों के बारे में जानकारी सीधे प्रस्तुत की जाती है, जैसा कि अवस्थाओं पर आधारित विवरणों के विपरीत होता है। इस तरह, एसटीजी आमतौर पर समय आरेख द्वारा दर्शाए गए परिपथ के विवरण को औपचारिक बनाने में मदद करते हैं, जिन्हें कभी-कभी तरंग रूप भी कहा जाता है। बाद वाले का व्यापक रूप से इलेक्ट्रॉनिक इंजीनियरों द्वारा उपयोग किया जाता है। अधिक औपचारिक रूप से, एक एसटीजी एक प्रकार का व्याख्या (या लेबल किया गया) पेट्री नेट है जिसके संक्रमणों को संकेतों के मूल्यों में परिवर्तन के नामों के साथ लेबल किया जाता है (सीएफ। संकेत संक्रमण)। उदाहरण के लिए, लेबलिंग का विशिष्ट मामला वह मामला है जहां संकेत द्विआधारी होते हैं, इसलिए संक्रमण को परिपथ में संकेतों के बढ़ते और गिरने वाले किनारों के रूप में व्याख्या की जाती है। एस. टी. जी. आमतौर पर स्टेट ग्राफ की तुलना में एसिंक्रोनस सर्किट के व्यवहार का अधिक संक्षिप्त विवरण देते हैं। एक परिपथ के एसटीजी विनिर्देश की जटिलता आमतौर पर परिपथ में संकेतों की संख्या में रैखिक होती है, जबकि एक अवस्था ग्राफ की जटिलता तेजी से बढ़ सकती है, इस तथ्य के कारण कि अतुल्यकालिक परिपथ में उच्च स्तर की समवर्तीता होती है। एस. टी. जी. में समवर्ती घटनाओं को कारण-अनुक्रम संबंधों (सी. एफ. वास्तविक समवर्ती मुद्रा) जबकि राज्य ग्राफ में समवर्ती मुद्रा को इंटरलीविंग के माध्यम से दर्शाया जाता है। एसटीजी को पहली बार 1981 में लियोनिद रोसेनब्लम (रूसी में) द्वारा सिग्नल ग्राफ के नाम से प्रस्तावित किया गया था। उनका अधिक औपचारिक रूप से अध्ययन किया गया और 1982 में एलेक्स याकोवलेव द्वारा अपने पीएचडी थीसिस (रूसी में) में अतुल्यकालिक इंटरफेस के डिजाइन पर लागू किया गया। उन्हें बाद में 1985 में दो स्वतंत्र स्रोतों में अंग्रेजी में प्रस्तुत किया गया था, एक रोसेनब्लम और याकोवलेव द्वारा और दूसरा ताम-अन्ह चू द्वारा (एक पुराना संस्करण आईसीसीडी '85 में प्रस्तुत किया गया था)। तब से, एस. टी. जी. का सिद्धांत और व्यवहार में व्यापक रूप से अध्ययन किया गया है, जिससे अतुल्यकालिक नियंत्रण परिपथों के विश्लेषण और संश्लेषण के लिए लोकप्रिय सॉफ्टवेयर उपकरणों का विकास हुआ है, जैसे कि पेट्रिफी (मुख्य विकासकर्ताः जॉर्डी कॉर्टाडेला) और वर्कक्राफ्ट (न्यूकैसल विश्वविद्यालय से एक टूलकिट)। अतुल्यकालिक परिपथों को डिजाइन करने में एस. टी. जी. का उपयोग करने के विभिन्न उदाहरणों में, सबसे अच्छी तरह से ज्ञात वे हैं जो अतुल्यकालिक इंटरफेस, नियंत्रक, मध्यस्थ और एनालॉग-मिश्रित संकेत परिपथों के क्षेत्र में हैं, सी. एफ., हाल ही में एस. टी. जी. को कैपेसिटिव कपलिंग द्वारा मध्यस्थता से जुड़े कारण व्यवहार वाले मॉडल तक विस्तारित किया गया है, जैसे कि स्विच कैपेसिटर कन्वर्टर्स (एस. सी. सी.) में उपयोग किए जाने वाले। विस्तार और संबंधित मॉडल एस. टी. जी. के अलावा, द्विआधारी संकेतों पर आधारित, प्रतीकात्मक एस. टी. जी. भी हैं, जहाँ संकेतों को बहु-मूल्यवान किया जा सकता है। समय (देरी) सूचना एनोटेशन के साथ एसटीजी को पहले 1998 में पेश किया गया था, और बाद में 1998 में, जहां समय की बाधाओं के साथ सर्किट के व्यवहार के विश्लेषण के विचार, जिन्हें बाद में रिलेटिव टाइमिंग कहा गया, को भी पहले पेश किया गया था। एसिंक्रोनी और इंटरप्ट को कॉम्पैक्ट रूप में पकड़ने के लिए बुनियादी अंतर्निहित पेट्री नेट मॉडल के विशेष विस्तार को प्लेस चार्ट नेट्स में पेश किया गया था। एसिंक्रोनस सर्किट के राज्य-आधारित मॉडल और पेट्री नेट-आधारित मॉडल (एस. टी. जी. सहित) के बीच एक महत्वपूर्ण संबंध क्षेत्रों के सिद्धांत (सी. एफ.) का उपयोग करने में स्थापित किया गया है। रॉबर्ट स्प्रौल, इवान सदरलैंड और चार्ल्स मोलनार के कारण काउंटरफ्लो पाइपलाइन प्रोसेसर के लिए एक एसटीजी मॉडल और इसके सर्किट कार्यान्वयन को प्राप्त करने के लिए क्षेत्रों के सिद्धांत का उपयोग किया गया था। एस. टी. जी. से निकटता से संबंधित मॉडलों में से एक परिवर्तन आरेख है, जिसे माइकल किशिनेव्स्की, एलेक्स कोंड्रेटयेव, अलेक्जेंडर टौबिन और विक्टर वार्शाव्स्की द्वारा प्रस्तावित किया गया है। परिवर्तन आरेखों में ए. एन. डी. और ओ. आर. कार्यकारणता दोनों को एक संक्षिप्त तरीके से मॉडल करने में सक्षम होने के फायदे हैं। लेकिन उनमें चयन के मामले में वर्णनात्मक शक्ति की कमी है। पेट्री जाल और परिवर्तन आरेख के बीच तुलना उनकी वर्णनात्मक शक्ति और कारण तर्क जाल के रूप में उनके एकीकरण के संदर्भ में प्रस्तुत की गई है। हार्डवेयर विवरण भाषाओं के साथ लिंक एस. टी. जी. को विभिन्न एच. डी. एल. के साथ जोड़ा गया है, उदाहरण के लिए एसिंक्रोनस डिजाइन का समर्थन करने के उद्देश्य से वी. एच. डी. एल. (1996) और वेरिलॉग (2000) के साथ लिंक देखें। वी. एच. डी. एल., एस. टी. जी. और पेट्री जाल से संश्लेषण प्रवाह में रखे जाने को सहायक दिखाया गया है, और इसी तरह वेरिलॉग के साथ, जहां एक उपकरण वेरिसिन विकसित किया गया था। हाल ही में एस. टी. जी. को उन संकेतनों के साथ जोड़ा गया है जो व्यावहारिक हार्डवेयर डिजाइनरों के लिए आसान माने जाते हैं, इसलिए तरंग-संक्रमण ग्राफ (डब्ल्यू. टी. जी.) के मॉडल का उदय हुआ है। इसी तरह, यह महसूस करते हुए कि फाइनाइट स्टेट मशीन (एफ. एस. एम.) का मॉडल डिजाइनरों के लिए संभालना आसान हो सकता है, उदाहरण के लिए, पेट्री नेट या एस. टी. जी., फ्रंट-एंड के रूप में बर्स्ट मोड एफ. एस. एम. के साथ एक लिंक विकसित किया गया है। विश्लेषण के तरीके इस समय, अतुल्यकालिक परिपथों के विश्लेषण और संश्लेषण के लिए यकीनन सबसे कुशल तरीके पेट्री नेट अनफोल्डिंग पर आधारित हैं-उनका अध्ययन विक्टर खोमेंको ने अपने पीएचडी थीसिस में किया था। इन्हें वर्कक्राफ्ट के तहत लागू किया जाता है। अतुल्यकालिक परिपथ के पेट्री नेट मॉडल के कुछ उपवर्गों के प्रदर्शन विश्लेषण की जांच ऐगुओ झी और पीटर बीरल द्वारा की गई है। एसिंक्रोनस सर्किट संश्लेषण एस. टी. जी. विनिर्देश से एसिंक्रोनस सर्किट के संश्लेषण में विभिन्न समस्याओं की जांच की गई है। उनके वर्गीकरण के तरीकों में से एक एसटीजी विनिर्देश के राज्य स्थान का प्रतिनिधित्व करने के लिए उपयोग किए जाने वाले विश्लेषण दृष्टिकोण पर आधारित है, जैसे कि स्पष्ट राज्य स्थान, अंतर्निहित पेट्री जाल का खुलासा, पेट्री जाल का संरचनात्मक विश्लेषण और एसटीजी का प्रत्यक्ष मानचित्रण (वाक्यविन्यास-प्रत्यक्ष अनुवाद)। ये दृष्टिकोण आमतौर पर संश्लेषण के एल्गोरिदम की जटिलता और इसलिए, उपकरणों के रन-टाइम से जुड़े होते हैं। दूसरी ओर, इनमें से कुछ तकनीकें पेट्री जाल के वर्ग पर कुछ प्रतिबंध लगाती हैं। उदाहरण के लिए, स्पष्ट राज्य स्थान आधारित विधियाँ आम तौर पर एक मनमाने पेट्री नेट प्रकार के लिए काम करती हैं, जबकि कुछ संरचनात्मक विधियों के लिए आवश्यक है कि अंतर्निहित पेट्री नेट एक चिह्नित ग्राफ या एक मुक्त-विकल्प नेट हो। कम्पलीट स्टेट कोडिंग समस्या परिपथ कार्यान्वयन के संश्लेषण में प्रमुख प्रसिद्ध समस्याओं में से एक कम्पलीट स्टेट कोडिंग (सी. एस. सी.) है। इस समस्या से निपटने के लिए कई तरीके विकसित किए गए हैं। सी. एस. सी. संतुष्टि के लिए विश्लेषण करने का एक विशेष रूप से मूल तरीका एलेक्स याकोवलेव और पीटर वानबेकबर्गेन द्वारा स्वतंत्र रूप से विकसित युग्मन संबंध या, समतुल्य, ताला संबंध की धारणा पर आधारित है। एक अन्य विधि ने क्षेत्रों के सिद्धांत का दोहन किया जो पेट्री जाल के तत्वों को राज्य ग्राफ में राज्यों के क्षेत्रों से जोड़ता है। एलेक्स सेमेनोव और विक्टर खोमेंको द्वारा आंशिक आदेशों और पेट्री नेट अनफोल्डिंग के आधार पर सीएससी का पता लगाने और रिज़ॉल्यूशन के लिए संश्लेषण विधियों का विकास किया गया है। इन विधियों ने वर्कक्राफ्ट में लागू किए गए सी. एस. सी. कोर के आधार पर सी. एस. सी. समस्याओं के प्रभावी दृश्य के लिए एक विधि को औपचारिक बनाने और लागू करने में मदद की है। एस. टी. जी. आधारित संश्लेषण के लिए संरचनात्मक संकेतन विधियों को जोसेप कार्मोना द्वारा विकसित किया गया है। सीमित तर्क आधारों में संश्लेषण गति-स्वतंत्र (या समान रूप से अर्ध-विलंब-असंवेदनशील-क्यू. डी. आई.) परिपथों के संश्लेषण में एक महत्वपूर्ण समस्या एक प्रतिबंधित तार्किक आधार के भीतर संश्लेषण है, उदाहरण के लिए, केवल प्रतिबंधित आधार तर्क द्वार जैसे ए. एन. डी. और ओ. आर. का उपयोग करना-उदाहरण के लिए, एलेक्स याकोवलेव का काम देखें, जहां ई (उत्तेजना)-स्थिरता की स्थिति को कार्यान्वयन में खतरे की स्वतंत्रता सुनिश्चित करने के लिए पेश किया गया था जिसमें उत्तेजना कार्यों के लिए दो-स्तरीय सम-ऑफ-प्रोडक्ट्स (एस. ओ. पी.) तर्क और दिए गए एस. टी. जी. विनिर्देश के मुख्य उत्पादन संकेतों के लिए एस. आर.-लैच शामिल हैं। बाद में, एलेक्स कोंड्रेटयेव और अन्य ने मोनोटोनिक कवर की धारणा में इस स्थिति को सामान्यीकृत किया, जिसने सॉफ्टवेयर उपकरणों में अपनी प्राप्ति पाई। नकारात्मक द्वार आधार, एन. ए. एन. डी. और एन. ओ. आर. में संश्लेषण की समस्या अधिक चुनौतीपूर्ण है। इसके लिए कई तरीके विकसित किए गए हैं, जिनमें से ज्यादातर का नेतृत्व निकोले स्टारोडोबत्सेव ने किया है। संश्लेषण के लिए एस. टी. जी. का अपघटन बड़े आकार के एस. टी. जी. के लिए संश्लेषण की मापनीयता की समस्या, और राज्य अंतरिक्ष विस्फोट को कम करने की आवश्यकता को अंतर्निहित पेट्री नेट के संरचनात्मक गुणों के संबंध में एस. टी. जी. के संकुचन के आधार पर तरीकों से निपटाया गया है-जैसे कि एक मुक्त-विकल्प पेट्री नेट को राज्य मशीनों या चिह्नित ग्राफों में विभाजित करने के तरीके-साथ ही साथ फैन-इन सिग्नल सबसेट (एक संकेत के लिए ट्रिगर घटनाएं)। मापनीयता से निपटने का एक अन्य तरीका एस. टी. जी. से अतुल्यकालिक परिपथों का प्रत्यक्ष मानचित्रण है जिसकी डेनिल सोकोलोव द्वारा जांच की गई है। मध्यस्थता के साथ एस. टी. जी. से संश्लेषण एक विशेष रूप से चुनौतीपूर्ण समस्या मध्यस्थों के लिए अतुल्यकालिक परिपथों को स्वचालित रूप से संश्लेषित करना है, क्योंकि उनके एस. टी. जी. विनिर्देश में उनके अंतर्निहित पेट्री जाल में व्यवहार संबंधी संघर्ष शामिल होंगे। व्यवहार संबंधी संघर्ष उन परिवर्तनों के अस्तित्व को इंगित करते हैं जो निरंतर नहीं हैं। सामान्य रूप से, ऐसे एसटीजी के तर्क आधारित कार्यान्वयन के लिए, परिपथ खतरों से ग्रस्त होगा। वर्कक्राफ्ट में म्यूटेक्स संकेत संक्रमण के अर्ध-स्वचालित सम्मिलन, मूल विनिर्देश को संरक्षित करने जैसी विशेष तकनीकों को विकसित और लागू किया गया है। न्यूकैसल यूनिवर्सिटी एसिंक्रोनस डिज़ाइन ग्रुप पेज ग्रुप ऑन एल्गोरिदम्स फॉर वी. एल. एस. आई. डिज़ाइन ऑटोमेशन पेज हार्डवेयर डिज़ाइन एंड पेट्री नेट्स, एडः ए. याकोवलेव, एल. लावग्नो और एल. गोम्स, स्प्रिंगर, 2002 ऑटोमेटा (गणना)