रीड-सोलोमन कोड के साथ जानकारी कोडिंग के लिए गैलोज़ फील्ड अंकगणित

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


रीड-सोलोमन कोड के साथ कोडिंग जानकारी के लिए समर्पित हब पर एक पोस्ट है , लेकिन एक उदाहरण के लिए लेखक एक साधारण गैलोजेन फ़ील्ड का उपयोग करता है। यह लेख विशेष रूप से GF (2 ^ m) विस्तारित गैलोज़ फ़ील्ड के साथ काम का वर्णन करता है, जो डिजिटल जानकारी के लिए तर्कसंगत रूप से उपयोग किया जाता है। एन्कोडिंग, डिकोडिंग, त्रुटि सुधार का मेरा समान कार्यान्वयन यहां पाया जा सकता है ।

रीड-सोलोमन कोड के साथ काम करते समय, निरर्थक वर्णों का प्रतिशत डेटा की वसूली योग्य मात्रा का 2 गुना है। मुझे एक उदाहरण के साथ समझाता हूं: यदि हमारे पास 10 वर्ण हैं और उनमें से 3 (मूल जानकारी का 30%) में त्रुटियों को पुनर्प्राप्त करने में सक्षम होना चाहते हैं, तो हमें 10 + 3 * 2 = 16 वर्णों को संग्रहीत करने की आवश्यकता है। हम प्रत्येक चर का नाम देते हैं: n = 10, सूचना प्रतीकों की संख्या; f = 3, पुनर्प्राप्त करने योग्य वर्णों की संख्या; जी = 16, एन्कोडेड अनुक्रम की लंबाई। इस प्रकार, सूत्र निम्नानुसार लिखे जा सकते हैं: g = n + f * 2।

फ़ील्ड्स गैलोज़

डेटा को एन्कोडिंग और डिकोड करने के दौरान जानकारी के साथ काम करने के लिए, सभी अंकगणित संचालन गैलोज़ क्षेत्रों में किए जाते हैं। तथाकथित बहुपद अंकगणित या गैलोज क्षेत्रों के अंकगणित को लागू किया जाता है। इस प्रकार, किसी भी ऑपरेशन का परिणाम भी इस क्षेत्र का एक तत्व है। एक विशेष गैलोज़ क्षेत्र में संख्याओं की एक निश्चित सीमा होती है। क्षेत्र की विशेषता को कुछ अभाज्य संख्या p कहा जाता है। फील्ड ऑर्डर, अर्थात्। इसके तत्वों की संख्या एक निश्चित प्राकृतिक डिग्री है जिसका नाम शाम है, जहाँ एम.एन.एन. एम = 1 के लिए, क्षेत्र को सरल कहा जाता है। ऐसे मामलों में जहां एम> 1, एक क्षेत्र के गठन के लिए, डिग्री मीटर की एक बहुपद बनाने की भी आवश्यकता होती है, ऐसे क्षेत्र को विस्तारित कहा जाता है। जीएफ (पी ^ एम) गैलोज क्षेत्र का पदनाम है।

डिजिटल डेटा के साथ काम करने के लिए, p = 2 का उपयोग फ़ील्ड विशेषता के रूप में करना स्वाभाविक है। M = 1 के लिए, कोड अनुक्रम का तत्व m = 8 - 8 बिट्स के लिए होगा, जो कि एक बाइट है। दरअसल, रीड-सोलोमन कोड जो बाइट के साथ काम करते हैं, सबसे आम हैं।

एन्कोडिंग और डिकोडिंग के संचालन के लिए आगे बढ़ने से पहले, हम GF (2: 3) के उदाहरण का उपयोग करके गैलोज़ के खेतों के अंकगणित को समझेंगे। इस क्षेत्र में 0 से 7 तक संख्याएँ हैं।

जोड़ आपरेशन

सबसे सरल जोड़ ऑपरेशन है, जो एक साधारण बिटवाइज़ जोड़ मोडुलो 2 (XOR) है।

उदाहरण: 5 + 3 = 110 = 6

गुणन क्रिया

दुर्भाग्य से, गुणन का संचालन बहुत अधिक जटिल है, इसे पूरा करने के लिए, संख्याओं को बहुपद रूप में परिवर्तित करना आवश्यक है।

उदाहरण: 5 = 101 = 1: x ^ 2 + 0 + x ^ 1 + 1 = x ^ 0 = x ^ 2 1 1

जैसा कि आप देख सकते हैं, बहुपद रूप में संख्या एक बहुपद है जिसका गुणांक संख्या के द्विआधारी प्रतिनिधित्व में अंकों के मान हैं।

