🔢 mathematics

Function-Correcting Codes for Insertion-Deletion Channel

यह शोध पत्र इंसर्शन-डिलेशन चैनलों के लिए फंक्शन-करेक्टिंग कोड्स का एक नया ढांचा प्रस्तावित करता है, इसके विभिन्न स्वरूपों की समानता स्थापित करता है, इष्टतम रेडंडेंसी और कोड लंबाई पर मौलिक सीमाएं व्युत्पन्न करता है, और कई प्रकार के फलनों (फंक्शंस) के लिए विशिष्ट प्रदर्शन सीमाओं का विश्लेषण करता है।

मूल लेखक: Anamika Singh, Abhay Kumar Singh

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

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

CC BY 4.0

मूल लेखक: Anamika Singh, Abhay Kumar Singh

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

कल्पना कीजिए कि आप एक शोर-शराबे वाली, उथल-पुथल भरी नदी के पार एक गुप्त संदेश भेज रहे हैं। पारंपरिक कोडिंग की दुनिया में, नदी कुछ अक्षरों को बदल सकती है (जैसे "A" को "B" में बदलना)। लेकिन इस शोध पत्र में, लेखक एक बहुत अधिक जटिल नदी से निपटते हैं: जो आपके संदेश से अक्षरों को बेतरतीब ढंग से निकाल देती है या उसमें अतिरिक्त, यादृच्छिक अक्षर जोड़ देती है। इसे "इंसर्शन-डिलिशन" (insertion-deletion) चैनल कहा जाता है।

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

मुख्य विचार: क्या आपको पूरे फूलदान की आवश्यकता है?

लेखक एक सरल प्रश्न पूछते हैं: क्या वास्तव में आपको पूरे संदेश की आवश्यकता है?

अक्सर, आपको केवल संदेश के बारे में एक विशिष्ट तथ्य जानने की आवश्यकता होती है।

परिदृश्य A: आप एक लंबा दस्तावेज़ भेजते हैं। आपको डिकोडर को हर शब्द पढ़ने की आवश्यकता नहीं है। आपको बस यह जानने की आवश्यकता है: "क्या यह दस्तावेज़ संस्करण 1 है या संस्करण 2?"
परिदृश्य B: आप DNA डेटा संग्रहीत कर रहे हैं। आपको पूरे अनुक्रम (sequence) की आवश्यकता नहीं है; आपको बस यह जानने की आवश्यकता है: "यह विशिष्ट पैटर्न कितनी बार दोहराता है?"

यहीं पर फंक्शन-करेक्टिंग कोड्स (FCCs) काम आते हैं। पूरे संदेश को बचाने के बजाय, ये कोड केवल एक विशिष्ट प्रश्न (फंक्शन) के उत्तर को सुरक्षित करने के लिए डिज़ाइन किए गए हैं। इसके लिए पूरे संदेश को बचाने की तुलना में बहुत कम "गोंद" (redundancy) की आवश्यकता होती है।

समस्या: "फिसलन भरी" नदी

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

इसे दो लोगों के साथ-साथ चलते हुए हाथ पकड़ने जैसा समझें।

पुराना तरीका (प्रतिस्थापन त्रुटियां/Substitution Errors): यदि एक व्यक्ति अपनी शर्ट का रंग बदल लेता है, तो उसे पहचानना आसान है।
नया तरीका (इंसर्शन/डिलिशन): यदि एक व्यक्ति एक कदम चूक जाता है या एक अतिरिक्त कदम ले लेता है, तो दूसरा व्यक्ति गलती से बगल वाले व्यक्ति का गलत हाथ पकड़ सकता है। "अलाइनमेंट" (alignment) टूट जाता है।

लेखकों ने पाया कि यदि आपका "गोंद" (redundancy) आपके "संदेश" से छोटा है, तो यह मिश्रण इतना खराब हो जाता है कि सिस्टम विफल हो जाता है। इसे ठीक करने के लिए, उन्होंने सिद्ध किया कि इस उथल-पुथल भरी नदी में ठीक से काम करने के लिए गोंद संदेश के कम से कम बराबर लंबा होना चाहिए।

नया टूलकिट: "डिस्टेंस मैट्रिसेस" (Distance Matrices)

इसे हल करने के लिए, लेखकों ने एक नया तरीका बनाया जिससे यह मापा जा सके कि इस अराजक नदी में दो संदेश एक-दूसरे से कितने "दूर" हैं। वे इन्हें इंसडेल-डिस्टेंस मैट्रिसेस (Insdel-Distance Matrices) कहते हैं।

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

पुरानी गणित: "कितने स्थान अलग हैं?" (हैमिंग डिस्टेंस)।
नई गणित: "कार A को कार B की जगह पर ले जाने के लिए मुझे कितने कदम उठाने होंगे, इस बात को ध्यान में रखते हुए कि लोग बीच में आ और जा रहे हैं?"

