🔢 mathematics

Codes for Metastability-Containing Addition

यह शोध पत्र अंतराल (इंटरवल) के रूप में प्रस्तुत अनिश्चित मानों को जोड़ने की चुनौती को संबोधित करता है, जिसमें अनिश्चितता को बनाए रखने के लिए कोड दरों पर एक ऊपरी सीमा स्थापित की गई है और एक स्पर्शोन्मुखी अनुकूलतम (एसिम्प्टोटिकली ऑप्टिमल) रिकवरेबल कोड को डिजाइन किया गया है जो मेटास्टेबल बिट्स के कारण होने वाले अनिश्चितता के प्रवर्धन को रोकता है।

मूल लेखक: Johannes Bund, Christoph Lenzen, Moti Medina

प्रकाशित 2026-02-09

📖 6 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: Johannes Bund, Christoph Lenzen, Moti Medina

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

यहाँ इस शोध पत्र (paper) का सरल भाषा और रोज़मर्रा के उदाहरणों के साथ विवरण दिया गया है।

समस्या: "धुंधले" (Fuzzy) नंबरों को जोड़ना

कल्पना कीजिए कि आप दो संख्याओं को जोड़ने की कोशिश कर रहे हैं, लेकिन आपको उनके सटीक मान (values) पता नहीं हैं। इसके बजाय, आप केवल इतना जानते हैं कि वे एक छोटी सी सीमा (range) के भीतर आती हैं।

संख्या A 25 और 26 के बीच में कहीं है।
संख्या B ठीक 37 है।

एक आदर्श दुनिया में, आप केवल सीमाओं को जोड़ देंगे: $25+37=62$ और $26+37=63$ । तो, आपका उत्तर होगा "62 और 63 के बीच कहीं।" इसे इंटरवल एडिशन (interval addition) कहा जाता है।

हालाँकि, कंप्यूटर चिप्स की दुनिया में चीजें गड़बड़ा जाती हैं। कभी-कभी, एक सिग्नल (बिट) मेटास्टेबिलिटी (metastability) नामक भ्रम की स्थिति में फंस जाता है। यह एक ऐसे लाइट स्विच की तरह है जो "ऑन" और "ऑफ" के बीच आधा फंसा हुआ है। यह 0 पर स्थिर हो सकता है, या 1 पर, लेकिन अभी यह "X" (अज्ञात) है।

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

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

लक्ष्य: एक "फजी-प्रूफ" (Fuzzy-Proof) कोड

शोधकर्ताओं ने नंबरों को लिखने का एक नया तरीका (एनकोडिंग) खोजने की कोशिश की ताकि जब आप उन्हें जोड़ें, तो "धुंधलापन" (अनिश्चितता) बढ़े नहीं। वे इसे प्रिसिजन को बनाए रखना (preserving precision) कहते हैं।

वे एक ऐसा तरीका भी चाहते थे जिससे परिणाम को देखकर यह कहा जा सके, "ठीक है, भले ही यह धुंधला है, लेकिन मैं आपको निश्चित रूप से बता सकता हूँ कि उत्तर 62 और 63 के बीच है।" वे इसे रिकवरेबिलिटी (recoverability) कहते हैं।

समाधान: "हाइब्रिड" कोड

टीम ने नंबरों को लिखने का एक नया तरीका बनाया जिसे हाइब्रिड कोड (Hybrid Code) कहा जाता है। इसे नंबरों के लिए एक दो-भाग वाली एड्रेस प्रणाली के रूप में समझें:

