1. परिचय: सूचना पुनर्प्राप्ति के दो दैनिक किंतु अद्भुत इंजीनियरिंग चमत्कार
अंतरतारकीय अंतरिक्ष (interstellar space) की गहराइयों से लेकर आपके स्मार्टफोन के कैमरे तक, आधुनिक डिजिटल इंजीनियरिंग प्रतिदिन ऐसा कार्य करती है जो भौतिक अंतर्ज्ञान को चुनौती देता प्रतीत होता है: थर्मल शोर (thermal noise), खरोंच या भौतिक क्षति से बुरी तरह विकृत हो चुके सिग्नल या माध्यम से 100% बिट-सटीक डिजिटल जानकारी को पुनः प्राप्त करना।
चमत्कार 1: 24 अरब किलोमीटर दूर से $10^{-16}\text{ वाट}$ पर संचार करता वॉयेजर 1 और 2
1977 में प्रक्षेपित नासा के Voyager 1 और Voyager 2 अंतरिक्ष यानों ने बृहस्पति, शनि, यूरेनस और नेपच्यून की ऐतिहासिक तस्वीरें भेजीं और आज वे पृथ्वी से 24 अरब किलोमीटर से अधिक दूर अंतरतारकीय अंतरिक्ष में यात्रा कर रहे हैं। वॉयेजर के रेडियो ट्रांसमीटर की शक्ति मात्र $23\text{ वाट}$ है — जो घरेलू रेफ्रिजरेटर के बल्ब से भी कम है। जब यह संकेत पृथ्वी पर नासा के डीप स्पेस नेटवर्क (DSN) के 70-मीटर एंटीना तक पहुँचता है, तो प्राप्त शक्ति घटकर केवल $10^{-16}\text{ वाट}$ ($0.1\text{ एटोवाट}$) रह जाती है, जो पूरी तरह से थर्मल शोर (Johnson–Nyquist noise) में डूबी होती है। फिर भी, वॉयेजर ने शून्य बिट त्रुटि (Zero Bit Errors) के साथ ग्रहों के अत्यंत स्पष्ट रंगीन चित्र पृथ्वी पर पहुंचाए।
चमत्कार 2: कॉफी के दाग या कंपनी लोगो से $30\%$ ढका हुआ QR कोड
इसी प्रकार, जब आप किसी ऐसे QR कोड (Quick Response Code) को स्कैन करते हैं जिस पर कॉफी गिर गई हो या जिसके मध्य भाग का $30\%$ हिस्सा किसी ब्रांड लोगो से ढका हो, तो आपका स्मार्टफोन $10\text{ मिलीसेकंड}$ से भी कम समय में बिना किसी त्रुटि के सटीक URL या भुगतान डेटा निकाल लेता है।
flowchart TD
subgraph Voyager["गहन अंतरिक्ष टेलीमेट्री (Voyager 1 & 2)"]
V1["ग्रह चित्र डेटा (k बिट्स)"] --> V2["संयुक्त कोडिंग (बाहरी RS कोड + आंतरिक कन्वोल्यूशनल/LDPC कोड)"]
V2 --> V3["23 W ट्रांसमीटर → अरबों किमी प्रसार (10⁻¹⁶ W प्राप्त)"]
V3 --> V4["गाउसियन थर्मल शोर (AWGN) और बिट पलटाव"]
V4 --> V5["सॉफ्ट-डिसीजन विटरबी / बिलीफ प्रोपेगेशन + RS डिकोडिंग"]
V5 --> V6["स्पष्ट ग्रह चित्र (शून्य बिट त्रुटि)"]
end
subgraph QR["दैनिक QR कोड स्कैनिंग"]
Q1["URL / पेलोड डेटा (k बाइट्स)"] --> Q2["GF(2⁸) रीड-सोलोमन कोडिंग (n बाइट्स)"]
Q2 --> Q3["कॉफी दाग या लोगो से 30% मॉड्यूल नष्ट"]
Q3 --> Q4["सिंड्रोम गणना + बर्लेकैम्प-मैसी / यूक्लिडियन एल्गोरिदम"]
Q4 --> Q5["चिएन सर्च (Chien Search) + फोर्नी सूत्र (10 ms)"]
Q5 --> Q6["100% सटीक डेटा पुनर्निर्माण"]
end
यह गणितीय रूप से कैसे संभव है? इसका उत्तर क्लॉड शैनन के सूचना सिद्धांत (1948) और त्रुटि-सुधार कोड (Error-Correcting Codes, ECC) के बीजगणित में निहित है।
2. क्लॉड शैनन की 1948 की क्रांति और नॉइज़ी-चैनल कोडिंग प्रमेय
2.1 साधारण पुनरावृत्ति कोड (Repetition Code $0 \to 00000$) की विफलता
$$P_e^{(n)} = \sum_{i = (n+1)/2}^{n} \binom{n}{i} p^i (1-p)^{n-i}$$जब $n \to \infty$, तो $P_e^{(n)} \to 0$, किंतु साथ ही कोड दर भी शून्य हो जाती है: $R = k/n = 1/n \to 0$.
2.2 शैनन का प्रमेय और परम शैनन सीमा ($-1.59\,\text{dB}$)
1948 में, क्लॉड शैनन (Claude E. Shannon) ने “A Mathematical Theory of Communication” में अपना ऐतिहासिक प्रमेय सिद्ध किया:
$$\left(\frac{E_b}{N_0}\right)_{\min} = \ln 2 \approx 0.6931 \implies 10 \log_{10}(\ln 2) \approx \mathbf{-1.5917\,\text{dB}}$$प्रमेय (शैनन का नॉइज़ी-चैनल कोडिंग प्रमेय, 1948): प्रत्येक मेमोरीलेस चैनल की एक धनात्मक चैनल क्षमता (Channel Capacity) $C > 0$ होती है:
- बाइनरी सिमेट्रिक चैनल (BSC) के लिए बाइनरी एन्ट्रॉपी $H_2(p) = -p\log_2 p - (1-p)\log_2(1-p)$ के साथ: $$C_{\text{BSC}}(p) = 1 - H_2(p) = 1 + p\log_2 p + (1-p)\log_2(1-p) \quad [\text{bits / channel use}]$$
- बैंडविड्थ $B$, सिग्नल शक्ति $S$ और शोर $N = N_0 B$ वाले AWGN चैनल के लिए (शैनन-हार्टले प्रमेय): $$C_{\text{AWGN}} = B \log_2\!\left(1 + \frac{S}{N}\right) = B \log_2\!\left(1 + \frac{S}{N_0 B}\right) \quad [\text{bits / s}]$$
किसी भी सूचना दर $R < C$ के लिए, ब्लॉक लंबाई $n \to \infty$ होने पर ऐसे ब्लॉक कोड अस्तित्व में हैं जिनकी डिकोडिंग त्रुटि प्रायिकता $P_e \to 0$ हो जाती है!
3. रिचर्ड हैमिंग की 1950 की ज्यामितीय क्रांति: हैमिंग दूरी और $[7, 4, 3]$ परफेक्ट कोड
3.1 हैमिंग दूरी $d_H(\mathbf{u}, \mathbf{v})$ और गोला-पैकिंग सीमा (Sphere-Packing Bound)
$$d_H(\mathbf{u}, \mathbf{v}) \triangleq \bigl|\{ i \in \{1, \dots, n\} \mid u_i \neq v_i \}\bigr| = w_H(\mathbf{u} - \mathbf{v})$$न्यूनतम दूरी $d_{\min} = \min_{\mathbf{u}\neq\mathbf{v}} d_H(\mathbf{u},\mathbf{v})$ वाले कोड $\mathcal{C} \subset \mathbb{F}_q^n$ के लिए असंयुक्त हैमिंग गोलों की ज्यामिति सिद्ध करती है कि यह कोड:
- $d_{\min} - 1$ त्रुटियों की पहचान (Detection) कर सकता है;
- ज्ञात स्थानों पर $e = d_{\min} - 1$ मिटाव (Erasures) को सुधार सकता है;
- अज्ञात स्थानों पर $t = \lfloor(d_{\min} - 1)/2\rfloor$ त्रुटियों (Errors) को सुधार सकता है: $$\mathbf{d_{\min} \ge 2t + e + 1}, \qquad |\mathcal{C}| \cdot \sum_{i=0}^{t} \binom{n}{i} (q-1)^i \le q^n \quad \text{(हैमिंग सीमा)}$$
3.2 हैमिंग $(7,4)$ परफेक्ट कोड और सिंड्रोम डिकोडिंग
$$\mathbf{G}_{4\times 7} = \left(\begin{array}{cccc|ccc} 1 & 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 \end{array}\right), \qquad \mathbf{H}_{3\times 7} = \left(\begin{array}{cccc|ccc} 1 & 1 & 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 1 & 0 & 0 & 1 \end{array}\right)$$3-बिट सिंड्रोम $\mathbf{s} = \mathbf{H}\mathbf{y}^T = \mathbf{H}(\mathbf{c} + \mathbf{e})^T = \mathbf{H}\mathbf{e}^T \pmod 2$ सीधे $\mathbf{H}$ के उस स्तंभ को इंगित करता है जहाँ बिट पलटा है: यदि स्तंभों को $1$ से $7$ के बाइनरी क्रम में रखा जाए, तो सिंड्रोम $\mathbf{s}$ सीधे खराब बिट की बाइनरी इंडेक्स $(1 \dots 7)$ देता है! यही तकनीक आज सभी सर्वरों की ECC DRAM मेमोरी की रक्षा करती है।
4. रीड और सोलोमन की 1960 की उत्कृष्ट कृति: गैलोइस फील्ड $\mathbb{F}_{2^m}$ पर रीड-सोलोमन (RS) कोड
4.1 गैलोइस फील्ड $\text{GF}(2^8)$ और बर्स्ट त्रुटियों (Burst Errors) से सुरक्षा
लगातार कई बिट्स को नष्ट करने वाली बर्स्ट त्रुटियों (डिस्क पर खरोंच, QR कोड पर दाग) को हराने के लिए इरविंग रीड और गुस्ताव सोलोमन (1960) ने प्रत्येक बाइट ($m=8$ बिट्स) को परिमित क्षेत्र $\text{GF}(2^8) = \mathbb{F}_2[x]/(x^8 + x^4 + x^3 + x^2 + 1)$ के एक एकल प्रतीक (symbol) के रूप में बांधा। यदि एक बाइट के सभी 8 बिट्स भी नष्ट हो जाएं, तो भी $\text{GF}(2^8)$ में वह केवल एक प्रतीक त्रुटि है!
4.2 बहुपद अंतर्वेशन (Polynomial Interpolation) और MDS सिंगलटन सीमा $d_{\min} = n - k + 1$
$$\mathbf{d_{\min} = n - k + 1 \implies 2t + e \le n - k}$$इस प्रकार, $n - k$ पैरिटी बाइट्स $e = n - k$ मिटाव (RAID-6, क्लाउड स्टोरेज) या अज्ञात स्थानों पर $t = \lfloor(n-k)/2\rfloor$ बाइट त्रुटियों (QR कोड लेवल H में 30% क्षति; वॉयेजर का $[255, 223]$ कोड) को जनरेटर बहुपद $g(x) = \prod_{i=1}^{2t}(x - \alpha^i)$, बर्लेकैम्प-मैसी / यूक्लिडियन एल्गोरिदम ($\Lambda(x)S(x) \equiv \Omega(x) \pmod{x^{2t}}$), चिएन सर्च और फोर्नी सूत्र द्वारा पूरी तरह सुधार लेते हैं।
5. शैनन सीमा के करीब: LDPC कोड (1962), टर्बो कोड (1993) और पोलर कोड (2009)
- रॉबर्ट गैलेगर के LDPC कोड (1962): विरल (sparse) मैट्रिक्स $\mathbf{H}$ और द्विदलीय टैनर ग्राफ (Tanner Graph) पर आधारित हैं। सॉफ्ट लॉग-लाइकलीहुड अनुपात $L(c_i) = \ln\frac{P(c_i=0|y_i)}{P(c_i=1|y_i)}$ के बिलीफ प्रोपेगेशन (Sum-Product) द्वारा LDPC कोड शैनन सीमा के $0.0045\,\text{dB}$ के भीतर कार्य करते हैं (5G NR डेटा चैनल, Wi-Fi 6/7, और 3D NAND SSDs)।
- एरदाल अरिकन के पोलर कोड (Polar Codes, 2009): क्रोनेकर रूपांतरण $\mathbf{G}_N = \mathbf{B}_N \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix}^{\otimes m}$ के पुनरावर्ती प्रयोग से चैनल ध्रुवीकरण (Channel Polarization) होता है — $N \to \infty$ पर $C = I(W)$ अनुपात के उप-चैनल क्षमता $1$ (शोर-रहित, सूचना बिट्स) की ओर और $1 - C$ अनुपात क्षमता $0$ (फ़्रोज़न बिट्स / Frozen Bits $= 0$) की ओर अभिसरित होते हैं। यह $O(N \log N)$ जटिलता में शैनन क्षमता को गणितीय रूप से सिद्ध करने वाला पहला कोड है (5G NR कंट्रोल चैनल)।
flowchart TD
subgraph CapHI["शैनन क्षमता प्राप्त करने वाले आधुनिक कोड"]
L1["LDPC कोड (विरल द्विदलीय टैनर ग्राफ)"] --> L2["सॉफ्ट LLR संदेशों का पुनरावर्ती आदान-प्रदान"]
L2 --> L3["Sum-Product बिलीफ प्रोपेगेशन (शैनन सीमा से 0.0045 dB दूर)"]
P1["पोलर कोड (क्रोनेकर रूपांतरण G_N = B_N F^{⊗m})"] --> P2["चैनल ध्रुवीकरण: W⁻ (क्षीण) और W⁺ (उन्नत) उप-चैनल"]
P2 --> P3["अनुपात C → क्षमता 1 (डेटा बिट्स), अनुपात 1-C → क्षमता 0 (फ़्रोज़न बिट्स)"]
end
प्रमुख त्रुटि-सुधार कोड परिवारों की तुलना तालिका
| कोड परिवार | वर्ष और प्रणेता | गणितीय आधार | मुख्य डिकोडिंग एल्गोरिदम | मुख्य विशेषता | प्रमुख व्यावहारिक अनुप्रयोग |
|---|---|---|---|---|---|
| हैमिंग / SECDED | 1950 R. Hamming | $\mathbb{F}_2^n$ गोला पैकिंग | सिंड्रोम $\mathbf{s}=\mathbf{H}\mathbf{y}^T$ ($O(1)$) | $<1\text{ ns}$ में एकल बिट सुधार | ECC DRAM सर्वर मेमोरी, CPU कैश |
| रीड-सोलोमन (RS) | 1960 Reed & Solomon | $\mathbb{F}_{2^m}$ पर बहुपद अंतर्वेशन | बर्लेकैम्प-मैसी + चिएन + फोर्नी | बर्स्ट त्रुटियों के विरुद्ध इष्टतम MDS $d_{\min}=n-k+1$ | QR कोड, RAID-6, क्लाउड स्टोरेज, वॉयेजर |
| LDPC कोड | 1962 R. Gallager (1996 पुनः खोज) | विरल मैट्रिक्स $\mathbf{H}$ व टैनर ग्राफ | बिलीफ प्रोपेगेशन (Sum-Product) | शैनन सीमा के $0.0045\,\text{dB}$ के भीतर | 5G NR (डेटा), Wi-Fi 6/7, NVMe SSD |
| पोलर कोड (Polar) | 2009 Erdal Arıkan | क्रोनेकर घात $\mathbf{F}^{\otimes m}$ | CA-SCL लिस्ट डिकोडिंग ($O(N\log N)$) | गणितीय रूप से शैनन क्षमता $C$ प्राप्त | 5G NR (कंट्रोल), 6G IoT |
6. संपूर्ण Python कार्यान्वयन: हैमिंग $(7,4)$ और $\text{GF}(2^8)$ रीड-सोलोमन
| |
7. निष्कर्ष
शैनन की $-1.59\,\text{dB}$ सीमा (1948) से लेकर हैमिंग की ज्यामिति (1950), गैलोइस फील्ड $\mathbb{F}_{2^m}$ पर रीड-सोलोमन के बहुपद अंतर्वेशन (1960), और गैलेगर के LDPC बिलीफ प्रोपेगेशन तथा अरिकन के पोलर कोड्स तक — कोडिंग सिद्धांत यह सिद्ध करता है कि शुद्ध गणित किस प्रकार ब्रह्मांड के थर्मल शोर और भौतिक एन्ट्रॉपी पर विजय प्राप्त करता है।