🔢 mathematics

Improved Capacity Upper Bounds for the Deletion Channel using a Parallelized Blahut-Arimoto Algorithm

यह शोध पत्र बाइनरी डिलीशन चैनल की क्षमता पर बेहतर ऊपरी सीमाएँ स्थापित करने के लिए ब्लाट-आरिमोटो एल्गोरिदम के एक GPU-समानांतर कार्यान्वयन को प्रस्तुत करता है, जो विशेष रूप से यह दर्शाता है कि $d \geq 0.64$ के लिए डिलीशन प्रायिकता $d$ हेतु क्षमता अधिकतम $0.3578(1-d)$ है।

मूल लेखक: Martim Pinto, João Ribeiro

प्रकाशित 2026-04-08

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

CC BY 4.0

मूल लेखक: Martim Pinto, João Ribeiro

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

कल्पना कीजिए कि आप अपने एक दोस्त को वॉकी-टॉकी पर एक गुप्त संदेश भेजने की कोशिश कर रहे हैं, लेकिन कनेक्शन बहुत खराब है। हर बार जब आप कोई शब्द बोलते हैं, तो शोर (static) के कारण उस शब्द के गायब होने की संभावना रहती है। आपके दोस्त को उन शब्दों की एक उलझी हुई सूची सुनाई देती है जो गायब नहीं हुए, लेकिन उन्हें यह पता नहीं होता कि कौन से शब्द गायब हुए हैं या वे पहले कहाँ थे।

कंप्यूटर विज्ञान की दुनिया में, इसे बाइनरी डिलीशन चैनल (Binary Deletion Channel) कहा जाता है। आप 0 और 1 की एक स्ट्रिंग भेजते हैं, और उनमें से कुछ गायब हो जाते हैं। सबसे बड़ा सवाल जो वैज्ञानिक दशकों से पूछ रहे हैं, वह यह है: आप इस टूटे हुए चैनल के माध्यम से वास्तव में कितनी जानकारी भेज सकते हैं इससे पहले कि यह डिकोड करना असंभव हो जाए? इस सीमा को "कैपेसिटी" (क्षमता) कहा जाता है।

लंबे समय तक, हमारे पास इस सीमा का केवल एक बहुत ही मोटा अनुमान था, लेकिन यह समुद्र को एक चम्मच से मापने की कोशिश करने जैसा था। यह शोध पत्र इसे मापने का एक नया, बहुत अधिक सटीक तरीका प्रस्तुत करता है।

यहाँ बताया गया है कि लेखकों ने इस काम को कैसे किया, जिसे भारी गणित के बिना समझाया गया है।

1. समस्या: "ब्रूट फोर्स" की बाधा

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

जासूस को संदेशों के हर संभव संयोजन (combination) की जांच करनी होती है।

यदि आपका संदेश 10 बिट लंबा है, तो 1,024 संयोजन हैं। आसान है।
यदि आपका संदेश 20 बिट लंबा है, तो दस लाख से अधिक संयोजन हैं। कठिन है।
यदि आपका संदेश 30 बिट लंबा है, तो एक अरबों से भी अधिक संयोजन हैं।

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

2. समाधान: "सुपर-पावर्ड टीम"

लेखों ने महसूस किया कि जासूस एक छोटे से कमरे में अकेला काम कर रहा था। उन्होंने एक साथ काम करने के लिए हजारों जासूसों की एक टीम को काम पर रखने का फैसला किया।

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

उन्होंने एल्गोरिदम को इस तरह से फिर से लिखा ताकि एक जासूस द्वारा एक संदेश की जांच करने के बजाय, 1,000 जासूस एक ही समय में 1,000 अलग-अलग संदेशों की जांच कर सकें।

3. तरकीब: स्मार्ट शॉर्टकट

भले ही 1,000 लोगों की टीम के साथ भी, काम अभी भी बहुत बड़ा होता यदि उन्हें हर बार शून्य से शुरुआत करनी पड़ती। इसलिए, लेखकों ने दो चतुर तरकीबें जोड़ीं:

