Talk:Low-density parity-check code: Difference between revisions

Revision as of 03:30, 15 February 2014

Latest revision as of 05:21, 5 February 2024

(26 intermediate revisions by 13 users not shown)

Line 1:

{{oldpeerreview|archive=1}}

{{WikiProject banner shell|class=C|

{{Tel Project}}

{{WikiProject Telecommunications }}

}}

{{Expert-talk}}

For a person who has not studied information theory, the introduction chapter says absolutely nothing. It's some state of the art code, rrright. For what/Where/Why is it used? I think the introduction should answer these questions first. Then it's okay to jump into the technics. Besides, what's Forney's factor graph notation anyway? Maybe an article about it should be created, or at least [[Forney]] linked somewhere. (Elsewhere than to [[Forney, Texas]]). --[[User:ZeroOne|ZeroOne]] 19:52, 12 Oct 2004 (UTC)

Line 34 ⟶ 36:

Yes its specifiyed in the HT of 802.11n wich codelength between 648 and 1944 bits. <span style="font-size: smaller;" class="autosigned">—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/131.188.138.93|131.188.138.93]] ([[User talk:131.188.138.93|talk]]) 13:19, 13 August 2010 (UTC)</span><!-- Template:UnsignedIP --> <!--Autosigned by SineBot-->

== Operational use ==

I think some of the details need to be better written here. The variable 'k' is not even defined. Also, the sentence "or there must be an even number of odd values" is confusing. Instead of writing that, should write something straight-forward, such as - the "Exclusive OR" of all the bits linked by the lines will be logical 0. Also, as if by 'magic', the matrices "P" and "I" just pop out of nowhere, and nobody has any idea what they are. [[User:KorgBoy|KorgBoy]] ([[User talk:KorgBoy|talk]]) 08:10, 25 May 2017 (UTC)

I think H should be reduced to -P^T | I_{k} and not (n-k). Because the number of rows of H is actually k. It works for this example since n-k = k here, but for general n and k, it will not work. <!-- Template:Unsigned --><small class="autosigned">—&nbsp;Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[User:Swaprava|Swaprava]] ([[User talk:Swaprava#top|talk]] • [[Special:Contributions/Swaprava|contribs]]) 17:53, 5 January 2020 (UTC)</small> <!--Autosigned by SineBot-->

Similarly, G will be starting with I_{n-k} and not k. LDPC codes encode n-k bits into n bits, right? <!-- Template:Unsigned --><small class="autosigned">—&nbsp;Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[User:Swaprava|Swaprava]] ([[User talk:Swaprava#top|talk]] • [[Special:Contributions/Swaprava|contribs]]) 17:56, 5 January 2020 (UTC)</small> <!--Autosigned by SineBot-->

== Forgotten? ==

Line 40 ⟶ 50:

In the paper that effectively reintroducted LDPC codes (MacKay and Neal "Near Shannon Limit Performance of Low Density Parity Check Codes") there is a brief mention of this topic. The suggestion is that a slightly related family of codes (concatenated codes) were believed to be better and hence LDPC codes were ignored. This paper cites personal communication from Gallager on this topic. [[User:Edratzer|Edratzer]] 17:25, 17 September 2006 (UTC)

LDPC codes were actually rediscovered one year before MacKay and Neal, by Wiberg, Loeliger, and Kötter in "Codes and Iterated Decoding on General Graphs", published in 1995. This was triggered by the publication of Turbo codes in 1993, which sparked the new interest in iterative decoding algorithms. This page should be updated with a reference to that paper. [[User:Nicwi|Nicwi]] ([[User talk:Nicwi|talk]]) 21:21, 6 March 2016 (UTC)

== Links ==

Line 85 ⟶ 97:

This section states that decoding an LDPC code is NP-complete. Well, this is certainly not true for a [[binary erasure channel]], and ironically the example given discusses just that channel.

Does the subsection on lookup-table decoding need a citation? Or does anyone know of some elaboration on the method described? I'm not sure how a 1024-bit table would help decode an LDPC with a 1024-bit block size. (I may be misreading that section; it could probably be cleaned up anyway; e.g. "very high iterations" could be "many iterations" or some more fluent wording.) <span style="font-size: smaller;" class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/173.73.92.75|173.73.92.75]] ([[User talk:173.73.92.75|talk]]) 03:30, 15 February 2014 (UTC)</span><!-- Template:Unsigned IP --> <!--Autosigned by SineBot-->

The section on lookup-table absolutely needs a citation. How can any machine store a lookup table for arbitrary 1024 bit strings, much less a microcontroller? -EdwinOlson <span style="font-size: smaller;" class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/64.94.31.206|64.94.31.206]] ([[User talk:64.94.31.206|talk]]) 23:13, 24 June 2014 (UTC)</span><!-- Template:Unsigned IP --> <!--Autosigned by SineBot-->

=== Other things ===

Line 221 ⟶ 235:

:Oups I just reverted the change before reading your post ... Maybe it is a way to represent or implement the iterative decoding, and in this case it should be justified. <small><span class="autosigned">—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[User:Cunchem|Cunchem]] ([[User talk:Cunchem|talk]] • [[Special:Contributions/Cunchem|contribs]]) 07:39, 21 October 2009 (UTC)</span></small><!-- Template:Unsigned --> <!--Autosigned by SineBot-->

== Probably trivial in the context... ==

Trivial, I'm sure, but...

In the introduction to the article, it refers to Gallager developing the LDPC concept in his doctoral dissertation at MIT in 1960.

However, in the History section, it states that LDPC codes were first developed by Gallager in 1963. Reference 6 states 1963. Which is true?

David Kelsey <small class="autosigned">—&nbsp;Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/101.178.141.19|101.178.141.19]] ([[User talk:101.178.141.19|talk]]) 00:54, 27 September 2015 (UTC)</small><!-- Template:Unsigned IP --> <!--Autosigned by SineBot-->

