समता जांच मैट्रिक्स
GF(2) पर प्रत्येक रैखिक कोड — केवल 0 और 1 के साथ क्षेत्र, अंकगणित मॉड्यूलो 2 — का एक समता जांच मैट्रिक्स H होता है। (7,4) हैमिंग कोड के लिए, H एक 3×7 मैट्रिक्स है जिसके स्तंभ 1 से 7 तक के बाइनरी प्रतिनिधित्व हैं:
``
H = [ 0 0 0 1 1 1 1 ] ← स्थिति संख्या का बिट 2
[ 0 1 1 0 0 1 1 ] ← स्थिति संख्या का बिट 1
[ 1 0 1 0 1 0 1 ] ← स्थिति संख्या का बिट 0
``
H का कॉलम j, j का बाइनरी प्रतिनिधित्व है। यही कारण है कि सिंड्रोम s = Hr सीधे त्रुटि की स्थिति का नाम देता है।
मानचित्र H: GF(2)^7 → GF(2)^3 एक रैखिक मानचित्र है (मैट्रिक्स गुणन मॉड 2)। इसका कर्नल ker(H) = { r : Hr = 0 } बिल्कुल मान्य कोडवर्ड का सेट है।
आयाम गणना: dim(ker H) = 7 − rank(H) = 7 − 3 = 4। तो 2^4 = 16 कोडवर्ड हैं। यह 4 संदेश बिट की पुष्टि करता है।
कर्नल के रूप में कोड
एक शब्द c ∈ {0,1}^7 एक मान्य कोडवर्ड है यदि और केवल यदि Hc = 0 (मॉड 2)। यह एक रैखिक कोड की परिभाषित समीकरण है।
उदाहरण: c = 0011001। Hc मॉड 2 की जांच करें:
``
पंक्ति 1: 0·0+0·0+0·1+1·1+1·0+1·0+1·1 = 0+0+0+1+0+0+1 = 2 ≡ 0
पंक्ति 2: 0·0+1·0+1·1+0·1+0·0+1·0+1·1 = 0+0+1+0+0+0+1 = 2 ≡ 0
पंक्ति 3: 1·0+0·0+1·1+0·1+1·0+0·0+1·1 = 0+0+1+0+0+0+1 = 2 ≡ 0
``
Hc = 000। तो 0011001 एक मान्य कोडवर्ड है।
कोड के कोसेट्स
कोडवर्ड C = ker(H) GF(2)^7 का एक उप-समूह बनाते हैं। GF(2)^7 में प्रत्येक अन्य शब्द बिल्कुल एक कोसेट C के अंतर्गत आता है।
कोसेट परिभाषा: किसी भी शब्द e के लिए, कोसेट C + e = { c + e : c ∈ C }।
दो शब्द समान कोसेट के अंतर्गत आते हैं यदि और केवल यदि उनका अंतर एक कोडवर्ड है — समकक्ष रूप से, यदि उनके पास समान सिंड्रोम है: H(r₁) = H(r₂) iff H(r₁ − r₂) = 0 iff r₁ − r₂ ∈ C।
सिंड्रोम मानचित्र H एक समरूपता को प्रेरित करता है GF(2)^7 / C ≅ GF(2)^3। |C| = 16 और |GF(2)^7| = 128 के साथ: बिल्कुल 128/16 = 8 कोसेट्स हैं, GF(2)^3 में प्रत्येक सिंड्रोम मान के लिए एक।
मानक सरणी: प्रति कोसेट एक कोसेट नेता सूचीबद्ध करें — उस कोसेट में न्यूनतम हैमिंग वजन वाला शब्द। एकल-त्रुटि सुधार के लिए, प्रत्येक गैर-शून्य सिंड्रोम विशिष्ट रूप से एक वजन-1 त्रुटि पैटर्न (सात स्थानों में से एक में एक 1) के अनुरूप है। यही कारण है कि 7 त्रुटि पैटर्न + 1 कोई त्रुटि नहीं = 8 कोसेट्स = 2^3।
कोसेट नेताओं के माध्यम से डिकोडिंग
डिकोडिंग एल्गोरिदम: r प्राप्त करें → s = Hr की गणना करें → कोसेट नेता e_s को खोजें (सिंड्रोम s के लिए विहित त्रुटि) → r − e_s = r + e_s (GF(2) में समान) का आउटपुट।
(7,4) कोड के लिए, 8 कोसेट नेता हैं: 0000000 (सिंड्रोम 000), 1000000 (सिंड्रोम 001), 0100000 (सिंड्रोम 010), 0010000 (सिंड्रोम 011), 0001000 (सिंड्रोम 100), 0000100 (सिंड्रोम 101), 0000010 (सिंड्रोम 110), 0000001 (सिंड्रोम 111)।
क्यों (7,4) पूर्ण है
एक कोड C ⊆ GF(2)^n न्यूनतम दूरी 3 के साथ सभी एकल त्रुटियों को सुधारता है। प्रत्येक कोडवर्ड c के पास त्रिज्या 1 की हैमिंग गेंद है: केंद्र c और इसके n तत्काल पड़ोसी (वजन-1 त्रुटि पैटर्न)। गेंद की मात्रा = 1 + n।
n = 7 के लिए: गेंद की मात्रा = 8। 16 कोडवर्डों के साथ: 16 × 8 = 128 = 2^7। गेंदें GF(2)^7 को पूरी तरह से टाइल करती हैं — कोई बिंदु अनावृत नहीं, कोई बिंदु दो बार आवृत नहीं।
यह पूर्ण कोड की परिभाषा है: M · Vol(n, t) = 2^n। पूर्ण एकल-त्रुटि-सुधारने वाले कोड (t=1) केवल विशिष्ट मापदंडों के लिए मौजूद हैं: (7,4), (15,11), (23,12) (बाइनरी गोलय कोड), और तुच्छ रूप से n = 2^r − 1, k = n − r किसी भी r ≥ 2 के लिए।
ज्यामिति: GF(2)^7 कोड के कार्य के तहत बिल्कुल 8 कक्षाओं में विघटित होता है एक कोसेट विभाजन के रूप में। प्रत्येक कक्षा एक कोसेट है; प्रत्येक कोसेट का एक अद्वितीय सिंड्रोम है। सिंड्रोम मानचित्र H कोसेट्स से GF(2)^3 तक एक द्विवचन है।
गणना तर्क
n = 2^r − 1 बिट के साथ r समता जांच बिट्स के साथ एक पूर्ण एकल-त्रुटि-सुधारने वाले कोड के लिए:
- कोडवर्डों की संख्या: M = 2^k = 2^(n−r)
- गेंद की मात्रा: Vol(n, 1) = 1 + n = 1 + 2^r − 1 = 2^r
- कुल आवृत: M × Vol = 2^(n−r) × 2^r = 2^n ✓
तथ्य यह है कि Vol(n,1) = 2^r जब n = 2^r − 1 यही है जो इन लंबाइयों पर पूर्ण कोड्स को संभव बनाता है। अन्य लंबाइयों पर, 1 + n 2 की शक्ति नहीं है, और पूर्ण एकल-त्रुटि-सुधारने वाले बाइनरी कोड मौजूद नहीं हो सकते।
जेनरेटर मैट्रिक्स & द्वैत
समता जांच मैट्रिक्स H कर्नल के माध्यम से कोड को परिभाषित करता है। इसका दोहरा: एक जेनरेटर मैट्रिक्स G जिसकी पंक्तियां ker(H) के लिए एक आधार बनाती हैं।
(7,4) कोड के लिए: G एक 4×7 मैट्रिक्स है। कोई भी कोडवर्ड c = mG किसी संदेश वेक्टर m ∈ GF(2)^4 के लिए। G की पंक्तियां कोड को विस्तारित करती हैं; H की पंक्तियां कोड के null स्पेस को विस्तारित करती हैं।
मुख्य संबंध: HG^T = 0 (मॉड 2)। G की प्रत्येक पंक्ति ker(H) में है; H की प्रत्येक पंक्ति G की प्रत्येक पंक्ति को शून्य करती है।
दोहरा कोड: C⊥ = ker(G^T) = image(H^T)। (7,4) कोड के लिए, दोहरा एक (7,3) कोड है — एक [7,3,4] कोड न्यूनतम दूरी 4 के साथ।
द्वैत की ज्यामिति: C और C⊥ GF(2)^7 के लंबवत उप-स्थान हैं। संपूर्ण स्पेस कोड, इसके कोसेट्स, और दोहरी संरचना में विघटित होता है जो सिंड्रोम मानचित्र एन्कोड करता है।