Content deleted Content added
→Start again: sort my reply out |
|||
Line 187:
:::: 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.
:::::: In the original article of Gallager<ref> http://www.inference.phy.cam.ac.uk/mackay/gallager/papers/</ref>, after anylising the performances of LDPC under Maximum Likelihood decoding, he introduces 2 algorithms in part 4 that are in fact iterative algorithm. He says that this algorithms are suboptimal but have a low complexity. Maybe you were refering at the matrix multiplication for the encoding. [[User:Cunchem|Cunchem]] ([[User talk:Cunchem|talk]]) 19:54, 8 June 2009 (UTC)
:::: 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]]<sup>([[User talk:Oli Filth|talk]]<nowiki>|</nowiki>[[Special:Contributions/Oli_Filth|contribs]])</sup> 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.
| |||