Talk:Low-density parity-check code

Low-density parity-check code received a peer review by Wikipedia editors, which is now archived. It may contain ideas you can use to improve this article.

Telecommunications

	Telecommunication portal This article is within the scope of WikiProject Telecommunications, a collaborative effort to improve the coverage of Telecommunications on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.TelecommunicationsWikipedia:WikiProject TelecommunicationsTemplate:WikiProject TelecommunicationsTelecommunications articles
???	This article has not yet received a rating on the project's importance scale.

This topic is in need of attention from an expert on the subject.

The section or sections that need attention may be noted in a message below.

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). --ZeroOne 19:52, 12 Oct 2004 (UTC)

LDPC advantage

I'd agree with the first comment. I am not an information theory specialist and have been trying to get an idea what advantage LDPC gives over eg Reed Solomon, but cannot find this basic information anywhere. Andrew P, UK.

Not impressed with the article either. But in answer to your question: LDPC codes approach the theoretical (Shannon) limit as the block size increases. (I.E. They are the best (in terms of error recovery) that an error correcting code can be.) A Google of LDPC turns up a lot of good articles. Nahaj 15:25, 8 November 2005 (UTC)[reply]

Generating the parity-check matrix

Although Gallager's original codes used a randomly generated parity-check matrix, this doesn't have to be the case. A subset of Gallager codes can be built analytically by an algebraic method based on shortened Reed-Solomon codes with two information symbols. LDPC codes can also be constructed algebraically based on the points and lines of finite geometries. The highest performance LDPC codes are constructed using a method known as density evolution.

Density evolution is a measure of the code, not a method of code construction. To quote Moon's "Error Correction Coding": "Density evolution is an analytical technique which can be used to understand limits of performance of LDPC decoders. " Although, obviously, ANYTHING that measures a code can be used to AID in generating good codes. (And there have been many articles on building various subsets of Gallager codes by many many different methods.) If the author of the anonymous comment above would like to provide a *current* reference for their interesting claim that "The highest performance LDPC codes are constructed using a method known as density evolution.", I'd appreciate it. Work on finding GOOD non-randomly generated LDPC codes is still ongoing in a number of places... I'd recommed the "IEEE Trans. Information Theory", and the "IEEE Trans. Communications" as jumping in points. Nahaj 17:18, 16 January 2006 (UTC)[reply]

The reference I had in mind when making the statement about "The highest performance LDPC codes..." was S.-Y. Chung, G. D. Forney, T. J. Richardson, R. L. Urbanke, "On the Design of Low-Density Parity-Check Codes within 0.0045 dB of the Shannon Limit," IEEE Communications Letters, vol. 5, no. 2, Feb. 2001. The authors develop an improved implementation of density evolution called discretized density evolution. Using this algorithm and an improved optimization algorithm they design good rate-1/2 irregular LDPC codes for binary-input AWGN channels that approach the Shannon limit very closely, i.e., to within 0.0045 dB. I'm not sure whether this is regarded as a current reference or not. Duncan Aitken, UK.

The claim was made that "The highest performance LDPC codes" are constructed by the method. I'm still waiting for a reference supporting that extreme claim. When it comes to "highest", or best, or any other such term for an algorithm, the status can change rapidly... and only a current article can tell which is currently best. An article from several years ago [ which is very good, by the way ] showing that a method was good doesn't address the issue whether it is the method that currently produces the highest performance codes. Nahaj 15:32, 18 February 2006 (UTC)[reply]

There are two separate issues here: the origin of good parity-check matrices, and the current "best" performance.

I agree with Nahaj that there is more than one way of creating a good parity-check matrix; some documentation of good methods needs to be documented. The LDPC world splits slightly into two camps, psuedo-random generation and non-random approaches. I mainly have experience of the former and am happy to write about the approaches used in this community (ie determination of good degree sequences via denisty evolution or an approximation, and then construction of codes with this degree sequence). Do we have a good author to write about deterministic methods?
As far as I'm aware the best performance is still from SY Chung's paper. I'm not sure what standard of proof is required for Wikipedia as the lack of specific counter evidence can not be proved without citing every LDPC paper since!

