बर्स्ट त्रुटि-सुधार करने वाले कोड

कोडिंग सिद्धांत में, बर्स्ट त्रुटि-सुधार करने वाले कोड बर्स्ट त्रुटियों को ठीक करने के विधियों को नियोजित करते हैं, जो त्रुटियां हैं जो एक-दूसरे से स्वतंत्र रूप से बिट्स में होने के अतिरिक्त निरंतर अनेक बिट्स में होती हैं।

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

परिभाषाएँ

लम्बाई का बर्स्ट 5

इस प्रकार की लम्बाई का बर्स्ट ℓ कोडवर्ड बोलो $C$ प्रसारित किया जाता है, और इसे $Y=C+E.$ प्राप्त किया जाता है फिर, त्रुटि सदिश $E$ लम्बाई का बर्स्ट $\ell$ कहलाता है यदि $E$ के गैर-शून्य अवयव $\ell$ तक निरंतर अवयव ही सीमित हैं . उदाहरण के लिए, $E=(0{\textbf {1000011}}0)$ लम्बाई का बर्स्ट $\ell =7.$ है

चूँकि यह परिभाषा यह बताने के लिए पर्याप्त है कि बर्स्ट त्रुटि क्या है, बर्स्ट त्रुटि सुधार के लिए विकसित अधिकांश उपकरण चक्रीय कोड पर निर्भर करते हैं। यह हमारी अगली परिभाषा को प्रेरित करता है।

त्रुटि सदिश $E$ को $\ell$ लंबाई की चक्रीय बर्स्ट त्रुटि कहलाती है यदि इसके गैरशून्य अवयव $\ell$ चक्रीय रूप से निरंतर अवयव तक ही सीमित हैं। उदाहरण के लिए, पहले माना गया त्रुटि सदिश $E=(010000110)$, लंबाई का चक्रीय बर्स्ट है $\ell =5$, चूंकि हम स्थिति से प्रारंभ होने वाली त्रुटि पर विचार करते हैं $6$ और स्थिति $1$ पर समाप्त हो रहा है. ध्यान दें कि सूचकांक हैं $0$-आधारित, अर्थात पहला अवयव $0$ पर स्थिति है .

इस लेख के शेष भाग के लिए, हम चक्रीय बर्स्ट को संदर्भित करने के लिए बर्स्ट शब्द का उपयोग करेंगे, जब तक कि अन्यथा उल्लेख न किया गया हो।

बर्स्ट विवरण

बर्स्ट त्रुटि की संक्षिप्त परिभाषा रखना अधिकांशतः उपयोगी होता है, जिसमें न केवल इसकी लंबाई, किंतु ऐसी त्रुटि का पैटर्न और स्थान भी सम्मिलित होता है। हम बर्स्ट विवरण को $(P,L)$ टुपल के रूप में परिभाषित करते हैं जहाँ $P$ त्रुटि का पैटर्न है (जो कि त्रुटि पैटर्न में पहली गैर-शून्य प्रविष्टि से प्रारंभ होने वाले और अंतिम गैर-शून्य प्रतीक के साथ समाप्त होने वाले प्रतीकों की स्ट्रिंग है), और $L$ कोडवर्ड पर वह स्थान है, जहां बर्स्ट पाया जा सकता है।

उदाहरण के लिए, त्रुटि पैटर्न $E=(010000110)$ का बर्स्ट विवरण $D=(1000011,1)$ है ध्यान दें कि ऐसा वर्णन अद्वितीय नहीं है, क्योंकि$D'=(11001,6)$ उसी बर्स्ट त्रुटि का वर्णन करता है। सामान्यतः , यदि $E$ में गैर-शून्य अवयव की संख्या $w$ है , तब $E$ में $w$ भिन्न -भिन्न बर्स्ट विवरण होगा, जिनमें से प्रत्येक $E$ भिन्न गैर-शून्य प्रविष्टि पर प्रारंभ होता है . नीचे दिए गए प्रमेय के साथ बर्स्ट विवरण की अस्पष्टता से उत्पन्न होने वाले विवादों को हल करने के लिए, चूंकि ऐसा करने से पहले हमें पहले परिभाषा की आवश्यकता है।

परिभाषा। किसी दिए गए त्रुटि $y,$ पैटर्न में प्रतीकों की संख्या $\mathrm {length} (y).$द्वारा निरूपित किया जाता है

Theorem (Uniqueness of burst descriptions) — मान लीजिए $E$ लंबाई का त्रुटि सदिश है $n$ दो बर्स्ट विवरण के साथ $(P_{1},L_{1})$ and $(P_{2},L_{2})$. If $\mathrm {length} (P_{1})+\mathrm {length} (P_{2})\leqslant n+1,$ तो दोनों विवरण समान हैं अर्थात् उनके अवयव समतुल्य हैं.

{{math proof | proof = $w$ हैमिंग वज़न (या गैर-शून्य प्रविष्टियों की संख्या) हो $E$. तब $E$ बिलकुल है $w$त्रुटि विवरण. के लिए $w=0,1,$साबित करने के लिए कुछ भी नहीं है. तो हम ऐसा मान लेते हैं $w\geqslant 2$ और यह कि विवरण समान नहीं हैं। हम देखते हैं कि प्रत्येक गैर-शून्य प्रविष्टि$E$ wमैं पैटर्न में दिखाई दूंगा, और इसी तरह, इसके अवयव भी$E$ पैटर्न में सम्मिलित नहीं किए जाने पर शून्यों का चक्रीय क्रम बनेगा, जो अंतिम गैर-शून्य प्रविष्टि के पश्चात प्रारंभ होगा, और पैटर्न की पहली गैर-शून्य प्रविष्टि से ठीक पहले जारी रहेगा। हम इस रन के अनुरूप सूचकांकों के सेट को शून्य रन कहते हैं। हमने तुरंत देखा कि प्रत्येक बर्स्ट विवरण के साथ एक शून्य रन जुड़ा हुआ है और प्रत्येक शून्य रन असंयुक्त है। चूंकि हमारे पास है $w$ शून्य रन, और प्रत्येक असंयुक्त है, हमारे पास कुल है $n-w$सभी शून्य रन में विशिष्ट तत्व। दूसरी ओर हमारे पास है:

$${\begin{aligned}n-w={\text{number of zeros in }}E&\geqslant (n-\mathrm {length} (P_{1}))+(n-\mathrm {length} (P_{2}))\\&=2n-\left(\mathrm {length} (P_{1})+\mathrm {length} (P_{2})\right)\\&\geqslant 2n-(n+1)&&\mathrm {length} (P_{1})+\mathrm {length} (P_{2})\leqslant n+1\\&=n-1\end{aligned}}$$

यह विरोधाभासी है $w\geqslant 2.$ इस प्रकार, बर्स्ट त्रुटि विवरण समान हैं.}}

उपरोक्त प्रमेय का परिणाम यह है कि हमारे पास लंबाई के बर्स्ट के लिए दो भिन्न -भिन्न बर्स्ट ${\tfrac {1}{2}}(n+1).$ विवरण नहीं हो सकते हैं

बर्स्ट त्रुटि सुधार के लिए चक्रीय कोड

चक्रीय कोड को इस प्रकार परिभाषित किया गया है: $q$ प्रतीक को $\mathbb {F} _{q}$ के अवयव के रूप के बारे में सोचें. अब, हम शब्दों को $\mathbb {F} _{q},$ से अधिक बहुपद के रूप में सोच सकते हैं जहां किसी शब्द के भिन्न -भिन्न प्रतीक बहुपद के विभिन्न गुणांकों से मेल खाते हैं। चक्रीय कोड को परिभाषित करने के लिए, हम निश्चित बहुपद चुनते हैं, जिसे जनरेटर बहुपद कहा जाता है। इस चक्रीय कोड के कोडवर्ड वे सभी बहुपद हैं जो इस जनरेटर बहुपद से विभाज्य हैं।

