लीनियर कोड

कोडिंग सिद्धांत में, रैखिक कोड त्रुटि-सुधार करने वाला कोड होता है जिसके लिए कोड शब्द का कोई भी रैखिक संयोजन भी कोडवर्ड होता है। रैखिक कोड को पारंपरिक रूप से ब्लॉक कोड और कन्वोल्यूशनल कोड में विभाजित किया जाता है, हालांकि टर्बो कोड को इन दो प्रकारों के हाइब्रिड के रूप में देखा जा सकता है। रैखिक कोड अन्य कोड की तुलना में अधिक कुशल एन्कोडिंग और डिकोडिंग एल्गोरिदम की अनुमति देते हैं (सीएफ सिंड्रोम डिकोडिंग)।

रैखिक कोड का उपयोग आगे की त्रुटि सुधार में किया जाता है और संचार चैनल पर प्रतीकों (जैसे, अंश ्स) को प्रसारित करने के तरीकों में लागू किया जाता है ताकि, यदि संचार में त्रुटियां होती हैं, तो संदेश ब्लॉक के प्राप्तकर्ता द्वारा कुछ त्रुटियों को ठीक किया जा सके या पता लगाया जा सके। रैखिक ब्लॉक कोड में कोडवर्ड प्रतीकों के ब्लॉक होते हैं जिन्हें भेजे जाने वाले मूल मान से अधिक प्रतीकों का उपयोग करके एन्कोड किया जाता है। लंबाई n का रैखिक कोड n प्रतीकों वाले ब्लॉक को प्रसारित करता है। उदाहरण के लिए, [7,4,3] हैमिंग कोड रैखिक बाइनरी कोड है जो 7-बिट कोडवर्ड का उपयोग करके 4-बिट संदेशों का प्रतिनिधित्व करता है। दो अलग-अलग कोडवर्ड कम से कम तीन बिट में भिन्न होते हैं। परिणामस्वरूप, प्रति कोडवर्ड अधिकतम दो त्रुटियों का पता लगाया जा सकता है जबकि त्रुटि को ठीक किया जा सकता है। इस कोड में 2 शामिल हैं⁴=16 कोडवर्ड.

परिभाषा और पैरामीटर

लंबाई n और आयाम k का रैखिक कोड सदिश स्थल के आयाम (रैखिक बीजगणित) k के साथ रैखिक उपस्थान C है $\mathbb {F} _{q}^{n}$ कहाँ $\mathbb {F} _{q}$ q तत्वों वाला परिमित क्षेत्र है। ऐसे कोड को q-ary कोड कहा जाता है। यदि q = 2 या q = 3, तो कोड को क्रमशः 'बाइनरी कोड', या 'टर्नरी कोड' के रूप में वर्णित किया जाता है। C में वेक्टर को कोडवर्ड कहा जाता है। किसी कोड का 'आकार' कोडवर्ड की संख्या है और q के बराबर है^क.

किसी कोडवर्ड का 'वजन' उसके उन तत्वों की संख्या है जो शून्य नहीं हैं और दो कोडवर्ड के बीच की 'दूरी' उनके बीच की हैमिंग दूरी है, यानी उन तत्वों की संख्या जिनमें वे भिन्न हैं। रैखिक कोड की दूरी d उसके गैर-शून्य कोडवर्ड का न्यूनतम वजन है, या समकक्ष रूप से, अलग-अलग कोडवर्ड के बीच की न्यूनतम दूरी है। लंबाई n, आयाम k और दूरी d के रैखिक कोड को [n,k,d] कोड कहा जाता है (या, अधिक सटीक रूप से, $[n,k,d]_{q}$ कोड).

हम देना चाहते हैं $\mathbb {F} _{q}^{n}$ मानक आधार क्योंकि प्रत्येक समन्वय बिट का प्रतिनिधित्व करता है जो ट्रांसमिशन त्रुटि (एक द्विआधारी सममित चैनल) की कुछ छोटी संभावना के साथ शोर चैनल में प्रसारित होता है। यदि किसी अन्य आधार का उपयोग किया जाता है तो इस मॉडल का उपयोग नहीं किया जा सकता है और हैमिंग मीट्रिक ट्रांसमिशन में त्रुटियों की संख्या को नहीं मापता है, जैसा कि हम चाहते हैं।

