लुबी रूपांतरण कोड

कंप्यूटर विज्ञान में, लुबी ट्रांसफॉर्म कोड (एलटी कोड) व्यावहारिक फाउंटेन कोड की पहली श्रेणी हैं जो निकट-इष्टतम विलोपन सुधार कोड हैं। उनका आविष्कार 1998 में माइकल लुबी द्वारा किया गया था और 2002 में प्रकाशित किया गया था।^[1] कुछ अन्य फव्वारा कोडों की तरह, एलटी कोड विरल द्विदलीय रेखांकन पर निर्भर करते हैं ताकि एन्कोडिंग और डिकोडिंग गति के लिए रिसेप्शन ओवरहेड का व्यापार किया जा सके। एलटी कोड की विशिष्ट विशेषता अनन्य या ऑपरेशन के आधार पर विशेष रूप से सरल एल्गोरिदम को नियोजित करने में है ( $\oplus$ ) संदेश को एनकोड और डिकोड करने के लिए।^[2] एलटी कोड रेटलेस हैं क्योंकि एन्कोडिंग एल्गोरिथ्म सिद्धांत रूप में संदेश पैकेटों की एक अनंत संख्या का उत्पादन कर सकता है (यानी, संदेश को डिकोड करने के लिए प्राप्त होने वाले पैकेटों का प्रतिशत मनमाने ढंग से छोटा हो सकता है)। वे इरेज़र करेक्टिंग कोड हैं क्योंकि उनका उपयोग बाइनरी इरेज़र चैनल पर डिजिटल डेटा को मज़बूती से प्रसारित करने के लिए किया जा सकता है।

एलटी कोड से परे अगली पीढ़ी रैप्टर कोड हैं (उदाहरण के लिए आईईटीएफ आरएफसी 5053 या आईईटीएफ आरएफसी 6330 देखें), जिसमें रैखिक समय एन्कोडिंग और डिकोडिंग है। रैप्टर कोड मौलिक रूप से एलटी कोड पर आधारित होते हैं, यानी रैप्टर कोड के लिए एन्कोडिंग दो एन्कोडिंग चरणों का उपयोग करता है, जहां दूसरा चरण एलटी एन्कोडिंग है। इसी तरह, रैप्टर कोड के साथ डिकोडिंग मुख्य रूप से एलटी डिकोडिंग पर निर्भर करती है, लेकिन एलटी डिकोडिंग अधिक उन्नत डिकोडिंग तकनीकों के साथ मिश्रित होती है। IETF RFC 6330 में निर्दिष्ट रैप्टरक्यू कोड, जो सबसे उन्नत फाउंटेन कोड है, में केवल एलटी कोड का उपयोग करने की तुलना में बेहतर डिकोडिंग संभावनाएं और प्रदर्शन हैं।

एलटी कोड का उपयोग क्यों करें?

एक इरेज़र चैनल में डेटा स्थानांतरित करने की पारंपरिक योजना निरंतर दो-तरफ़ा संचार पर निर्भर करती है।

प्रेषक सूचना का एक पैकेट एन्कोड करता है और भेजता है।
रिसीवर प्राप्त पैकेट को डीकोड करने का प्रयास करता है। यदि इसे डिकोड किया जा सकता है, तो रिसीवर ट्रांसमीटर को एक पावती वापस भेजता है। अन्यथा, रिसीवर ट्रांसमीटर को फिर से पैकेट भेजने के लिए कहता है।
यह दो-तरफ़ा प्रक्रिया तब तक जारी रहती है जब तक संदेश में सभी पैकेट सफलतापूर्वक स्थानांतरित नहीं हो जाते।

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

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

जैसा कि ऊपर उल्लेख किया गया है, IETF RFC 6330 में निर्दिष्ट रैप्टरक्यू कोड व्यवहार में एक एलटी कोड से बेहतर प्रदर्शन करता है।

एलटी एन्कोडिंग

एन्कोडिंग प्रक्रिया अनकोडेड संदेश को लगभग समान लंबाई के n ब्लॉकों में विभाजित करके शुरू होती है। एन्कोडेड पैकेट तब छद्म यादृच्छिक संख्या जेनरेटर की सहायता से उत्पादित किए जाते हैं।

डिग्री d, 1 ≤ d ≤ n, अगले पैकेट का यादृच्छिक रूप से चुना जाता है।
सटीक d संदेश से ब्लॉक बेतरतीब ढंग से चुने गए हैं।
यदि एम_i संदेश का iवां ब्लॉक है, अगले पैकेट के डेटा भाग की गणना इस प्रकार की जाती है

M_{i_{1}}\oplus M_{i_{2}}\oplus \cdots \oplus M_{i_{d}}\,

जहां मैं₁, मैं₂, …, मैं_d} इस पैकेट में शामिल d ब्लॉकों के लिए बेतरतीब ढंग से चुने गए सूचकांक हैं।

