🔢 mathematics

Optimal Non-Binary Single-Track Gray Code

यह शोध पत्र $p=3$ और $p=5$ के अभाज्य संख्याओं के लिए परिमित क्षेत्र $\mathbb{F}_p$ पर $p^{p^t}$ कोडवर्ड वाले $p^t$ लंबाई के इष्टतम गैर-बाइनरी सिंगल-ट्रैक ग्रे कोड्स (Gray codes) के अस्तित्व को सिद्ध करता है, साथ ही बड़ी अभाज्य संख्याओं और गैर-अभाज्य वर्णमाला आकारों के लिए उनके अस्तित्व हेतु स्थितियाँ भी प्रदान करता है।

मूल लेखक: Tuvi Etzion

प्रकाशित 2026-07-16

📖 8 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: Tuvi Etzion

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

कल्पना कीजिए कि आप एक घूमते हुए पहिए का हिसाब रखने की कोशिश कर रहे हैं, जैसे कि साइकिल का पहिया या कोई विशाल औद्योगिक पंखा। आप यह जानना चाहते हैं कि किसी भी क्षण में पहिया बिल्कुल कहाँ है। ऐसा करने के लिए, इंजीनियर पहिए पर पट्टियाँ (stripes) पेंट करते हैं और सेंसर का उपयोग करके उन्हें पढ़ते हैं। यदि आप एक मानक नंबरिंग सिस्टम का उपयोग करते हैं, तो सेंसर भ्रमित हो सकते हैं जब पहिया दो नंबरों के ठीक बीच में होता है, क्योंकि एक साथ कई पट्टियाँ बदल सकती हैं, जिससे एक "ग्लिच" (glitch) पैदा हो सकता है जहाँ कंप्यूटर सोचता है कि पहिया गलत जगह पर है।

इसे ठीक करने के लिए, गणितज्ञों ने एक विशेष प्रकार का कोड बनाया जिसे ग्रे कोड (Gray code) कहा जाता है। इसे ऐसे समझें कि यह एक गुप्त भाषा है जहाँ, एक नंबर से अगले नंबर पर जाने के लिए, आपको एक बार में केवल एक ही चीज़ बदलने की अनुमति है। यह एक सीढ़ी चढ़ने जैसा है जहाँ आप केवल एक पायदान ऊपर या नीचे जा सकते हैं; आप कभी भी एक साथ दो पायदान नहीं कूदते। यह सुनिश्चित करता है कि यदि आपके सेंसर थोड़े डगमगाते भी हैं, तो वे केवल एक छोटी, हानिरहित गलती देखेंगे, न कि एक बड़ी उलझन।

अब, कल्पना कीजिए कि आप एक सुपर-प्रिसाइज (अति-सटीक) पहिया बनाना चाहते हैं, लेकिन आपके पास हर एक सेंसर के लिए एक अलग ट्रैक पेंट करने के लिए पर्याप्त जगह नहीं है। आपको उस सारी जानकारी को एक छोटे पैकेज में समेटने की आवश्यकता है। यहीं पर सिंगल-ट्रैक ग्रे कोड्स (Single-Track Gray Codes) काम आते हैं। कई ट्रैकों के बजाय, आपके पास केवल एक ट्रैक होता है जिसे कॉपी और शिफ्ट किया जाता है। यह एक लंबे, कोड वाले रिबन जैसा है जिसे पहिए के चारों ओर लपेटा गया है, लेकिन सेंसर इसे अलग-अलग शुरुआती बिंदुओं से पढ़ते हैं। जादू यह है कि जब इस एक रिबन को अलग-अलग कोणों से पढ़ा जाता है, तो यह अभी भी "केवल एक चीज़ बदलने" के नियम का पालन करता है।

लंबे समय तक, वैज्ञानिक जानते थे कि साधारण "हाँ/नहीं" (बाइनरी) सिस्टम के लिए इन्हें कैसे बनाया जाए, लेकिन वे एक दीवार से टकरा गए: वे इन्हें हर संभव आकार के लिए काम करने लायक नहीं बना सके, खासकर जब पहिए को बिना कुछ छोड़े हर स्थिति दिखानी हो। उन्हें जटिल सिस्टम (जो 0, 1, 2, 3 और 4 जैसे नंबरों का उपयोग करते हैं) के लिए भी बनाने में संघर्ष करना पड़ा।

