On the equivalence between additive and linear codes

यहाँ कनात अब्दुक़ालिखोव और ड्यूई हो के शोध पत्र "On the equivalence between additive and linear codes" का विस्तृत तकनीकी सारांश दिया गया है।

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

$\mathbb{F}_{q^2}$ पर एडिटिव कोड्स (विशेष रूप से क्वाटरनरी कोड्स जहाँ $q=2$) ने न्यूनतम दूरी (minimum distance) के मामले में लीनियर कोड्स से बेहतर प्रदर्शन करने की क्षमता के कारण ध्यान आकर्षित किया है। हालाँकि, एक मौलिक अस्पष्टता मौजूद है: यह समझना अक्सर कठिन होता है कि एक नया निर्मित "स्ट्रिक्टली एडिटिव" कोड (एक ऐसा कोड जो किसी लीनियर कोड के तुल्य नहीं है) वास्तव में नया है या केवल एक अलग प्रतिनिधित्व के तहत छिपा हुआ लीनियर कोड है।

एक स्ट्रिक्टली एडिटिव कोड को लीनियर कोड से अलग करने के लिए मौजूदा विधियाँ ज्यामितीय तकनीकों (जैसे कि स्यूडो-आर्क और डेसार्गेसियन स्प्रेड्स) पर बहुत अधिक निर्भर करती हैं, जो जटिल हैं और सार्वभौमिक रूप से लागू नहीं होती हैं। लेखक इस खुले प्रश्न का समाधान करते हैं: एक एडिटिव कोड के जनरेटर मैट्रिक्स को देखते हुए, यह कैसे निर्धारित रूप से परीक्षण किया जाए कि क्या वह $\mathbb{F}_{q^2}$ पर एक लीनियर कोड के तुल्य है?

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

लेखक एक शुद्ध बीजगणितीय ढांचे (algebraic framework) को विकसित करते हैं जो कोड के जनरेटर मैट्रिक्स पर आधारित है, जिससे ज्यामितीय निर्माणों की आवश्यकता समाप्त हो जाती है।

2.1 गणितीय ढांचा (Mathematical Framework)

• प्रतिनिधित्व (Representation): $\mathbb{F}_{q^2}^n$ में एक एडिटिव कोड $C$ को $\mathbb{F}_{q^2}^n$ में $k$ आयाम वाले $\mathbb{F}_q$-लीनियर सबस्पेस के रूप में देखा जाता है। मानचित्र $\phi: \mathbb{F}_{q^2}^n \to \mathbb{F}_q^{2n}$ कोड को $\mathbb{F}_q$ पर एक लीनियर सबस्पेस में परिवर्तित करता है।
• तुल्यता की परिभाषा (Equivalence Definition): दो कोड मोनोमिअल रूप से तुल्य (monomially equivalent) होते हैं यदि एक को निर्देशांकों के क्रमपरिवर्तन (permutation) और समन्वय युग्मों पर कार्य करने वाली व्युत्क्रमणीय $2 \times 2$ मैट्रिसेस ($A_i \in GL_2(\mathbb{F}_q)$) द्वारा गुणा करके दूसरे में बदला जा सके।
• नियमित प्रतिनिधित्व (The Regular Representation): लेखक क्षेत्र $\mathbb{F}_{q^2}$ के नियमित प्रतिनिधित्व का उपयोग करते हैं। मान लीजिए $\omega$ एक प्रिमिटिव तत्व है जिसका न्यूनतम बहुपद $x^2 + c_1x + c_0$ है। $\omega$ द्वारा गुणा करना एक कॉम्पेनियन मैट्रिक्स $M_\omega$ के अनुरूप होता है।
• मुख्य शर्त (The Core Condition): एक एडिटिव कोड $C$ जिसका जनरेटर मैट्रिक्स $G$ है, एक लीनियर कोड के तुल्य है यदि और केवल यदि एक व्युत्क्रमणीय मैट्रिक्स $R \in GL_k(\mathbb{F}_q)$ और एक ब्लॉक-डायगोनल मैट्रिक्स $A = \text{diag}(A_1, \dots, A_n)$ मौजूद है ताकि:
  $$RG = G(AM_\omega A^{-1})$$
  यह समीकरण दर्शाता है कि कोड (तुल्यता के अंतर्गत) $\omega$ द्वारा स्केलर गुणन के लिए बंद (closed) है।

