परिचय।

सबसे पहले, यह कहने योग्य है कि हेमिंग कोड क्या है और इसकी आवश्यकता क्यों है। निम्नलिखित परिभाषा विकिपीडिया पर दी गई है :

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

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

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

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

यह कैसे काम करता है?

इस एल्गोरिथ्म के संचालन को समझने के लिए, एक उदाहरण पर विचार करें।

ट्रेनिंग

मान लीजिए कि हमारे पास एक हबल संदेश है जिसे त्रुटि के बिना प्रसारित करना होगा। ऐसा करने के लिए, आपको सबसे पहले हेमिंग कोड का उपयोग करके हमारे संदेश को एनकोड करना होगा। हमें इसे बाइनरी रूप में प्रस्तुत करने की आवश्यकता है।



इस स्तर पर, यह सूचना शब्द की तथाकथित लंबाई पर निर्णय लेने के लायक है, अर्थात शून्य की स्ट्रिंग की लंबाई और जिन्हें हम एन्कोड करेंगे। मान लें कि हमारे पास शब्द की लंबाई 16 है। इस प्रकार, हमें अपने मूल संदेश ("हब्र") को 16 बिट्स के ब्लॉक में विभाजित करने की आवश्यकता है, जिसे हम बाद में एक-दूसरे से अलग से एनकोड करेंगे। चूँकि एक वर्ण स्मृति में 8 बिट्स रखता है, ठीक दो ASCII वर्णों को एक एन्कोडेड शब्द में रखा गया है। तो, हमें 16 बिट्स के दो बाइनरी स्ट्रिंग्स मिले:

और

इसके बाद, एन्कोडिंग प्रक्रिया को समानांतर किया जाता है, और संदेश के दो भाग ("हा" और "ब्र") एक दूसरे से स्वतंत्र रूप से एन्कोड किए जाते हैं। आइए विचार करें कि पहले भाग के उदाहरण का उपयोग करके यह कैसे किया जाता है।
सबसे पहले, आपको नियंत्रण बिट्स सम्मिलित करने की आवश्यकता है। उन्हें कड़ाई से परिभाषित स्थानों में डाला जाता है - ये दो की शक्तियों के बराबर संख्या के साथ स्थितियां हैं। हमारे मामले में (16 बिट्स की एक सूचना शब्द लंबाई के साथ) ये 1, 2, 4, 8, 16 पदों पर होंगे। तदनुसार, हमें 5 नियंत्रण बिट्स (लाल रंग में हाइलाइट किए गए) मिले:

यह था:


यह बन गया:


इस प्रकार, पूरे संदेश की लंबाई 5 बिट बढ़ गई। नियंत्रण बिट्स की गणना करने से पहले, हमने उन्हें "0" का मान दिया।

नियंत्रण बिट्स की गणना।

अब आपको प्रत्येक नियंत्रण बिट के मूल्य की गणना करने की आवश्यकता है। प्रत्येक नियंत्रण बिट का मूल्य सूचना बिट्स के मूल्यों (अप्रत्याशित रूप से) पर निर्भर करता है, लेकिन सभी पर नहीं, केवल उन पर जो इस नियंत्रण बिट को नियंत्रित करते हैं। यह समझने के लिए कि प्रत्येक नियंत्रण बिट के लिए कौन सा बिट जिम्मेदार है, यह एक बहुत ही सरल पैटर्न को समझने के लिए आवश्यक है: नंबर N के साथ नियंत्रण बिट सभी N बिट्स को प्रत्येक N बिट्स से नियंत्रित करता है, स्थिति N से शुरू होता है। यह बहुत स्पष्ट नहीं है, लेकिन मुझे लगता है कि यह तस्वीर से नहीं होगा। साफ:

यहां, "X" उन बिट्स को दर्शाता है जो नियंत्रण बिट द्वारा नियंत्रित होते हैं, जिनमें से संख्या दाईं ओर है। यही है, उदाहरण के लिए, बिट संख्या 12 को बिट्स द्वारा 4 और 8 के साथ नियंत्रित किया जाता है। यह स्पष्ट है कि नंबर बी के साथ बिट्स को नियंत्रित करने के लिए यह पता लगाने के लिए, आपको केवल दो की शक्तियों में एन का विस्तार करने की आवश्यकता है।

लेकिन प्रत्येक नियंत्रण बिट के मूल्य की गणना कैसे करें? यह बहुत सरलता से किया जाता है: हम प्रत्येक नियंत्रण बिट को लेते हैं और देखते हैं कि इसके द्वारा नियंत्रित बिट्स के बीच कितनी इकाइयाँ हैं, हमें एक निश्चित पूर्णांक मिलता है और यदि यह समान है, तो हम शून्य डालते हैं, अन्यथा हम एक सेट करते हैं। वह सब है! यह संभव है, निश्चित रूप से, और इसके विपरीत, यदि संख्या सम है, तो एकता में सेट करें, अन्यथा, 0. से सेट करें। मुख्य बात यह है कि एल्गोरिथ्म "कोडिंग" और "डिकोडिंग" भागों में समान होना चाहिए। (हम पहला विकल्प लागू करेंगे)।
हमारी जानकारी शब्द के लिए नियंत्रण बिट्स की गणना करने के बाद, हमें निम्नलिखित मिलते हैं:

और दूसरे भाग के लिए:


वह सब है! एल्गोरिथम का पहला भाग पूरा हो गया है।

डिकोडिंग और त्रुटि सुधार।

अब, मान लें कि हमें एल्गोरिथ्म के पहले भाग द्वारा एक संदेश मिला है, लेकिन यह हमारे लिए एक त्रुटि है। उदाहरण के लिए, हमें यह मिला (11 वां बिट गलत तरीके से प्रेषित किया गया था):

एल्गोरिथ्म का पूरा दूसरा हिस्सा इस तथ्य में शामिल है कि सभी नियंत्रण बिट्स (पहले भाग के रूप में) को पुनर्गणना करना और उन्हें प्राप्त नियंत्रण बिट्स के साथ तुलना करना आवश्यक है। इसलिए, नियंत्रण बिट्स को गलत 11 बिट के साथ गिनते हुए, हमें निम्न चित्र मिलता है:

जैसा कि हम देख सकते हैं, संख्या के तहत नियंत्रण बिट्स: 1, 2, 8 उसी नियंत्रण बिट्स के साथ मेल नहीं खाते हैं जो हमें प्राप्त हुए थे। अब सिर्फ गलत नियंत्रण बिट्स (1 + 2 + 8 = 11) की स्थिति संख्याओं को जोड़कर हम गलत बिट की स्थिति प्राप्त करते हैं। अब बस इसे निष्क्रिय करके और नियंत्रण बिट्स को त्यागकर, हम मूल संदेश को उसके मूल रूप में प्राप्त करते हैं! हम संदेश के दूसरे भाग के साथ ठीक वैसा ही करते हैं।

निष्कर्ष।

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

नोट।

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

सूत्रों का कहना है।

1. विकिपीडिया
2. हैमिंग कोड की गणना