🔢 mathematics

Efficient Decoding of Twisted GRS Codes and Roth-Lempel Codes

यह शोध पत्र गुरस्वामी-सुदान एल्गोरिदम पर आधारित ट्विस्टेड जीआरएस (GRS) और रोथ-लेम्पेल (Roth-Lempel) कोड के लिए कुशल, निकट-रैखिक समय वाले लिस्ट और यूनिक डिकोडिंग एल्गोरिदम प्रस्तुत करता है, जो पिछले द्विघातीय-समय (quadratic-time) विधियों में महत्वपूर्ण सुधार करता है, कई ट्विस्ट वाले कोड्स के लिए समर्थन का विस्तार करता है, और मजबूत संदेश रिकवरी के लिए बीजगणितीय हेरफेर पहचान (algebraic manipulation detection) को एकीकृत करता है।

मूल लेखक: Runtian Zhu, Lingfei Jin

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

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

CC BY 4.0

मूल लेखक: Runtian Zhu, Lingfei Jin

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

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

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

इस समस्या को हल करने के लिए, वैज्ञानिकों ने इनके "ट्विस्टेड" (घुमावदार) संस्करण और अन्य विचित्र प्रकार के कोड बनाए जो दिखने में समान हैं लेकिन उनकी संरचना छिपी हुई और अनियमित है। ये क्रैक करने में कठिन हैं, लेकिन इन्हें ठीक करना भी कठिन है। अब तक, इन ट्विस्टेड कोड्स को ठीक करना एक टूटी हुई घड़ी को हथौड़े से ठीक करने जैसा था: यह काम तो करता था, लेकिन यह धीमा, भद्दा और केवल छोटे ब्रेक को संभालने में सक्षम था।

यह शोध पत्र इन जटिल कोड्स के लिए अति-तेज़, सटीक मरम्मत उपकरण पेश करता है। ये कैसे काम करते हैं, इसके लिए सरल उपमाओं का उपयोग यहाँ दिया गया है:

1. "ट्विस्टेड" कोड्स (TGRS)

एक मानक कोड को मोतियों की एक सीधी रेखा के रूप में सोचें। एक ट्विस्टेड जनरलाइज्ड रीड-सोलोमन (TGRS) कोड उसी मोतियों की रेखा की तरह है, लेकिन किसी ने गुप्त रूप से उनके कुछ मोतियों को अजीब गांठों (जिन्हें "ट्विस्ट" कहा जाता है) में एक साथ बांध दिया है। ये गांठें कोड को अनुमान लगाने में कठिन बनाती हैं, लेकिन ये भी कठिन बना देती हैं कि यदि रेखा बिखर जाए तो कौन से मोती कहाँ के हैं।

पुराना तरीका: पिछले मरम्मत के तरीके केवल उन कोड्स को संभाल सकते थे जिनमें एक गांठ होती थी। यदि आपके पास कई गांठों वाला कोड होता, तो मरम्मत उपकरण भ्रमित हो जाता और उसे बहुत अधिक समय लगता (क्वाड्रेटिक समय, या $O(n^2)$ )।
नया तरीका: लेखकों ने महसूस किया कि गांठों के बावजूद, ट्विस्टेड कोड अभी भी एक बड़े, सरल "पैरेंट" कोड (मोतियों की एक सीधी रेखा) के भीतर छिपा हुआ है।
- उपमा: कल्पना करें कि आप मोतियों के ढेर में से एक विशिष्ट, गांठदार हार की तलाश कर रहे हैं। ढेर के हर एक हार को सुलझाने की कोशिश करने के बजाय, आप एक सुपर-फास्ट स्कैनर (गुरुस्वामी-सुडन एल्गोरिदम) का उपयोग करते हैं जो उन सभी हारों को ढूंढ निकालता है जो लगभग आपके वांछित हार जैसे दिखते हैं।
- फ़िल्टर: एक बार जब स्कैनर आपको उम्मीदवारों की एक छोटी सूची दे देता है, तो आप बस "गांठों" की जाँच करते हैं। यदि गांठें गुप्त पैटर्न से मेल खाती हैं, तो आप उसे रखते हैं; यदि नहीं, तो आप उसे फेंक देते हैं।
- परिणाम: यह तरीका अविश्वसनीय रूप से तेज़ है (लगभग रैखिक समय/near-linear time)। यह हजारों गांठों वाले कोड्स को संभाल सकता है (up to $O(n^2)$ ), जबकि पहले यह केवल एक ही संभाल सकता था। यह एक मैनुअल स्क्रूड्राइवर से लेजर-गाइडेड ड्रिल में अपग्रेड करने जैसा है।

