🔢 mathematics

Capacity-Achieving Codes for Noisy Insertion Channels

यह शोध पत्र डीएनए स्टोरेज से संबंधित एक शोर वाले इंसर्शन चैनल (noisy insertion channel) की जांच करता है, जहाँ यह कोडिंग क्षमता का निर्धारण करता है और एक एकल यादृच्छिक इंसर्शन के साथ कई समान या पूरक इंसर्शन को संभालने में सक्षम स्पर्शोन्मुख रूप से इष्टतम त्रुटि-सुधार कोड (asymptotically optimal error-correcting codes) का निर्माण करता है।

मूल लेखक: Hengfeng Liu, Chunming Tang, Cuiling Fan

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

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

CC BY 4.0

मूल लेखक: Hengfeng Liu, Chunming Tang, Cuiling Fan

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

कल्पना कीजिए कि आप एक विशेष भाषा (DNA) में लिखा गया एक गुप्त संदेश एक बहुत ही अराजक, शोर-शराबे वाली नदी के पार भेजने की कोशिश कर रहे हैं।

परिवेश: द DNA रिवर (DNA की नदी)

DNA डेटा स्टोरेज की दुनिया में, हम सूचना की विशाल मात्रा को DNA के सूक्ष्म धागों के भीतर संग्रहीत करना चाहते हैं। यह एक रेत के कण पर लाइब्रेरी लिखने जैसा है। लेकिन, ठीक वैसे ही जैसे कागज के टुकड़े पर लिखा गया संदेश बहती नदी में बह सकता है, आपका संदेश भी गड़बड़ हो सकता है।

इस विशिष्ट नदी में, "धारा" (current) तीन मुख्य प्रकार का कोलाहल पैदा करती है:

"मिरर" ग्लिच (कॉम्प्लीमेंट इंसर्शन): कभी-कभी, नदी पिछले अक्षर का "दर्पण प्रतिबिंब" (mirror image) वाला एक अक्षर जोड़ देती है। यदि आपके पास 'A' है, तो नदी उसके ठीक बगल में उसका साथी 'T' जोड़ सकती है।
"इको" ग्लिच (टैंडम डुप्लिकेशन): कभी-कभी, नदी अटक जाती है और एक अक्षर को दोहरा देती है। यदि आपके पास 'C' है, तो यह अचानक 'CC' बन सकता है।
"रैंडम स्प्लैश" (रैंडम इंसर्शन): कभी-कभी, एक यादृच्छिक पत्थर (एक रैंडम अक्षर) धारा में छपाक कर देता है, जिससे एक पूरी तरह से अप्रत्याशित अक्षर जुड़ जाता है जो पैटर्न में फिट नहीं बैठता।

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

समाधान: द "सिग्नेचर" फ़िल्टर

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

संदेश को मोतियों की एक माला के रूप में सोचें।

यदि आप एक "मिरर" मोती या एक "इको" मोती जोड़ते हैं, तो यह स्ट्रिंग में एक डुप्लिकेट या मिलान करने वाले जोड़े को जोड़ने जैसा है।
यदि आप स्ट्रिंग को "कोलैप्स" (collapse) करते हैं—यानी सभी समान या मिलान करने वाले मोतियों को एक साथ सिकोड़ देते हैं—तो आप वापस मूल पैटर्न प्राप्त कर लेते हैं।

वे इस कोलैप्स्ड पैटर्न को "सिग्नेचर" कहते हैं।

उपमा: कल्पना कीजिए कि आपका संदेश एक गाना है।

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

जादुई ट्रिक: द कोड

शोधकर्ताओं ने संदेश के लिए एक विशेष "लिफाफा" (एक कोड) बनाया है। इस लिफाफे के पास दो महाशक्तियाँ हैं:

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

परिणाम: परफेक्ट रिकवरी

यह पेपर दो अद्भुत चीजें सिद्ध करता है:

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

यह क्यों महत्वपूर्ण है

यह केवल गणितीय पहेली नहीं है। यह DNA स्टोरेज को वास्तविकता बनाने की कुंजी है।

वर्तमान समस्या: DNA स्टोरेज के लिए बेहतरीन है, लेकिन यह नाजुक है। जब हम इसे वापस पढ़ने की कोशिश करते हैं, तो त्रुटियां होती हैं।
ब्रेकथ्रू: यह पेपर हमें ऐसे DNA स्टोरेज सिस्टम बनाने का ब्लूप्रिंट देता है जो जैविक वास्तविकता की अव्यवस्था को संभालने के लिए पर्याप्त मजबूत हो। यह हमें बताता है कि हम इस कोलाहल के बावजूद विश्वसनीय रूप से डेटा स्टोर कर सकते हैं, और हम इसे कुशलतापूर्वक कर सकते हैं।

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

