A New Class of Linear Codes

तकनीकी सारांश: रैखिक कोडों का एक नया वर्ग

समस्या विवरण
यह शोध पत्र परिमित क्षेत्रों (finite fields) $\mathbb{F}_r$ पर लंबाई $n$ और सापेक्ष दूरी (relative distance) $1/2$ के समीप (विशेष रूप से $d \approx n/2$) वाले रैखिक कोडों के निर्माण को संबोधित करता है। जबकि लगभग $n/2$ की न्यूनतम दूरी वाले बाइनरी कोड मौलिक हैं, प्लॉटकिन बाउंड (Plotkin bound) $d \ge n/2$ होने पर ऐसे कोडों के आकार को अत्यंत छोटा रखने के लिए प्रतिबंधित करता है। उस शासन (regime) में जहाँ $d < n/2$ है लेकिन $n - 2d = \Omega(\sqrt{n})$ है, अब तक के सर्वोत्तम ज्ञात निर्माण गैर-रैखिक डेलसार्ट-गोएथल्स (Delsarte–Goethals) कोड रहे हैं। ये कोड प्रभावी तो हैं, लेकिन लंबाई बढ़ने के साथ इनकी दर (rate) तेजी से घटती जाती है। लेखक ऐसे रैखिक कोडों का निर्माण करने का लक्ष्य रखते हैं जो डेलसार्ट-गोएथल्स कोड के तुलनीय या बेहतर पैरामीटर प्राप्त कर सकें, विशेष रूप से $1/2$ की सापेक्ष दूरी बनाए रखते हुए कोड के आकार (दर) में घातीय सुधार (exponential improvement) लक्षित करते हैं।

कार्यप्रणाली
लेखक मल्टीप्लिकेटिव कैरेक्टर सम (multiplicative character sums) और सुपर-एलिप्टिक कर्व्स (superelliptic curves) के सिद्धांत पर आधारित एक निर्माण पेश करते हैं, जिसे शैडो कोड (Shadow Codes) कहा जाता है। मुख्य रणनीति इस प्रकार है:

1. क्षेत्र सेटअप (Field Setup): एक छोटे आधार क्षेत्र $\mathbb{F}_r$ (जहाँ $r$ एक अभाज्य संख्या है जो $q-1$ को विभाजित करती है) पर एक कोड निर्मित करने के लिए एक सहायक क्षेत्र $\mathbb{F}_q$ (जहाँ $q$ एक अभाज्य शक्ति है) का उपयोग करना।
2. सुपर-एलिप्टिक कर्व्स: $\mathbb{F}_q$ पर मोनिक अपरिवर्तनीय बहुपदों (monic irreducible polynomials) का एक संग्रह $P = \{p_1, \dots, p_L\}$ चुनना।
3. कैरेक्टर मैपिंग: एक मैपिंग को परिभाषित करना जहाँ कोडवर्ड प्रविष्टियाँ इन बहुपदों के उत्पादों पर एक मल्टीप्लिकेटिव कैरेक्टर $\chi_r$ के मूल्यांकन द्वारा निर्धारित होती हैं। विशेष रूप से, संदेश वेक्टर $(v_1, \dots, v_L) \in \mathbb{F}_r^L$ के लिए, इंडेक्स $x \in \mathbb{F}_q$ पर कोडवर्ड $\phi_r(\chi_r(\prod p_i(x)^{v_i}))$ द्वारा दिया जाता है, जहाँ $\phi_r$ रूट ऑफ यूनिटी (roots of unity) को $\mathbb{F}_r$ के एडिटिव ग्रुप में मैप करने वाला एक आइसोमोर्फिज्म (isomorphism) है।
4. ज्यामितीय व्याख्या: "शैडो" (छाया) सुपर-एलिप्टिक कर्व $y^r = f(x)$ (जहाँ $f$ बहुपदों का उत्पाद है) का x-अक्ष पर प्रोजेक्शन है। कोडवर्ड के शून्य (zeroes) उन x-निर्देशांकों के अनुरूप होते हैं जहाँ $f(x)$, $r$-पावर (r-th power) है।
5. कंकाकण (Concatenation): पैरामीटर को और अधिक सुधारने के लिए, लेखक इन शैडो कोडों को रीड-सोलोमन (Reed-Solomon - RS) कोड के साथ कंकैटिनेट करने का प्रस्ताव देते हैं।

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

• शैडो कोड का निर्माण: शोध पत्र $\mathbb{F}_r$-रैखिक कोडों के अस्तित्व को सिद्ध करता है जिनकी लंबाई $n=q$, आयाम (dimension) $k \approx q^{1/2-\epsilon}$, और न्यूनतम दूरी $d \ge \frac{r-1}{r}q - O(q^{1-\epsilon})$ है।

  • थ्योरम I.1: किसी भी $\epsilon \in (0, 1/2)$ और पर्याप्त बड़े $q$ के लिए इन कोडों के अस्तित्व को स्थापित करता है।
  • कोरोलरी I.2: बाइनरी कोड ($r=2$) के लिए विशिष्ट है, जो $[q, \lfloor q^{1/2-\epsilon} \rfloor, d]$ पैरामीटर देता है जहाँ $d \ge q/2 - 2q^{1-\epsilon}$ है।