"कोर्स" भाग (पड़ोस/Neighborhood): यह भाग एक विशेष कोड का उपयोग करता है जिसे ग्रे कोड (Gray Code) कहा जाता है। ग्रे कोड में, जब आप गिनती करते हैं (1, 2, 3...), तो आप एक बार में केवल एक ही बिट बदलते हैं। यह एक ऐसी सड़क पर चलने जैसा है जहाँ आप अपना घर नंबर एक बार में केवल एक अंक से बदलते हैं। यह सुनिश्चित करता है कि यदि आप अपनी स्थिति को लेकर थोड़े भ्रमित हैं, तो आप केवल अपने आस-पास के पड़ोसियों के बारे में भ्रमित होंगे, पूरे शहर के बारे में नहीं।
"फाइन" भाग (घर का नंबर/House Number): यह भाग यूनेरी कोड (Unary Code) का उपयोग करता है। कल्पना कीजिए कि लाइट स्विचों की एक पंक्ति है। संख्या 3 को दर्शाने के लिए, आप पहले तीन स्विच चालू करते हैं (111000)। 4 के लिए, आप पहले चार चालू करते हैं (111100)। यह बहुत अधिक रेडंडेंट (अधिक बिट्स का उपयोग करने वाला) है, लेकिन यह बहुत मजबूत (robust) है। यदि एक स्विच बीच में फंसा हुआ है, तो भी आप सटीक रूप से बता सकते हैं कि आप किन नंबरों की सीमा में हैं।

ये दोनों मिलकर कैसे काम करते हैं:
हाइब्रिड कोड इन दोनों को मिलाता है। ग्रे कोड वाला भाग "बड़ी तस्वीर" (पड़ोस) बताता है, और यूनेरी भाग "विवरण" (विशिष्ट घर) बताता है।

जादुई ट्रिक: शोधकर्ताओं ने इसे इस तरह डिज़ाइन किया है कि ग्रे कोड वाले हिस्से का "धुंधलापन" यूनेरी भाग की स्थिरता द्वारा संभाला जाता है, और इसके विपरीत भी।
परिणाम: जब आप इस कोड का उपयोग करके दो धुंधले नंबरों को जोड़ते हैं, तो उत्तर में "धुंधलापन" इनपुट के धुंधलेपन के बराबर ही होता है। यह विस्फोट नहीं करता।

ट्रेड-ऑफ (समझौता): रेडंडेंसी (Redundancy)

इसे काम करने के लिए, आपको एक कीमत चुकानी होगी: रेडंडेंसी।

मानक बाइनरी: 100 लिखने के लिए, आपको 7 बिट्स ($1100100$) की आवश्यकता होती है।
हाइब्रिड कोड: इस नए सुरक्षा फीचर के साथ 100 लिखने के लिए, आपको अधिक बिट्स की आवश्यकता होगी (पड़ोस के लिए 7 बिट्स + घर के विवरण के लिए अतिरिक्त बिट्स)।

शोध पत्र एक गणितीय नियम सिद्ध करता है: आप एक ऐसा कोड नहीं बना सकते जो पूरी तरह से सटीक और पूरी तरह से रिकवरेबल हो बिना अतिरिक्त बिट्स जोड़े। यदि आप एक निश्चित मात्रा में "धुंधलेपन" को संभालना चाहते हैं, तो आपको उस जानकारी को संग्रहीत करने के लिए अतिरिक्त स्थान का उपयोग करना ही होगा।

सर्किट: इन्हें कैसे जोड़ा जाता है

शोध पत्र यह भी बताता है कि इस जोड़ को करने के लिए एक भौतिक सर्किट (मशीन) कैसे बनाया जाए।

अनुवाद (Translation): सबसे पहले, मशीन हाइब्रिड कोड को मानक बाइनरी नंबरों में बदल देती है (ताकि वह सामान्य कैलकुलेटर का उपयोग कर सके)।
जोड़ (Addition): यह नंबरों को जोड़ती है।
वापस अनुवाद: यह परिणाम को वापस हाइब्रिड कोड में बदल देती है।
सुरक्षा जाल (Safety Net): उन्होंने मशीन को इस तरह डिज़ाइन किया है कि भले ही इनपुट सिग्नल "फंसे" (metastable) हों, मशीन क्रैश नहीं होती या गलत आउटपुट नहीं देती। यह सबसे अच्छा संभव "धुंधला" उत्तर देती है जो इनपुट से मेल खाता है।

शोध पत्र में उल्लेखित वास्तविक दुनिया का उदाहरण

लेखक एक विशिष्ट स्थान का उल्लेख करते हैं जहाँ यह उपयोगी है: फॉल्ट-टॉलरेंट क्लॉक सिंक्रोनाइज़ेशन (Fault-tolerant Clock Synchronization)।

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

सारांश

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

