🔢 mathematics

Average-Radius List-Decodability of Random Linear Codes

यह शोध पत्र सिद्ध करता है कि किसी भी वर्णमाला $\mathbb{F}_q$ पर यादृच्छिक रैखिक कोड (random linear codes), $O(1/\epsilon)$ के सूची आकार (list size) के साथ औसत-त्रिज्या सूची-डिकोडिंग (average-radius list-decoding) के लिए इष्टतम दर प्राप्त करते हैं, जिससे पिछले परिणाम जो केवल बाइनरी रैखिक कोड और सामान्य गैर-रैखिक कोड के लिए ज्ञात थे, को किसी भी अभाज्य घात वाली वर्णमालाओं पर रैखिक कोडों के व्यापक परिवेश तक विस्तारित किया गया है।

मूल लेखक: Venkatesan Guruswami, Shilun Li, Mihir Singhal

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

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

CC BY 4.0

मूल लेखक: Venkatesan Guruswami, Shilun Li, Mihir Singhal

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

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

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

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

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

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

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

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

तकनीकी सारांश: रैंडम लीनियर कोड्स की औसत-त्रिज्या सूची-डिकोडेबिलिटी (Average-Radius List-Decodability)

समस्या विवरण
यह कार्य $\mathbb{F}_q$ के परिमित क्षेत्रों (finite fields) पर रैंडम लीनियर कोड्स की कॉम्बिनेटोरियल लिस्ट-डिकोडेबिलिटी को संबोधित करता है, जो लिस्ट-डिकोडिंग क्षमता के करीब दरों (rates) तक पहुँचती है। विशेष रूप से, यह औसत-त्रिज्या सूची-डिकोडेबिलिटी (average-radius list-decodability) गुण की जांच करता है, जो मानक सूची-डिकोडिंग का एक अधिक सशक्त संस्करण है।

जबकि मानक $(p, L)$ -सूची-डिकोडेबिलिटी के लिए यह आवश्यक है कि $pn$ त्रिज्या वाले किसी भी हैमिंग बॉल (Hamming ball) में $L$ से अधिक कोडवर्ड न हों, औसत-त्रिज्या $(p, L)$ -सूची-डिकोडेबिलिटी यह मांग करती है कि किसी भी केंद्र $y \in \mathbb{F}_q^n$ के लिए, $L+1$ निकटतम कोडवर्ड का औसत भिन्नात्मक हैमिंग दूरी (fractional Hamming distance) $p$ से कड़ाई से अधिक होनी चाहिए। यह एक अधिक सशक्त स्थिति है क्योंकि औसत दूरी हमेशा अधिकतम दूरी से कम होती है।

इस कार्य से पूर्व, यह ज्ञात था कि:

सामान्य रैंडम कोड्स $O(1/\epsilon)$ सूची आकार के साथ औसत-त्रिज्या सूची-डिकोडेबिलिटी प्राप्त करते हैं (Elias, 1991)।
रैंडम बाइनरी लीनियर कोड्स इसे $O(1/\epsilon)$ के साथ प्राप्त करते हैं (Guruswami et al., 2021)।
गैर-बाइनरी रैंडम लीनियर कोड्स के लिए, औसत-त्रिज्या सूची-डिकोडेबिलिटी के लिए सर्वोत्तम ज्ञात सीमा $O(1/\epsilon^2)$ थी (जो Rudra और Wootters, 2018 द्वारा एक मानक सूची-डिकोडिंग परिणाम को औसत-त्रिज्या सेटिंग पर लागू करके प्राप्त की गई थी)।

मुख्य खुला प्रश्न यह था कि क्या सामान्य वर्णमाला $\mathbb{F}_q$ पर रैंडम लीनियर कोड्स औसत-त्रिज्या सूची-डिकोडिंग के लिए इष्टतम $O(1/\epsilon)$ सूची आकार प्राप्त कर सकते हैं, जो सामान्य रैंडम कोड्स और बाइनरी लीनियर कोड्स के प्रदर्शन से मेल खाता हो।

कार्यप्रणाली और प्रमाण दृष्टिकोण
लेखक Guruswami, Håstad, और Kopparty (GHK, 2010) की प्रमाण रणनीति को अनुकूलित करते हैं, जिसने गैर-बाइनरी रैंडम लीनियर कोड्स के मानक सूची-डिकोडिंग के लिए $O(1/\epsilon)$ सूची-डिकोडेबिलिटी स्थापित की थी। हालाँकि, GHK तर्क हैमिंग बॉल्स की ज्यामितीय संरचना और इस तथ्य पर बहुत अधिक निर्भर करता है कि सभी विचारित कोडवर्ड एक निश्चित त्रिज्या के भीतर ही स्थित होते हैं। यह ज्यामितीय "बढ़ते-सपोर्ट्स" (increasing-supports) वाला तर्क औसत-त्रिज्या सेटिंग में विफल हो जाता है, जहाँ कोडवर्ड को केवल औसतन निकट होना आवश्यक है, न कि व्यक्तिगत रूप से बॉल के भीतर।

इसे दूर करने के लिए, शोध पत्र में दो नए तकनीकी घटक पेश किए गए हैं जो GHK प्रमाण के ज्यामितीय चरणों को प्रतिस्थापित करते हैं:

जेन्सन/एन्ट्रॉपी काउंटिंग बाउंड (लेम्मा 6): एक बॉल में वेक्टर्स की संख्या को सीमित करने के बजाय, लेखक एक छोटे रैखिक रूप से स्वतंत्र सेट के "कुल भार घाटे" (total weight deficit) को नियंत्रित करते हैं। वे $q$ -ary एन्ट्रॉपी फंक्शन $h_q$ पर जेन्सन की असमानता (Jensen's inequality) का उपयोग यह दिखाने के लिए करते हैं कि आकार $L = \Theta(1/\epsilon)$ का एक रैखिक रूप से स्वतंत्र सेट एक बड़ा कुल घाटा नहीं रख सकता (अर्थात, सेट में वेक्टर्स $v$ के लिए $\sum (pn - |v|)$ बहुत अधिक नहीं हो सकता)।
ग्रीडी-बेसिस तर्क (Greedy-Basis Argument): लेखक निकटतम कोडवर्ड्स (या कोड और एक केंद्र के स्पैन में तत्वों) को बढ़ते हुए भार के क्रम में व्यवस्थित करते हैं। वे लालची (greedily) रूप से एक अधिकतम रैखिक रूप से स्वतंत्र उप-अनुक्रम निकालते हैं। स्पैन-बॉल थ्योरम (लेम्मा 5, GHK से अनुकूलित) का उपयोग करते हुए, वे सिद्ध करते हैं कि यह ग्रीडी बेसिस पूरी क्रमबद्ध सूची में बार-बार दिखाई देनी चाहिए। विशेष रूप से, $r$ बेसिस वेक्टर्स का स्पैन एक बॉल के भीतर अधिकतम $O(r)$ वेक्टर्स को ही समाहित कर सकता है। यह नियमितता लेखकों को पूरे निकटतम कोडवर्ड्स के सेट से स्वतंत्र बेसिस वेक्टर्स से घाटे के बाउंड को स्थानांतरित करने की अनुमति देती है, जिससे उनकी औसत दूरी सीमित हो जाती है।

प्रमुख परिणाम
मुख्य प्रमेय (थ्योरम 1) स्थापित करता है कि:

प्रमेय: प्रत्येक प्राइम पावर $q$ और प्रत्येक $p \in (0, 1-1/q)$ के लिए, एक रैंडम $\mathbb{F}_q$ -लीनियर कोड जिसकी दर $R = 1 - h_q(p) - \epsilon$ है, प्रायिकता $1 - q^{-\Omega(n)}$ के साथ $(p, C_{p,q}/\epsilon)$ -औसत-त्रिज्या सूची-डिकोडेबल है।
यहाँ, $C_{p,q}$ एक स्थिरांक है जो केवल $p$ और $q$ पर निर्भर करता है।
यह परिणाम सामान्य रैंडम कोड्स और बाइनरी लीनियर कोड्स द्वारा प्राप्त $O(1/\epsilon)$ सूची आकार से मेल खाता है, जो गैर-बाइनरी लीनियर कोड्स के लिए अंतराल को हल करता है।

प्रमाण दो लेम्मा पर आधारित है:

लेम्मा 5 (स्पैन-बॉल बाउंड): उच्च प्रायिकता के साथ, एक हैमिंग बॉल के भीतर किसी भी छोटे रैखिक रूप से स्वतंत्र सेट के वेक्टर्स का स्पैन, बॉल के साथ केवल $O(|S|)$ वेक्टर्स के माध्यम से प्रतिच्छेद करता है।
लेम्मा 6 (डेफिसिट बाउंड): उच्च प्रायिकता के साथ, कोड (और एक केंद्र) के स्पैन में कोई भी छोटा रैखिक रूप से स्वतंत्र सेट $\epsilon n$ से अधिक कुल भार घाटा नहीं रख सकता।

महत्व और दावे
शोध पत्र दावा करता है कि यह GHK (2010) के परिणाम को सामान्य रैंडम लीनियर कोड्स के लिए अधिक मजबूत औसत-त्रिज्या गारंटी तक विस्तारित करता है, जो समान इष्टतम सूची आकार $O(1/\epsilon)$ बनाए रखता है।

एकीकरण: यह विभिन्न वर्णमाला आकारों और डिकोडिंग वेरिएंट (मानक बनाम औसत-त्रिज्या) के लिए रैंडम लीनियर कोड्स की सूची-डिकोडेबिलिटी की समझ को एकीकृत करता है।
ज्यामितीय बाधाओं पर विजय: यह कार्य प्रदर्शित करता है कि मानक सूची-डिकोडिंग के लिए GHK प्रमाण में निहित ज्यामितीय बाधाएं औसत-त्रिज्या मामले के लिए आवश्यक नहीं हैं; इसके बजाय, एन्ट्रॉपी-आधारित काउंटिंग और ग्रीडी बेसिस एक्सट्रैक्शन पर्याप्त हैं।
सीमाएँ: लेखक नोट करते हैं कि जबकि सूची आकार $O(1/\epsilon)$ है, स्थिरांक $C_{p,q}$ जैसे-जैसे $p \to 1 - 1/q$ (उच्च-शोर शासन) की ओर बढ़ता है, वैसे ही घटता जाता है। वे इस प्रश्न को खुला छोड़ देते है कि क्या एक पूर्ण स्थिरांक $C$ (जो $p$ और $q$ से स्वतंत्र हो) प्राप्त किया जा सकता है, जो बाइनरी मामले के लिए ज्ञात है लेकिन सामान्य $q$ के लिए खुला है।

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

इसी तरह के और पेपर