यहाँ Liu, Tang, और Fan के शोध पत्र "Capacity-Achieving Codes for Noisy Insertion Channels" का विस्तृत तकनीकी सारांश दिया गया है।

1. समस्या विवरण (Problem Statement)

यह शोध पत्र DNA-आधारित डेटा स्टोरेज के लिए त्रुटि-सुधार कोड (error-correcting codes - ECCs) डिजाइन करने की चुनौती को संबोधित करता है, जो विशेष रूप से नॉइज़ी इंसर्शन चैनल्स (noisy insertion channels) पर केंद्रित है।

संदर्भ: DNA स्टोरेज संश्लेषण (synthesis), अनुक्रमण (sequencing), और जैविक संरक्षण के दौरान विशिष्ट प्रकार की त्रुटियों के प्रति संवेदनशील होता है। जबकि पारंपरिक इंसर्शन/डिलेशन (indel) त्रुटियाँ अच्छी तरह से अध्ययन की गई हैं, DNA स्टोरेज अद्वितीय त्रुटि तंत्र पेश करता है:
- कॉम्प्लीमेंट इंसर्शन (Complement Insertion): मूल प्रतीक का रासायनिक पूरक (chemical complement) प्रतीक का इंसर्शन (जैसे, A $\leftrightarrow$ T, C $\leftrightarrow$ G)।
- 1-टैंडम डुप्लिकेशन (1-Tandem Duplication): मूल प्रतीक के ठीक बाद एक ही समान प्रतीक का इंसर्शन।
- रैंडम इंसर्शन (Random Insertion): जैविक शोर के कारण, इंसर्ट किए गए प्रतीक वर्णमाला (alphabet) से यादृच्छिक (random) प्रतीकों में उत्परिवर्तित (mutate) हो सकते हैं।
अंतराल (The Gap): पिछले कार्यों (जैसे, Yohananov और Schwartz) ने सटीक कॉम्प्लीमेंट इंसर्शन को संबोधित किया था लेकिन एक शोर-मुक्त (noise-free) वातावरण माना था। वास्तविक दुनिया के DNA स्टोरेज में "नॉइज़ी" इंसर्शन शामिल होते हैं जहाँ कॉम्प्लीमेंट इंसर्शन या डुप्लिकेशन्स के साथ रैंडम सब्स्टिट्यूशन या रैंडम इंसर्शन भी हो सकते हैं।
उद्देश्य: लेखकों का लक्ष्य है:
1. एक नॉइज़ी इंसर्शन चैनल मॉडल को औपचारिक रूप देना, जो अनिश्चित संख्या में कॉम्प्लीमेंट इंसर्शन और 1-टैंडम डुप्लिकेशन, साथ ही अधिकतम एक रैंडम इंसर्शन की अनुमति देता है।
2. इस चैनल की कोडिंग क्षमता (coding capacity) (एसिम्प्टोटिक रेट) निर्धारित करना।
3. ऐसे कोड बनाना जो लीनियर-टाइम डिकोडिंग (linear-time decoding) के साथ इस क्षमता को प्राप्त करते हैं।

2. कार्यप्रणाली (Methodology)

लेखक सिग्नेचर-आधारित कोडिंग (signature-based coding), कन्स्ट्रेंड कोडिंग (constrained coding), और एल्जेब्रिक कोडिंग थ्योरी के संयोजन का उपयोग करते हैं।

A. चैनल मॉडलिंग और परिभाषाएँ (Channel Modeling and Definitions)

वर्णमाला (Alphabet): $\mathbb{Z}_q$ (जहाँ $q \ge 4$ सम है), जिसमें एक कॉम्प्लीमेंट ऑपरेशन $\bar{u} = q - 1 - u$ के रूप में परिभाषित है।
डिसेंडेंट कोन्स (Descendant Cones):
- $D^*_{ct}(x)$ : उन अनुक्रमों का सेट जो अनिश्चित कॉम्प्लीमेंट इंसर्शन और 1-टैंडम डुप्लिकेशन के माध्यम से प्राप्त होते हैं।
- $D^*_{ct}^{(\le 1)}(x)$ : "नॉइज़ी डिसेंडेंट कोन", जिसमें उपरोक्त के साथ अधिकतम एक रैंडम इंसर्शन शामिल है।
सिग्नेचर ( $\sigma(x)$ ): एक प्रमुख अवधारणा जहाँ एक अनुक्रम को लगातार समान या पूरक प्रतीकों को संक्षिप्त (collapse) करके कम किया जाता है। उदाहरण के लिए, $\mathbb{Z}_4$ $Z_{4}$ में जहाँ $\bar{0}=3, \bar{1}=2$ $\overset{ˉ}{0} = 3, \overset{ˉ}{1} = 2$ है, अनुक्रम $0312130 $घटकर सिग्नेचर$ $घटकरसिग्नेचर$ 013$ बन जाता है।
- मुख्य गुण: कॉम्प्लीमेंट इंसर्शन और 1-टैंडम डुप्लिकेशन अनुक्रम के सिग्नेचर को बदलते नहीं हैं। केवल रैंडम इंसर्शन ही सिग्नेचर को बदलते हैं।