"चीट शीट" (पूर्व-गणना/Pre-computation): हर बार शून्य से यह गणना करने के बजाय कि एक संदेश डिलीट होने की कितनी संभावना है, उन्होंने समस्या के छोटे हिस्सों के लिए "चीट शीट" की एक विशाल लाइब्रेरी बनाई। जब जासूसों को उत्तर की आवश्यकता होती, तो वे गणित करने के बजाय लाइब्रेरी में उत्तर देख लेते थे।
"व्यवस्थित खोज" (एनुमरेशन/Enumeration): कल्पना कीजिए कि आपके पास लेगो (Lego) ब्रिक्स का एक बड़ा डिब्बा है और आपको यह पता लगाना है कि आप ठीक 5 ब्रिक्स ऊंचे कितने टावर बना सकते हैं। एक साधारण व्यक्ति हर एक टावर को एक-एक करके बनाने की कोशिश करेगा और यदि वे बहुत छोटे हुए तो उन्हें फेंक देगा।
लेखकों ने एक विशेष प्रोग्राम लिखा जो एक स्मार्ट लाइब्रेरियन की तरह काम करता है। बनाने और नष्ट करने के बजाय, लाइब्रेरियन को पता होता है कि अगला वैध टावर बनाने के लिए कौन सा ब्रिक कहाँ लगेगा। वे पहले 499 टावर बनाने के बजाय सीधे 500वें वैध टावर पर जा सकते हैं। इसने उनका बहुत सारा समय बचाया।

4. परिणाम: एक सटीक सीमा

सुपर-पावर्ड टीम (GPUs) और स्मार्ट शॉर्टकट (चीट शीट्स और व्यवस्थित खोज) को मिलाकर, लेखक 31 बिट लंबे संदेशों तक की पहेली को हल करने में सक्षम हुए।

यह शायद 28 से 31 तक का बहुत बड़ा उछाल न लगे, लेकिन घातांकीय गणित (exponential math) की दुनिया में, यह एक बड़ी छलांग है। इसने उन्हें यह गणना करने की अनुमति दी कि सूचना भेजी जा सकती है इसकी एक बहुत ही सटीक "ऊपरी सीमा" (ceiling) क्या है।

बड़ी खोज:
उन्होंने पाया कि यदि चैनल बहुत शोर वाला है (यानी बिट्स 64% से अधिक समय तक डिलीट हो रहे हैं), तो कैपेसिटी शेष बचे हुए बिट्स का अधिकतम 0.3578 गुना है।

पिछला सबसे अच्छा अनुमान: "आप हर जीवित बचे बिट के लिए लगभग 0.3745 बिट जानकारी भेज सकते हैं।"
नया परिणाम: "नहीं, वास्तव में, आप केवल लगभग 0.3578 बिट ही भेज सकते हैं।"

यह एक छोटा नंबर है, लेकिन इस क्षेत्र में, उस मामूली हिस्से को भी कम कर देना एक बड़ी जीत है। यह इंजीनियरों को ठीक-ठीक बताता है कि वे अपने डीएनए स्टोरेज या सैटेलाइट लिंक पर कितना भरोसा कर सकते हैं, इससे पहले कि सिग्नल बेकार हो जाए।

सारांश उपमा (Summary Analogy)

कल्पना कीजिए कि आप एक ऐसे शहर में घर की कीमत का अनुमान लगाने की कोशिश कर रहे हैं जहाँ वास्तविक लिस्टिंग हवा के कारण लगातार फट रही हैं।

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

यह शोध पत्र सिद्ध करता है कि सही उपकरणों (पैरेलल कंप्यूटिंग) और सही रणनीति (स्मार्ट एन्यूमरेशन) के साथ, हम उन समस्याओं को हल कर सकते हैं जिन्हें पहले सुलझाना असंभव माना जाता था।

यहाँ मार्टिम पिंटो और जोआओ रिबेरो के शोध पत्र "Improved Capacity Upper Bounds for the Deletion Channel using a Parallelized Blahut-Arimoto Algorithm" का विस्तृत तकनीकी सारांश दिया गया है।