:"The story of LDPC codes and iterative decoding begins in Gallager’s remarkable Ph.D. thesis completed in 1960, and later published in 1963"

:[R. G. Gallager. Low-Density Parity-Check Codes. MIT Press, 1963]

:[[User:Markovisch|Markovisch]] ([[User talk:Markovisch#top|talk]] • [[Special:Contributions/Markovisch|contribs]]) 01:02, 27 March 2017 (UTC)

== External links modified ==

Hello fellow Wikipedians,

I have just modified 5 external links on [[Low-density parity-check code]]. Please take a moment to review [[special:diff/819110467|my edit]]. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit [[User:Cyberpower678/FaQs#InternetArchiveBot|this simple FaQ]] for additional information. I made the following changes:

*Added archive https://web.archive.org/web/20061008053124/http://www.ieeevtc.org/vtc2003fall/2003panelsessions/llee.pdf to http://www.ieeevtc.org/vtc2003fall/2003panelsessions/llee.pdf

*Added archive https://web.archive.org/web/20091213012126/http://blog.ds2.es/ds2blog/2009/10/ieee-communications-magazine-paper-on-ghn.html to http://blog.ds2.es/ds2blog/2009/10/ieee-communications-magazine-paper-on-ghn.html

*Added archive https://web.archive.org/web/20130526003113/http://www.atsc.org/cms/pdf/pt2/Wells_ATSC_paper_on_T2.pdf to http://www.atsc.org/cms/pdf/pt2/Wells_ATSC_paper_on_T2.pdf

*Added archive https://web.archive.org/web/20090926035703/http://www.mathworks.com/access/helpdesk/help/toolbox/comm/ref/fec.ldpcenc.html to http://www.mathworks.com/access/helpdesk/help/toolbox/comm/ref/fec.ldpcenc.html

*Added archive https://web.archive.org/web/20090217170744/http://www.mathworks.com/access/helpdesk/help/toolbox/comm/ref/fec.ldpcdec.html to http://www.mathworks.com/access/helpdesk/help/toolbox/comm/ref/fec.ldpcdec.html

When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.

{{sourcecheck|checked=false|needhelp=}}

Cheers.—[[User:InternetArchiveBot|'''<span style="color:darkgrey;font-family:monospace">InternetArchiveBot</span>''']] <span style="color:green;font-family:Rockwell">([[User talk:InternetArchiveBot|Report bug]])</span> 14:14, 7 January 2018 (UTC)

== Decoding ==

The decoding section directly jumps to technicalities and state-of-the-art improvements while never really introducing belief propagation and bit flipping algorithms which I believe are not that hard to understand.

The part about seeing an LDPC as independent SPC codes and using SOVA or BCJR is confusing. I believe it tries to draw an analogy between turbo codes or convolutional codes and LDPC codes. It currently has no reference and the only references I could find on applying those algorithms to LDPC were in really specific constructions with structured codes or concatenations.

The part about lookup table has no reference either. I have no doubt that a bit flipping algorithm can run on a low power CPU and that some computations can be avoided by using a lookup table (for the check nodes computations for example). But I am not sure that this is what the author meant and if this is what was meant I don't see how it is relevant to detail the lookup table and the usage of the FIFO.

[[User:Bpcov|Bpcov]] ([[User talk:Bpcov|talk]]) 19:44, 28 July 2018 (UTC)