चेस एल्गोरिथ्म

प्रस्तावना

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

मेरा विषय मुख्य रूप से चिकित्सकों पर लक्षित है। जो इस तरह के एल्गोरिदम को लागू करने में रुचि रखते हैं और एक स्वीकार्य अवधि के लिए एक छोटा सा काम करने वाला आवेदन प्राप्त करते हैं।

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

सिद्धांत की बिट

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

ब्लॉक कोड डिकोडिंग कठिन या नरम निर्णय लेने से किया जा सकता है। कठिन निर्णय डिकोडिंग में, डिमोडुलेटर में प्राप्त प्रत्येक बिट को एक मान दिया जाता है
0 या 1. एक नरम निर्णय डिकोडर न केवल 1 या 0 के बाइनरी मान को स्वीकार करता है, बल्कि एक दिए गए बिट के साथ जुड़ा हुआ एक विश्वास मूल्य भी है। डिकोडर इस नरम जानकारी का उपयोग करेगा, और आउटपुट पर हमें एक ही कठिन निर्णय मिलता है।
संक्षेप में, मान 0 या 1 से वेक्टर चैनल से हार्ड डिकोडर के लिए इनपुट है। मूल्यों (-∞; + ∞) से वेक्टर नरम डिकोडर के इनपुट पर प्राप्त होता है। नरम समाधान का उपयोग अधिक अवसर देता है, क्योंकि यह हस्तक्षेप को सही करने के लिए एक व्यापक पैंतरेबाज़ी प्रदान करता है।
चेस का एल्गोरिदम एक नरम समाधान के साथ ब्लॉक कोड है ।

चेस एल्गोरिथ्म

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

काम का उदाहरण

चेस के डिकोडर अपने काम में एक कठिन डिकोडर का उपयोग करता है। चलो पहले से ही वर्णित हैमिंग डिकोडर का उपयोग करें। एक बार फिर, मुझे याद है कि उसका वर्णन यहाँ पाया जा सकता है । हमारे मामले के लिए एकमात्र परिवर्तन, संदेश के अंत में परीक्षण वर्णों का स्थानांतरण है।

1. मान लीजिए कि हमारे पास मूल वेक्टर u = [1, 0, 0, 1] है;

2. हम इसे हेमिंग एल्गोरिथ्म के अनुसार एनकोड करते हैं और सी = [1, 0, 0, 1, 1, 0, 0] प्राप्त करते हैं;

3. एक समता जाँच जोड़ें - [8] = 2. आधुनिक के साथ 2. यह ध्यान देने योग्य है कि इन उद्देश्यों के लिए विस्तारित हैमिंग कोड का उपयोग करना सुविधाजनक है। लेकिन इसके बारे में अलग से बेहतर है।
नतीजतन, हम सी = [1, 0, 0, 1, 1, 0, 0, 1] प्राप्त करते हैं।

4. हम कुछ हस्तक्षेप करते हैं और वेक्टर आर = [-1.02, -1.1, -2, 1.95, 0.98, -2.34, -0.73, 1.97] प्राप्त करते हैं।

5. हम दूसरे चेस एल्गोरिथ्म का उपयोग करते हैं। यह सत्यापन कोड शब्दों की एक सरणी बनाने की निम्नलिखित विधि द्वारा विशेषता है:

• प्राप्त वेक्टर आर पी से कम से कम विश्वसनीय बिट्स का चयन करें, अर्थात, सबसे छोटे मोडुलो के पी बिट्स। वेक्टर में अंतिम बिट को ध्यान में नहीं रखा जाता है, क्योंकि यह समता की जांच करता है और अन्य बिट्स के आधार पर गणना की जा सकती है;
• संख्या v = <p चुनें;
• सहायक वैक्टर ज की एक सरणी उत्पन्न करें। लंबाई पी के वैक्टर से मिलकर, 1 के मान के साथ बिट्स के सभी प्रकार के संयोजन के साथ, जिसमें एक वेक्टर में संख्या वी से अधिक नहीं होनी चाहिए, और अन्य पदों में 0 के मान के साथ बिट्स (नीचे उदाहरण देखें);
• सत्यापन वैक्टर ई की एक सरणी उत्पन्न करें। निम्नलिखित नियमों के अनुसार:
  
  • प्रत्येक वेक्टर वेक्टर r से थोड़ा छोटा होना चाहिए;
  • वैक्टर का सरणी उसी लंबाई का होना चाहिए जैसा कि पिछले चरण में उत्पन्न सहायक वैक्टरों का सरणी है;
  • प्रत्येक वेक्टर को पहले चरण में चयनित कम से कम विश्वसनीय बिट्स के पदों को छोड़कर, शून्य बिट्स से युक्त होना चाहिए। इन पदों पर, सहायक वैक्टर एच के सरणी से बिट स्थित होना चाहिए।
  
  