Edratzer 17:17, 17 September 2006 (UTC)[reply]

Applications of LDPC

Other than the mention that LDPC is adopted for satellite broadcasting it would be useful if someone added more text on other applications of LDPC. In particular, any thoughts on comparsions with turbo codes in "real world" cases (mobile, etc.).--Alistair9210 08:42, 4 July 2006 (UTC)[reply]

Is not LDPC used in 802.11n? 192.114.175.2 (talk) 11:57, 5 December 2007 (UTC)[reply]

Yes its specifiyed in the HT of 802.11n wich codelength between 648 and 1944 bits. —Preceding unsigned comment added by 131.188.138.93 (talk) 13:19, 13 August 2010 (UTC)[reply]

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. KorgBoy (talk) 08:10, 25 May 2017 (UTC)[reply]

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. — Preceding unsigned comment added by Swaprava (talk • contribs) 17:53, 5 January 2020 (UTC)[reply]

Similarly, G will be starting with I_{n-k} and not k. LDPC codes encode n-k bits into n bits, right? — Preceding unsigned comment added by Swaprava (talk • contribs) 17:56, 5 January 2020 (UTC)[reply]

Forgotten?

Were LDPC codes "forgotten"? Gallager was a famous name in the information theory community in the 1970s and 1980s, so I doubt they were truly forgotten; they just couldn't be practically used. Calbaer 01:03, 21 July 2006 (UTC)[reply]

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. Edratzer 17:25, 17 September 2006 (UTC)[reply]

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. Nicwi (talk) 21:21, 6 March 2016 (UTC)[reply]

Links

I have just reverted the addition of a link added by an anonymous user to a University repository of various LDPC papers. The repository does not appear to be a general source of reference or contain VHDL code that may aid the new reader. I propose adding a link to [1] instead as this page contains open-source hardware source code. Any comments? Can the anonymous link adder come forward? Edratzer 08:07, 8 January 2007 (UTC)[reply]

Expert attention needed

Apparently, some diagrams were deleted due to no source because the diagram creator did not use a *-self template, making this article incomplete because the text depends on them. Could someone who knows about LDPC codes redraw the missing diagrams? Jesse Viviano 07:24, 26 September 2007 (UTC)[reply]

Can someone let me know what diagrams need redrawing? There is a pretty good chance that I can redraw them. User dfhayes 24/04/2008 —Preceding unsigned comment added by Dfhayes (talk • contribs) 11:03, 24 April 2008 (UTC)[reply]

The page used to have a series of steps of belief propagation on a channel with erasures. It would be good to reinstate these. If you have a good way of showing belief propagation on a channel with soft messages that would be good too. Edratzer (talk) 19:08, 24 April 2008 (UTC)[reply]

I think we should the decoding part should be divided into two parts: one for the erasure channel and another for the decoding of soft messages. I'm quite new in wikipedia, but I'm working on LDPC codes and I think I can help to improve this part. —Preceding unsigned comment added by Cunchem (talk • contribs) 12:30, 2 September 2008 (UTC)[reply]

Gallager Codes

I think that the title of this page should also be Gallager Codes so that it will come up easily in an internet search. I don't know how to do this or I would do it myself —Preceding unsigned comment added by Lansey (talk • contribs) 09:12, 4 June 2008 (UTC)[reply]

I have created a redirect from Gallager codes. Edratzer (talk) 14:59, 7 June 2008 (UTC)[reply]

Thanks, this wiki pages now comes up first for a search of Gallager Codes, thanks --Lansey (talk) 10:07, 6 July 2008 (UTC)[reply]

Function