कोडवर्ड डिग्री $\leqslant n-1$ के बहुपद हैं. मान लीजिए कि जनरेटर बहुपद $g(x)$ की डिग्री $r$ है . तथा $\leqslant n-1$ डिग्री के बहुपद जिनसे $g(x)$ विभाज्य होते हैं $g(x)$ को घात $\leqslant n-1-r$ के बहुपदों से गुणा करने से परिणाम प्राप्त होते है . अपने पास $q^{n-r}$ ऐसे बहुपद है. उनमें से प्रत्येक कोडवर्ड से मेल खाता है। इसलिए, $k=n-r$ चक्रीय कोड के लिए उपयोग किये जाते है .

चक्रीय कोड $\ell =n-k=r$ तक की लंबाई के सभी बर्स्ट का पता लगा सकते हैं . हम पश्चात में देखेंगे कि किसी की $(n,k)$ बर्स्ट त्रुटि का पता लगाने की क्षमता कोड ऊपर से $\ell \leqslant n-k$ तक सीमित है। . बर्स्ट त्रुटि का पता लगाने के लिए चक्रीय कोड को इष्टतम माना जाता है क्योंकि वे इस ऊपरी सीमा को पूरा करते हैं:

Theorem (Cyclic burst correction capability) — डिग्री के जनरेटर बहुपद के साथ प्रत्येक चक्रीय कोड $r$ लंबाई के सभी विस्फोटों का पता लगा सकता है $\leqslant r.$

{{math proof | proof =$\leqslant r$ कोडवर्ड के लिए (अर्थात एक बहुपद के लिए जो विभाज्य है $g(x)$), तब परिणाम कोई कोडवर्ड नहीं होगा (अर्थात संबंधित बहुपद इससे विभाज्य नहीं है) $g(x)$). यह दिखाने के लिए पर्याप्त है कि लंबाई में कोई उछाल नहीं है $\leqslant r$से विभाज्य है $g(x)$.ऐसे फूटने का रूप होता है $x^{i}b(x)$, जहाँ $\deg(b(x))<r.$ इसलिए, $b(x)$से विभाज्य नहीं है $g(x)$ (क्योंकि पश्चात वाले के पास डिग्री है$r$). $g(x)$से विभाज्य नहीं है $x$ (अन्यथा, सभी कोडवर्ड से प्रारंभ होंगे $0$). इसलिए, $x^{i}$से विभाज्य नहीं है$g(x)$ as well.}}

उपरोक्त प्रमाण चक्रीय कोड में बर्स्ट त्रुटि का पता लगाने/सुधार के लिए सरल एल्गोरिदम का सुझाव देता है: संचरित शब्द (अर्थात डिग्री $\leqslant n-1$ का बहुपद) दिया गया है ), जो कि $g(x)$से विभाजित करने पर इस शब्द के शेषफल की गणना करता और यदि शेषफल शून्य है (अर्थात् यदि शब्द $g(x)$ विभाज्य है ), तो यह वैध कोडवर्ड है। अन्यथा, त्रुटि की रिपोर्ट करें. इस त्रुटि को ठीक करने के लिए, इस शेषफल को प्रेषित शब्द से घटाएँ। घटाव का परिणाम $g(x)$व से िभाजित होने वाला है (अर्थात यह वैध कोडवर्ड होगा)।

