🔢 mathematics

Deterministic list decoding of Reed-Solomon codes

यह शोधपत्र एक नियतात्मक एल्गोरिदम (deterministic algorithm) प्रस्तुत करता है जो किसी भी परिमित क्षेत्र (finite field) के लिए, क्षेत्र के अभिलक्षण (characteristic) पर निर्भरता से बचते हुए, $n$ और $\log |\mathbb{F}|$ के बहुपद समय में, $\sqrt{(k-1)n}$ के समझौते तक $k$ आयाम और $n$ ब्लॉक लंबाई वाले रीड-सोलोमन कोड्स को लिस्ट डिकोड करता है, जिससे एक कुशल नियतात्मक समाधान प्रदान करते हुए एक लंबे समय से चले आ रहे खुले प्रश्न को हल किया गया है।

मूल लेखक: Soham Chatterjee, Prahladh Harsha, Mrinal Kumar

प्रकाशित 2026-03-26

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

CC BY 4.0

मूल लेखक: Soham Chatterjee, Prahladh Harsha, Mrinal Kumar

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

कल्पना कीजिए कि आप एक शोर भरे चैनल के माध्यम से भेजे गए संदेश को पढ़ने की कोशिश कर रहे हैं, जैसे कि तूफान के दौरान रेडियो ट्रांसमिशन। यह संदेश एक विशेष गणितीय कोड का उपयोग करके एनकोड किया गया है जिसे रीड-सोलोमन कोड (Reed-Solomon code) कहा जाता है। इस कोड को एक गुप्त रेसिपी की तरह समझें जहाँ "सामग्री" (संदेश) को एक विशाल, जटिल केक (कोडवर्ड) में पकाया गया है।

जब तूफान आता है, तो केक के कुछ हिस्से टूट जाते हैं या उन पर कीचड़ लग जाता है (त्रुटियाँ)। आपका काम मूल रेसिपी का पता लगाना है।

समस्या: बहुत अधिक शोर

आमतौर पर, यदि केक थोड़ा ही क्षतिग्रस्त होता है, तो आप आसानी से मूल रेसिपी का अनुमान लगा सकते हैं। लेकिन क्या होगा यदि तूफान इतना खराब हो कि केक आधा नष्ट हो जाए?

पुराना तरीका: अतीत में, यदि क्षति गंभीर थी, तो कंप्यूटर को "अनुमान लगाने और जांचने" (guess-and-check) की विधि का उपयोग करना पड़ता था। वे केक पर यादृच्छिक रूप से एक स्थान चुनते थे, मूल रेसिपी को पुनर्गठित करने की कोशिश करते थे, और यदि वह विफल हो जाता, तो वे दूसरा स्थान चुनते थे। यह काम करता था, लेकिन यह भाग्य (यादृच्छिकता/randomness) पर निर्भर था। यदि आपको हर बार एक गारंटीकृत उत्तर चाहिए था (निश्चित/deterministic), तो कंप्यूटर अटक जाते या बहुत समय लेते, खासकर यदि "कीचड़" एक बहुत ही जटिल पदार्थ (एक बड़ा गणितीय क्षेत्र/field) से बना हो।

सफलता: एक नया जासूसी उपकरण

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

उन्होंने इसे कैसे किया, इसके लिए यहाँ कुछ सरल उपमाएँ दी गई हैं:

1. "मैजिक पॉलिनॉमियल" (केक का ब्लूप्रिंट)

इन कोडों में, संदेश को एक विशाल, बहु-स्तरीय गणितीय आकार जिसे पॉलिनॉमियल (polynomial) कहा जाता है, के अंदर छिपाया जाता है।

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

2. "न्यूटन की सीढ़ी" (ऊपर चढ़ना)