जेनरेटर और चेक मैट्रिसेस

के रैखिक उपस्थान के रूप में $\mathbb {F} _{q}^{n}$, संपूर्ण कोड C (जो बहुत बड़ा हो सकता है) को सेट के स्पैन (रैखिक बीजगणित) के रूप में दर्शाया जा सकता है $k$ कोडवर्ड (रैखिक बीजगणित में आधार (रैखिक बीजगणित) के रूप में जाना जाता है)। ये आधार कोडवर्ड अक्सर मैट्रिक्स जी की पंक्तियों में एकत्रित किए जाते हैं जिन्हें कोड सी के लिए जेनरेटर मैट्रिक्स के रूप में जाना जाता है। जब G के पास ब्लॉक मैट्रिक्स फॉर्म है ${\boldsymbol {G}}=[I_{k}|P]$, कहाँ $I_{k}$ को दर्शाता है $k\times k$ पहचान मैट्रिक्स और पी कुछ है $k\times (n-k)$ मैट्रिक्स, तो हम कहते हैं कि G मानक रूप में है।

एक मैट्रिक्स H रैखिक फ़ंक्शन का प्रतिनिधित्व करता है $\phi :\mathbb {F} _{q}^{n}\to \mathbb {F} _{q}^{n-k}$ जिसका कर्नेल (मैट्रिक्स) C है, उसे C का 'मैट्रिक्स की जाँच करें ' (या कभी-कभी पैरिटी चेक मैट्रिक्स) कहा जाता है। समान रूप से, H मैट्रिक्स है जिसका शून्य स्थान C है। यदि C मानक रूप में जेनरेटिंग मैट्रिक्स G वाला कोड है, ${\boldsymbol {G}}=[I_{k}|P]$, तब ${\boldsymbol {H}}=[-P^{T}|I_{n-k}]$ C के लिए चेक मैट्रिक्स है। H द्वारा उत्पन्न कोड को C का 'डुअल कोड' कहा जाता है। यह सत्यापित किया जा सकता है कि G है $k\times n$ मैट्रिक्स, जबकि H है $(n-k)\times n$ आव्यूह।

रैखिकता गारंटी देती है कि कोडवर्ड c के बीच न्यूनतम हैमिंग दूरी d है₀ और कोई भी अन्य कोडवर्ड c ≠ c₀ सी से स्वतंत्र है₀. इस गुण से यह पता चलता है कि अंतर c − c है₀ C में दो कोडवर्ड का कोडवर्ड भी है (यानी, सबस्पेस C का तत्व (गणित), और वह गुण जो d(c,c) है₀) = d(c − c₀,0). ये गुण यही दर्शाते हैं

$\min _{c\in C,\ c\neq c_{0}}d(c,c_{0})=\min _{c\in C,\ c\neq c_{0}}d(c-c_{0},0)=\min _{c\in C,\ c\neq 0}d(c,0)=d.$

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

एक रैखिक कोड C की दूरी d, चेक मैट्रिक्स H के रैखिक रूप से निर्भर स्तंभों की न्यूनतम संख्या के बराबर होती है।

