वैध LDPC समता जाँच मैट्रिसेस

Question

मुझे LDPC कोड के लिए एक समता जाँच मैट्रिक्स बनाने के लिए कई अलग-अलग तरीके मिले हैं और मैंने उनमें से कुछ को लागू किया है (उदाहरण के लिए मूल गैलगर पहनावा, यह विधि और कुछ और)।

मैंने पाया है, कि वे सभी एक समस्या साझा करते हैं: परिणामी मैट्रिक्स हमेशा एक वैध समता जाँच मैट्रिक्स नहीं होती है।

एक उदाहरण के रूप में, यह एक मैट्रिक्स है जो मुझे गैलगर पहनावा से मिली है (बस एक छोटा सा उदाहरण, एल्गोरिथ्म के लिए खराब मानों को चुना गया है): $$\begin{pmatrix}1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1\\ 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 1 & 0\\ 1 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 1\\ 1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 1 & 0\\ 0 & 0 & 1 & 0 & 1 & 1 & 1 & 0 & 0 & 1\end{pmatrix}$$यह मैट्रिक्स गैलर पहनावा के माध्यम से उत्पन्न हुआ, जाहिर है। लेकिन यह भी एक वैध समता चेक मैट्रिक्स नहीं है, क्योंकि इसे एक समान व्यवस्थित LDPC कोड मैट्रिक्स में नहीं बदला जा सकता है, अर्थात इसके "सही भाग" के निर्धारक।$$\begin{pmatrix}1 & 0 & 0 & 0 & 0 & 0\\ 0 & 1 & 1 & 1 & 1 & 1\\ 1 & 0 & 0 & 0 & 1 & 0\\ 0 & 1 & 1 & 1 & 0 & 1\\ 0 & 0 & 0 & 1 & 1 & 0\\ 1 & 1 & 1 & 0 & 0 & 1\end{pmatrix}$$ के बराबर है $0$।

मेरी समस्या यह है कि वास्तव में इन एल्गोरिदम का उपयोग करने से उत्पन्न अधिकांश मैट्रिसेज़ अवैध हो जाते हैं।

इसलिए, मेरा प्रश्न यह है कि, यदि इन सभी जनरेटर एल्गोरिदम में हमेशा एक वैध समता जाँच मैट्रिक्स वापस करने के लिए एक संशोधन है या अगर मुझे वास्तव में while(invalid) {//generate another one}हमेशा एक वैध मैट्रिक्स प्राप्त करने के लिए करना है ।

Answer 1

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

एक व्यावहारिक $(n,k)$LDPC- कोड में बड़े पैमाने पर पैरामीटर हैं। लंबाई$n$ और रैंक $k$ आमतौर पर संख्या हजारों में होती है, जैसा कि संख्या है $r=n-k$बिट्स की जाँच करें। इसका मतलब यह है कि उस विशाल चेक मैट्रिक्स को कहीं भी स्टोर करना समझदारी नहीं हो सकती है, अकेले उसके साथ इनपुट वैक्टर को गुणा करें। यह विशेष रूप से ऐसा मामला है, जब प्राथमिक पंक्ति संचालन को एक पंक्ति में लाने की आवश्यकता होती है, (संभवतः दाहिने छोर पर इक्वेलन के साथ ) कम घनत्व -प्रतिरोध को नष्ट कर देगा। आप वास्तव में अपेक्षित संख्या के साथ चेक समीकरणों (या जनरेटर मैट्रिक्स की पंक्तियों) का उपयोग नहीं करना चाहते हैं$\approx k/2$ बिट्स के बजाय एकल चेक बिट को परिभाषित करना, कहना $12$, बिट्स के रूप में कम घनत्व संस्करण में मामला होगा।

इसके बजाय, आप कम घनत्व समता चेक समीकरण का उपयोग करके चेक बिट्स बनाने के लिए प्रक्रियाओं को रिकॉर्ड कर सकते हैं। निम्नलिखित चेक मैट्रिक्स पर विचार करें$$ H=\left(\begin{array}{cccccccccc} 1&1&1&1&0&0&0&0&0&0\\ 1&0&0&0&1&1&1&0&0&0\\ 0&1&0&0&1&0&0&1&1&0\\ 0&0&1&0&0&1&0&1&0&1\\ 0&0&0&1&0&0&1&0&1&1 \end{array}\right). $$यह अत्यधिक सममित है कि सभी स्तंभों का वजन दो है, और सभी दस संभावनाएं स्तंभ के रूप में दिखाई देती हैं। ध्यान दें कि इस मैट्रिक्स की रैंक चार है, इसलिए यह चेक मैट्रिक्स होने की आपकी अन्य चिंता में फिट बैठता है जो पूर्ण रैंक नहीं है। अधिक सटीक रूप से, अंतिम पंक्ति अन्य चार का योग है। डिजाइन के अनुसार, सभी स्तंभों का वजन दो होता है!

वैसे भी, एन्कोडिंग के उद्देश्यों के लिए केवल शीर्ष चार पंक्तियां प्रासंगिक हैं (अंतिम चेक समीकरण का उपयोग अभी भी विश्वास प्रचार डिकोडिंग में किया जा सकता है, लेकिन यह एक अलग निर्णय है)। आप देखते हैं कि उनके पास उपयोगी संपत्ति है जो अंतिम है$1$चार शीर्ष पंक्तियाँ अलग-अलग स्तंभों पर होती हैं। यह हम सभी की जरूरत है! हम यह घोषित कर सकते हैं कि जाँच के उन अंतिम बिट्स की स्थिति, यहाँ स्थितियाँ$4$, $7$, $9$ तथा $10$चेक बिट्स हैं, लेकिन अन्य छह स्थिति पेलोड हैं। बेशक, स्तंभों को इस तरह से फेरबदल करना तुच्छ है कि चेक की स्थिति सही छोर पर जाती है।

एन्कोडिंग प्रक्रिया तब तुच्छ है। बस शेष पदों (यहाँ) बाढ़$1,2,3,5,6,8$) सूचना बिट्स के साथ। फिर चेक पदों में भरने के लिए विश्वास प्रसार का एक एकल पुनरावृत्ति चलाएँ: पहला चेक स्थिति की गणना करता है$4$दूसरा पद भरेगा $7$et cetera गौर करें कि जब तक हमने उन्हें "अंतिम भाग लेने वाले प्रतीकों" के लिए अलग से व्यवस्थित करने के लिए केवल मूल समता जाँच की आवश्यकता होती है। यह खिलौना उदाहरण कुछ पहलुओं को छुपाता है:

• $4$ से बाहर $10$ वास्तव में "कम घनत्व" नहीं है, लेकिन उम्मीद है कि आप इस विचार को देखेंगे
• उपरोक्त मैट्रिक्स असाधारण था कि शीर्ष चार समीकरणों में भाग लेने वाले अन्य बिट्स जहां सभी पेलोड बिट्स, और विश्वास प्रसार का एक एकल पुनरावृत्ति पर्याप्त था। यह संभव है ( बहुत संभावना पढ़ें ) कि बड़े मापदंडों के साथ$(n,k)$ये बात नहीं है। आप पूरी तरह से उन मामलों में विश्वास प्रचार चलाना नहीं चाहते हैं। लेकिन, यदि चेक मैट्रिक्स की प्रत्येक पंक्ति में एक निश्चित छोटी संख्या है, तो कहें$w$, $1$s, तो आप बस राशि के रूप में चेक बिट की गणना करते हैं $w-1$ पहले बिट्स , जिनमें से कुछ स्वयं बिट्स की जांच करने की संभावना है।
• इसे स्पष्ट करने के लिए: आपको XOR की आवश्यकता है $w-1$ कुल के लिए जाँच बिट्स में से प्रत्येक के लिए बिट्स $(w-1)r$संचालन। डिजाइन द्वारा निरीक्षण करते हैं$w\ll k$। यदि आपने जांच मैट्रिक्स को अंत में उस पहचान खंड में हेरफेर किया है, तो आपको बिट्स के "यादृच्छिक संख्या" के साथ चेक समीकरण प्राप्त होंगे, और परिणामस्वरूप सामान्य तरीके से चेक मैट्रिक्स (या जनरेटर मैट्रिक्स) का उपयोग करने के लिए एक आवश्यकता होगी संचालन की यादृच्छिक संख्या ($\approx (k/2)$) प्रति चेक बिट के बजाय $w-1$।

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

• DVB के लिए दूसरी पीढ़ी के मानक में LDPC- कोड को परिभाषित करने वाले चेक मेट्रिक्स चेक बिट क्षेत्र में एक सीढ़ी संरचना, साथ ही साथ एक चक्रवात दोहराता संरचना कहीं और लगाते हैं
• IIRC MediaFlo मानक में LDPC- कोड एकल के साथ सर्कुलर ब्लॉक के साथ एक संरचना का उपयोग करते हैं $1$ एक ब्लॉक के भीतर प्रति पंक्ति।

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