Hi all. As far as i know, check matrix $H$ can not be represented as ${\begin{bmatrix}P|I_{k}\end{bmatrix}}$ just by changing the row-column order. Because almost every column contains j 1's, there is not enought columns with single 1. Example is not good enought. Vlsergey (talk) 20:47, 28 August 2008 (UTC)[reply]

The row operations include addition of rows to each other - we're not just talking about row/column permutations. I've linked to the page on row operations but if you would like to make the article clearer then feel free. I guess more mention could be made of matrix rank too. Edratzer (talk) 22:07, 23 September 2008 (UTC)[reply]

In this case $P$ is also called a generator matrix of the code. --Cunchem 08:46, 3 April 2009 (UTC) —Preceding unsigned comment added by Cunchem (talk • contribs)

POV

Citation 5 on carrier recovery doesn't seem to be significant in the LDPC coding arena (Google Scholar gives 7 citations of which 2 are self-citations). I note that the Userid that added the section is very similar to the name of one of the article authors. Edratzer (talk) 21:51, 23 January 2009 (UTC)[reply]

Sorry, I should have looked here first, since I just reverted and asked you to explain. The better thing to do, instead of the cryptic POV tag on something that doesn't like like a POV issue, is to just fix it, especially if it was added with an apparent WP:COI, and leave the editor a note to explain that he think his own stuff should be cited then he should make his case on this talk page instead of citing it himself. WP:SOFIXIT. Dicklyon (talk) 00:39, 24 January 2009 (UTC)[reply]

Some observations on this article

Section Function

This section adds no information on LDPC encoding or other properties. Information on Generator and Parity Check matrices and deriving the code using these belongs to an article on general FEC coding. And I am pretty sure that in practice you don't do a large size, sparse(!) matrix multiplication, but rather sum up the check nodes along the edges in the graph. Please remove this unhelpful stuff. The section may rather tell something about the structure of LDPC codes, as bipartite graphs, regular or irregular etc. Give links to derived codes, such as Tornado codes for the BEC etc.

Section Decoding

Similar to above, this section should write something about decoding algorithms, such as message passing etc. 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.) — Preceding unsigned comment added by 173.73.92.75 (talk) 03:30, 15 February 2014 (UTC)[reply]

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 — Preceding unsigned comment added by 64.94.31.206 (talk) 23:13, 24 June 2014 (UTC)[reply]

Other things

Sentence two in the introduction: isn't that kinda obvious? Sentence three: data transmission rate? please be precise: code rate. Turbo codes can also be classified as LDPC codes. How are they differentiated? The article states three different years for the invention of Gallager codes: 1960, 1962, and 1963. The article should further cite different variants of LDPC codes in practice.

Sorry if points are rather rough, it's late, I'm tired, and I am not an expert on coding. Anyway, thanks for giving a check. G'night ;) Nageh (talk) 22:39, 22 May 2009 (UTC)[reply]

Capacity achieving?

The third sentence of the introduction ("LDPC was the first code to allow data transmission rates close to the theoretical maximum") does not really bring any valuable information. It all depends too much on what is meant by "close to the theoretical maximum". Either one should give a precise value like "within XX dB from theoretical maximum" with a corresponding reference, or one should lose the sentence altogether. Kaioshin82 (talk) 13:19, 30 July 2009 (UTC)[reply]

I've tried to clarify the start of the article. I'm guessing the original author is referring to whether or not LDPC codes can achieve capacity. Edratzer (talk) 08:08, 5 August 2009 (UTC)[reply]

Thanks! That's a much better introduction. Pfagerburg (talk) 01:28, 7 August 2009 (UTC)[reply]

comparison to multidimensional parity check code

I have put a sentence in the introduction saying: "LDPC codes operate on the same principle as Multidimensional parity-check codes except that LDPC codes form the Parity bits from groups of randomly selected data bits" MDPC codes being much simpler make it easier for the beginner to grasp the central idea being used in LDPC codes. At least one person has disputed the connection between MDPC and LDPC codes. I cannot imagine how anyone could fail to see the connection. I am starting this new section in order that we may arrive at a consensus on this issue. just-emery (talk) 23:43, 6 June 2009 (UTC)[reply]