B. कोड निर्माण रणनीति (Code Construction Strategy)

निर्माण इरिड्यूसिबल सीक्वेंस (irreducible sequences) ($Irr(n)$) के सेट पर प्रतिबंध लगाने पर आधारित है, जहाँ कोई भी दो आसन्न (adjacent) प्रतीक कॉम्प्लीमेंट या समान नहीं होते हैं। यह सुनिश्चित करता है कि कोडवर्ड का सिग्नेचर स्वयं वह कोडवर्ड ही हो ( $\sigma(x) = x$ )।

लेखक सिग्नेचर में विभिन्न त्रुटि प्रकारों को संभालने के लिए तीन विशिष्ट सब-कोड के प्रतिच्छेदन (intersection) द्वारा अंतिम कोड का निर्माण करते हैं:

रैंडम सब्स्टिट्यूशन (पॉइंट सब्स्टिट्यूशन) को संभालना:
- एक संशोधित Varshamov-Tenengolts (VT) जैसे कोड ( $C(a,b)(n)$ ) का उपयोग करता है।
- प्रतिबंध: प्रतीकों का योग $\equiv a \pmod{2q}$ और भारित योग (weighted sum) $\equiv b \pmod{qn}$ ।
- कार्य: सिग्नेचर में एक कॉम्प्लीमेंट प्रतीक के रैंडम इंसर्शन के कारण होने वाले सिंगल पॉइंट सब्स्टिट्यूशन को ठीक करता है।
पॉइंट इंसर्शन को संभालना:
- $2q$ के मॉडुलस के साथ एक संशोधित VT कोड ( $C_T(c,d)(n)$ ) का उपयोग करता है।
- कार्य: सिग्नेचर में एक सिंगल पॉइंट इंसर्शन को ठीक करता है।
बर्स्ट इंसर्शन (लंबाई 2) को संभालना:
- रैंडम इंसर्शन कभी-कभी सिग्नेचर में लंबाई 2 का "बर्स्ट" उत्पन्न कर सकते हैं।
- लेखक कोडवर्ड को $2 \times (n/2)$ ऐरे (array) में मैप करते हैं।
- रो 1 (Row 1): अधिकतम रन लेंथ को सीमित करने के लिए रन-लेंथ लिमिटेड (RLL) प्रतिबंध के साथ एनकोड किया गया है, जिससे यह सुनिश्चित होता है कि डिलीशन लोकेशन सीमित रहे।
- रो 2 (Row 2): एक शिफ्टेड VT (SVT) कोड ($SVT(e,f,g) $) के साथ एनकोड किया गया है, जो एक$ P$-बाउंडेड सिंगल-डिलेशन-करेक्टिंग कोड है।
- कार्य: सिग्नेचर में लंबाई 2 के बर्स्ट इंसर्शन को ठीक करता है।

अंतिम निर्माण: कोड $C_F$ , इरिड्यूसिबल सेट, RLL-कन्स्ट्रेंड सेट और उपरोक्त तीन एल्जेब्रिक प्रतिबंधों का प्रतिच्छेदन है।

C. डिकोडिंग एल्गोरिदम (Decoding Algorithm)

डिकोडिंग प्रक्रिया को लीनियर टाइम $O(N)$ के लिए डिज़ाइन किया गया है, जहाँ $N$ प्राप्त अनुक्रम की लंबाई है:

सिग्नेचर रिकवरी: प्राप्त अनुक्रम $y$ को उसके सिग्नेचर $r = \sigma(y)$ में संक्षिप्त करें। यह संभावित रूप से लंबे अनुक्रम $y$ (अनिश्चित इंसर्शन के कारण) को लगभग $n$ लंबाई के छोटे अनुक्रम $r$ में संकुचित करता है।
त्रुटि वर्गीकरण (Error Classification): $r$ $r$ की लंबाई के आधार पर:
- यदि $|r| = n+1$ : यह पॉइंट इंसर्शन को दर्शाता है। VT डिकोडर का उपयोग करें।
- यदि $|r| = n+2$ : यह बर्स्ट इंसर्शन को दर्शाता है। $2 \times \dots$ ऐरे पर SVT डिकोडर का उपयोग करें।
- यदि $|r| = n$ : यह सब्स्टिट्यूशन को दर्शाता है। त्रुटि की पहचान करने और उसे ठीक करने के लिए सिंड्रोम गणना (syndrome calculation) का उपयोग करें।
रिकवरी: सिग्नेचर की अद्वितीय रिकवरी मूल कोडवर्ड को अनन्य रूप से निर्धारित करती है।

