एएन कोड

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

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

अंकगणितीय वजन और दूरी

एक पूर्णांक का अंकगणितीय भार $x$ बेस में $r$ द्वारा परिभाषित किया गया है

$w(x)=\min\{t|x=\sum _{i=1}^{t}a_{i}r^{n(i)}\}$

कहां $|{a_{i}}|$< $r$, $n(i)\geq 0$, और $r,n(i)\in \mathbb {Z}$. किसी शब्द की अंकगणितीय दूरी उसके हैमिंग भार से ऊपरी सीमा होती है क्योंकि किसी भी पूर्णांक को उसके मानक बहुपद रूप द्वारा दर्शाया जा सकता है $x=\sum _{i=1}^{n}b_{i}r^{i}$ जहां $b_{i}$ पूर्णांक में अंक हैं। जहां सभी शर्तों को हटा रहा है $b_{i}=0$ ए अनुकरण करेगा $t$ इसके हैमिंग वजन के बराबर। अंकगणितीय वजन आमतौर पर हैमिंग वजन से कम होगा $a_{i}$ नकारात्मक होने की अनुमति है। उदाहरण के लिए, पूर्णांक $x=29$ जो है $11101$ बाइनरी में हैमिंग का वजन है $4$. यह अंकगणितीय भार पर एक त्वरित ऊपरी सीमा है $x=2^{0}+2^{2}+2^{3}+2^{4}$. हालांकि, चूंकि $a_{i}$ नकारात्मक हो सकता है, हम लिख सकते हैं $x=2^{5}-2^{1}-2^{0}$ जो अंकगणितीय भार के बराबर बनाता है $3$.

दो पूर्णांकों के बीच की अंकगणितीय दूरी किसके द्वारा परिभाषित की जाती है?

$d(x,y)=w(x-y)$

यह अंकगणितीय कोड का विश्लेषण करते समय उपयोग की जाने वाली प्राथमिक मीट्रिक में से एक है।

एएन कोड

AND कोड पूर्णांकों द्वारा परिभाषित किए जाते हैं $A$ और $B$ और से पूर्णांकों को एनकोड करने के लिए उपयोग किया जाता है $0$ को $B-1$ ऐसा है कि

$C=\{AN|N\in \mathbb {Z} ,0\leq N$<$B\}$

की प्रत्येक पसंद $A$ परिणाम एक अलग कोड में होगा, जबकि $B$ कोड की दूरी में उपयोगी गुणों को सुनिश्चित करने के लिए सीमित कारक के रूप में कार्य करता है। यदि $B$ बहुत बड़ा है, यह एक कोडवर्ड को कोड में बहुत कम अंकगणितीय भार के साथ दे सकता है जो पूरे कोड की दूरी को कम कर देगा। इन कोडों का उपयोग करने के लिए, दो पूर्णांकों पर एक अंकगणितीय ऑपरेशन करने से पहले, प्रत्येक पूर्णांक को गुणा किया जाता है $A$. कोडवर्ड पर ऑपरेशन का परिणाम होने दें $R$. ध्यान दें कि $R$ के बीच भी होना चाहिए $0$ को $B-1$ उचित डिकोडिंग के लिए। डिकोड करने के लिए, बस विभाजित करें $R/A$. यदि $A$ का कारक नहीं है $R$, तो कम से कम एक त्रुटि हुई है और सबसे संभावित समाधान वह कोडवर्ड होगा जिससे कम से कम अंकगणितीय दूरी होगी $R$. हैमिंग दूरी का उपयोग करने वाले कोडों की तरह, AN कोड तक सही कर सकते हैं $\lfloor {\frac {d-1}{2}}\rfloor$ त्रुटियां जहां $d$ कोड की दूरी है।

