गलतियाँ क्यों होती हैं?
बिट्स बिजली के स्पंद, प्रकाश की झलक या रेडियो तरंगों के रूप में चलते हैं। शोर (गर्मी, बिजली कड़कना, डिस्क पर खरोंच, कमज़ोर सिग्नल) 0 को 1 या 1 को 0 बना सकता है। छोटा बदलाव भी बड़ी दिक्कत है: 1 0 1 1 यानी 11, पर 1 1 1 1 यानी 15।
दो विचार हमारी मदद करते हैं:
- त्रुटि की पहचान (error detection): पता लगाना कि गलती हुई।
- त्रुटि का सुधार (error correction): यह भी खोजना कि कौन-सा बिट ग़लत है और उसे ठीक करना।
दोनों के लिए अतिरिक्तता (redundancy) चाहिए: ऐसे अतिरिक्त बिट जिनमें नया डेटा नहीं, सिर्फ़ जाँच की जानकारी होती है।
समता बिट: एक गलती की पहचान
सम समता (even parity) में हम एक बिट ऐसे जोड़ते हैं कि कुल 1 की संख्या (डेटा और समता बिट मिलाकर) सम हो।
- डेटा 1 0 1 1 में तीन 1 हैं। समता बिट 1 जोड़ो। अब चार 1।
- डेटा 1 0 0 1 में दो 1 हैं। समता बिट 0 जोड़ो। अब भी दो 1।
पाने वाला 1 गिनता है। सम मतलब "ठीक लगता है"। विषम मतलब "गलती!" (विषम समता में नियम उलटा है: कुल संख्या विषम होनी चाहिए।)
सीमाएँ: एक समता बिट 1, 3, 5 ... पलटे बिट (विषम संख्या) पकड़ता है, पर 2, 4 ... पलटे बिट चूक जाता है, क्योंकि गिनती फिर सम हो जाती है। यह भी नहीं बता पाता कि कौन-सा बिट ग़लत है, इसलिए संदेश दोबारा भेजना पड़ता है।
पंक्ति और स्तंभ की समता: खोजना और सुधारना
डेटा बिट्स को ग्रिड में रखो। हर पंक्ति के अंत में और हर स्तंभ के नीचे एक समता बिट जोड़ो (और कोने में एक बिट)। अगर एक बिट ग़लत हो, तो ठीक एक पंक्ति और एक स्तंभ विषम हो जाते हैं। ग़लत बिट उनके कटान पर होता है, इसलिए पाने वाला उसे वापस पलट देता है। यह एक आसान त्रुटि सुधार कोड है।
- केवल एक पंक्ति विषम: ग़लत बिट उसी पंक्ति का अपना समता बिट है।
- केवल एक स्तंभ विषम: ग़लत बिट उसी स्तंभ का समता बिट है।
- दो बिट ग़लत: पकड़े जाते हैं, पर ठीक से सुधरें यह ज़रूरी नहीं।
r पंक्ति और c स्तंभ वाले डेटा ग्रिड में r × c डेटा बिट और (r + 1)(c + 1) − r × c जाँच-बिट जाते हैं।
हैमिंग कोड: होशियार जाँच-बिट
रिचर्ड हैमिंग ने ऐसा कोड बनाया जिसमें हर जाँच-बिट स्थानों के अलग समूह को देखता है। जाँच-बिट स्थान 1, 2, 4, 8 ... पर रहते हैं और मिलकर एक ग़लत बिट की ठीक जगह बता देते हैं (फ़ेल हुई जाँचों को जोड़ने पर स्थान की संख्या मिलती है)। m डेटा बिट के लिए r जाँच-बिट चाहिए जहाँ 2r ≥ m + r + 1। 4 डेटा बिट के लिए r = 3, यानी मशहूर हैमिंग (7,4) कोड में कुल 7 बिट होते हैं। यह बड़े ग्रिड से कहीं कम जाँच-बिट में किसी भी एक पलटे बिट को सुधार देता है।
प्रसारण समय
चैनल की गति बिट प्रति सेकंड (bit/s) में नापी जाती है। संदेश भेजने का समय है
समय = बिट की संख्या ÷ गति
जाँच-बिट भी भेजे जाते हैं, इसलिए वे समय बढ़ाते हैं। 16 बिट (9 डेटा + 7 जाँच) को 8 bit/s पर भेजने में 2 s लगते हैं; अकेले 9 डेटा बिट में 1.125 s लगते। अगर पाने वाले को गलती मिले और वह दोबारा माँगे, तो संदेश दो बार जाता है और समय दोगुना हो जाता है। पहचानने वाला कोड (सस्ता) और कभी-कभी दोबारा भेजना, या सुधारने वाला कोड (ज़्यादा बिट पर दोबारा भेजना नहीं): यह समय और सुरक्षा के बीच का सौदा है।
इकाइयाँ याद रखो: 1 बाइट = 8 बिट, और 1 kbit/s = 1000 bit/s।
करके देखो
7 दोस्तों के साथ करके देखो। हर दोस्त 0 या 1 वाला कार्ड उठाए। 1 गिनो: संख्या सम चाहिए, तो आठवाँ दोस्त (समता) 0 या 1 का कार्ड उठाकर उसे सम बनाए। अब एक दोस्त चुपके से अपना कार्ड पलट दे। फिर गिनो: विषम! गलती पकड़ ली। अब 9 दोस्तों को 3 × 3 ग्रिड में खड़ा करो, पंक्ति-स्तंभ के सहायकों के साथ, और देखो कौन-सी पंक्ति और कौन-सा स्तंभ विषम है, उसी से पलटा कार्ड मिल जाएगा। ऊपर के 3D में पहली स्लाइडर से 16 में से कोई भी बिट पलटो और पढ़ो कि ग्रिड क्या कहता है।
मुख्य सूत्र और परिभाषाएँ
- सम समता: 1 की कुल संख्या (डेटा + समता बिट) सम होती है
- समता बिट = (डेटा में 1 की संख्या) mod 2
- प्रसारण समय = बिट की संख्या ÷ गति (bit/s)
- हैमिंग: 2^r ≥ m + r + 1 (m डेटा बिट, r जाँच-बिट)
- r × c डेटा ग्रिड कुल (r + 1)(c + 1) बिट भेजता है
- 1 बाइट = 8 बिट; 1 kbit/s = 1000 bit/s
हल किए गए उदाहरण
1. डेटा 1 1 0 1 0 0 1 के लिए सम समता बिट निकालो।
1 गिनो: 1 + 1 + 0 + 1 + 0 + 0 + 1 = 4। यह पहले से सम है, इसलिए समता बिट 0। संदेश: 1 1 0 1 0 0 1 0।
2. पाने वाले को सम समता के साथ 1 0 1 1 0 1 0 1 मिला (आख़िरी बिट समता बिट है)। क्या गलती है?
1 गिनो: 1 + 0 + 1 + 1 + 0 + 1 + 0 + 1 = 5। पाँच विषम है, जबकि सम समता में सम चाहिए। इसलिए गलती पकड़ी गई (विषम संख्या में बिट पलटे)।
3. डेटा 1 0 1 1 समता बिट 1 के साथ भेजा गया (1 0 1 1 1)। दो बिट पलटे और 0 1 1 1 1 मिला। क्या समता जाँच गलती पकड़ेगी?
0 1 1 1 1 में 1 की गिनती 4 है, यानी सम। जाँच गलती चूक गई, क्योंकि दो बिट पलटे (पहला 1 से 0 और दूसरा 0 से 1)। एक समता बिट सम संख्या में पलटे बिट नहीं पकड़ता। अगर सिर्फ़ पहला बिट पलटता, यानी 0 0 1 1 1, तो 1 की गिनती 3 होती, विषम, और गलती पकड़ी जाती।
4. 1 200 बिट को 300 bit/s पर भेजने में कितना समय लगेगा?
समय = बिट ÷ गति = 1200 ÷ 300 = 4 s।
5. 600 बाइट की फ़ाइल 2 400 bit/s पर भेजी जाती है। कितना समय लगेगा? हर बाइट में एक समता बिट जोड़ें तो?
600 बाइट = 600 × 8 = 4800 बिट। समय = 4800 ÷ 2400 = 2 s। हर बाइट में समता बिट जोड़ने पर हर बाइट 9 बिट: 600 × 9 = 5400 बिट। समय = 5400 ÷ 2400 = 2.25 s। जाँच की कीमत 0.25 s।
6. 3 × 3 डेटा ग्रिड में पंक्ति-स्तंभ समता (कोने के बिट सहित) है। मिले ग्रिड में पंक्ति 3 और स्तंभ 1 विषम हैं। ग़लत बिट कहाँ है और क्या करोगे?
ग़लत बिट वहाँ है जहाँ पंक्ति 3 और स्तंभ 1 कटते हैं: पंक्ति 3, स्तंभ 1। उस बिट को वापस पलट दो (0 से 1 या 1 से 0)। कोड ने गलती सुधार दी, दोबारा भेजना नहीं पड़ा।
7. 11 डेटा बिट के लिए हैमिंग कोड को कितने जाँच-बिट चाहिए?
हमें 2^r ≥ m + r + 1 चाहिए, m = 11। r = 3: 8 ≥ 15? नहीं। r = 4: 16 ≥ 16? हाँ। इसलिए r = 4 जाँच-बिट; कोड शब्द 15 बिट का है (हैमिंग (15,11))।
आम गलतियाँ
- यह सोचना कि समता बिट गलती सुधार सकता है। वह सिर्फ़ पहचानता है कि गलती हुई (विषम संख्या में पलटने पर)। सुधार के लिए ग्रिड या हैमिंग कोड चाहिए।
- यह भूलना कि दो पलटे बिट एक समता जाँच में एक-दूसरे को काट देते हैं, इसलिए गलती छूट जाती है।
- समता बिट को गिनती से बाहर रखना। समता बिट भी संदेश का हिस्सा है: डेटा और समता बिट, सब मिलाकर 1 गिनो।
- प्रसारण समय निकालते समय जाँच-बिट भूल जाना। समय = (डेटा बिट + जाँच-बिट) ÷ गति। बाइट और बिट भी न मिलाओ: बाइट को 8 से गुणा करो।