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

Revision as of 15:49, 8 June 2009

Revision as of 16:59, 8 June 2009

Line 181:

:::: 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 that LDPC are also characterized by there ability to be efficiently decoded by a low complexity iterative decoding algorithm. [[User:Cunchem|Cunchem]] ([[User talk:Cunchem|talk]]) 14:54, 8 June 2009 (UTC)

::::: 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.

:::: 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. [[User:Oli Filth|Oli Filth]]^{([[User talk:Oli Filth|talk]]<nowiki>|</nowiki>[[Special:Contributions/Oli_Filth|contribs]])} 15:31, 8 June 2009 (UTC)

::::: 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".

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

: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.