🔢 mathematics

Tensor Reed-Muller Codes: Achieving Capacity with Quasilinear Decoding Time

यह शोध पत्र टेंसर उत्पाद (tensor product) के माध्यम से निर्मित टेंसर रीड-मुलर कोड्स को प्रस्तुत करता है, जो यह प्रदर्शित करता है कि वे एक नवीन एल्गोरिदम के माध्यम से चैनल क्षमता (channel capacity) प्राप्त करते हैं, जिसमें प्रतिकूल त्रुटियों (adversarial errors) से किसी भी टेंसर कोड को डिकोड करने की क्षमता है और इसके लिए घटक कोड्स का कुशलतापूर्वक डिकोडेबल होना आवश्यक नहीं है, तथा यह अर्ध-रैखिक (quasilinear) डिकोडिंग समय और तेजी से घटती त्रुटि संभावनाओं को भी प्रदर्शित करता है।

मूल लेखक: Emmanuel Abbe, Colin Sandon, Oscar Sprumont

प्रकाशित 2026-01-23

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

CC BY 4.0

मूल लेखक: Emmanuel Abbe, Colin Sandon, Oscar Sprumont

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

मुख्य चित्र: टूटे हुए संदेशों को ठीक करना

कल्पना कीजिए कि आप एक बहुत ही शोर वाले रेडियो चैनल के माध्यम से एक गुप्त संदेश भेज रहे हैं। स्टेटिक (static), हस्तक्षेप और रैंडम ग्लिच (त्रुटियाँ) आपके संदेश को खराब कर रहे हैं। कंप्यूटर विज्ञान की दुनिया में, हम इन संदेशों की सुरक्षा के लिए कोड्स (codes) का उपयोग करते हैं। एक कोड इन संदेशों में अतिरिक्त "रिडंडेंट" (redundant) जानकारी जोड़ता है ताकि यदि कुछ हिस्से खराब हो जाएं, तो रिसीवर अभी भी मूल संदेश को समझ सके।

दशकों से, रीड-मुलर (Reed-Muller - RM) कोड्स नामक एक विशिष्ट प्रकार का कोड प्रसिद्ध रहा है। वे विश्वसनीयता के लिए "गोल्ड स्टैंडर्ड" की तरह हैं। हालिया शोध ने सिद्ध किया है कि ये कोड सैद्धांतिक रूप से पूर्ण हैं: वे उतना शोर झेल सकते हैं जितना भौतिक रूप से संभव है (इसे "क्षमता प्राप्त करना" या "achieving capacity" कहा जाता है)।

हालाँकि, एक बड़ी समस्या थी: हालांकि हम जानते थे कि ये कोड संदेश को ठीक कर सकते हैं, लेकिन हमारे पास वास्तव में ऐसा करने के लिए पर्याप्त तेज़ कंप्यूटर प्रोग्राम (एल्गोरिदम) नहीं था जब संदेश लंबे हों और शोर रैंडम हो। यह एक ऐसे आदर्श ताले की तरह था जिसे आप उपयोगी होने के लिए कभी भी पर्याप्त तेज़ी से खोल नहीं सकते थे।

यह पेपर टेंसर रीड-मुलर (Tensor Reed-Muller - TRM) कोड्स नामक एक नया संस्करण पेश करता है। लेखक दिखाते हैं कि इन कोड्स को बनाने के तरीके को पुनर्व्यवस्थित करके, वे इन्हें अविश्वसनीय रूप से तेज़ी से डिकोड (ठीक) कर सकते हैं, जो लगभग सैद्धांतिक सीमा जितनी ही तेज़ है।

मुख्य विचार: "टेंसर" ट्विस्ट

नए कोड को समझने के लिए, आइए पहले पुराने वाले को देखें।

पुराने RM कोड्स: कल्पना करें कि एक संदेश संख्याओं का एक विशाल ग्रिड है। पुराने कोड इस ग्रिड को डेटा की एक एकल, सपाट शीट के रूप में देखते हैं।
नए TRM कोड्स: लेखक सुझाव देते हैं कि संदेश को एक सपाट शीट के रूप में नहीं, बल्कि एक बहु-परतीय केक (multi-layered cake) या पारदर्शी शीटों के ढेर के रूप में सोचना चाहिए।

वे वेरिएबल्स (संदेश के घटक) को लेते हैं और उन्हें अलग-अलग समूहों में विभाजित करते हैं।