यह शोध पत्र उस दीवार को तोड़ने के बारे में है। लेखकों ने, टी. एत्ज़ियन (T. Etzion) के नेतृत्व में, यह पता लगाया है कि कैसे इन "सिंगल-ट्रैक" कोडों को उन सिस्टम के लिए बनाया जाए जो 3 और 5 जैसे अभाज्य संख्याओं (prime numbers) को अपने वर्णमाला के आकार के रूप में उपयोग करते हैं। उन्होंने केवल अनुमान नहीं लगाया; उन्होंने एक गणितीय मशीन—एक रिकर्सिव रेसिपी (recursive recipe)—बनाई, जो यह साबित करती है कि ये कोड निश्चित रूप से मौजूद हैं (विशिष्ट आकारों के लिए, जैसे $p^t$ जहाँ $p$ 3 या 5 है और $t$ कोई भी संख्या 2 या उससे अधिक है)।

यहाँ बताया गया है कि उन्होंने इसे कैसे किया, कुछ मनोरंजक रूपकों (metaphors) का उपयोग करते हुए:

निर्माण खंड: "सेल्फ-डुअल" रिबन (The Building Blocks: The "Self-Dual" Ribbons)

अपने कोड को बनाने के लिए, लेखकों को एक विशेष प्रकार की सामग्री की आवश्यकता थी। कल्पना कीजिए कि आपके पास कागज की एक लंबी पट्टी है जिस पर नंबरों का पैटर्न है। अब, कल्पना कीजिए कि एक "जादुвिक दर्पण" है जो पट्टी के हर नंबर में 1 जोड़ देता है (तो 0 बन जाता है 1, 1 बन जाता है 2, और 2 वापस 0 हो जाता है)।

आमतौर पर, यदि आप मूल पट्टी और दर्पण वाली पट्टी को देखते हैं, तो वे पूरी तरह से अलग दिखती हैं। लेकिन लेखकों को एक विशेष प्रकार की पट्टी चाहिए थी जहाँ, यदि आप दर्पण छवि को सही मात्रा में खिसका दें, तो वह बिल्कुल मूल पट्टी जैसी ही दिखे। वे इन्हें सेल्फ-डुअल सीक्वेंस (Self-Dual Sequences - SDS) कहते हैं। इन्हें उन रिबनों के रूप में सोचें जो एक विशिष्ट प्रकार के जादुविक रूपांतरण के तहत पूरी तरह से सममित (symmetrical) हैं।

यह शोध पत्र सिद्ध करता है कि आप 3 या 5 के सिस्टम के लिए इन रिबनों की एक अनंत आपूर्ति बना सकते हैं। उन्होंने यह करके दिखाया कि आप एक छोटा रिबन लें, उसमें कुछ अतिरिक्त "फ्लेवर" (गणितीय शब्द जिन्हें $Z$ और $Y$ कहा जाता है) जोड़ें, और बस—आपके पास एक बड़ा, पूर्ण रिबन तैयार है। यह एक फ्रैक्टल (fractal) की तरह है: आप एक छोटा पैटर्न लेते हैं, एक नियम लागू करते हैं, और यह एक बड़े पैटर्न में विकसित हो जाता है जो अभी भी अपनी विशेष समरूपता बनाए रखता है।

असेंबली लाइन: रिबनों को आपस में सिलना (The Assembly Line: Stitching the Ribbons Together)

रिबन होना लड़ाई का केवल आधा हिस्सा है। आपको उन्हें एक विशिष्ट क्रम में व्यवस्थित करने की आवश्यकता है ताकि अंतिम कोड बनाया जा सके। यदि आप उन्हें बस एक ढेर में फेंक देते हैं, तो सेंसर भ्रमित हो जाएंगे।

लेखकों को इन रिबनों को इस तरह व्यवस्थित करना था कि जब आप एक रिबन से दूसरे पर जाते हैं, तो आप कोड में केवल एक ही स्थान बदलते हैं। यह सबसे कठिन हिस्सा है। यह ताश की गड्डी को एक विशेष क्रम में रखने जैसा है जहाँ हर बार जब आप एक कार्ड बदलते हैं, तो आप केवल उस एक कार्ड का मान बदल सकते हैं, और आपको अंततः बिना कहीं अटके वापस शुरुआत पर आना होगा।