• डेलसार्ट-गोएथल्स कोड पर घातीय सुधार:

  • लेखक यह प्रदर्शित करते हैं कि $n - 2d = \Omega(\sqrt{n})$ वाले शासन के लिए, उनके रैखिक शैडो कोड का आकार डेलसार्ट-गोएथल्स कोड की तुलना में घातीय रूप से बड़ा है।
  • प्रपोजिशन III.2: यह दिखाता है कि पैरामीटर्स के एक अनुक्रम के लिए, शैडो कोड के आकार के लघुगणक (logarithm) और डेलसकार्स-गोएथल्स कोड के लघुगणक का अनुपात $\Omega(2^{m\delta/2}/m^2)$ है, जो एक घातीय लाभ की पुष्टि करता है। डेलसार्ट-गोएथल्स कोड के विपरीत, नए कोड रैखिक हैं और उनमें एक डिकोडिंग एल्गोरिदम मौजूद है।

• कंकाकण बूस्ट (Concatenation Boosts):

  • RS-शैडो कंकैटिनेशन (थ्योरम V.1): एक रीड-सोलोमन कोड को शैडो कोड के साथ कंकैटिनेट करके, लेखक एक कोड प्राप्त करते हैं जिसकी लंबाई $N = q^{n+1}$, आयाम $N^{1 - \frac{1}{2n+2} - \frac{2\epsilon}{n+1}}$ और सापेक्ष दूरी $1/2$ के समीप है।
  • RS-RM के साथ तुलना: शोध पत्र तर्क देता है कि मानक कंकैटिनेशन में आंतरिक रीड-मुलर (RM) कोड के स्थान पर शैडो कोड का उपयोग करने से समान लंबाई और दूरी शासन के लिए काफी उच्च दर प्राप्त होती है, क्योंकि शैडो कोड प्रथम-क्रम के RM कोड की तुलना में बड़े आयामों का समर्थन करते हैं।

• शैडो कोड का वर्ग और क्रिप्टोग्राफी:

  • थ्योरम VI.1: यह सिद्ध करता है कि शैडो कोड का वर्ग (शूर उत्पाद के तहत) आयाम $L(L+1)/2$ रखता है, बशर्ते $q$, आयाम $L$ के सापेक्ष पर्याप्त रूप से बड़ा हो। यह रैंडम कोड के व्यवहार की नकल करता है।
  • महत्व: उच्च-आयामी वर्ग वाले कोड क्रिप्टोग्राफिक अनुप्रयोगों (जैसे सिग्नेचर स्कीम्स) के लिए मूल्यवान हैं क्योंकि वे कुछ बीजगणितीय हमलों का प्रतिरोध करते हैं। इसके विपरीत, शोध पत्र दिखाता है (थ्योरम VI.4) कि एक कंकैटिनेटेड RS-RM कोड का वर्ग सार्वभौमिक सीमा की तुलना में नगण्य आयाम रखता है, जिससे यह ऐसे अनुप्रयोगों के लिए कम उपयुक्त हो जाता है।

• डिकोडिंग एल्गोरिदम:

  • सेक्शन VII: शोध पत्र स्वस्तिक कोप्पार्टी (Swastik Kopparty) की विधि पर आधारित बाइनरी शैडो कोड के लिए एक कुशल डिकोडिंग एल्गोरिदम प्रस्तुत करता है। इसमें क्वाड्रेटिक कैरेक्टर के शोर युक्त मूल्यांकनों से एक स्क्वायर-फ्री मैसेज पॉलीनोमियल को रिकवर करना शामिल है, जिसमें लीनियर अलजेब्रा और पॉलीनोमियल फैक्टराइजेशन का उपयोग किया जाता है।

• संख्या सिद्धांत में अनुप्रयोग:

  • सेक्शन IV: लेखक एक्सपोनेंशियल सम (exponential sums) पर नए परिणाम प्राप्त करने के लिए कोडिंग थ्योरेटिक बाउंड्स (प्लॉटकिन और मैकलीस) को लागू करते हैं, विशेष रूप से परिमित क्षेत्रों पर कुछ कैरेक्टर सम के अधिकतम मान के लिए निचली सीमाएं स्थापित करते हैं।

महत्व और दावे
शोध पत्र यह दावा करता है कि यह सापेक्ष दूरी $1/2$ के शासन में लंबे समय से चले आ रहे डेलसार्ट-गोएथल्स गैर-रैखिक कोडों से बेहतर प्रदर्शन करने वाले एक नए वर्ग के रैखिक कोड के अस्तित्व का रचनात्मक प्रमाण प्रदान करता है। इसकी प्राथमिक महत्ता रैखिकता बनाए रखते हुए और एक स्पष्ट डिकोडिंग एल्गोरिदम प्रदान करते हुए कोड के आकार (दर) में घातीय सुधार में निहित है। इसके अलावा, शोध पत्र यह रेखांकित करता है कि इन कोडों की बीजगणितीय संरचना (विशेष रूप से उनके वर्गों का व्यवहार) उन्हें क्रिप्टोग्राफिक अनुप्रयोगों के लिए एक आशाजनक उम्मीदवार बनाती है, जो उन्हें RS-RM जैसे अन्य कंकैटिनेटेड कोड परिवारों से अलग करती है। यह कार्य कोडिंग थ्योरी और संख्या सिद्धांत को जोड़कर कैरेक्टर सम पर नए बाउंड्स प्राप्त करता है।