बर्स्ट त्रुटि का पता लगाने पर $\ell \leqslant n-k=r$ की ऊपरी सीमा द्वारा हम जानते हैं कि चक्रीय कोड लंबाई $\ell >r$ के सभी बर्स्ट का पता नहीं लगा सकता है. चूँकि चक्रीय कोड वास्तव में लंबाई $>r$ के अधिकांश बर्स्ट का पता लगा सकते हैं .जिसका कारण यह है कि पता लगाना तभी विफल होता है जब बर्स्ट $g(x)$ विभाज्य हो . द्विआधारी वर्णमाला से अधिक, वहाँ उपस्तिथ हैं $2^{\ell -2}$ लंबाई का फटना $\ell$. उनमें से ही $2^{\ell -2-r}$ से विभाज्य हैं $g(x)$. इसलिए,) लंबाई $\ell$ के सभी बर्स्ट पर समान वितरण मानते हुए पता लगाने में विफलता की संभावना बहुत कम है ($g(x)$.

अब हम चक्रीय कोड के बारे में मौलिक प्रमेय पर विचार करते हैं जो बर्स्ट को भिन्न -भिन्न सहसमुच्चय में वर्गीकृत करके कुशल बर्स्ट-त्रुटि सुधार कोड को डिजाइन करने में सहायता करेगा।

Theorem (Distinct Cosets) — एक रेखीय कोड$C$एक$\ell$-बर्स्ट-एरर-सही कोड यदि लंबाई की सभी बर्स्ट त्रुटियां $\leqslant \ell$ भिन्न -भिन्न उपसमुच्चय में झूठ बोलें$C$.

{{math proof | proof =$\mathbf {e} _{1},\mathbf {e} _{2}$लंबाई की भिन्न -भिन्न बर्स्ट त्रुटियाँ हों $\leqslant \ell$ जो कोड के एक ही कोसेट में स्थित हैं $C$. Then $\mathbf {c} =\mathbf {e} _{1}-\mathbf {e} _{2}$ कोडवर्ड है. इसलिए, यदि हम प्राप्त करते हैं $\mathbf {e} _{1},$ हम इसे या तो डिकोड कर सकते हैं $\mathbf {0}$ or $\mathbf {c}$. इसके विपरीत, यदि सभी विस्फोट त्रुटियाँ $\mathbf {e} _{1}$ and $\mathbf {e} _{2}$ एक ही कोसेट में न रहें, तो प्रत्येक बर्स्ट त्रुटि उसके सिंड्रोम द्वारा निर्धारित होती है। फिर त्रुटि को उसके सिंड्रोम के माध्यम से ठीक किया जा सकता है। इस प्रकार, एक रैखिक कोड $C$ is an $\ell$-बर्स्ट-त्रुटि-सही कोड यदि और केवल यदि लंबाई की सभी बर्स्ट त्रुटियां$\leqslant \ell$ के भिन्न-भिन्न कोसेट में स्थित हैं$C$.}}

Theorem (Burst error codeword classification) — मान लीजिये $C$ एक रेखीय हो $\ell$-विस्फोट-त्रुटि-सुधार कोड। फिर लंबाई का कोई शून्येतर विस्फोट नहीं $\leqslant 2\ell$ कोडवर्ड हो सकता है.

Proof

$c$ लंबाई में वृद्धि के साथ एक कोडवर्ड बनें $\leqslant 2\ell$. इस प्रकार इसका पैटर्न है $(0,1,u,v,1,0)$, जहाँ $u$ and $v$ लंबाई के शब्द हैं $\leqslant \ell -1.$ इसलिए, शब्द $w=(0,1,u,0,0,0)$ and $c-w=(0,0,0,v,1,0)$ लंबाई के दो विस्फोट हैं $\leqslant \ell$. बाइनरी रैखिक कोड के लिए, वे एक ही कोसेट से संबंधित हैं। यह विशिष्ट कोसेट प्रमेय का खंडन करता है, इसलिए लंबाई का कोई गैर-शून्य विस्फोट नहीं होता है$\leqslant 2\ell$एक कोडवर्ड हो सकता है

बर्स्ट त्रुटि सुधार सीमा

बर्स्ट त्रुटि का पता लगाने और सुधार पर ऊपरी सीमा

ऊपरी सीमा से हमारा तात्पर्य हमारी त्रुटि पता लगाने की क्षमता की सीमा से है जिसे हम कभी भी पार नहीं कर सकते। मान लीजिए कि हम डिज़ाइन बनाना चाहते हैं $(n,k)$ कोड जो लंबाई की सभी बर्स्ट त्रुटियों का पता लगा सकता है $\leqslant \ell .$ पूछने के लिए स्वाभाविक प्रश्न है: दिया गया $n$ और $k$, अधिकतम क्या है $\ell$ कि हम इससे आगे कभी हासिल नहीं कर सकते? दूसरे शब्दों में, लंबाई की ऊपरी सीमा क्या है $\ell$ हम किसी भी बर्स्ट का पता लगा सकते हैं $(n,k)$ कोड? निम्नलिखित प्रमेय इस प्रश्न का उत्तर प्रदान करता है।

Theorem (Burst error detection ability) — किसी की भी बर्स्ट त्रुटि का पता लगाने की क्षमता $(n,k)$ code is $\ell \leqslant n-k.$

Proof

पहले हम देखते हैं कि एक कोड लंबाई के सभी विस्फोटों का पता लगा सकता है $\leqslant \ell$ यदि और केवल यदि कोई भी दो कोडवर्ड लंबाई के हिसाब से भिन्न न हों $\leqslant \ell$. मान लीजिए कि हमारे पास दो कोड वर्ड हैं $\mathbf {c} _{1}$ and $\mathbf {c} _{2}$जो विस्फोट से भिन्न होता है $\mathbf {b}$ लम्बाई का $\leqslant \ell$. प्राप्त करने पर $\mathbf {c} _{1}$, हम यह नहीं बता सकते कि प्रेषित शब्द वास्तव में है या नहीं $\mathbf {c} _{1}$ बिना किसी ट्रांसमिशन त्रुटि के, या चाहे वह हो $\mathbf {c} _{2}$बर्स्ट त्रुटि के साथ$\mathbf {b}$जो प्रसारण के दौरान घटित हुआ। अब, मान लीजिए कि प्रत्येक दो कोडवर्ड की लंबाई में बहुत अधिक अंतर होता है $\ell .$ भले ही प्रेषित कोडवर्ड $\mathbf {c} _{1}$ विस्फोट की चपेट में आ गया है $\mathbf {b}$ लम्बाई का $\ell$,यह किसी अन्य वैध कोडवर्ड में परिवर्तित नहीं होगा. इसे प्राप्त करने पर, हम बता सकते हैं कि यह है $\mathbf {c} _{1}$ विस्फोट के साथ$\mathbf {b} .$ उपरोक्त अवलोकन से, हम जानते हैं कि कोई भी दो कोडवर्ड पहले को साझा नहीं कर सकते हैं $n-\ell$प्रतीक. कारण यह है कि भले ही वे सभी में भिन्न हों $\ell$ प्रतीक, वे अभी भी लंबाई के आधार पर भिन्न होंगे $\ell .$ इसलिए, कोडवर्ड की संख्या $q^{k}$संतुष्ट$q^{k}\leqslant q^{n-\ell }.$ को प्रयुक्त करने $\log _{q}$ दोनों तरफ और पुनर्व्यवस्थित करके, हम इसे देख सकते हैं $\ell \leqslant n-k$.

अब, हम वही प्रश्न दोहराते हैं किन्तु त्रुटि सुधार के लिए: दिया गया है $n$ और $k$, लंबाई पर ऊपरी सीमा क्या है $\ell$ बर्स्ट का जिन्हें हम किसी का उपयोग करके ठीक कर सकते हैं $(n,k)$ कोड? निम्नलिखित प्रमेय इस प्रश्न का प्रारंभिक उत्तर प्रदान करता है:

Theorem (Burst error correction ability) — किसी की भी बर्स्ट त्रुटि सुधार क्षमता $(n,k)$ कोड संतुष्ट करता है $\ell \leqslant n-k-\log _{q}(n-\ell )+2$

Proof

पहले हम देखते हैं कि एक कोड लंबाई के सभी विस्फोटों को ठीक कर सकता है $\leqslant \ell$यदि और केवल यदि कोई भी दो कोडवर्ड लंबाई के दो बर्स्ट के योग से भिन्न न हों $\leqslant \ell .$ मान लीजिए कि दो कोडवर्ड $\mathbf {c} _{1}$ और $\mathbf {c} _{2}$ विस्फोट से भिन्न$\mathbf {b} _{1}$ and $\mathbf {b} _{2}$ लम्बाई का $\leqslant \ell$ each.प्राप्त करने पर$\mathbf {c} _{1}$विस्फोट से मारा गया$\mathbf {b} _{1}$, हम इसकी व्याख्या ऐसे कर सकते हैं जैसे कि यह था $\mathbf {c} _{2}$ विस्फोट से मारा गया $-\mathbf {b} _{2}$. हम यह नहीं बता सकते कि प्रेषित शब्द है या नहीं $\mathbf {c} _{1}$ or $\mathbf {c} _{2}$. अब, मान लीजिए कि प्रत्येक दो कोडवर्ड की लंबाई दो से अधिक भिन्न होती है $\ell$. तदपि प्रेषित कोडवर्ड $\mathbf {c} _{1}$ लम्बाई के विस्फोट से मारा जाता है $\ell$, यह किसी अन्य कोडवर्ड की तरह नहीं दिखने वाला है जो एक और विस्फोट से प्रभावित हुआ है. For each codeword $\mathbf {c} ,$ मान लीजिये $B(\mathbf {c} )$ से भिन्न सभी शब्दों के समुच्चय को निरूपित करें $\mathbf {c}$ bआप लंबाई का एक विस्फोट $\leqslant \ell .$ नोटिस जो $B(\mathbf {c} )$सम्मिलित $\mathbf {c}$अपने आप। उपरोक्त अवलोकन से, हम जानते हैं कि दो भिन्न-भिन्न कोडवर्ड के लिए $\mathbf {c} _{i}$ और $\mathbf {c} _{j},B(\mathbf {c} _{i})$ और $B(\mathbf {c} _{j})$ असंयुक्त हैं. अपने पास $q^{k}$ कोडवर्ड इसलिए हम ऐसा कह सकते हैं$q^{k}|B(\mathbf {c} )|\leqslant q^{n}$. इसके अतिरिक्त, हमारे पास है$(n-\ell )q^{\ell -2}\leqslant |B(\mathbf {c} )|$. पश्चात वाली असमानता को पहले वाली असमानता से जोड़कर, फिर आधार लेकर $q$लघुगणक और पुनर्व्यवस्थित करने पर, हमें उपरोक्त प्रमेय प्राप्त होता है।

रीगर बाउंड द्वारा मजबूत परिणाम दिया गया है:

Theorem (Rieger bound) — यदि $\ell$की बर्स्ट त्रुटि सुधार करने की क्षमता है $(n,k)$रैखिक ब्लॉक कोड, फिर$2\ell \leqslant n-k$.

Proof

कोई भी रैखिक कोड जो लंबाई के किसी भी विस्फोट पैटर्न को सही कर सकता है $\leqslant \ell$लम्बाई का विस्फोट नहीं हो सकता $\leqslant 2\ell$ एक कोडवर्ड के रूप में. यदि इसकी लम्बाई में वृद्धि होती $\leqslant 2\ell$ एक कोडवर्ड के रूप में, फिर लंबाई का विस्फोट$\ell$ कोडवर्ड को लंबाई के बर्स्ट पैटर्न में बदल सकता है $\ell$, जिसे लंबाई की बर्स्ट त्रुटि बनाकर भी प्राप्त किया जा सकता है $\ell$ बिल्कुल शून्य कोडवर्ड में. यदि सदिश पहले शून्येतर हैं$2\ell$ प्रतीकों, तो सदिश एक सरणी के विभिन्न उपसमूहों से होने चाहिए ताकि उनका अंतर लंबाई के फटने का कोडवर्ड न हो$2\ell$. इस शर्त को सुनिश्चित करते हुए, ऐसे उपसमुच्चय की संख्या कम से कम सदिश की संख्या के समान्तर है। इस प्रकार, उपसमुच्चय की संख्या कम से कम होगी$q^{2\ell }$.इसलिए, हमारे पास कम से कम है $2\ell$ अलग-अलग प्रतीक, अन्यथा, ऐसे दो बहुपदों का अंतर एक कोडवर्ड होगा जो लंबाई के दो विस्फोटों का योग है $\leqslant \ell .$ इस प्रकार, यह रीगर बाउंड सिद्ध होता है।

परिभाषा। उपरोक्त रीगर सीमा को प्राप्त करने वाले रैखिक बर्स्ट-त्रुटि-सुधार करने वाले कोड को इष्टतम बर्स्ट-त्रुटि-सुधार करने वाला कोड कहा जाता है।

बर्स्ट त्रुटि सुधार पर आगे की सीमाएं

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

Theorem (number of bursts) — इसके लिए $1\leqslant \ell \leqslant {\tfrac {1}{2}}(n+1),$ एक द्विआधारी वर्णमाला पर, वहाँ हैं $n2^{\ell -1}+1$ लंबाई के सदिश$n$ जो लम्बाई के विस्फोट हैं $\leqslant \ell$.

Proof

चूंकि बर्स्ट की लंबाई है$\leqslant {\tfrac {1}{2}}(n+1),$विस्फोट के साथ एक अनोखा विस्फोट वर्णन जुड़ा हुआ है। विस्फोट इनमें से किसी पर भी प्रारंभ हो सकता है $n$ पैटर्न की स्थिति. प्रत्येक पैटर्न की प्रारंभिक होती है$1$ और की लंबाई सम्मलित है $\ell$. हम इसे प्रारंभ होने वाली सभी स्ट्रिंग्स के समूह के रूप में सोच सकते हैं $1$ और लंबाई है $\ell$. इस प्रकार, कुल हैं$2^{\ell -1}$ऐसे पैटर्न संभव हैं, और कुल $n2^{\ell -1}$लंबाई का फटना$\leqslant \ell .$यदि हम सर्व-शून्य विस्फोट को सम्मिलित करते हैं, तो हमारे पास है $n2^{\ell -1}+1$ सदिश लंबाई के विस्फोट का प्रतिनिधित्व करते हैं $\leqslant \ell .$

Theorem (Bound on the number of codewords) — यदि $1\leqslant \ell \leqslant {\tfrac {1}{2}}(n+1),$बाइनरी $\ell$-विस्फोट त्रुटि सुधार कोड में अधिकतम है $2^{n}/(n2^{\ell -1}+1)$ कूटशब्द.

Proof

Since $\ell \leqslant {\tfrac {1}{2}}(n+1)$, हम जानते हैं कि वहाँ हैं $n2^{\ell -1}+1$लंबाई का फटना$\leqslant \ell$. कहो कोड है $M$ कोडवर्ड, तो वहाँ हैं $Mn2^{\ell -1}$ऐसे कोडवर्ड जो लंबाई की दृष्टि से कोडवर्ड से भिन्न होते हैं $\leqslant \ell$.हरेक $M$ शब्द भिन्न-भिन्न होने चाहिए, अन्यथा कोड में दूरी होगी$<1$. इसलिए, $M(2^{\ell -1}+1)\leqslant 2^{n}$ तात्पर्य $M\leqslant 2^{n}/(n2^{\ell -1}+1).$

Theorem (Abramson's bounds) — यदि $1\leqslant \ell \leqslant {\tfrac {1}{2}}(n+1)$ एक बाइनरी है रैखिक $(n,k),\ell$-बर्स्ट त्रुटि सुधार कोड, इसकी ब्लॉक-लंबाई को संतुष्ट करना होगा:

$$n\leqslant 2^{n-k-\ell +1}-1.$$

Proof

For a linear $(n,k)$ कोड, वहाँ हैं $2^{k}$ कोडवर्ड हमारे पिछले परिणाम से, हम यह जानते हैं

$$2^{k}\leqslant {\frac {2^{n}}{n2^{\ell -1}+1}}.$$

भिन्न $n$, we get $n\leqslant 2^{n-k-\ell +1}-2^{-\ell +1}$.तब से $\ell \geqslant 1$ and $n$एक पूर्णांक होना चाहिए, हमारे पास है $n\leqslant 2^{n-k-\ell +1}-1$.

टिप्पणी। $r=n-k$ कोड की अतिरेक कहा जाता है और अब्रामसन की सीमा के लिए वैकल्पिक सूत्रीकरण में है $r\geqslant \lceil \log _{2}(n+1)\rceil +\ell -1.$

अग्नि कोड

जबकि सामान्यतः चक्रीय कोड बर्स्ट त्रुटियों का पता लगाने के लिए शक्तिशाली उपकरण होते हैं, अब हम फायर कोड नामक बाइनरी चक्रीय कोड के वर्ग पर विचार करते हैं, जिसमें अच्छी एकल बर्स्ट त्रुटि सुधार क्षमताएं होती हैं। एकल बर्स्ट से, लंबाई $\ell$ के बारे में कहें , हमारा अर्थ है कि प्राप्त कोडवर्ड में उपस्तिथ सभी त्रुटियां निश्चित अवधि के अंदर होती हैं $\ell$ अंक है .

मान लीजिये $p(x)$ डिग्री का अपरिवर्तनीय बहुपद बनें $m$ ऊपर $\mathbb {F} _{2}$, और जाने $p$ की अवधि हो $p(x)$. की अवधि $p(x)$, और वास्तव में किसी भी बहुपद को सबसे कम धनात्मक पूर्णांक के रूप में परिभाषित किया गया है $r$ ऐसा है कि $p(x)|x^{r}-1.$ होने देना $\ell$ धनात्मक पूर्णांक $\ell \leqslant m$ और $2\ell -1$ संतोषजनक हो तथा $p$ से विभाज्य नहीं है , जहाँ $p$ की अवधि है $p(x)$. अग्नि संहिता को परिभाषित करें $G$ निम्नलिखित जनरेटर बहुपद द्वारा:

$$g(x)=\left(x^{2\ell -1}+1\right)p(x).$$

हम वो दिखाएंगे $G$ $\ell$-बर्स्ट -त्रुटि सुधार कोड।

Lemma 1 — $\gcd \left(p(x),x^{2\ell -1}+1\right)=1.$

Proof

Let $d(x)$ दो बहुपदों का सबसे बड़ा सामान्य भाजक बनें। तब से $p(x)$ अपरिवर्तनीय है, $\deg(d(x))=0$ या $\deg(p(x))$.मान लीजिए $\deg(d(x))\neq 0,$ तब $p(x)=cd(x)$ for कुछ स्थिर$c$. किन्तु, $(1/c)p(x)$ का भाजक है$x^{2\ell -1}+1$ तब से$d(x)$ का भाजक है$x^{2\ell -1}+1$.किन्तु यह हमारी धारणा का खंडन करता है$p(x)$ विभाजित नहीं करता $x^{2\ell -1}+1.$ यद्यपि, $\deg(d(x))=0,$ प्रमेयिका सिद्ध करना.

Lemma 2 — यदि $p(x)$काल का एक बहुपद है$p$, तब $p(x)|x^{k}-1$ यदि और केवल यदि$p|k.$

Proof

यदि $p|k$, तब $x^{k}-1=(x^{p}-1)(1+x^{p}+x^{2p}+\dots +x^{k/p})$. इस प्रकार, $p(x)|x^{k}-1.$

अब मान लीजिए $p(x)|x^{k}-1$. तब , $k\geqslant p$. हम वो दिखाते हैं$k$से विभाज्य है $p$ पर प्रेरण द्वारा $k$. आधार स्तिथि $k=p$अनुसरण करता है। इसलिए, मान लीजिए$k>p$.हम वह जानते हैं$p(x)$ दोनों को विभाजित करता है (क्योंकि इसमें आवर्त है$p$)

$$x^{p}-1=(x-1)\left(1+x+\dots +x^{p-1}\right)\quad {\text{and}}\quad x^{k}-1=(x-1)\left(1+x+\dots +x^{k-1}\right).$$

किन्तु $p(x)$ अपरिवर्तनीय है, इसलिए इसे दोनों को विभाजित करना होगा $(1+x+\dots +x^{p-1})$ and $(1+x+\dots +x^{k-1})$; इस प्रकार, यह अंतिम दो बहुपदों के अंतर को भी विभाजित करता है, $x^{p}(1+x+\dots +x^{p-k-1})$. फिर, यह उसका अनुसरण करता है $p(x)$ divides $(1+x+\cdots +x^{p-k-1})$. अंत में, यह भी विभाजित होता है:$x^{k-p}-1=(x-1)(1+x+\dots +x^{p-k-1})$.प्रेरण परिकल्पना द्वारा,$p|k-p$, तब $p|k$.

लेम्मा 2 का एक परिणाम यह है कि तब से $p(x)=x^{p}-1$अवधि है $p$, तब $p(x)$ विभाजित$x^{k}-1$ यदि और केवल यदि $p|k$.

Theorem — फायर कोड है$\ell$-विस्फोट त्रुटि को सुधारना

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

प्रमेय का प्रमाण

मान लीजिए कि $x^{i}a(x)$ और $x^{j}b(x)$ डिग्री $\ell _{1}-1$ और $\ell _{2}-1$ के साथ बहुपद हैं, जो क्रमशः $\ell _{1},\ell _{2}\leqslant \ell .$ के साथ लंबाई $\ell _{1}$ और $\ell _{2}$ के विस्फोट का प्रतिनिधित्व करते हैं, पूर्णांक $i,j$ प्रारंभिक का प्रतिनिधित्व करते हैं बर्स्ट की स्थिति, और कोड की ब्लॉक लंबाई से कम होते हैं। विरोधाभास के लिए, यह मान लें $x^{i}a(x)$ और $x^{j}b(x)$ ही सहसमुच्चय में हैं. तब, $v(x)=x^{i}a(x)+x^{j}b(x)$ वैध कोडवर्ड है (क्योंकि दोनों पद ही सहसमुच्चय में हैं)। व्यापकता की हानि के बिना, $i\leqslant j$.चुनें विभाजन प्रमेय द्वारा हम लिख सकते हैं: पूर्णांकों $g$ और $r,0\leqslant r<2\ell -1$ के लिए $j-i=g(2\ell -1)+r,$| हम बहुपद को फिर से लिखते हैं $v(x)$ निम्नलिखित नुसार:

$$v(x)=x^{i}a(x)+x^{i+g(2\ell -1)+r}=x^{i}a(x)+x^{i+g(2\ell -1)+r}+2x^{i+r}b(x)=x^{i}\left(a(x)+x^{b}b(x)\right)+x^{i+r}b(x)\left(x^{g(2\ell -1)}+1\right)$$

ध्यान दें कि दूसरे परिवर्तन में, हमने $2x^{i+r}b(x)$ शब्द प्रस्तुत किया . हमें ऐसा करने की अनुमति है, क्योंकि फायर कोड $\mathbb {F} _{2}$ क्रियान्वित हैं . और हमारी धारणा से, $v(x)$ वैध कोडवर्ड है, तथा इस प्रकार, इसका गुणज $g(x)$ होना चाहिए . जैसा कि पहले उल्लेख किया गया है, कि $g(x)$कारकों के पश्चात $v(x)$से अपेक्षाकृत प्रमुख हैं, जो कि $x^{2\ell -1}+1$ से विभाज्य होना चाहिए . $v(x)$ के लिए व्युत्पन्न अंतिम अभिव्यक्ति को समीप से देख रहे हैं हम उस पर ध्यान देते हैं कि $x^{g(2\ell -1)}+1$, $x^{2\ell -1}+1$ (लेम्मा 2 के परिणाम द्वारा ) से विभाज्य है। इसलिए, $a(x)+x^{b}b(x)$ या $x^{2\ell -1}+1$ तो विभाज्य $0$ है विभाजन प्रमेय को दोबारा प्रयुक्त करने पर, हम देखते हैं कि $\delta$ वाला बहुपद $d(x)$ पर इस प्रकार उपस्तिथ है

$$a(x)+x^{b}b(x)=d(x)(x^{2\ell -1}+1)$$

तब हम लिख सकते हैं:

$${\begin{aligned}\delta +2\ell -1&=\deg \left(d(x)\left(x^{2\ell -1}+1\right)\right)\\&=\deg \left(a(x)+x^{b}b(x)\right)\\&=\deg \left(x^{b}b(x)\right)&&\deg(a(x))=\ell _{1}-1<2\ell -1\\&=b+\ell _{2}-1\end{aligned}}$$

दोनों पक्षों की डिग्री को समान करने से हमें $b=2\ell -\ell _{2}+\delta .$ प्राप्त होता है तब से $\ell _{1},\ell _{2}\leqslant \ell$ हम निष्कर्ष निकाल सकते हैं $b\geqslant \ell +\delta ,$ जो ये दर्शाता हे $b>\ell -1$ और $b>\delta$. ध्यान दें कि विस्तार में:

$$a(x)+x^{b}b(x)=1+a_{1}x+a_{2}x^{2}+\dots +x^{\ell _{1}-1}+x^{b}\left(1+b_{1}x+b_{2}x^{2}+\dots +x^{\ell _{2}-1}\right).$$

शब्द $x^{b}$ प्रकट होता है, किन्तु $\delta <b<2\ell -1$ के पश्चात से , परिणामी अभिव्यक्ति $d(x)(x^{2\ell -1}+1)$ में $x^{b}$ सम्मिलित नहीं है, इसलिए $d(x)=0$ और पश्चात में $a(x)+x^{b}b(x)=0.$ इसके लिए इसकी आवश्यकता है कि $b=0$, और $a(x)=b(x)$. हम $b=0,$ अर्थात $j-i=g(2\ell -1)$. को प्रतिबिंबित करने के लिए $j-i$ के अपने विभाजन को $g(2\ell -1)$ तक संशोधित कर सकते हैं। $v(x)$ में वापस प्रतिस्थापित करने पर हमें प्राप्त होता है,,

$$v(x)=x^{i}b(x)\left(x^{j-1}+1\right).$$

तब से $\deg(b(x))=\ell _{2}-1<\ell$, अपने पास $\deg(b(x))<\deg(p(x))=m$. किन्तु $p(x)$ इसलिए, अपरिवर्तनीय है $b(x)$ और $p(x)$ अपेक्षाकृत प्रधान होना चाहिए। तब से $v(x)$ कोडवर्ड है, $x^{j-1}+1$ से विभाज्य होना चाहिए $p(x)$, क्योंकि इसे विभाज्य नहीं किया जा सकता $x^{2\ell -1}+1$. इसलिए, $j-i$ का गुणज होना चाहिए $p$. किन्तु इसका गुणज भी होना चाहिए $2\ell -1$, जिसका अर्थ है कि यह का गुणज होना चाहिए $n={\text{lcm}}(2\ell -1,p)$ किन्तु वह बिल्कुल कोड की ब्लॉक-लंबाई है। इसलिए, $j-i$ का गुणज नहीं हो सकता $n$ चूँकि वे दोनों इससे कम हैं $n$. इस प्रकार, हमारी धारणा $v(x)$ कोडवर्ड होना गलत है, और इसलिए $x^{i}a(x)$ और $x^{j}b(x)$ अद्वितीय सिंड्रोम के साथ भिन्न -भिन्न सहसमुच्चय में हैं, और इसलिए सुधार योग्य हैं।

उदाहरण: फायर कोड को सही करने में 5-बर्स्ट त्रुटि

उपरोक्त अनुभाग में प्रस्तुत सिद्धांत के साथ, के निर्माण पर विचार करें $5$-फ़ायर कोड को सही करने में बर्स्ट त्रुटि। याद रखें कि फायर कोड बनाने के लिए, हमें अपरिवर्तनीय बहुपद की आवश्यकता होती है $p(x)$, पूर्णांक $\ell$, हमारे कोड की बर्स्ट त्रुटि सुधार क्षमता का प्रतिनिधित्व करता है, और हमें उस संपत्ति को संतुष्ट करने की आवश्यकता है

 $2\ell -1$ की अवधि से विभाज्य नहीं है $p(x)$. इन आवश्यकताओं को ध्यान में रखते हुए, अपरिवर्तनीय बहुपद पर विचार करें $p(x)=1+x^{2}+x^{5}$, और जाने $\ell =5$. तब से $p(x)$ आदिम बहुपद है, इसका आवर्त है $2^{5}-1=31$. हम इसकी पुष्टि करते हैं $2\ell -1=9$ से विभाज्य नहीं है $31$. इस प्रकार,

$$g(x)=(x^{9}+1)\left(1+x^{2}+x^{5}\right)=1+x^{2}+x^{5}+x^{9}+x^{11}+x^{14}$$

इस प्रकार फायर कोड जनरेटर है. हम न्यूनतम समापवर्त्य का मूल्यांकन करके कोड की ब्लॉक-लंबाई की गणना कर सकते हैं $p$ और $2\ell -1$. दूसरे शब्दों में, $n={\text{lcm}}(9,31)=279$. इस प्रकार, उपरोक्त फायर कोड चक्रीय कोड है जो लंबाई के किसी भी बर्स्ट को ठीक करने में सक्षम है $5$ या कम।

बाइनरी रीड-सोलोमन कोड

कोड के कुछ वर्ग , जैसे रीड-सोलोमन त्रुटि सुधार|रीड-सोलोमन, बाइनरी से बड़े वर्णमाला आकार पर काम करते हैं। यह संपत्ति ऐसे कोड को शक्तिशाली बर्स्ट त्रुटि सुधार क्षमताएं प्रदान करती है। $\mathbb {F} _{2^{m}}$उस कोड पर विचार करें जिस पर कार्य चल रहा है . वर्णमाला $m$ के प्रत्येक प्रतीक को $m$ बिट्स द्वारा दर्शाया जा सकता है? यदि $C$ $\mathbb {F} _{2^{m}}$ के ऊपर $(n,k)$ रीड-सोलोमन कोड ख़त्म है, हम $C$ को $\mathbb {F} _{2}$ के ऊपर $[mn,mk]_{2}$ कोड के रूप में सोच सकते हैं .

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

ध्यान दें कि बर्स्ट $(m+1)$ त्रुटियाँ अधिकतम प्रभावित कर सकती हैं $2$ प्रतीकों, और का बर्स्ट $2m+1$ अधिक से अधिक प्रभावित कर सकता है $3$ प्रतीक. फिर, बर्स्ट $tm+1$ अधिक से अधिक प्रभावित कर सकता है $t+1$ प्रतीक; इसका तात्पर्य यह है कि ए $t$-प्रतीक-त्रुटि सुधार कोड अधिकतम लंबाई के बर्स्ट को ठीक कर सकता है $(t-1)m+1$.

सामान्यतः , a $t$-रीड-सोलोमन कोड को सही करने में त्रुटि $\mathbb {F} _{2^{m}}$ के किसी भी संयोजन को ठीक कर सकता है

$${\frac {t}{1+\lfloor (l+m-2)/m\rfloor }}$$

या लंबाई के कम बर्स्ट $l$, सही करने में सक्षम होने के शीर्ष पर $t$-यादृच्छिक सबसे व्यर्थ स्थिति त्रुटियाँ।

बाइनरी आरएस कोड का उदाहरण

मान लीजिये $G$ हो $[255,223,33]$ आरएस कोड ख़त्म $\mathbb {F} _{2^{8}}$. इस कोड को नासा ने अपने कैसिनी-हुय्गेंस अंतरिक्ष यान में नियोजित किया था। यह ठीक करने में सक्षम है $\lfloor 33/2\rfloor =16$ प्रतीक त्रुटियाँ. अब हम बाइनरी आरएस कोड बनाते हैं $G'$ से $G$. प्रत्येक चिन्ह का प्रयोग करके लिखा जायेगा $\lceil \log _{2}(255)\rceil =8$ बिट्स इसलिए, बाइनरी आरएस कोड होगा $[2040,1784,33]_{2}$ इसके पैरामीटर के रूप में। यह लंबाई के किसी भी बर्स्ट को ठीक करने में सक्षम है $l=121$.

इंटरलीव्ड कोड

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

इंटरलीवर की बर्स्ट त्रुटि सुधार क्षमता

पंक्ति और स्तंभ-प्रमुख क्रम का चित्रण

Theorem — यदि बर्स्ट एरर को कुछ कोड की सही करने की क्षमता है $\ell ,$ फिर बर्स्ट त्रुटि को ठीक करने की क्षमता $\lambda$-वे इंटरलीव है $\lambda \ell .$

Proof

मान लीजिए कि हमारे पास एक $(n,k)$ कोड जो लंबाई के सभी विस्फोटों को ठीक कर सकता है $\leqslant \ell .$ इंटरलीविंग हमें प्रदान कर सकता है$(\lambda n,\lambda k)$ कोड जो लंबाई के सभी विस्फोटों को ठीक कर सकता है $\leqslant \lambda \ell ,$किसी भी दिए गए के लिए$\lambda$.यदि हम इंटरलीविंग का उपयोग करके अपनी इच्छानुसार लंबाई के संदेश को एन्कोड करना चाहते हैं, तो पहले हम इसे लंबाई के ब्लॉक में विभाजित करते हैं $\lambda k$.हम लिखते हैं$\lambda k$ प्रत्येक ब्लॉक की प्रविष्टियाँ a $\lambda \times k$ पंक्ति-प्रमुख क्रम का उपयोग कर मैट्रिक्स। फिर, हम प्रत्येक पंक्ति का उपयोग करके एन्कोड करते हैं $(n,k)$ कोड. हमें जो मिलेगा वह है a $\lambda \times n$ आव्यूह। अब, इस आव्यूह को कॉलम-प्रमुख क्रम में पढ़ा और प्रसारित किया जाता है। विधि यह है कि यदि लम्बाई का विस्फोट होता है$h$ प्रेषित शब्द में, तो प्रत्येक पंक्ति में लगभग शामिल होगा${\tfrac {h}{\lambda }}$लगातार त्रुटियाँ (अधिक विशेष रूप से, प्रत्येक पंक्ति में कम से कम लंबाई का विस्तार होगा $\lfloor {\tfrac {h}{\lambda }}\rfloor$और अधिक से अधिक$\lceil {\tfrac {h}{\lambda }}\rceil$).यदि $h\leqslant \lambda \ell ,$ तब ${\tfrac {h}{\lambda }}\leqslant \ell$ और यह $(n,k)$कोड प्रत्येक पंक्ति को सही कर सकता है। इसलिए, इंटरलीव्ड $(\lambda n,\lambda k)$ कोड लंबाई के विस्फोट को ठीक कर सकता है $h$.इसके विपरीत, यदि$h>\lambda \ell ,$तो कम से कम एक पंक्ति में इससे अधिक होंगे ${\tfrac {h}{\lambda }}$निरंतर त्रुटियाँ, और $(n,k)$कोड उन्हें ठीक करने में विफल हो सकता है। इसलिए, इंटरलीव्ड की त्रुटि सुधार क्षमता$(\lambda n,\lambda k)$ कोड बिल्कुल सही है$\lambda \ell .$ इंटरलीव्ड कोड की बीईसी दक्षता मूल के समान ही रहती है $(n,k)$ कोड. यह सच है क्योंकि:

$${\frac {2\lambda \ell }{\lambda n-\lambda k}}={\frac {2\ell }{n-k}}$$

ब्लॉक इंटरलीवर

नीचे दिया गया चित्र 4 बाय 3 इंटरलीवर दिखाता है।

ब्लॉक इंटरलीवर का उदाहरण

उपरोक्त इंटरलीवर को ब्लॉक इंटरलीवर कहा जाता है। यहां, इनपुट प्रतीकों को पंक्तियों में क्रमिक रूप से लिखा जाता है और आउटपुट प्रतीकों को स्तम्भ को क्रमिक रूप से पढ़कर प्राप्त किया जाता है। इस प्रकार, यह इस रूप में है $M\times N$ सरणी. सामान्यतः , $N$ कोडवर्ड की लंबाई है.

ब्लॉक इंटरलीवर की क्षमता: के लिए $M\times N$ ब्लॉक इंटरलीवर और लंबाई का फटना $\ell ,$ त्रुटियों की संख्या की ऊपरी सीमा है ${\tfrac {\ell }{M}}.$ यह इस तथ्य से स्पष्ट है कि हम आउटपुट को स्तम्भ के अनुसार पढ़ रहे हैं और पंक्तियों की संख्या है $M$. उपरोक्त प्रमेय के अनुसार त्रुटि सुधार क्षमता तक $t,$ अनुमत अधिकतम बर्स्ट लंबाई है $Mt.$ की बर्स्ट लंबाई के लिए $Mt+1$, डिकोडर विफल हो सकता है।

ब्लॉक इंटरलीवर की दक्षता ($\gamma$): यह बर्स्ट लंबाई का अनुपात लेकर पाया जाता है जहां डिकोडर इंटरलीवर मेमोरी में विफल हो सकता है। इस प्रकार, हम सूत्रीकरण कर सकते हैं $\gamma$ जैसा

$$\gamma ={\frac {Mt+1}{MN}}\approx {\frac {t}{N}}.$$

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

कन्वेंशनल इंटरलीवर

क्रॉस इंटरलीवर प्रकार का मल्टीप्लेक्सर-डेमल्टीप्लेक्सर प्रणाली है। इस प्रणाली में, लंबाई को उत्तरोत्तर बढ़ाने के लिए विलंब रेखाओं का उपयोग किया जाता है। विलंब रेखा मूल रूप से इलेक्ट्रॉनिक परिपथ है जिसका उपयोग सिग्नल को निश्चित समय अवधि तक विलंबित करने के लिए किया जाता है। होने देना $n$ विलंब रेखाओं की संख्या हो और $d$ प्रत्येक विलंब रेखा द्वारा प्रस्तुत प्रतीकों की संख्या हो। इस प्रकार, निरंतर इनपुट के बीच भिन्नता = $nd$ प्रतीक. कोडवर्ड की लंबाई बताएं $\leqslant n.$ इस प्रकार, इनपुट कोडवर्ड में प्रत्येक प्रतीक भिन्न विलंब रेखा पर होगा। लंबाई की बर्स्ट त्रुटि दें $\ell$ घटित होना। चूँकि $nd,$ क्रमागत प्रतीकों के बीच पृथक्करण है डीइंटरलीव्ड आउटपुट में त्रुटियों की संख्या ${\tfrac {\ell }{nd+1}}.$हो सकती है उपरोक्त प्रमेय के अनुसार, त्रुटि सुधार क्षमता $t$ तक, अनुमत अधिकतम बर्स्ट लंबाई $(nd+1)(t-1).$ है तथा इसकी बर्स्ट लंबाई के लिए $(nd+1)(t-1)+1,$ डिकोडर विफल हो सकता है.

कन्वेल्यूशनल इंटरलीवर का उदाहरण

डिइंटरलीवर का उदाहरण

क्रॉस इंटरलीवर की दक्षता ($\gamma$): यह बर्स्ट लंबाई के अनुपात को लेकर पाया जाता है जहां डिकोडर इंटरलीवर मेमोरी में विफल हो सकता है। इस उपस्तिथियों में, इंटरलीवर की मेमोरी की गणना इस प्रकार की जा सकती है

$$(0+1+2+3+\cdots +(n-1))d={\frac {n(n-1)}{2}}d.$$

इस प्रकार, हम $\gamma$ का सूत्रीकरण कर सकते हैं निम्नलिखित नुसार:

$$\gamma ={\frac {(nd+1)(t-1)+1}{{\frac {n(n-1)}{2}}d}}.$$

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

अनुप्रयोग

कॉम्पैक्ट डिस्क

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

वर्तमान कॉम्पैक्ट डिस्क डिजिटल ऑडियो प्रणाली नीदरलैंड के एन. वी. फिलिप्स और जापान के सोनी कॉरपोरेशन (1979 में हस्ताक्षरित समझौते) द्वारा विकसित किया गया था।

कॉम्पैक्ट डिस्क में स्पष्ट प्लास्टिक कोटिंग के साथ लेपित 120 मिमी एल्युमिनाइज्ड डिस्क होती है, जिसमें सर्पिल ट्रैक होता है, जिसकी लंबाई लगभग 5 किमी होती है, जिसे ~ 0.8 माइक्रोमीटर तरंग दैर्ध्य के लेजर द्वारा ~ 1.25 मीटर/सेकेंड की निरंतर गति से ऑप्टिकली स्कैन किया जाता है। इस स्थिर गति को प्राप्त करने के लिए, ट्रैक के आंतरिक भाग पर स्कैन करते समय डिस्क का घुमाव ~8 रेव/सेकेंड से लेकर बाहरी भाग पर ~3.5 रेव/सेकेंड तक भिन्न होता है। गड्ढे और भूमि अवसाद (0.12 माइक्रोमीटर गहरे) और समतल खंड हैं जो ट्रैक के साथ बाइनरी डेटा बनाते हैं (0.6 माइक्रोमीटर चौड़ाई)।

सीडी प्रक्रिया को निम्नलिखित उप-प्रक्रियाओं के अनुक्रम के रूप में समझा जा सकता है:

• सिग्नल के स्रोत का चैनल एन्कोडिंग
• मास्टर डिस्क तैयार करने, उपयोगकर्ता डिस्क का उत्पादन करने और खेलते समय उपयोगकर्ता डिस्क पर एम्बेडेड संकेतों को अनुभूत करने की यांत्रिक उप-प्रक्रियाएँ - चैनल
• उपयोगकर्ता डिस्क से प्राप्त संकेतों को डिकोड करना

यह प्रक्रिया बर्स्ट त्रुटियों और यादृच्छिक त्रुटियों दोनों के अधीन है।बर्स्ट त्रुटियों में डिस्क सामग्री (एल्यूमीनियम प्रतिबिंबित फिल्म के दोष, पारदर्शी डिस्क सामग्री का व्यर्थ प्रतिबिंबित सूचकांक), डिस्क उत्पादन (डिस्क बनाने और डिस्क काटने आदि के दौरान दोष), डिस्क हैंडलिंग (स्क्रैच - सामान्यतः पतली, रेडियल और रिकॉर्डिंग की दिशा में ऑर्थोगोनल) और प्ले-बैक तंत्र में भिन्नताएं सम्मिलित हैं। यादृच्छिक त्रुटियों में पुनर्निर्मित सिग्नल तरंग की घबराहट और सिग्नल में हस्तक्षेप के कारण होने वाली त्रुटियां सम्मिलित हैं। सीआईआरसी (क्रॉस-इंटरलीव्ड रीड-सोलोमन कोडिंग|क्रॉस-इंटरलीव्ड रीड-सोलोमन कोड) सीडी प्रक्रिया में त्रुटि का पता लगाने और सुधार का आधार है। यह क्रमिक रूप से 3,500 बिट्स (सीडी सतह पर देखी गई लंबाई में 2.4 मिमी) तक त्रुटि बर्स्ट को ठीक करता है और 12,000 बिट्स (8.5 मिमी) तक त्रुटि बर्स्ट की भरपाई करता है जो मामूली खरोंच के कारण हो सकते हैं।

एन्कोडिंग: ध्वनि-तरंगों का नमूना लिया जाता है और ए/डी कनवर्टर द्वारा डिजिटल रूप में परिवर्तित किया जाता है। ध्वनि तरंग का नमूना आयाम के लिए लिया जाता है (44.1 kHz या 44,100 जोड़े पर, स्टीरियो ध्वनि के बाएँ और दाएँ चैनलों के लिए एक-एक)। उदाहरण पर आयाम को लंबाई 16 की बाइनरी स्ट्रिंग सौंपी गई है। इस प्रकार, प्रत्येक नमूना दो बाइनरी सदिश $\mathbb {F} _{2}^{16}$ या 4 $\mathbb {F} _{2}^{8}$ डेटा के बाइट्स उत्पन्न करता है. रिकॉर्ड की गई ध्वनि के प्रत्येक सेकंड में 44,100 × 32 = 1,411,200 बिट्स (176,400 बाइट्स) डेटा प्राप्त होता है।1.41 एमबिट्स/एस नमूना डेटा स्ट्रीम त्रुटि सुधार प्रणाली से होकर गुजरती है और अंततः 1.88 एमबिट्स/एस की स्ट्रीम में परिवर्तित हो जाती है।

एनकोडर के लिए इनपुट में 24 8-बिट प्रतीकों (ए/डी कनवर्टर से 12 16-बिट नमूने, बाएं और दाएं डेटा (ध्वनि) स्रोतों से 6 प्रत्येक) के इनपुट फ्रेम होते हैं। फ़्रेम $L_{1}R_{1}L_{2}R_{2}\ldots L_{6}R_{6}$ का प्रतिनिधित्व किया जा सकता है जहाँ $L_{i}$ और $R_{i}$ से बाएँ और दाएँ $i^{th}$ फ़्रेम का नमूना चैनल से बाइट्स हैं .

प्रारंभ में, बाइट्स को नए फ़्रेम बनाने के लिए क्रमपरिवर्तित किया जाता है $L_{1}L_{3}L_{5}R_{1}R_{3}R_{5}L_{2}L_{4}L_{6}R_{2}R_{4}R_{6}$ जहाँ $L_{i},R_{i}$प्रतिनिधित्व करना $i$-2 मध्यवर्ती फ़्रेमों के पश्चात फ़्रेम से बाएँ और दाएँ नमूने।

इसके पश्चात , इन 24 संदेश प्रतीकों को C2 (28,24,5) रीड-सोलोमन कोड का उपयोग करके एन्कोड किया गया है जो कि संक्षिप्त RS कोड $\mathbb {F} _{256}$ है . यह दो-त्रुटि-सुधार करने वाला है, न्यूनतम दूरी 5 का है। यह अतिरेक के 4 बाइट्स जोड़ता है, $P_{1}P_{2}$ नया फ्रेम बनाना: $L_{1}L_{3}L_{5}R_{1}R_{3}R_{5}P_{1}P_{2}L_{2}L_{4}L_{6}R_{2}R_{4}R_{6}$. परिणामी 28-प्रतीक कोडवर्ड को (28.4) क्रॉस इंटरलीवर के माध्यम से पारित किया जाता है, जिससे 28 इंटरलीव्ड प्रतीक बन जाते हैं। फिर इन्हें C1 (32,28,5) RS कोड से गुजारा जाता है, जिसके परिणामस्वरूप 32 कोडित आउटपुट प्रतीकों के कोडवर्ड प्राप्त होते हैं। किसी कोडवर्ड के विषम संख्या वाले प्रतीकों को अगले कोडवर्ड के सम संख्या वाले प्रतीकों के साथ फिर से समूहीकृत किया जाता है ताकि किसी भी छोटे बर्स्ट को तोड़ा जा सके जो उपरोक्त 4-फ्रेम विलंब इंटरलीविंग के पश्चात भी उपस्तिथ हो सकता है। इस प्रकार, प्रत्येक 24 इनपुट प्रतीकों के लिए 32 आउटपुट प्रतीक होंगे $R=24/32$. अंत में नियंत्रण और प्रदर्शन जानकारी की बाइट जोड़ी जाती है।33 बाइट्स में से प्रत्येक को ईएफएम (आठ से चौदह मॉड्यूलेशन) के माध्यम से 17 बिट्स में परिवर्तित किया जाता है और 3 मर्ज बिट्स को जोड़ा जाता है। इसलिए, छह नमूनों के फ्रेम का परिणाम 33 बाइट्स × 17 बिट्स (561 बिट्स) होता है, जिसमें 24 सिंक्रोनाइज़ेशन बिट्स और 3 मर्जिंग बिट्स जोड़े जाते हैं, जिससे कुल 588 बिट्स प्राप्त होते हैं।

डिकोडिंग: सीडी प्लेयर (सीआईआरसी डिकोडर) 32 आउटपुट सिंबल डेटा स्ट्रीम प्राप्त करता है। यह धारा पहले डिकोडर D1 से होकर गुजरती है। डिकोडिंग विधियों पर निर्णय लेना और अपने उत्पाद प्रदर्शन को अनुकूलित करना सीडी प्रणाली के व्यक्तिगत डिजाइनरों पर निर्भर है। न्यूनतम दूरी 5 होने के कारण D1, D2 डिकोडर प्रत्येक के संयोजन को सही कर सकते हैं $e$ त्रुटियाँ और $f$ ऐसे मिटाता है $2e+f<5$.अधिकांश डिकोडिंग समाधानों में, D1 को एकल त्रुटि को ठीक करने के लिए डिज़ाइन किया गया है। और 1 से अधिक त्रुटि के उपस्तिथियां में, यह डिकोडर 28 इरेज़र आउटपुट करता है। अगले चरण में डीइंटरलीवर इन विलोपनों को 28 डी2 कोडवर्ड में वितरित करता है। पुनः अधिकांश समाधानों में, D2 को केवल मिटाने से निपटने के लिए सेट किया गया है ( सरल और कम महंगा समाधान)। यदि 4 से अधिक विलोपन का सामना करना पड़ता है, तो 24 विलोपन D2 द्वारा आउटपुट होते हैं। इसके पश्चात , त्रुटि छुपाने वाली प्रणाली अचूक प्रतीकों के उपस्तिथियां में (पड़ोसी प्रतीकों से) प्रक्षेप करने का प्रयास करती है, जिसमें विफल रहने पर ऐसे गलत प्रतीकों के अनुरूप ध्वनियाँ म्यूट हो जाती हैं।

सीआईआरसी का प्रदर्शन:सीआईआरसी सरल रैखिक प्रक्षेप द्वारा लंबी बस्ट त्रुटियों को छुपाता है। 2.5 मिमी ट्रैक लंबाई (4000 बिट्स) अधिकतम पूरी तरह से सुधार योग्य बर्स्ट लंबाई है। 7.7 मिमी ट्रैक लंबाई (12,300 बिट्स) अधिकतम बर्स्ट लंबाई है जिसे इंटरपोल किया जा सकता है। बिट त्रुटि दर (बीईआर) पर नमूना प्रक्षेप दर हर 10 घंटे में होती है $=10^{-4}$ और बीईआर पर प्रति मिनट 1000 नमूने = $10^{-3}$ अज्ञात त्रुटि नमूने (क्लिक): बीईआर = पर हर 750 घंटे में से कम $10^{-3}$ और BER = पर नगण्य $10^{-4}$.

यह भी देखें

• त्रुटि का पता लगाना और सुधार करना
• प्रतिक्रिया के साथ त्रुटि-सुधार कोड
• कोड दर
• रीड-सोलोमन त्रुटि सुधार