2. "रोथ-लेम्पेल" (Roth–Lempel) कोड्स

ये एक अन्य प्रकार के विचित्र कोड हैं, जो वास्तव में मानक कोड्स से अलग होने के रूप में सिद्ध हुए पहले कोड हैं।

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

3. केवल "छोटे" ब्रेक से अधिक को ठीक करना

आमतौरता पर, यदि कोई कोड बहुत अधिक क्षतिग्रस्त हो जाता है (आधे से अधिक मोती गलत हो जाते हैं), तो आप निश्चित नहीं हो सकते कि मूल संदेश क्या था। आपको संभावित संदेशों की एक सूची मिल सकती है (जैसे, "यह संदेश A या संदेश B है")।

"लिस्ट" डिकोडर: नए उपकरण कोड को तब भी ठीक कर सकते हैं जब क्षति गंभीर हो, लेकिन वे आपको उम्मीदवारों की एक छोटी सूची दे सकते हैं (जैसे, "यह संदेश A या संदेश B है")।
"AMD" सुरक्षा जाल: इस सूची वाली समस्या को हल करने के लिए, लेखकों ने संदेश भेजने से पहले उसमें एक विशेष "सुरक्षा टैग" (एल्जेब्रिक मैनिपुलेशन डिटेक्शन) जोड़ा।
- उपमा: कल्पना करें कि आप एक पैकेज भेजते हैं जिस पर एक अद्वितीय, अटूट मोहर (wax seal) लगी है। यदि पैकेज रास्ते में क्षतिग्रस्त हो जाता है, तो आपको संभावित सामग्री की एक सूची मिल सकती है। लेकिन आप प्रत्येक संभावना पर मोहर की जाँच करते हैं। केवल असली संदेश में ही सही मोहर होगी। नकली वाले (गलत उम्मीदवार) या तो टूटी हुई या गायब मोहर वाले होंगे।
- परिणाम: यह सिस्टम को अत्यधिक उच्च विश्वास के साथ सूची में से एक सही संदेश चुनने की अनुमति देता है, भले ही क्षति पहले की तुलना में बहुत अधिक हो।

सुधारों का सारांश

गति: नए उपकरण बहुत तेज़ हैं। वे "धीमे और भद्दे" से "लगभग तत्काल" में बदल गए हैं, विशेष रूप से लंबे संदेशों के लिए।
क्षमता: वे पहले की तुलना में बहुत अधिक "ट्विस्ट" (जटिलताओं) को संभाल सकते हैं।
प्रथम (Firsts): वे रोथ-लेम्पेल कोड्स को ठीक करने का पहला कुशल तरीका प्रदान करते हैं।
विश्वसनीयता: इन तेज़ उपकरणों को "मोहर" (AMD) वाली तरकीब के साथ जोड़कर, वे अत्यधिक शोर के बावजूद सही संदेश को पुनः प्राप्त कर सकते हैं, जो पुराने सीमित स्तरों को पार कर जाता है।

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

तकनीकी सारांश: ट्विस्टेड GRS कोड और रोथ-लेम्पल कोड का कुशल डिकोडिंग

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