समूह 1: पंक्तियों (rows) को नियंत्रित करता है।
समूह 2: कॉलम (columns) को नियंत्रित करता है।
समूह 3: परतों (layers/depth) को नियंत्रित करता है।

इस संरचना को टेंसर (Tensor) कहा जाता है। यह एक 2D स्प्रेडशीट को 3D ब्लॉक में, या यहाँ तक कि 4D हाइपर-ब्लॉक में बदलने जैसा है। जादू यह है कि "वैधता" के नियम इस ब्लॉक के प्रत्येक स्लाइस (slice) पर स्वतंत्र रूप से लागू होते हैं।

डिकोडिंग कैसे काम करती है: "लेयर्ड रिपेयर" रणनीति

यह पेपर इस बहु-स्तरीय ब्लॉक में त्रुटियों को ठीक करने का एक चतुर तरीका प्रस्तावित करता है। पूरे मलबे को एक साथ ठीक करने के बजाय (जो धीमा है), वे इसे परत-दर-परत ठीक करते हैं।

उपमा: "रो-देन-कॉलम" रिपेयर क्रू (Row-Then-Column Repair Crew)
कल्पना कीजिए कि आपके पास दीवार पर बना एक विशाल, क्षतिग्रस्त भित्ति चित्र (mural) है। कुछ पेंट गायब है या गलत है।

चरण 1 (छोटा सुधार): पहले, आप केवल पंक्तियों (क्षैतिज रेखाओं) को देखते हैं। क्योंकि पंक्तियाँ छोटी और सरल हैं, आप एक "ब्रूट फोर्स" (brute force) विधि का उपयोग कर सकते हैं: आप उस छोटी रेखा के हर संभावित संस्करण की जाँच करते हैं और उसे चुनते हैं जो मूल के सबसे करीब दिखता है। यह तेज़ है क्योंकि पंक्तियाँ छोटी हैं।
चरण 2 (बड़ा सुधार): अब जब पंक्तियाँ काफी हद तक ठीक हो गई हैं, तो आप कॉलम (लंबवत रेखाओं) को देखते हैं। कॉलम लंबे हैं, लेकिन चूंकि पंक्तियाँ पहले से ही काफी हद तक सही हैं, इसलिए कॉलम में केवल कुछ ही त्रुटियां बची हैं। लेखक इन लंबी कॉलमों को तेज़ी से ठीक करने के लिए एक विशेष, उच्च-गति वाले एल्गोरिदम (पिछले काम पर आधारित) का उपयोग करते हैं।
चरण 3 (गहरा सुधार): यदि संदेश और भी जटिल है (3D या 4D), तो वे "डेप्थ" परतों के लिए इस प्रक्रिया को दोहराते हैं। वे स्लाइस को ठीक करते हैं, फिर स्लाइस के कॉलम को, फिर पूरे ब्लॉक की परतों को।

यह तेज़ क्यों है?
पेपर का दावा है कि इस प्रक्रिया में क्वासिलिनियर समय (quasilinear time) लगता है। रोज़मर्रा की भाषा में, यदि आपके संदेश का आकार दोगुना हो जाता है, तो इसे ठीक करने में लगने वाला समय केवल दोगुने से थोड़ा ही अधिक बढ़ता है (जैसे $N \times \log N$ )। यह पुराने तरीकों की तुलना में अविश्वसनीय रूप से कुशल है जो $N^2$ या $N^3$ समय ले सकते हैं।

दो मुख्य परिणाम

लेखक इन कोड्स को बनाने के दो विशिष्ट तरीके प्रस्तुत करते हैं, इस आधार पर कि आपका "ब्लॉक" कितना जटिल है:

3-लेयर केक (t=3):
- गति: अत्यंत तेज़ ( $O(n \log \log n)$ )। यह लगभग संदेश को पढ़ने जितना ही तेज़ है।
- विश्वसनीयता: संदेश को ठीक करने में विफल होने की संभावना अविश्वसनीय रूप से कम है (इतनी कम कि इसे $n$ की घात के रूप में एक बहुत बड़ी ऋणात्मक संख्या के रूप में लिखा जाता है)।
- सर्वश्रेष्ठ: जब गति सर्वोपरि हो।
मल्टी-लेयर टॉवर (t≥4):
- गति: अभी भी बहुत तेज़ ( $O(n \log n)$ ), जैसे नामों की सूची को सॉर्ट करना।
- विश्वसनीयता: और भी अधिक विश्वसनीय। विफलता की संभावना तेजी से घटती है (जैसे $2^{-n}$ )।
- सर्वश्रेष्ठ: जब आपको उच्च गति बनाए रखते हुए लगभग पूर्ण विश्वसनीयता की आवश्यकता हो।