संख्या 3 (टेनरी सिस्टम) और संख्या 5 (क्वेनरी सिस्टम) के लिए, लेखकों ने इसे करने का एक तरीका खोजा। उन्होंने एक चतुर "मर्जिंग" (merging) तकनीक का उपयोग किया। कल्पना कीजिए कि आपके पास रिबनों के कई समूह हैं। कुछ समूह बहुत समान हैं, जिनमें केवल एक छोटी सी जगह पर अंतर है। लेखकों ने दिखाया कि कैसे आप दो समूहों को ले सकते हैं, उस सटीक स्थान को ढूंढ सकते हैं जहाँ वे भिन्न होते हैं, और उन्हें एक बड़े समूह में बुन सकते हैं, जबकि "केवल एक चीज़ बदलने" के नियम को बरकरार रखते हुए।

उन्होंने सिद्ध किया कि आकारों के आधार पर (जैसे $3^2, 3^3, 5^2$ आदि), आप हमेशा एक फुल-पीरियड (full-period) कोड बनाने के लिए इन रिबनों को जोड़ने का एक तरीका ढूंढ सकते हैं। इसका मतलब है कि यह कोड हर एक संभावित स्थिति ( $m^{m^t}$ codewords) को बिना कुछ छोड़े दर्शा सकता है।

उन्होंने क्या नहीं किया (और उन्होंने क्या खारिज कर दिया)

यह जानना महत्वपूर्ण है कि यह शोध पत्र क्या नहीं कह रहा है।

यह सभी संख्याओं के लिए कोई जादुई छड़ी नहीं है: लेखकों ने स्पष्ट रूप से कहा है कि बाइनरी सिस्टम (केवल 0 और 1 का उपयोग करने वाले) के लिए, आप $n=2$ के अलावा किसी भी आकार के लिए फुल-पीरियड सिंगल-ट्रैक कोड नहीं बना सकते। उन्होंने सिद्ध किया कि बड़े बाइनरी पहियों के लिए यह असंभव है।
यह अभी सभी अभाज्य संख्याओं के लिए नहीं है: हालांकि उन्होंने 3 और 5 के लिए यह सिद्ध किया, लेकिन उन्होंने स्वीकार किया कि बड़े अभाज्य नंबरों (जैसे 7, 11, 13) के लिए, उन्हें अभी तक "सीड" (seed) रिबन नहीं मिले हैं। उन्हें संदेह है कि रेसिपी काम करती है, लेकिन उन्हें पहले शुरुआती पैटर्न खोजने की आवश्यकता है।
यह (ज्यादातर) गैर-अभाज्य संख्याओं के लिए नहीं है: उन्होंने आकार 4 के लिए एक विशिष्ट उदाहरण दिया, लेकिन उनका मुख्य, कठोर प्रमाण अभाज्य संख्याओं के लिए है।

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

यह शोध पत्र केवल यह सुझाव नहीं देता कि ये कोड मौजूद हो सकते हैं; यह 3 और 5 के आधार पर आकारों के एक अनंत परिवार के लिए इनके अस्तित्व को सिद्ध करता है। उन्होंने गणितीय "ब्लूप्रिंट" (रिकर्सिव कंस्ट्रक्शन) और "स्टार्टर किट्स" (3 और 5 के लिए बीज/seeds) प्रदान किए हैं।

जिज्ञासु किशोर या इंजीनियर के लिए जो एक हाई-स्पीड सेंसर डिजाइन कर रहा है, यह एक बड़ी बात है। इसका मतलब है कि मशीनों के एक पूरे नए वर्ग के लिए, अब हम ऐसे एनकोडर बना सकते हैं जो छोटे, अधिक सटीक और त्रुटियों के प्रति कम संवेदनशील हैं। लेखकों ने एक दरवाजा खोल दिया है, यह दिखाते हुए कि सही गणितीय उपकरणों के साथ, हम सूचनाओं को उन तरीकों से व्यवस्थित कर सकते हैं जो पहले असंभव माने जाते थे। उन्होंने केवल घास के ढेर में सुई नहीं ढूंढी; उन्होंने एक ऐसी मशीन बनाई है जो अनंत घास के ढेरों में से सुई ढूंढ सकती है, जब तक कि वे ढेर 3 और 5 के बने हों।

तकनीकी सारांश: इष्टतम गैर-बाइनरी सिंगल-ट्रैक ग्रे कोड (Optimal Non-Binary Single-Track Gray Code)

