🔢 mathematics

Recursively Extended Permutation Codes under Chebyshev Distance

यह शोध पत्र स्थापित करता है कि चेबिशेव दूरी (Chebyshev distance) के तहत एक पुनरावर्ती रूप से विस्तारित क्रमचय कोड (recursively extended permutation code) का अधिकतम आकार $\prod_{j=0}^{n-1}(\lfloor j/d\rfloor+1)$ है, जो डायरेक्ट प्रोडक्ट ग्रुप क्रमचय कोड के आकार से मेल खाता है, साथ ही यह कुशल $O(n\log n)$ एन्कोडिंग और $O(n\log^2 n)$ बाउंडेड-डिस्टेंस डिकोडिंग एल्गोरिदम भी प्रदान करता है।

मूल लेखक: Tomoya Hirobe, Kenta Kasai

प्रकाशित 2026-09-09

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

CC BY 4.0

मूल लेखक: Tomoya Hirobe, Kenta Kasai

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

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

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

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

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

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

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

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

तकनीकी सारांश: चेबिशेव दूरी (Chebyshev distance) के अंतर्गत पुनरावर्ती रूप से विस्तारित क्रमचय कोड (Recursively Extended Permutation Codes)

समस्या विवरण
यह शोध पत्र चेबिशेव दूरी (जिसे $\ell_\infty$ दूरी भी कहा जाता है) के अंतर्गत पुनरावर्ती रूप से विस्तारित क्रमचय (REP) कोड के अधिकतम संभव आकार की जांच करता है। एक REP कोड का निर्माण मौजूदा क्रमचयों में पहले निर्देशांक (coordinate) में एक अनुमत प्रतीक (एक "हेड") को पुनरावर्ती रूप से सम्मिलित करके और वैध क्रमचय संरचना बनाए रखने के लिए शेष प्रतीकों को पुन: लेबल करके किया जाता है। केंद्रीय प्रश्न यह है कि: एक निर्धारित लंबाई $n$ और न्यूनतम दूरी $d$ के लिए, एक REP कोड में कितने कोडवर्ड समाहित हो सकते हैं?

इसका उत्तर देने में कठिनाई आकार और दूरी संरक्षण (distance preservation) के बीच के संतुलन में निहित है। एक सीधा दृष्टिकोण यह सुझाव देता है कि यदि प्रत्येक विस्तार चरण में एक ऐसा 'हेड सेट' उपयोग किया जाता है जहाँ प्रतीक कम से कम $d$ द्वारा युग्मित रूप से अलग हों, तो न्यूनतम दूरी सुरक्षित रहती है। हालांकि, यह स्थिति पर्याप्त है लेकिन आवश्यक नहीं है। एक बाद का विस्तार चरण, जिसमें केवल एक एकल (singleton) हेड होता है, पूर्ववर्ती निकटतम कोडवर्ड्स के बीच की दूरी को कोड के आकार को बढ़ाए बिना बढ़ा सकता है। फलस्वरूप, एक मध्यवर्ती चरण में दूरी की बाधा का उल्लंघन हो सकता है, बशर्ते कि भविष्य का एक 'सिंगलटन स्टेप' इसकी मरम्मत कर दे। यह "विलंबित मरम्मत" (delayed repair) तंत्र ऊपरी सीमा (upper bound) के व्युत्पन्न को जटिल बनाता है, क्योंकि आप प्रत्येक व्यक्तिगत चरण पर केवल दूरी की बाधा को लागू नहीं कर सकते।

कार्यप्रणाली
लेखक एक गणना तर्क विकसित करते हैं जो भविष्य के आकार-संरक्षण (सिंगलटन) विस्तार चरणों के संदर्भ में "दूरी की कमी" (distance shortfalls) के "लागत" (cost) को ट्रैक करता है।

अंतराल विश्लेषण (Interval Analysis): शोध पत्र दो प्रतीक मानों के बीच एक "अंतराल" $I(x, y)$ को परिभाषित करता है। एक मुख्य लेम्मा स्थापित करता है कि एक क्रमचय को हेड $s$ द्वारा विस्तारित करने से दो कोडवर्ड के बीच की दूरी ठीक 1 से बढ़ जाती है यदि और केवल यदि $s$ उनके भिन्न निर्देशांकों द्वारा परिभाषित अंतराल के भीतर स्थित हो।
अधिकतम अंतराल (Maximum Intervals): किसी भी जोड़े के कोडवर्ड के लिए, लेखक एक "अधिकतम अंतराल" की पहचान करते जिसकी लंबाई उनके बीच की चेबिशेव दूरी के बराबर होती है। वे सिद्ध करते हैं कि विलगित (disjoint) अधिकतम अंतराल आगामी विस्तारों के तहत विलगित ही रहते हैं।
लागत लेखांकन (Cost Accounting): लेखक $c_1(C; d)$ को उन भविष्य के सिंगलटन-हेड विस्तारों की न्यूनतम संख्या के रूप में परिभाषित करते जो एक मध्यवर्ती कोड $C$ को कम से कम $d$ की न्यूनतम दूरी तक लाने के लिए आवश्यक हैं। वे इस लागत को एक हेड सेट $S$ के "स्पेसिंग शॉर्टफॉल" $\delta_d(S)$ से जोड़ते हैं, जो यह मापता है कि $S$ में क्रमिक अंतराल $d$ से कितना कम है।
सिंगलटन चरणों पर निचली सीमा (Lower Bound on Singleton Steps): मुख्य सैद्धांतिक परिणाम (थ्योरम 8) सिद्ध करता है कि यदि एक हेड सेट $S$ का स्पेसिंग शॉर्टफॉल $\delta_d(S)$ है, तो न्यूनतम दूरी को $d$ तक बहाल करने के लिए कम से कम $\delta_d(S)$ आगामी सिंगलटन-हेड विस्तार आवश्यक हैं। यह एक बड़े हेड सेट से होने वाले तत्काल आकार के लाभ को भविष्य के दंड (अनिवार्य सिंगलटन चरणों) से जोड़ता है।
अनुकूलन (Optimization): एक विशिष्ट शॉर्टफॉल दिए गए हेड सेट के आकार पर ऊपरी सीमा (लेम्मा 13) को भविष्य के आवश्यक सिंगलटन चरणों (थ्योरम 8) के साथ संयोजित करके, लेखक कोड के आकार पर एक वैश्विक ऊपरी सीमा प्राप्त करते हैं।

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