उन्होंने गणना करने के लिए दो प्रकार के मानचित्र (मैट्रिक्स) बनाए:

प्रकार 1: एक बुनियादी मानचित्र।
प्रकार 2: एक "सुपर-मैप" जो लंबे गोंद के साथ होने वाली अतिरिक्त उथल-पुथल को ध्यान में रखता है। उन्होंने पाया कि सिस्टम के काम करने के लिए, आपको सुपर-मैप का उपयोग करना ही होगा।

परिणाम: DNA और फाइलों पर पैसे बचाना

यह शोध पत्र इस नए सिस्टम का परीक्षण चार विशिष्ट प्रकार के "प्रश्नों" (फंक्शन्स) पर करता है जो वास्तविक जीवन में सामान्य हैं:

VT-सिंड्रोम (VT-Syndrome): एकल त्रुटियों को ठीक करने के लिए उपयोग किया जाने वाला एक विशिष्ट गणितीय चेक।
नंबर-ऑफ-रन्स (Number-of-Runs): पैटर्न कितनी बार बदलता है, इसकी गिनती (जैसे, DNA में, कितनी बार अनुक्रम "A" से "T" में बदलता है)।
मैक्सिमम रन-लेंथ (Maximum Run-Length): समान अक्षरों के सबसे लंबे विस्तार को खोजना (जैसे, "AAAAA" का सबसे लंबा स्ट्रिंग)।
लोकलली बाउंडेड फंक्शन्स (Locally Bounded Functions): ऐसे प्रश्न जहाँ उत्तर बहुत अधिक नहीं बदलता भले ही संदेश थोड़ा अस्त-व्यस्त हो जाए।

निष्कर्ष:

उन्होंने प्रत्येक प्रश्न के लिए सही उत्तर सुनिश्चित करने के लिए आवश्यक न्यूनतम अतिरिक्त डेटा की गणना की।
उन्होंने पाया कि "रन कितने हैं?" जैसे प्रश्नों के लिए, आप पूरे संदेश को बचाने की तुलना में बहुत अधिक डेटा बचा सकते हैं।
उन्होंने गणितीय "फ्लोर" (floor) और "सीलिंग" (ceiling) सीमाएं प्रदान कीं ताकि इंजीनियरों को पता चल सके कि उनके कोड कितने कुशल हो सकते हैं।

यह क्यों महत्वपूर्ण है (लेखक के अनुसार)

लेखक विशेष रूप से दो क्षेत्रों पर प्रकाश डालते हैं जहाँ यह अत्यंत महत्वपूर्ण है:

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

सारांश

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

तकनीकी सारांश: इंसर्शन-डिलिशन (insertion-deletion) चैनलों के लिए फंक्शन-करेक्टिंग कोड्स

समस्या विवरण
पारंपरिक त्रुटि-सुधार कोड (ECCs) सटीक प्रसारित संदेश को पुनः प्राप्त करने के लिए डिज़ाइन किए गए हैं। हालाँकि, कई अनुप्रयोगों जैसे कि वितरित कंप्यूटिंग (distributed computing), आर्काइवल स्टोरेज और डीएनए डेटा स्टोरेज में, डिकोडर को अक्सर पूरे संदेश के पुनर्निर्माण के बजाय संदेश के एक विशिष्ट फलन (function) (जैसे कि चेकसम, सिंक्रोनाइज़ेशन मार्कर, या एक बाधा-संबंधी गुण) की आवश्यकता होती है। जबकि प्रतिस्थापन-आधारित मेट्रिक्स (हैमिंग, सिंबल-पेयर, ली) के लिए "फंक्शन-करेक्टिंग कोड्स" (FCCs) विकसित किए गए हैं, वे इस गुण पर निर्भर करते हैं कि दूरी व्यवस्थित विभाजनों (systematic splits) में योगात्मक (additive) होती है। यह गुण इंसर्शन-डिलिशन (insdel) चैनलों के लिए लागू नहीं होता है, जहाँ त्रुटियाँ प्रसारित अनुक्रमों के बीच संरेखण (alignment) को बाधित करती हैं। इंसडेल चैनलों में, संयोजित शब्दों (concatenated words) के बीच क्रॉस-ब्लॉक संरेखण (cross-block alignment) एक संयोजन की दूरी को कम कर सकता है, जिससे मानक FCC ढांचे अप्रभावी हो जाते हैं। यह शोध पत्र विशेष रूप से इंसडेल चैनलों के लिए अनुकूलित FCCs के लिए रेडंडेंसी (redundancy) को अनुकूलित करने की चुनौती को संबोधित करता है।