3. मुख्य परिणाम (Key Results)

A. कोडिंग क्षमता (Coding Capacity)

यह शोध पत्र नॉइज़ी इंसर्शन चैनल के लिए सटीक कोडिंग क्षमता स्थापित करता है:
$\text{cap}^{\text{noisy}}_q = \log_q(q - 2)$

महत्व: यह परिणाम सटीक कॉम्प्लीमेंट इंसर्शन चैनल (बिना रैंडम नॉइज़ के) की क्षमता के समान है।
निहितार्थ: अतिरिक्त रैंडम इंसर्शन त्रुटि (और 1-टैंडम डुप्लिकेशन्स) को ठीक करने से शून्य एसिम्प्टोटिक रेट पेनल्टी (zero asymptotic rate penalty) लगती है। शोर-मुक्त कॉम्प्लीमेंट चैनल की तुलना में "नॉइज़" घटक की उपस्थिति से क्षमता कम नहीं होती है।

B. कोड का आकार और इष्टतमता (Code Size and Optimality)

निर्मित कोड एसिम्प्टोटिक रूप से इष्टतम (asymptotically optimal) हैं।
कोड के आकार $|C_F|$ का निचला स्तर (lower bound) लगभग है:
$|C_F| \ge \frac{q(q-2)^{n-1}}{4 n^3 (3 \log_q n + 4) q^3}$
रेडंडेंसी (Redundancy) $O(\log_q n)$ है, जिसका अर्थ है कि जैसे-जैसे $n \to \infty$ होता है, दर $\log_q(q-2)$ के करीब पहुँच जाती है।

C. जटिलता (Complexity)

डिकोडिंग एल्गोरिदम प्राप्त अनुक्रम की लंबाई $N$ के संबंध में स्ट्रिक्टली लीनियर टाइम $O(N)$ में चलता है। यह व्यावहारिक DNA स्टोरेज अनुप्रयोगों के लिए महत्वपूर्ण है जहाँ रीड लेंथ (read lengths) बहुत बड़ी हो सकती है।

4. महत्व और योगदान (Significance and Contributions)

यथार्थवादी चैनल मॉडलिंग: यह शोध पत्र अनिश्चित कॉम्प्लीमेंट इंसर्शन चैनल में बायोकेमिकल शोर (रैंडम इंसर्शन) को शामिल करके आदर्श मॉडलों से आगे बढ़ता है, जिससे इसके परिणाम वास्तविक दुनिया के DNA स्टोरेज सिस्टम के लिए अधिक लागू योग्य हो जाते हैं।
क्षमता लक्षण वर्णन (Capacity Characterization): यह एक विरोधाभासी परिणाम सिद्ध करता है: अनिश्चित संख्या में कॉम्प्लीमेंट इंसर्शन वाले चैनल में एक रैंडम इंसर्शन त्रुटि जोड़ने से सैद्धांतिक सूचना ट्रांसमिशन दर कम नहीं होती है।
व्यावहारिक निर्माण: कई गैर-रचनात्मक (non-constructive) क्षमता-प्राप्त प्रमाणों के विपरीत, यह शोध पत्र एक स्पष्ट कोड निर्माण (explicit code construction) और एक लीनियर-टाइम डिकोडिंग एल्गोरिदम प्रदान करता है।
सामान्यीकरण (Generalization): यह कार्य सटीक कॉम्प्लीमेंट इंसर्शन चैनल और टैंडम डुप्लिकेशन चैनल्स के पिछले परिणामों को एक नॉइज़ी फ्रेमवर्क के तहत एकीकृत करता है।

5. भविष्य की दिशाएँ (Future Directions)

लेखक दो खुले प्रश्न प्रस्तावित करते हैं:

मॉडल को $p$ रैंडम इंसर्शन की अनुमति देने के लिए विस्तारित करना (यह अनुमान लगाते हुए कि क्षमता $\log_q(q-2)$ बनी रहती है)।
कॉम्प्लीमेंट इंसर्शन और रैंडम शोर के साथ लंबाई $>1$ के टैंडम डुप्लिकेशन्स (विशेष रूप से लंबाई 3 तक) को संभालना।

संक्षेप में, यह शोध पत्र जटिल, नॉइज़ी इंसर्शन त्रुटियों के अधीन DNA सिस्टम में विश्वसनीय डेटा स्टोरेज के लिए एक कठोर सैद्धांतिक आधार और एक व्यावहारिक इंजीनियरिंग समाधान प्रदान करता है।