2.2 नियतात्मक एल्गोरिदम (The Deterministic Algorithm - Algorithm 1)

लेखक तुल्यता का परीक्षण करने के लिए तीन-चरणीय एल्गोरिदम प्रस्तावित करते हैं:

1. रैंक जाँच (Rank Check):

   • जनरेटर मैट्रिक्स $G$ को $k \times 2$ आकार के $n$ ब्लॉक कॉलम $G_i$ में विभाजित करें।
   • यदि कोई भी $G_i$ शून्य मैट्रिक्स है, तो उस निर्देशांक को पंचर (puncture) कर दें।
   • प्रमेय 3.2: यदि शेष $G_i$ में से कोई भी रैंक 1 का है, तो कोड स्ट्रिक्टली एडिटिव (लीनियर कोड के तुल्य नहीं) है। ऐसा इसलिए है क्योंकि एक 1D सबस्पेस को संरक्षित करने वाला कोई भी लीनियर ट्रांसफॉर्मेशन $\mathbb{F}_q$ में एक आइगेनवैल्यू (eigenvalue) रखता है, जबकि लीनियर कोड के लिए आवश्यक ट्रांसफॉर्मेशन $R$ का $\mathbb{F}_q$ में कोई आइगेनवैल्यू नहीं होना चाहिए।

2. नलिटी टेस्ट (Nullity Test):

   • एक बड़ा लीनियर सिस्टम $S\mathbf{x} = 0$ निर्मित करें जो शर्त $RG_i = G_i T_i$ (जहाँ $T_i$, $M_\omega$ के अनुरूप है) से प्राप्त होता है।
   • मैट्रिक्स $S$ की नलिटी (नल स्पेस का आयाम) ज्ञात करें, जिसे $d$ द्वारा दर्शाया गया है।
   • प्रमेय 3.3: यदि $d$ विषम (odd) है, तो कोड स्ट्रिक्टली एडिटिव है। इसका प्रमाण इस तथ्य पर आधारित है कि यदि कोड लीनियर होता, तो $R$ के लिए समाधान स्थान एक क्षेत्र बनाता जो $\mathbb{F}_{q^2}$ के समरूप (isomorphic) होता, जिसका अर्थ है कि आयाम को सम (even) होना चाहिए।

3. नल स्पेस खोज (Null Space Search):

   • यदि नलिटी सम है और कोई रैंक-1 ब्लॉक्स मौजूद नहीं हैं, तो एल्गोरिदम तुल्यता की स्थिति को संतुष्ट करने वाले एक वैध मैट्रिक्स $R$ के लिए $S$ के नल स्पेस की खोज करता है।

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

1. बीजगणितीय लक्षण वर्णन (Algebraic Characterization): यह शोध पत्र यह निर्धारित करने के लिए पहला नियतात्मक, बीजगणितीय परीक्षण (प्रमेय 3.1) प्रदान करता है कि क्या एक एडिटिव कोड लीनियर कोड के तुल्य है, जो केवल जनरेटर मैट्रिक्स का उपयोग करता है।
2. आवश्यक शर्तें (Necessary Conditions):
   • आइगेनवैल्यू की स्थिति (प्रमेय 3.2): यदि एक जनरेटर ब्लॉक का रैंक 1 है, तो कोड लीनियर नहीं हो सकता।
   • पैरिटी की स्थिति (प्रमेय 3.3): यदि निर्मित मैट्रिक्स $S$ की नलिटी विषम है, तो कोड लीनियर नहीं हो सकता।
3. सामान्य प्रयोज्यता (General Applicability): पिछली ज्यामितीय विधियों के विपरीत, यह दृष्टिकोण किसी भी एडिटिव कोड पर लागू होता है और मानक लीनियर अलजेब्रा उपकरणों (जिसे यहाँ MAGMA में कार्यान्वित किया गया है) का उपयोग करके गणनात्मक रूप से कुशल है।