कार्यप्रणाली और ढांचा
लेखक फंक्शन-करेक्टिंग इंसडेल-डिस्टेंस कोड्स (FCIDCs) के लिए एक नया कोडिंग ढांचा प्रस्तावित करते हैं। मुख्य कार्यप्रणाली में शामिल हैं:

प्रारूपों की तुल्यता (Equivalence of Formulations): शोध पत्र फंक्शन-करेक्टिंग डिलीशन कोड, इंसर्शन कोड और इंसडेल कोड को परिभाषित करता है। यह सिद्ध करता है कि एक दिए गए फलन $f$ और त्रुटि सहनशीलता $t$ के लिए ये तीनों प्रारूप तुल्य हैं। विशेष रूप से, एक कोड अलग-अलग फलन मानों के अनुरूप कोडवर्ड्स के लिए $2t + 2$ की इंसडेल दूरी बनाए रखकर $t$ डिलीशन (या इंसर्शन) को ठीक कर सकता है।
क्रॉस-ब्लॉक संरेखण को संभालना: एक महत्वपूर्ण तकनीकी बाधा की पहचान की गई है कि व्यवस्थित एनकोडिंग $\psi(x) = (x, p(x))$ के लिए, इंसडेल दूरी $d_{ID}(\psi(x), \psi(y))$ संदेश और रेडंडेंसी भागों की दूरियों के योग से काफी कम हो सकती है, जो क्रॉस-ब्लॉक लॉन्गएस्ट कॉमन सब्सक्वेंस (LCS) प्रभावों के कारण होता है। लेखक यह सीमा (bound) व्युत्पन्न करते हैं:
$d_{ID}(\psi(x), \psi(y)) \geq d_{ID}(x, y) + d_{ID}(p(x), p(y)) - 2\min\{k, r\}$
जहाँ $k$ संदेश की लंबाई और $r$ रेडंडेंसी की लंबाई है।
अनियमित इंसडेल-डिस्टेंस कोड्स (Irregular Insdel-Distance Codes): गैर-योगात्मक प्रकृति के प्रबंधन के लिए, लेखक इंसडेल-डिस्टेंस मैट्रिसेस ( $I^{(1)}_f$ $I_{f}^{(1)}$ और $I^{(2)}_f$ $I_{f}^{(2)}$ ) और अनियमित इंसडेल-डिस्टेंस कोड्स को पेश करते हैं।
- टाइप 1 मैट्रिसेस ( $I^{(1)}_f$ ): $2t + 2 - d_{ID}(x, y)$ के आधार पर बाधाएं निर्धारित करते हैं।
- टाइप 2 मैट्रिसेस ( $I^{(2)}_f$ ): क्रॉस-ब्लॉक LCS हानि की भरपाई के लिए एक अतिरिक्त $+2k$ पद शामिल करते हैं।
  लेखक प्रदर्शित करते हैं कि गैर-तुच्छ (non-trivial) व्यवस्थित FCIDCs केवल उस शासन (regime) में ही संभव हैं जहाँ रेडंडेंसी $r \geq k$ है। यदि $r < k$ , तो संदेश वेक्टरों को स्वयं शास्त्रीय $t$ -इंसडेल कोड की बाधाओं को पूरा करना होगा, जिससे कोई रेडंडेंसी बचत नहीं मिलती है।
बाउंड्स का व्युत्पत्ति (Bounds Derivation): शोध पत्र $r^f_{ID}(k, t)$ $r_{I D}^{f} (k, t)$ और अनियमित इंसडेल-डिस्टेंस कोड्स की लघुतम प्राप्त करने योग्य लंबाई $N^{(1)}_{ID}$ $N_{I D}^{(1)}$ और $N^{(2)}_{ID}$ $N_{I D}^{(2)}$ के बीच संबंध स्थापित करता है। इस संबंध का उपयोग करते हुए, लेखक निम्नलिखित व्युत्पन्न करते हैं:
- प्लॉटकिन-जैसे बाउंड्स (Plotkin-like bounds): $d_H \geq \frac{1}{2}d_{ID}$ के संबंध का उपयोग करके हैमिंग मेट्रिक बाउंड्स से अनुकूलित।
- गिल्बर्ट-वरसाम-जैसे बाउंड्स (Gilbert-Varshamov-like bounds): सुपरसीक्वेंस तर्कों और रन-आधारित गणना का उपयोग करके व्युत्पन्न, यह स्वीकार करते हुए कि इंसडेल बॉल का आकार केंद्र-निर्भर होता है (हैमिंग स्पेस के समान एकसमान गोलों के विपरीत)।

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

