त्रुटि-सुधार कोड समझाए गए

कोई भी चैनल पूर्ण नहीं होता। कॉस्मिक किरणें मेमोरी में बिट पलट देती हैं, खरोंचें डिस्क के हिस्से मिटा देती हैं, और रेडियो सिग्नल कमज़ोर पड़ जाते हैं। अच्छे की उम्मीद करने के बजाय डिजिटल सिस्टम चतुराई से अतिरिक्तता जोड़ते हैं, ताकि प्राप्तकर्ता यह पता लगा सके कि क्या भेजा गया था, भले ही उसका कुछ हिस्सा गलत पहुँचे। 1940 के दशक के अंत में शुरू हुआ इन कोडों का गणित चुपचाप लगभग हर उस बिट की रक्षा करता है जिसे हम संग्रहीत करते हैं या भेजते हैं।

एक-दूसरे पर चढ़े तीन वृत्त जिनमें हैमिंग कोडवर्ड के सात बिट हैं, और जहाँ पैरिटी जाँच विफल होती है वह एक वृत्त हाइलाइट किया गया है
एक-दूसरे पर चढ़े तीन वृत्त जिनमें हैमिंग कोडवर्ड के सात बिट हैं, और जहाँ पैरिटी जाँच विफल होती है वह एक वृत्त हाइलाइट किया गया है

पैरिटी से त्रुटियाँ पकड़ना

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

पुनरावृत्ति से सुधार

दोबारा माँगे बिना त्रुटि सुधारने के लिए प्राप्तकर्ता को इतनी अतिरिक्तता चाहिए कि वह मतदान से त्रुटि को हरा सके। हर बिट तीन बार भेजने पर, 000 या 111, प्राप्तकर्ता बहुमत ले सकता है: तिकड़ी में एक पलटाव सुधर जाता है। कीमत भारी है: डेटा के हर बिट के लिए तीन बिट, और एक ही तिकड़ी में दो पलटाव फिर भी जीत जाते हैं। कोडिंग सिद्धांत की शुरुआत इसी प्रश्न से हुई कि क्या इससे बेहतर किया जा सकता है।

हैमिंग का कोड

1947 में रिचर्ड हैमिंग बेल लैब्स में एक रिले कंप्यूटर पर काम करते थे जो पंच कार्डों से प्रोग्राम पढ़ता था। सप्ताहांत में त्रुटि मिलने पर वह बस रुक जाता था, और सोमवार को लौटकर हैमिंग को बेकार गए काम मिलते थे। उन्होंने पूछा, अगर मशीन त्रुटि पकड़ सकती है, तो वह उसे ढूँढ़कर सुधार क्यों नहीं सकती? 1950 में प्रकाशित उनका उत्तर 4 डेटा बिट को 7 के रूप में भेजता है। स्थान 1, 2 और 4 पर स्थित तीन पैरिटी बिटों में से हर एक स्थानों के एक अलग, एक-दूसरे पर चढ़े समूह की जाँच करता है, जिन्हें इस तरह चुना गया है कि हर एकल त्रुटि जाँचों के एक अनूठे संयोजन को तोड़े।

सिंड्रोम

प्राप्तकर्ता तीनों जाँचों की फिर से गणना करता है। अगर सभी सफल हों, तो शब्द स्वीकार कर लिया जाता है। अगर कुछ विफल हों, तो विफल जाँचों को बाइनरी अंकों के रूप में लिखने पर, जाँच 4 को सबसे ऊँचा अंक मानकर, 1 से 7 तक की एक संख्या मिलती है: सिंड्रोम, जो ठीक पलटे गए बिट का स्थान है। उसे वापस पलटने से कोडवर्ड बहाल हो जाता है। यह तरकीब इसलिए काम करती है क्योंकि स्थानों को इस तरह क्रमांकित किया गया है कि हर स्थान का बाइनरी विस्तार उन जाँचों की सूची देता है जिनसे वह जुड़ा है, और इसीलिए तीन एक-दूसरे पर चढ़े वृत्तों के रूप में बनाने पर यह कोड इतना सुव्यवस्थित दिखता है।

हैमिंग दूरी

दो शब्दों के बीच की हैमिंग दूरी उन स्थानों की संख्या है जहाँ वे अलग हैं। (7,4) कोड में कोई भी दो कोडवर्ड कम से कम 3 की दूरी पर होते हैं। एक त्रुटि वाला शब्द भेजे गए कोडवर्ड से अब भी 1 की दूरी पर होता है और बाकी हर कोडवर्ड से कम से कम 2 की दूरी पर, इसलिए सबसे निकट कोडवर्ड में डिकोड करने से वह सुधर जाता है। सामान्य रूप से, जिस कोड के कोडवर्ड कम से कम d की दूरी पर हों, वह d − 1 त्रुटियाँ पकड़ता है और उनमें से (d − 1)/2 को, नीचे की ओर पूर्णांकित करके, सुधारता है। एक समग्र पैरिटी बिट जोड़ने से दूरी 4 हो जाती है, जिससे वह विस्तारित कोड बनता है जो एक त्रुटि सुधारता है और दो पकड़ता है।