एन्कोडेड पैकेट में एक उपसर्ग जोड़ा जाता है, यह परिभाषित करता है कि संदेश में कितने ब्लॉक n हैं, कितने ब्लॉक d को इस पैकेट के डेटा भाग में अनन्य-ओर्ड किया गया है, और सूचकांकों की सूची {i₁, मैं₂, …, मैं_d}.
अंत में, त्रुटि का पता लगाने वाले कोड का कुछ रूप (शायद चक्रीय अतिरेक जाँच के रूप में सरल) पैकेट पर लागू होता है, और पैकेट प्रेषित होता है।

यह प्रक्रिया तब तक जारी रहती है जब तक कि रिसीवर संकेत नहीं देता कि संदेश प्राप्त हो गया है और सफलतापूर्वक डिकोड हो गया है।

एलटी डिकोडिंग

डिकोडिंग प्रक्रिया एन्कोडेड संदेश को पुनः प्राप्त करने के लिए अनन्य या ऑपरेशन का उपयोग करती है।

यदि वर्तमान पैकेट साफ़ नहीं है, या यदि यह पहले से संसाधित किए जा चुके पैकेट की प्रतिकृति बनाता है, तो वर्तमान पैकेट को छोड़ दिया जाता है।
यदि वर्तमान में साफ-सुथरा प्राप्त पैकेट डिग्री d > 1 का है, तो इसे पहले संदेश कतार क्षेत्र में सभी पूरी तरह से डिकोड किए गए ब्लॉकों के खिलाफ संसाधित किया जाता है (जैसा कि अगले चरण में पूरी तरह से वर्णित है), फिर बफर क्षेत्र में संग्रहीत किया जाता है यदि इसकी डिग्री कम हो जाती है 1 से बड़ा है।
जब डिग्री डी = 1 का एक नया, साफ पैकेट (ब्लॉक एम_i) प्राप्त होता है (या मौजूदा पैकेट की डिग्री पिछले चरण से 1 तक कम हो जाती है), इसे संदेश कतार क्षेत्र में ले जाया जाता है, और फिर बफर में रहने वाले डिग्री d > 1 के सभी पैकेटों के साथ मिलान किया जाता है। यह किसी भी बफ़र्ड पैकेट के डेटा भाग में अनन्य-ओर किया जाता है जिसे एम का उपयोग करके एन्कोड किया गया था_i, उस मेल खाने वाले पैकेट की डिग्री कम हो जाती है, और उस पैकेट के सूचकांकों की सूची एम के आवेदन को प्रतिबिंबित करने के लिए समायोजित की जाती है_i.
जब यह प्रक्रिया बफर में डिग्री डी = 2 के ब्लॉक को अनलॉक करती है, तो वह ब्लॉक 1 डिग्री तक कम हो जाता है और बदले में संदेश कतार क्षेत्र में ले जाया जाता है, और फिर बफर में शेष पैकेटों के विरुद्ध संसाधित किया जाता है।
जब संदेश के सभी एन ब्लॉक को संदेश कतार क्षेत्र में ले जाया जाता है, तो रिसीवर ट्रांसमीटर को संकेत देता है कि संदेश सफलतापूर्वक डिकोड हो गया है।

यह डिकोडिंग प्रक्रिया काम करती है क्योंकि A $\oplus$ किसी भी बिट स्ट्रिंग A के लिए A = 0। d − 1 अलग-अलग ब्लॉकों को डिग्री d के एक पैकेट में अनन्य-ऑर्ड किए जाने के बाद, बेजोड़ ब्लॉक की मूल अनकोडेड सामग्री ही शेष रह जाती है। प्रतीकों में हमारे पास है

{\begin{aligned}&{}\qquad (M_{i_{1}}\oplus \dots \oplus M_{i_{d}})\oplus (M_{i_{1}}\oplus \dots \oplus M_{i_{k-1}}\oplus M_{i_{k+1}}\oplus \dots \oplus M_{i_{d}})\\&=M_{i_{1}}\oplus M_{i_{1}}\oplus \dots \oplus M_{i_{k-1}}\oplus M_{i_{k-1}}\oplus M_{i_{k}}\oplus M_{i_{k+1}}\oplus M_{i_{k+1}}\oplus \dots \oplus M_{i_{d}}\oplus M_{i_{d}}\\&=0\oplus \dots \oplus 0\oplus M_{i_{k}}\oplus 0\oplus \dots \oplus 0\\&=M_{i_{k}}\,\end{aligned}}

रूपांतर