उदाहरण के लिए, एक एएन कोड के साथ $A=3$, जोड़ने का कार्य $15$ और $16$ दोनों ऑपरेंड को एन्कोड करके शुरू होगा। इसका परिणाम ऑपरेशन में होता है $R=45+48=93$. फिर, समाधान खोजने के लिए हम विभाजित करते हैं $93/3=31$. जब तक कि $B$>$31$, यह कोड के तहत एक संभावित ऑपरेशन होगा। मान लीजिए कि ऑपरेंड के प्रत्येक बाइनरी प्रतिनिधित्व में एक त्रुटि होती है जैसे कि $45=101101\rightarrow 101111$ और $48=110000\rightarrow 110001$, तब $R=101111+110001=1100000$. ध्यान दें कि जब से $93=1011101$, प्राप्त शब्द और सही समाधान के बीच हैमिंग वजन है $5$ बस के बाद $2$ त्रुटियां। अंकगणितीय भार की गणना करने के लिए, हम लेते हैं $1100000-1011101=11$ जिसका प्रतिनिधित्व किया जा सकता है $11=2^{0}+2^{1}$ या $11=2^{2}-2^{0}$. किसी भी मामले में, अंकगणितीय दूरी है $2$ अपेक्षा के अनुरूप क्योंकि यह की गई त्रुटियों की संख्या है। इस त्रुटि को ठीक करने के लिए, अंकगणितीय दूरी के संदर्भ में प्राप्त शब्द के निकटतम कोडवर्ड की गणना करने के लिए एक एल्गोरिथ्म का उपयोग किया जाएगा। हम एल्गोरिदम का विस्तार से वर्णन नहीं करेंगे।

यह सुनिश्चित करने के लिए कि कोड की दूरी बहुत कम न हो, हम मॉड्यूलर AN कोड परिभाषित करेंगे। एक मॉड्यूलर एएन कोड $C$ का एक उपसमूह है $\mathbb {Z} /m\mathbb {Z}$, कहां $m=AB$. कोड को मॉड्यूलर दूरी के संदर्भ में मापा जाता है जिसे एक ग्राफ के रूप में परिभाषित किया जाता है जिसमें कोने तत्व होते हैं $\mathbb {Z} /m\mathbb {Z}$. दो शिखर $x{\pmod {m}}$ और $x'{\pmod {m}}$ जुड़े हुए हैं

$x-x'\equiv \pm c\cdot r^{j}{\pmod {m}}$

कहां $c,j\in \mathbb {Z}$ और $0$<$c$<$r$, $j\geq 0$. फिर दो शब्दों के बीच मॉड्यूलर दूरी ग्राफ में उनके नोड्स के बीच सबसे कम पथ की लंबाई है। किसी शब्द का मॉड्यूलर वजन उसकी दूरी है $0$ जो बराबर है

$w_{m}(x)=min\{w(y)|y\in \mathbb {Z} ,y\equiv x{\pmod {m}}\}$

व्यवहार में, का मूल्य $m$ आमतौर पर ऐसा चुना जाता है $m=r^{n}-1$ चूंकि अधिकांश कंप्यूटर अंकगणित की गणना की जाती है $\mod 2^{n}-1$ इसलिए कोड के सीमा से बाहर जाने के कारण डेटा का कोई अतिरिक्त नुकसान नहीं हुआ है क्योंकि कंप्यूटर भी सीमा से बाहर हो जाएगा। का चयन $m=r^{n}-1$ अन्य कोडों की तुलना में बड़ी दूरी वाले कोडों में भी परिणाम होता है।

के साथ मॉड्यूलर वजन का उपयोग करके $m=r^{n}-1$, AN कोड चक्रीय कोड होंगे।

परिभाषा: एक चक्रीय एएन कोड एक कोड है $C$ का एक उपसमूह है $[r^{n}-1]$, कहां $[r^{n}-1]=\{0,1,2,\dots ,r^{n}-1\}$.

एक चक्रीय एएन कोड रिंग का एक प्रमुख आदर्श है $[r^{n}-1]$. पूर्णांक हैं $A$ और $B$ कहां $AB=r^{n}-1$ और $A,B$ AN कोड की परिभाषा को पूरा करें। चक्रीय एएन कोड चक्रीय कोड का एक सबसेट है और इसमें समान गुण हैं।

मंडेलबौम-बैरो कोड्स

मैंडेलबाउम-बैरो कोड एक प्रकार का चक्रीय एएन कोड है जो डी. मैंडेलबाम और जे.टी. बैरो द्वारा शुरू किया गया है। ये कोड चुनकर बनाए जाते हैं $B$ एक अभाज्य संख्या होना जो विभाजित नहीं होती है $r$ ऐसा है कि $\mathbb {Z} /B\mathbb {Z}$ से उत्पन्न होता है $r$ और $-1$, और $m=r^{n}-1$. होने देना $n$ जहां एक सकारात्मक पूर्णांक हो $r^{n}\equiv 1{\pmod {B}}$ और $A=(r^{n}-1)/B$. उदाहरण के लिए, चुनना $r=2,B=5,n=4$, और $A=(r^{n}-1)/B=3$ परिणाम एक मैंडेलबाउम-बैरो कोड होगा जैसे कि $C=\{3N|N\in \mathbb {Z} ,0\leq N$<$5\}$ बेस में $2$.

