Constructing linear codes from digraphs and groups

कल्पना कीजिए कि आप एक शोर भरे कमरे में एक गुप्त संदेश भेजने की कोशिश कर रहे हैं। यदि आप केवल शब्दों को फुसफुसाते हैं, तो स्टेटिक (static) उन्हें बिगाड़ सकता है। लेकिन यदि आप एक चतुर पैटर्न में संदेश को दोहराते हैं, तो सुनने वाला मूल शब्दों को समझ सकता है, भले ही कुछ हिस्से खो जाएं। यही एरर-करेक्टिंग कोड्स (error-correcting codes) का जादू है—वे गणितीय रेसिपी जो आपके टेक्स्ट, फोटो और बैंक ट्रांसफर को गड़बड़ियों से सुरक्षित रखती हैं। दशकों से, गणितज्ञ एक "गोल्डिलॉक्स" (Goldilocks) कोड की तलाश में रहे हैं: एक ऐसा कोड जो तेजी से भेजने के लिए पर्याप्त छोटा हो, कई त्रुटियों को ठीक करने के लिए पर्याप्त मजबूत हो, और कंप्यूटर द्वारा तुरंत जांचने के लिए पर्याप्त सरल हो।

इन कोड्स को बनाने के लिए, वैज्ञानिक अक्सर दो शक्तिशाली उपकरणों का उपयोग करते हैं: ग्रुप्स (groups) (जो समरूपता के नियमकोश की तरह होते हैं, जो आपको बताते हैं कि पैटर्न को तोड़े बिना चीजों को कैसे व्यवस्थित किया जाए) और ग्राफ (graphs) (जो रेखाओं से जुड़े बिंदुओं के मानचित्र होते हैं)। एक प्रसिद्ध प्रकार का मानचित्र केली ग्राफ (Cayley graph) कहलाता है, जिसे एक समूह के विशिष्ट नियमों का पालन करके बनाया जाता है। 2012 में, शोधकर्ताओं ने पाया कि इन विशेष मानचित्रों का उपयोग करके एक नए प्रकार का सुपर-एफिशिएंट कोड बनाया जा सकता है। लेकिन इसमें एक समस्या थी: ये मानचित्र बहुत कठोर नियमों से बने थे, जिससे बनाए जा जाने वाले कोड के प्रकार सीमित हो गए थे। यह एक शानदार रेसिपी होने जैसा था, लेकिन आपको केवल एक विशिष्ट ब्रांड की सामग्रियों का उपयोग करने की अनुमति थी।

अब, दो गणितज्ञों, कोएन डेल वैले (Coen Del Valle) और चेरिल ई. प्रैगर (Cheryl E. Praeger) ने उस पेंट्री के दरवाजे खोल दिए हैं। उन्होंने यह पता लगा लिया है कि इन शक्तिशाली कोड्स को किसी भी प्रकार के मानचित्र का उपयोग करके कैसे बनाया जा सकता है, न कि केवल उन कठोर मानचित्रों का। वे इन्हें ग्राफ कोड्स (graph codes) और डिग्राफ कोड्स (digraph codes) कहते हैं। एक मानक ग्राफ को एक ऐसे मानचित्र के रूप में सोचें जहाँ सड़कें दोनों दिशाओं में जाती हैं, और एक डिग्राफ (digraph) (निर्देशित ग्राफ) एक ऐसे मानचित्र के रूप में है जहाँ एकतरफा सड़कें होती हैं। इन अधिक लचीले मानचित्रों का उपयोग करके, लेखक दिखाते हैं कि हम बहुत अधिक विविध प्रकार के एरर-करेक्टिंग कोड बना सकते हैं। उन्होंने सिद्ध किया कि ये नए कोड पुराने कोड्स जितने ही मजबूत और कुशल हैं, लेकिन इनमें लगभग किसी भी काल्पनिक सममित संरचना (symmetrical structure) से निर्माण करने की स्वतंत्रता जुड़ी हुई है। यह एक बड़ी बात है क्योंकि यह इंजीनियरों और वैज्ञानिकों को बेहतर, तेज़ और अधिक विश्वसनीय संचार प्रणाली डिजाइन करने के लिए एक नया टूलबॉक्स प्रदान करता है।

नया ब्लूप्रिंट: कठोर नियमों से लचीले मानचित्रों तक