I'm no expert on LDPC, but I'm not sure I see the direct connection either, other than their names! LDPCs are designed around the concept of random parity matrices, whereas MDPCs are completely structured. My understanding is that the performance of LDPCs is determined in terms of the expectation over all random sparse parity matrices, whereas the weight spectrum of an MDPC is obviously deterministic. Oli Filth^{(talk|contribs)} 02:12, 7 June 2009 (UTC)[reply]

Oh, now you are just being ridiculous. Obviously there are differences. When I say that they operate on the same basic 'principle' I am speaking to beginners who are unfamiliar with error correction who might find MDPC codes to be more intuitive. LDPC codes perform much better because there aren't as many 'cycles' in their graphs. MDPC codes are nothing but 'cycles'. I think it would be useful to point out (in the article) how they differ and why LDPC codes are better.

And no, I am not an expert either But I can plainly see how they are similar. If you disagree then what 'basic principle' do you say they are based on? just-emery (talk) 03:10, 7 June 2009 (UTC)[reply]

My point is, how is LDPC related to MDPC any more than it is to any other block code? Oli Filth^{(talk|contribs)} 12:04, 7 June 2009 (UTC)[reply]

What else would you compare it to? just-emery (talk) 17:01, 7 June 2009 (UTC)[reply]

Why do they need a specific comparison point? Singling out MDPC implies that they're related in some way (i.e. more so than any other block code). Oli Filth^{(talk|contribs)} 17:11, 7 June 2009 (UTC)[reply]

If you dont think they are most closely related to MDPC codes then what do you think they are most closely related to? please stop ignoring me and answer my question. just-emery (talk) 17:40, 7 June 2009 (UTC)[reply]

I'm not sure why you think there has to be an answer to that question! LDPC is what it is; a block code that achieves close to the Shannon bound, which has a class of sub-optimal iterative decoders, and whose performance is defined statistically over all random parity matrices. On these points alone, it sounds most like a turbo code. But even that would be misleading, as the construction is entirely different. Oli Filth^{(talk|contribs)} 17:57, 7 June 2009 (UTC)[reply]

According to what you just said the difference between LDPC and MDPC codes is that LDPC produces its parity bits from groups of randomly selected data bits and it therefore achieves close to the shannon limit. how does that differ from what I said originally? just-emery (talk) 18:53, 7 June 2009 (UTC)[reply]

I've already stated what the problem is with "LDPC operates on the same principle as MDPC"; it indicates a relationship where there is none. You may as well have substituted BCH, RS, Golay, Hamming, turbo or RM in there and the sentence would have been as meaningful! Oli Filth^{(talk|contribs)} 19:00, 7 June 2009 (UTC)[reply]

If my statement had simply been that they operate on the same principle and nothing else then you might, arguably, have had a point but my statement as it now reads is: "LDPC codes operate on the same general principle as Multidimensional parity-check codes. The main difference between them being that LDPC codes form the Parity bits from groups of randomly selected data bits and are therefore able to achieve much closer to the Shannon limit due to the greatly reduced number of cycles within their graphs." It is the difference that is being pointed out as being meaningful. Furthermore MDPC codes are more intuitive and easier for beginners to understand so pointing out the difference between MDPC and LDPC codes should help them understand it better. That is the purpose of the article is it not? just-emery (talk) 19:45, 7 June 2009 (UTC)[reply]

If that sentence were to be retained, I would scrap the mention of MDPC entirely, and talk about block codes in general.

Incidentally, I don't believe that the reduced cycles is what lets it attain close to the Shannon limit; instead it simplifies the decoding procedure (although I'm happy to be proved wrong on that one!). Oli Filth^{(talk|contribs)} 20:01, 7 June 2009 (UTC)[reply]