एकीकृत ढांचा: FCIDCs की भूमिका और डिलीशन, इंसर्शन और संयुक्त इंसडेल सुधार के बीच समानता का प्रमाण।
सैद्धांतिक उपकरण: अनियमित इंसडेल-डिस्टेंस कोड्स और क्रॉस-ब्लॉक संरेखण हानि को ध्यान में रखने वाले डिस्टेंस मैट्रिसेस की परिभाषा, यह स्थापित करते हुए कि व्यवस्थित लाभ के लिए $r \geq k$ एक आवश्यक शर्त है।
सामान्य बाउंड्स: विशिष्ट फलन वर्गों के लिए सामान्य बाउंड्स सहित, किसी भी फलन के लिए इष्टतम रेडंडेंसी पर निचले और ऊपरी बाउंड्स का व्युत्पन्न।
विशिष्ट फलन विश्लेषण: इंसडेल मेट्रिक के लिए मूल चार फलन वर्गों पर इस ढांचे का अनुप्रयोग:
1. VT-सिंड्रोम फलन (VT-Syndrome Function): बिट पोजीशन के भारित योग (weighted sum) के लिए प्राप्त बाउंड्स।
2. रन-की-संख्या फलन (Number-of-Runs Function): समान प्रतीकों के अधिकतम निरंतर ब्लॉकों की गणना का विश्लेषण।
3. मैक्सिमम-रन-लेंथ फलन (Maximum-Run-Length Function): सबसे लंबे निरंतर ब्लॉक की लंबाई का विश्लेषण।
4. स्थानीय रूप से सीमित फलन (Locally Bounded Functions): इंसडेल मेट्रिक में स्थानीय $(\lambda, \rho)$ -फंक्शन अवधारणा का विस्तार।

परिणाम
शोध पत्र पहचाने गए फलन वर्गों के लिए FCIDCs की इष्टतम रेडंडेंसी के स्पष्ट निचले और ऊपरी बाउंड प्रदान करता है:

VT-सिंड्रोम: रेडंडेंसी $\frac{2tk}{k+1}$ और $k$ तथा $t$ के लॉगरिदमिक व्यंजक के बीच सीमित है।
नंबर-ऑफ-रन्स और मैक्सिमम-रन-लेंथ: लेखक $t$ के संदर्भ में क्यूबिक लोअर बाउंड्स (जैसे $\approx \frac{10t^3}{3(t+2)^2}$ ) और लॉगरिदमिक अपर बाउंड्स व्युत्पन्न करते हैं। विशेष रूप से, नंबर-ऑफ-रन्स फलन के लिए, एक समर्पित रेसिड्यू-क्लास निर्माण जेनेरिक लोकली-बाउंडेड दृष्टिकोण की तुलना में अधिक सटीक अपर बाउंड प्रदान करता है।
स्थानीय रूप से सीमित फलन: स्थानीय $(2, 2t)_{ID}$ फलनों के लिए, रेडंडेंसी $t$ और $t+1$ के बीच है। स्थानीय $(3, 2t)_{ID}$ फलनों के लिए, निचला बाउंड $\lceil 3t/2 \rceil$ है और ऊपरी बाउंड $2t+2$ है।

महत्व और दावे
शोध पत्र का दावा है कि यह कार्य प्रतिस्थापन-आधारित मेट्रिक्स से आगे बढ़कर अधिक चुनौतीपूर्ण इंसडेल मेट्रिक तक फंक्शन-करेक्टिंग कोड्स का विस्तार करके एक महत्वपूर्ण सैद्धांतिक मील का पत्थर है। इसका महत्व निम्नलिखित में निहित है:

एक मौलिक अंतराल को संबोधित करना: यह इस समस्या को हल करता है कि जब अंतर्निहित दूरी मेट्रिक व्यवस्थित विभाजनों के माध्यम से गैर-योगात्मक होती है, तो रेडंडेंसी को कैसे अनुकूलित किया जाए, एक ऐसी समस्या जो पिछले FCC पद्धतियों को अमान्य कर देती है।
व्यावहारिक प्रासंगिकता: इस ढांचे को डीएनए डेटा स्टोरेज और दस्तावेज़ विनिमय जैसे अनुप्रयोगों द्वारा प्रेरित किया गया है, जहाँ इंसर्शन और डिलीशन प्रमुख त्रुटि प्रकार हैं। इन परिदृश्यों में, पूरे स्ट्रैंड के बजाय विशिष्ट गुणों (जैसे रन-लेंथ या VT सिंड्रोम) को पुनः प्राप्त करना संश्लेषण लागत और रेडंडेंसी को काफी कम कर सकता है।
सैद्धांतिक कठोरता: अनियमित इंसडेल-डिस्टेंस कोड्स के लिए प्लॉटकिन और गिल्बर्ट-वरसाम प्रकार के बाउंड्स स्थापित करके, यह शोध पत्र सिंक्रोनाइज़ेशन-एरर चैनलों में भविष्य के कोड निर्माण और प्रदर्शन सीमाओं के लिए आधार तैयार करता है।

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