मंडेलबौम-बैरो कोड की दूरी का विश्लेषण करने के लिए, हमें निम्नलिखित प्रमेय की आवश्यकता होगी।

प्रमेय: चलो $C\subset [r^{n}-1]$ जनरेटर के साथ चक्रीय एएन कोड बनें $A$, और

$B=|C|=(r^{n}-1)/A$

फिर,

$\sum _{x\in C}w_{m}(x)=n(\lfloor {\frac {rB}{r+1}}\rfloor -\lfloor {\frac {B}{r+1}}\rfloor )$

सबूत: मान लें कि प्रत्येक $x\in C$ एक अद्वितीय चक्रीय गैर-निकटवर्ती रूप है प्रतिनिधित्व जो है

$x\equiv \sum _{i=0}^{n-1}c_{i,x}r^{i}{\pmod {r^{n}-1}}$

हम एक परिभाषित करते हैं $n\times B$ तत्वों के साथ मैट्रिक्स $c_{i,x}$ कहां $0\leq i\leq n-1$ और $x\in C$. यह मैट्रिक्स अनिवार्य रूप से सभी कोडवर्ड्स की एक सूची है $C$ जहां प्रत्येक कॉलम एक कोडवर्ड है। तब से $C$ चक्रीय है, मैट्रिक्स के प्रत्येक स्तंभ में समान संख्या में शून्य हैं। हमें अब गणना करनी चाहिए $n|\{x\in C|c_{n-1,x}\neq 0\}|$, जो है $n$ उन कोडवर्ड्स की संख्या का गुना जो a से समाप्त नहीं होते हैं $0$. चक्रीय NAF में होने की संपत्ति के रूप में, $c_{n-1,x}\neq 0$ यदि कोई है $y\in \mathbb {Z}$ साथ $y\equiv x{\pmod {r^{n}-1}},{\frac {m}{r+1}}$<$y\leq {\frac {mr}{r+1}}$. तब से $x=AN{\pmod {r^{n}-1}}$ साथ $0\leq N$<$B$, तब ${\frac {B}{r+1}}$<$N\leq {\frac {Br}{r+1}}$. फिर उन पूर्णांकों की संख्या जिनके अंतिम बिट के रूप में एक शून्य है $\lfloor {\frac {rB}{r+1}}\rfloor -\lfloor {\frac {B}{r+1}}\rfloor$. इसे से गुणा करें $n$ कोडवर्ड में वर्ण हमें के कोडवर्ड के वजन का योग देते हैं $n(\lfloor {\frac {rB}{r+1}}\rfloor -\lfloor {\frac {B}{r+1}}\rfloor )$ जैसी इच्छा।

अब हम पिछले प्रमेय का उपयोग यह दिखाने के लिए करेंगे कि मैंडेलबाउम-बैरो कोड समान दूरी पर हैं (जिसका अर्थ है कि कोडवर्ड के प्रत्येक जोड़े की दूरी समान है), की दूरी के साथ

${\frac {n}{B-1}}(\lfloor {\frac {rB}{r+1}}\rfloor -\lfloor {\frac {B}{r+1}}\rfloor )$

सबूत: चलो $x\in C,x\neq 0$, तब $x=AN{\pmod {r^{n}-1}}$ और $N$ से विभाज्य नहीं है $B$. इसका तात्पर्य वहाँ है $\exists j(N\equiv \pm r^{j}{\pmod {B}})$. फिर $w_{m}(x)=w_{m}(\pm r^{j}A)=w_{m}(A)$. इससे यह सिद्ध होता है $C$ समान दूरी पर है क्योंकि सभी कोडवर्ड का भार समान होता है $A$. चूँकि सभी कोडवर्ड्स का वजन समान होता है, और पिछले प्रमेय द्वारा हम सभी कोडवर्ड्स का कुल वजन जानते हैं, कोडवर्ड्स की संख्या (0 को छोड़कर) द्वारा कुल वजन को विभाजित करके कोड की दूरी पाई जाती है।

यह भी देखें

• त्रुटि का पता लगाने और सुधार
• आगे त्रुटि सुधार

इस पेज में लापता आंतरिक लिंक की सूची

• त्रुटि सुधार कोड
• त्रुटि का पता लगाना और सुधार