scientific article; zbMATH DE number 1775410
In 1963 Gallager introduces a family of codes based on sparse bipartite graphs, which he calls low-density parity-check codes. He suggests a natural decoding algorithm for these codes, and proves a good bound on the fraction of errors that can be corrected. As the codes that Gallager builds are derived from regular graphs, we refer to them as regular codes. Following the general approach introduced in \textit{M. Luby}, \textit{M. Mitzenmacher}, \textit{M. A. Shokrollahi}, \textit{D. A. Spielman} and \textit{V. Stemann} [Practical Loss-Resilient Codes, Proc. 29th Symp. on Theory of Computing, 150-159 (1997)] for the design and analysis of erasure codes, we consider error-correcting codes based on random irregular bipartite graphs, which we call irregular codes. We introduce tools based on linear programming for designing linear time irregular codes with better error-correcting capabilities than possible with regular codes. For example, the decoding algorithm for the rate \(1/2\) regular codes of Gallager can provably correct up to \(5.17\%\) errors asymptotically, whereas we have found irregular codes for which our decoding algorithm can provably correct up to \(6.27\%\) errors asymptotically. We include the results of simulations demonstrating the effectiveness of our codes on systems of reasonable size. For the entire collection see [Zbl 0988.00089].
- On the hardness of sampling independent sets beyond the tree threshold
- Multidimensional decoding networks for trapping set analysis
- Mildly nonlinear codes
- Weaknesses of Margulis and Ramanujan-Margulis low-density parity-check codes
- A class of quantum low-density parity check codes by combining seed graphs
- Regular and irregular progressive edge-growth tanner graphs
- The typical performance of irregular low-density generator-matrix codes for lossy compression
- A recursive approach to low complexity codes
- scientific article; zbMATH DE number 3559420 (Why is no real title available?)
- Efficient erasure correcting codes
- Improved low-density parity-check codes using irregular graphs
- Design of capacity-approaching irregular low-density parity-check codes
- Good error-correcting codes based on very sparse matrices
- Graph based linear error correcting codes
- The set of solutions of random XORSAT formulae
- Linear exact repair for dual decomposable codes
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4542543)