ऊपर वर्णित एन्कोडिंग और डिकोडिंग प्रक्रियाओं के कई रूपांतर संभव हैं। उदाहरण के लिए, वास्तविक संदेश ब्लॉक सूचकांक {i₁, मैं₂, …, मैं_d}, एनकोडर बस एक छोटी कुंजी भेज सकता है जो छद्म यादृच्छिक संख्या जनरेटर (PRNG) या इंडेक्स की सूची बनाने के लिए उपयोग की जाने वाली इंडेक्स तालिका के लिए बीज के रूप में कार्य करती है। चूँकि एक ही RNG या इंडेक्स टेबल से लैस रिसीवर इस बीज से सूचकांकों की यादृच्छिक सूची को मज़बूती से फिर से बना सकता है, डिकोडिंग प्रक्रिया को सफलतापूर्वक पूरा किया जा सकता है। वैकल्पिक रूप से, एक मजबूत त्रुटि-सुधार कोड के साथ कम औसत डिग्री के एक साधारण एलटी कोड को जोड़कर, एक रैप्टर कोड का निर्माण किया जा सकता है जो अभ्यास में एक अनुकूलित एलटी कोड को बेहतर प्रदर्शन करेगा।^[3]

एलटी कोड का अनुकूलन

सीधे एलटी कोड को अनुकूलित करने के लिए केवल एक पैरामीटर का उपयोग किया जा सकता है: डिग्री डिस्ट्रीब्यूशन फ़ंक्शन (ऊपर 'एलटी एन्कोडिंग' अनुभाग में डिग्री डी के लिए एक छद्म यादृच्छिक संख्या जनरेटर के रूप में वर्णित)। व्यवहार में अन्य यादृच्छिक संख्याएँ (सूचकांकों की सूची { i₁, मैं₂, …, मैं_d} ) हमेशा [0, n) पर एक समान वितरण से लिया जाता है, जहां n उन ब्लॉकों की संख्या है जिनमें संदेश को विभाजित किया गया है।^[4] लुबी स्व^[1]द्वारा परिभाषित आदर्श सॉलिटॉन वितरण पर चर्चा की

{\begin{aligned}\mathrm {P} \{d=1\}&={\frac {1}{n}}\\[2pt]\mathrm {P} \{d=k\}&={\frac {1}{k(k-1)}}\qquad (k=2,3,\dots ,n).\,\end{aligned}}

यह डिग्री वितरण सैद्धांतिक रूप से डिकोडिंग प्रक्रिया पूरी होने से पहले भेजे जाने वाले अनावश्यक कोड शब्दों की अपेक्षित संख्या को कम करता है। हालांकि आदर्श सॉलिटॉन वितरण व्यवहार में अच्छी तरह से काम नहीं करता है क्योंकि अपेक्षित व्यवहार के आसपास किसी भी उतार-चढ़ाव से यह संभावना बनती है कि डिकोडिंग प्रक्रिया में किसी चरण पर (कम) डिग्री 1 का कोई उपलब्ध पैकेट नहीं होगा, इसलिए डिकोडिंग विफल हो जाएगी। इसके अलावा, कुछ मूल ब्लॉक किसी भी ट्रांसमिशन पैकेट में xor-ed नहीं होंगे। इसलिए, व्यवहार में, एक संशोधित वितरण, मजबूत सॉलिटॉन वितरण, को आदर्श वितरण के लिए प्रतिस्थापित किया जाता है। संशोधन का प्रभाव, आम तौर पर, बहुत छोटी डिग्री (लगभग 1) के अधिक पैकेट और 1 से अधिक डिग्री के कम पैकेट का उत्पादन करने के लिए होता है, यह सुनिश्चित करने के लिए चुने गए पैकेटों की स्पाइक को छोड़कर कि सभी मूल ब्लॉक होंगे किसी पैकेट में शामिल।^[4]

यह भी देखें

ऑनलाइन कोड
रैप्टर कोड
बवंडर कोड

नोट्स और संदर्भ

↑ ^1.0 ^1.1 M.Luby, "LT Codes", The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002.
↑ The exclusive or (XOR) operation, symbolized by ⊕, has the very useful property that A ⊕ A = 0, where A is an arbitrary string of bits.
↑ Fountain codes, by D.J.C. MacKay, first published in IEEE Proc.-Commun., Vol. 152, No. 6, December 2005.
↑ ^4.0 ^4.1 Optimizing the Degree Distribution of LT Codes with an Importance Sampling Approach, by Esa Hyytiä, Tuomas Tirronen, and Jorma Virtamo (2006).

इस पेज में लापता आंतरिक लिंक की सूची

बाहरी कड़ियाँ

श्रेणी: कोडिंग सिद्धांत

[Luby-1] 1.0 ^1.1 M.Luby, "LT Codes", The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002.

[2] The exclusive or (XOR) operation, symbolized by ⊕, has the very useful property that A ⊕ A = 0, where A is an arbitrary string of bits.

[MacKay-3] Fountain codes, by D.J.C. MacKay, first published in IEEE Proc.-Commun., Vol. 152, No. 6, December 2005.

[Tirronen-4] 4.0 ^4.1 Optimizing the Degree Distribution of LT Codes with an Importance Sampling Approach, by Esa Hyytiä, Tuomas Tirronen, and Jorma Virtamo (2006).

[1]

[2]

[3]

[4]