Folded Reed–Solomon code
कोडिंग सिद्धांत में, मुड़े हुए रीड-सोलोमन कोड रीड-सोलोमन कोड की तरह होते हैं, जो कोडवर्ड प्रतीकों को सावधानीपूर्वक जोड़कर एक बड़ी वर्णमाला पर रीड-सोलोमन कोडवर्ड का मानचित्रण करके प्राप्त किए जाते हैं। फोल्डेड रीड-सोलोमन कोड भी परवारेश-वार्डी कोड का एक विशेष मामला है। इष्टतम मापदंडों का उपयोग करके कोई भी आर की दर के साथ डिकोड कर सकता है, और 1-आर की डिकोडिंग त्रिज्या प्राप्त कर सकता है। "फोल्डेड रीड-सोलोमन कोड" शब्द वी. वाई. द्वारा एक पेपर में गढ़ा गया था। क्राचकोव्स्की एक एल्गोरिथ्म के साथ जिसने कई यादृच्छिक "चरणबद्ध विस्फोट" त्रुटियों के साथ रीड-सोलोमन कोड प्रस्तुत किए। फोल्ड किए गए आरएस कोड के लिए सूची-डिकोडिंग एल्गोरिथ्म ऐसी चरणबद्ध विस्फोट त्रुटियों के लिए गुरुस्वामी-सुदान एल्गोरिथ्म द्वारा प्राप्त रीड-सोलोमन कोड के लिए सीमा से परे सुधार करता है। इतिहास कोडिंग सिद्धांत में चल रही चुनौतियों में से एक त्रुटि सुधार कोड (कोडिंग) दर और त्रुटि-सुधार त्रिज्या के बीच एक इष्टतम व्यापार-बंद प्राप्त करना है। हालांकि इसे व्यावहारिक रूप से प्राप्त करना संभव नहीं हो सकता है (शोर चैनल कोडिंग सिद्धांत के मुद्दों के कारण), सैद्धांतिक रूप से अर्ध इष्टतम व्यापार प्राप्त किया जा सकता है। फोल्डेड रीड-सोलोमन कोड तैयार किए जाने से पहले, सभी दरों के लिए रीड-सोलोमन कोड द्वारा सबसे अच्छा त्रुटि-सुधार त्रिज्या प्राप्त किया गया था। इस सीमा पर एक सुधार परवारेश और वार्डी द्वारा दरों के लिए प्राप्त किया गया था क्योंकि परवारेश-वार्डी एल्गोरिदम त्रुटियों के एक अंश को डिकोड कर सकता है। फोल्डेड रीड-सोलोमन कोड इन पिछले निर्माणों में सुधार करते हैं, और किसी भी स्थिरांक के लिए त्रुटियों के एक अंश के लिए बहुपद समय में डिकोड किए जा सकते हैं। परिभाषा लंबाई और आयाम के एक रीड-सोलोमन कोड और एक तह पैरामीटर पर विचार करें। मान लीजिए कि यह विभाजित होता है। रीड-सोलोमन कोड के लिए मानचित्रण इस तरहः जहाँ एक आदिम तत्व है। रीड सोलोमन कोड का मुड़ा हुआ संस्करण, जिसे दर्शाया गया है, ब्लॉक की लंबाई का एक कोड है। आरएस कोडवर्ड्स के लगातार प्रतीकों के साथ सिर्फ रीड सोलोमन कोड हैं जिन्हें एक साथ समूहीकृत किया गया है। ग्राफिक विवरण उपरोक्त परिभाषा को आरेख के माध्यम से अधिक स्पष्ट किया गया है, जहाँ तह पैरामीटर है। संदेश को इसके द्वारा दर्शाया जाता है, जिसे जब रीड-सोलोमन एन्कोडिंग का उपयोग करके एन्कोड किया जाता है, तो इसमें एट, व्हाट के मान होते हैं। फिर वर्णमाला पर लंबाई का एक कूटशब्द देने के लिए 3 तत्वों के समूहों में बंडलिंग की जाती है। यहाँ ध्यान देने वाली बात यह है कि प्रदर्शित फोल्डिंग ऑपरेशन मूल रीड-सोलोमन कोड की दर को नहीं बदलता है। इसे साबित करने के लिए, लंबाई, आयाम और दूरी के एक रैखिक कोड पर विचार करें। फोल्डिंग ऑपरेशन इसे एक कोड बना देगा। इससे दर वही रहेगी। फोल्डेड रीड-सोलोमन कोड और सिंगलटन बाउंड सिंगलटन बाउंड के एसिम्प्टोटिक संस्करण के अनुसार, यह ज्ञात है कि एक कोड की सापेक्ष दूरी को संतुष्ट करना चाहिए कि कोड की दर कहाँ है। जैसा कि पहले साबित किया गया है, चूंकि दर बनाए रखी जाती है, सापेक्ष दूरी भी सिंगलटन सीमा से मिलती है। मोड़ने से क्यों मदद मिल सकती है? फोल्डेड रीड-सोलोमन कोड मूल रूप से रीड सोलोमन कोड के समान हैं, जिन्हें सिर्फ एक बड़ी वर्णमाला पर देखा जाता है। यह दिखाने के लिए कि यह कैसे मदद कर सकता है, एक मुड़े हुए रीड-सोलोमन कोड पर विचार करें। एक रीड-सोलोमन कोड को डिकोड करना और त्रुटियों के समान अंश के लिए फोल्ड किए गए रीड-सोलोमन कोड लगभग समान कम्प्यूटेशनल तीव्रता के कार्य हैंः कोई भी फोल्ड किए गए रीड-सोलोमन कोड के प्राप्त शब्द को उजागर कर सकता है, इसे मूल रीड-सोलोमन कोड के प्राप्त शब्द के रूप में मान सकता है, और उस पर रीड-सोलोमन सूची डिकोडिंग एल्गोरिदम चला सकता है। जाहिर है, इस सूची में प्राप्त शब्द की दूरी के भीतर सभी मुड़े हुए रीड-सोलोमन कूटशब्द होंगे, साथ ही कुछ अतिरिक्त शब्द भी होंगे, जिन्हें हम हटा सकते हैं। इसके अलावा, एक मुड़े हुए रीड-सोलोमन कोड को डिकोड करना एक आसान काम है। मान लीजिए कि हम एक तिहाई त्रुटियों को ठीक करना चाहते हैं। चुने गए डिकोडिंग एल्गोरिदम को एक त्रुटि पैटर्न को सही करना चाहिए जो रीड-सोलोमन एन्कोडिंग में हर तीसरे प्रतीक को सही करता है। लेकिन मोड़ने के बाद, यह त्रुटि पैटर्न सभी प्रतीकों को दूषित कर देगा और त्रुटि सुधार की आवश्यकता को समाप्त कर देगा। त्रुटियों के इस प्रसार को चित्रमय विवरण में नीले रंग से इंगित किया गया है। यह साबित करता है कि त्रुटियों के एक निश्चित अंश के लिए तह संचालन त्रुटियों को वितरित करने के लिए चैनल के लचीलेपन को कम कर देता है, जिससे बदले में त्रुटि पैटर्न की संख्या में कमी आती है जिन्हें ठीक करने की आवश्यकता होती है। हम फोल्डेड रीड सोलोमन कोड को परवारेश वार्डी कोड के साथ जोड़ सकते हैं जो डिग्री के बहुपद को बहुपदों के साथ कूटबद्ध करता है जहां एक अपरिवर्तनीय बहुपद है। इरेड्यूसिबल पोलीनोमिअल और पैरामीटर का चयन करते समय हमें यह जांचना चाहिए कि क्या डिग्री का प्रत्येक पोलीनोमिअल अधिक से अधिक संतुष्ट करता है क्योंकि यह केवल स्थानांतरित समकक्ष है जहां आदिम तत्व है। यदि हम मूल्यांकन बिंदुओं के सेट के लिए मुड़े हुए आर. एस. कोड की तुलना क्रम 2 के पी. वी. कोड से करते हैं तो हम देख सकते हैं कि के पी. वी. एन्कोडिंग में, प्रत्येक के लिए और पर दिखाई देता है, मुड़े हुए एफ. आर. एस. एन्कोडिंग के विपरीत जिसमें यह केवल एक बार दिखाई देता है। इस प्रकार, पी. वी. और मुड़े हुए आर. एस. कोड में समान जानकारी होती है लेकिन केवल एफ. आर. एस. की दर एक कारक से बड़ी होती है और इसलिए केवल पी. वी. कोड की सूची डिकोडेबिलिटी का उपयोग करके मुड़े हुए आर. एस. कोड के लिए सूची डिकोडिंग त्रिज्या व्यापार-बंद बेहतर है। एफ. आर. एस. कोड को इस तरह से चुनने में लाभ है कि वे संबंधित पी. वी. कोड की तुलना में बेहतर दर के साथ समान त्रुटि सुधार प्रदर्शन के साथ उपयुक्त पी. वी. कोड के संपीड़ित रूप हैं। इस विचार का उपयोग दर के एक मुड़े हुए आरएस कोड का निर्माण करने के लिए किया जा सकता है जो लगभग त्रिज्या तक सूची डिकोडेबल हैं। सूची-डिकोडिंग फोल्डेड रीड-सोलोमन कोड का संक्षिप्त अवलोकन गुरुस्वामी द्वारा प्रस्तुत एक सूची डिकोडिंग एल्गोरिदम जो त्रिज्या तक एफ. आर. एस. कोड को डिकोड करने के लिए द्विघात समय में चलता है। एल्गोरिथम में अनिवार्य रूप से तीन चरण होते हैं, अर्थात् अंतर्वेशन चरण जिसमें वेल्च बर्लेकैम्प शैली अंतर्वेशन का उपयोग गैर-शून्य बहुपद को अंतर्वेशन करने के लिए किया जाता है, जिसके बाद अंतर्वेशन में प्राप्त समीकरण को संतुष्ट करने वाले डिग्री वाले सभी बहुपद पाए जाते हैं। तीसरे चरण में पास के कूटशब्दों की वास्तविक सूची को समाधान उपक्षेत्र की छंटाई से जाना जाता है जिसमें समय लगता है। रैखिक-बीजगणितीय सूची डिकोडिंग एल्गोरिथ्म गुरुस्वामी रैखिक-बीजगणित पर आधारित एक समय सूची डिकोडिंग एल्गोरिथ्म प्रस्तुत करते हैं, जो रीड-सोलोमन कोड को त्रिज्या तक की सूची-आकार के साथ डिकोड कर सकता है। इस एल्गोरिथ्म में तीन चरण हैंः इंटरपोलेशन चरण, रूट फाइंडिंग चरण और प्रून चरण। इंटरपोलेशन चरण में यह एक रैखिक प्रणाली को हल करके उम्मीदवार संदेश बहुपद को खोजने का प्रयास करेगा। रूट फाइंडिंग चरण में, यह एक अन्य रैखिक प्रणाली को हल करके समाधान सबस्पेस खोजने का प्रयास करेगा। अंतिम चरण दूसरे चरण में प्राप्त समाधान उपक्षेत्र की छंटाई करने का प्रयास करेगा। हम निम्नलिखित में विवरण में प्रत्येक चरण का परिचय देंगे। चरण 1: अंतर्वेशन चरण यह एक वेल्च-बर्लेकैम्प-शैली अंतर्वेशन है (क्योंकि इसे वेल्च-बर्लेकैम्प एल्गोरिथ्म के उच्च-आयामी सामान्यीकरण के रूप में देखा जा सकता है)। मान लीजिए कि हमें-फोल्ड किए गए रीड-सोलोमन कोड का एक कूटशब्द प्राप्त हुआ है जैसा कि नीचे दिखाया गया है हम सावधानीपूर्वक चुने गए डिग्री पैरामीटर का उपयोग करके गैर-शून्य बहुपद को प्रक्षेपित करते हैं। तो अंतर्वेशन की आवश्यकताएँ होंगी तब मोनोमियल्स की संख्या है क्योंकि इसमें मोनोमियल्स की संख्या अंतर्वेशन स्थितियों की संख्या से अधिक है। हमारे पास नीचे लेम्मा 1 है. उपरोक्त अंतर्वेशन स्थिति को संतुष्ट करने के लिए अधिकांश बाधाओं और चर के साथ एक सजातीय रैखिक प्रणाली को हल करके पाया जा सकता है। इसके अलावा इस अंतर्वेशन को संचालन में किया जा सकता है। यह सूत्र हमें दिखाता है कि अंतर्वेशन चरण निकट-रैखिक समय में किया जा सकता है। अभी के लिए, हमने बहुभिन्नरूपी बहुपद के लिए आवश्यक हर चीज के बारे में बात की है। शेष कार्य संदेश बहुपदों पर ध्यान केंद्रित करना है। लेम्मा 2. यदि एक उम्मीदवार संदेश बहुपद अधिक से अधिक डिग्री का एक बहुपद है जिसका फोल्डेड रीड-सोलोमन एन्कोडिंग कम से कम कॉलम में प्राप्त शब्द से सहमत है तो यहाँ "सहमत" का अर्थ है कि एक कॉलम में सभी मान कोडवर्ड में संबंधित मूल्यों से मेल खाना चाहिए। यह लेम्मा हमें दिखाता है कि ऐसी कोई भी बहुपद एक बीजगणितीय स्थिति प्रस्तुत करती है जो उन संदेश बहुपदों के लिए संतुष्ट होनी चाहिए जिन्हें हम सूची डिकोडिंग में रुचि रखते हैं। आगे हम डिकोडिंग बाध्य प्राप्त कर सकते हैं हम देखते हैं कि भिन्नात्मक समझौता चरण 2 हैः मूल-खोज चरण इस चरण के दौरान, हमारा कार्य इस बात पर ध्यान केंद्रित करता है कि कैसे सभी बहुपदों को डिग्री से अधिक नहीं खोजना है और चरण 1 से हमें मिलने वाले समीकरण को संतुष्ट करना है, अर्थात् चूंकि उपरोक्त समीकरण बहुपद के गुणांक में एक रैखिक प्रणाली समीकरण बनाता है, उपरोक्त समीकरण का समाधान एक उपक्षेत्र है। यह तथ्य वह प्रमुख बिंदु है जो एक कुशल एल्गोरिथ्म को जन्म देता है-हम रैखिक प्रणाली को हल कर सकते हैं। यह पूछना स्वाभाविक है कि समाधान का आयाम कितना बड़ा है? क्या आयाम पर कोई ऊपरी सीमा है? एक कुशल सूची डिकोडिंग एल्गोरिथ्म के निर्माण में एक ऊपरी सीमा होना बहुत महत्वपूर्ण है क्योंकि कोई भी किसी भी डिकोडिंग समस्या के लिए सभी कूटशब्दों को आसानी से आउटपुट कर सकता है। वास्तव में इसकी वास्तव में एक ऊपरी सीमा है जैसा कि नीचे लीम्मा का तर्क है। लेम्मा 3. यदि का क्रम कम से कम है (विशेष रूप से जब आदिम है), तो समाधान का आयाम अधिक से अधिक है। यह लेम्मा हमें समाधान स्थान के लिए आयाम की ऊपरी सीमा दिखाता है। अंत में, उपरोक्त विश्लेषण के आधार पर, हमारे पास नीचे प्रमेय प्रमेय 1 है। ब्लॉक लंबाई के मुड़े हुए रीड-सोलोमन कोड के लिए और सभी पूर्णांकों के लिए निम्नलिखित मान निर्धारित करें। एक प्राप्त शब्द को देखते हुए, समय के साथ, कोई भी अधिक से अधिक आयाम के एक उपक्षेत्र के लिए एक आधार पा सकता है जिसमें डिग्री से कम के सभी संदेश बहुपद होते हैं जिनकी एफआरएस एन्कोडिंग कूटशब्द स्थितियों के अधिकतम एक अंश से भिन्न होती है। जब, हम देखते हैं कि यह त्रुटियों के एक अंश के साथ एक अद्वितीय डिकोडिंग एल्गोरिदम तक कम हो जाता है। दूसरे शब्दों में, हम अद्वितीय डिकोडिंग एल्गोरिदम को सूची डिकोडिंग एल्गोरिदम की एक विशेषता के रूप में मान सकते हैं। मात्रा उन पैरामीटर विकल्पों के लिए है जो एक सूची डिकोडिंग त्रिज्या प्राप्त करते हैं। प्रमेय 1 हमें बताता है कि त्रुटि त्रिज्या कितनी बड़ी होगी। अब हम अंत में समाधान सबस्पेस प्राप्त करते हैं। लेकिन एक समस्या अभी भी बनी हुई है। सबसे खराब स्थिति में सूची का आकार है। लेकिन करीबी कूटशब्दों की वास्तविक सूची उस उपक्षेत्र के भीतर केवल एक छोटा समूह है। इसलिए हमें इसे कम करने के लिए उपक्षेत्र को काटने के लिए कुछ प्रक्रिया की आवश्यकता है। इस प्रून प्रक्रिया में सबसे खराब स्थिति में समय लगता है। दुर्भाग्य से यह ज्ञात नहीं है कि चलने के समय में सुधार कैसे किया जाए क्योंकि हम नहीं जानते कि फोल्ड किए गए रीड-सोलोमन कोड के लिए सूची के आकार की सीमा में सुधार कैसे किया जाए। चीजें बेहतर हो जाती हैं यदि हम संदेश के रूप में सभी संभावित डिग्री बहुपदों के सबसेट को सावधानीपूर्वक चुनकर कोड को बदलते हैं, तो सूची का आकार बहुत छोटा दिखाई देता है जबकि दर में थोड़ा सा नुकसान होता है। हम अगले चरण में इसके बारे में संक्षेप में बात करेंगे। चरण 3: छँटाई चरण एक मुड़े हुए रीड-सोलोमन कोड को डिकोड करने की समस्या को दो रैखिक प्रणालियों में परिवर्तित करके, एक रैखिक प्रणाली जिसका उपयोग अंतर्वेशन चरण के लिए किया जाता है और दूसरा रैखिक प्रणाली उम्मीदवार समाधान उपक्षेत्र खोजने के लिए, डिकोडिंग समस्या की जटिलता को सफलतापूर्वक घटाकर द्विघात कर दिया जाता है। हालाँकि, सबसे खराब स्थिति में, आउटपुट के सूची आकार की सीमा बहुत खराब है। चरण 2 में यह उल्लेख किया गया था कि यदि कोई संदेश के रूप में सभी संभावित डिग्री बहुपदों के केवल एक उपसमुच्चय को सावधानीपूर्वक चुनता है, तो सूची के आकार को बहुत कम किया जा सकता है। यहाँ हम अपनी चर्चा का विस्तार करेंगे। इस लक्ष्य को प्राप्त करने के लिए, विचार गुणांक सदिश को एक विशेष उपसमुच्चय तक सीमित करना है, जो नीचे दी गई दो शर्तों को पूरा करता हैः शर्त 1। सेट काफी बड़ा होना चाहिए ()। यह सुनिश्चित करने के लिए है कि दर को कारक के आधार पर कम किया जाएगा। शर्त 2. सेट में संतोषजनक आयाम के किसी भी उपक्षेत्र के साथ निम्न प्रतिच्छेदन होना चाहिए और इस तरह के उपसमुच्चय को उपक्षेत्र-अपवर्तक उपसमुच्चय कहा जाता है। सबसे खराब स्थिति में सूची के आकार के लिए सीमा है, और इसे सबस्पेस-इवेसिव सबसेट का उपयोग करके एक सापेक्ष छोटी सीमा तक कम किया जा सकता है। इस चरण के दौरान, क्योंकि इसे समाधान उपक्षेत्र के प्रत्येक तत्व की जांच करनी होती है जो हमें चरण 2 से मिलता है, इसमें सबसे खराब स्थिति में समय लगता है (समाधान उपक्षेत्र का आयाम है)। डीवीर और लोवेट ने गुरुस्वामी के काम के आधार पर परिणाम में सुधार किया, जो सूची के आकार को स्थिर कर सकता है। यहाँ केवल उस विचार को प्रस्तुत किया गया है जिसका उपयोग समाधान उपक्षेत्र को काटने के लिए किया जाता है। छंटाई प्रक्रिया के विवरण के लिए, कृपया गुरुस्वामी, डीवीर और लोवेट के कागजात देखें, जो संदर्भ में सूचीबद्ध हैं। सारांश यदि हम चरण 3 पर विचार नहीं करते हैं, तो यह एल्गोरिथ्म द्विघात समय में चल सकता है। इस एल्गोरिथ्म का सारांश नीचे दिया गया है। यह भी देखें रीड-सोलोमन त्रुटि सुधार सिंगलटन बाउंड कोडिंग सिद्धांत सूची डिकोडिंग संदर्भ अत्रि रुद्र के व्याख्यान नोट्सः फोल्डेड रीड-सोलोमन कोड अत्रि रुद्र के व्याख्यान नोट्सः बाउंड्स वेंकटेशन गुरुस्वामी के व्याख्यान नोट्सः कोड पर प्राथमिक सीमाएं वेंकटेशन गुरुस्वामी के व्याख्यान नोट्सः सूची डिकोडिंग फोल्डेड रीड-सोलोमन कोड कोडिंग सिद्धांत त्रुटि का पता लगाने और सुधार कम्प्यूटेशनल जटिलता सिद्धांत