1. समस्या विवरण (Problem Statement)

यह शोध पत्र बाइनरी डिलीशन चैनल (BDC) की क्षमता (capacity) निर्धारित करने की दीर्घकालिक खुली समस्या को संबोधित करता है।

BDC मॉडल: एक ऐसा चैनल जहाँ एक इनपुट बिटस्ट्रिंग $x \in \{0, 1\}^n$ प्रसारित की जाती है, और प्रत्येक बिट को प्रायिकता $d$ के साथ स्वतंत्र रूप से हटा (delete) दिया जाता है। आउटपुट शेष उप-अनुक्रम (subsequence) होता है।
चुनौती: बाइनरी इरेज़र चैनल (जहाँ हटाए गए बिट्स को "?" के रूप में चिह्नित किया जाता है) के विपरीत, BDC सिंक्रोनाइज़ेशन (तालमेल) का नुकसान करता है। रिसीवर को यह ज्ञात नहीं होता कि आउटपुट का विशिष्ट बिट किस इनपुट बिट के अनुरूप है। यह म्यूचुअल इंफॉर्मेशन (mutual information) और चैनल क्षमता की गणना को विश्लेषणात्मक रूप से असाध्य (intractable) बना देता है।
वर्तमान स्थिति: जबकि लोअर बाउंड्स (lower bounds) मौजूद हैं, सर्वोत्तम ज्ञात अपर बाउंड्स (upper bounds) इस चैनल के "परिमित-लंबाई" (finite-length) संस्करणों ( $C_n(d)$ ) की क्षमता को संख्यात्मक रूप से अनुमानित करने और इस असमिका (inequality) $C(d) \leq \frac{1}{n}C_n(d)$ का उपयोग करने पर निर्भर करते हैं।
बाधा (Bottleneck): $C_n(d)$ की गणना के लिए ब्लाहु-अरिमोटो एल्गोरिदम (BAA) की आवश्यकता होती है। हालाँकि, BAA की समय और स्थान जटिलता (time and space complexity) इनपुट लंबाई $n$ के साथ घातीय (exponentially) रूप से बढ़ती है (इनपुट वर्णमाला के आकार के लिए विशेष रूप से $O(2^n)$ )। पिछले अत्याधुनिक कार्यान्वयन (रुबिनस्टीन और कॉन, 2023) मेमोरी और कंप्यूटेशनल बाधाओं के कारण $n \approx 28$ तक ही सीमित थे, जो बड़े $n$ के लिए कड़े बाउंड्स प्राप्त करने से रोकता था।

2. कार्यप्रणाली (Methodology)

लेखक एक अत्यधिक अनुकूलित BAA कार्यान्वयन का प्रस्ताव करते हैं जो डिलीशन चैनल के लिए विशेष रूप से तैयार किया गया है, जो पिछले स्केलेबिलिटी अवरोधों को दूर करने के लिए GPU पैरेललाइजेशन और डायनेमिक प्रोग्रामिंग का लाभ उठाता है।

अ. एल्गोरिथमिक अनुकूलन (Algorithmic Optimizations)

उनका दृष्टिकोण BAA के पुनरावृत्ति चरणों (iterative steps) को अनुकूलित करने पर केंद्रित है, विशेष रूप से सहायक फलन (auxiliary function) $W^{(t)}(x)$ और चैनल आउटपुट वितरण $Y^{(t)}(y)$ की गणना को।