गुप्त हथियार: "एडवर्सरियल" बनाम "रैंडम" त्रुटियाँ

पेपर का एक बड़ा हिस्सा एक नया टूल है जिसे उन्होंने डिकोडिंग में मदद करने के लिए बनाया है।

रैंडम त्रुटियाँ (Random Errors): रेडियो पर स्टेटिक की तरह; वे संयोग से होती हैं।
एडवर्सरियल त्रुटियाँ (Adversarial Errors): एक हैकर की तरह जो विशेष रूप से आपके कोड को तोड़ने के लिए सबसे खराब संभव बिट्स को बदलने की कोशिश कर रहा है।

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

सारांश

यह पेपर 70 साल पुरानी पहेली को हल करता है। यह सिद्ध करता है कि रीड-मुलर कोड्स को बहु-आयामी "टेंसर" संरचना में पुनर्गठित करके, हम:

सैद्धांतिक सीमा तक पहुँच सकते हैं कि एक चैनल कितना शोर झेल सकता है।
संदेश को लगभग तुरंत डिकोड कर सकते हैं (क्वासिलिनियर समय में)।

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

तकनीकी सारांश: टेंसर रीड-मुलर कोड्स (Tensor Reed-Muller Codes)

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

रीड-मुलर (RM) कोड, जिन्हें 1954 में पेश किया गया था, त्रुटि-सुधार करने वाले कोडों (error-correcting codes) का एक मौलिक परिवार है। हालांकि हालिया सैद्धांतिक कार्यों ने यह स्थापित किया है कि RM कोड बाइनरी इरेज़र चैनल (BEC) और सभी बाइनरी मेमलेस सिमेट्रिक (BMS) चैनलों पर क्षमता (capacity) प्राप्त करते हैं, लेकिन निरंतर-दर (constant-rate) शासन के संबंध में कुशल डिकोडिंग के लिए एक महत्वपूर्ण अंतर बना हुआ है। विशेष रूप से, वर्तमान में निरंतर-दर वाले रीड-मुलर कोड को रैंडम शोर (random noise) के तहत विश्वसनीय रूप से डिकोड करने के लिए कोई बहुपद-समय (polynomial-time) एल्गोरिदम ज्ञात नहीं है। मौजूदा कुशल डिकोडर विशिष्ट शासन तक ही सीमित हैं: या तो बहुत कम/उच्च दर, छोटे ब्लॉक-लेंथ, या विशिष्ट त्रुटि पैटर्न जहाँ शोर कोड की न्यूनतम दूरी (minimum distance) के सापेक्ष एक निश्चित थ्रेशोल्ड से नीचे होता है।

यह शोध पत्र रीड-मुलर कोड के एक संस्करण का निर्माण करने की चुनौती को संबोधित करता है जो BMS चैनलों पर क्षमता प्राप्त करता है और जिसमें क्वासिलिनियर (quasilinear) समय जटिलता वाला डिकोडिंग एल्गोरिदम शामिल है।

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

लेखक टेंसर रीड-मुलर (TRM) कोड पेश करते हैं, जो कई रीड-मुलर कोड के टेंसर उत्पाद (tensor product) के रूप में परिभाषित हैं। $\text{TRM}(r_1, m_1; \dots; r_t, m_t)$ में एक कोडवर्ड चरों के समूहों $x_{i1}, \dots, x_{im_i}$ में प्रत्येक समूह में अधिकतम डिग्री $r_i$ वाले बहुचर बहुपदों (multivariate polynomials) के मूल्यांकन वेक्टर (evaluation vector) के अनुरूप होता है। एक TRM कोड का जनरेटर मैट्रिक्स इसके घटक RM कोड के जनरेटर मैट्रिसेस का टेंसर उत्पाद होता है।

डिकोडिंग रणनीति दो अलग-अलग RM डिकोडिंग शासनों को संयोजित करने वाले एक हाइब्रिड दृष्टिकोण पर निर्भर करती है:

छोटे, लो-रेट घटकों के लिए ब्रूट-फोर्स डिकोडिंग: टेंसर के पहले कुछ आयामों को छोटे RM कोड ( $m_1, m_2$ ) से बनाया जाता है जिनका ब्लॉक-लेंथ सब-लीनियर होता है। इन्हें ब्रूट-फोर्स सर्च के माध्यम से डिकोड किया जाता है, जो तब कुशल होता है जब ब्लॉक-लेंथ छोटा हो (उदाहरण के लिए, $2^{m_1} \approx \log n$ )।
लंबे घटकों के लिए हाई-रेट एडवरसेरियल डिकोडिंग: शेष आयाम उच्च-दर वाले RM कोड का उपयोग करते हैं। लेखक [SSV17] के एक परिणाम का लाभ उठाते हैं जो उच्च-दर वाले RM कोड में रैंडम त्रुटियों के एक स्थिर अंश को सुधारने की अनुमति देता है, बशर्ते कि त्रुटि पैटर्न कोड की न्यूनतम दूरी के सापेक्ष पर्याप्त विरल (sparse) हो।

मुख्य तकनीकी नवाचार किसी भी टेंसर कोड ( $C = C_1 \otimes \dots \otimes C_t$ ) को एडवरसेरियल त्रुटियों से डिकोड करने के लिए एक सामान्य एल्गोरिदम है। यह एल्गोरिदम त्रुटियों को इरेज़र (erasures) के रूप में मानकर पुनरावृत्ति (iteratively) करता है:

यह पहले उन पंक्तियों (या सब-टेन्सरों) की पहचान करता है जो घटक कोड $C_1$ के वैध कोडवर्ड नहीं हैं और उन्हें इरेज़र प्रतीकों से बदल देता है।
फिर यह कॉलम (या अगले अक्ष) की जाँच करता है कि क्या $C_2$ में एक अद्वितीय कोडवर्ड आंशिक रूप से मिटाए गए डेटा के साथ सुसंगत (consistent) है। यदि ऐसा है, तो यह कॉलम को भर देता है; अन्यथा, यह पूरे कॉलम को मिटा देता है।
यह प्रक्रिया सभी अक्षों के लिए दोहराई जाती है।
महत्वपूर्ण रूप से, इस एल्गोरिदम के लिए यह आवश्यक नहीं है कि घटक कोड $C_i$ स्वयं कुशलता से डिकोडेबल हों; इसे केवल एक कोडवर्ड के साथ सुसंगतता परीक्षण के लिए बहुपद-समय प्रक्रिया की आवश्यकता होती है (जो गैसियन एलिमिनेशन या विशिष्ट RM डिकोडर के माध्यम से RM कोड के लिए कुशल है)।

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

टेंसर रीड-मुलर कोड: कुशल डिकोडिंग गुणों के साथ क्षमता-प्राप्त करने वाले परिवार के रूप में TRM कोड की परिभाषा और विश्लेषण।
सामान्य टेंसर कोड डिकोडर: $\frac{d_{\min}(C)}{2 \max_i d_{\min}(C_i)} - 1$ एडवरसेरियल त्रुटियों से किसी भी टेंसर कोड $C_1 \otimes \dots \otimes C_t$ को डिकोड करने वाला एक बहुपद-समय एल्गोरिदम (Theorem 2/Theorem 5)। यह RM घटकों के लिए $O(n \log n)$ समय में चलता है।
क्षमता-प्राप्त करने वाले निर्माण (Capacity-Achieving Constructions): TRM कोड के दो विशिष्ट निर्माण जो क्वासिलिनियर डिकोडिंग समय के साथ किसी भी दर $R < 1 - h(p)$ $R < 1 - h (p)$ (जहाँ $p$ $p$ शोर की संभावना है) को प्राप्त करते हैं:
- निर्माण 1 ( $t=3$ ): त्रुटि संभावना $n^{-\omega(\log n)}$ प्राप्त करता है जिसका डिकोडिंग समय $O(n \log \log n)$ है।
- निर्माण 2 ( $t \ge 4$ ): त्रुटि संभावना $2^{-n^{\frac{1}{2} - \frac{1}{2(t-2)} - o(1)}}$ प्राप्त करता है जिसका डिकोडिंग समय $O(n \log n)$ है।

परिणाम (Results)

