Guruswami–Sudan list decoding algorithm
कोडिंग सिद्धांत में, सूची डिकोडिंग कई त्रुटियों की उपस्थिति में त्रुटि-सुधार कोड के अद्वितीय डिकोडिंग का एक विकल्प है। यदि किसी कोड की सापेक्ष दूरी है, तो सिद्धांत रूप में एक एन्कोडेड संदेश को पुनर्प्राप्त करना संभव है जब कोडवर्ड प्रतीकों के अंश तक दूषित हो जाते हैं। लेकिन जब त्रुटि दर उससे अधिक होगी, तो यह सामान्य रूप से संभव नहीं होगा। सूची डिकोडिंग डिकोडर को संदेशों की एक छोटी सूची आउटपुट करने की अनुमति देकर उस मुद्दे को पार करती है जो एन्कोड किए गए हो सकते हैं। सूची डिकोडिंग त्रुटियों के अंश से अधिक को ठीक कर सकती है। सूची डिकोडिंग के लिए कई बहुपद-समय एल्गोरिदम हैं। इस लेख में, हम सबसे पहले रीड-सोलोमन (आरएस) कोड के लिए एक एल्गोरिथ्म प्रस्तुत करते हैं जो त्रुटियों को ठीक करता है और मधु सूडान के कारण है। इसके बाद, हम बेहतर गुरुस्वामी-सुदान सूची डिकोडिंग एल्गोरिदम का वर्णन करते हैं, जो त्रुटियों को ठीक कर सकता है। यहाँ विभिन्न एल्गोरिदम के लिए दर आर और दूरी का एक प्लॉट है। https://wiki.cse.buffalo.edu/cse545/sites/wiki.cse.buffalo.edu.cse545/files/81/Graph.jpg एल्गोरिदम 1 (सूडान की सूची डिकोडिंग एल्गोरिदम) समस्या कथन इनपुटः एक क्षेत्र; तत्वों के अलग-अलग जोड़े; और पूर्णांक और। आउटपुटः सभी संतुष्ट करने वाले कार्यों की एक सूची अधिक से अधिक डिग्री में एक बहुपद है सूडान के एल्गोरिदम को बेहतर ढंग से समझने के लिए, कोई पहले एक और एल्गोरिदम को जानना चाहेगा जिसे आरएस कोड की सूची डिकोडिंग के लिए एल्गोरिदम का पहला संस्करण या मौलिक संस्करण माना जा सकता है-बर्लेकैम्प-वेल्च एल्गोरिदम। वेल्च और बर्लेकैम्प शुरू में एक एल्गोरिथ्म के साथ आए थे जो सबसे अच्छी सीमा के साथ बहुपद समय में समस्या का समाधान कर सकता है। सूडान के एल्गोरिदम का तंत्र लगभग बर्लेकैम्प-वेल्च एल्गोरिदम के एल्गोरिदम के समान है, चरण 1 को छोड़कर, कोई भी सीमित डिग्री के द्विभिन्न बहुपद की गणना करना चाहता है। रीड-सोलोमन कोड के लिए सूडान की सूची डिकोडिंग एल्गोरिथ्म जो बर्लेकैम्प और वेल्च एल्गोरिथ्म पर एक सुधार है, के साथ समस्या का समाधान कर सकता है। यह बाउंड अद्वितीय डिकोडिंग बाउंड से बेहतर है। एल्गोरिदम परिभाषा 1 (भारित डिग्री) भार के लिए, एकांक की भारित डिग्री है। एक बहुपद की भारित डिग्री, गैर-शून्य गुणांक वाले एकाक्षरों पर, एकाक्षर की भारित डिग्री की अधिकतम होती है। उदाहरण के लिए,-डिग्री 7 एल्गोरिथम हैः इनपुटः; {}/* पैरामीटर l, m बाद में सेट किया जाना है। */चरण 1: प्रत्येक के लिए एक गैर-शून्य द्विभिन्न बहुपद संतोषजनक भारित डिग्री का पता लगाएं। अपरिवर्तनीय कारकों में कारक क्यू। चरण 3. सभी बहुपदों को आउटपुट करें जैसे कि क्यू का एक कारक है और विश्लेषण के कम से कम टी मानों के लिए एक को यह साबित करना होगा कि उपरोक्त एल्गोरिथ्म बहुपद समय में चलता है और सही परिणाम देता है। यह निम्नलिखित दावों को साबित करके किया जा सकता है। दावा 1: यदि कोई संतोषजनक फलन (2) मौजूद है, तो कोई इसे बहुपद समय में पा सकता है। प्रमाणः ध्यान दें कि अधिक से अधिक भारित डिग्री के द्विभिन्न बहुपद को विशिष्ट रूप से लिखा जा सकता है। फिर प्रत्येक के लिए बाधाओं को संतुष्ट करने वाले गुणांकों को खोजना होगा। यह अज्ञात {} में समीकरणों का एक रैखिक समूह है। बहुपद समय में गौसी उन्मूलन का उपयोग करके कोई भी समाधान खोज सकता है। दावा 2: यदि कोई संतोषजनक कार्य मौजूद है (2) प्रमाणः यह सुनिश्चित करने के लिए कि एक गैर-शून्य समाधान मौजूद है, तो गुणांक की संख्या बाधाओं की संख्या से अधिक होनी चाहिए। मान लीजिए कि इन की अधिकतम डिग्री m है और इन की अधिकतम डिग्री है। तब की डिग्री अधिक से अधिक होगी। यह देखना होगा कि रैखिक प्रणाली सजातीय है। सेटिंग सभी रैखिक बाधाओं को संतुष्ट करती है। हालाँकि यह (2) को संतुष्ट नहीं करता है, क्योंकि समाधान समान रूप से शून्य हो सकता है। यह सुनिश्चित करने के लिए कि एक गैर-शून्य समाधान मौजूद है, किसी को यह सुनिश्चित करना होगा कि रैखिक प्रणाली में अज्ञात की संख्या होनी चाहिए, ताकि किसी के पास गैर-शून्य हो सके। चूँकि यह मान n से अधिक है, इसलिए बाधाओं की तुलना में अधिक चर हैं और इसलिए एक गैर-शून्य समाधान मौजूद है। दावा 3: यदि एक कार्य संतोषजनक है (2) और कार्य संतोषजनक है (1) और, तो प्रमाण को विभाजित करता हैः एक कार्य पर विचार करें। यह एक बहुपद है, और तर्क देता है कि इसमें अधिकतम डिग्री है। के किसी भी एकाधिकार पर विचार करें। चूंकि अधिक से अधिक भारित डिग्री है, इसलिए ऐसा कहा जा सकता है। इस प्रकार यह शब्द अधिकतम डिग्री में एक बहुपद है। इस प्रकार अधिकतम डिग्री होती है अगला तर्क है कि समान रूप से शून्य है। चूँकि शून्य है जब भी, कोई कह सकता है कि सख्ती से अधिक अंकों के लिए शून्य है। इस प्रकार इसकी डिग्री की तुलना में अधिक शून्य हैं और इसलिए समान रूप से शून्य है, जिसका अर्थ है और के लिए इष्टतम मान खोजना। ध्यान दें कि और किसी दिए गए मान के लिए, कोई भी सबसे छोटे की गणना कर सकता है जिसके लिए दूसरी शर्त होती है दूसरी शर्त को आपस में बदलने से कोई भी इस मान को पहली स्थिति में प्रतिस्थापित कर सकता है। समीकरण का व्युत्पन्न लेकर और उसे शून्य के बराबर करके ऐसा किया जा सकता है ऐसा करने से किसी को मान वापस मिल जाएगा और किसी को एल्गोरिथम 2 मिल जाएगा (गुरुस्वामी-सुदान सूची डिकोडिंग एल्गोरिथ्म) परिभाषा मूल्यांकन सेट और एक सकारात्मक पूर्णांक के साथ सीमित क्षेत्र पर एक रीड-सोलोमन कोड पर विचार करें, गुरुस्वामी-सुदान सूची डिकोडर एक वेक्टर को इनपुट के रूप में स्वीकार करता है, और डिग्री के बहुपदों की एक सूची आउटपुट करता है जो कोडवर्ड्स के साथ 1 से 1 पत्राचार में हैं। विचार द्वि-भिन्न बहुपद पर अधिक प्रतिबंध जोड़ना है जिसके परिणामस्वरूप जड़ों की संख्या के साथ बाधाओं में वृद्धि होती है। गुणन एक द्वि-चर बहुपद में ऐसे साधनों पर गुणन का शून्य होता है जिसमें डिग्री का कोई पद नहीं होता है, जहां x-डिग्री को किसी भी x पद की अधिकतम डिग्री के रूप में परिभाषित किया जाता है। https://wiki.cse.buffalo.edu/cse545/sites/wiki.cse.buffalo.edu.cse545/files/76/Fig1.jpg इसलिए, (0,0) पर गुणन 1 का शून्य है। जाने दीजिए। https://wiki.cse.buffalo.edu/cse545/sites/wiki.cse.buffalo.edu.cse545/files/76/Fig2.jpg इसलिए, (0,0) पर गुणन 1 का शून्य है। माना https://wiki.cse.buffalo.edu/cse545/sites/wiki.cse.buffalo.edu.cse545/files/76/Fig3.jpg इसलिए, (0,0) पर गुणन 2 का शून्य है। इसी तरह, यदि तब, गुणन 2 का शून्य है। बहुलता की सामान्य परिभाषा की जड़ें हैं यदि कब बहुलता का शून्य है। एल्गोरिदम संचरित कूटशब्द को संचरित कूटशब्द का समर्थन समूह और प्राप्त शब्द होना चाहिए एल्गोरिदम इस प्रकार हैः एक प्राप्त सदिश के लिए, एक गैर-शून्य द्वि-चर बहुपद का निर्माण करें जिसमें अधिक से अधिक भारित डिग्री हो जिसमें प्रत्येक बिंदु पर बहुलता का शून्य हो जहां फैक्टराइजेशन चरण रूप के सभी कारकों को ढूंढें और कम से कम कहाँ और कहाँ डिग्री का बहुपद है के मूल्यों के लिए याद रखें कि डिग्री के बहुपद कूटशब्द के साथ 1 से 1 पत्राचार में हैं। इसलिए, यह चरण कूटशब्दों की सूची तैयार करता है। विश्लेषण इंटरपोलेशन चरण लेम्माः इंटरपोलेशन चरण का तात्पर्य लेट व्हाट एंड देन के गुणांकों पर बाधाओं को दर्शाता है. (समीकरण 1) जहां समीकरण 1 का प्रमाणः. लेम्मा का द्विपद विस्तार प्रमाण का उपयोग करनाः बहुपद में यदि ऐसा हो तो गुणन का शून्य होता है जो मानों को इस प्रकार ले सकता है। इस प्रकार, बाधाओं की कुल संख्या है इस प्रकार, चयनों की संख्या फैक्टराइजेशन चरण प्रस्ताव के गुणांकों के लिए की जा सकती है और प्रत्येक चयन का तात्पर्य फैक्टराइजेशन चरण प्रस्ताव के गुणांकों पर बाधाओं को दर्शाता हैः यदि प्रमाण का एक कारक हैः चूंकि, एक कारक है, तो इसे इस रूप में दर्शाया जा सकता है कि क्या भागफल प्राप्त होता है जब इसे शेष भाग से विभाजित किया जाता है। जैसा कि ऊपर साबित किया गया है, जहां एल. एच. एस. गुणांकों की संख्या पर ऊपरी सीमा है और आर. एच. एस. पहले सिद्ध लेम्मा है। इसलिए, प्रतिस्थापित करें, इसलिए साबित किया कि गुरुस्वामी-सुदान सूची डिकोडिंग एल्गोरिदम त्रुटियों तक डिकोड रीड-सोलोमन कोड को सूचीबद्ध कर सकता है। संदर्भ https://web.archive.org/web/20100702120650/http:// सी. एस. ई. बफेलो. ई. डी. यू./~ एट्री/पाठ्यक्रम/कोडिंग-सिद्धांत/https://www.cs.cmu.edu ~ वेंकटग/पब/पेपर/लिस्टकोडिंग-NOW.pdf http://www.mendeley.com/research/algebraic-softdecision-decoding-reedsolomon-codes आर. जे. मैकलेइस। रीड-सोलोमन कोड के लिए गुरुस्वामी-सुदान डिकोडिंग एल्गोरिदम। एम. सूडान। रीड सोलोमन कोड की डिकोडिंग त्रुटि-सुधार सीमा से परे है। कोडिंग सिद्धांत