त्रुटि संसूचन और सुधार: Difference between revisions
m (added Category:Vigyan Ready using HotCat) |
No edit summary |
||
| (One intermediate revision by one other user not shown) | |||
| Line 212: | Line 212: | ||
* [http://www.eccpage.com/ ईसीसी Page] - implementations of popular ईसीसी encoding and decoding routines | * [http://www.eccpage.com/ ईसीसी Page] - implementations of popular ईसीसी encoding and decoding routines | ||
[[Category:All articles needing additional references]] | |||
[[Category:All articles with dead external links]] | |||
[[Category:Articles needing additional references from अगस्त 2008]] | |||
[[Category:Articles needing more detailed references]] | |||
[[Category:Articles with dead external links from March 2020]] | |||
[[Category:Articles with hatnote templates targeting a nonexistent page]] | |||
[[Category:Articles with invalid date parameter in template]] | |||
[[Category:Articles with permanently dead external links]] | |||
[[Category:Articles with short description]] | |||
[[Category:CS1 English-language sources (en)]] | |||
[[Category:Machine Translated Page]] | [[Category:Machine Translated Page]] | ||
[[Category: | [[Category:Short description with empty Wikidata description]] | ||
Latest revision as of 16:03, 17 November 2022
 | This आलेख needs additional citations for verification. (अगस्त 2008) (Learn how and when to remove this template message) |
सूचना सिद्धांत तथा संगणक विज्ञान तथा दूरसंचार में अनुप्रयोगों के साथ कोडिंग सिद्धांत में त्रुटि के संसूचन तथा संशोधन (ईडीएसी) या त्रुटि नियंत्रण हेतु ऐसी तकनीकें हैं जो अविश्वसनीय संचार चैनलों पर डिजिटल डेटा के विश्वसनीय वितरण को सक्षम बनाती हैं। कई संचार चैनल, चैनल रव (नॉइज़) के अधीन होते हैं, तथा इस प्रकार स्रोत से गृहीता तक संचरण के दौरान त्रुटियां त्रुटियाँ प्रदर्शित हो सकती हैं। त्रुटि संसूचन तकनीक ऐसी त्रुटियों का पता लगाने की अनुमति देती है, जबकि त्रुटि संशोधन कई स्थितियों में मूल डेटा के पुनर्निर्माण को सक्षम बनाता है।
परिभाषाएं
त्रुटि के संसूचन से ट्रांसमीटर से गृहीता तक संचरण के दौरान रव (नॉइज़) या अन्य हानि के कारण होने वाली त्रुटियों का पता लगाना है।
त्रुटि संशोधन त्रुटियों का पता लगाना तथा मूल, त्रुटि मुक्त डेटा का पुनर्निर्माण है।
इतिहास
प्राचीन पुराकाल में, हिब्रू बाइबिल के प्रतिलेखकों को उनके काम के लिए पंक्तिकाय (कविता की पंक्तियाँ) की संख्या के अनुसार सवेतन प्रदान किया गया था। चूंकि बाइबिल की गद्य पुस्तकें शायद ही कभी पंक्तिकाय में लिखी गई थीं, प्रतिलिपिकार को काम की मात्रा का अनुमान लगाने के लिए अक्षरों को गिनना पड़ता था।[1] इससे अनुवर्ती प्रतियों के उत्पादन के साथ पाठ के प्रसारण में यथार्थता सुनिश्चित करने में भी मदद मिली।[2][3] 7वीं तथा 10वीं शताब्दी के बीच यहूदी शास्त्रियों के एक समूह ने पवित्र पाठ के सटीक पुनरुत्पादन को सुनिश्चित करने के लिए न्यूमेरिकल मसोराह बनाने के लिए औपचारिक रूप से इसका विस्तार किया था। इसमें पंक्ति, खंड, पुस्तक तथा पुस्तकों के समूहों में शब्दों की संख्या की गणना, एक पुस्तक के मध्य स्टिच को ध्यान में रखते हुए, शब्द उपयोग सांख्यिकी तथा कमेंट्री सम्मिलित थी।[1] मानक ऐसे बन गए कि टोरा स्क्रॉल में एक भी अक्षर में विचलन को अस्वीकार्य माना जाता था।[4] उनकी त्रुटि संशोधन पद्धति की प्रभावशीलता को 1947-1956 में मृत सागर स्क्रॉल की खोज द्वारा प्रदर्शित सदियों से प्रतिलिपि बनाने की यथार्थता से सत्यापित किया गया था, जो कि 150 ईसा पूर्व-75 सीई से डेटिंग थी।[5]
त्रुटि संशोधन कोड के आधुनिक विकास का श्रेय 1947 में रिचर्ड हैमिंग को जाता है।[6] हैमिंग के कोड का वर्णन क्लॉड शैनन की ए मैथमेटिकल थ्योरी ऑफ़ कम्युनिकेशन में दिखाई दिया[7] तथा मार्सेल जे.ई. गोलय द्वारा जल्दी से सामान्यीकृत किया गया।[8]
परिचय
सभी त्रुटि-संसूचन तथा संशोधन योजनाएँ एक संदेश में कुछ शब्दातिरेक (अर्थात्, कुछ अतिरिक्त डेटा) जोड़ती हैं, जिसका उपयोग गृहीता वितरित संदेश की निरंतरता की जाँच करने के लिए तथा अपमिश्रित होने के लिए निर्धारित डेटा को पुनर्प्राप्त करने के लिए कर सकते हैं। त्रुटि-संसूचन तथा संशोधन योजनाएँ व्यवस्थित या गैर-व्यवस्थित हो सकती हैं। एक व्यवस्थित योजना में, ट्रांसमीटर मूल डेटा भेजता है, तथा एक निश्चित संख्या में चेक बिट्स (या समता डेटा) संलग्न करता है, जो डेटा बिट्स से कुछ नियतात्मक एल्गोरिदम द्वारा प्राप्त किए जाते हैं। यदि केवल त्रुटि का पता लगाने की आवश्यकता है, तो एक गृहीता केवल प्राप्त डेटा बिट्स के लिए समान एल्गोरिदम लागू कर सकता है तथा प्राप्त चेक बिट्स के साथ इसके आउटपुट की तुलना कर सकता है; यदि मान मेल नहीं खाते हैं, तो संचरण के दौरान किसी बिंदु पर त्रुटि हुई है। एक ऐसी प्रणाली में जो एक गैर-व्यवस्थित कोड का उपयोग करती है, मूल संदेश एक एन्कोडेड संदेश में बदल जाता है जिसमें समान जानकारी होती है तथा कम से कम मूल संदेश के रूप में कई बिट्स होते हैं।
अच्छे त्रुटि नियंत्रण प्रदर्शन के लिए संचार चैनल की विशेषताओं के आधार पर योजना का चयन करना आवश्यक होता है। सामान्य चैनल मॉडल में मेमोरी-रहित मॉडल सम्मिलित होते हैं जहां त्रुटियां अव्यवस्थिततः से तथा एक निश्चित संभावना के साथ होती हैं, तथा डायनेमिक मॉडल जहां मुख्य रूप से बर्स्ट में त्रुटियां होती हैं। परिणामस्वरूप, त्रुटि-संसूचन तथा संशोधन कोड को सामान्यतः यादृच्छिक-त्रुटि-संसूचन /संशोधन तथा फट-त्रुटि-संसूचन/संशोधन के बीच अलग किया जा सकता है। यादृच्छिक त्रुटियों तथा फट त्रुटियों के मिश्रण के लिए कुछ कोड भी उपयुक्त हो सकते हैं।
यदि चैनल विशेषताओं को निर्धारित नहीं किया जा सकता है, या अत्यधिक परिवर्तनशील हैं, तो एक त्रुटि-संसूचन योजना को गलत डेटा के पुनर्संचार के लिए एक प्रणाली के साथ जोड़ा जा सकता है। इसे ऑटोमैटिक रिपीट रिक्वेस्ट (एआरक्यू) के रूप में जाना जाता है, तथा इंटरनेट में इसका सबसे अधिक उपयोग किया जाता है। त्रुटि नियंत्रण के लिए एक वैकल्पिक दृष्टिकोण हाइब्रिड ऑटोमैटिक रिपीट रिक्वेस्ट (एचएआरक्यू) है, जो एआरक्यू तथा त्रुटि-संशोधन कोडिंग का संयोजन है।
त्रुटि संशोधन के प्रकार
त्रुटि संशोधन के तीन प्रमुख प्रकार हैं।[9]
ऑटोमैटिक रिपीट रिक्वेस्ट
ऑटोमैटिक रिपीट रिक्वेस्ट (एआरक्यू) डेटा संचरण के लिए एक त्रुटि-संसूचन विधि है जो विश्वसनीय डेटा संचरण प्राप्त करने के लिए त्रुटि-संसूचन कोड, अभिस्वीकृति तथा/ या ऋणात्मक अभिस्वीकृति संदेशों तथा मध्यांतर का उपयोग करता है। अभिस्वीकृति एक संदेश है जो प्राप्तकर्ता द्वारा यह इंगित करने के लिए भेजा जाता है कि उसे उचित रूप से एक डेटा फ्रेम प्राप्त हुआ है।
सामान्यतः, जब ट्रांसमीटर को समय समाप्त होने से पहले अभिस्वीकृति प्राप्त नहीं होती है (अर्थात, डेटा फ़्रेम भेजने के बाद उचित समय के भीतर), यह फ्रेम को तब तक फिर से प्रसारित करता है जब तक कि यह या तो उचित रूप से प्राप्त नहीं हो जाता है या त्रुटि पूर्व निर्धारित संख्या से अधिक होने तक बनी रहती है।
तीन प्रकार के एआरक्यू प्रोटोकॉल स्टॉप-एंड-वेट एआरक्यू, गो-बैक-एन एआरक्यू तथा सेलेक्टिव रिपीट एआरक्यू हैं।
एआरक्यू उपयुक्त है यदि संचार चैनल में भिन्न या अज्ञात क्षमता है, जैसा कि इंटरनेट पर होता है। हालांकि, एआरक्यू को एक बैक चैनल की उपलब्धता की आवश्यकता होती है, जिसके परिणामस्वरूप संभावित रूप से पुनः संचरण के कारण विलंबता बढ़ जाती है, तथा पुनः संचरण के लिए बफर तथा टाइमर के रखरखाव की आवश्यकता होती है, जो नेटवर्क भीड़ के स्थितियों में सर्वर तथा समग्र नेटवर्क क्षमता पर दबाव डाल सकता है।[10]
उदाहरण के लिए, एआरक्यू का उपयोग एआरक्यू-ई के रूप में लघु तरंग रेडियो डेटा लिंक पर किया जाता है, या एआरक्यू-एम के रूप में मल्टीप्लेक्सिंग के साथ जोड़ा जाता है।
अग्रेषित त्रुटि संशोधन
अग्रेषित त्रुटि संशोधन (एफईसी) एक संदेश में एक त्रुटि-संशोधन कोड (ईसीसी) जैसे अनावश्यक डेटा जोड़ने की एक प्रक्रिया है ताकि इसे एक गृहीता द्वारा पुनर्प्राप्त किया जा सके, भले ही कई त्रुटियां (प्रयुक्त कोड की क्षमता तक) पेश की गई हों, या तो संचरण की प्रक्रिया के दौरान या संचयन पर। चूंकि गृहीता को प्रेषक को डेटा के पुन: प्रेषण के लिए नहीं पूछना पड़ता है, इसलिए आगे की त्रुटि संशोधन में बैकचैनल की आवश्यकता नहीं होती है। त्रुटि-संशोधन कोड का उपयोग निचली-परत संचार में किया जाता है जैसे सेल्युलर नेटवर्क, हाई-स्पीड फाइबर-ऑप्टिक संचार तथा वाई-फाई,[11][12] तथा साथ ही मीडिया में विश्वसनीय भंडारण जैसे फ्लैश मेमोरी, हार्ड डिस्क तथा रैम।[13]
त्रुटि-संशोधन करने वाले कोड सामान्यतः दृढ़ कोड तथा ब्लॉक कोड के बीच प्रतिष्ठित होते हैं:
- संवलन कोड को बिट-दर-बिट आधार पर प्रोसेस किया जाता है। वे हार्डवेयर में कार्यान्वयन के लिए विशेष रूप से उपयुक्त हैं, तथा विटरबी डिकोडर इष्टतम डिकोडिंग की अनुमति देता है।
- ब्लॉक कोड ब्लॉक-दर-ब्लॉक आधार पर संसाधित होते हैं। ब्लॉक कोड के प्रारंभिक उदाहरण पुनरावृत्ति कोड, हैमिंग कोड तथा बहुआयामी समता-चेक कोड हैं। उनके बाद कई कुशल कोड थे, रीड-सोलोमन कोड उनके वर्तमान व्यापक उपयोग के कारण सबसे उल्लेखनीय थे। टर्बो कोड तथा लो-डेंसिटी पैरिटी-चेक कोड (एलडीपीसी) अपेक्षाकृत नए निर्माण हैं जो लगभग इष्टतम दक्षता प्रदान कर सकते हैं।
शैनन की प्रमेय आगे की त्रुटि संशोधन में एक महत्वपूर्ण प्रमेय है, तथा अधिकतम सूचना दर का वर्णन करता है जिस पर एक चैनल पर विश्वसनीय संचार संभव है जिसमें एक निश्चित त्रुटि संभावना या सिग्नल-टू-रव (नॉइज़) अनुपात (एसएनआर) है। यह सख्त ऊपरी सीमा चैनल क्षमता के संदर्भ में अभिव्यक्त की जाती है। अधिक विशेष रूप से, प्रमेय कहता है कि कोड मौजूद हैं जैसे कि बढ़ती एन्कोडिंग लंबाई के साथ एक असतत मेमोरीलेस चैनल पर त्रुटि की संभावना को मनमाने ढंग से छोटा किया जा सकता है, बशर्ते कोड दर चैनल क्षमता से कम हो। कोड दर को के स्रोत प्रतीकों तथा एन एन्कोडेड प्रतीकों के अंश के/एन के रूप में परिभाषित किया गया है।
अनुमत वास्तविक अधिकतम कोड दर उपयोग किए गए त्रुटि-संशोधन कोड पर निर्भर करता है, तथा कम हो सकता है। ऐसा इसलिए है क्योंकि शैनन का प्रमाण केवल अस्तित्वगत प्रकृति का था, तथा यह नहीं दिखाया कि ऐसे कोड कैसे बनाए जाएं जो इष्टतम हों तथा कुशल एन्कोडिंग तथा डिकोडिंग एल्गोरिदम हों।
हाइब्रिड योजनाएं
हाइब्रिड एआरक्यू एआरक्यू तथा अग्रेषित त्रुटि संशोधन का मेल है। दो बुनियादी दृष्टिकोण हैं:[10]
- संदेशों को हमेशा एफईसी समता डेटा (तथा त्रुटि-संसूचन शब्दातिरेक) के साथ प्रेषित किया जाता है। एक गृहीता समता जानकारी का उपयोग करके एक संदेश को डीकोड करता है, तथा केवल एआरक्यू का उपयोग करके पुन: प्रेषण का अनुरोध करता है, यदि समता डेटा सफल डिकोडिंग के लिए पर्याप्त नहीं था (एक असफल अखंडता जांच के माध्यम से संसूचना गया)।
- संदेश समता डेटा के बिना प्रेषित होते हैं (केवल त्रुटि-संसूचन जानकारी के साथ)। यदि कोई गृहीता किसी त्रुटि का पता लगाता है, तो वह एआरक्यू का उपयोग करके ट्रांसमीटर से एफईसी जानकारी का अनुरोध करता है, तथा मूल संदेश को फिर से बनाने के लिए इसका उपयोग करता है।
रेटलेस इरेज़र कोड का उपयोग करते समय इरेज़र चैनल पर बाद वाला दृष्टिकोण विशेष रूप से आकर्षक होता है।
त्रुटि संसूचन योजनाएँ
एक उपयुक्त हैश फ़ंक्शन (या विशेष रूप से, एक चेकसम, चक्रीय शब्दातिरेक जाँच या अन्य एल्गोरिथम) का उपयोग करके त्रुटि का पता लगाना सबसे आम है। हैश फ़ंक्शन, संदेश में एक निश्चित-लंबाई का टैग जोड़ता है, जो गृहीता को टैग को पुनः कंप्यूट करके तथा प्रदान किए गए के साथ तुलना करके वितरित संदेश को सत्यापित करने में सक्षम बनाता है।
विभिन्न हैश फ़ंक्शन डिज़ाइनों की एक विस्तृत विविधता मौजूद है। हालांकि, कुछ विशेष प्रकार की त्रुटियों का पता लगाने के लिए उनकी सादगी या उनकी उपयुक्तता के कारण विशेष रूप से व्यापक उपयोग के हैं (उदाहरण के लिए, फट त्रुटियों का पता लगाने में चक्रीय शब्दातिरेक जांच का प्रदर्शन)।
न्यूनतम अतर कोडिंग
न्यूनतम अतर कोडिंग के आधार पर एक यादृच्छिक-त्रुटि-संशोधन कोड पता लगाने योग्य त्रुटियों की संख्या पर सख्त गारंटी प्रदान कर सकता है, लेकिन यह प्रीइमेज हमले के विरुद्ध सुरक्षा नहीं कर सकता है।
पुनरावर्तन कोड
पुनरावर्तन कोड एक कोडिंग योजना है जो त्रुटि-मुक्त संचार प्राप्त करने के लिए पूरे चैनल में बिट्स को पुनरावृत होती है। संचारित होने वाले डेटा की एक धारा को देखते हुए, डेटा को बिट्स के ब्लॉक में विभाजित किया जाता है। प्रत्येक ब्लॉक कुछ पूर्व निर्धारित संख्या में प्रसारित होता है। उदाहरण के लिए, बिट पैटर्न "1011" भेजने के लिए, चार-बिट ब्लॉक को तीन बार दोहराया जा सकता है, इस प्रकार "1011 1011 1011" का उत्पादन किया जा सकता है। यदि यह बारह-बिट पैटर्न "1010 1011 1011" के रूप में प्राप्त हुआ था - जहां पहला ब्लॉक अन्य दो के विपरीत है - एक त्रुटि उत्पन्न हुई है।
पुनरावृत्ति कोड बहुत अक्षम है, तथा यदि प्रत्येक समूह के लिए ठीक उसी स्थान पर त्रुटि होती है (उदाहरण के लिए, "1010 1010 1010" पिछले उदाहरण में सही के रूप में पाया जाएगा) तो समस्याओं के लिए अतिसंवेदनशील हो सकता है। दोहराव कोड का लाभ यह है कि वे बेहद सरल हैं, तथा वास्तव में नंबर स्टेशनों के कुछ प्रसारणों में उपयोग किए जाते हैं।[14][15]
समता बिट
समता बिट एक बिट है जिसे स्रोत बिट्स के समूह में जोड़ा जाता है ताकि यह सुनिश्चित किया जा सके कि परिणाम में सेट बिट्स (अर्थात, मान 1 के साथ बिट्स) की संख्या सम या विषम है। यह एक बहुत ही सरल योजना है जिसका उपयोग आउटपुट में त्रुटियों के एकल या किसी अन्य विषम संख्या (अर्थात, तीन, पांच, आदि) का पता लगाने के लिए किया जा सकता है। फ़्लिप किए गए बिट्स की एक सम संख्या समता बिट को सही बना देगी, भले ही डेटा गलत हो।
भेजे गए प्रत्येक "शब्द" में जोड़े गए समता बिट्स को अनुप्रस्थ शब्दातिरेक जाँच कहा जाता है, जबकि "शब्दों" की एक धारा के अंत में जोड़े जाने वाले अनुदैर्ध्य शब्दातिरेक जाँच कहलाते हैं। उदाहरण के लिए, यदि एम-बिट "शब्दों" की प्रत्येक श्रृंखला में एक समता बिट जोड़ा गया है, यह दिखाते हुए कि उस शब्द में एक विषम या सम संख्या थी, इसमें एक त्रुटि वाला कोई भी शब्द खोजा जाएगा। हालांकि यह पता नहीं चल पाएगा कि शब्द में कहां गलती है। यदि, इसके अलावा, एन शब्दों की प्रत्येक धारा के बाद एक समता योग भेजा जाता है, जिनमें से प्रत्येक बिट दिखाता है कि क्या उस बिट-स्थिति में सबसे हाल के समूह में भेजे गए विषम या सम संख्या वाले थे, त्रुटि की सही स्थिति का निर्धारण किया जा सकता है तथा त्रुटि को ठीक किया जा सकता है। हालाँकि, इस विधि के प्रभावी होने की गारंटी तभी दी जाती है, जब एन शब्दों के प्रत्येक समूह में 1 से अधिक त्रुटि न हो। अधिक त्रुटि संशोधन बिट्स के साथ, अधिक त्रुटियों का पता लगाया जा सकता है तथा कुछ स्थितियों में उन्हें ठीक किया जा सकता है।
अन्य बिट-समूहीकरण तकनीकें भी हैं।
चेकसम
संदेश का चेकसम एक निश्चित शब्द लंबाई (जैसे, बाइट मान) के संदेश कोड शब्दों का एक मॉड्यूलर अंकगणितीय योग है। अनजाने में सभी शून्य संदेशों का पता लगाने के लिए संचरण से पहले एक-पूरक ऑपरेशन के माध्यम से योग को अस्वीकार किया जा सकता है।
चेकसम योजनाओं में समता बिट्स, चेक अंक तथा देशांतरीय शब्दातिरेक जांच सम्मिलित हैं। कुछ चेकसम योजनाएं, जैसे कि डैम एल्गोरिथम, लुहन एल्गोरिथम, तथा वेरहोफ एल्गोरिथम, विशेष रूप से उन त्रुटियों का पता लगाने के लिए डिज़ाइन की गई हैं जो सामान्यतः संसूचन संख्या लिखने या याद रखने में मनुष्यों द्वारा शुरू की गई हैं।
चक्रीय शब्दातिरेक जाँच
चक्रीय शब्दातिरेक जाँच (सीआरसी) एक गैर-सुरक्षित हैश फ़ंक्शन होता है जिसे संगणक नेटवर्क में डिजिटल डेटा में आकस्मिक परिवर्तन का पता लगाने के लिए डिज़ाइन किया गया है। यह दुर्भावनापूर्ण रूप से प्रस्तुत त्रुटियों का पता लगाने के लिए उपयुक्त नहीं है। यह एक जनरेटर बहुपद के विनिर्देशन द्वारा विशेषता है, जिसका उपयोग एक परिमित क्षेत्र पर बहुपद लंबे विभाजन में भाजक के रूप में किया जाता है, इनपुट डेटा को लाभांश के रूप में लेते हुए। शेष परिणाम बन जाता है।
एक सीआरसी में ऐसे गुण होते हैं जो इसे प्रस्फोट त्रुटियों का पता लगाने के लिए उपयुक्त बनाते हैं। सीआरसी विशेष रूप से हार्डवेयर में लागू करने में आसान होते हैं तथा इसलिए सामान्यतः संगणक नेटवर्क तथा हार्ड डिस्क ड्राइव जैसे संचयन युक्ति में उपयोग किए जाते हैं।
समता बिट को विशेष-केस 1-बिट सीआरसी के रूप में देखा जा सकता है।
प्रच्छन्नालेखी (क्रिप्टोग्राफिक) हैश फ़ंक्शन
प्रच्छन्नालेखी हैश फ़ंक्शन का आउटपुट, जिसे संदेश डाइजेस्ट के रूप में भी जाना जाता है, डेटा अखंडता के बारे में मजबूत आश्वासन प्रदान कर सकता है, चाहे डेटा के परिवर्तन आकस्मिक हों (उदाहरण के लिए, संचरण त्रुटियों के कारण) या दुर्भावनापूर्ण रूप से पेश किए गए हों। डेटा में किसी भी संशोधन का पता बेमेल हैश मान के माध्यम से लगाया जा सकता है। इसके अलावा, कुछ हैश मान दिए जाने पर, कुछ इनपुट डेटा (दिए गए एक के अलावा) को ढूंढना सामान्यतः संभव नहीं है जो समान हैश मान उत्पन्न करेगा। यदि कोई हमलावर न केवल संदेश बल्कि हैश मान को भी बदल सकता है, तो अतिरिक्त सुरक्षा के लिए एक बंद हैश या संदेश प्रमाणीकरण कोड (मैक) का उपयोग किया जा सकता है। कुंजी को जाने बिना, हमलावर के लिए आसानी से या आसानी से संशोधित संदेश के लिए सही कुंजी वाले हैश मान की गणना करना संभव नहीं है।
त्रुटि संशोधन कोड
त्रुटि का पता लगाने के लिए किसी भी त्रुटि-संशोधन कोड का उपयोग किया जा सकता है। न्यूनतम हैमिंग अतर कोड, डी, एक कोड वर्ड में डी-1 त्रुटियों तक का पता लगा सकता है। त्रुटि का पता लगाने के लिए न्यूनतम-दूरी-आधारित त्रुटि-संशोधन कोड का उपयोग करना उपयुक्त हो सकता है यदि पता लगाने के लिए त्रुटियों की न्यूनतम संख्या पर एक सख्त सीमा वांछित है।
न्यूनतम हैमिंग दूरी डी = 2 वाले कोड त्रुटि-संशोधन कोड के पतित स्थितियों हैं, तथा एकल त्रुटियों का पता लगाने के लिए उपयोग किया जा सकता है। समता बिट एकल-त्रुटि-पता लगाने वाले कोड का एक उदाहरण है।
अनुप्रयोग
कम विलंबता की आवश्यकता वाले एप्लिकेशन (जैसे टेलीफोन वार्तालाप) स्वचालित दोहराव अनुरोध (एआरक्यू) का उपयोग नहीं कर सकते हैं; उन्हें अग्रेषित त्रुटि संशोधन (एफईसी) का इस्तेमाल करना चाहिए। जब तक एक एआरक्यू सिस्टम एक त्रुटि का पता लगाता है तथा इसे फिर से प्रसारित करता है, तब तक फिर से भेजा गया डेटा प्रयोग करने योग्य होने के लिए बहुत देर से आएगा।
ऐसे अनुप्रयोग जहां ट्रांसमीटर सूचना भेजते ही तुरंत भूल जाता है (जैसे कि अधिकांश टेलीविजन कैमरे) एआरक्यू का उपयोग नहीं कर सकते हैं; उन्हें एफईसी का उपयोग अवश्य करना चाहिए क्योंकि जब कोई त्रुटि होती है, तो मूल डेटा अब उपलब्ध नहीं होता है।
अनुप्रयोग जो एआरक्यू का उपयोग करते हैं, उनके पास एक वापसी चैनल होना चाहिए; बिना वापसी चैनल वाले एप्लिकेशन एआरक्यू का उपयोग नहीं कर सकते।
एफईसी के साथ अचूक त्रुटियों की संभावना के कारण जिन अनुप्रयोगों के लिए अत्यंत कम त्रुटि दर (जैसे डिजिटल धन हस्तांतरण) की आवश्यकता होती है, उन्हें एआरक्यू का उपयोग करना चाहिए।
विश्वसनीयता तथा निरीक्षण इंजीनियरिंग भी त्रुटि-संशोधन करने वाले कोड के सिद्धांत का उपयोग करते हैं।[16]
इंटरनेट
सामान्य टीसीपी/आईपी स्टैक में, त्रुटि नियंत्रण कई स्तरों पर किया जाता है:
- प्रत्येक ईथरनेट फ्रेम सीआरसी-32 त्रुटि संसूचन का उपयोग करता है। पता लगाई गई त्रुटियों वाले फ़्रेमों को गृहीता हार्डवेयर द्वारा हटा दिया जाता है।
- IPv4 हेडर में हेडर की सामग्री की सुरक्षा के लिए चेकसम होता है। गलत चेकसम वाले पैकेट नेटवर्क के अंदर या गृहीता के पास छोड़ दिए जाते हैं।
- नेटवर्क रूटिंग में प्रसंस्करण लागत को कम करने के लिए IPv6 हेडर से चेकसम को हटा दिया गया था और क्योंकि वर्तमान लिंक परत तकनीक को पर्याप्त त्रुटि पहचान प्रदान करने के लिए माना जाता है (आरएफसी 3819 भी देखें)।
- यूडीपी के पास एक वैकल्पिक चेकसम है जो यूडीपी तथा आईपी हेडर में पेलोड तथा एड्रेसिंग जानकारी को कवर करता है। गलत चेकसम वाले पैकेट्स को नेटवर्क स्टैक द्वारा छोड़ दिया जाता है। IPv4̟ के तहत चेकसम वैकल्पिक है तथा आईपीवी6 के तहत आवश्यक है। छोड़े जाने पर, यह माना जाता है कि डेटा-लिंक परत त्रुटि सुरक्षा का वांछित स्तर प्रदान करती है।
- टीसीपी पेलोड की सुरक्षा तथा टीसीपी तथा आईपी हेडर में सूचना को संबोधित करने के लिए चेकसम प्रदान करता है। गलत चेकसम वाले पैकेटों को नेटवर्क स्टैक द्वारा हटा दिया जाता है, तथा अंततः एआरक्यू का उपयोग करके पुनः प्रेषित किया जाता है, या तो स्पष्ट रूप से (जैसे कि तीन-तरफ़ा हैंडशेक के माध्यम से) या समय समाप्त होने के कारण निहित रूप से।
गहन अंतरिक्ष दूरसंचार
अंतर-ग्रहीय दूरी पर सिग्नल शक्ति के अत्यधिक कमजोर पड़ने तथा अंतरिक्ष जांच में सीमित बिजली उपलब्धता के कारण त्रुटि-संशोधन कोड का विकास गहरे अंतरिक्ष मिशन के इतिहास के साथ कसकर जोड़ा गया था। जबकि शुरुआती मिशनों ने अपने डेटा को बिना कोड के भेजा, 1968 से शुरू होकर, डिजिटल त्रुटि संशोधन को (सब-इष्टतम रूप से डीकोडेड) कनवल्शनल कोड तथा रीड-मुलर कोड के रूप में लागू किया गया था।[17] रीड-मुलर कोड उस रव (नॉइज़) के अनुकूल था जो अंतरिक्ष यान (लगभग एक घंटी वक्र से मेल खाता था) के अधीन था, तथा इसे मेरिनर अंतरिक्ष यान के लिए लागू किया गया था तथा 1969 तथा 1977 के बीच मिशनों पर उपयोग किया गया था।
वोयाजर 1 तथा वोयाजर 2 मिशन, जो 1977 में शुरू हुए थे, को बृहस्पति तथा शनि से रंगीन इमेजिंग तथा वैज्ञानिक जानकारी देने के लिए डिजाइन किया गया था।[18] इसके परिणामस्वरूप कोडिंग आवश्यकताओं में वृद्धि हुई, तथा इस प्रकार, अंतरिक्ष यान को (बेहतर वितरबी-डीकोडेड) कनवल्शनल कोड द्वारा समर्थित किया गया था जो कि एक बाहरी गोले (24,12,8) कोड के साथ जोड़ा जा सकता है। वोयाजर 2 यान ने रीड-सोलोमन कोड के कार्यान्वयन का अतिरिक्त समर्थन किया। जुड़े हुए रीड-सोलोमन-विटरबी (आरएसवी) कोड ने बहुत शक्तिशाली त्रुटि संशोधन की अनुमति दी, तथा अंतरिक्ष यान की यूरेनस तथा नेप्च्यून की विस्तारित यात्रा को सक्षम किया। 1989 में ईसीसी प्रणाली के उन्नयन के बाद, दोनों शिल्पों ने IPv42 आरएसवी कोडिंग का इस्तेमाल किया।
स्पेस डेटा सिस्टम्स के लिए सलाहकार समिति वर्तमान में वायेजर V2 आरएसवी कोड के समान प्रदर्शन के साथ त्रुटि संशोधन कोड के उपयोग की सिफारिश करती है। संयोजित कोड तेजी से अंतरिक्ष मिशनों के पक्ष में होते जा रहे हैं, तथा टर्बो कोड या एलडीपीसी कोड जैसे अधिक शक्तिशाली कोड द्वारा प्रतिस्थापित किए जाते हैं।
आयोजित किए गए विभिन्न प्रकार के गहरे अंतरिक्ष तथा कक्षीय मिशन सुझाव देते हैं कि एक आकार-फिट-सभी त्रुटि संशोधन प्रणाली खोजने की कोशिश करना एक सतत समस्या होगी। पृथ्वी के करीब के मिशनों के लिए, संचार चैनल में रव (नॉइज़) की प्रकृति उससे भिन्न होती है जो एक अंतरग्रहीय मिशन पर अंतरिक्ष यान अनुभव करता है। इसके अतिरिक्त, जैसे ही एक अंतरिक्ष यान पृथ्वी से अपनी दूरी बढ़ाता है, रव (नॉइज़) के लिए संशोधन की समस्या तथा अधिक कठिन हो जाती है।
उपग्रह प्रसारण
टेलीविजन (नए चैनल और हाई-डेफिनिशन टेलीविजन सहित) और आईपी डेटा देने की इच्छा उपग्रह ट्रांसपोंडर बैंडविड्थ की मांग को जारी रखे हुए है। ट्रांसपोंडर की उपलब्धता और बैंडविड्थ बाधाओं ने इस वृद्धि को सीमित कर दिया है। ट्रांसपोंडर क्षमता चयनित मॉडुलन योजना के अनुपात और एफईसी द्वारा खपत की गई बिजली से निर्धारित होती है।
डेटा संचयन
डेटा संचयन मीडिया की विश्वसनीयता में संशोधन के लिए त्रुटि का पता लगाने तथा संशोधन कोड का उपयोग अक्सर किया जाता है।[19] 1951 में पहले मैग्नेटिक टेप डेटा संचयन पर सिंगल-बिट त्रुटियों का पता लगाने में सक्षम पैरिटी ट्रैक मौजूद था। समूह कोडित रिकॉर्डिंग टेप में उपयोग किया जाने वाला इष्टतम आयताकार कोड न केवल पता लगाता है बल्कि सिंगल-बिट त्रुटियों को ठीक भी करता है। कुछ फ़ाइल स्वरूपों, विशेष रूप से संग्रह स्वरूपों में भ्रष्टाचार तथा छंटनी का पता लगाने के लिए एक चेकसम (अक्सर सीआरसी32) सम्मिलित होता है तथा अपमिश्रित डेटा के हिस्से को पुनर्प्राप्त करने के लिए शब्दातिरेक या समता फ़ाइलों को नियोजित कर सकता है। रीड-सोलोमन कोड कॉम्पैक्ट डिस्क में खरोंच के कारण होने वाली त्रुटियों को ठीक करने के लिए उपयोग किए जाते हैं।
आधुनिक हार्ड ड्राइव्स रीड-सोलोमन कोड का उपयोग सेक्टर रीड में छोटी त्रुटियों का पता लगाने तथा उन्हें ठीक करने के लिए करते हैं, तथा विफल सेक्टरों से अपमिश्रित डेटा को पुनर्प्राप्त करने के लिए तथा उस डेटा को अतिरिक्त क्षेत्रों में संग्रहीत करते हैं।[20] जब हार्ड ड्राइव पूरी तरह से विफल हो जाता है, तो डेटा को पुनर्प्राप्त करने के लिए आरएआईडी सिस्टम विभिन्न प्रकार की त्रुटि संशोधन तकनीकों का उपयोग करता है। जेडएफएस या बीटीआरएफएस जैसे फाइल सिस्टम, साथ ही कुछ आरएआईडी कार्यान्वयन, डेटा स्क्रबिंग तथा रिसिल्वरिंग का समर्थन करते हैं, जो खराब ब्लॉकों का पता लगाने की अनुमति देता है तथा (उम्मीद है) उनका उपयोग करने से पहले उन्हें पुनर्प्राप्त किया जा सकता है।[21] पुनर्प्राप्त डेटा को ठीक उसी भौतिक स्थान पर फिर से लिखा जा सकता है, हार्डवेयर के एक ही टुकड़े पर कहीं तथा ब्लॉक करने के लिए, या डेटा को प्रतिस्थापन हार्डवेयर पर फिर से लिखा जा सकता है।
त्रुटि-संशोधन मेमोरी
डायनेमिक रैंडम-एक्सेस मेमोरी (डीरैम) त्रुटि-संशोधन कोड पर निर्भर करके सॉफ्ट त्रुटियों के विरुद्ध मजबूत सुरक्षा प्रदान कर सकती है। ऐसी त्रुटि-संशोधन करने वाली मेमोरी, जिसे ईसीसी या ईडीएसी-संरक्षित मेमोरी के रूप में जाना जाता है, मिशन-महत्वपूर्ण अनुप्रयोगों के लिए विशेष रूप से वांछनीय है, जैसे वैज्ञानिक कंप्यूटिंग, वित्तीय, चिकित्सा, आदि के साथ-साथ अंतरिक्ष में बढ़ते विकिरण के कारण अलौकिक अनुप्रयोग भी।
त्रुटि-संशोधन मेमोरी नियंत्रक पारंपरिक रूप से हैमिंग कोड का उपयोग करते हैं, हालांकि कुछ त्रि मॉड्यूलर शब्दातिरेक का उपयोग करते हैं। अंतग्रंथन एक एकल ब्रह्मांडीय किरण के प्रभाव को वितरित करने की अनुमति देता है जो अपने अस पास के बिट्स को अलग-अलग शब्दों से जोड़कर कई शारीरिक रूप से पड़ोसी बिट्स को कई शब्दों में संभावित रूप से परेशान करता है। जब तक सिंगल-इवेंट अपसेट (एसईयू) एक्सेस के बीच किसी विशेष शब्द में एरर थ्रेशोल्ड (उदाहरण के लिए, एक त्रुटि) से अधिक नहीं होता है, तब तक इसे ठीक किया जा सकता है (उदाहरण के लिए, एक बिट त्रुटि संशोधन कोड द्वारा), तथा एक एरर-फ्री मेमोरी सिस्टम के भ्रम को बनाए रखा जा सकता है। [22]
ईसीसी मेमोरी को संचालित करने के लिए आवश्यक हार्डवेयर प्रदान करने के अलावा, ऑपरेटिंग सिस्टम में सामान्यतः संबंधित रिपोर्टिंग सुविधाएं होती हैं, जिनका उपयोग क्षणिक त्रुटि (सॉफ्ट एरर) को पारदर्शी रूप से पुनर्प्राप्त करने पर सूचनाएं प्रदान करने के लिए किया जाता है। एक उदाहरण लिनक्स कर्नेल का ईडीएसी सबसिस्टम है (जिसे पहले ब्लूस्मोक के नाम से जाना जाता था), जो संगणक सिस्टम के अंदर त्रुटि-जांच-सक्षम घटकों से डेटा एकत्र करता है; ईसीसी मेमोरी से संबंधित घटनाओं को एकत्र करने तथा वापस रिपोर्ट करने के अलावा, यह पीसीआई बस में पाए गए सहित अन्य चेकसमिंग त्रुटियों का भी समर्थन करता है।[23][24][25] कुछ प्रणालियाँ[specify] भी संशोधनी न जाने योग्य बनने से पहले त्रुटियों को पकड़ने तथा ठीक करने के लिए मेमोरी स्क्रबिंग का समर्थन करती हैं।
यह भी देखें
- बर्गर कोड
- बर्स्ट त्रुटि-संशोधन कोड
- ईसीसी मेमोरी, एक प्रकार का संगणक डेटा संचयन
- लिंक अनुकूलन
- एल्गोरिदम की सूची § त्रुटि संसूचन और संशोधन
- हैश फ़ंक्शन की सूची
संदर्भ
- ↑ 1.0 1.1 "Masorah". Jewish Encyclopedia.
- ↑ Pratico, Gary D.; Pelt, Miles V. Van (2009). Basics of Biblical Hebrew Grammar: Second Edition. Zondervan. ISBN 978-0-310-55882-8.
- ↑ Mounce, William D. (2007). Greek for the Rest of Us: Using Greek Tools Without Mastering Biblical Languages. Zondervan. p. 289. ISBN 978-0-310-28289-1.
- ↑ Mishneh Torah, Tefillin, Mezuzah, and Sefer Torah, 1:2. Example English translation: Eliyahu Touger. The Rambam's Mishneh Torah. Moznaim Publishing Corporation.
- ↑ Brian M. Fagan (5 December 1996). "Dead Sea Scrolls". The Oxford Companion to Archaeology. Oxford University Press. ISBN 0195076184.
- ↑ Thompson, Thomas M. (1983), From Error-Correcting Codes through Sphere Packings to Simple Groups, The Carus Mathematical Monographs (#21), The Mathematical Association of America, p. vii, ISBN 0-88385-023-0
- ↑ Shannon, C.E. (1948), "A Mathematical Theory of Communication", Bell System Technical Journal, 27 (3): 379–423, doi:10.1002/j.1538-7305.1948.tb01338.x, hdl:10338.dmlcz/101429, PMID 9230594
- ↑ Golay, Marcel J. E. (1949), "Notes on Digital Coding", Proc.I.R.E. (I.E.E.E.), 37: 657
- ↑ Gupta, Vikas; Verma, Chanderkant (November 2012). "Error Detection and Correction: An Introduction". International Journal of Advanced Research in Computer Science and Software Engineering. 2 (11). S2CID 17499858.
- ↑ 10.0 10.1 A. J. McAuley, Reliable Broadband Communication Using a Burst Erasure Correcting Code, ACM SIGCOMM, 1990.
- ↑ Shah, Pradeep M.; Vyavahare, Prakash D.; Jain, Anjana (September 2015). "Modern error correcting codes for 4G and beyond: Turbo codes and LDPC codes". 2015 Radio and Antenna Days of the Indian Ocean (RADIO): 1–2. doi:10.1109/RADIO.2015.7323369. ISBN 978-9-9903-7339-4. S2CID 28885076. Retrieved 22 May 2022.
- ↑ "IEEE SA - IEEE 802.11ac-2013". IEEE Standards Association (in English).
- ↑ "Transition to Advanced Format 4K Sector Hard Drives | Seagate US". Seagate.com (in English). Retrieved 22 May 2022.
- ↑ Frank van Gerwen. "Numbers (and other mysterious) stations". Retrieved 12 March 2012.
- ↑ Gary Cutlack (25 August 2010). "Mysterious Russian 'Numbers Station' Changes Broadcast After 20 Years". Gizmodo. Retrieved 12 March 2012.
- ↑ Ben-Gal I.; Herer Y.; Raz T. (2003). "Self-correcting inspection procedure under inspection errors" (PDF). IIE Transactions. IIE Transactions on Quality and Reliability, 34(6), pp. 529-540. Archived from the original (PDF) on 2013-10-13. Retrieved 2014-01-10.
- ↑ K. Andrews et al., The Development of Turbo and LDPC Codes for Deep-Space Applications, Proceedings of the IEEE, Vol. 95, No. 11, Nov. 2007.
- ↑ Huffman, William Cary; Pless, Vera S. (2003). Fundamentals of Error-Correcting Codes. Cambridge University Press. ISBN 978-0-521-78280-7.
- ↑ Kurtas, Erozan M.; Vasic, Bane (2018-10-03). Advanced Error Control Techniques for Data Storage Systems (in English). CRC Press. ISBN 978-1-4200-3649-7.[permanent dead link]
- ↑ Scott A. Moulton. "My Hard Drive Died". Archived from the original on 2008-02-02.
- ↑ Qiao, Zhi; Fu, Song; Chen, Hsing-Bung; Settlemyer, Bradley (2019). "Building Reliable High-Performance Storage Systems: An Empirical and Analytical Study". 2019 IEEE International Conference on Cluster Computing (CLUSTER): 1–10. doi:10.1109/CLUSTER.2019.8891006. ISBN 978-1-7281-4734-5. S2CID 207951690.
- ↑ "Using StrongArm SA-1110 in the On-Board Computer of Nanosatellite". Tsinghua Space Center, Tsinghua University, Beijing. Archived from the original on 2011-10-02. Retrieved 2009-02-16.
- ↑ Jeff Layton. "Error Detection and Correction". Linux Magazine. Retrieved 2014-08-12.
- ↑ "EDAC Project". bluesmoke.sourceforge.net. Retrieved 2014-08-12.
- ↑ "Documentation/edac.txt". Linux kernel documentation. kernel.org. 2014-06-16. Archived from the original on 2009-09-05. Retrieved 2014-08-12.
इस पृष्ठ में अनुपलब्ध आंतरिक कड़ियों की सूची
अग्रिम पठन
- Shu Lin; Daniel J. Costello, Jr. (1983). Error Control Coding: Fundamentals and Applications. Prentice Hall. ISBN 0-13-283796-X.
- Softईसीसी: A System for Software Memory Integrity Checking
- A Tunable, Software-based डीरैम Error Detection and Correction Library for HPC
- Detection and Correction of Silent Data Corruption for Large-Scale High-Performance Computing
बाहरी संबंध
- The on-line textbook: Information Theory, Inference, and Learning Algorithms, by David J.C. MacKay, contains chapters on elementary error-correcting codes; on the theoretical limits of error-correction; and on the latest state-of-the-art error-correcting codes, including low-density parity-check codes, turbo codes, and fountain codes.
- ईसीसी Page - implementations of popular ईसीसी encoding and decoding routines