इन गैर-GRS कोडों के निर्माण और संरचनात्मक गुणों में व्यापक शोध के बावजूद, उनके डिकोडिंग एल्गोरिदम पीछे रह गए हैं। TGRS कोडों के लिए मौजूदा डिकोडिंग तरीके मुख्य रूप से सिंगल-ट्विस्ट मामलों तक सीमित हैं और उनकी समय जटिलता (time complexity) द्विघाती ( $O(n^2)$ ) है, और रोथ-लेम्पल कोडों के लिए कोई कुशल डिकोडिंग एल्गोरिदम रिपोर्ट नहीं किया गया है। इसके अतिरिक्त, वर्तमान दृष्टिकोण शास्त्रीय त्रिज्या (classical radius) $\lfloor(n-k)/2\rfloor$ के भीतर अद्वितीय डिकोडिंग तक ही सीमित हैं, जिससे इस त्रिज्या से परे लिस्ट डिकोडिंग की क्षमता को काफी हद तक अनछुआ छोड़ दिया गया है।

कार्यप्रणाली
लेखक गुरस्वामी-सुदन (GS) लिस्ट डिकोडिंग एल्गोरिदम पर आधारित TGRS और रोथ-लेम्पल कोड के डिकोडिंग के लिए एक एकीकृत ढांचा प्रस्तावित करते हैं। मुख्य रणनीति इन गैर-GRS कोड और मानक GRS कोड के बीच संरचनात्मक संबंध का लाभ उठाना है:

ट्विस्टेड GRS (TGRS) कोड: लेखक यह देखते हैं कि कोई भी TGRS कोड जिसकी छद्म-विमा (pseudo-dimension) $k'$ है, वह लंबाई $n$ और विमा $k'$ वाले एक GRS कोड का उप-कोड (subcode) है। वे एक दो-चरणीय डिकोडिंग प्रक्रिया प्रस्तावित करते हैं:
- लिस्ट जनरेशन: उम्मीदवार बहुपदों (candidate polynomials) की एक सूची उत्पन्न करने के लिएcontaining GRS कोड $C_{GRS}(\alpha, v, k')$ पर निकट-रैखिक समय (near-linear time) वाला गुरस्वामी-सुदन एल्गोरिदम लागू करें।
- फिल्टरिंग: यह जांचने के लिए कि क्या उम्मीदवार बहुपद विशिष्ट "ट्विस्ट" बाधाओं को पूरा करते हैं (अर्थात, क्या वे ट्विस्टेड बहुपद स्थान $P_{TGRS}(k, T)$ के सदस्य हैं), इस सूची को फ़िल्टर करें। यह फ़िल्टरिंग चरण कुशल है, जिसमें केवल गुणांक तुलना (coefficient comparisons) की आवश्यकता होती है।
रोथ-लेम्पल कोड: लेखक इस अवलोकन का उपयोग करते हैं कि एक रोथ-लेम्पल कोड को उसके अंतिम निर्देशांक (coordinate) पर पंचर (puncture) करने से एक मानक GRS कोड प्राप्त होता है। डिकोडिंग प्रक्रिया में शामिल है:
- पंचरिंग: प्राप्त शब्द (received word) के अंतिम निर्देशांक को हटा दें।
- लिस्ट जनरेशन: पंचर्ड GRS कोड पर गुरस्वामी-सुदन एल्गोरिदम लागू करें।
- पुनः एन्कोडिंग और सत्यापन: प्रत्येक उम्मीदवार बहुपद को पूर्ण रोथ-लेम्पल कोडवर्ड में पुनः एन्कोड करें और केवल उन उम्मीदवारों को रखें जिनका हैमिंग दूरी मूल प्राप्त शब्द से निर्धारित डिकोडिंग त्रिज्या के भीतर है।
AMD-सहायता प्राप्त डिकोडिंग: जब सूची का आकार एक से अधिक हो जाए (अर्थात, अद्वितीय-डिकोडिंग त्रिज्या से परे), तो अस्पष्टता को हल करने के लिए, लेखक बीजगणिक हेरफेर पहचान (Algebraic Manipulation Detection - AMD) कोड को एकीकृत करते हैं। संदेशों को TGRS या रोथ-लेम्पल एन्कोडिंग से पहले एक व्यवस्थित AMD टैग के साथ पूर्व-एन्कोड किया जाता है। डिकोडिंग के दौरान, आउटपुट सूची में मौजूद उम्मीदवारों को AMD टैग के विरुद्ध सत्यापित किया जाता है, जिससे उच्च संभावना के साथ सही संदेश की पहचान की जा सके।

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

निकट-रैखिक समय डिकोडिंग: यह शोध पत्र रोथ-लेम्पल कोडों के लिए पहला स्पष्ट डिकोडिंग एल्गोरिदम प्रस्तुत करता है और मौजूदा TGRS डिकोडर्स में महत्वपूर्ण सुधार करता है। उपयुक्त पैरामीटर स्थितियों (विशेष रूप से स्थिर-दर कोडों के लिए) के तहत, दोनों लिस्ट और अद्वितीय डिकोडिंग एल्गोरिदम $O(n \log^2 n \log \log n)$ का रनिंग टाइम प्राप्त करते हैं, जो पहले से ज्ञात सर्वोत्तम $O(n^2)$ जटिलता से बेहतर है।
TGRS के लिए विस्तारित ट्विस्ट क्षमता: प्रस्तावित TGRS डिकोडर $O(n \log^2 n \log \log n)$ तक के ट्विस्ट $\ell$ की संख्या को सहारा देता है (और विशिष्ट बाधाओं के तहत स्थिर-दर कोडों के लिए $O(n^2)$ तक), जो पिछले कार्य की तुलना में एक बड़ा सुधार है जो सिंगल-ट्विस्ट मामले ( $\ell=1$ ) तक सीमित था।
अद्वितीय-डिकोडिंग त्रिज्या से परे: एल्गोरिदम लिस्ट डिकोडर के रूप में कार्य करते हैं जो शास्त्रीय अद्वितीय-डिकोडिंग त्रिज्या $\lfloor(-k)/2\rfloor$ $⌊(- k) /2 ⌋$ से परे त्रुटियों को ठीक कर सकते हैं।
- TGRS कोड के लिए, लिस्ट डिकोडिंग त्रिज्या $\tau < n - \sqrt{n(k'-1)}$ है, जहाँ $k'$ छद्म-विमा है।
- रोथ-लेम्पल कोड के लिए, त्रिज्या $\tau < (n-1) - \sqrt{(n-1)(k-1)}$ है।
अद्वितीय डिकोडिंग स्थितियाँ: लेखक ऐसी स्थितियाँ व्युत्पन्न करते हैं जिनके तहत लिस्ट डिकोडर एक अद्वितीय समाधान प्रदान करता है, जिससे MDS TGRS और रोथ-लेम्पल कोड के लिए कुशल अद्वितीय डिकोडर प्राप्त होते हैं। TGRS के लिए, अद्वितीय डिकोडिंग तब सुनिश्चित होती है जब $k' < \frac{(n+k)^2}{4n} + 1$ हो।
AMD एकीकरण: यह शोध पत्र AMD-सहायता प्राप्त ढांचे के लिए अतिरेक (redundancy) और त्रुटि संभावना के बीच एक स्पष्ट ट्रेड-ऑफ प्रदान करता है। कुछ संख्या में अतिरेक प्रतीकों (जैसे, चार प्रतीक) को जोड़ने से, सूची से अद्वितीय प्रेषित संदेश को पहचानने में विफल होने की संभावना को $O(1/q)$ तक कम किया जा सकता है।

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

1. "ट्विस्टेड" कोड्स (TGRS)

2. "रोथ-लेम्पेल" (Roth–Lempel) कोड्स

3. केवल "छोटे" ब्रेक से अधिक को ठीक करना

सुधारों का सारांश

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