अब हम अपने वेक्टर आर = [-1.02, -1.1, -2, 1.95, 0.98, -2.34, 0.73, 1.97] के उदाहरण का उपयोग करके सत्यापन वैक्टर उत्पन्न करेंगे।

• पी = 3, फिर कम से कम विश्वसनीय बिट्स की स्थिति हैं [1, 5, 7] (हम सूचकांक 1 से संख्या), [ -1.02 , -1.1, -2, 1.95, 0.98 , -2.34, 0.73 , 1.97];
• चलो v = 2;
• हम सहायक वैक्टर h की एक सरणी उत्पन्न करते हैं:
  h [१] = [०, ०, ०]
  h [२] = [०, ०, १],
  h [३] = [०, १, ०],
  h [४] = [०, १, १],
  h [५] = [१, ०, ०]
  h [६] = [१, ०, १],
  h [;] = [१, १, ०];
  
• हम चेक वर्णों की एक सरणी उत्पन्न करते हैं:
  ई [१] = [०, ०, ०, ०, ०, ०, ०], हम १, ५ और 1 के पदों का उपयोग वेक्टर एच [१] से क्रमश: ०, १ और २ के पदों पर करते हैं।
  ई [२] = [०, ०, ०, ०, ०, १], हम १, ५ और h तत्वों का उपयोग वेक्टर एच [२] से क्रमश: ०, १ और २ के पदों पर करते हैं,
  ई [३] = [०, ०, ०, ०, १, ०, ०], हम १, ५ और 1 तत्वों का उपयोग वेक्टर एच [३] से क्रमश: ०, १ और २ के पदों पर करते हैं,
  ई [४] = [०, ०, ०, ०, १, ०, १], हम १, ५ और 1 तत्वों का उपयोग वेक्टर एच [४] से क्रमश: ०, १ और २ स्थान पर करते हैं।
  ई [५] = [१, ०, ०, ०, ०, ०, ०], हम १, ५ और 1 के पदों का उपयोग वेक्टर एच [५] से क्रमश: ०, १ और २ के पदों पर करते हैं।
  ई [६] = [१, ०, ०, ०, ०, ०, १], हम १, ५ और h तत्त्वों का उपयोग वेक्टर h [६] के पदों से क्रमशः ०, १ और २ पदों पर करते हैं,
  ई [0] = [१, ०, ०, ०, १, ०, ०], हम क्रमशः १, ५ और at के पदों में से तत्वों का उपयोग करते हैं; [7] क्रमशः,, १ और २ के पदों पर;
  

6. हम वेक्टर आर को डीमोड्यूलेट करते हैं और वेक्टर वाई प्राप्त करते हैं। y [i] = r [i]> ०, फिर १, अन्यथा ०; और अंतिम बिट को त्यागें।
y = [0, 0, 0, 1, 1, 0, 1]।