लेख एक 2012 के महत्वपूर्ण कार्य को स्वीकार करते हुए शुरू होता है, जो कॉफमैन और लुबोट्स्की (Kaufman and Lubotzky) द्वारा किया गया था। उन्होंने "सिमेट्रिक एलडीपीसी गुड कोड्स" (symmetric LDPC good codes) का एक परिवार बनाने वाले पहले व्यक्ति के रूप में काम किया था। आइए इसे तोड़ते हैं: "LDPC" का अर्थ है कि कोड की जांच करना आसान है (लो-डेंसिटी पैरिटी-चेक), "गुड" का अर्थ है कि यह कुशल और मजबूत दोनों है, और "सिमेट्रिक" का अर्थ है कि कोड वैसा ही दिखता है चाहे आप इसके हिस्सों को कैसे भी घुमाएं या व्यवस्थित करें। उन्होंने इसे केली कोड्स (Cayley codes) का उपयोग करके बनाया था, जो एक ऐसा घर बनाने जैसा है जहाँ हर कमरा अगले कमरे की एक सटीक प्रतिलिपि है, जो नियमों के एक सख्त समूह के अनुसार व्यवस्थित है।

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

लेखकों ने महसूस किया कि यदि किसी मानचित्र में यह "एक जैसा दिखने" का गुण है, तो आपको एक महान कोड बनाने के लिए उसे केली ग्राफ होने की आवश्यकता नहीं है। इससे उनके दो मुख्य आविष्कार हुए:

1. ग्राफ कोड्स (Graph Codes): ये अनडिरेक्टेड मानचित्रों (जहाँ सड़कें दोनों दिशाओं में जाती हैं) पर आधारित हैं। आप एक शुरुआती बिंदु चुनते हैं, अपने पड़ोसियों को देखते हैं, और कनेक्शनों पर एक छोटा, स्थानीय कोड लागू करते हैं। फिर, क्योंकि पूरा मानचित्र हर बिंदु से एक जैसा दिखता है, आप इस स्थानीय नियम को हर जगह कॉपी करते हैं।
2. डिग्राफ कोड्स (Digraph Codes): ये डायरेक्टेड मानचित्रों (एकतरफा सड़कों) पर आधारित हैं। यहाँ, आपको थोड़ा सावधान रहना होगा क्योंकि "आउट" पड़ोसी (जहाँ सड़क जाती है) "इन" पड़ोसियों (जहाँ से सड़क आती है) से अलग हो सकते हैं। इसलिए, आप बाहर जाने वाली सड़कों के लिए एक स्थानीय कोड लागू करते हैं और आने वाली सड़कों के लिए एक अलग कोड।

खेल के नियम

लेखकों ने केवल इन कोड्स का आविष्कार ही नहीं किया; उन्होंने यह भी सिद्ध किया कि ये काम करते हैं। उन्होंने दिखाया कि यदि आप अपने स्थानीय "सामग्रियों" (छोटे कोड्स) को सही ढंग से चुनते हैं, तो अंतिम विशाल कोड मानचित्र की समरूपता को विरासत में प्राप्त करेगा।

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

एक दिलचस्प खोज कनेक्टिविटी (connectivity) के बारे में है। लेखकों ने सिद्ध किया कि यदि आपका मानचित्र डिस्कनेक्टेड है (जैसे कि एक मानचित्र जिसमें दो अलग द्वीप हैं जो आपस में नहीं जुड़ते), तो बड़ा कोड प्रत्येक द्वीप पर बने छोटे कोड्स का एक संग्रह मात्र है। इसका अर्थ है कि आप अपना ध्यान कनेक्टेड मानचित्रों (एक बड़ा द्वीप) के लिए कोड बनाने पर केंद्रित कर सकते हैं, और आप स्वचालित रूप से जान जाएंगे कि बाकी को कैसे संभालना है। यह समस्या को काफी सरल बना देता है।

संख्याओं का खेल: वे कितने अच्छे हैं?

लेखक केवल सिद्धांत तक ही नहीं रुके; उन्होंने गणना की कि ये कोड वास्तव में कितने अच्छे हैं। उन्होंने दो मुख्य आंकड़ों को देखा:

• रेट (Rate): संदेश के कुल आकार की तुलना में आप कितनी उपयोगी जानकारी भेज सकते हैं।
• रिलेटिव डिस्टेंस (Relative Distance): कोड कितनी त्रुटियों को ठीक कर सकता है।

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

यह सिद्ध करने के लिए कि यह वास्तविक दुनिया में काम करता है, उन्होंने इन नए कोड्स का एक अनंत परिवार (infinite family) बनाया। उन्होंने $PSL_2(q)$ (मैट्रिक्स का एक समूह) नामक समूह पर आधारित एक विशिष्ट प्रकार के डायरेक्टेड ग्राफ का उपयोग किया और एक अभाज्य संख्या $p = 4093$ ली। उन्होंने दिखाया कि अभाज्य संख्याओं $q$ की एक अनंत संख्या के लिए, वे ऐसे कोड बना सकते हैं जिनमें:

• एक रेट कम से कम $2/(p+1)$ है, जो लगभग $0.0005$ है।
• एक रिलेटिव डिस्टेंस कम से कम $0.001$ है।

चूंकि ये संख्याएं कोड के बड़ा होने पर भी सकारात्मक बनी रहती हैं, इसलिए वे इसे "अच्छे डिग्राफ कोड्स का एक अनंत परिवार" कहते हैं। यह एक बड़ा कदम है क्योंकि यह सिद्ध करता है कि आप इन कोड्स को उनकी दक्षता खोए बिना बड़ा और बड़ा बना सकते हैं।

आगे क्या है? खुले प्रश्न

लेख एक गणितीय समुदाय को चुनौती देते हुए समाप्त होता है। लेखकों ने कोड्स की एक नई दुनिया के लिए एक पुल बनाया है, लेकिन अभी भी अनछुए क्षेत्र मौजूद हैं। वे तीन विशिष्ट प्रश्न पूछते हैं:

1. क्या हम सिमेट्रिक कोड्स का एक अनंत परिवार पा सकते हैं जो केली ग्राफ से नहीं बने हैं? (उन्हें संदेह है कि हाँ, लेकिन उन्होंने अभी तक इसे सिद्ध नहीं किया है)।
2. क्या हम प्रॉपर डिग्राफ्स (proper digraphs) से बने सिमेट्रिक कोड्स का एक अनंत परिवार पा सकते हैं? एक "प्रॉपर डिग्राफ" एक ऐसा मानचित्र है जहाँ कम से कम एक सड़क एकतरफा है (यदि आप A से B तक जा सकते हैं, तो जरूरी नहीं कि आप B से A तक वापस आ सकें)। यह कठिन है क्योंकि अधिकांश सममित मानचित्र दो-तरफा होते हैं।
3. क्या हम एक ऐसा सिमेट्रिक कोड बना सकते हैं जहाँ "आउट" कोड और "इन" कोड एक दूसरे से अलग हों?

लेखक यह भी बताते हैं कि उनकी विधि अन्य ज्ञात कोड कंस्ट्रक्शन को भी पुन: निर्मित कर सकती है, जैसे कि कोड का डायरेक्ट प्रोडक्ट (direct product) (दो कोड्स को मिलाकर एक बड़ा कोड बनाना)। वास्तव में, उन्होंने दिखाया कि प्रसिद्ध पीटर्सन ग्राफ (10 बिंदुओं वाला एक विशिष्ट, गैर-केली मानचित्र) का उपयोग एक ऐसा कोड बनाने के लिए किया जा सकता है जो अत्यधिक सममित है लेकिन जिसे केली कोड के रूप में नहीं बनाया जा सकता। यह उनकी थ्योरी का एक ठोस उदाहरण है: एक ऐसा कोड जो पुराने कठोर नियमों द्वारा उत्पादित किए जा सकने वाले कोड से बेहतर या भिन्न है।

संक्षेप में, डेल वैले और प्रैगर ने एक शक्तिशाली गणितीय उपकरण लिया, उसकी बाधाओं को कम किया, और दिखाया कि यह अधिक स्वतंत्रता के साथ और भी बेहतर काम करता है। उन्होंने केवल एक नया कोड नहीं खोजा है; उन्होंने उन्हें बनाने के बारे में सोचने का एक नया तरीका खोजा है, जो उन संभावनाओं के लिए द्वार खोलता है जो पहले सख्त समूह नियमों के दरवाजे के पीछे बंद थे।