बहुपद रूप में दो संख्याओं को गुणा करें:
5 ∙ 7 = (x ^ 2 + 1) x (x ^ 2 + x + 1) = x ^ 4 + x ^ 3 + x ^ 2 + x ^ 2 + x + 1 = x ^ 4 + x ^ 3 + x + 1 = 11011 = 27

तो, सबसे पहले, यह ध्यान दिया जाना चाहिए कि बहुपद रूप में भी मोडुलो 2 को जोड़ा जाता है, इसलिए x ^ 2 + x ^ 2 = 0। दूसरे, गुणन 27 का परिणाम उपयोग किए गए फ़ील्ड GF (2 ^ 3) में शामिल नहीं है (इसमें 0 से 7 तक संख्याएं भी हैं, जैसा कि ऊपर बताया गया है)। इस समस्या से निपटने के लिए, एक उत्पन्न बहुपद का उपयोग करना आवश्यक है। बहुपद उत्पन्न करने वाला विडंबनापूर्ण है, अर्थात, सरल (अभाज्य संख्याओं के साथ समानता से यह 1 और अपने आप से विभाज्य है)। गाल्वा के खेतों के अंकगणित में, एक इरेड्यूसबल बहुपद primes का एक एनालॉग है। उदाहरण के लिए, हम उत्पन्न बहुपद f (x) = x ^ 3 + x + 1 का उपयोग करते हैं।

यह भी माना जाता है कि x समीकरण f (x) = x ^ 3 + x + 1 = 0 को संतुष्ट करता है

गुणन उदाहरण पर वापस जाएं:

उसी परिणाम को बहुपद के शेष भाग के रूप में प्राप्त किया जा सकता है जो उत्पन्न बहुपद से गुणा करके प्राप्त किया जाता है:


चलो एक गुणन तालिका बनाते हैं:

विभाग संचालन

बहुपद रूप में विभाजन के संचालन को समझना संभव है, लेकिन यह मुश्किल है। इसलिए, गुणा तालिका के अनुसार इसे लागू करना बेहतर है।

उदाहरण: 6: 5 = 7

बहुत महत्व की बात यह है कि गैलोज क्षेत्र के तत्वों की डिग्री की तालिका है। गुणन के रूप में, शक्ति बढ़ाने को बहुपद रूप में भी किया जाता है।

उदाहरण: 5 ^ 2 = 〖(x ^ 2 + 1) = ^ 2 = x ^ 4 + x ^ 2 + x ^ 2 + 1 = x ^ 4 + x ^ 2 + x + x ^ 2 + x + 1 = x x (x ^ 3 + x + 1) = x ^ 2 + x + 1 = 111 = 7

इस प्रकार, हम डिग्री की एक तालिका संकलित करते हैं:


डिग्री तालिका चक्रीय है: सातवीं डिग्री शून्य से मेल खाती है, इसलिए आठवीं पहली से मेल खाती है, आदि। आप चाहें तो इसे चेक कर सकते हैं।

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



जिन क्षेत्रों पर हम विचार कर रहे हैं, वह है, विशेषता 2 के साथ, हमेशा 2 चुनें। आदिम सदस्य के रूप में, इसकी संपत्ति को देखते हुए, क्षेत्र के किसी भी तत्व को आदिम सदस्य की डिग्री के संदर्भ में व्यक्त किया जा सकता है।
उदाहरण: 5 = 26, 7 = 25

इस संपत्ति का उपयोग करना, और डिग्री तालिका की चक्रीयता को ध्यान में रखते हुए, हम संख्याओं को फिर से गुणा करने का प्रयास करेंगे:
5 5 7 = 2 ^ 6 ^ 2 ^ 5 = 2 ^ (6 + 5) = 2 ^ 11 = 2 ^ (11 मॉड 7) = 2 ^ 4 = 6
परिणाम के साथ संयोग है कि हमने पहले क्या गणना की थी।

अब करते हैं विभाजन:
6 6 5 = 2 ^ 4 ^ 2 ^ 6 = 2 ^ (4-6) = 2 ^ (- 2) = 2 ^ ((- 2) mod 7) = 2 ^ 5 = 7
प्राप्त परिणाम भी सही है।

खैर, पूर्णता के लिए, आइए एक शक्ति को बढ़ाते हुए देखें:
5 ^ 2 = (^ 2 ^ 6) = ^ 2 = 2 ^ (6 = 2) = 2 ^ 12 = 2 ^ (12 मॉड 7) = 2 ^ 5 = 7
फिर, अप्रत्याशित रूप से एक ही परिणाम मिला।

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