GPU पैरेललाइजेशन (CUDA):
- लेखक BAA पुनरावृत्तियों को CUDA कर्नेल (kernels) में मैप करते हैं।
- पैरेललाइजेशन रणनीति: एक समय में एक इनपुट स्ट्रिंग $x$ को प्रोसेस करने के बजाय, वे प्रत्येक विशिष्ट इनपुट $x$ को एक अलग GPU ब्लॉक को सौंपते हैं। प्रत्येक ब्लॉक के भीतर, 1024 थ्रेड्स समानांतर में कार्य करते हैं।
- कार्य अपघटन (Task Decomposition): दिए गए $x$ के लिए, $\log W^{(t)}(x)$ की गणना में सभी संभावित आउटपुट उप-अनुक्रमों $y$ का योग शामिल है। थ्रेड्स उप-अनुक्रमों के सेट $S_{x,k}$ को विभाजित करते हैं और समानांतर में आंशिक योग (partial sums) की गणना करते हैं, जिन्हें फिर एक अंतिम मान में कम (reduce) किया जाता है।
कुशल उप-अनुक्रम गणना (Efficient Subsequence Enumeration - Unranking):
- एक सहज (naive) दृष्टिकोण में सभी उप-अनुक्रमों को संग्रहीत करने या उनके माध्यम से अक्षम रूप से पुनरावृत्ति करने की आवश्यकता होगी। लेखक एक डायनेमिक प्रोग्रामिंग-आधारित अनरैंकिंग एल्गोरिदम (एल्गोरिदम 4) लागू करते हैं।
- पूर्व-गणना की गई तालिकाएँ (Pre-computed Tables): वे दो तालिकाओं का उपयोग करते हैं, NextPos (0 या 1 के अगले प्रसंग को खोजना) और Count (एक विशिष्ट इंडेक्स से शुरू होने वाले वैध उप-अनुक्रमों को गिनना)।
- जटिलता: यह एक थ्रेड को पूरे उप-अनुक्रमों की सूची संग्रहीत किए बिना $O(k)$ समय में $j$ -वें लेक्सिकोग्राफिकल (lexicographical) उप-अनुक्रम को उत्पन्न करने की अनुमति देता है, जिससे मेमोरी का उपयोग काफी कम हो जाता है।
कुशल सुपरसीक्वेंस गणना (Efficient Supersequence Enumeration):
- इसी प्रकार, आउटपुट $y$ के लंबाई- $n$ के सुपरसीक्वेंस (supersequences) को सूचीबद्ध करने के लिए, एल्गोरिदम को आउटपुट संभाव्यता $Y^{(t)}(y)$ की गणना करनी होती है।
- वे एक रिकर्सिव विधि (एल्गोरिदम 6) का उपयोग करते हैं जो एक इंडेक्स को एक विशिष्ट सुपरसीक्वेंस से मैप करता है, पहले "अनमैच्ड" बिट स्थितियों के एक उपसमुच्चय का चयन करता है और फिर शेष को भरता है। यह भी प्रति थ्रेड $O(n)$ है।
रुबिनस्टीन-कॉन के साथ हाइब्रिड दृष्टिकोण:
- लेखक रुबिनस्टीन और कॉन (2023) के "लूप-नेस्ट" अनुकूलन और कैश-आधारित ट्रांजिशन प्रोबेबिलिटी गणना को बनाए रखते हैं। वे छोटे सब-चैनलों ( $n' \approx n/2$ ) के लिए ट्रांजिशन प्रोबेबिलिटी को पूर्व-गणना करते हैं ताकि उन्हें शून्य से पुनर्गणना न करना पड़े, जिसे उनकी नई समानांतर गणना तकनीकों के साथ जोड़ा गया है।

3. मुख्य योगदान (Key Contributions)

GPU-त्वरित BAA: डिलीशन चैनल के लिए ब्लाहु-तिमटो एल्गोरिदम का पहला कार्यान्वयन जो विशाल स्टेट स्पेस को संभालने के लिए पूर्ण रूप से GPU पैरेललिज्म का लाभ उठाता है।
विस्तारित इनपुट लंबाई: यह पद्धति सफलतापूर्वक $n = 31$ (विशेष रूप से $k \leq 18$ के लिए $C_{31,k}$ ) तक की इनपुट लंबाई के लिए क्षमता अनुमानों की गणना करती है, जो पिछले $n=28$ के सीमा को पार कर जाती है।
नए अपर बाउंड्स: बड़े $n$ के लिए $C_{n,k}$ की गणना करके, लेखक एसिम्प्टोटिक क्षमता $C(d)$ के लिए काफी कड़े अपर बाउंड्स प्राप्त करते हैं।
एसिम्प्टोटिक सुधार: वे उच्च-शोर शासन (high-noise regime, $d \to 1$ ) के लिए एक नया रैखिक बाउंड स्थापित करते हैं।

4. परिणाम (Results)

लेखक डिलीशन प्रोबेबिलिटी की सीमा में $C(d)$ के लिए बेहतर अपर बाउंड रिपोर्ट करते हैं।

उच्च-शोर शासन ( $d \geq 0.64$ ):
- $d=0.64$ पर अपने सुधारे गए बाउंड को रहमती और डुमन (2015) के परिणाम के साथ जोड़कर, वे सिद्ध करते हैं:
  $C(d) \leq 0.3578(1 - d) \quad \text{सभी } d \geq 0.64 \text{ के लिए}$
- तुलना: यह रुबिनस्टीन और कॉन द्वारा स्थापित पिछले सर्वोत्तम बाउंड $0.3745(1-d)$ (जो $d \geq 0.68$ के लिए मान्य है) में सुधार करता है।
विशिष्ट बाउंड्स:
- उन्होंने $1 \leq k \leq 28$ के लिए सभी $C_{29,k}$ और $1 \leq k \leq 18$ के लिए $C_{31,k}$ के अपर बाउंड की गणना की।
- $n=29$ के लिए, गणनाओं में RTX 5070 Ti GPU पर 5 दिन तक का समय लगा, जिसमें $k \approx n/2$ के लिए पुनरावृत्ति (iterations) में ~400 सेकंड लगे।
- $n=31$ के लिए, जटिलता काफी बढ़ गई, जिसमें $k \geq 14$ के लिए 800 सेकंड से अधिक के पुनरावृत्ति समय के कारण उच्च टॉलरेंस थ्रेसहोल्ड की आवश्यकता पड़ी।

5. महत्व (Significance)

अंतराल को कम करना (Tightening the Gap): बाइनरी डिलीशन चैनल की क्षमता सूचना सिद्धांत (information theory) की सबसे प्रसिद्ध खुली समस्याओं में से एक है। यह कार्य ज्ञात लोअर और अपर बाउंड्स के बीच के अंतर को कम करता है, विशेष रूप से उच्च-डिलीशन प्रोबेबिलिटी शासन में जहाँ चैनल का उपयोग करना सबसे कठिन होता है।
पद्धतिगत प्रगति: यह शोध पत्र प्रदर्शित करता है कि कैसे विशेष GPU पैरेललाइजेशन को कॉम्बिनेटोरियल एन्यूमरेशन तकनीकों (unranking) के साथ जोड़कर उन घातीय मेमोरी बाधाओं को दूर किया जा सकता है जिन्होंने दशकों से सूचना-सैद्धांतिक अनुसंधान को सीमित कर रखा है।
व्यावहारिक निहितार्थ: जैसे-जैसे DNA-आधारित डेटा स्टोरेज वास्तविकता बन रहा है, सिंक्रोनाइज़ेशन चैनलों (जैसे BDC) की सीमाओं को समझना कुशल कोडिंग स्कीम्स डिजाइन करने के लिए महत्वपूर्ण है। बेहतर बाउंड्स कोड डिजाइनरों के लिए एक अधिक सटीक लक्ष्य प्रदान करते हैं।
पुनरुत्पादकता (Reproducibility): लेखकों ने अपना कार्यान्वयन GitHub पर सार्वजनिक रूप से उपलब्ध कराया है, जिससे आगे के शोध और सत्यापन की सुविधा मिलती है।

संक्षेप में, पिंटो और रिबेरो ने एक मेमोरी-बाउंड अनुक्रमिक समस्या को एक समानांतर योग्य GPU कार्य में बदलकर डिलीशन चैनल की क्षमता के संख्यात्मक अनुमान की सीमाओं को सफलतापूर्वक आगे बढ़ाया है, जिससे अब तक के BDC क्षमता के सबसे कड़े ज्ञात अपर बाउंड प्राप्त हुए हैं।