उनके समाधान का एक हिस्सा न्यूटन इटरेशन (Newton's Iteration) नामक तकनीक का उपयोग करता है।

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

3. "हेन्सेल लिफ्टिंग" (रूसी गुड़िया/Russian Doll)

सबसे कठिन मामलों के लिए (जब केक वास्तव में बहुत अधिक टूट चुका हो), उन्होंने हेन्सेल लिफ्टिंग (Hensel Lifting) नामक तकनीक का उपयोग किया।

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

यह क्यों मायने रखता है

इस शोध पत्र से पहले, यदि आप शून्य विफलता की संभावना और शून्य भाग्य पर निर्भरता के साथ एक संदेश को डिकोड करना चाहते थे, तो आपको बहुत लंबा इंतजार करना पड़ता था यदि गणितीय "क्षेत्र" (वह प्रकार का कीचड़ जिससे केक बना था) जटिल था।

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

निश्चित (Deterministic): यह हर बार एक ही तरह से काम करता है। कोई सिक्का उछालना या भाग्यशाली अनुमान नहीं।
तेज़ (Fast): यह एक ऐसे समय में चलता है जो डेटा की विशाल मात्रा के लिए भी व्यावहारिक है।
सार्वभौमिक (Universal): यह किसी भी प्रकार के परिमित क्षेत्र (finite field) के लिए काम करता है, यहाँ तक कि सबसे जटिल क्षेत्रों के लिए भी।

बड़ी तस्वीर

इसे एक टिमटिमाती फ्लैशलाइट से लेजर पॉइंटर में अपग्रेड करने के रूप में देखें जो कभी चूकता नहीं है।

पुराना तरीका: "मुझे उम्मीद है कि मैं संदेश खोजने के लिए सही जगह पर रोशनी डाल पाऊंगा।"
नया तरीका: "मैं जानता हूँ कि क्षति के आधार पर संदेश कहाँ छिपा है, इसलिए मैं सीधे वहां तक जाऊंगा।"

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

यहाँ सोहम चटर्जी, प्रहलाद हर्ष और मृणाल कुमार के शोध पत्र "Deterministic list decoding of Reed-Solomon codes" का विस्तृत तकनीकी सारांश दिया गया है।

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

यह शोध पत्र परिमित क्षेत्रों (finite fields) पर रीड-सोलोमन (RS) कोड्स के लिए डिटरमिनिस्टिक लिस्ट डिकोडिंग (deterministic list decoding) की समस्या को संबोधित करता है।

संदर्भ: RS कोड्स एरर-करेक्टिंग कोड्स का एक मौलिक परिवार हैं। लिस्ट डिकोडिंग समस्या प्राप्त किए गए शब्द (received word) से एक निश्चित हैमिंग दूरी (agreement) के भीतर सभी कोडवर्ड्स को आउटपुट करने के बारे में पूछती है, भले ही त्रुटियों (errors) की संख्या यूनिक डिकोडिंग रेडियस से अधिक हो।
बाधा (The Barrier): इस कार्य से पूर्व, कुशल लिस्ट डिकोडिंग एल्गोरिदम (विशेष रूप से सूडान एल्गोरिदम और गुरुस्वामी-सूडन एल्गोरिदम) परिमित क्षेत्रों पर रैंडमाइज्ड (randomized) बहुपद गुणनखंड (polynomial factorization) चरणों पर निर्भर थे। जबकि विशिष्ट मामलों (जैसे छोटे विशेषता वाले क्षेत्रों या GRH जैसी अप्रमाणित परिकल्पनाओं के तहत) के लिए डिटरमिनिस्टिक बहुपद गुणनखंड उपलब्ध है, सामान्य परिमित क्षेत्रों के लिए $\text{poly}(n, \log |F|)$ समय में चलने वाला कोई अनकंडीशनल डिटरमिनिस्टिक एल्गोरिदम ज्ञात नहीं था।
लक्ष्य: लेखक एक ऐसा डिटरमिनिस्टिक एल्गोरिदम बनाने का लक्ष्य रखते हैं जो $\sqrt{(k-1)n}$ (जॉनसन रेडियस) के एग्रीमेंट से $k$ आयाम और $n$ ब्लॉक लंबाई वाले RS कोड्स को $\text{poly}(n, \log |F|)$ समय में लिस्ट डिकोड कर सके, जिससे क्षेत्र की विशेषता (characteristic) या रैंडमाइजेशन पर निर्भरता समाप्त हो जाए।

2. कार्यप्रणाली और तकनीकी दृष्टिकोण (Methodology and Technical Approach)

सूडान और गुरुस्वामी-सूडन एल्गोरिदम को डिटरमाइनाइज (derandomize) करने में मुख्य चुनौती फैक्टरइजेशन स्टेप (factorization step) है। ये एल्गोरिदम एक द्विविचर बहुपद (bivariate polynomial) $Q(X, Y)$ का निर्माण करते हैं जो उच्च बहुलता (multiplicity) के साथ प्राप्त बिंदुओं पर शून्य होता है। डिकोडर को $(Y - f(X))$ के रूप में सभी कारकों को खोजना होता है। मानक गुणनखंड प्रक्रिया रैंडमाइज्ड होती है।

लेखक इस संरचनात्मक लाभ का उपयोग करके इस बाधा को दूर करते हैं जो लिस्ट-डिकोडिंग सेटिंग में निहित है:

मूल्यांकन बिंदुओं का ज्ञान (Knowledge of Evaluation Points): एल्गोरिदम को उन विशिष्ट बिंदुओं $(\alpha_j, \beta_j)$ का ज्ञान होता है जहाँ प्राप्त शब्द (received word) परिभाषित है।
बहुलता की जानकारी (Multiplicity Information): बहुपद $Q$ को इन बिंदुओं पर विशिष्ट बहुलता के साथ शून्य होने के लिए निर्मित किया जाता है।

कार्यप्रणाली मुख्य दो एल्गोरिदम के लिए थोड़ी भिन्न है:

A. सूडान डिकोडर का डिटरमाइजेशन (Agreement $\approx \sqrt{2(k-1)n}$ )

दृष्टिकोण: न्यूटन इटरेशन (Newton's Iteration) का उपयोग करता है।
तंत्र (Mechanism):
- एक मूल (root) $f(X)$ को पुनः प्राप्त करने के लिए, आमतौर पर एक बिंदु $(\alpha, \beta)$ की आवश्यकता होती है जहाँ $Q(\alpha, \beta)=0$ और आंशिक अवकलज (partial derivative) $\frac{\partial Q}{\partial Y}(\alpha, \beta) \neq 0$ हो।
- मानक सेटिंग में, ऐसा बिंदु खोजने के लिए रैंडम सैंपलिंग और रैंडमाइज्ड फैक्टराइजेशन की आवश्यकता होती है।
- डिटरमिनिस्टिक ट्रिक: एल्गोरिदम सभी $n$ $n$ प्राप्त बिंदुओं $(\alpha_j, \beta_j)$ $(α_{j}, β_{j})$ के माध्यम से पुनरावृत्ति (iterate) करता है।
  - यदि किसी $j$ के लिए $\frac{\partial Q}{\partial Y}(\alpha_j, \beta_j) \neq 0$ है, तो रूट को लिफ्ट करने के लिए न्यूटन इटरेशन को डिटरमिनिस्टिक रूप से लागू किया जाता है।
  - यदि सभी एग्रीमेंट बिंदुओं के लिए $\frac{\partial Q}{\partial Y}(\alpha_j, \beta_j) = 0$ है, तो लेखक दिखाते हैं कि $f(X)$ को डेरिवेटिव बहुपद $\frac{\partial Q}{\partial Y}(X, Y)$ का एक मूल होना चाहिए।
- एल्गोरिदम डेरिवेटिव बहुपद (जिसका $Y$ -डिग्री कम है) पर इस तर्क को पुनरावर्ती रूप से लागू करता है जब तक कि एक गैर-शून्य डेरिवेटिव न मिल जाए या डिग्री 1 तक न गिर जाए।

B. गुरुस्वामी-सूडन डिकोडर का डिटरमाइजेशन (Agreement $\approx \sqrt{(k-1)n}$ )

चुनौती: सूडान का डेरिवेटिव पुनरावृत्ति यहाँ विफल हो जाता है क्योंकि इंटरपोलेशन मल्टीप्लिसिटी $m$ बहुत अधिक ( $m = \text{poly}(n)$ ) है। इसके परिणामस्वरूप, पहले $m-1$ डेरिवेटिव सभी एग्रीमेंट बिंदुओं पर शून्य होते हैं, जिससे सरल डेरिवेटिव पुनरावृत्ति अक्षम हो जाती है (क्योंकि आवश्यक एग्रीमेंट के सापेक्ष बहुपद की डिग्री पर्याप्त तेजी से कम नहीं होती है)।
दृष्टिकोण: हेन्सलिफ्टिंग (Hensel Lifting) को लोकल स्प्लिटिंग (Local Splitting) के साथ उपयोग करता है।
तंत्र (Mechanism):
1. लोकल स्प्लिटिंग: प्रत्येक प्राप्त बिंदु $(\alpha_j, \beta_j)$ के लिए, एल्गोरिदम डिटरमिनिस्टिक रूप से एकचर बहुपद (univariate polynomial) $Q(\alpha_j, Y)$ को सह-अभाज्य भागों (coprime parts) में विभाजित करता है: $(Y - \beta_j)^{m_j}$ और एक शेष भाग $\tilde{P}_j(Y)$ जहाँ $\tilde{P}_j(\beta_j) \neq 0$ है। यह बार-बार विभाजन (repeated division) के माध्यम से किया जाता है, जिससे रैंडमाइज्ड फैक्टराइजेशन बीज (seeds) की आवश्यकता नहीं रहती।
2. हेन्सलिफ्टिंग: यह स्थानीय गुणनखंड एक "सीड" के रूप में कार्य करता है। एल्गोरिदम इस गुणनखंड को $(X-\alpha_j)$ के मॉड्युलो से उच्च घातों तक लिफ्ट करता है, जो प्रभावी रूप से द्विविचर बहुपद $Q(X, Y)$ को घटकों $P_A$ (जिसमें कारक $Y-f(X)$ शामिल है) और $P_B$ (जिसमें अन्य कारक शामिल हैं) में विभाजित करता है।
3. रिफाइनमेंट लूप: एल्गोरिदम एक बहुपदों का सेट $S$ बनाए रखता है। यह प्रत्येक बहुपद को प्रत्येक प्राप्त बिंदु के विरुद्ध हर प्राप्त बिंदु के विरुद्ध Split प्रक्रिया को पुनरावृत्ति से लागू करता है।
4. स्थिरता (Stability): प्रक्रिया तब तक जारी रहती है जब तक कि सेट $S$ "स्थिर" (stable) नहीं हो जाता (अर्थात, $S$ के प्रत्येक बहुपद और प्रत्येक बिंदु के लिए, बहुपद या तो पूरी तरह से "एग्रीमेंट" घटक में है या "नॉन-एग्रीमेंट" घटक में है)।
5. एक्सट्रैक्शन: एक बार स्थिर होने के बाद, एल्गोरिदम उन बहुपदों की पहचान करता है जो बिंदुओं के एक बड़े सेट पर शून्य होते हैं और संदेश बहुपदों $f(X)$ को रिकवर करने के लिए इंटरपोलेशन करता है।

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

प्रथम डिटरमिनिस्टिक पॉली-टाइम लिस्ट डिकोडिंग: यह शोध पत्र किसी भी परिमित क्षेत्र $F$ के लिए $\text{poly}(n, \log |F|)$ रनिंग टाइम के साथ, जॉनसन रेडियस तक RS कोड्स के लिए पहला डिटरमिनिस्टिक एल्गोरिदम प्रदान करता है। यह एक लंबे समय से चले आ रहे खुले प्रश्न को हल करता है जहाँ पिछले डिटरमिनिस्टिक समाधान या तो क्षेत्र की विशेषता में घातीय (exponential) थे या अप्रमाणित परिकल्पनाओं (जैसे GRH) पर आधारित थे।
स्ट्रक्चर्ड सेटिंग्स में डिटरमिनिस्टिक द्विविचर गुणनखंड: लेखक प्रदर्शित करते हैं कि जबकि सामान्य डिटरमिनिस्टिक द्विविचर गुणनखंड एक खुला प्रश्न है, कोडिंग थ्योरी में आने वाले विशिष्ट उदाहरणों (जहाँ कारक $Y$ में रैखिक हैं और मूल्यांकन बिंदु ज्ञात हैं) को डिटरमिनिस्टिक रूप से हल किया जा सकता है।
नया स्प्लिटिंग एल्गोरिदम: वे हेन्सलिफ्टिंग पर आधारित एक नवीन डिटरमिनिस्टिक Split एल्गोरिदम पेश करते हैं जो रैंडमाइज्ड यूनिवेरिएट फैक्टराइजेशन सीड्स की आवश्यकता को बायपास करने के लिए प्राप्त शब्द की संरचना का उपयोग करता है।
सूडान एल्गोरिदम का डिटरमाइजेशन: वे सूडान एल्गोरिदम के डिटरमाइजेशन के लिए एक स्पष्ट, रचनात्मक प्रमाण प्रदान करते हैं (यह नोट करते हुए कि ऑगुट और पेक्क्वेट [AP00] द्वारा एक समान परिणाम मौजूद था लेकिन वह केवल सूडान एल्गोरिदम तक सीमित था और गुरुस्वामी-सूडन तक विस्तारित नहीं हुआ था)।

4. परिणाम (Results)

थ्योरम 1.1: एक डिटरमिनिस्टिक एल्गोरिदम मौजूद है जो, किसी भी परिमित क्षेत्र $F$ और मापदंडों $n > k$ के लिए, $\text{poly}(n, \log |F|)$ समय में चलता है और $\sqrt{(k-1)n}$ से अधिक एग्रीमेंट से ब्लॉक लंबाई $n$ और आयाम $k$ वाले RS कोड्स को लिस्ट डिकोड करता है।
थ्योरम 1.2: सूडान डिकोडर (एग्रीमेंट $\sqrt{2(k-1)n)}$ के लिए एक डिटरमिनिस्टिक एल्गोरिदम उसी समय जटिलता के साथ मौजूद है।
जटिलता (Complexity): समय जटिलता ब्लॉक लंबाई $n$ और क्षेत्र के आकार $|F|$ के लघुगणक (logarithm) के बहुपद में है, जो इसे बहुत बड़े क्षेत्रों (जैसे कि प्राइम फील्ड जहाँ $p \gg n$ ) के लिए भी कुशल बनाती है।

5. महत्व (Significance)

कंप्यूटेशनल कॉम्प्लेक्सिटी: यह कार्य कॉम्प्लेक्सिटी थ्योरी में "डिटरमाइजेशन प्रोग्राम" में एक महत्वपूर्ण योगदान है। यह दिखाता है कि बिना किसी अप्रमाणित धारणाओं (जैसे GRH) पर भरोसा किए, किसी मौलिक बीजगणितीय कोडिंग समस्या से रैंडमनेस को हटाया जा सकता है।
व्यावहारिक निहितार्थ: हालांकि RS कोड्स का व्यापक रूप से उपयोग किया जाता है, रैंडमाइज्ड फैक्टराइजेशन पर निर्भरता के कारण सैद्धांतिक सीमाओं में डिटरमिनिस्टिक गारंटी की कमी थी। यह परिणाम सुनिश्चित करता है कि लिस्ट डिकोडिंग को सभी व्यावहारिक और सैद्धांतिक सेटिंग्स में डिटरमिनिस्टिक रूप से किया जा सकता है।
बीजगणिक अंतर्दृष्टि (Algebraic Insight): यह शोध पत्र रेखांकित करता है कि सामान्य बहुपद गुणनखंड की "कठिनाई" कोडिंग थ्योरी में पाए जाने वाले विशिष्ट, संरचित उदाहरणों पर लागू नहीं होती है। प्राप्त शब्द (received word) द्वारा प्रदान किए गए "नॉइजी" (noisy) मूल्यांकन डेटा का लाभ उठाकर, एल्गोरिदम सामान्य गुणनखंड बाधा को दरकिनार कर देता है।

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