2025-11-10T03:13:59.288121

Quasi perfect codes in the cartesian product of some graphs

Mane, Shinde
An important question in the study of quasi-perfect codes is whether such codes can be constructed for all possible lengths $n$. In this paper, we address this question for specific values of $n$. First, we investigate the existence of quasi-perfect codes in the Cartesian product of a graph $G$ and a path (or cycle), assuming that $G$ admits a perfect code. Second, we explore quasi-perfect codes in the Cartesian products of two or three cycles, $C_m\square C_n$ and $C_m\square C_n\square C_l$, as well as in the Cartesian products of two or three paths, $P_m\square P_n$ and $P_m\square P_n\square P_l$.
academic

कुछ ग्राफ के कार्तीय गुणनफल में अर्ध-पूर्ण कोड

मूल जानकारी

  • पेपर ID: 2510.13613
  • शीर्षक: कुछ ग्राफ के कार्तीय गुणनफल में अर्ध-पूर्ण कोड
  • लेखक: S. A. Mane, N. V. Shinde
  • वर्गीकरण: math.CO (संयोजन गणित)
  • प्रकाशन समय: 15 अक्टूबर 2025
  • पेपर लिंक: https://arxiv.org/abs/2510.13613

सारांश

अर्ध-पूर्ण कोड अनुसंधान में एक महत्वपूर्ण समस्या यह है कि क्या सभी संभावित लंबाई n के लिए ऐसे कोड का निर्माण किया जा सकता है। यह पेपर विशिष्ट n मानों के लिए इस समस्या पर विचार करता है। सबसे पहले, ग्राफ G में पूर्ण कोड के अस्तित्व की पूर्वधारणा के तहत, ग्राफ G और पथ (या चक्र) के कार्तीय गुणनफल में अर्ध-पूर्ण कोड के अस्तित्व का अध्ययन किया गया। दूसरा, दो या तीन चक्रों के कार्तीय गुणनफल Cm□CnC_m\square C_n और Cm□Cn□ClC_m\square C_n\square C_l में अर्ध-पूर्ण कोड, तथा दो या तीन पथों के कार्तीय गुणनफल Pm□PnP_m\square P_n और Pm□Pn□PlP_m\square P_n\square P_l में अर्ध-पूर्ण कोड की खोज की गई।

अनुसंधान पृष्ठभूमि और प्रेरणा

  1. समाधान की जाने वाली समस्या: यह अनुसंधान अर्ध-पूर्ण कोड निर्माण की मौजूदगी समस्या को हल करने का उद्देश्य रखता है, विशेष रूप से ग्राफ के कार्तीय गुणनफल में अर्ध-पूर्ण कोड के निर्माण की व्यवस्थित विधि।
  2. समस्या की महत्ता:
    • पूर्ण कोड त्रुटि सुधार कोड सिद्धांत में मूल भूमिका निभाते हैं, लेकिन अपेक्षाकृत दुर्लभ हैं
    • Golomb-Welch अनुमान यह दावा करता है कि लंबाई n≥3 और e>1 वाले पूर्ण Lee e त्रुटि सुधार कोड मौजूद नहीं हैं
    • अर्ध-पूर्ण कोड पूर्ण कोड के निकट विकल्प के रूप में सैद्धांतिक और व्यावहारिक मूल्य रखते हैं
  3. मौजूदा विधियों की सीमाएं:
    • अर्ध-पूर्ण कोड की मौजूदगी की शर्तें अभी भी काफी कठोर हैं
    • कवरिंग त्रिज्या 3 से अधिक वाले अर्ध-पूर्ण कोड बहुत कम ज्ञात हैं
    • व्यवस्थित निर्माण विधियों की कमी है
  4. अनुसंधान प्रेरणा: ग्राफ G में पूर्ण कोड के आधार पर, G और विशिष्ट ग्राफ के कार्तीय गुणनफल में अर्ध-पूर्ण कोड निर्माण की तकनीकें विकसित करना।