7. परीक्षण अनुक्रम टी की एक सरणी उत्पन्न करें। t [i] = y [e [i]।
हमें मिलता है:
t [1] = [0, 0, 0, 1, 1, 0, 1] - y y e [1],
t [2] = [0, 0, 0, 1, 1, 0, 0] - y [e [2],
t [३] = [०, ०, ०, १, ०, ०, १] - y ⊕ e [३],
t [4] = [0, 0, 0, 1, 0, 0, 0] - y [e [4],
t [५] = [१, ०, ०, १, १, ०, १] - y ⊕ e [५],
t [6] = [1, 0, 0, 1, 1, 0, 0] - y [e [6],
t [7] = [1, 0, 0, 1, 0, 0, 1] - y [e [7];

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

8. हम t [i] (इस मामले में, हेमिंग एल्गोरिथम) के लिए एक कठिन समाधान लागू करते हैं, लेकिन परीक्षण वर्णों को छोड़ देते हैं और वैक्टर का एक सरणी प्राप्त करते हैं:
s [१] = [०, ०, ०, ०, १, १, १, १], टी के लिए एक कठिन समाधान [१],
s [२] = [१, ०, ०, १, १, ०, ०], t [२,
s [3] = [0, 0, 1, 1, 0, 0, 1], t [3,, के लिए एक कठिन समाधान
s [4] = [0, 0, 0, 0, 0, 0, 0], टी के लिए एक कठिन समाधान [4,,
s [5] = [1, 0, 0, 1, 1, 0, 0], t [5,
s [6] = [1, 0, 0, 1, 1, 0, 0], t [6,
s [7] = [1, 1, 0, 1, 0, 0, 1], t [7] के लिए एक कठिन समाधान;

9. वैक्टर s [i] में समता जाँच जोड़ें:
s [१] = [०, ०, ०, १, १, १, १, ०],
s [2] = [1, 0, 0, 1, 1, 0, 0, 1],
s [3] = [0, 0, 1, 1, 0, 0, 1, 1],
s [4] = [0, 0, 0, 0, 0, 0, 0, 0],
s [5] = [1, 0, 0, 1, 1, 0, 0, 1],
s [6] = [1, 0, 0, 1, 1, 0, 0, 1],
s [7] = [1, 1, 0, 1, 0, 0, 1, 0];

10. हम सरणी s से वैक्टर के मूल्यों को संशोधित करेंगे। सूत्र s [i] [j] = 2 * s [i] [j] - 1:
s [1] = [-1, -1, -1, 1, 1, 1, 1, -1],
s [2] = [1, -1, -1, 1, 1, -1, -1, 1],
s [3] = [-1, -1, 1, 1, -1, -1, 1, 1],
s [4] = [-1, -1, -1, -1, -1, -1, -1, -1],
s [5] = [1, -1, -1, 1, 1, -1, -1, 1],
s [6] = [1, -1, -1, 1, 1, -1, -1, 1],
s [7] = [1, 1, -1, 1, -1, -1, 1, -1];

11. सरणी s से वेक्टर r के सबसे करीब वेक्टर आर का पता लगाएं। एक मीट्रिक के रूप में यूक्लिडियन दूरी का उपयोग करना।
evkl (s [1], r) = 21.96, s [1] के लिए
evkl (s [2], r) = 11.72 , s [2] के लिए
evkl (s [3], r) = 16.64, s [3] के लिए
evkl (s [4], r) = 27.24, s [4] के लिए
evkl (s [5], r) = 11.72 , s [5] के लिए
evkl (s [6], r) = 11.72 , s [6] के लिए
evkl (s [7], r) = 25.00, s [7] के लिए

हमें कई समान मेट्रिक्स मिले। हम किसी भी वैक्टर को चुन सकते हैं। चलो पहले वाले को चुनें, जो कि है, s [2] = [1, -1, -1, 1, 1, -1, -1, 1]।

12. आइए हम s [2] को ध्वस्त करते हैं और वेक्टर को पुनः प्राप्त करते हैं। res [i] = s [2] [i]> 0, फिर 1, अन्यथा 0।
res = [१, ०, ०, १, १, ०, ०, १]।

13. हम वेक्टर रेस से चेक प्रतीकों को छोड़ देते हैं और मूल वेक्टर u = [1, 0, 0, 1] प्राप्त करते हैं, जिसे प्रेषित किया जाना था।

हस्तक्षेप के बारे में

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

उपसंहार

पहली बार हैबे पर लिखा। अगर किसी को दिलचस्पी है, तो भविष्य में मैं विटर्बी एल्गोरिथ्म, दहलीज डिकोडर, संभवतः टर्बो कोड समर्पित करना चाहूंगा। मैं रचनात्मक टिप्पणियों के लिए आभारी रहूंगा।

साहित्य

इस विषय पर, मैं सलाह देता हूं - “डिजिटल संचार प्रणालियों में त्रुटि सुधार के साथ कोडिंग। जे। क्लार्क, जे। केन । "