सटीक अधिकतम आकार: $n > d \ge 1$ के लिए, शोध पत्र सिद्ध करता है कि न्यूनतम चेबिशेव दूरी $d$ के साथ एक REP कोड का अधिकतम आकार है:
$|C(n)| = \prod_{j=0}^{n-1} \left( \left\lfloor \frac{j}{d} \right\rfloor + 1 \right)$
यह मान डायरेक्ट प्रोडक्ट ग्रुप परम्यूटेशन (DPGP) कोड के कार्डिलिटी (cardinality) के समान है, जो एक ज्ञात निर्माण है जहाँ अवशेष वर्गों (residue classes) के modulo $d$ के भीतर प्रतीकों को क्रमचय किया जाता है।
प्राप्यता (Attainability): यह सीमा एक ऐसे REP कोड के निर्माण द्वारा प्राप्त की जा सकती है जहाँ, प्रत्येक चरण $j$ पर, हेड सेट $[0, j+1]$ की सीमा में उपलब्ध सभी $d$ के गुणकों का समूह होता है। यह निर्माण किसी भी स्पेसिंग शॉर्टफॉल को बनने से रोकता है, जिससे शून्य भविष्य के सिंगलटन चरण आवश्यक होते हैं।
संरचनात्मक भिन्नता: जबकि अधिकतम REP कोड और DPGP कोड का कार्डिलिटी समान है, शोध पत्र प्रदर्शित करता है कि वे सममित (isometric) नहीं हैं। $n=4, d=2$ के लिए, युग्मवार दूरी वितरण भिन्न होते हैं, जो इंगित करता है कि पुनरावर्ती संरचना आवश्यक रूप से प्रत्यक्ष उत्पाद निर्माण के ज्यामितीय गुणों को दोहराती नहीं है।
कुशल एल्गोरिदम (Efficient Algorithms):
- एन्कोडिंग (Encoding): पुनरावर्ती परिभाषा एक निर्देशांक-क्रम अनुक्रमिक एन्कोडर (coordinate-order sequential encoder) की अनुमति देती है। हेड्स के उलटे क्रम को मिश्रित-रैडिक्स प्रणाली (mixed-radix system) में अंकों के रूप में व्याख्या करके (लेहमर कोड के समान), लेखक $O(n \log n)$ जटिलता वाला एक एन्कोडर प्रस्तावित करते हैं।
- डिकोडिंग (Decoding): यदि प्रत्येक चरण के हेड सेट $d$ -पृथक (pairwise $d$ -separated) हैं, तो शोध पत्र एक बाउंडेड-डिस्टेंस डिकोडर प्रस्तुत करता है। यह डिकोडर संदेश को पुनः प्राप्त करता है एक ऐसे संभावित प्रतीक को चुनकर जो प्राप्त मान के निकटतम हो। यह किसी भी त्रुटि वेक्टर को सुधारने की गारंटी देता है जिसका चेबिशेव दूरी $d/2$ से कम है और $O(n \log^2 n)$ की जटिलता के साथ कार्य करता है।

महत्व
यह शोध पत्र चेबिशेव मीट्रिक के अंतर्गत REP कोड के चरम समस्या (extremal problem) को यह दिखाकर हल करता है कि पुनरावर्ती निर्माण, "विलंबित मरम्मत" की अपनी लचीलेपन के बावजूद, बीजगणितीय DPGP निर्माण के आकार से अधिक नहीं हो सकता है। इसका महत्व निम्नलिखित में है:

सैद्धांतिक सीमा: एक ज्ञात स्पष्ट निर्माण से मेल खाने वाली एक सटीक ऊपरी सीमा स्थापित करना, जो पुष्टि करता है कि पुनरावर्ती विस्तार विधि इस मीट्रिक के लिए कार्डिलिटी के मामले में इष्टतम है।
एल्गोरिदम दक्षता: इन कोडों के लिए कुशल $O(n \log n)$ एन्कोडिंग और $O(n \log^2 n)$ डिकोडिंग एल्गोरिदम प्रदान करना, जो कार्यान्वयन के लिए व्यावहारिक हैं।
पद्धतिगत अंतर्दृष्टि: पुनरावर्ती निर्माणओं में दूरी संरक्षण की गैर-स्थानीय (non-local) प्रकृति को समझने के लिए विलगित अंतरालों के माध्यम से "दूरी की कमी" को ट्रैक करने की एक नवीन तकनीक पेश करना।

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

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