तकनीकी सारांश: मेटास्टेबिलिटी-युक्त जोड़ (Addition) के लिए कोड्स

समस्या विवरण (Problem Statement)
यह शोध पत्र अनिश्चितता वाले इनपुट्स पर जोड़ (addition) करने की मौलिक चुनौती को संबोधित करता है, विशेष रूप से जब एनालॉग मानों के डिस्क्रीट-वैल्यूड (discrete-valued) माप मेटास्टेबिलिटी (metastability) के प्रति संवेदनशील होते हैं। मानक डिजिटल सर्किटों में, मेटास्टेबल सिग्नल (जिन्हें टर्नरी मान $M$ या $X$ द्वारा दर्शाया जाता है) बाइनरी निरूपणों को बाधित करते हैं। जब ऐसे अस्थिर बिट्स गणना में हस्तक्षेप करते हैं, तो मानक बाइनरी एनकोडिंग अनिश्चितता को बढ़ा देती है। उदाहरण के लिए, एक मानक बाइनरी एडर (adder) में एक एकल मेटास्टेबल इनपुट बिट सभी आउटपुट बिट्स को मेटास्टेबल बना सकता है, जिससे परिणाम पूरी तरह से सूचनाहीन हो जाता है (जैसे कि एक आउटपुट अंतराल जो पूरे रेंज $[0, 2^n-1]$ तक फैला हो)।

जबकि यूनरी (thermometer) एनकोडिंग मेटास्टेबिलिटी के तहत परिशुद्धता (precision) को बनाए रखती है, इसमें सर्किट आकार और विलंबता (latency) में घातांकीय ओवरहेड (exponential overhead) होता है। इसके विपरीत, मानक बाइनरी कोड और ग्रे कोड (Gray codes) उच्च दर (दक्षता) प्रदान करते हैं, लेकिन वे इनपुट अंतराल के निहित निचले और ऊपरी स्तरों (lower and upper bounds) को सुरक्षित रखने में विफल रहते हैं जब मेटास्टेबिलिटी होती है। मुख्य समस्या एक ऐसा एनकोडिंग स्कीम तैयार करने की है जो इनपुट अंतरालों की परिशुद्धता को बनाए रखे (सूचना की हानि को रोकते हुए), जबकि उच्च दर (अनावश्यकता को कम करते हुए) प्राप्त करे और कुशल सर्किट कार्यान्वयन की अनुमति दे।

