विभिन्न कोडों का उपयोग करते हुए मजबूत कोडिंग

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



मैंने एक व्यक्ति के लिए जितना संभव हो सके सब कुछ आसानी से वर्णन करने की कोशिश की, जो कभी भी कोडिंग की जानकारी में नहीं लगा था, और बिना किसी विशेष गणितीय सूत्र के।



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



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

कोड अतिरेक एक संदेश में सत्यापन जानकारी की राशि है। इसकी गणना सूत्र द्वारा की जाती है:

k / (i + k) , जहां

k चेक बिट्स की संख्या है,

मैं सूचना बिट्स की संख्या है।

उदाहरण के लिए, हम 3 बिट्स को स्थानांतरित करते हैं और उनके लिए 1 चेक बिट जोड़ते हैं - अतिरेक 1 / (3 + 1) = 1/4 (25%) होगा।

समानता कोड

संचारित डेटा पैकेट में त्रुटियों का पता लगाने के लिए समता एक बहुत ही सरल विधि है। इस कोड के साथ, हम डेटा को पुनर्प्राप्त नहीं कर सकते हैं, लेकिन हम केवल एक त्रुटि का पता लगा सकते हैं।



प्रत्येक डेटा पैकेट में एक समता बिट या तथाकथित समता बिट होती है । यह बिट डेटा लेखन (या भेजने) के दौरान सेट किया जाता है, और फिर डेटा की रीडिंग (प्राप्त) करते समय इसकी गणना और तुलना की जाती है। यह पैकेट में सभी डेटा बिट्स के योग मोडुलो 2 के बराबर है । यही है, पैकेज में इकाइयों की संख्या हमेशा भी होगी । इस बिट को बदलना (उदाहरण के लिए, 0 से 1 तक) एक त्रुटि की रिपोर्ट करता है।

इस कोड के लिए एनकोडर का ब्लॉक आरेख नीचे दिखाया गया है।







और डिकोडर









एक उदाहरण:

प्रारंभिक डेटा: 1111

एन्कोडिंग के बाद डेटा: 1111 0 (1 + 1 + 1 + 1 = 0 (mod 2))

प्राप्त डेटा: 1 0 110 (दूसरा बिट बदल गया है)

जैसा कि हम देखते हैं, प्राप्त पैकेट में इकाइयों की संख्या विषम है, इसलिए, ट्रांसमिशन के दौरान एक त्रुटि हुई।

जैसा कि पहले उल्लेख किया गया है, यह विधि केवल एक त्रुटि निर्धारित करने के लिए कार्य करती है। दो बिट्स की स्थिति में परिवर्तन के मामले में, यह संभव है कि नियंत्रण बिट की गणना रिकॉर्ड किए गए के साथ मेल खाती है। इस मामले में, सिस्टम एक त्रुटि का पता नहीं लगाता है, और यह अच्छा नहीं है। उदाहरण के लिए:

प्रारंभिक डेटा: 1111

एन्कोडिंग के बाद डेटा: 1111 0 (1 + 1 + 1 + 1 = 0 (mod 2))

प्राप्त डेटा: 1 00 10 (2 और 3 बिट्स बदल गए हैं)

प्राप्त आंकड़ों में, इकाइयों की संख्या सम है, और इसलिए, डिकोडर एक त्रुटि का पता नहीं लगाएगा।

चूंकि सभी अनियमित त्रुटियों का लगभग 90% एक ही बिट के साथ होता है, ज्यादातर स्थितियों के लिए समता पर्याप्त है।

हैमिंग कोड

जैसा कि पिछले भाग में कहा गया था, रिचर्ड हैमिंग ने शोर-प्रतिरोधी कोडिंग के लिए बहुत कुछ किया। विशेष रूप से, उसने कोड विकसित किया जो अतिरिक्त चेक बिट्स की न्यूनतम संभव संख्या के साथ एकल त्रुटियों का पता लगाने और सुधार के लिए प्रदान करता है। प्रत्येक संख्या में परीक्षण वर्णों के लिए, प्रपत्र (k, i) के एक विशेष अंकन का उपयोग किया जाता है, जहां k संदेश में वर्णों की संख्या है, मैं संदेश में सूचना वर्णों की संख्या है। उदाहरण के लिए, कोड (7, 4), (15, 11), (31, 26) हैं। हैमिंग कोड में प्रत्येक चेक कैरेक्टर, कुछ डेटा के बाद के योग का प्रतिनिधित्व करता है। आइए एक उदाहरण को तुरंत देखें, जब ब्लॉक में सूचना बिट्स की संख्या 4 है - यह कोड (7.4) है, चेक वर्णों की संख्या 3 है। शास्त्रीय रूप से, ये वर्ण आरोही क्रम में दो की शक्तियों के बराबर पदों पर स्थित हैं:

2 ⁰ = 1 पर पहले चेक बिट;

2 ¹ = 2 पर दूसरा चेक बिट;

2 ² = 4 पर तीसरा चेक बिट;

लेकिन आप उन्हें प्रेषित डेटा ब्लॉक के अंत में रख सकते हैं (लेकिन तब उनकी गणना का सूत्र अलग होगा)।

अब इन परीक्षण वर्णों की गणना करें:

r1 = i1 + i2 + i4

r2 = i1 + i3 + i4

r3 = i2 + i3 + i4

तो, एन्कोडेड संदेश में, हमें निम्नलिखित मिलते हैं:

r1 r2 i1 r3 i2 i3 i4

सिद्धांत रूप में, इस एल्गोरिथ्म के संचालन का विश्लेषण हेमिंग कोड लेख में बहुत विस्तार से किया गया है । एल्गोरिथ्म के संचालन का एक उदाहरण , इसलिए मुझे इस लेख में विस्तार से वर्णन करने की बात नहीं दिखती है। इसके बजाय, मैं एनकोडर का एक ब्लॉक आरेख देता हूँ:



और डिकोडर



(शायद काफी भ्रामक है, लेकिन यह बेहतर काम नहीं करता है)



ई 0, ई 1, ई 2 को बिट्स k1 के आधार पर फ़ंक्शंस के रूप में परिभाषित किया जाता है - डिकोडर द्वारा प्राप्त k7:

e0 = k1 + k3 + k5 + k7 mod 2

e1 = k2 + k3 + k6 + k7 mod 2

e2 = k4 + k5 + k6 + k7 mod 2

इन मूल्यों का सेट e2e1e0 उस स्थिति का एक द्विआधारी रिकॉर्ड है जहां डेटा ट्रांसफर के दौरान त्रुटि हुई। डिकोडर इन मानों की गणना करता है, और यदि वे सभी 0 के बराबर नहीं हैं (अर्थात, 000 वर्कआउट नहीं करता है), तो त्रुटि को ठीक किया जाता है।

उत्पाद कोड

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



प्रेषित जानकारी दो बार एन्कोड की गई है: बाहरी और आंतरिक एन्कोडर्स में। उनके बीच एक बफर स्थापित किया गया है, जिसका ऑपरेशन आकृति में दिखाया गया है:



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



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



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



उत्पाद कोड का उपयोग बार-बार मामूली अतिरेक के साथ त्रुटि-सुधार कोड की शक्ति को बढ़ाता है।



पुनश्च: मैं इस विषय के साथ करीब 3 साल पहले निपटा था जब मैं अपनी स्नातक परियोजना लिख ​​रहा था, शायद मैं कुछ याद कर रहा था। सभी सुधार, टिप्पणियां, सुझाव - कृपया निजी संदेशों के माध्यम से