समस्या का विवरण
यह शोध पत्र गैर-बाइनरी वर्णमाला (alphabets) पर सिंगल-ट्रैक ग्रे कोड्स (STGCs) के निर्माण को संबोधित करता है। लंबाई $n$ और आवर्त $P$ वाला एक STGC, $P$ विशिष्ट शब्दों की एक चक्रीय सूची है जहाँ क्रमिक शब्द ठीक एक स्थिति में भिन्न होते हैं, और कोड ऐरे के $n$ ट्रैक (कॉलम) एक ही ट्रैक के चक्रीय शिफ्ट (cyclic shifts) होते हैं। जबकि बाइनरी STGCs के लिए पूर्ण आवर्त ( $P=2^n$ ) केवल $n=2$ के लिए ज्ञात है, और $n > 2$ के लिए अधिकतम आवर्त $2^n - 2^n$ तक सीमित है, यह शोध पत्र बड़े वर्णमालाओं पर ऐसे कोड्स के अस्तित्व की जांच करता है। विशेष रूप से, यह $\mathbb{F}_p$ (जहाँ $p$ एक अभाज्य संख्या है) पर लंबाई $n = p^t$ और आवर्त $P = p^{p^t}$ के लिए STGCs के निर्माण की खोज करता है, जो इन मापदंडों के लिए पूर्ण-अवर्त (full-period) कोड्स का प्रतिनिधित्व करेंगे।

कार्यप्रणाली (Methodology)
लेखक गैर-बफरी सेल्फ-डुअल सीक्वेंस (SDSs) पर आधारित एक पुनरावर्ती निर्माण रणनीति (recursive construction strategy) का उपयोग करते हैं। कार्यप्रणाली निम्नलिखित चरणों के माध्यम से आगे बढ़ती है:

बाइनरी निर्माणों का सामान्यीकरण: शोध पत्र मौजूदा बाइनरी STGC निर्माण प्रमेयों (विशेष रूप से पूर्व कार्य में शामिल सेल्फ-डुअल अनुक्रमों से संबंधित प्रमेय 2) को गैर-बाइनरी वर्णमाला $\mathbb{Z}_m$ पर अनुकूलित करता है। यह अनुकूलन (प्रमेय 4) के लिए $m^n$ आवर्त के $r$ युग्म-अतुल्य (pairwise inequivalent) SDSs के क्रम की आवश्यकता होती है ताकि क्रमिक अनुक्रम ठीक $m$ निर्देशांकों में भिन्न हों, जिसमें शिफ्ट ऑपरेटर $E$ और अंतर सेट (difference set) पर विशिष्ट शर्तें लागू होती हैं।
SDSs का पुनरावर्ती उत्पादन (Recursive Generation of SDSs): SDSs को $\mathbb{Z}_p$ $Z_{p}$ (जहाँ $p$ $p$ एक विषम अभाज्य संख्या है) पर उत्पन्न करने के लिए एक मुख्य घटक एक पुनरावर्ती विधि है।
- आधार मामला (Base Case): दिए गए आवर्त $p^t$ के लिए, एक SDS का रूप $[X, X+1, \dots, X+(p-1)]$ होता है।
- पुनरावर्ती चरण (Recursive Step): आवर्त $p^t$ से आवर्त $p^{t+1}$ का SDS बनाने के लिए, लेखक एक आधार शब्द $Z$ (शून्य से शुरू) और सहायक शब्दों $Y_1, \dots, Y_{p-2}$ का उपयोग करके एक नया शब्द $V$ परिभाषित करते हैं। नया SDS $[V, V+1, \dots, V+(p-1)]$ के रूप में बनाया जाता है।
- संयोजन गणना (Combinatorial Counting): शोध पत्र सिद्ध करता है कि यह निर्माण आवश्यक संख्या में विशिष्ट SDSs ( $p^{p^t - t - 1}$ ) प्रदान करता है, जो $Z$ और $Y$ वेक्टर्स के चयन की गणना करता है।
व्यवस्था और विलय (Arrangement and Merging): इन उत्पन्न SDSs को एक अनुक्रम में व्यवस्थित करने की महत्वपूर्ण चुनौती है जो STGC आसन्नता (adjacency) शर्तों (अंतिम कोड में ठीक एक निर्देशांक में भिन्न होना) को संतुष्ट करता हो।
- लेखक (P1) और (P2) गुणों को परिभाषित करते हैं कि वे स्थान जहाँ क्रमिक SDSs भिन्न होते हैं।
- एक जटिल विलय प्रक्रिया (जो $p=3$ के लिए विस्तृत है) वर्णित है जहाँ SDSs के घटकों को संयोजित किया जाता है। इसमें भार (weight) द्वारा शब्दों को विभाजित करना और सूचियों $A(Z, Y)$ को इस तरह मिलाना शामिल है कि परिणामी SDSs का अनुक्रम आवश्यक अंतर गुणों को बनाए रखे।
- विलय तर्क यह सुनिश्चित करता है कि अंतर स्थितियों का सेट $D_{p^{t+1}}$ सभी आवश्यक इंडेक्स $\{0, 1, \dots, p^t - 1\}$ को कवर करता है।

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