I found this:http://www.comlab.hut.fi/studies/3410/slides_08_12_4.pdf I havent read it through completely but it seems to be relevant. just-emery (talk) 20:23, 7 June 2009 (UTC)[reply]

the lack of cycles makes belief propagation work better. beliefs arent propagating around in circles. that would be bad. just-emery (talk) 20:26, 7 June 2009 (UTC)[reply]

also see Gallager p42 where he talks about 'independence assumption'. also theorem c.1 just-emery (talk) 20:52, 7 June 2009 (UTC)[reply]

I've removed the new paragraph for now, as I think we should be sure on the details first (and probably need someone like User:Edratzer who really knows what they're talking about to help!). Also, this is material that should really be somewhere other than the lead, as the lead isn't supposed to introduce material which isn't then discussed further down. Oli Filth^{(talk|contribs)} 21:23, 7 June 2009 (UTC)[reply]

if you dont 'know' what you are talking about then why are you taking it upon yourself to remove it? this is not how wikipedia is supposed to work. just-emery (talk) 21:33, 7 June 2009 (UTC)[reply]

regarding cycles:http://www.ece.cmu.edu/~moura/papers/intermag05-lu-ieeexplore-1.pdf just-emery (talk) 21:33, 7 June 2009 (UTC)[reply]

reducing cycles is called increasing 'girth' for ldpc codes. just-emery (talk) 21:46, 7 June 2009 (UTC)[reply]

http://axiom.anu.edu.au/~williams/papers/P167.pdf just-emery (talk) 22:04, 7 June 2009 (UTC)[reply]

With no disrespect intended, I'm not sure you know what you're talking about either (that was my point: my impression is that neither of us is qualified to make in-depth edits to this article). At the moment it seems to be a case of adding sentences based on cobbling together nuggets gleaned from various Google searches; that's not a good way to get a coherent or factually correct article on a subject of this nature. My editing policy is that it's better to remove material than to have unsourced and questionable material remain in the article. (That, by the way, is how Wikipedia is supposed to work; see WP:Verifiability and so on.)

Secondly, the one thing I am fairly confident in is that there is no meaningful connection between MDPC and LDPC. Please find a source for this assertion if you believe it should remain in the article. Oli Filth^{(talk|contribs)} 22:13, 7 June 2009 (UTC)[reply]

Thats obviously a subjective judgement call. I totally disagree with you. as you obviously realize, no reference will ever prove a judgement call. I have repeatedly explained myself at great length on this and other topics only to be completely ignored by you. its clear that you will not allow anything in any of the articles except what you yourself want in it despite the fact that you clearly know very little about mdpc, belief propagation, or soft-in soft-out decoding. heavy handed edits such as yours are ruining wikipedia.just-emery (talk) 22:38, 7 June 2009 (UTC)[reply]

If it's an unsourced (or unsourceable) subjective judgement, then I'm afraid it has no place in an article. And as I've already iterated, there's no meaningful rationale for such a comparison. These are the two reasons for my removal of the material. Oli Filth^{(talk|contribs)} 22:50, 7 June 2009 (UTC)[reply]

Again, with no disrespect intended, your explanations have been (to a large degree) based on flawed or incomplete understanding of the issues. Please don't make unfounded accusations about the motivation behind my edits (see WP:AGF); in essence, the only thing I will not "allow" is unsourced material, especially when it's of dubious accuracy. Oli Filth^{(talk|contribs)} 23:13, 7 June 2009 (UTC)[reply]

Regarding comparing the 2. Do you not admit that you could create an ldpc matrix that was equivalent to a mdpc code? so in effect you can think of an mdpc code as a ldpc code whose matrix satisfies certain constraints. so the fact that it uses a matrix doesnt change anything. hence the connection between them. its the randomness of the matrix that is important. just-emery (talk) 22:32, 7 June 2009 (UTC) Since that is the only difference between them then it must be the reason for teh increased performance of ldpc codes.[reply]