4. परिणाम और अनुप्रयोग (Results and Applications)

लेखकों ने हालिया साहित्य में रिपोर्ट किए गए कई कोड समूहों को सत्यापित करने के लिए अपने एल्गोरिदम को लागू किया:

• [14] से क्वाटरनरी एडिटिव कोड्स:

  • उन्होंने Guan et al. [14] की तालिका II के कोड्स का परीक्षण किया।
  • परिणाम: परीक्षण किए गए सभी कोड्स (विस्तारित और संवर्धित संस्करणों सहित) में मैट्रिक्स $S$ के लिए विषम नलिटी (odd nullity) थी।
  • निष्कर्ष: ये कोड स्ट्रिक्टली एडिव हैं और किसी भी लीनियर कोड के तुल्य नहीं हैं। इसने इस अस्पष्टता को सुलझा दिया कि क्या ये उच्च-प्रदर्शन वाले कोड केवल एक अलग रूप में प्रस्तुत लीनियर कोड थे।

• एडिटिव कॉम्प्लीमेंट्री ड्यूल (ACD) कोड्स:

  • मामला 1 (स्ट्रिक्टली एडिटिव): उन्होंने [14, Table IV] और [18, Table 2] से ACD कोड्स का परीक्षण किया।
    • [18] के कोड्स (Plotkin sum construction) को स्ट्रिक्टली एडिटिव के रूप में पुष्ट किया गया।
    • [14, Table IV] के कोड्स (Lines 5, 6, 10) को नलिटी टेस्ट के माध्यम से स्ट्रिक्टली एडिटिव के रूप में पुष्ट किया गया।
  • मामला 2 (लीनियर कोड के तुल्य):
    • उन्होंने [14, Table IV, Line 1] के पैरामीटर्स $[22, 10, 9]_2^2$ वाले ACD कोड का विश्लेषण किया।
    • नलिटी टेस्ट अनिर्णायक रहा (नलिटी = 2, जो कि सम है)।
    • सिस्टम को हल करके, उन्होंने एक ट्रांसफॉर्मेशन मैट्रिक्स $A$ पाया जो सिद्ध करता है कि यह कोड $[22, 10, 9]_4$ पैरामीटर्स वाले एक लीनियर हर्मिटियन LCD कोड के तुल्य है।
    • महत्व: यह खोज लीनियर हर्मिटियन LCD कोड्स के सर्वोत्तम ज्ञात सीमाओं में सुधार करती है, यह दर्शाती है कि एक "एडिटिव" निर्माण एक बेहतर लीनियर कोड दे सकता है।

5. महत्व (Significance)

• अस्पष्टता का समाधान: यह शोध पत्र कई "नए" एडिटिव कोड्स की स्थिति को निर्णायक रूप से स्पष्ट करता है, यह पुष्टि करता है कि उनमें से कई वास्तव में स्ट्रिक्टली एडिटिव हैं और वे लीनियर कोड्स द्वारा प्राप्त न की जा सकने वाली दक्षता प्रदान करते हैं।
• नए लीनियर कोड्स की खोज: इसके विपरीत, विधि ने सफलतापूर्वक एक ऐसे एडिटिव कोड की पहचान की जो वास्तव में एक लीनियर कोड है, जिससे लीनियर हर्मिटियन LCD कोड्स के सर्वोत्तम ज्ञात पैरामीटर्स को अपडेट किया गया।
• पद्धतिगत बदलाव: ज्यामितीय परीक्षण से बीजगणितीय परीक्षण की ओर बदलाव एक स्केलेबल, नियतात्मक उपकरण प्रदान करता है, जिससे कोड सिद्धांतकार जटिल ज्यामितीय संरचनाओं पर निर्भर रहने के बजाय कोडों को वर्गीकृत कर सकते हैं।
• व्यावहारिक उपयोगिता: एल्गोरिदम को MAGMA का उपयोग करके कार्यान्वित और सत्यापित किया गया है, जिससे यह कोड रचनाकारों के लिए तुरंत उपयोगी बन जाता है।

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