प्रमाण: क्योंकि ${\boldsymbol {H}}\cdot {\boldsymbol {c}}^{T}={\boldsymbol {0}}$, जो के बराबर है $\sum _{i=1}^{n}(c_{i}\cdot {\boldsymbol {H_{i}}})={\boldsymbol {0}}$, कहाँ ${\boldsymbol {H_{i}}}$ है $i^{th}$ का स्तंभ ${\boldsymbol {H}}$. उन वस्तुओं को हटा दें $c_{i}=0$, वे ${\boldsymbol {H_{i}}}$ साथ $c_{i}\neq 0$ रैखिक रूप से निर्भर हैं. इसलिए, $d$ कम से कम रैखिक रूप से निर्भर स्तंभों की न्यूनतम संख्या है। दूसरी ओर, रैखिक रूप से निर्भर स्तंभों के न्यूनतम सेट पर विचार करें $\{{\boldsymbol {H_{j}}}|j\in S\}$ कहाँ $S$ कॉलम इंडेक्स सेट है. $\sum _{i=1}^{n}(c_{i}\cdot {\boldsymbol {H_{i}}})=\sum _{j\in S}(c_{j}\cdot {\boldsymbol {H_{j}}})+\sum _{j\notin S}(c_{j}\cdot {\boldsymbol {H_{j}}})={\boldsymbol {0}}$. अब वेक्टर पर विचार करें ${\boldsymbol {c'}}$ ऐसा है कि $c_{j}'=0$ अगर $j\notin S$. टिप्पणी ${\boldsymbol {c'}}\in C$ क्योंकि ${\boldsymbol {H}}\cdot {\boldsymbol {c'}}^{T}={\boldsymbol {0}}$ . इसलिए, हमारे पास है $d\leq wt({\boldsymbol {c'}})$, जो कि रैखिक रूप से निर्भर स्तंभों की न्यूनतम संख्या है ${\boldsymbol {H}}$. इसलिए दावा की गई संपत्ति प्रमाणित है।

उदाहरण: हैमिंग कोड

Main article: Hamming code

त्रुटि सुधार के उद्देश्य से विकसित रैखिक कोड की पहली श्रेणी के रूप में, डिजिटल संचार प्रणालियों में हैमिंग कोड का व्यापक रूप से उपयोग किया गया है। किसी भी सकारात्मक पूर्णांक के लिए $r\geq 2$, वहाँ मौजूद है $[2^{r}-1,2^{r}-r-1,3]_{2}$ हैमिंग कोड. तब से $d=3$, यह हैमिंग कोड 1-बिट त्रुटि को ठीक कर सकता है।

उदाहरण: निम्नलिखित जनरेटर मैट्रिक्स और पैरिटी चेक मैट्रिक्स के साथ रैखिक ब्लॉक कोड है $[7,4,3]_{2}$ हैमिंग कोड.

${\boldsymbol {G}}={\begin{pmatrix}1\ 0\ 0\ 0\ 1\ 1\ 0\\0\ 1\ 0\ 0\ 0\ 1\ 1\\0\ 0\ 1\ 0\ 1\ 1\ 1\\0\ 0\ 0\ 1\ 1\ 0\ 1\end{pmatrix}},$ ${\boldsymbol {H}}={\begin{pmatrix}1\ 0\ 1\ 1\ 1\ 0\ 0\\1\ 1\ 1\ 0\ 0\ 1\ 0\\0\ 1\ 1\ 1\ 0\ 0\ 1\end{pmatrix}}$

उदाहरण: हैडामर्ड कोड

Main article: Hadamard code

Hadamard कोड है $[2^{r},r,2^{r-1}]_{2}$ रैखिक कोड और कई त्रुटियों को ठीक करने में सक्षम है। हैडामर्ड कोड को कॉलम दर कॉलम बनाया जा सकता है: द $i^{th}$ स्तंभ पूर्णांक के द्विआधारी प्रतिनिधित्व का बिट है $i$, जैसा कि निम्नलिखित उदाहरण में दिखाया गया है। हैडामर्ड कोड में न्यूनतम दूरी होती है $2^{r-1}$ और इसलिए सही कर सकते हैं $2^{r-2}-1$ त्रुटियाँ.

उदाहरण: निम्नलिखित जनरेटर मैट्रिक्स के साथ रैखिक ब्लॉक कोड है $[8,3,4]_{2}$ हैडामर्ड कोड: ${\boldsymbol {G}}_{Had}={\begin{pmatrix}0\ 0\ 0\ 0\ 1\ 1\ 1\ 1\\0\ 0\ 1\ 1\ 0\ 0\ 1\ 1\\0\ 1\ 0\ 1\ 0\ 1\ 0\ 1\end{pmatrix}}$.

हैडामर्ड कोड रीड-मुलर कोड का विशेष मामला है। यदि हम पहला कॉलम (सर्व-शून्य कॉलम) निकालते हैं ${\boldsymbol {G}}_{Had}$, हम पाते हैं $[7,3,4]_{2}$ सिम्प्लेक्स कोड, जो हैमिंग कोड का दोहरा कोड है।

निकटतम पड़ोसी एल्गोरिदम

पैरामीटर d कोड की त्रुटि सुधार क्षमता से निकटता से संबंधित है। निम्नलिखित निर्माण/एल्गोरिदम इसे दर्शाता है (जिसे निकटतम पड़ोसी डिकोडिंग एल्गोरिदम कहा जाता है):

इनपुट: ए प्राप्त वेक्टर वी इन $\mathbb {F} _{q}^{n}$ .

आउटपुट: कोडवर्ड $w$ में $C$ से नजदीकी $v$, यदि कोई।

• प्रारंभ स्थल $t=0$, निम्नलिखित दो चरणों को दोहराएँ।
• (हैमिंग) त्रिज्या की गेंद के तत्वों की गणना करें $t$ प्राप्त शब्द के आसपास $v$, निरूपित $B_{t}(v)$.
  • प्रत्येक के लिए $w$ में $B_{t}(v)$, अगर जांच $w$ में $C$. यदि ऐसा है तो वापस लौटें $w$ समाधान के रूप में.
• वृद्धि $t$. असफल तभी जब $t>(d-1)/2$ इसलिए गणना पूरी हो गई है और कोई समाधान नहीं निकला है।

हम कहते हैं कि रैखिक $C$ है $t$-यदि अधिकतम कोडवर्ड है तो त्रुटि सुधारना $B_{t}(v)$, प्रत्येक के लिए $v$ में $\mathbb {F} _{q}^{n}$.

लोकप्रिय संकेतन

Main article: Block code § Popular notation

सामान्य तौर पर कोड को अक्सर C अक्षर से दर्शाया जाता है, और लंबाई n और आयाम (रैखिक बीजगणित) k (यानी, इसके आधार में k कोड शब्द और इसके जेनरेटिंग मैट्रिक्स में k पंक्तियाँ) वाले कोड को आम तौर पर ( n,k) कोड। रैखिक ब्लॉक कोड को अक्सर [n,k,d] कोड के रूप में दर्शाया जाता है, जहां d किन्हीं दो कोड शब्दों के बीच कोड की न्यूनतम हैमिंग दूरी को संदर्भित करता है।

([एन, के, डी] नोटेशन को (एन, एम, डी) नोटेशन के साथ भ्रमित नहीं किया जाना चाहिए, जिसका उपयोग लंबाई एन, आकार एम (यानी, एम कोड शब्द वाले) और न्यूनतम हैमिंग के गैर-रेखीय कोड को दर्शाने के लिए किया जाता है। दूरी डी.)

सिंगलटन बाध्य

लेम्मा (सिंगलटन बाउंड): प्रत्येक रैखिक [n,k,d] कोड C संतुष्ट करता है $k+d\leq n+1$.

एक कोड C जिसके पैरामीटर k+d=n+1 को संतुष्ट करते हैं, अधिकतम दूरी वियोज्य या MDS कहलाता है। ऐसे कोड, जब वे मौजूद होते हैं, कुछ अर्थों में सर्वोत्तम संभव होते हैं।

यदि सी₁ और सी₂ लंबाई n के दो कोड हैं और यदि सममित समूह S में कोई क्रमपरिवर्तन p है_n जिसके लिए (सी₁,...,सी_n) सी में₁ यदि और केवल यदि (सी_p(1),...,सी_p(n)) सी में₂, तो हम कहते हैं C₁ और सी₂ क्रमपरिवर्तन समतुल्य हैं। अधिक व्यापकता में, यदि कोई है $n\times n$ एकपदी मैट्रिक्स $M\colon \mathbb {F} _{q}^{n}\to \mathbb {F} _{q}^{n}$ जो C भेजता है₁ समरूपी रूप से C₂ तो हम कहते हैं सी₁ और सी₂ समतुल्य हैं.

लेम्मा: कोई भी रैखिक कोड कोड के समतुल्य क्रमपरिवर्तन है जो मानक रूप में है।

बोनिसोली का प्रमेय

एक कोड को समान दूरी के रूप में परिभाषित किया जाता है यदि और केवल तभी जब कुछ स्थिरांक d मौजूद हो, जैसे कि कोड के किन्हीं दो अलग-अलग कोडवर्ड के बीच की दूरी d के बराबर हो। 1984 में एरिगो बोनीसोली ने परिमित क्षेत्रों पर रैखिक एक-भार कोड की संरचना निर्धारित की और साबित किया कि प्रत्येक समदूरस्थ रैखिक कोड w: दोहरे कोड हैमिंग कोड का अनुक्रम है।

उदाहरण

रैखिक कोड के कुछ उदाहरणों में शामिल हैं:

• दोहराव कोड
• समता कोड
• चक्रीय कोड
• हैमिंग कोड
• गोले कोड (बहुविकल्पी), बाइनरी भाषा में कोड और टेनेरी गले में कोड दोनों संस्करण
• बहुपद कोड, जिनमें से BCH कोड एक उदाहरण हैं
• रीड-सोलोमन त्रुटि सुधार|रीड-सोलोमन कोड
• रीड-मुलर कोड
• बीजगणितीय ज्यामिति कोड
• बाइनरी बढ़िया कोड है
• कम-घनत्व समता-जांच कोड
• विस्तारक कोड
• बहुआयामी समता-जाँच कोड
• टोरिक कोड
• टर्बो कोड

सामान्यीकरण

गैर-क्षेत्रीय वर्णमाला पर हैमिंग रिक्त स्थान पर भी विचार किया गया है, विशेष रूप से परिमित रिंगों पर, विशेष रूप से मॉड्यूलर अंकगणित पर गैलोज़ रिंग्स|Z₄. यह वेक्टर स्पेस के बजाय मॉड्यूल (गणित) और रैखिक कोड के बजाय रिंग-लीनियर कोड (सबमॉड्यूल के साथ पहचाने गए) को जन्म देता है। इस मामले में उपयोग की जाने वाली विशिष्ट मीट्रिक ली दूरी है। इनके बीच ग्रे आइसोमेट्री मौजूद है $\mathbb {Z} _{2}^{2m}$ (यानी जीएफ(2^{2 मी})) हैमिंग दूरी के साथ और $\mathbb {Z} _{4}^{m}$ (ली दूरी के साथ जीआर(4,एम) के रूप में भी दर्शाया गया है); इसका मुख्य आकर्षण यह है कि यह कुछ अच्छे कोडों के बीच पत्राचार स्थापित करता है जो रैखिक नहीं होते हैं $\mathbb {Z} _{2}^{2m}$ रिंग-लीनियर कोड की छवियों के रूप में $\mathbb {Z} _{4}^{m}$. अभी हाल ही में, कुछ लेखकों ने रिंगों पर ऐसे कोड को केवल रैखिक कोड के रूप में भी संदर्भित किया है।

यह भी देखें

• डिकोडिंग के तरीके

संदर्भ

ग्रन्थसूची

• J. F. Humphreys; M. Y. Prest (2004). Numbers, Groups and Codes (2nd ed.). Cambridge University Press. ISBN 978-0-511-19420-7. Chapter 5 contains a more gentle introduction (than this article) to the subject of linear codes.

बाहरी संबंध

• q-ary code generator program
• Code Tables: Bounds on the parameters of various types of codes, IAKS, Fakultät für Informatik, Universität Karlsruhe (TH)]. Online, up to date table of the optimal binary codes, includes non-binary codes.
• The database of Z4 codes Online, up to date database of optimal Z4 codes.