All linear block codes may be defined in terms of a parity matrix! (That's practically the definition.) MDPC is nothing special in this regard. Oli Filth^{(talk|contribs)} 22:49, 7 June 2009 (UTC)[reply]

LDPC codes and MDPC are based on the same component code: the parity checksum, and in my opinion the relationship stop there. In an LDPC codes, the number of symbols involved in a parity check is small and does not depend on the length of the code, while in MDPC the number of symbols involved in one parity check depend on the length of the code. In my opinion it is a big difference, since the encoding and the decoding algorithm will not have the same complexity. In addition, for a given length and a given dimension, an LDPC code will outperform an MDPC codes if decoded with an iterative decoding algorithm.Cunchem (talk) 08:40, 8 June 2009 (UTC)[reply]

That was my point just above; all linear codes can be defined in terms of a parity checksum. Oli Filth^{(talk|contribs)} 15:31, 8 June 2009 (UTC)[reply]

Start again

The above discussion is clearly getting nowhere, so I'll repeat my challenges to the material again. If the answer to any one of the following questions is "no" then the material should be removed (although I suspect the answer to all three is "no"):

Do you have a justification as to why the comparison "LDPC vs. MDPC" is more relevant than "LDPC vs. x"? (where x is any other linear block code).
Can you think of any similarities between LPDC and MDPC other than that they're both linear block codes, and both have the term "parity check" in their name?
Do you have a source for any of this?

Oli Filth^{(talk|contribs)} 23:38, 7 June 2009 (UTC)[reply]

@User:Em3ryguy: My 2 cents on this: I'm pretty sure that multi-dimensionality on parity check matrices is a more general concept, and has no specific connection to LDPC codes. If you want to add information about MDPC in an article about LDPC, you have to provide a (scientific) reference stating the connection.

Ok, I had another look at Multidimensional parity-check code. If that is what it is, I can see where you see the connection. I guess you could indeed classify these codes as LDPC codes, since there would be roughly sqrt_d(k) ones per column in the parity-check matrix for a k-size word and dimension d.

This would make a MDPC code a special case of an LDPC code.

Yet, I think this information should be somewhere at the bottom of the page.

What do other people think? Nageh (talk) 11:24, 8 June 2009 (UTC)[reply]

Answering to myself... I think the confusion arises because there is some information missing in the article. LDPC codes are characterized by two central points:

construction via bipartite graph,
resulting parity-check matrix is sparse.

So the question is whether you regard MDPC codes as being constructed via a bipartite graph. Since that certainly was not the original intention of MDPC code design, classifying MDPC codes as LDPC codes seems a little bit stretched after all.

To summarize: If there is reference to MDPC codes in the article, then it should say that "an MDPC code may be viewed as a simple, regular LDPC code". After all, I would rather omit this information than to include it.

Nageh (talk) 11:44, 8 June 2009 (UTC)[reply]

does "sqrt_d(k) ones per column" makes a matrix sparse?

since sqrt(k)/k approaches 0 with k->infinity, I would say, yes, they are sparse... but that's just my opinion.

I think the number of ones per column is

\lim _{k\rightarrow \infty }{\frac {dk+2{\sqrt {k}}}{k+2{\sqrt {k}}}}=d

. (Note that I'm tired, so I could easily have screwed up...)

Your threshold for sparsity seems to be based on the number of ones divided by the overall number of elements (n.k). This sounds fair enough, but wouldn't this classify most codes as sparse (e.g. Hamming)? Oli Filth^{(talk|contribs)} 19:01, 8 June 2009 (UTC)[reply]

If I didn't mess things up in my head, then for a hypercube of dimension d and a k element word you would have sqrt_d(k) ones per column in the parity-check matrix, and consequently the percentage of ones in the matrix approaches zero. I don't see this is true for most linear block codes, in fact RS codes have pretty dense parity-check matrices... but I might be dumb right now.

BTW, I'm just talking about the "parity part" of the matrix... so, number of ones in the parity part divided by (n-k)*k.

Nageh (talk) 20:59, 8 June 2009 (UTC)[reply]

I think that LDPC are also characterized by there ability to be efficiently decoded by a low complexity iterative decoding algorithm. Cunchem (talk) 14:54, 8 June 2009 (UTC)[reply]

Not really. In the original Gallager codes you had to do a full matrix multiplication. The idea was just that there was algorithms doing this faster for sparse matrices than general algorithms, but it was definitely not low complexity.

In the original article of Gallager^[1], after analysing the performances of LDPC under Maximum Likelihood decoding, he introduces 2 algorithms in part 4 that are in fact iterative algorithm. He says that these algorithms are suboptimal but have a low complexity. Maybe you were refering at the encoding when speaking about matrix multiplication. Cunchem (talk) 19:54, 8 June 2009 (UTC)[reply]

It seems my memories were blurry... thanks for correcting me.

Nageh (talk) 20:59, 8 June 2009 (UTC)[reply]

My (rather limited) understanding of LDPC is that the bipartite graph viewpoint and the parity-matrix viewpoint are equivalent (it's just a mapping between codeword bits and parity constraints), therefore all linear block codes have one. In the case of LDPC, however, the sparsity of the parity matrix leads to a sparse graph, which in turn leads to an efficient decoder. So I'm still not convinced that MDPC is especially relevant, and would still be reluctant to include this without some authoritative reference. Oli Filth^{(talk|contribs)} 15:31, 8 June 2009 (UTC)[reply]

All linear block codes may be modeled as bipartite graphs, sure. But the point is: how do you construct the codes? If you take the graph approach, this is what would be called LDPC codes. Other codes, e.g. RS codes, take other approaches, such as polynomial interpolation.

I agree with you regarding MDPC. As I said before, it seems very stretched to view MDPC codes as constructed via bipartite graphs, since the original intention was likely simply to compute single parity bits over rows and columns in a hypercube. I suggest leaving mentioning MDPC codes out, or otherwise, if there is an appropriate place (subjective) in the article, then it should only say that "MDPC codes may be viewed as simple regular LDPC codes".

Edit: I rather vote for removing the reference to MDPC codes.

Nageh (talk) 16:59, 8 June 2009 (UTC)[reply]

I see your point on why LDPC construction is special, and I think we agree that it means that MDPC is no more relevant than any other code construction. Oli Filth^{(talk|contribs)} 18:46, 8 June 2009 (UTC)[reply]

Regarding randomness, I do not recall randomness being a central criterion in the definition of LDPC codes; in fact, you could very well construct low-density parity check matrices algebraically and deterministically, it's just that randomized constructions turn out to be superior.

Nageh (talk) 09:14, 8 June 2009 (UTC)[reply]

@ User:78.42.25.227

I am confused by your recent edit... In the parity-check matrix, there will be either 1's or 0's. The null space of the matrix defines the graph. I don't see why there should be "probabilities" in the matrix for syndrome computation. And syndrome computation tells you normally whether decoding was correct (syndrome is 0) or not (not 0). Please justify your edit (or anyone else), either on the talk page or as a reference, or I will revert your edit. Thanks, cheers, Nageh (talk) 18:14, 20 October 2009 (UTC)[reply]

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. —Preceding unsigned comment added by Cunchem (talk • contribs) 07:39, 21 October 2009 (UTC)[reply]

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 — Preceding unsigned comment added by 101.178.141.19 (talk) 00:54, 27 September 2015 (UTC)[reply]

"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]

Markovisch (talk • contribs) 01:02, 27 March 2017 (UTC)[reply]

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 my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

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

This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 5 June 2024).

If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—InternetArchiveBot (Report bug) 14:14, 7 January 2018 (UTC)[reply]

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.

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

^ http://www.inference.phy.cam.ac.uk/mackay/gallager/papers/

[1] ttp://www.inference.phy.cam.ac.uk/mackay/gallager/papers/

[1]