कम-घनत्व समता-जाँच कोड: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
Line 2: Line 2:




[[सूचना सिद्धांत]] में, कम-घनत्व समता-जांच (एलडीपीसी) कोड एक [[रैखिक कोड]] [[त्रुटि सुधार कोड]] है, जो [[संकेत शोर]] ट्रांसमिशन चैनल पर एक संदेश प्रसारित करने की एक विधि है।<ref>[[David J.C. MacKay]] (2003) Information theory, Inference and Learning Algorithms, CUP, {{ISBN|0-521-64298-1}}, (also [http://www.inference.phy.cam.ac.uk/mackay/itila/book.html available online])</ref><ref>[[Todd K. Moon]] (2005) Error Correction Coding, Mathematical Methods and Algorithms. Wiley, {{ISBN|0-471-64800-0}} (Includes code)</ref> एक एलडीपीसी कोड एक विरल [[टान्नर ग्राफ]] (द्विपक्षीय ग्राफ का उपवर्ग) का उपयोग करके बनाया गया है।<ref>[[Amin Shokrollahi]] (2003) LDPC Codes: An Introduction</ref> एलडीपीसी कोड हैं:श्रेणी:क्षमता-अनुमोदन कोड|क्षमता-अनुमोदन कोड, जिसका अर्थ है कि व्यावहारिक निर्माण मौजूद हैं जो एक सममित स्मृतिहीन चैनल के लिए शोर सीमा को सैद्धांतिक अधिकतम ([[शैनन-हार्टले प्रमेय]]) के बहुत करीब सेट करने की अनुमति देते हैं। शोर सीमा चैनल शोर के लिए ऊपरी सीमा को परिभाषित करती है, जहां तक ​​खोई हुई जानकारी की संभावना को इच्छानुसार छोटा किया जा सकता है। पुनरावृत्तीय विश्वास प्रसार तकनीकों का उपयोग करके, एलडीपीसी कोड को उनकी ब्लॉक लंबाई के रैखिक समय में डिकोड किया जा सकता है।


खराब शोर की उपस्थिति में बैंडविड्थ-बाधित या रिटर्न-चैनल-बाधित लिंक पर विश्वसनीय और अत्यधिक कुशल सूचना हस्तांतरण की आवश्यकता वाले अनुप्रयोगों में एलडीपीसी कोड का उपयोग बढ़ रहा है। एलडीपीसी कोड का कार्यान्वयन अन्य कोड, विशेषकर [[टर्बो कोड]] से पिछड़ गया है। टर्बो कोड के लिए मौलिक पेटेंट 29 अगस्त 2013 को समाप्त हो गया।<ref>{{cite patent |url=https://www.google.com/patents/US5446747 |country=US |number=5446747}}</ref><ref>NewScientist, ''Communication speed nears terminal velocity'', by Dana Mackenzie, 9 July 2005</ref>
सूचना सिद्धांत में, कम-घनत्व समता-जांच (एलडीपीसी) कोड एक रैखिक त्रुटि सुधार कोड है, जो एक ध्वनि संचरण चैनल पर एक संदेश प्रसारित करने की एक विधि है <ref>[[David J.C. MacKay]] (2003) Information theory, Inference and Learning Algorithms, CUP, {{ISBN|0-521-64298-1}}, (also [http://www.inference.phy.cam.ac.uk/mackay/itila/book.html available online])</ref><ref>[[Todd K. Moon]] (2005) Error Correction Coding, Mathematical Methods and Algorithms. Wiley, {{ISBN|0-471-64800-0}} (Includes code)</ref> एक एलडीपीसी कोड एक विरल [[टान्नर ग्राफ]] (द्विपक्षीय ग्राफ का उपवर्ग) का उपयोग करके बनाया गया है।<ref>[[Amin Shokrollahi]] (2003) LDPC Codes: An Introduction</ref> एलडीपीसी कोड हैं:श्रेणी:क्षमता-अनुमोदन कोड|क्षमता-अनुमोदन कोड, जिसका अर्थ है कि व्यावहारिक निर्माण उपस्थित हैं जो एक सममित मेमोरी लेस चैनल के लिए ध्वनि सीमा को सैद्धांतिक अधिकतम ([[शैनन-हार्टले प्रमेय]]) के बहुत समीप सेट करने की अनुमति देते हैं। ध्वनि सीमा चैनल ध्वनि के लिए ऊपरी सीमा को परिभाषित करती है, जहां तक ​​खोई हुई जानकारी की संभावना को इच्छानुसार छोटा किया जा सकता है। पुनरावृत्तीय विश्वास प्रसार तकनीकों का उपयोग करके, एलडीपीसी कोड को उनकी ब्लॉक लंबाई के रैखिक समय में डिकोड किया जा सकता है।
 
व्यर्थ ध्वनि की उपस्थिति में बैंडविड्थ-बाधित या रिटर्न-चैनल-बाधित लिंक पर विश्वसनीय और अत्यधिक कुशल सूचना हस्तांतरण की आवश्यकता वाले एप्लीकेशन में एलडीपीसी कोड का उपयोग बढ़ रहा है। एलडीपीसी कोड का कार्यान्वयन अन्य कोड, विशेषकर [[टर्बो कोड]] से पिछड़ गया है। टर्बो कोड के लिए मौलिक पेटेंट 29 अगस्त 2013 को समाप्त हो गया।<ref>{{cite patent |url=https://www.google.com/patents/US5446747 |country=US |number=5446747}}</ref><ref>NewScientist, ''Communication speed nears terminal velocity'', by Dana Mackenzie, 9 July 2005</ref>
 
एलडीपीसी कोड को रॉबर्ट जी गैलगर के सम्मान में गैलगर कोड के रूप में भी जाना जाता है, जिन्होंने 1960 में [[मैसाचुसेट्स की तकनीकी संस्था]] में अपने डॉक्टरेट शोध प्रबंध में एलडीपीसी अवधारणा विकसित की थी।<ref>{{Cite news |url=http://web.mit.edu/newsoffice/2010/gallager-codes-0121.html |title=Explained: Gallager codes |author=Larry Hardesty |journal=MIT News |date= January 21, 2010 |access-date= August 7, 2013 }}</ref><ref name="G1962">[https://ieeexplore.ieee.org/document/1057683] R. G. Gallager, "Low density parity check codes," IRE Trans. Inf. Theory, vol. IT-8, no. 1, pp. 21- 28, Jan. 1962.</ref> एलडीपीसी कोड में आदर्श संयोजन गुण भी दिखाए गए हैं। अपने शोध प्रबंध में, गैलागर ने दिखाया कि एलडीपीसी कोड उच्च संभावना वाले बाइनरी क्षेत्रों पर रैखिक कोड के लिए बाध्य गिल्बर्ट-वार्शमोव को प्राप्त करते हैं। 2020 में यह दिखाया गया कि गैलेजर के एलडीपीसी कोड [[सूची डिकोडिंग]] क्षमता प्राप्त करते हैं और सामान्य क्षेत्रों पर रैखिक कोड के लिए बाध्य गिल्बर्ट-वार्शमोव भी प्राप्त करते हैं। <ref name="MRRSW20">[https://epubs.siam.org/doi/abs/10.1137/20M1365934] J. Moshieff, N. Resch, N. Ron-Zewi, S. Silas, [[Mary Wootters|M. Wootters]], "Low-density parity-check codes achieve list-decoding capacity," SIAM Journal on Computing, FOCS20-38-FOCS20-73.</ref>
एलडीपीसी कोड को रॉबर्ट जी गैलगर के सम्मान में गैलगर कोड के रूप में भी जाना जाता है, जिन्होंने 1960 में [[मैसाचुसेट्स की तकनीकी संस्था]] में अपने डॉक्टरेट शोध प्रबंध में एलडीपीसी अवधारणा विकसित की थी।<ref>{{Cite news |url=http://web.mit.edu/newsoffice/2010/gallager-codes-0121.html |title=Explained: Gallager codes |author=Larry Hardesty |journal=MIT News |date= January 21, 2010 |access-date= August 7, 2013 }}</ref><ref name="G1962">[https://ieeexplore.ieee.org/document/1057683] R. G. Gallager, "Low density parity check codes," IRE Trans. Inf. Theory, vol. IT-8, no. 1, pp. 21- 28, Jan. 1962.</ref> एलडीपीसी कोड में आदर्श संयोजन गुण भी दिखाए गए हैं। अपने शोध प्रबंध में, गैलागर ने दिखाया कि एलडीपीसी कोड उच्च संभावना वाले बाइनरी क्षेत्रों पर रैखिक कोड के लिए बाध्य गिल्बर्ट-वार्शमोव को प्राप्त करते हैं। 2020 में यह दिखाया गया कि गैलेजर के एलडीपीसी कोड [[सूची डिकोडिंग]] क्षमता प्राप्त करते हैं और सामान्य क्षेत्रों पर रैखिक कोड के लिए बाध्य गिल्बर्ट-वार्शमोव भी प्राप्त करते हैं। <ref name="MRRSW20">[https://epubs.siam.org/doi/abs/10.1137/20M1365934] J. Moshieff, N. Resch, N. Ron-Zewi, S. Silas, [[Mary Wootters|M. Wootters]], "Low-density parity-check codes achieve list-decoding capacity," SIAM Journal on Computing, FOCS20-38-FOCS20-73.</ref>




==इतिहास==
==इतिहास==
1963 में रॉबर्ट जी. गैलागर द्वारा पहली बार विकसित होने पर इसे लागू करना अव्यावहारिक था।<ref>{{Cite book |author= Robert G. Gallager |title= कम घनत्व समता जाँच कोड|publisher= Monograph, M.I.T. Press |year= 1963 |url= http://www.inference.phy.cam.ac.uk/mackay/gallager/papers/ldpc.pdf |access-date= August 7, 2013 }}</ref> 1996 में उनका काम दोबारा खोजे जाने तक एलडीपीसी कोड भुला दिए गए थे।<ref name=MacKay96>[[David J.C. MacKay]] and Radford M. Neal, "Near Shannon Limit Performance of Low Density Parity Check Codes," Electronics Letters, July 1996</ref> टर्बो कोड, 1993 में खोजे गए क्षमता-अनुरूप कोड का एक और वर्ग, 1990 के दशक के अंत में पसंद की कोडिंग योजना बन गया, जिसका उपयोग [[डीप स्पेस नेटवर्क]] और [[उपग्रह संचार]] जैसे अनुप्रयोगों के लिए किया जाता था। हालाँकि, कम-घनत्व समता-जाँच कोड में प्रगति ने उन्हें त्रुटि स्तर और उच्च [[कोड दर]] सीमा में प्रदर्शन के मामले में टर्बो कोड से आगे निकलते देखा है, जिससे टर्बो कोड केवल कम कोड दरों के लिए बेहतर अनुकूल हो गए हैं।<ref>[http://deepspace.jpl.nasa.gov/dsndocs/810-005/208/208B.pdf Telemetry Data Decoding, Design Handbook]</ref>
1963 में रॉबर्ट जी. गैलागर द्वारा पहली बार विकसित होने पर इसे प्रयुक्त करना अव्यावहारिक था।<ref>{{Cite book |author= Robert G. Gallager |title= कम घनत्व समता जाँच कोड|publisher= Monograph, M.I.T. Press |year= 1963 |url= http://www.inference.phy.cam.ac.uk/mackay/gallager/papers/ldpc.pdf |access-date= August 7, 2013 }}</ref> 1996 में उनका काम दोबारा खोजे जाने तक एलडीपीसी कोड भुला दिए गए थे।<ref name=MacKay96>[[David J.C. MacKay]] and Radford M. Neal, "Near Shannon Limit Performance of Low Density Parity Check Codes," Electronics Letters, July 1996</ref> टर्बो कोड, 1993 में खोजे गए क्षमता-अनुरूप कोड का एक और वर्ग, 1990 के दशक के अंत में पसंद की कोडिंग योजना बन गया, जिसका उपयोग [[डीप स्पेस नेटवर्क]] और [[उपग्रह संचार]] जैसे एप्लीकेशन के लिए किया जाता था। चूँकि, कम-घनत्व समता-जाँच कोड में प्रगति ने उन्हें त्रुटि स्तर और उच्च [[कोड दर]] सीमा में प्रदर्शन के स्थिति में टर्बो कोड से आगे निकलते देखा है, जिससे टर्बो कोड केवल कम कोड दरों के लिए उत्तम अनुकूल हो गए हैं।<ref>[http://deepspace.jpl.nasa.gov/dsndocs/810-005/208/208B.pdf Telemetry Data Decoding, Design Handbook]</ref>
 


==एप्लीकेशन ==
2003 में, एक रिपीट-एक्युमुलेट कोड या इररेगुलर रिपीट एक्युमुलेट कोड्स (आईआरए) स्टाइल एलडीपीसी कोड छह टर्बो कोड को पराजित करके [[डिजिटल टेलीविजन]] के लिए नए [[डीवीबी-एस 2]] मानक में त्रुटि-सुधार करने वाला कोड बन गया।<ref name="hughesdvb">[http://www.ieeevtc.org/vtc2003fall/2003panelsessions/llee.pdf Presentation by Hughes Systems] {{webarchive|url=https://web.archive.org/web/20061008053124/http://www.ieeevtc.org/vtc2003fall/2003panelsessions/llee.pdf |date=2006-10-08 }}</ref> डीवीबी-S2 चयन समिति ने समानांतर डिकोडर आर्किटेक्चर के अतिरिक्त बहुत कम कुशल सीरियल डिकोडर आर्किटेक्चर का उपयोग करके टर्बो कोड प्रस्तावों के लिए डिकोडर कॉम्प्लेक्सिटी  अनुमान लगाया। इसने टर्बो कोड प्रस्तावों को एलडीपीसी प्रस्तावों के आधे फ्रेम आकार के क्रम पर फ्रेम आकार का उपयोग करने के लिए विविश किया था।


==अनुप्रयोग==
2008 में, एलडीपीसी ने [[ITU-T]] G.hn मानक के लिए [[ आगे त्रुटि सुधार |आगे त्रुटि सुधार]] (एफईसी) प्रणाली के रूप में कन्वेन्शनल टर्बो कोड को पराजित करते है।<ref>[http://homepnablog.typepad.com/my_weblog/2008/12/ghn-a-phy-for-all-seasons.html HomePNA Blog: G.hn, a PHY For All Seasons]</ref> G.hn ने टर्बो कोड की तुलना में एलडीपीसी कोड को उनकी कम डिकोडिंग कॉम्प्लेक्सिटी  के कारण चुना (विशेषकर जब 1.0 Gbit/s के समीप डेटा दरों पर काम कर रहा हो) और क्योंकि प्रस्तावित टर्बो कोड ने ऑपरेशन की वांछित सीमा पर एक महत्वपूर्ण त्रुटि स्तर प्रदर्शित किया था।<ref>[http://blog.ds2.es/ds2blog/2009/10/ieee-communications-magazine-paper-on-ghn.html IEEE Communications Magazine paper on G.hn] {{webarchive|url=https://web.archive.org/web/20091213012126/http://blog.ds2.es/ds2blog/2009/10/ieee-communications-magazine-paper-on-ghn.html |date=2009-12-13 }}</ref>
2003 में, एक रिपीट-एक्युमुलेट कोड#इररेगुलर रिपीट एक्युमुलेट कोड्स (आईआरए) स्टाइल एलडीपीसी कोड छह टर्बो कोड को हराकर [[डिजिटल टेलीविजन]] के लिए नए [[डीवीबी-एस 2]] मानक में त्रुटि-सुधार करने वाला कोड बन गया।<ref name="hughesdvb">[http://www.ieeevtc.org/vtc2003fall/2003panelsessions/llee.pdf Presentation by Hughes Systems] {{webarchive|url=https://web.archive.org/web/20061008053124/http://www.ieeevtc.org/vtc2003fall/2003panelsessions/llee.pdf |date=2006-10-08 }}</ref> DVB-S2 चयन समिति ने समानांतर डिकोडर आर्किटेक्चर के बजाय बहुत कम कुशल सीरियल डिकोडर आर्किटेक्चर का उपयोग करके टर्बो कोड प्रस्तावों के लिए डिकोडर जटिलता अनुमान लगाया। इसने टर्बो कोड प्रस्तावों को एलडीपीसी प्रस्तावों के आधे फ्रेम आकार के क्रम पर फ्रेम आकार का उपयोग करने के लिए मजबूर किया।


2008 में, LDPC ने [[ITU-T]] G.hn मानक के लिए [[ आगे त्रुटि सुधार |आगे त्रुटि सुधार]] (FEC) सिस्टम के रूप में कन्वेन्शनल टर्बो कोड को हराया।<ref>[http://homepnablog.typepad.com/my_weblog/2008/12/ghn-a-phy-for-all-seasons.html HomePNA Blog: G.hn, a PHY For All Seasons]</ref> G.hn ने टर्बो कोड की तुलना में LDPC कोड को उनकी कम डिकोडिंग जटिलता के कारण चुना (विशेषकर जब 1.0 Gbit/s के करीब डेटा दरों पर काम कर रहा हो) और क्योंकि प्रस्तावित टर्बो कोड ने ऑपरेशन की वांछित सीमा पर एक महत्वपूर्ण त्रुटि स्तर प्रदर्शित किया।<ref>[http://blog.ds2.es/ds2blog/2009/10/ieee-communications-magazine-paper-on-ghn.html IEEE Communications Magazine paper on G.hn] {{webarchive|url=https://web.archive.org/web/20091213012126/http://blog.ds2.es/ds2blog/2009/10/ieee-communications-magazine-paper-on-ghn.html |date=2009-12-13 }}</ref>
एलडीपीसी कोड का उपयोग [[10GBASE-T]] ईथरनेट के लिए भी किया जाता है, जो ट्विस्टेड-पेयर केबल पर 10 गीगाबिट प्रति सेकंड पर डेटा भेजता है। 2009 तक, हाई थ्रूपुट (HT) पीएचवाई विनिर्देश में, एलडीपीसी कोड 802.11n और 802.11ac के वैकल्पिक भाग के रूप में वाई-फाई 802.11 मानक का भी भाग हैं।<ref>IEEE Standard, section 20.3.11.6 [http://standards.ieee.org/getieee802/download/802.11n-2009.pdf "802.11n-2009"], IEEE, October 29, 2009, accessed March 21, 2011.</ref> एलडीपीसी 802.11ax (वाई-फाई 6) का एक अनिवार्य भाग है।<ref>{{cite web |title=IEEE SA - IEEE 802.11ax-2021 |url=https://standards.ieee.org/ieee/802.11ax/7180/ |website=IEEE Standards Association |access-date=22 May 2022 |language=en}}</ref>
एलडीपीसी कोड का उपयोग [[10GBASE-T]] ईथरनेट के लिए भी किया जाता है, जो ट्विस्टेड-पेयर केबल पर 10 गीगाबिट प्रति सेकंड पर डेटा भेजता है। 2009 तक, हाई थ्रूपुट (HT) PHY विनिर्देश में, LDPC कोड 802.11n और 802.11ac के वैकल्पिक भाग के रूप में वाई-फाई 802.11 मानक का भी हिस्सा हैं।<ref>IEEE Standard, section 20.3.11.6 [http://standards.ieee.org/getieee802/download/802.11n-2009.pdf "802.11n-2009"], IEEE, October 29, 2009, accessed March 21, 2011.</ref> एलडीपीसी 802.11ax (वाई-फाई 6) का एक अनिवार्य हिस्सा है।<ref>{{cite web |title=IEEE SA - IEEE 802.11ax-2021 |url=https://standards.ieee.org/ieee/802.11ax/7180/ |website=IEEE Standards Association |access-date=22 May 2022 |language=en}}</ref>
कुछ [[ओएफडीएम]] सिस्टम एक अतिरिक्त बाहरी त्रुटि सुधार जोड़ते हैं जो कभी-कभी होने वाली त्रुटियों (त्रुटि स्तर) को ठीक करता है जो कम [[बिट त्रुटि दर]] पर भी एलडीपीसी सुधार आंतरिक कोड से आगे निकल जाता है।


उदाहरण के लिए:
कुछ [[ओएफडीएम]] प्रणाली एक अतिरिक्त बाहरी त्रुटि सुधार जोड़ते हैं जो कभी-कभी होने वाली त्रुटियों (त्रुटि स्तर) को ठीक करता है जो कम [[बिट त्रुटि दर]] पर भी एलडीपीसी सुधार आंतरिक कोड से आगे निकल जाता है।
एलडीपीसी कोडेड मॉड्यूलेशन (आरएस-एलसीएम) के साथ [[रीड-सोलोमन कोड]] रीड-सोलोमन बाहरी कोड का उपयोग करता है।<ref>
 
उदाहरण के लिए: एलडीपीसी कोडेड मॉड्यूलेशन (आरएस-एलसीएम) के साथ [[रीड-सोलोमन कोड]] रीड-सोलोमन बाहरी कोड का उपयोग करता है।<ref>
Chih-Yuan Yang, Mong-Kai Ku.
Chih-Yuan Yang, Mong-Kai Ku.
http://123seminarsonly.com/Seminar-Reports/029/26540350-Ldpc-Coded-Ofdm-Modulation.pdf
http://123seminarsonly.com/Seminar-Reports/029/26540350-Ldpc-Coded-Ofdm-Modulation.pdf
"LDPC coded OFDM modulation for high spectral efficiency transmission"
"LDPC coded OFDM modulation for high spectral efficiency transmission"
</ref> DVB-S2, DVB-T2 और DVB-C2 मानक सभी LDPC डिकोडिंग के बाद अवशिष्ट त्रुटियों को मिटाने के लिए BCH कोड [[बीसीएच कोड]] का उपयोग करते हैं।<ref>
</ref> डीवीबी-S2, डीवीबी-T2 और डीवीबी-C2 मानक सभी एलडीपीसी डिकोडिंग के बाद अवशिष्ट त्रुटियों को मिटाने के लिए BCH कोड [[बीसीएच कोड]] का उपयोग करते हैं।<ref>
Nick Wells.
Nick Wells.
[http://www.atsc.org/cms/pdf/pt2/Wells_ATSC_paper_on_T2.pdf "DVB-T2 in relation to the DVB-x2 Family of Standards"] {{webarchive|url=https://web.archive.org/web/20130526003113/http://www.atsc.org/cms/pdf/pt2/Wells_ATSC_paper_on_T2.pdf |date=2013-05-26 }}
[http://www.atsc.org/cms/pdf/pt2/Wells_ATSC_paper_on_T2.pdf "DVB-T2 in relation to the DVB-x2 Family of Standards"] {{webarchive|url=https://web.archive.org/web/20130526003113/http://www.atsc.org/cms/pdf/pt2/Wells_ATSC_paper_on_T2.pdf |date=2013-05-26 }}
</ref>
</ref>
[[5जी नं]] नियंत्रण चैनलों के लिए पोलर कोड (कोडिंग सिद्धांत) और डेटा चैनलों के लिए एलडीपीसी का उपयोग करता है।<ref>{{cite web|url=https://accelercomm.com/sites/accelercomm.com/files/5G-Channel-Coding_0.pdf|title=5G Channel Coding|access-date=January 6, 2019|archive-url=https://web.archive.org/web/20181206003124/https://www.accelercomm.com/sites/accelercomm.com/files/5G-Channel-Coding_0.pdf|archive-date=December 6, 2018|url-status=dead}}</ref><ref>{{cite web|url=https://accelercomm.com/sites/accelercomm.com/files/5G-Channel-Coding_0.pdf|title=A Vision for 5G Channel Coding|last=Maunder|first=Robert|date=September 2016|access-date=January 6, 2019|archive-url=https://web.archive.org/web/20181206003124/https://www.accelercomm.com/sites/accelercomm.com/files/5G-Channel-Coding_0.pdf|archive-date=December 6, 2018|url-status=dead}}</ref>
[[5जी नं]] नियंत्रण चैनलों के लिए पोलर कोड (कोडिंग सिद्धांत) और डेटा चैनलों के लिए एलडीपीसी का उपयोग करता है।<ref>{{cite web|url=https://accelercomm.com/sites/accelercomm.com/files/5G-Channel-Coding_0.pdf|title=5G Channel Coding|access-date=January 6, 2019|archive-url=https://web.archive.org/web/20181206003124/https://www.accelercomm.com/sites/accelercomm.com/files/5G-Channel-Coding_0.pdf|archive-date=December 6, 2018|url-status=dead}}</ref><ref>{{cite web|url=https://accelercomm.com/sites/accelercomm.com/files/5G-Channel-Coding_0.pdf|title=A Vision for 5G Channel Coding|last=Maunder|first=Robert|date=September 2016|access-date=January 6, 2019|archive-url=https://web.archive.org/web/20181206003124/https://www.accelercomm.com/sites/accelercomm.com/files/5G-Channel-Coding_0.pdf|archive-date=December 6, 2018|url-status=dead}}</ref>
यद्यपि एलडीपीसी कोड को वाणिज्यिक हार्ड डिस्क ड्राइव में सफलता मिली है, [[एसएसडी]] में इसकी त्रुटि सुधार क्षमता का पूरी तरह से फायदा उठाने के लिए अपरंपरागत बारीक फ्लैश मेमोरी सेंसिंग की आवश्यकता होती है, जिससे मेमोरी रीड विलंबता में वृद्धि होती है। एलडीपीसी-इन-एसएसडी<ref>{{Cite conference |author= Kai Zhao, Wenzhe Zhao, Hongbin Sun, Tong Zhang, Xiaodong Zhang, and Nanning Zheng | title=" LDPC-in-SSD: Making Advanced Error Correction Codes Work Effectively in Solid State Drives" |conference= FAST' 13| pages=243–256|year=2013|url=https://www.usenix.org/system/files/conference/fast13/fast13-final125.pdf}}</ref> बहुत कम विलंबता वृद्धि के साथ एसएसडी में एलडीपीसी को तैनात करने का एक प्रभावी तरीका है, जो एसएसडी में एलडीपीसी को वास्तविकता में बदल देता है। तब से, एलडीपीसी को प्रमुख भंडारण विक्रेताओं द्वारा ग्राहक-ग्रेड और एंटरप्राइज़-ग्रेड दोनों में वाणिज्यिक एसएसडी में व्यापक रूप से अपनाया गया है। कई टीएलसी (और बाद के) एसएसडी एलडीपीसी कोड का उपयोग कर रहे हैं। सबसे पहले एक तेज़ हार्ड-डिकोड (बाइनरी इरेज़र) का प्रयास किया जाता है, जो धीमी लेकिन अधिक शक्तिशाली सॉफ्ट डिकोडिंग में वापस आ सकता है।<ref>{{cite web|url= https://www.eetimes.com/soft-decoding-in-ldpc-based-ssd-controllers/|website=EE Times|date=2015|title= Soft-Decoding in LDPC based SSD Controllers}}</ref>
 
यद्यपि एलडीपीसी कोड को वाणिज्यिक हार्ड डिस्क ड्राइव में सफलता मिली है, [[एसएसडी]] में इसकी त्रुटि सुधार क्षमता का पूरी तरह से लाभ  उठाने के लिए अपरंपरागत समीप फ्लैश मेमोरी सेंसिंग की आवश्यकता होती है, जिससे मेमोरी रीड विलंबता में वृद्धि होती है। एलडीपीसी-इन-एसएसडी<ref>{{Cite conference |author= Kai Zhao, Wenzhe Zhao, Hongbin Sun, Tong Zhang, Xiaodong Zhang, and Nanning Zheng | title=" LDPC-in-SSD: Making Advanced Error Correction Codes Work Effectively in Solid State Drives" |conference= FAST' 13| pages=243–256|year=2013|url=https://www.usenix.org/system/files/conference/fast13/fast13-final125.pdf}}</ref> बहुत कम विलंबता वृद्धि के साथ एसएसडी में एलडीपीसी को तैनात करने का एक प्रभावी विधि है, जो एसएसडी में एलडीपीसी को वास्तविकता में बदल देता है। तब से, एलडीपीसी को प्रमुख संचयन विक्रेताओं द्वारा ग्राहक-ग्रेड और एंटरप्राइज़-ग्रेड दोनों में वाणिज्यिक एसएसडी में व्यापक रूप से अपनाया गया है। कई टीएलसी (और बाद के) एसएसडी एलडीपीसी कोड का उपयोग कर रहे हैं। सबसे पहले एक तेज़ हार्ड-डिकोड (बाइनरी इरेज़र) का प्रयास किया जाता है, जो धीमी किंतु अधिक शक्तिशाली सॉफ्ट डिकोडिंग में वापस आ सकता है।<ref>{{cite web|url= https://www.eetimes.com/soft-decoding-in-ldpc-based-ssd-controllers/|website=EE Times|date=2015|title= Soft-Decoding in LDPC based SSD Controllers}}</ref>
 




==परिचालन उपयोग==
==परिचालन उपयोग==
एलडीपीसी कोड कार्यात्मक रूप से विरल [[समता-जांच मैट्रिक्स]] द्वारा परिभाषित किए जाते हैं। यह [[विरल मैट्रिक्स]] अक्सर यादृच्छिक रूप से उत्पन्न होता है, [[विरलता]] बाधाओं के अधीन - #कोड निर्माण पर चर्चा की जाती है #कोड निर्माण। ये कोड पहली बार 1960 में रॉबर्ट गैलागर द्वारा डिज़ाइन किए गए थे।<ref name="G1962" />
एलडीपीसी कोड कार्यात्मक रूप से विरल समता-जांच आव्यूह द्वारा परिभाषित किए जाते हैं। यह विरल आव्यूह  अधिकांशतः यादृच्छिक रूप से उत्पन्न होता है, विरलता बाधाओं के अधीन - एलडीपीसी कोड निर्माण पर बाद में चर्चा की जाती है। ये कोड पहली बार 1960 में रॉबर्ट गैलागर द्वारा डिज़ाइन किए गए थे।<ref name="G1962" />


नीचे फ़ैक्टर ग्राफ़|फ़ोर्नी के फ़ैक्टर ग्राफ़ नोटेशन का उपयोग करते हुए एक उदाहरण एलडीपीसी कोड का ग्राफ़ टुकड़ा दिया गया है। इस ग्राफ़ में, ग्राफ़ के शीर्ष में n वैरिएबल नोड्स ग्राफ़ के निचले भाग में (n−k) बाधा नोड्स से जुड़े हुए हैं।
नीचे फ़ॉर्नी के फ़ैक्टर ग्राफ़ नोटेशन का उपयोग करते हुए एक उदाहरण एलडीपीसी कोड का ग्राफ़ टुकड़ा दिया गया है। इस ग्राफ़ में, ग्राफ़ के शीर्ष में n वैरिएबल नोड्स ग्राफ़ के निचले भाग में (n−k) बाधा नोड्स से जुड़े हुए हैं।


यह (एन,के) एलडीपीसी कोड को ग्राफ़िक रूप से प्रस्तुत करने का एक लोकप्रिय तरीका है। एक वैध संदेश के बिट्स, जब ग्राफ़ के शीर्ष पर 'टी' पर रखे जाते हैं, तो ग्राफिकल बाधाओं को पूरा करते हैं। विशेष रूप से, एक वेरिएबल नोड ('=' चिन्ह वाला बॉक्स) से जुड़ने वाली सभी पंक्तियों का मान समान होता है, और कारक नोड ('+' चिन्ह वाला बॉक्स) से जुड़ने वाले सभी मानों का योग, [[मॉड्यूलर अंकगणित]]ीय दो, शून्य तक होना चाहिए (दूसरे शब्दों में, उन्हें एक सम संख्या में योग करना चाहिए; या विषम मानों की एक सम संख्या होनी चाहिए)।
यह (n , k) एलडीपीसी कोड को ग्राफ़िक रूप से प्रस्तुत करने का एक लोकप्रिय विधि है। एक वैध संदेश के बिट्स, जब ग्राफ़ के शीर्ष पर ''''T's'''<nowiki/>' पर रखे जाते हैं, तो ग्राफिकल बाधाओं को पूरा करते हैं। विशेष रूप से, एक वेरिएबल नोड ('=' चिन्ह वाला बॉक्स) से जुड़ने वाली सभी पंक्तियों का मान समान होता है, और कारक नोड ('+' चिन्ह वाला बॉक्स) से जुड़ने वाले सभी मानों का योग, [[मॉड्यूलर अंकगणित]] दो, शून्य तक होना चाहिए (दूसरे शब्दों में, उन्हें एक सम संख्या में योग करना चाहिए; या विषम मानों की एक सम संख्या होनी चाहिए)।


[[Image:ldpc code fragment factor graph.svg|none]]तस्वीर से बाहर जाने वाली किसी भी लाइन को नजरअंदाज करते हुए, वैध कोडवर्ड के अनुरूप आठ संभावित छह-बिट स्ट्रिंग हैं: (यानी, 000000, 011001, 110010, 101011, 111100, 100101, 001110, 010111)। यह एलडीपीसी कोड खंड छह बिट्स के रूप में एन्कोडेड तीन-बिट संदेश का प्रतिनिधित्व करता है। चैनल त्रुटियों से उबरने की संभावना बढ़ाने के लिए, यहां अतिरेक का उपयोग किया जाता है। यह एक (6, 3) रैखिक कोड है, जिसमें n = 6 और k = 3 है।
[[Image:ldpc code fragment factor graph.svg|none]]छवि से बाहर जाने वाली किसी भी लाइन को अनदेखा करते हुए, वैध कोडवर्ड के अनुरूप आठ संभावित छह-बिट स्ट्रिंग हैं: (अथार्थ  , 000000, 011001, 110010, 101011, 111100, 100101, 001110, 010111)। यह एलडीपीसी कोड खंड छह बिट्स के रूप में एन्कोडेड तीन-बिट संदेश का प्रतिनिधित्व करता है। चैनल त्रुटियों से उबरने की संभावना बढ़ाने के लिए, यहां अतिरेक का उपयोग किया जाता है। यह एक (6, 3) रैखिक कोड है, जिसमें n = 6 और k = 3 है।


चित्र से बाहर जाने वाली रेखाओं को फिर से अनदेखा करते हुए, समता-जाँच मैट्रिक्स इस ग्राफ़ खंड का प्रतिनिधित्व करता है
चित्र से बाहर जाने वाली रेखाओं को फिर से अनदेखा करते हुए, समता-जाँच आव्यूह इस ग्राफ़ खंड का प्रतिनिधित्व करता है


:<math>
:<math>
Line 51: Line 58:
\end{pmatrix}.
\end{pmatrix}.
</math>
</math>
इस मैट्रिक्स में, प्रत्येक पंक्ति तीन समता-जांच बाधाओं में से एक का प्रतिनिधित्व करती है, जबकि प्रत्येक कॉलम प्राप्त कोडवर्ड में छह बिट्स में से एक का प्रतिनिधित्व करता है।
इस आव्यूह में, प्रत्येक पंक्ति तीन समता-जांच बाधाओं में से एक का प्रतिनिधित्व करती है, जबकि प्रत्येक स्तम्भ प्राप्त कोडवर्ड में छह बिट्स में से एक का प्रतिनिधित्व करता है।


इस उदाहरण में, समता-जांच मैट्रिक्स एच को इस फॉर्म में डालकर आठ कोडवर्ड प्राप्त किए जा सकते हैं <math>\begin{bmatrix} -P^T | I_{n-k} \end{bmatrix}</math> [[GF(2)]] में बुनियादी [[पंक्ति संचालन]] के माध्यम से:
इस उदाहरण में, जीएफ(2) में मूलभूत पंक्ति संचालन के माध्यम से समता-जांच आव्यूह '''H'''  को इस फॉर्म <math>\begin{bmatrix} -P^T | I_{n-k} \end{bmatrix}</math> में डालकर आठ कोडवर्ड प्राप्त किए जा सकते हैं:
:<math>\mathbf{H}
:<math>\mathbf{H}
=
=
Line 88: Line 95:
चरण 4: पंक्ति 1 को पंक्ति 3 में जोड़ा जाता है।
चरण 4: पंक्ति 1 को पंक्ति 3 में जोड़ा जाता है।


इससे [[जनरेटर मैट्रिक्स]] G को इस प्रकार प्राप्त किया जा सकता है <math>\begin{bmatrix} I_{k} | P \end{bmatrix}</math> (ध्यान दें कि विशेष मामले में यह एक बाइनरी कोड है <math>P = -P</math>), या विशेष रूप से:
इससे, जनरेटर आव्यूह G को <math>\begin{bmatrix} I_{k} | P \end{bmatrix}</math> के रूप में प्राप्त किया जा सकता है (ध्यान दें कि विशेष स्थिति में यह एक बाइनरी कोड <math>P = -P</math> है), या विशेष रूप से:


:<math>\mathbf{G}
:<math>\mathbf{G}
Line 116: Line 123:
</math>,
</math>,


कहाँ <math>\odot</math> मॉड 2 गुणन का प्रतीक है।
जहाँ <math>\odot</math> मॉड 2 गुणन का प्रतीक है।


जाँच के रूप में, G की पंक्ति का स्थान H के लिए ओर्थोगोनल है जैसे कि <math> G \odot H^T = 0 </math>
जाँच के रूप में, G की पंक्ति का स्थान H के लिए ओर्थोगोनल है जैसे कि <math> G \odot H^T = 0 </math>
बिट-स्ट्रिंग '101' कोडवर्ड '101011' के पहले 3 बिट्स के रूप में पाई जाती है।
बिट-स्ट्रिंग '101' कोडवर्ड '101011' के पहले 3 बिट्स के रूप में पाई जाती है।


== उदाहरण एन्कोडर ==
== उदाहरण एन्कोडर ==
[[File:LDPC encoder Figure.png|thumb|none|500px|एलडीपीसी एनकोडर]]एक फ्रेम के एन्कोडिंग के दौरान, इनपुट डेटा बिट्स (डी) को दोहराया जाता है और घटक एन्कोडर्स के एक सेट में वितरित किया जाता है। घटक एनकोडर आम तौर पर संचायक होते हैं और प्रत्येक संचायक का उपयोग समता प्रतीक उत्पन्न करने के लिए किया जाता है। मूल डेटा की एक प्रति (एस<sub>0,K-1</sub>) कोड प्रतीकों को बनाने के लिए समता बिट्स (पी) के साथ प्रेषित होता है। प्रत्येक घटक एनकोडर से एस बिट्स को हटा दिया जाता है।
[[File:LDPC encoder Figure.png|thumb|none|500px|एलडीपीसी एनकोडर]]एक फ्रेम के एन्कोडिंग के समय , इनपुट डेटा बिट्स (डी) को दोहराया जाता है और कांस्टीटुएंट एन्कोडर्स के एक सेट में वितरित किया जाता है। कांस्टीटुएंट एनकोडर समान्यत: संचायक होते हैं और प्रत्येक संचायक का उपयोग समता प्रतीक उत्पन्न करने के लिए किया जाता है। मूल डेटा की एक प्रति (S<sub>0,K-1</sub>) कोड प्रतीकों को बनाने के लिए समता बिट्स (पी) के साथ प्रेषित होता है। प्रत्येक कांस्टीटुएंट एनकोडर से एस बिट्स को हटा दिया जाता है।


समता बिट का उपयोग किसी अन्य घटक कोड के भीतर किया जा सकता है।
समता बिट का उपयोग किसी अन्य कांस्टीटुएंट कोड के अंदर किया जा सकता है।


DVB-S2 रेट 2/3 कोड का उपयोग करते हुए एक उदाहरण में एन्कोडेड ब्लॉक का आकार 64800 प्रतीक (N=64800) है जिसमें 43200 डेटा बिट्स (K=43200) और 21600 पैरिटी बिट्स (M=21600) हैं। प्रत्येक घटक कोड (चेक नोड) पहले समता बिट को छोड़कर 16 डेटा बिट्स को एनकोड करता है जो 8 डेटा बिट्स को एनकोड करता है। पहले 4680 डेटा बिट्स को 13 बार दोहराया जाता है (13 समता कोड में उपयोग किया जाता है), जबकि शेष डेटा बिट्स 3 समता कोड (अनियमित एलडीपीसी कोड) में उपयोग किया जाता है।
डीवीबी-S2 रेट 2/3 कोड का उपयोग करते हुए एक उदाहरण में एन्कोडेड ब्लॉक का आकार 64800 प्रतीक (N=64800) है जिसमें 43200 डेटा बिट्स (K=43200) और 21600 पैरिटी बिट्स (M=21600) हैं। प्रत्येक कांस्टीटुएंट कोड (चेक नोड) पहले समता बिट को छोड़कर 16 डेटा बिट्स को एनकोड करता है जो 8 डेटा बिट्स को एनकोड करता है। पहले 4680 डेटा बिट्स को 13 बार दोहराया जाता है (13 समता कोड में उपयोग किया जाता है), जबकि शेष डेटा बिट्स 3 समता कोड (अनियमित एलडीपीसी कोड) में उपयोग किया जाता है।


तुलना के लिए, क्लासिक टर्बो कोड आमतौर पर समानांतर में कॉन्फ़िगर किए गए दो घटक कोड का उपयोग करते हैं, जिनमें से प्रत्येक डेटा बिट्स के संपूर्ण इनपुट ब्लॉक (K) को एन्कोड करता है। ये घटक एनकोडर मध्यम गहराई (8 या 16 राज्यों) के पुनरावर्ती [[कन्वेन्शनल कोड]] (आरएससी) हैं जो एक कोड इंटरलीवर द्वारा अलग किए जाते हैं जो फ्रेम की एक प्रति को इंटरलीव करता है।
तुलना के लिए, क्लासिक टर्बो कोड समान्यत: समानांतर में कॉन्फ़िगर किए गए दो कांस्टीटुएंट कोड का उपयोग करते हैं, जिनमें से प्रत्येक डेटा बिट्स के संपूर्ण इनपुट ब्लॉक (K) को एन्कोड करता है। ये कांस्टीटुएंट एनकोडर मध्यम गहराई (8 या 16 स्थिति) के पुनरावर्ती [[कन्वेन्शनल कोड]] (आरएससी) हैं जो एक कोड इंटरलीवर द्वारा अलग किए जाते हैं जो फ्रेम की एक प्रति को इंटरलीव करता है।


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


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


व्यावहारिक बात के रूप में, संचायक बनाने वाले हार्डवेयर को एन्कोडिंग प्रक्रिया के दौरान पुन: उपयोग किया जाता है। अर्थात्, एक बार समता बिट्स का पहला सेट उत्पन्न हो जाता है और समता बिट्स संग्रहीत हो जाते हैं, उसी संचायक हार्डवेयर का उपयोग समता बिट्स का अगला सेट उत्पन्न करने के लिए किया जाता है।
व्यावहारिक रूप में, संचायक बनाने वाले हार्डवेयर को एन्कोडिंग प्रक्रिया के समय  पुन: उपयोग किया जाता है। अर्थात्, एक बार समता बिट्स का पहला सेट उत्पन्न हो जाता है और समता बिट्स संग्रहीत हो जाते हैं, उसी संचायक हार्डवेयर का उपयोग समता बिट्स का अगला सेट उत्पन्न करने के लिए किया जाता है।


==डिकोडिंग==
==डिकोडिंग==
अन्य कोडों की तरह, [[द्विआधारी सममित चैनल]] पर एलडीपीसी कोड की [[अधिकतम संभावना डिकोडिंग]] एक एनपी-पूर्ण समस्या है। किसी भी उपयोगी आकार के एनपी-पूर्ण कोड के लिए इष्टतम डिकोडिंग करना व्यावहारिक नहीं है।
अन्य कोडों की तरह, [[द्विआधारी सममित चैनल|बाइनरी सममित चैनल]] पर एलडीपीसी कोड की [[अधिकतम संभावना डिकोडिंग]] एक एनपी-पूर्ण समस्या है। किसी भी उपयोगी आकार के एनपी-पूर्ण कोड के लिए इष्टतम डिकोडिंग करना व्यावहारिक नहीं है।


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


एसपीसी कोड की डिकोडिंग को अक्सर चेक नोड प्रोसेसिंग के रूप में जाना जाता है, और वेरिएबल्स की क्रॉस-चेकिंग को अक्सर वेरिएबल-नोड प्रोसेसिंग के रूप में जाना जाता है।
एसपीसी कोड की डिकोडिंग को अधिकांशतः चेक नोड प्रोसेसिंग के रूप में जाना जाता है, और वेरिएबल्स की क्रॉस-चेकिंग को अधिकांशतः वेरिएबल-नोड प्रोसेसिंग के रूप में जाना जाता है।


व्यावहारिक एलडीपीसी डिकोडर कार्यान्वयन में, थ्रूपुट बढ़ाने के लिए एसपीसी कोड के सेट को समानांतर में डिकोड किया जाता है।
व्यावहारिक एलडीपीसी डिकोडर कार्यान्वयन में, थ्रूपुट बढ़ाने के लिए एसपीसी कोड के सेट को समानांतर में डिकोड किया जाता है।


इसके विपरीत, [[बाइनरी इरेज़र चैनल]] पर विश्वास का प्रसार विशेष रूप से सरल है जहां इसमें पुनरावृत्त बाधा संतुष्टि शामिल है।
इसके विपरीत, [[बाइनरी इरेज़र चैनल]] पर विश्वास का प्रसार विशेष रूप से सरल है जहां इसमें पुनरावृत्त बाधा संतुष्टि सम्मिलित है।


उदाहरण के लिए, मान लें कि उपरोक्त उदाहरण से मान्य कोडवर्ड, 101011, एक बाइनरी इरेज़र चैनल में प्रसारित होता है और ?01?11 प्राप्त करने के लिए पहले और चौथे बिट को मिटाकर प्राप्त किया जाता है। चूंकि प्रेषित संदेश को कोड की बाधाओं को पूरा करना होगा, इसलिए संदेश को कारक ग्राफ़ के शीर्ष पर प्राप्त संदेश लिखकर दर्शाया जा सकता है।
उदाहरण के लिए, मान लें कि उपरोक्त उदाहरण से मान्य कोडवर्ड, 101011, एक बाइनरी इरेज़र चैनल में प्रसारित होता है और ?01?11 प्राप्त करने के लिए पहले और चौथे बिट को मिटाकर प्राप्त किया जाता है। चूंकि प्रेषित संदेश को कोड की बाधाओं को पूरा करना होगा, इसलिए संदेश को कारक ग्राफ़ के शीर्ष पर प्राप्त संदेश लिखकर दर्शाया जा सकता है।
Line 151: Line 159:
इस उदाहरण में, पहला बिट अभी भी पुनर्प्राप्त नहीं किया जा सकता है, क्योंकि इससे जुड़े सभी अवरोधों में एक से अधिक अज्ञात बिट हैं। संदेश को डिकोड करने के लिए आगे बढ़ने के लिए, मिटाए गए बिट्स में से केवल एक से कनेक्ट होने वाली बाधाओं की पहचान की जानी चाहिए। इस उदाहरण में, केवल दूसरा अवरोध ही पर्याप्त है। दूसरे अवरोध की जांच करने पर, चौथा बिट शून्य रहा होगा, क्योंकि उस स्थिति में केवल एक शून्य ही अवरोध को संतुष्ट करेगा।
इस उदाहरण में, पहला बिट अभी भी पुनर्प्राप्त नहीं किया जा सकता है, क्योंकि इससे जुड़े सभी अवरोधों में एक से अधिक अज्ञात बिट हैं। संदेश को डिकोड करने के लिए आगे बढ़ने के लिए, मिटाए गए बिट्स में से केवल एक से कनेक्ट होने वाली बाधाओं की पहचान की जानी चाहिए। इस उदाहरण में, केवल दूसरा अवरोध ही पर्याप्त है। दूसरे अवरोध की जांच करने पर, चौथा बिट शून्य रहा होगा, क्योंकि उस स्थिति में केवल एक शून्य ही अवरोध को संतुष्ट करेगा।


फिर यह प्रक्रिया दोहराई जाती है. चौथे बिट के लिए नया मान अब पहले बिट को पुनर्प्राप्त करने के लिए पहले बाधा के साथ संयोजन में उपयोग किया जा सकता है जैसा कि नीचे देखा गया है। इसका मतलब यह है कि पहला बिट सबसे बाईं ओर की बाधा को पूरा करने वाला होना चाहिए।
फिर यह प्रक्रिया दोहराई जाती है चौथे बिट के लिए नया मान अब पहले बिट को पुनर्प्राप्त करने के लिए पहले बाधा के साथ संयोजन में उपयोग किया जा सकता है जैसा कि नीचे देखा गया है। इसका अर्थ यह है कि पहला बिट सबसे बाईं ओर की बाधा को पूरा करने वाला होना चाहिए।


[[Image:ldpc code fragment factor graph w erasures decode step 2.svg|none]]इस प्रकार, संदेश को पुनरावृत्त रूप से डिकोड किया जा सकता है। अन्य चैनल मॉडल के लिए, वेरिएबल नोड्स और चेक नोड्स के बीच पारित संदेश [[वास्तविक संख्या]]एं हैं, जो विश्वास की संभावनाओं और संभावनाओं को व्यक्त करते हैं।
[[Image:ldpc code fragment factor graph w erasures decode step 2.svg|none]]इस प्रकार, संदेश को पुनरावृत्त रूप से डिकोड किया जा सकता है। अन्य चैनल मॉडल के लिए, वेरिएबल नोड्स और चेक नोड्स के बीच पारित संदेश [[वास्तविक संख्या]]एं हैं, जो विश्वास की संभावनाओं और संभावनाओं को व्यक्त करते हैं।


इस परिणाम को समता-जांच मैट्रिक्स एच द्वारा सही कोडवर्ड आर को गुणा करके मान्य किया जा सकता है:
इस परिणाम को समता-जांच आव्यूह '''H''' द्वारा सही कोडवर्ड '''r''' को गुणा करके मान्य किया जा सकता है:


:<math>\mathbf{z} = \mathbf{H \odot r}
:<math>\mathbf{z} = \mathbf{H \odot r}
Line 174: Line 182:
\end{pmatrix}.
\end{pmatrix}.
</math>
</math>
चूँकि इस ऑपरेशन का परिणाम z (डिकोडिंग विधियाँ#सिंड्रोम डिकोडिंग) तीन × एक शून्य वेक्टर है, परिणामी कोडवर्ड r सफलतापूर्वक मान्य है।
चूँकि इस ऑपरेशन का परिणाम z (डिकोडिंग विधियाँ या सिंड्रोम डिकोडिंग) तीन × एक शून्य वेक्टर है, परिणामी कोडवर्ड r सफलतापूर्वक मान्य है।


डिकोडिंग पूरी होने के बाद, कोडवर्ड के पहले 3 बिट्स को देखकर मूल संदेश बिट्स '101' निकाला जा सकता है।
डिकोडिंग पूरी होने के बाद, कोडवर्ड के पहले 3 बिट्स को देखकर मूल संदेश बिट्स '101' निकाला जा सकता है।
Line 180: Line 188:
उदाहरणात्मक होते हुए भी, यह इरेज़र उदाहरण सॉफ्ट-डिसीजन डिकोडिंग या सॉफ्ट-डिसीजन संदेश पासिंग का उपयोग नहीं दिखाता है, जिसका उपयोग लगभग सभी वाणिज्यिक एलडीपीसी डिकोडर्स में किया जाता है।
उदाहरणात्मक होते हुए भी, यह इरेज़र उदाहरण सॉफ्ट-डिसीजन डिकोडिंग या सॉफ्ट-डिसीजन संदेश पासिंग का उपयोग नहीं दिखाता है, जिसका उपयोग लगभग सभी वाणिज्यिक एलडीपीसी डिकोडर्स में किया जाता है।


=== नोड जानकारी अद्यतन करना ===
=== नोड जानकारी अपडेट करना ===
हाल के वर्षों में, वैरिएबल-नोड और बाधा-नोड अद्यतन के लिए वैकल्पिक शेड्यूल के प्रभावों का अध्ययन करने में भी काफी काम किया गया है। एलडीपीसी कोड को डिकोड करने के लिए जिस मूल तकनीक का उपयोग किया गया था उसे बाढ़ के रूप में जाना जाता था। इस प्रकार के अद्यतन के लिए आवश्यक है कि, एक चर नोड को अद्यतन करने से पहले, सभी बाधा नोड्स को अद्यतन करने की आवश्यकता हो और इसके विपरीत। विला कैसाडो एट अल द्वारा बाद के काम में,<ref name=Vila07>A.I. Vila Casado, M. Griot, and R.Wesel, "Informed dynamic scheduling for belief propagation decoding of LDPC codes," Proc. [[IEEE]] Int. Conf. on Comm. (ICC), June 2007.</ref> वैकल्पिक अद्यतन तकनीकों का अध्ययन किया गया, जिसमें परिवर्तनीय नोड्स को नवीनतम उपलब्ध चेक-नोड जानकारी के साथ अद्यतन किया जाता है।
वर्तमान के वर्षों में, वैरिएबल-नोड और बाधा-नोड अपडेट के लिए वैकल्पिक शेड्यूल के प्रभावों का अध्ययन करने में भी अधिक काम किया गया है। एलडीपीसी कोड को डिकोड करने के लिए जिस मूल तकनीक का उपयोग किया गया था उसे बाढ़ के रूप में जाना जाता था। इस प्रकार के अपडेट के लिए आवश्यक है कि, एक चर नोड को अपडेट करने से पहले, सभी बाधा नोड्स को अपडेट करने की आवश्यकता हो और इसके विपरीत विला कैसाडो एट अल द्वारा बाद के काम में,<ref name=Vila07>A.I. Vila Casado, M. Griot, and R.Wesel, "Informed dynamic scheduling for belief propagation decoding of LDPC codes," Proc. [[IEEE]] Int. Conf. on Comm. (ICC), June 2007.</ref> वैकल्पिक अपडेट तकनीकों का अध्ययन किया गया, जिसमें परिवर्तनीय नोड्स को नवीनतम उपलब्ध चेक-नोड जानकारी के साथ अपडेट किया जाता है।
 
इन एल्गोरिदम के पीछे अंतर्ज्ञान यह है कि वेरिएबल नोड्स जिनके मान सबसे अधिक भिन्न होते हैं, उन्हें पहले अपडेट करने की आवश्यकता होती है। अत्यधिक विश्वसनीय नोड्स, जिनका [[लॉग-संभावना अनुपात]] (एलएलआर) परिमाण बड़ा है और एक अपडेट से दूसरे अपडेट में महत्वपूर्ण रूप से नहीं बदलता है, उन्हें अन्य नोड्स के समान आवृत्ति के साथ अपडेट की आवश्यकता नहीं होती है, जिनके संकेत और परिमाण में अधिक व्यापक रूप से उतार-चढ़ाव होता है।


इन एल्गोरिदम के पीछे अंतर्ज्ञान यह है कि वेरिएबल नोड्स जिनके मान सबसे अधिक भिन्न होते हैं, उन्हें पहले अद्यतन करने की आवश्यकता होती है। अत्यधिक विश्वसनीय नोड्स, जिनका [[लॉग-संभावना अनुपात]] (एलएलआर) परिमाण बड़ा है और एक अपडेट से दूसरे अपडेट में महत्वपूर्ण रूप से नहीं बदलता है, उन्हें अन्य नोड्स के समान आवृत्ति के साथ अपडेट की आवश्यकता नहीं होती है, जिनके संकेत और परिमाण में अधिक व्यापक रूप से उतार-चढ़ाव होता है।
ये शेड्यूलिंग एल्गोरिदम बाढ़ का उपयोग करने वाले एल्गोरिदम की तुलना में अभिसरण की अधिक गति और कम त्रुटि वाले फर्श दिखाते हैं। ये निचली त्रुटि मंजिलें सूचित गतिशील शेड्यूलिंग (आईडीएस) की क्षमता से हासिल की जाती हैं<ref name="Vila07" /> निकट कोडवर्ड के अधिकृत करने वाले सेटों पर नियंत्रण पाने के लिए एल्गोरिदम है ।<ref name="Richardson03">T. Richardson, "Error floors of LDPC codes," in Proc. 41st Allerton Conf. Comm., Control, and Comput., Monticello, IL, 2003.</ref>
ये शेड्यूलिंग एल्गोरिदम बाढ़ का उपयोग करने वाले एल्गोरिदम की तुलना में अभिसरण की अधिक गति और कम त्रुटि वाले फर्श दिखाते हैं। ये निचली त्रुटि मंजिलें सूचित गतिशील शेड्यूलिंग (आईडीएस) की क्षमता से हासिल की जाती हैं<ref name=Vila07/>निकट कोडवर्ड के फँसाने वाले सेटों पर काबू पाने के लिए एल्गोरिदम।<ref name=Richardson03>T. Richardson, "Error floors of LDPC codes," in Proc. 41st Allerton Conf. Comm., Control, and Comput., Monticello, IL, 2003.</ref>
 
जब गैर-बाढ़ शेड्यूलिंग एल्गोरिदम का उपयोग किया जाता है, तो पुनरावृत्ति की एक वैकल्पिक परिभाषा का उपयोग किया जाता है। दर k/n के (n,k) LDPC कोड के लिए, एक पूर्ण पुनरावृत्ति तब होती है जब n चर और n − k बाधा नोड्स को अद्यतन किया गया है, इससे कोई फर्क नहीं पड़ता कि वे किस क्रम में अद्यतन किए गए थे।
जब गैर-फ्शेलूडिंग ड्यूलिंग एल्गोरिदम का उपयोग किया जाता है, तो पुनरावृत्ति की एक वैकल्पिक परिभाषा का उपयोग किया जाता है। दर k/n के (n,k) एलडीपीसी कोड के लिए, एक पूर्ण पुनरावृत्ति तब होती है जब n चर और n − k बाधा नोड्स को अपडेट किया गया है, इससे कोई ​अंतर नहीं पड़ता कि वे किस क्रम में अपडेट किए गए थे।


== कोड निर्माण ==
== कोड निर्माण ==
बड़े ब्लॉक आकारों के लिए, एलडीपीसी कोड आमतौर पर पहले डिकोडर्स के व्यवहार का अध्ययन करके बनाए जाते हैं। चूंकि ब्लॉक का आकार अनंत तक जाता है, एलडीपीसी डिकोडर्स को एक शोर सीमा दिखाई जा सकती है जिसके नीचे डिकोडिंग विश्वसनीय रूप से हासिल की जाती है, और जिसके ऊपर डिकोडिंग हासिल नहीं की जाती है,<ref name=richardson01>Thomas J. Richardson and M. Amin Shokrollahi and Rüdiger L. Urbanke, "Design of Capacity-Approaching Irregular Low-Density Parity-Check Codes," IEEE Transactions on  Information Theory, 47(2), February 2001</ref> बोलचाल की भाषा में इसे चट्टान प्रभाव कहा जाता है। इस सीमा को चेक नोड्स से आर्क और वेरिएबल नोड्स से आर्क का सर्वोत्तम अनुपात ढूंढकर अनुकूलित किया जा सकता है। इस सीमा को देखने के लिए एक अनुमानित ग्राफिकल दृष्टिकोण एक EXIT चार्ट है।
बड़े ब्लॉक आकारों के लिए, एलडीपीसी कोड समान्यत: पहले डिकोडर्स के व्यवहार का अध्ययन करके बनाए जाते हैं। चूंकि ब्लॉक का आकार अनंत तक जाता है, एलडीपीसी डिकोडर्स को एक ध्वनि सीमा दिखाई जा सकती है जिसके नीचे डिकोडिंग विश्वसनीय रूप से प्राप्त की जाती है, और जिसके ऊपर डिकोडिंग प्राप्त नहीं की जाती है,<ref name=richardson01>Thomas J. Richardson and M. Amin Shokrollahi and Rüdiger L. Urbanke, "Design of Capacity-Approaching Irregular Low-Density Parity-Check Codes," IEEE Transactions on  Information Theory, 47(2), February 2001</ref> बोलचाल की भाषा में इसे क्लिफ इफ़ेक्ट कहा जाता है। इस सीमा को चेक नोड्स से आर्क और वेरिएबल नोड्स से आर्क का सर्वोत्तम अनुपात खोजकर अनुकूलित किया जा सकता है। इस सीमा को देखने के लिए एक अनुमानित ग्राफिकल दृष्टिकोण एक EXIT चार्ट है।


इस अनुकूलन के बाद एक विशिष्ट एलडीपीसी कोड का निर्माण दो मुख्य प्रकार की तकनीकों में आता है:
इस अनुकूलन के बाद एक विशिष्ट एलडीपीसी कोड का निर्माण दो मुख्य प्रकार की तकनीकों में आता है:
Line 195: Line 205:
*संयुक्त दृष्टिकोण
*संयुक्त दृष्टिकोण


छद्म-यादृच्छिक दृष्टिकोण द्वारा निर्माण सैद्धांतिक परिणामों पर आधारित होता है, जो बड़े ब्लॉक आकार के लिए, एक यादृच्छिक निर्माण अच्छा डिकोडिंग प्रदर्शन देता है।<ref name=MacKay96/>सामान्य तौर पर, छद्म यादृच्छिक कोड में जटिल एनकोडर होते हैं, लेकिन सर्वोत्तम डिकोडर वाले छद्म यादृच्छिक कोड में सरल एनकोडर हो सकते हैं।<ref name=richardson01b>Thomas J. Richardson and Rüdiger L. Urbanke, "Efficient Encoding of Low-Density Parity-Check Codes," IEEE Transactions on  Information Theory, 47(2), February 2001</ref> यह सुनिश्चित करने में सहायता के लिए अक्सर विभिन्न बाधाएं लागू की जाती हैं कि अनंत ब्लॉक आकार की सैद्धांतिक सीमा पर अपेक्षित वांछित गुण एक सीमित ब्लॉक आकार पर होते हैं।
छद्म-यादृच्छिक दृष्टिकोण द्वारा निर्माण सैद्धांतिक परिणामों पर आधारित होता है, जो बड़े ब्लॉक आकार के लिए, एक यादृच्छिक निर्माण अच्छा डिकोडिंग प्रदर्शन देता है।<ref name=MacKay96/> सामान्य रूप से, छद्म यादृच्छिक कोड में काम्प्लेक्स एनकोडर होते हैं, किंतु सर्वोत्तम डिकोडर वाले छद्म यादृच्छिक कोड में सरल एनकोडर हो सकते हैं।<ref name=richardson01b>Thomas J. Richardson and Rüdiger L. Urbanke, "Efficient Encoding of Low-Density Parity-Check Codes," IEEE Transactions on  Information Theory, 47(2), February 2001</ref> यह सुनिश्चित करने में सहायता के लिए अधिकांशतः विभिन्न बाधाएं प्रयुक्त की जाती हैं कि अनंत ब्लॉक आकार की सैद्धांतिक सीमा पर अपेक्षित वांछित गुण एक सीमित ब्लॉक आकार पर होते हैं।


कॉम्बिनेटोरियल दृष्टिकोण का उपयोग छोटे ब्लॉक-आकार के एलडीपीसी कोड के गुणों को अनुकूलित करने या सरल एनकोडर के साथ कोड बनाने के लिए किया जा सकता है।
कॉम्बिनेटोरियल दृष्टिकोण का उपयोग छोटे ब्लॉक-आकार के एलडीपीसी कोड के गुणों को अनुकूलित करने या सरल एनकोडर के साथ कोड बनाने के लिए किया जा सकता है।


कुछ एलडीपीसी कोड रीड-सोलोमन कोड पर आधारित होते हैं, जैसे [[10 गीगाबिट ईथरनेट]] मानक में उपयोग किया जाने वाला आरएस-एलडीपीसी कोड।<ref>
कुछ एलडीपीसी कोड रीड-सोलोमन कोड पर आधारित होते हैं, जैसे [[10 गीगाबिट ईथरनेट]] मानक में उपयोग किया जाने वाला आरएस-एलडीपीसी कोड<ref>
Ahmad Darabiha, Anthony Chan Carusone, Frank R. Kschischang.
Ahmad Darabiha, Anthony Chan Carusone, Frank R. Kschischang.
[http://www.eecg.toronto.edu/~tcc/darabiha_jssc08.pdf "Power Reduction Techniques for LDPC Decoders"]
[http://www.eecg.toronto.edu/~tcc/darabiha_jssc08.pdf "Power Reduction Techniques for LDPC Decoders"]
</ref> बेतरतीब ढंग से उत्पन्न एलडीपीसी कोड की तुलना में, संरचित एलडीपीसी कोड - जैसे कि डीवीबी-एस 2 मानक में प्रयुक्त एलडीपीसी कोड - में सरल और इसलिए कम लागत वाले हार्डवेयर हो सकते हैं - विशेष रूप से, कोड ऐसे निर्मित होते हैं कि एच मैट्रिक्स एक [[मैट्रिक्स का चक्कर लगाना]] है।<ref>
</ref> व्यवस्थित रूप  से उत्पन्न एलडीपीसी कोड की तुलना में, संरचित एलडीपीसी कोड - जैसे कि डीवीबी-एस 2 मानक में प्रयुक्त एलडीपीसी कोड - में सरल और इसलिए कम निवेश वाले हार्डवेयर हो सकते हैं - विशेष रूप से, कोड ऐसे निर्मित होते हैं कि एच आव्यूह एक [[मैट्रिक्स का चक्कर लगाना|आव्यूह सर्कुलर आव्यूह]] है।<ref>
Zhengya Zhang, Venkat Anantharam, Martin J. Wainwright, and Borivoje Nikolic.
Zhengya Zhang, Venkat Anantharam, Martin J. Wainwright, and Borivoje Nikolic.
[https://web.eecs.umich.edu/~zhengya/papers/jssc10_05437474.pdf "An Efficient 10GBASE-T Ethernet LDPC Decoder Design With Low Error Floors"].
[https://web.eecs.umich.edu/~zhengya/papers/jssc10_05437474.pdf "An Efficient 10GBASE-T Ethernet LDPC Decoder Design With Low Error Floors"].
</ref>
</ref>
एलडीपीसी कोड बनाने का एक अन्य तरीका [[परिमित ज्यामिति]] का उपयोग करना है। यह विधि वाई. कोउ एट अल द्वारा प्रस्तावित की गई थी। 2001 में।<ref name=Kou1>Y. Kou, S. Lin and M. Fossorier, "Low-Density Parity-Check Codes
 
एलडीपीसी कोड बनाने का एक अन्य विधि परिमित ज्यामिति का उपयोग करना है। यह विधि 2001 में वाई. कोउ एट अल द्वारा प्रस्तावित की गई थी।<ref name="Kou1">Y. Kou, S. Lin and M. Fossorier, "Low-Density Parity-Check Codes
Based on Finite Geometries: A Rediscovery and New Results," IEEE
Based on Finite Geometries: A Rediscovery and New Results," IEEE
Transactions on Information Theory, vol. 47, no. 7, November 2001, pp. 2711-
Transactions on Information Theory, vol. 47, no. 7, November 2001, pp. 2711-
Line 214: Line 225:
== एलडीपीसी कोड बनाम टर्बो कोड ==
== एलडीपीसी कोड बनाम टर्बो कोड ==


एलडीपीसी कोड की तुलना अन्य शक्तिशाली कोडिंग योजनाओं से की जा सकती है, जैसे टर्बो कोड.<ref>Tahir, B., Schwarz, S., & Rupp, M. (2017, May). BER comparison between Convolutional, Turbo, LDPC, and Polar codes. In 2017 24th International Conference on Telecommunications (ICT) (pp. 1-7). IEEE.</ref> एक ओर, टर्बो कोड की बिट त्रुटि दर प्रदर्शन कम कोड सीमाओं से प्रभावित होती है।<ref>Moon Todd, K. Error correction coding: mathematical methods and algorithms. 2005 by John Wiley & Sons. {{ISBN|0-471-64800-0}}. - p.614</ref> एलडीपीसी कोड में न्यूनतम दूरी की कोई सीमा नहीं है,<ref>Moon Todd, K. Error correction coding: mathematical methods and algorithms. 2005 by John Wiley & Sons. {{ISBN|0-471-64800-0}}. - p.653</ref> इसका अप्रत्यक्ष अर्थ यह है कि एलडीपीसी कोड टर्बो कोड की तुलना में अपेक्षाकृत बड़ी कोड दरों (जैसे 3/4, 5/6, 7/8) पर अधिक कुशल हो सकते हैं। हालाँकि, एलडीपीसी कोड पूर्ण प्रतिस्थापन नहीं हैं: टर्बो कोड कम कोड दरों (जैसे 1/6, 1/3, 1/2) पर सबसे अच्छा समाधान हैं।<ref>Andrews, Kenneth S., et al. "The development of turbo and LDPC codes for deep-space applications." Proceedings of the IEEE 95.11 (2007): 2142-2156.</ref><ref>Hassan, A.E.S., Dessouky, M., Abou Elazm, A. and Shokair, M., 2012. [https://www.researchgate.net/profile/Mona_Shokair/publication/234051399_Evaluation_of_Complexity_Versus_Performance_for_Turbo_Code_and_LDPC_Under_Different_Code_Rates/links/56b7b68908ae44bb330bc82f.pdf Evaluation of complexity versus performance for turbo code and LDPC under different code rates]. Proc. SPACOMM, pp.93-98.</ref>
एलडीपीसी कोड की तुलना अन्य शक्तिशाली कोडिंग योजनाओं से की जा सकती है, जैसे टर्बो कोड.<ref>Tahir, B., Schwarz, S., & Rupp, M. (2017, May). BER comparison between Convolutional, Turbo, LDPC, and Polar codes. In 2017 24th International Conference on Telecommunications (ICT) (pp. 1-7). IEEE.</ref> एक ओर, टर्बो कोड की बिट त्रुटि दर प्रदर्शन कम कोड सीमाओं से प्रभावित होती है।<ref>Moon Todd, K. Error correction coding: mathematical methods and algorithms. 2005 by John Wiley & Sons. {{ISBN|0-471-64800-0}}. - p.614</ref> एलडीपीसी कोड में न्यूनतम दूरी की कोई सीमा नहीं है,<ref>Moon Todd, K. Error correction coding: mathematical methods and algorithms. 2005 by John Wiley & Sons. {{ISBN|0-471-64800-0}}. - p.653</ref> इसका अप्रत्यक्ष अर्थ यह है कि एलडीपीसी कोड टर्बो कोड की तुलना में अपेक्षाकृत बड़ी कोड दरों (जैसे 3/4, 5/6, 7/8) पर अधिक कुशल हो सकते हैं। चूँकि एलडीपीसी कोड पूर्ण प्रतिस्थापन नहीं हैं: टर्बो कोड कम कोड दरों (जैसे 1/6, 1/3, 1/2) पर सबसे अच्छा समाधान हैं।<ref>Andrews, Kenneth S., et al. "The development of turbo and LDPC codes for deep-space applications." Proceedings of the IEEE 95.11 (2007): 2142-2156.</ref><ref>Hassan, A.E.S., Dessouky, M., Abou Elazm, A. and Shokair, M., 2012. [https://www.researchgate.net/profile/Mona_Shokair/publication/234051399_Evaluation_of_Complexity_Versus_Performance_for_Turbo_Code_and_LDPC_Under_Different_Code_Rates/links/56b7b68908ae44bb330bc82f.pdf Evaluation of complexity versus performance for turbo code and LDPC under different code rates]. Proc. SPACOMM, pp.93-98.</ref>




Line 234: Line 245:
=== अनुप्रयोग ===
=== अनुप्रयोग ===


*जी.एचएन|जी.एचएन/जी.9960 (बिजली लाइनों, फोन लाइनों और समाक्षीय केबल पर नेटवर्किंग के लिए आईटीयू-टी मानक)
*जी.एचएन या जी.एचएन/जी.9960 (बिजली लाइनों, फोन लाइनों और समाक्षीय केबल पर नेटवर्किंग के लिए आईटीयू-टी मानक)
*802.3an या 10GBASE-T (ट्विस्टेड पेयर पर 10 गीगाबिट/सेकेंड ईथरनेट)
*802.3an या 10GBASE-T (ट्विस्टेड पेयर पर 10 गीगाबिट/सेकेंड ईथरनेट)
*[[सीएमएमबी]] (चीन मल्टीमीडिया मोबाइल ब्रॉडकास्टिंग)
*[[सीएमएमबी]] (चीन मल्टीमीडिया मोबाइल ब्रॉडकास्टिंग)
*DVB-S2 / [[DVB-T2]] / [[DVB-C2]] (डिजिटल वीडियो प्रसारण, दूसरी पीढ़ी)
*डीवीबी-S2 / [[DVB-T2|डीवीबी-T2]] / [[DVB-C2|डीवीबी-C2]] (डिजिटल वीडियो प्रसारण, दूसरी पीढ़ी)
*डीएमबी-टी/एच (डिजिटल वीडियो प्रसारण)<ref>{{cite web |url=https://spectrum.ieee.org/consumer-electronics/standards/does-china-have-the-best-digital-television-standard-on-the-planet/2 |title=IEEE Spectrum: Does China Have the Best Digital Television Standard on the Planet? |website=spectrum.ieee.org |url-status=dead |archive-url=https://web.archive.org/web/20091212140917/http://spectrum.ieee.org/consumer-electronics/standards/does-china-have-the-best-digital-television-standard-on-the-planet/2 |archive-date=2009-12-12}} </ref>
*डीएमबी-टी/एच (डिजिटल वीडियो प्रसारण)<ref>{{cite web |url=https://spectrum.ieee.org/consumer-electronics/standards/does-china-have-the-best-digital-television-standard-on-the-planet/2 |title=IEEE Spectrum: Does China Have the Best Digital Television Standard on the Planet? |website=spectrum.ieee.org |url-status=dead |archive-url=https://web.archive.org/web/20091212140917/http://spectrum.ieee.org/consumer-electronics/standards/does-china-have-the-best-digital-television-standard-on-the-planet/2 |archive-date=2009-12-12}} </ref>
*[[वाइमैक्स]] (माइक्रोवेव संचार के लिए IEEE 802.16e मानक)
*[[वाइमैक्स]] (माइक्रोवेव संचार के लिए आईईईई 802.16e मानक)
* IEEE 802.11n-2009 (वाई-फ़ाई मानक)
* आईईईई 802.11n-2009 (वाई-फ़ाई मानक)
*[[डॉक्सिस]] 3.1
*[[डॉक्सिस]] 3.1
*एटीएससी 3.0 (अगली पीढ़ी उत्तरी अमेरिका डिजिटल स्थलीय प्रसारण)
*एटीएससी 3.0 (अगली पीढ़ी उत्तरी अमेरिका डिजिटल स्थलीय प्रसारण)
Line 262: Line 273:
== बाहरी संबंध ==
== बाहरी संबंध ==
* [http://sigpromu.org/sarah/SJohnsonLDPCintro.pdf Introducing Low-Density Parity-Check Codes (by Sarah J Johnson, 2010)]
* [http://sigpromu.org/sarah/SJohnsonLDPCintro.pdf Introducing Low-Density Parity-Check Codes (by Sarah J Johnson, 2010)]
* [http://bernh.net/media/download/papers/ldpc.pdf LDPC Codes – a brief Tutorial (by Bernhard Leiner, 2005)]
* [http://bernh.net/media/download/papers/ldpc.pdf एलडीपीसी Codes – a brief Tutorial (by Bernhard Leiner, 2005)]
* [https://www.nt.tuwien.ac.at/wp-content/uploads/2016/10/DC2-16_Ch7_LDPC.pdf LDPC Codes (TU Wien)] {{Webarchive|url=https://web.archive.org/web/20190228003946/https://www.nt.tuwien.ac.at/wp-content/uploads/2016/10/DC2-16_Ch7_LDPC.pdf |date=February 28, 2019 }}
* [https://www.nt.tuwien.ac.at/wp-content/uploads/2016/10/DC2-16_Ch7_LDPC.pdf एलडीपीसी Codes (TU Wien)] {{Webarchive|url=https://web.archive.org/web/20190228003946/https://www.nt.tuwien.ac.at/wp-content/uploads/2016/10/DC2-16_Ch7_LDPC.pdf |date=February 28, 2019 }}
* [http://www.inference.phy.cam.ac.uk/mackay/itila/ The on-line textbook: Information Theory, Inference, and Learning Algorithms], by [[David J.C. MacKay]], discusses LDPC codes in Chapter 47.
* [http://www.inference.phy.cam.ac.uk/mackay/itila/ The on-line textbook: Information Theory, Inference, and Learning Algorithms], by [[David J.C. MacKay]], discusses एलडीपीसी codes in Chapter 47.
* [https://arxiv.org/abs/cs/0610022 Iterative Decoding of Low-Density Parity Check Codes (by Venkatesan Guruswami, 2006)]
* [https://arxiv.org/abs/cs/0610022 Iterative Decoding of Low-Density Parity Check Codes (by Venkatesan Guruswami, 2006)]
* [http://www.ics.uci.edu/~welling/teaching/ICS279/LPCD.pdf LDPC Codes: An Introduction (by Amin Shokrollahi, 2003)]
* [http://www.ics.uci.edu/~welling/teaching/ICS279/LPCD.pdf एलडीपीसी Codes: An Introduction (by Amin Shokrollahi, 2003)]
* [http://www.tsc.uc3m.es/~fernando/BP_LDPC.pdf Belief-Propagation Decoding of LDPC Codes (by Amir Bennatan, Princeton University)]
* [http://www.tsc.uc3m.es/~fernando/BP_LDPC.pdf Belief-Propagation Decoding of एलडीपीसी Codes (by Amir Bennatan, Princeton University)]
* [http://community.wvu.edu/~mcvalenti/documents/TurboLDPCTutorial.pdf Turbo and LDPC Codes: Implementation, Simulation, and Standardization (West Virginia University)]
* [http://community.wvu.edu/~mcvalenti/documents/TurboLDPCTutorial.pdf Turbo and एलडीपीसी Codes: Implementation, Simulation, and Standardization (West Virginia University)]
* [http://www5.tu-ilmenau.de/nt/de/teachings/vorlesungen/itsc_master/folien/script.pdf Information theory and coding (Marko Hennhöfer, 2011, TU Ilmenau)] - discusses LDPC codes at pages 74–78.
* [http://www5.tu-ilmenau.de/nt/de/teachings/vorlesungen/itsc_master/folien/script.pdf Information theory and coding (Marko Hennhöfer, 2011, TU Ilmenau)] - discusses एलडीपीसी codes at pages 74–78.
* [http://www.inference.phy.cam.ac.uk/mackay/CodesFiles.html LDPC codes and performance results]
* [http://www.inference.phy.cam.ac.uk/mackay/CodesFiles.html एलडीपीसी codes and performance results]
* [https://www.mathworks.com/help/comm/examples/dvb-s-2-link-including-ldpc-coding.html?s_tid=srchtitle DVB-S.2 Link, Including LDPC Coding (MatLab)]
* [https://www.mathworks.com/help/comm/examples/dvb-s-2-link-including-ldpc-coding.html?s_tid=srchtitle डीवीबी-S.2 Link, Including एलडीपीसी Coding (MatLab)]
*Source code for encoding, decoding, and simulating LDPC codes is available from a variety of locations:
*Source code for encoding, decoding, and simulating एलडीपीसी codes is available from a variety of locations:
** [http://www.cs.utoronto.ca/~radford/ldpc.software.html Binary LDPC codes] in [[C (programming language)|C]]
** [http://www.cs.utoronto.ca/~radford/ldpc.software.html Binary एलडीपीसी codes] in [[C (programming language)|C]]
** [http://freshmeat.net/projects/pycodes/ Binary LDPC codes] for [[Python (programming language)|Python]] (core algorithm in C)
** [http://freshmeat.net/projects/pycodes/ Binary एलडीपीसी codes] for [[Python (programming language)|Python]] (core algorithm in C)
** [https://web.archive.org/web/20090926035703/http://www.mathworks.com/access/helpdesk/help/toolbox/comm/ref/fec.ldpcenc.html LDPC encoder] and [https://web.archive.org/web/20090217170744/http://www.mathworks.com/access/helpdesk/help/toolbox/comm/ref/fec.ldpcdec.html LDPC decoder] in [[MATLAB]]
** [https://web.archive.org/web/20090926035703/http://www.mathworks.com/access/helpdesk/help/toolbox/comm/ref/fec.ldpcenc.html एलडीपीसी encoder] and [https://web.archive.org/web/20090217170744/http://www.mathworks.com/access/helpdesk/help/toolbox/comm/ref/fec.ldpcdec.html एलडीपीसी decoder] in [[MATLAB]]
** [https://aff3ct.github.io A Fast Forward Error Correction Toolbox] (AFF3CT) in [[C++11]] for fast LDPC simulations
** [https://aff3ct.github.io A Fast Forward Error Correction Toolbox] (AFF3CT) in [[C++11]] for fast एलडीपीसी simulations


{{DEFAULTSORT:Low-Density Parity-Check Code}}[[Category: त्रुटि का पता लगाना और सुधार करना]] [[Category: कोडिंग सिद्धांत]] [[Category: क्षमता-अनुरूप कोड]]  
{{DEFAULTSORT:Low-Density Parity-Check Code}}[[Category: त्रुटि का पता लगाना और सुधार करना]] [[Category: कोडिंग सिद्धांत]] [[Category: क्षमता-अनुरूप कोड]]  

Revision as of 12:12, 31 July 2023


सूचना सिद्धांत में, कम-घनत्व समता-जांच (एलडीपीसी) कोड एक रैखिक त्रुटि सुधार कोड है, जो एक ध्वनि संचरण चैनल पर एक संदेश प्रसारित करने की एक विधि है [1][2] एक एलडीपीसी कोड एक विरल टान्नर ग्राफ (द्विपक्षीय ग्राफ का उपवर्ग) का उपयोग करके बनाया गया है।[3] एलडीपीसी कोड हैं:श्रेणी:क्षमता-अनुमोदन कोड|क्षमता-अनुमोदन कोड, जिसका अर्थ है कि व्यावहारिक निर्माण उपस्थित हैं जो एक सममित मेमोरी लेस चैनल के लिए ध्वनि सीमा को सैद्धांतिक अधिकतम (शैनन-हार्टले प्रमेय) के बहुत समीप सेट करने की अनुमति देते हैं। ध्वनि सीमा चैनल ध्वनि के लिए ऊपरी सीमा को परिभाषित करती है, जहां तक ​​खोई हुई जानकारी की संभावना को इच्छानुसार छोटा किया जा सकता है। पुनरावृत्तीय विश्वास प्रसार तकनीकों का उपयोग करके, एलडीपीसी कोड को उनकी ब्लॉक लंबाई के रैखिक समय में डिकोड किया जा सकता है।

व्यर्थ ध्वनि की उपस्थिति में बैंडविड्थ-बाधित या रिटर्न-चैनल-बाधित लिंक पर विश्वसनीय और अत्यधिक कुशल सूचना हस्तांतरण की आवश्यकता वाले एप्लीकेशन में एलडीपीसी कोड का उपयोग बढ़ रहा है। एलडीपीसी कोड का कार्यान्वयन अन्य कोड, विशेषकर टर्बो कोड से पिछड़ गया है। टर्बो कोड के लिए मौलिक पेटेंट 29 अगस्त 2013 को समाप्त हो गया।[4][5]

एलडीपीसी कोड को रॉबर्ट जी गैलगर के सम्मान में गैलगर कोड के रूप में भी जाना जाता है, जिन्होंने 1960 में मैसाचुसेट्स की तकनीकी संस्था में अपने डॉक्टरेट शोध प्रबंध में एलडीपीसी अवधारणा विकसित की थी।[6][7] एलडीपीसी कोड में आदर्श संयोजन गुण भी दिखाए गए हैं। अपने शोध प्रबंध में, गैलागर ने दिखाया कि एलडीपीसी कोड उच्च संभावना वाले बाइनरी क्षेत्रों पर रैखिक कोड के लिए बाध्य गिल्बर्ट-वार्शमोव को प्राप्त करते हैं। 2020 में यह दिखाया गया कि गैलेजर के एलडीपीसी कोड सूची डिकोडिंग क्षमता प्राप्त करते हैं और सामान्य क्षेत्रों पर रैखिक कोड के लिए बाध्य गिल्बर्ट-वार्शमोव भी प्राप्त करते हैं। [8]


इतिहास

1963 में रॉबर्ट जी. गैलागर द्वारा पहली बार विकसित होने पर इसे प्रयुक्त करना अव्यावहारिक था।[9] 1996 में उनका काम दोबारा खोजे जाने तक एलडीपीसी कोड भुला दिए गए थे।[10] टर्बो कोड, 1993 में खोजे गए क्षमता-अनुरूप कोड का एक और वर्ग, 1990 के दशक के अंत में पसंद की कोडिंग योजना बन गया, जिसका उपयोग डीप स्पेस नेटवर्क और उपग्रह संचार जैसे एप्लीकेशन के लिए किया जाता था। चूँकि, कम-घनत्व समता-जाँच कोड में प्रगति ने उन्हें त्रुटि स्तर और उच्च कोड दर सीमा में प्रदर्शन के स्थिति में टर्बो कोड से आगे निकलते देखा है, जिससे टर्बो कोड केवल कम कोड दरों के लिए उत्तम अनुकूल हो गए हैं।[11]


एप्लीकेशन

2003 में, एक रिपीट-एक्युमुलेट कोड या इररेगुलर रिपीट एक्युमुलेट कोड्स (आईआरए) स्टाइल एलडीपीसी कोड छह टर्बो कोड को पराजित करके डिजिटल टेलीविजन के लिए नए डीवीबी-एस 2 मानक में त्रुटि-सुधार करने वाला कोड बन गया।[12] डीवीबी-S2 चयन समिति ने समानांतर डिकोडर आर्किटेक्चर के अतिरिक्त बहुत कम कुशल सीरियल डिकोडर आर्किटेक्चर का उपयोग करके टर्बो कोड प्रस्तावों के लिए डिकोडर कॉम्प्लेक्सिटी अनुमान लगाया। इसने टर्बो कोड प्रस्तावों को एलडीपीसी प्रस्तावों के आधे फ्रेम आकार के क्रम पर फ्रेम आकार का उपयोग करने के लिए विविश किया था।

2008 में, एलडीपीसी ने ITU-T G.hn मानक के लिए आगे त्रुटि सुधार (एफईसी) प्रणाली के रूप में कन्वेन्शनल टर्बो कोड को पराजित करते है।[13] G.hn ने टर्बो कोड की तुलना में एलडीपीसी कोड को उनकी कम डिकोडिंग कॉम्प्लेक्सिटी के कारण चुना (विशेषकर जब 1.0 Gbit/s के समीप डेटा दरों पर काम कर रहा हो) और क्योंकि प्रस्तावित टर्बो कोड ने ऑपरेशन की वांछित सीमा पर एक महत्वपूर्ण त्रुटि स्तर प्रदर्शित किया था।[14]

एलडीपीसी कोड का उपयोग 10GBASE-T ईथरनेट के लिए भी किया जाता है, जो ट्विस्टेड-पेयर केबल पर 10 गीगाबिट प्रति सेकंड पर डेटा भेजता है। 2009 तक, हाई थ्रूपुट (HT) पीएचवाई विनिर्देश में, एलडीपीसी कोड 802.11n और 802.11ac के वैकल्पिक भाग के रूप में वाई-फाई 802.11 मानक का भी भाग हैं।[15] एलडीपीसी 802.11ax (वाई-फाई 6) का एक अनिवार्य भाग है।[16]

कुछ ओएफडीएम प्रणाली एक अतिरिक्त बाहरी त्रुटि सुधार जोड़ते हैं जो कभी-कभी होने वाली त्रुटियों (त्रुटि स्तर) को ठीक करता है जो कम बिट त्रुटि दर पर भी एलडीपीसी सुधार आंतरिक कोड से आगे निकल जाता है।

उदाहरण के लिए: एलडीपीसी कोडेड मॉड्यूलेशन (आरएस-एलसीएम) के साथ रीड-सोलोमन कोड रीड-सोलोमन बाहरी कोड का उपयोग करता है।[17] डीवीबी-S2, डीवीबी-T2 और डीवीबी-C2 मानक सभी एलडीपीसी डिकोडिंग के बाद अवशिष्ट त्रुटियों को मिटाने के लिए BCH कोड बीसीएच कोड का उपयोग करते हैं।[18]

5जी नं नियंत्रण चैनलों के लिए पोलर कोड (कोडिंग सिद्धांत) और डेटा चैनलों के लिए एलडीपीसी का उपयोग करता है।[19][20]

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


परिचालन उपयोग

एलडीपीसी कोड कार्यात्मक रूप से विरल समता-जांच आव्यूह द्वारा परिभाषित किए जाते हैं। यह विरल आव्यूह अधिकांशतः यादृच्छिक रूप से उत्पन्न होता है, विरलता बाधाओं के अधीन - एलडीपीसी कोड निर्माण पर बाद में चर्चा की जाती है। ये कोड पहली बार 1960 में रॉबर्ट गैलागर द्वारा डिज़ाइन किए गए थे।[7]

नीचे फ़ॉर्नी के फ़ैक्टर ग्राफ़ नोटेशन का उपयोग करते हुए एक उदाहरण एलडीपीसी कोड का ग्राफ़ टुकड़ा दिया गया है। इस ग्राफ़ में, ग्राफ़ के शीर्ष में n वैरिएबल नोड्स ग्राफ़ के निचले भाग में (n−k) बाधा नोड्स से जुड़े हुए हैं।

यह (n , k) एलडीपीसी कोड को ग्राफ़िक रूप से प्रस्तुत करने का एक लोकप्रिय विधि है। एक वैध संदेश के बिट्स, जब ग्राफ़ के शीर्ष पर 'T's' पर रखे जाते हैं, तो ग्राफिकल बाधाओं को पूरा करते हैं। विशेष रूप से, एक वेरिएबल नोड ('=' चिन्ह वाला बॉक्स) से जुड़ने वाली सभी पंक्तियों का मान समान होता है, और कारक नोड ('+' चिन्ह वाला बॉक्स) से जुड़ने वाले सभी मानों का योग, मॉड्यूलर अंकगणित दो, शून्य तक होना चाहिए (दूसरे शब्दों में, उन्हें एक सम संख्या में योग करना चाहिए; या विषम मानों की एक सम संख्या होनी चाहिए)।

Ldpc code fragment factor graph.svg

छवि से बाहर जाने वाली किसी भी लाइन को अनदेखा करते हुए, वैध कोडवर्ड के अनुरूप आठ संभावित छह-बिट स्ट्रिंग हैं: (अथार्थ , 000000, 011001, 110010, 101011, 111100, 100101, 001110, 010111)। यह एलडीपीसी कोड खंड छह बिट्स के रूप में एन्कोडेड तीन-बिट संदेश का प्रतिनिधित्व करता है। चैनल त्रुटियों से उबरने की संभावना बढ़ाने के लिए, यहां अतिरेक का उपयोग किया जाता है। यह एक (6, 3) रैखिक कोड है, जिसमें n = 6 और k = 3 है।

चित्र से बाहर जाने वाली रेखाओं को फिर से अनदेखा करते हुए, समता-जाँच आव्यूह इस ग्राफ़ खंड का प्रतिनिधित्व करता है

इस आव्यूह में, प्रत्येक पंक्ति तीन समता-जांच बाधाओं में से एक का प्रतिनिधित्व करती है, जबकि प्रत्येक स्तम्भ प्राप्त कोडवर्ड में छह बिट्स में से एक का प्रतिनिधित्व करता है।

इस उदाहरण में, जीएफ(2) में मूलभूत पंक्ति संचालन के माध्यम से समता-जांच आव्यूह H को इस फॉर्म में डालकर आठ कोडवर्ड प्राप्त किए जा सकते हैं:

चरण 1: एच.

चरण 2: पंक्ति 1 को पंक्ति 3 में जोड़ा जाता है।

चरण 3: पंक्ति 2 और 3 की अदला-बदली की जाती है।

चरण 4: पंक्ति 1 को पंक्ति 3 में जोड़ा जाता है।

इससे, जनरेटर आव्यूह G को के रूप में प्राप्त किया जा सकता है (ध्यान दें कि विशेष स्थिति में यह एक बाइनरी कोड है), या विशेष रूप से:

अंत में, सभी आठ संभावित 3-बिट स्ट्रिंग्स को G से गुणा करने पर, सभी आठ वैध कोडवर्ड प्राप्त होते हैं। उदाहरण के लिए, बिट-स्ट्रिंग '101' के लिए कोडवर्ड इसके द्वारा प्राप्त किया जाता है:

,

जहाँ मॉड 2 गुणन का प्रतीक है।

जाँच के रूप में, G की पंक्ति का स्थान H के लिए ओर्थोगोनल है जैसे कि

बिट-स्ट्रिंग '101' कोडवर्ड '101011' के पहले 3 बिट्स के रूप में पाई जाती है।

उदाहरण एन्कोडर

एलडीपीसी एनकोडर

एक फ्रेम के एन्कोडिंग के समय , इनपुट डेटा बिट्स (डी) को दोहराया जाता है और कांस्टीटुएंट एन्कोडर्स के एक सेट में वितरित किया जाता है। कांस्टीटुएंट एनकोडर समान्यत: संचायक होते हैं और प्रत्येक संचायक का उपयोग समता प्रतीक उत्पन्न करने के लिए किया जाता है। मूल डेटा की एक प्रति (S0,K-1) कोड प्रतीकों को बनाने के लिए समता बिट्स (पी) के साथ प्रेषित होता है। प्रत्येक कांस्टीटुएंट एनकोडर से एस बिट्स को हटा दिया जाता है।

समता बिट का उपयोग किसी अन्य कांस्टीटुएंट कोड के अंदर किया जा सकता है।

डीवीबी-S2 रेट 2/3 कोड का उपयोग करते हुए एक उदाहरण में एन्कोडेड ब्लॉक का आकार 64800 प्रतीक (N=64800) है जिसमें 43200 डेटा बिट्स (K=43200) और 21600 पैरिटी बिट्स (M=21600) हैं। प्रत्येक कांस्टीटुएंट कोड (चेक नोड) पहले समता बिट को छोड़कर 16 डेटा बिट्स को एनकोड करता है जो 8 डेटा बिट्स को एनकोड करता है। पहले 4680 डेटा बिट्स को 13 बार दोहराया जाता है (13 समता कोड में उपयोग किया जाता है), जबकि शेष डेटा बिट्स 3 समता कोड (अनियमित एलडीपीसी कोड) में उपयोग किया जाता है।

तुलना के लिए, क्लासिक टर्बो कोड समान्यत: समानांतर में कॉन्फ़िगर किए गए दो कांस्टीटुएंट कोड का उपयोग करते हैं, जिनमें से प्रत्येक डेटा बिट्स के संपूर्ण इनपुट ब्लॉक (K) को एन्कोड करता है। ये कांस्टीटुएंट एनकोडर मध्यम गहराई (8 या 16 स्थिति) के पुनरावर्ती कन्वेन्शनल कोड (आरएससी) हैं जो एक कोड इंटरलीवर द्वारा अलग किए जाते हैं जो फ्रेम की एक प्रति को इंटरलीव करता है।

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

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

व्यावहारिक रूप में, संचायक बनाने वाले हार्डवेयर को एन्कोडिंग प्रक्रिया के समय पुन: उपयोग किया जाता है। अर्थात्, एक बार समता बिट्स का पहला सेट उत्पन्न हो जाता है और समता बिट्स संग्रहीत हो जाते हैं, उसी संचायक हार्डवेयर का उपयोग समता बिट्स का अगला सेट उत्पन्न करने के लिए किया जाता है।

डिकोडिंग

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

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

एसपीसी कोड की डिकोडिंग को अधिकांशतः चेक नोड प्रोसेसिंग के रूप में जाना जाता है, और वेरिएबल्स की क्रॉस-चेकिंग को अधिकांशतः वेरिएबल-नोड प्रोसेसिंग के रूप में जाना जाता है।

व्यावहारिक एलडीपीसी डिकोडर कार्यान्वयन में, थ्रूपुट बढ़ाने के लिए एसपीसी कोड के सेट को समानांतर में डिकोड किया जाता है।

इसके विपरीत, बाइनरी इरेज़र चैनल पर विश्वास का प्रसार विशेष रूप से सरल है जहां इसमें पुनरावृत्त बाधा संतुष्टि सम्मिलित है।

उदाहरण के लिए, मान लें कि उपरोक्त उदाहरण से मान्य कोडवर्ड, 101011, एक बाइनरी इरेज़र चैनल में प्रसारित होता है और ?01?11 प्राप्त करने के लिए पहले और चौथे बिट को मिटाकर प्राप्त किया जाता है। चूंकि प्रेषित संदेश को कोड की बाधाओं को पूरा करना होगा, इसलिए संदेश को कारक ग्राफ़ के शीर्ष पर प्राप्त संदेश लिखकर दर्शाया जा सकता है।

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

फिर यह प्रक्रिया दोहराई जाती है चौथे बिट के लिए नया मान अब पहले बिट को पुनर्प्राप्त करने के लिए पहले बाधा के साथ संयोजन में उपयोग किया जा सकता है जैसा कि नीचे देखा गया है। इसका अर्थ यह है कि पहला बिट सबसे बाईं ओर की बाधा को पूरा करने वाला होना चाहिए।

Ldpc code fragment factor graph w erasures decode step 2.svg

इस प्रकार, संदेश को पुनरावृत्त रूप से डिकोड किया जा सकता है। अन्य चैनल मॉडल के लिए, वेरिएबल नोड्स और चेक नोड्स के बीच पारित संदेश वास्तविक संख्याएं हैं, जो विश्वास की संभावनाओं और संभावनाओं को व्यक्त करते हैं।

इस परिणाम को समता-जांच आव्यूह H द्वारा सही कोडवर्ड r को गुणा करके मान्य किया जा सकता है:

चूँकि इस ऑपरेशन का परिणाम z (डिकोडिंग विधियाँ या सिंड्रोम डिकोडिंग) तीन × एक शून्य वेक्टर है, परिणामी कोडवर्ड r सफलतापूर्वक मान्य है।

डिकोडिंग पूरी होने के बाद, कोडवर्ड के पहले 3 बिट्स को देखकर मूल संदेश बिट्स '101' निकाला जा सकता है।

उदाहरणात्मक होते हुए भी, यह इरेज़र उदाहरण सॉफ्ट-डिसीजन डिकोडिंग या सॉफ्ट-डिसीजन संदेश पासिंग का उपयोग नहीं दिखाता है, जिसका उपयोग लगभग सभी वाणिज्यिक एलडीपीसी डिकोडर्स में किया जाता है।

नोड जानकारी अपडेट करना

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

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

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

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

कोड निर्माण

बड़े ब्लॉक आकारों के लिए, एलडीपीसी कोड समान्यत: पहले डिकोडर्स के व्यवहार का अध्ययन करके बनाए जाते हैं। चूंकि ब्लॉक का आकार अनंत तक जाता है, एलडीपीसी डिकोडर्स को एक ध्वनि सीमा दिखाई जा सकती है जिसके नीचे डिकोडिंग विश्वसनीय रूप से प्राप्त की जाती है, और जिसके ऊपर डिकोडिंग प्राप्त नहीं की जाती है,[25] बोलचाल की भाषा में इसे क्लिफ इफ़ेक्ट कहा जाता है। इस सीमा को चेक नोड्स से आर्क और वेरिएबल नोड्स से आर्क का सर्वोत्तम अनुपात खोजकर अनुकूलित किया जा सकता है। इस सीमा को देखने के लिए एक अनुमानित ग्राफिकल दृष्टिकोण एक EXIT चार्ट है।

इस अनुकूलन के बाद एक विशिष्ट एलडीपीसी कोड का निर्माण दो मुख्य प्रकार की तकनीकों में आता है:

  • छद्म यादृच्छिक दृष्टिकोण
  • संयुक्त दृष्टिकोण

छद्म-यादृच्छिक दृष्टिकोण द्वारा निर्माण सैद्धांतिक परिणामों पर आधारित होता है, जो बड़े ब्लॉक आकार के लिए, एक यादृच्छिक निर्माण अच्छा डिकोडिंग प्रदर्शन देता है।[10] सामान्य रूप से, छद्म यादृच्छिक कोड में काम्प्लेक्स एनकोडर होते हैं, किंतु सर्वोत्तम डिकोडर वाले छद्म यादृच्छिक कोड में सरल एनकोडर हो सकते हैं।[26] यह सुनिश्चित करने में सहायता के लिए अधिकांशतः विभिन्न बाधाएं प्रयुक्त की जाती हैं कि अनंत ब्लॉक आकार की सैद्धांतिक सीमा पर अपेक्षित वांछित गुण एक सीमित ब्लॉक आकार पर होते हैं।

कॉम्बिनेटोरियल दृष्टिकोण का उपयोग छोटे ब्लॉक-आकार के एलडीपीसी कोड के गुणों को अनुकूलित करने या सरल एनकोडर के साथ कोड बनाने के लिए किया जा सकता है।

कुछ एलडीपीसी कोड रीड-सोलोमन कोड पर आधारित होते हैं, जैसे 10 गीगाबिट ईथरनेट मानक में उपयोग किया जाने वाला आरएस-एलडीपीसी कोड[27] व्यवस्थित रूप से उत्पन्न एलडीपीसी कोड की तुलना में, संरचित एलडीपीसी कोड - जैसे कि डीवीबी-एस 2 मानक में प्रयुक्त एलडीपीसी कोड - में सरल और इसलिए कम निवेश वाले हार्डवेयर हो सकते हैं - विशेष रूप से, कोड ऐसे निर्मित होते हैं कि एच आव्यूह एक आव्यूह सर्कुलर आव्यूह है।[28]

एलडीपीसी कोड बनाने का एक अन्य विधि परिमित ज्यामिति का उपयोग करना है। यह विधि 2001 में वाई. कोउ एट अल द्वारा प्रस्तावित की गई थी।[29]


एलडीपीसी कोड बनाम टर्बो कोड

एलडीपीसी कोड की तुलना अन्य शक्तिशाली कोडिंग योजनाओं से की जा सकती है, जैसे टर्बो कोड.[30] एक ओर, टर्बो कोड की बिट त्रुटि दर प्रदर्शन कम कोड सीमाओं से प्रभावित होती है।[31] एलडीपीसी कोड में न्यूनतम दूरी की कोई सीमा नहीं है,[32] इसका अप्रत्यक्ष अर्थ यह है कि एलडीपीसी कोड टर्बो कोड की तुलना में अपेक्षाकृत बड़ी कोड दरों (जैसे 3/4, 5/6, 7/8) पर अधिक कुशल हो सकते हैं। चूँकि एलडीपीसी कोड पूर्ण प्रतिस्थापन नहीं हैं: टर्बो कोड कम कोड दरों (जैसे 1/6, 1/3, 1/2) पर सबसे अच्छा समाधान हैं।[33][34]


यह भी देखें

लोग

सिद्धांत

अनुप्रयोग

  • जी.एचएन या जी.एचएन/जी.9960 (बिजली लाइनों, फोन लाइनों और समाक्षीय केबल पर नेटवर्किंग के लिए आईटीयू-टी मानक)
  • 802.3an या 10GBASE-T (ट्विस्टेड पेयर पर 10 गीगाबिट/सेकेंड ईथरनेट)
  • सीएमएमबी (चीन मल्टीमीडिया मोबाइल ब्रॉडकास्टिंग)
  • डीवीबी-S2 / डीवीबी-T2 / डीवीबी-C2 (डिजिटल वीडियो प्रसारण, दूसरी पीढ़ी)
  • डीएमबी-टी/एच (डिजिटल वीडियो प्रसारण)[35]
  • वाइमैक्स (माइक्रोवेव संचार के लिए आईईईई 802.16e मानक)
  • आईईईई 802.11n-2009 (वाई-फ़ाई मानक)
  • डॉक्सिस 3.1
  • एटीएससी 3.0 (अगली पीढ़ी उत्तरी अमेरिका डिजिटल स्थलीय प्रसारण)
  • 3जीपीपी (5जी-एनआर डेटा चैनल)

अन्य क्षमता-अनुरूप कोड

संदर्भ

  1. David J.C. MacKay (2003) Information theory, Inference and Learning Algorithms, CUP, ISBN 0-521-64298-1, (also available online)
  2. Todd K. Moon (2005) Error Correction Coding, Mathematical Methods and Algorithms. Wiley, ISBN 0-471-64800-0 (Includes code)
  3. Amin Shokrollahi (2003) LDPC Codes: An Introduction
  4. US 5446747 
  5. NewScientist, Communication speed nears terminal velocity, by Dana Mackenzie, 9 July 2005
  6. Larry Hardesty (January 21, 2010). "Explained: Gallager codes". MIT News. Retrieved August 7, 2013.
  7. 7.0 7.1 [1] R. G. Gallager, "Low density parity check codes," IRE Trans. Inf. Theory, vol. IT-8, no. 1, pp. 21- 28, Jan. 1962.
  8. [2] J. Moshieff, N. Resch, N. Ron-Zewi, S. Silas, M. Wootters, "Low-density parity-check codes achieve list-decoding capacity," SIAM Journal on Computing, FOCS20-38-FOCS20-73.
  9. Robert G. Gallager (1963). कम घनत्व समता जाँच कोड (PDF). Monograph, M.I.T. Press. Retrieved August 7, 2013.
  10. 10.0 10.1 David J.C. MacKay and Radford M. Neal, "Near Shannon Limit Performance of Low Density Parity Check Codes," Electronics Letters, July 1996
  11. Telemetry Data Decoding, Design Handbook
  12. Presentation by Hughes Systems Archived 2006-10-08 at the Wayback Machine
  13. HomePNA Blog: G.hn, a PHY For All Seasons
  14. IEEE Communications Magazine paper on G.hn Archived 2009-12-13 at the Wayback Machine
  15. IEEE Standard, section 20.3.11.6 "802.11n-2009", IEEE, October 29, 2009, accessed March 21, 2011.
  16. "IEEE SA - IEEE 802.11ax-2021". IEEE Standards Association (in English). Retrieved 22 May 2022.
  17. Chih-Yuan Yang, Mong-Kai Ku. http://123seminarsonly.com/Seminar-Reports/029/26540350-Ldpc-Coded-Ofdm-Modulation.pdf "LDPC coded OFDM modulation for high spectral efficiency transmission"
  18. Nick Wells. "DVB-T2 in relation to the DVB-x2 Family of Standards" Archived 2013-05-26 at the Wayback Machine
  19. "5G Channel Coding" (PDF). Archived from the original (PDF) on December 6, 2018. Retrieved January 6, 2019.
  20. Maunder, Robert (September 2016). "A Vision for 5G Channel Coding" (PDF). Archived from the original (PDF) on December 6, 2018. Retrieved January 6, 2019.
  21. Kai Zhao, Wenzhe Zhao, Hongbin Sun, Tong Zhang, Xiaodong Zhang, and Nanning Zheng (2013). " LDPC-in-SSD: Making Advanced Error Correction Codes Work Effectively in Solid State Drives" (PDF). FAST' 13. pp. 243–256.{{cite conference}}: CS1 maint: multiple names: authors list (link)
  22. "Soft-Decoding in LDPC based SSD Controllers". EE Times. 2015.
  23. 23.0 23.1 A.I. Vila Casado, M. Griot, and R.Wesel, "Informed dynamic scheduling for belief propagation decoding of LDPC codes," Proc. IEEE Int. Conf. on Comm. (ICC), June 2007.
  24. T. Richardson, "Error floors of LDPC codes," in Proc. 41st Allerton Conf. Comm., Control, and Comput., Monticello, IL, 2003.
  25. Thomas J. Richardson and M. Amin Shokrollahi and Rüdiger L. Urbanke, "Design of Capacity-Approaching Irregular Low-Density Parity-Check Codes," IEEE Transactions on Information Theory, 47(2), February 2001
  26. Thomas J. Richardson and Rüdiger L. Urbanke, "Efficient Encoding of Low-Density Parity-Check Codes," IEEE Transactions on Information Theory, 47(2), February 2001
  27. Ahmad Darabiha, Anthony Chan Carusone, Frank R. Kschischang. "Power Reduction Techniques for LDPC Decoders"
  28. Zhengya Zhang, Venkat Anantharam, Martin J. Wainwright, and Borivoje Nikolic. "An Efficient 10GBASE-T Ethernet LDPC Decoder Design With Low Error Floors".
  29. Y. Kou, S. Lin and M. Fossorier, "Low-Density Parity-Check Codes Based on Finite Geometries: A Rediscovery and New Results," IEEE Transactions on Information Theory, vol. 47, no. 7, November 2001, pp. 2711- 2736.
  30. Tahir, B., Schwarz, S., & Rupp, M. (2017, May). BER comparison between Convolutional, Turbo, LDPC, and Polar codes. In 2017 24th International Conference on Telecommunications (ICT) (pp. 1-7). IEEE.
  31. Moon Todd, K. Error correction coding: mathematical methods and algorithms. 2005 by John Wiley & Sons. ISBN 0-471-64800-0. - p.614
  32. Moon Todd, K. Error correction coding: mathematical methods and algorithms. 2005 by John Wiley & Sons. ISBN 0-471-64800-0. - p.653
  33. Andrews, Kenneth S., et al. "The development of turbo and LDPC codes for deep-space applications." Proceedings of the IEEE 95.11 (2007): 2142-2156.
  34. Hassan, A.E.S., Dessouky, M., Abou Elazm, A. and Shokair, M., 2012. Evaluation of complexity versus performance for turbo code and LDPC under different code rates. Proc. SPACOMM, pp.93-98.
  35. "IEEE Spectrum: Does China Have the Best Digital Television Standard on the Planet?". spectrum.ieee.org. Archived from the original on 2009-12-12.


बाहरी संबंध