मुख्य योगदान

  1. पूर्ण कोड से अर्ध-पूर्ण कोड निर्माण की व्यवस्थित विधि प्रस्तावित की: यदि ग्राफ G पूर्ण e त्रुटि सुधार कोड को स्वीकार करता है, तो G□Pn या G□Cn में अर्ध-पूर्ण e त्रुटि सुधार कोड का निर्माण किया जा सकता है
  2. विभिन्न प्रकार के ठोस अर्ध-पूर्ण कोड का निर्माण किया:
    • Pm□Pn□P6k-2 और Cm□Cn□C6k में अर्ध-पूर्ण 2 त्रुटि सुधार कोड
    • P2□P2□P2 में पूर्ण कोड के आधार पर P4□P4□P4 में अर्ध-पूर्ण कोड
  3. ज्ञात परिणामों का विस्तार किया: Cn□Cn□Cl (3≤n≤19) में अर्ध-पूर्ण कोड का निर्माण, Cn□Cn में ज्ञात अर्ध-पूर्ण कोड का उपयोग करके
  4. संपूर्ण सैद्धांतिक ढांचा प्रदान किया: पथ और चक्र के कार्तीय गुणनफल में अर्ध-पूर्ण कोड निर्माण विधियों का व्यवस्थित विश्लेषण

विधि विवरण

कार्य परिभाषा

दिए गए ग्राफ G के लिए, इसके पथ Pn या चक्र Cn के साथ कार्तीय गुणनफल G□Pn, G□Cn में अर्ध-पूर्ण कोड का निर्माण करना। एक कोड D, t-अर्ध-पूर्ण है, यदि और केवल यदि यह t त्रुटि सुधार है और कवरिंग त्रिज्या t+1 है।

मुख्य निर्माण विधि

1. मौलिक निर्माण प्रमेय (प्रमेय 3.1)

ग्राफ G में पूर्ण e त्रुटि सुधार कोड D के लिए:

  • e=1 समय: G□P3k और G□C3k में अर्ध-पूर्ण 1 त्रुटि सुधार कोड का निर्माण किया जा सकता है
  • e≥2 समय: G□P3 और G□C3 में अर्ध-पूर्ण e त्रुटि सुधार कोड का निर्माण किया जा सकता है

निर्माण विधि:

D' = D ⊕ {1}

जहां ⊕ समुच्चय के प्रत्यक्ष गुणनफल को दर्शाता है।

2. त्रि-आयामी विस्तार निर्माण (प्रमेय 3.2)

Pm□Pn में पूर्ण 2 त्रुटि सुधार कोड D1 के लिए, Pm□Pn□P6k-2 में अर्ध-पूर्ण 2 त्रुटि सुधार कोड का निर्माण:

चरण:

  1. D2 = (0,3) + D1 परिभाषित करें (स्थानांतरित कोड)
  2. D = (D1⊕{0}) ∪ (D2⊕{3}) का निर्माण करें
  3. बड़े आयाम तक विस्तारित करें: C = ⋃(i=0 to k-1)(D1⊕{6i} ∪ D2⊕{6i+3})

3. चक्र गुणनफल निर्माण

प्रमेय 3.6: C3□C6□C4k में अर्ध-पूर्ण 1 त्रुटि सुधार कोड का निर्माण

D0 = {(0,0), (1,2), (2,4)}
D1 = {(2,1), (0,3), (1,5)}
C = ⋃(i=0 to k-1)(D0⊕{4i} ∪ D1⊕{4i+2})

तकनीकी नवाचार बिंदु

  1. स्तरीय निर्माण रणनीति: उच्च-आयामी ग्राफ को निम्न-आयामी परतों में विभाजित करना, प्रत्येक परत में ज्ञात पूर्ण कोड लागू करना
  2. स्थानांतरण तकनीक: उपयुक्त स्थानांतरण संचालन के माध्यम से विभिन्न परतों के बीच कोड शब्दों के न्यूनतम दूरी को सुनिश्चित करना
  3. आवधिक विस्तार: मौलिक निर्माण ब्लॉक के आवधिक पुनरावृत्ति का उपयोग करके मनमानी आकार का निर्माण

प्रायोगिक सेटअप

सत्यापन विधि

