लीनियर कोड

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

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

परिभाषा और मापदंड

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

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

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

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

$\mathbb {F} _{q}^{n}$ के एक रैखिक उपस्थान के रूप में, संपूर्ण कोड C (जो बहुत बड़ा हो सकता है) को $k$ कोडवर्ड के एक समुच्चय के विस्तार के रूप में दर्शाया जा सकता है (जिसे रैखिक बीजगणित में आधार के रूप में जाना जाता है)। इन आधार कोडवर्ड को अधिकांशतः आव्यूह G की पंक्तियों में एकत्रित किया जाता है, जिसे कोड C के लिए जेनरेटर आव्यूह के रूप में जाना जाता है। जब G के पास ब्लॉक आव्यूह फॉर्म ${\boldsymbol {G}}=[I_{k}|P]$ होता है, तो हम $I_{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 में दो कोडवर्ड का कोडवर्ड भी है (अर्थात, उपस्थान 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}}}$ हैं वे रैखिक रूप से निर्भर हैं। इसलिए, d कम से कम रैखिक रूप से निर्भर स्तंभों की न्यूनतम संख्या है। दूसरी ओर, रैखिक रूप से निर्भर स्तंभों के न्यूनतम समुच्चय पर विचार करें $c_{i}\neq 0$ जहां S स्तंभ सूचकांक समुच्चय है। $\{{\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'}}$ इसलिए, हमारे पास $d\leq wt({\boldsymbol {c'}})$ है, जो ${\boldsymbol {H}}$ में रैखिक रूप से निर्भर स्तंभों की न्यूनतम संख्या है। इसलिए प्रमाणित की गई प्रोपर्टी सिद्ध है।

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

Main article: हैमिंग कोड

त्रुटि सुधार के उद्देश्य से विकसित रैखिक कोड की पहली श्रेणी के रूप में, डिजिटल संचार प्रणालियों में हैमिंग कोड का व्यापक रूप से उपयोग किया गया है। किसी भी धनात्मक पूर्णांक $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: हैडामर्ड कोड

हैडामर्ड कोड एक $[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 कोड की त्रुटि सुधार क्षमता से निकटता से संबंधित है। निम्नलिखित निर्माण/एल्गोरिदम इसे दर्शाता है (जिसे निकटतम नेबर डिकोडिंग एल्गोरिदम कहा जाता है):

इनपुट: A प्राप्त सदिश v $\mathbb {F} _{q}^{n}$ में

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

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

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

लोकप्रिय नोटेशन

Main article: ब्लॉक कोड § लोकप्रिय नोटेशन

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

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

सिंगलटन बाउंड

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

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

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

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

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

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

उदाहरण

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

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

सामान्यीकरण

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