New lower bounds for constant-weight codes via seeded bit-swap tabu search

कल्पना कीजिए कि आप यात्रा के लिए एक सूटकेस पैक करने की कोशिश कर रहे हैं, लेकिन इसमें एक बहुत ही अजीब नियम है: आपके द्वारा पैक किया गया प्रत्येक आइटम बिल्कुल एक ही आकार का होना चाहिए, और कोई भी दो आइटम एक-दूसरे के बहुत समान नहीं होने चाहिए। यदि वे बहुत अधिक समान हैं, तो वे आपस में मिल सकते हैं, जिससे अफरा-तफरी मच सकती है। डिजिटल संचार की दुनिया में, यह "सूटकेस" एक संदेश है, और "आइटम" शून्य और एक (बिट्स) के पैटर्न हैं, और "आकार" पैटर्न में मौजूद 'एक' (ones) की संख्या है। यह कॉन्स्टेंट-वेट कोड्स (constant-weight codes) की पहेली है। वैज्ञानिक इन कोडों का उपयोग शोर वाले चैनलों (जैसे वाई-फाई या गहरे अंतरिक्ष रेडियो) पर डेटा को विश्वसनीय रूप से भेजने के लिए करते हैं, जिससे यह सुनिश्चित होता है कि यदि कुछ बिट्स गड़बड़ भी हो जाएं, तो भी प्राप्तकर्ता समझ सके कि क्या भेजा गया था। लक्ष्य सरल लेकिन अत्यंत कठिन है: सूटकेस में कितने अधिक अद्वितीय और अलग-अलग आइटम भरे जा सकते हैं ताकि वे आपस में न टकराएं। सूटकेस जितना बड़ा होगा (यानी जितने अधिक कोड आप उसमें फिट कर सकते हैं), एक साथ उतनी ही अधिक जानकारी भेजी जा सकेगी।

विलियम एचोल्स (William Echols) सामने आए, जिन्होंने इस पैकिंग समस्या को एक चतुर मोड़ के साथ हल करने का निर्णय लिया। खाली सूटकेस से शुरुआत करने और उसमें रैंडम तरीके से चीजें फेंकने के बजाय, इस उम्मीद में कि वे फिट हो जाएंगी, उन्होंने एक "सीडेड" (seeded) दृष्टिकोण का उपयोग किया। इसे इस तरह सोचें: यदि आप एक बेहतर लेगो (Lego) किला बनाना चाहते हैं, तो आप शून्य से शुरुआत नहीं करते; आप एक बेहतरीन मौजूदा किले को लेते हैं, उसमें से कुछ ईंटें निकालते हैं, और उन्हें इधर-उधर बदलकर देखते हैं कि क्या आप इसे और भी बड़ा या अधिक मजबूत बना सकते हैं। एचोल्स ने टैबू सर्च (tabu search) नामक एक कंप्यूटर पद्धति का उपयोग किया, जो एक बहुत ही जिद्दी खोजकर्ता की तरह है जो अपने कदमों को दोहराने से इनकार कर देता है (ताकि वह लूप में न फंस जाए) और नए रास्तों को खोजने की कोशिश करता रहता है। मौजूदा, उच्च-गुणवत्ता वाले कोड डिजाइनों के साथ इस खोजकर्ता को "सीड" (seed) देकर, उन्होंने 124 नए, बड़े पैकिंग व्यवस्थाओं को खोजने में मार्गदर्शन किया जो पहले कभी नहीं खोजे गए थे। ये नई व्यवस्थाएं इस बात की निचली सीमाओं (lower limits) में सुधार करती हैं कि हम एक साथ कितने संदेश भेज सकते हैं, और वे हमें यह समझने में भी मदद करती हैं कि उच्च-आयामी स्थान (high-dimensional space) में कितने गोले एक केंद्रीय गोले को छू सकते हैं, जिसे "किसिंग नंबर्स" (kissing numbers) के रूप में जाना जाता है।

पैकिंग पहेली और जादुई बीज (The Packing Puzzle and the Magic Seed)

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