यह पेपर मुख्य रूप से सैद्धांतिक प्रमाण के माध्यम से निर्माण की शुद्धता को सत्यापित करता है, विशिष्ट मामलों को सत्यापित करने के लिए कंप्यूटर खोज के साथ:

  1. सैद्धांतिक सत्यापन: निर्मित कोड की न्यूनतम दूरी और कवरिंग त्रिज्या को सिद्ध करना
  2. कंप्यूटर सत्यापन: जटिल मामलों के लिए (जैसे प्रमेय 4.4 में कुछ पैरामीटर), कंप्यूटर खोज का उपयोग करके सत्यापन

मूल्यांकन संकेतक

  • न्यूनतम दूरी: किन्हीं दो कोड शब्दों के बीच की न्यूनतम दूरी
  • कवरिंग त्रिज्या: किसी भी शीर्ष से निकटतम कोड शब्द की अधिकतम दूरी
  • अर्ध-पूर्णता: कवरिंग त्रिज्या = त्रुटि सुधार क्षमता + 1 को सत्यापित करना

प्रायोगिक परिणाम

मुख्य परिणाम

  1. प्रमेय 3.1 के परिणाम:
    • e=1 समय, G□P3k और G□C3k में सफलतापूर्वक अर्ध-पूर्ण 1 त्रुटि सुधार कोड का निर्माण
    • e≥2 समय, G□P3 और G□C3 में सफलतापूर्वक अर्ध-पूर्ण e त्रुटि सुधार कोड का निर्माण
  2. त्रि-आयामी निर्माण परिणाम:
    • Pm□Pn□P6k-2 में अर्ध-पूर्ण 2 त्रुटि सुधार कोड का निर्माण (प्रमेय 3.2)
    • Cm□Cn□C6k में अर्ध-पूर्ण 2 त्रुटि सुधार कोड का निर्माण (अनुपात 3.3)
  3. ठोस उदाहरण:
    • C6□C6□C2 में पूर्ण 1 त्रुटि सुधार कोड (प्रमेय 4.2)
    • C3□C6□C4k में अर्ध-पूर्ण 1 त्रुटि सुधार कोड (प्रमेय 3.6)

निर्माण सारांश तालिका

मूल ग्राफलक्ष्य ग्राफ (कार्तीय गुणनफल)कोड गुण/विवरण
G (पूर्ण e त्रुटि सुधार कोड के साथ)G□Pn, G□Cnअर्ध-पूर्ण e त्रुटि सुधार कोड
Pm□Pn, Cm□CnPm□Pn□P6k-2, Cm□Cn□C6kअर्ध-पूर्ण 2 त्रुटि सुधार कोड
Cn□CnCn□Cn□Cl3≤n≤19 के अर्ध-पूर्ण कोड

केस विश्लेषण

पेपर कई ठोस निर्माण उदाहरण प्रदान करता है, जैसे:

  • चित्र 1 P4□P4□P4 में अर्ध-पूर्ण 1 त्रुटि सुधार कोड को दर्शाता है
  • चित्र 2-6 विभिन्न चक्र गुणनफल में अर्ध-पूर्ण कोड निर्माण को दर्शाते हैं

संबंधित कार्य

  1. पूर्ण कोड सिद्धांत: Livingston और Stout के पूर्ण नियंत्रण समुच्चय सिद्धांत पर आधारित
  2. Lee मेट्रिक के तहत कोड: Golomb-Welch अनुमान द्वारा संचालित अनुसंधान दिशा
  3. अर्ध-पूर्ण कोड निर्माण: AlBdaiwi आदि द्वारा Lee मेट्रिक के तहत निर्माण कार्य
  4. ग्राफ सिद्धांत में कोड: ग्राफ दूरी पर आधारित त्रुटि सुधार कोड सिद्धांत

निष्कर्ष और चर्चा

मुख्य निष्कर्ष

  1. पूर्ण कोड से अर्ध-पूर्ण कोड निर्माण की व्यवस्थित विधि सफलतापूर्वक स्थापित की
  2. विभिन्न ग्राफ के कार्तीय गुणनफल के लिए अर्ध-पूर्ण कोड के स्पष्ट निर्माण प्रदान किए
  3. अर्ध-पूर्ण कोड की मौजूदगी के ज्ञात परिणामों का विस्तार किया