यह शोध पत्र Theorem 1 को सिद्ध करता है, यह स्थापित करते हुए कि किसी भी शोर संभावना $p > 0$ और दर $R < 1 - h(p)$ के लिए, हम $n^{1 \pm o(1)}$ लंबाई और $R \pm o(1)$ दर वाला एक TRM कोड बना सकते हैं जो उच्च संभावना के साथ क्वासिलिनियर समय में डिकोडेबल है।

$t=3$ के लिए: डिकोडर $O(n \log \log n)$ समय में चलता है। विफलता की संभावना $n^{-\omega(\log n)}$ द्वारा सीमित है। यह एक बहुत ही छोटे पहले RM कोड (जिसे ब्रूट फोर्स द्वारा डिकोड किया जाता है) का उपयोग करके त्रुटि दर को नगण्य स्तर तक कम करके प्राप्त किया जाता है, जिसके बाद दूसरा RM कोड शेष त्रुटियों को साफ करने के लिए उपयोग किया जाता है।
$t \ge 4$ के लिए: डिकोडर $O(n \log n)$ समय में चलता है। विफलता की संभावना $2^{-n^{\frac{1}{2} - \frac{1}{2(t-2)} - o(1)}}$ द्वारा सीमित है। यह निर्माण अतिरिक्त टेंसर आयामों को जोड़ता है जो उच्च-दर वाले RM कोड का उपयोग करते हैं, जिससे त्रुटि संभावना को और अधिक कम किया जाता है। जैसे-जैसे $t$ बढ़ता है, त्रुटि घातांक (error exponent) $2^{-\Omega(\sqrt{n})}$ के करीब पहुँच जाता है, हालाँकि शोध पत्र नोट करता है कि $t \le \sqrt{\log n}$ के लिए, सुधार निचले-क्रम के पदों (lower-order terms) द्वारा समाहित हो जाता है।

विश्लेषण Chernoff bound पर निर्भर करता है ताकि यह दिखाया जा सके कि प्रारंभिक ब्रूट-फोर्स डिकोडिंग चरण त्रुटि घनत्व (error density) को पर्याप्त रूप से कम कर देता है ताकि बाद के उच्च-दर डिकोडिंग चरण (जो [SSV17] की एडवरसेरियल त्रुटि सुधार क्षमता पर निर्भर हैं) उच्च संभावना के साथ सफल हों।

महत्व (Significance)

यह शोध पत्र निरंतर-दर शासन में क्षमता-प्राप्त करने वाले रीड-मुलर जैसे कोडों के कुशल डिकोडिंग के खुले प्रश्न को हल करने का दावा करता है। जबकि मानक रीड-मुलर कोड क्षमता प्राप्त करने के लिए जाने जाते हैं, इस शासन में उनकी कुशल डिकोडिंग एक खुला प्रश्न बनी हुई है। TRM वेरिएंट को पेश करके, लेखक प्रदर्शित करते हैं कि क्षमता को क्वासिलिनियर डिकोडिंग समय ( $O(n \log n)$ या बेहतर) के साथ प्राप्त किया जा सकता है।

यह कार्य पारंपरिक संकेंद्रीकृत कोड (concatenated codes - Forney's construction) के ऊपर टेंसरिंग कोड के लाभों को उजागर करता है:

संरचनात्मक सरलता: RM कोड का टेंसर उत्पाद चरों के समूहों पर डिग्री प्रतिबंधों वाले बहु-रेखीय बहुपदों (multilinear polynomials) के रूप में एक सरल विवरण बनाए रखता है, जबकि संकेंद्रीकृत RM कोड में ऐसा सहज विवरण नहीं होता है।
वर्णमाला दक्षता (Alphabet Efficiency): संकेंद्रीकरण के विपरीत, जिसमें अक्सर बड़े वर्णमाला की आवश्यकता होती है, टेंसर उत्पाद दृष्टिकोण बाइनरी वर्णमाला के साथ स्वाभाविक रूप से काम करता है।

यह शोध पत्र सामान्य टेंसर कोड डिकोडर (Theorem 5) को एक स्वतंत्र रुचि के उपकरण के रूप में प्रस्तुत करता है, जो किसी भी टेंसर कोड को एडवरसेरियल त्रुटियों से डिकोड करने में सक्षम है, बशर्ते कि एक सुसंगतता जांच (consistency check) उपलब्ध हो।