शैनन की सीमा

1948 में, हैमिंग के शोधपत्र से दो साल पहले, क्लॉड शैनन ने एक चौंकाने वाला प्रमेय सिद्ध किया। हर शोर वाले चैनल की एक क्षमता होती है, और पर्याप्त लंबे कोडों का उपयोग करके उससे कम किसी भी दर पर डेटा को जितनी चाहें उतनी कम त्रुटियों के साथ भेजा जा सकता है; उससे ऊपर त्रुटियों से बचा नहीं जा सकता। शैनन ने दिखाया कि ऐसे कोड मौजूद हैं, पर यह नहीं कि उन्हें कैसे बनाया जाए। उनकी सीमा के करीब पहुँचने वाले व्यावहारिक कोड खोजने में आधी सदी लगी, 1960 के रीड-सोलोमन कोड से लेकर 1993 के टर्बो कोड और लो-डेंसिटी पैरिटी-चेक कोड की पुनर्खोज तक।

क्लॉड शैनन, जिन्होंने 1948 में बेल लैब्स में यह स्पष्ट किया कि किसी संदेश में कितनी सूचना होती है, और उसे बिट्स में मापा।
क्लॉड शैनन, जिन्होंने 1948 में बेल लैब्स में यह स्पष्ट किया कि किसी संदेश में कितनी सूचना होती है, और उसे बिट्स में मापा।

हमारे चारों ओर कोड

रीड-सोलोमन कोड की बदौलत CD खरोंचों के बावजूद चलती हैं और QR कोड चिह्न का 30% तक हिस्सा खराब होने पर भी स्कैन हो जाते हैं। सर्वर मेमोरी कॉस्मिक किरणों से पलटे एकल बिटों को ठीक करने के लिए विस्तारित हैमिंग कोड का उपयोग करती है। वॉयजर की बाहरी ग्रहों की तस्वीरों को गोले और बाद में रीड-सोलोमन कोड से सुरक्षित किया गया था, और 5G व Wi-Fi के LDPC और पोलर कोड चैनल द्वारा अनुमत लगभग हर बिट का लाभ उठा लेते हैं। यहाँ तक कि किसी किताब पर छपा बारकोड और बैंक खाता संख्या का आखिरी अंक भी सरल त्रुटि-पहचान कोड हैं।

खुद आज़माएँ

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

अक्सर पूछे जाने वाले प्रश्न

त्रुटि पहचान और त्रुटि सुधार में क्या अंतर है?

पहचान प्राप्तकर्ता को केवल यह बताती है कि कुछ गलत है, इसलिए उसे डेटा दोबारा माँगना पड़ता है; पैरिटी बिट या चेकसम यही करते हैं। सुधार प्राप्तकर्ता को बिना माँगे मूल डेटा फिर से बनाने देता है, जिसके लिए अधिक अतिरिक्तता चाहिए। जो सिस्टम दोबारा नहीं माँग सकते, जैसे लाखों किलोमीटर दूर कोई अंतरिक्ष यान या कोई DVD, वे सुधार पर निर्भर रहते हैं।

सब कुछ बस दो बार क्यों न भेजा जाए?

दो प्रतियाँ दिखाती हैं कि त्रुटि हुई है, पर यह नहीं कि कौन-सी प्रति सही है, और वे लागत दोगुनी कर देती हैं। तीन प्रतियाँ बहुमत से फ़ैसला करने देती हैं, पर लागत तिगुनी कर देती हैं। हैमिंग का कोड दोगुने से कम बिटों के साथ सात बिट के हर ब्लॉक में एक त्रुटि सुधारता है, और लंबे कोड इससे कहीं बेहतर करते हैं।

रिचर्ड हैमिंग कौन थे?

एक अमेरिकी गणितज्ञ (1915–1998), जिन्होंने मैनहट्टन परियोजना पर और फिर तीस वर्षों तक बेल लैब्स में काम किया। अपने कोडों के अलावा वे सिग्नल प्रोसेसिंग में हैमिंग विंडो, हैमिंग दूरी और अपने व्याख्यान You and Your Research के लिए जाने जाते हैं। उन्हें 1968 में ट्यूरिंग पुरस्कार मिला।

क्या कोई कोड कितनी भी त्रुटियाँ सुधार सकता है?

केवल पर्याप्त अतिरिक्तता होने पर। कोई कोड प्रति ब्लॉक अधिकतम (d − 1)/2 त्रुटियाँ सुधार सकता है, जहाँ d कोडवर्डों के बीच की न्यूनतम दूरी है, और अधिक जाँच बिट वाले लंबे कोड बड़ा d हासिल करते हैं। शैनन का प्रमेय अंतिम सीमा तय करता है: कोई भी कोड चैनल की क्षमता को पार नहीं कर सकता।

आज़माने के लिए तैयार?

अपने ब्राउज़र में PictorX खोलें — शुरू करने के लिए इंस्टॉल या क्रेडिट कार्ड की ज़रूरत नहीं।

त्रुटि-सुधार कोड सिम्युलेटर खोलें