सीमाएं

  1. निर्माण विधि मूल ग्राफ में पूर्ण कोड की मौजूदगी पर निर्भर करती है
  2. कुछ पैरामीटर श्रेणियों का निर्माण अभी भी कंप्यूटर सत्यापन की आवश्यकता है
  3. सामान्य ग्राफ के कार्तीय गुणनफल के लिए, निर्माण विधि की प्रयोज्यता सीमित है

भविष्य की दिशाएं

  1. यह निर्धारित करना कि किन पूर्णांकों n और ग्राफ G2 के लिए, G1 और n G2 प्रतियों के कार्तीय गुणनफल में अर्ध-पूर्ण कोड का निर्माण किया जा सकता है
  2. सभी पैरामीटर मानों (m,n,l) की पहचान करना जो Cm□Cn□Cl को अर्ध-पूर्ण कोड स्वीकार करने देते हैं
  3. अधिक सामान्य ग्राफ वर्गों और मेट्रिक स्पेस तक विस्तार

गहन मूल्यांकन

लाभ

  1. सैद्धांतिक कठोरता: सभी निर्माणों के पास संपूर्ण गणितीय प्रमाण हैं
  2. व्यवस्थित विधि: एकीकृत निर्माण ढांचा प्रदान करता है
  3. व्यावहारिक मूल्य: निर्माण विधि कई ठोस मामलों में लागू की जा सकती है
  4. दृश्य सहायता: समृद्ध चित्र निर्माण प्रक्रिया को समझने में सहायता करते हैं

कमियां

  1. प्रयोज्यता की सीमा: विधि मुख्य रूप से पथ और चक्र के कार्तीय गुणनफल पर लागू होती है
  2. कंप्यूटेशनल जटिलता: कुछ निर्माणों का सत्यापन बड़ी मात्रा में गणना की आवश्यकता है
  3. अनुकूलन: निर्मित कोड की इष्टतमता पर चर्चा नहीं की गई है

प्रभाव

  1. सैद्धांतिक योगदान: अर्ध-पूर्ण कोड सिद्धांत के लिए नई निर्माण तकनीकें प्रदान करता है
  2. अनुप्रयोग संभावनाएं: नेटवर्क कोडिंग और वितरित भंडारण में संभावित अनुप्रयोग
  3. विस्तारशीलता: निर्माण विधि आगे के अनुसंधान के लिए आधार प्रदान करती है

प्रयोज्य परिदृश्य

  1. नियमित नेटवर्क टोपोलॉजी में त्रुटि सुधार कोड तैनात करने की आवश्यकता वाले परिदृश्य
  2. बहु-आयामी ग्रिड और टोरस नेटवर्क में त्रुटि नियंत्रण
  3. वितरित प्रणालियों में दोष-सहिष्णु संसाधन प्लेसमेंट समस्या

संदर्भ

पेपर 33 संबंधित संदर्भों का हवाला देता है, मुख्य रूप से शामिल हैं:

  • Golomb & Welch (1970): Lee मेट्रिक पूर्ण कोड का अग्रणी कार्य
  • AlBdaiwi & Bose (2003): अर्ध-पूर्ण Lee दूरी कोड
  • Livingston & Stout (1990): पूर्ण नियंत्रण समुच्चय सिद्धांत
  • अर्ध-पूर्ण कोड निर्माण पर कई हाल के अनुसंधान

समग्र मूल्यांकन: यह संयोजन गणित और कोडिंग सिद्धांत के अंतरविषय क्षेत्र में एक उच्च गुणवत्ता वाला पेपर है, जो अर्ध-पूर्ण कोड निर्माण की व्यवस्थित विधि प्रदान करता है, सैद्धांतिक रूप से कठोर है, व्यावहारिक मूल्य अधिक है, और इस क्षेत्र के आगे विकास के लिए एक अच्छा आधार तैयार करता है।