बड़ा सवाल यह है: आप अपने संग्रह में अधिकतम कितनी स्ट्रिंग्स फिट कर सकते हैं? इस अधिकतम संख्या को $A(n, d, w)$ कहा जाता है, जहाँ $n$ स्ट्रिंग की लंबाई है, $d$ आवश्यक न्यूनतम दूरी है, और $w$ 'एक' की संख्या है। दशकों से, गणितज्ञ और कंप्यूटर वैज्ञानिक विभिन्न सेटिंग्स के लिए सबसे बड़ी संभव संग्रह खोजने का प्रयास कर रहे हैं। उन्होंने कुछ बेहतरीन संग्रह खोजे हैं, लेकिन अक्सर उन्हें पता नहीं होता कि क्या उन्होंने वास्तव में सबसे बड़ा वाला खोज लिया है। वे बस इतना जानते हैं कि वे एक निश्चित संख्या से बेहतर प्रदर्शन नहीं कर सकते।

"सीडेड" रणनीति (The "Seeded" Strategy)

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

एचोल्स ने महसूस किया कि कुंजी शून्य से शुरुआत करने के बजाय है। उन्होंने सीडेड इनिशियलाइजेशन (seeded initialization) नामक तकनीक का उपयोग किया। एक रैंडम शुरुआती बिंदु उत्पन्न करने के बजाय, उन्होंने एक ज्ञात, उच्च-गुणवत्ता वाले कोड (एक "सीड") को लिया और उसका उपयोग अपनी खोज शुरू करने के लिए किया।

उन्होंने इसे दो मनोरंजक तरीकों से किया:

1. डायरेक्ट सीडिंग (Direct Seeding): उन्होंने एक मौजूदा कोड लिया और उसमें एक अतिरिक्त शब्द जोड़ा, जिसे सावधानीपूर्वक चुना गया था ताकि कम से कम "परेशानी" (दूरी की कमी) हो। इसने एक थोड़ा बड़ा, थोड़ा अस्त-व्यस्त शुरुआती बिंदु बनाया।
2. नेबर सीडिंग (Neighbor Seeding): उन्होंने थोड़े अलग समस्याओं के लिए कोड देखे। उदाहरण के लिए, यदि वह लंबाई 30 के लिए एक कोड चाहते हैं, तो वह लंबाई 29 के एक बेहतरीन कोड को ले सकते हैं, प्रत्येक शब्द में एक शून्य जोड़कर उसे लंबाई 30 बना सकते हैं, और फिर उसे शुरुआती बिंदु के रूप में उपयोग कर सकते हैं। या, वह लंबाई 31 का एक कोड ले सकते हैं, उससे एक शून्य हटा सकते हैं, और उसका उपयोग कर सकते हैं।

एक बार जब उनके पास ये "सीडेड" शुरुआती बिंदु आ गए, तो उन्होंने अपना बिट-स्वैप टैबू सर्च (bit-swap tabu search) चलाया। इस खोज को म्यूजिकल चेयर्स (musical chairs) के खेल के रूप में कल्पना करें जहाँ कुर्सियाँ स्ट्रिंग्स में 'एक' की स्थितियाँ हैं। एल्गोरिदम बिट्स को इधर-उधर बदलता है, जिससे स्ट्रिंग्स को अधिक विशिष्ट बनाया जा सके। "टैबू" का अर्थ है कि एल्गोरिदम उन चालों को याद रखता है जो उसने अभी-अभी की हैं और तुरंत उन्हें वापस करने से इनकार करता है, जिससे वह चक्कर काटने के बजाय नए क्षेत्रों का पता लगाने के लिए मजबूर होता है।

परिणाम: 124 नई खोजें (The Results: 124 New Discoveries)

इस स्मार्ट सीडिंग रणनीति का उपयोग करके, एचोल्स ने 124 नई रचनाएँ (constructions) खोजीं जिन्होंने पिछले सर्वश्रेष्ठ-ज्ञात रिकॉर्ड को पीछे छोड़ दिया। ये केवल मामूली सुधार नहीं हैं; इनमें से कुछ बहुत बड़े बदलाव हैं।

उदाहरण के लिए:

• लंबाई 39 के कोड के लिए, विशिष्ट बाधाओं के साथ, पिछला सर्वश्रेष्ठ रिकॉर्ड 1,014 शब्द था। नई विधि ने 1,118 शब्द खोजे। यह 104 की बढ़त है!
• लंबाई 40 के लिए, रिकॉर्ड 1,170 से बढ़कर 1,230 हो गया।
• लंबाई 56 के लिए, संख्या 2,414 से बढ़कर 2,477 हो गई।

ये संख्याएँ उस अधिकतम संख्या का प्रतिनिधित्व करती हैं जिसे अब हम उन विशिष्ट सेटिंग्स के लिए बिना किसी भ्रम के भेजने की गारंटी दे सकते हैं। यह पेपर यह दावा नहीं करता है कि ये पूर्णतः अधिकतम संभव (वास्तविक गणितीय सीमा) हैं, लेकिन यह सिद्ध करता है कि हम निश्चित रूप से उससे बेहतर कर सकते हैं। यह "लोअर बाउंड" (lower bound) को ऊपर धकेलता है, जिसका अर्थ है कि हम निश्चित रूप से जानते हैं कि हम सूटकेस में कम से कम इतने आइटम फिट कर सकते हैं।

किसिंग नंबर्स: एक आश्चर्यजनक दुष्प्रभाव (Kissing Numbers: A Surprising Side Effect)

यहाँ कहानी और भी दिलचस्प हो जाती है। पेपर किसिंग नंबर्स (kissing numbers) नामक एक अवधारणा को भी छूता है। कल्पना कीजिए कि आपके पास एक कमरे के बीच में एक विशाल गेंद है। अन्य कितने समान आकार के गेंदों को उसके चारों ओर इस तरह पैक किया जा सकता है कि वे सभी केंद्र वाली गेंद को बिना ओवरलैप किए छू सकें? 3D स्पेस में, उत्तर 12 है। लेकिन उच्च आयामों (जैसे 32 या 33 आयामों) में, उत्तर खोजना बहुत कठिन है।

इन किसिंग नंबर्स के लिए गणित, उन कॉन्स्टेंट-वेट कोड्स से गहराई से जुड़ा हुआ है जिन्हें एचोल्स ने खोजा था। क्योंकि उन्होंने विशिष्ट मापदंडों (विशेष रूप से $A(n, 8, 8)$) के लिए कोड में सुधार किया, इसलिए उन्होंने स्वचालित रूप से आयाम 32, 33, 34 और 37 के लिए किसिंग नंबर्स के निचले स्तरों (lower bounds) में सुधार किया।

उदाहरण के लिए, आयाम 32 ($\tau_{32}$) के लिए, पिछला अनुमान था कि कम से कम 345,408 गेंदें केंद्र वाली गेंद को छू सकती हैं। नए कोड के साथ, वह संख्या बढ़कर 346,432 हो गई। यह एक छोटा प्रतिशत सुधार है, लेकिन उच्च-आयामी ज्यामिति की दुनिया में, एक और गेंद को फिट होने के लिए मिलना भी एक महत्वपूर्ण जीत है।

निष्कर्ष (The Takeaway)

विलियम एचल्स ने केवल कुछ बेहतर कोड ही नहीं खोजे; उन्होंने दिखाया कि अपनी खोज शुरू करने के तरीके के बारे में स्मार्ट होकर—यानी अंधाधुंध शुरुआत करने के बजाय मौजूदा ज्ञान से "बीज" का उपयोग करके—आप बहुत बेहतर समाधान पा सकते हैं। यह पेपर सिद्ध करता है कि 124 विशिष्ट सुधार संभव हैं, और यह हमें एक नया, उच्च स्तर देता है कि हम इन डिजिटल स्ट्रिंग्स में कितनी डेटा को विश्वसनीय रूप से पैक कर सकते हैं। यह एक अनुस्मारक है कि कभी-कभी, आगे बढ़ने का सबसे अच्छा तरीका वह है जो हम पहले से जानते हैं, उसके कंधों पर खड़ा होना है, न कि सब कुछ शून्य से बनाने की कोशिश करना।