कार्यप्रणाली और परिभाषाएँ (Methodology and Definitions)
लेखक क्लीने के टर्नरी लॉजिक (Kleene's ternary logic, $T = \{0, 1, M\}$ ) का उपयोग करके इस समस्या को औपचारिक रूप देते हैं, जहाँ $M$ एक मेटास्टेबल सिग्नल को दर्शाता है। वे इस संदर्भ में कोड्स के लिए दो महत्वपूर्ण गुणों को पेश करते हैं:

संरक्षण (Preservation): एक कोड $k$ -preserving है यदि एक विस्तारित कोडवर्ड (एक अंतराल के आकार $k+1$ के सभी कोडवर्ड्स का सुपरपोजिशन) का रेजोल्यूशन मूल अंतराल के बाहर नए कोडवर्ड्स पेश नहीं करता है। यह सुनिश्चित करता है कि आउटपुट अनिश्चितता इनपुट अनिश्चितता के योग के बराबर हो।
रिकवरेबिलिटी (Recoverability): एक कोड $k$ -recoverable है यदि सभी बाइनरी स्ट्रिंग्स (मेटास्टेबिलिटी रेजोल्यूशन से उत्पन्न होने वाले गैर-कोडवर्ड्स सहित) से मूल अंतराल रेंज तक वापस जाने के लिए एक मैपिंग मौजूद है। यह सिस्टम को मेटास्टेबिलिटी हल होने के बाद मूल इनपुट अनिश्चितता के अनुरूप एक मान को निर्धारित रूप से रिकवर करने की अनुमति देता है।

यह शोध पत्र एक सैद्धांतिक निचली सीमा (lower bound) स्थापित करता है, यह सिद्ध करते हुए कि किसी भी $k$ -recoverable कोड के लिए रेडंडेंसी (redundancy) आवश्यक है। विशेष रूप से, एक $n$ -बिट कोड जो $k$ -recoverable है, वह अधिकतम $2^{n-k}(k+1)$ मानों को एनकोड कर सकता है, जो एक रेट अपर बाउंड $O(2^{n-k}k/n)$ का संकेत देता है।

मुख्य योगदान और परिणाम (Key Contributions and Results)
प्राथमिक योगदान एक "हाइब्रिड" कोड ( $\gamma^h_{n,k}$ ) का डिज़ाइन है जो $k$ -preserving और recoverability बाधाओं को पूरा करते हुए स्पर्शोन्मुख रूप से इष्टतम (asymptotically optimal) दर प्राप्त करता है।

हाइब्रिड कोड निर्माण: यह कोड एक $n$ -बिट बाइनरी रिफ्लेक्टेड ग्रे कोड (BRGC) भाग को $k$ -बिट यूनरी थर्मामीटर भाग के साथ जोड़ता है। यूनरी एनकोडिंग का विशिष्ट स्वरूप (या तो $1^i0^{k-i}$ या $0^i1^{k-i}$ ) BRGC भाग की पैरिटी (parity) द्वारा निर्धारित होता है।
प्रदर्शन गारंटी: हाइब्रिड कोड को $k$ -preserving और $\lceil k/2 \rceil$ -recoverable सिद्ध किया गया है। इसका अर्थ है कि यह इनपुट में $k$ अस्थिर बिट्स को बिना आउटपुट इम्प्रेसिजन (imprecision) बढ़ाए सहन कर सकता है, और यह $\lceil k/2 \rceil$ के आकार के अंतरालों को निर्धारित रूप से रिकवर कर सकता है।
सर्किट कार्यान्वयन: लेखक इस कोड के लिए एक एडिशन सर्किट डिजाइन करते हैं।
- स्थिर इनपुट्स के लिए, सर्किट BRGC और यूनरी भागों को बाइनरी में बदलता है, मानक बाइनरी जोड़ करता है, और परिणाम को वापस बदल देता है। इस योजना का आकार $O(n+k)$ और डेप्थ $O(\log n + \log k)$ है।
- मेटास्टेबल इनपुट्स (विस्तारित कोडवर्ड्स) को संभालने के लिए, लेखक मेटास्टेबिलिटी-कंटेनिंग (mc) सर्किट के ज्ञात कंस्ट्रक्शन का उपयोग करते हैं। इकेनमियर (Ikenmeyer) आदि के एक सामान्य कंस्ट्रक्शन का उपयोग करते हुए, वे $(n+k)^{O(k)}$ आकार और $O(k \log n + \log k)$ डेप्थ वाला एक शुद्ध कॉम्बिनेशनल mc एडर प्राप्त करते हैं। वैकल्पिक रूप से, मास्किंग रजिस्टरों का उपयोग करके, वे $O(k(n+k))$ आकार और $O(\log n + \log k)$ डेप्थ प्राप्त करते हैं।
इष्टतमता (Optimality): शोध पत्र सिद्ध करता है कि उनके कोड की दर $k$ -preserving कोड्स के लिए प्राप्त सैद्धांतिक अपर बाउंड से मेल खाती है, जिससे यह स्पर्शोन्मुख रूप से इष्टतम (asymptotically optimal) बन जाता है।

महत्व और दावे (Significance and Claims)
शोध पत्र का दावा है कि यह कार्य यूनरी एनकोडिंग की अक्षमता और मेटास्टेबिलिटी की उपस्थिति में बाइनरी एनकोडिंग की सूचना हानि के बीच के अंतर को पाटता है।

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

शोध पत्र निष्कर्ष निकालता है कि हालांकि हाइब्रिड कोड एक मामूली विषमता (asymmetry) लाता है ( $k$ इम्प्रेसिजन को सहन करना लेकिन केवल $\lceil k/2 \rceil$ को रिकवर करना), यह अनिश्चितता के तहत जोड़ के लिए एक मजबूत, उच्च-दर समाधान प्रदान करता है, जो डिजिटल कंट्रोल लूप्स को मेटास्टेबल इनपुट्स के बावजूद सही ढंग से संचालित करने में सक्षम बनाता है।