अस्तित्व का प्रमाण: शोध पत्र विशिष्ट अभाज्य संख्याओं $p=3$ और $p=5$ के लिए, सभी $t \ge 2$ के लिए, लंबाई $n = p^t$ और आवर्त $P = p^{p^t}$ के पूर्ण-अवर्त गैर-बाइनरी STGCs के अस्तित्व को सिद्ध करता है।
पुनरावर्ती ढांचा (Recursive Framework): यह किसी भी विषम अभाज्य $p$ के लिए एक सामान्य पुनरावर्ती निर्माण ढांचा प्रदान करता है। यह निर्माण एक "उपयुक्त बीज" (appropriate seed)—अर्थात, $p^2$ (या $p=3$ के लिए आवर्त 27) के सभी SDSs के एक विशिष्ट व्यवस्था—की उपस्थिति पर सशर्त है।
विशिष्ट बीज (Specific Seeds): लेखक $p=3$ (आवर्त 27 के 729 SDSs) और $p=5$ (परिशिष्ट A और B में विस्तृत) के लिए आवश्यक बीज प्रदान करते हैं, जिससे इन दो मामलों के लिए निर्माण पूरा होता है।
गैर-अभाज्य वर्णमाला: शोध पत्र नोट करता है कि हालांकि प्राथमिक ध्यान अभाज्य क्षेत्रों (prime fields) पर है, संकेत मौजूद हैं कि ऐसे कोड गैर-अभाज्य वर्णमाला आकारों के लिए भी अस्तित्व में हो सकते हैं (इसे उदाहरण 3 में $m=4$ के लिए प्रदर्शित किया गया है)।

महत्व और दावे
शोध पत्र का दावा है कि यह पूर्ण-अवर्त सिंगल-ट्रैक ग्रे कोड्स के पहले और एकमात्र ज्ञात दो अनंत परिवारों ( $p=3$ और $p=5$ के लिए) को प्रस्तुत करता है। इसका महत्व उस सीमा को पार करने में निहित है जो बाइनरी कोड्स में पाई जाती है जहाँ $n > 2$ के लिए पूर्ण-अवर्त STGCs मौजूद नहीं होते हैं। गैर-बाइनरी वर्णमालाओं का उपयोग करके, लेखक ऐसे कोड प्राप्त करते हैं जिनमें लंबाई $n$ के सभी संभावित शब्द ( $P = p^{p^t}$ ) शामिल होते हैं, जो उच्च रिज़ॉल्यूशन वाले क्वांटिज़ेशन और कोडिंग अनुप्रयोगों के लिए इष्टतम है जिन्हें एक एकल भौतिक ट्रैक की आवश्यकता होती है।

लेखक विनम्रतापूर्वक कहते हैं कि $p > 5$ के लिए अभाज्य संख्याओं हेतु, निर्माण सैद्धांतिक रूप से मान्य है लेकिन इसके लिए उपयुक्त बीजों (आवर्त $p^2$ के SDSs की व्यवस्था) की खोज की आवश्यकता है। वे भविष्य के अनुसंधान के प्राथमिक दिशाओं के रूप में बड़े अभाज्य संख्याओं के लिए इन बीजों की खोज, और गैर-बाइनरी वर्णमालाओं के लिए "कॉम्प्लीमेंटेड साइकलिंग रजिस्टर" के सामान्यीकरण की पहचान करते हैं। शोध पत्र यह दावा नहीं करता है कि इसने सभी अभाज्य या गैर-अभाज्य आकारों के लिए समस्या को हल कर दिया है, बल्कि यह $p=3$ और $p=5$ के लिए अस्तित्व स्थापित करता है और अन्य के लिए मार्ग रेखांकित करता है।

निर्माण खंड: "सेल्फ-डुअल" रिबन (The Building Blocks: The "Self-Dual" Ribbons)

असेंबली लाइन: रिबनों को आपस में सिलना (The Assembly Line: Stitching the Ribbons Together)

उन्होंने क्या नहीं किया (और उन्होंने क्या खारिज कर दिया)

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

इसी तरह के और पेपर