Tree Matrix Algorithm of LDPC Codes
- 1 Electronics and Information Engineering Institute, Foshan University, Foshan, China
Abstract
LDPC codes are finding increasing use in applications requiring reliable and highly efficient information transfer over bandwidth. An LDPC code is defined by a sparse parity-check matrix and can be described by a bipartite graph called Tanner graph. Loops in Tanner graph prevent the sum-product algorithm from converging. Further, loops, especially short loops, degrade the performance of LDPC decoder, because they affect the independence of the extrinsic information exchanged in the iterative decoding. This paper, by graph theory, deduces cut-node tree graph of LDPC code, and depicts it with matrix. On the basis of tree matrix algorithm, whole depictions of loops can be figured out, providing of foundation for further research of relations between loops and LDPC codes’ performance.
- Gallager, R.G. (1963) Low-Density Parity Check Codes. MIT Press, Cambridge.
- Mackay, D.J.C. (1999) Good Error-Correcting Codes Based on Very Sparse Matrices. IEEE Transactions on Information Theory, 45, 399-431. http://dx.doi.org/10.1109/18.748992
- Tanner, R.M. (1981) A Recursive Approach to Low Complexity Codes. IEEE Transactions on Information Theory, 27, 533-547. http://dx.doi.org/10.1109/TIT.1981.1056404
- Kschischang, R., Frey, B.J. and Loeliger, H.A. (2001) Factor Graphs and the Sum-Product Algorithm. IEEE Transactions on Information Theory, 47, 498-519. http://dx.doi.org/10.1109/18.910572
- Wiberg, N. (1996) Codes and Decoding on General Graphs, Linkoping Studies in Science and Technology. Ph.D. Dissertation, No. 440, Linkoping University, Linkoping.
- Reinhard, D. (1997) Graph Theory. Springer-Verlag, New York.
- Wainwright, M.J. (2007) Sparse Graph Codes for Side Information and Binning. IEEE Signal Processing Magazine, 47, 47-57.
- Forney Jr., G.D. (2001) Codes on Graphs: Normal Realizations. IEEE Transactions on Information Theory, 47, 520-548. http://dx.doi.org/10.1109/18.910573
- Loeliger, H.A. (2004) An Introduction to Factor Graph. IEEE Signal Processing Magazine, 28-41.
- Kschischang, F.R. (2003) Codes Defined on Graphs. IEEE Communications Magazine, 118-125.
- Vontobel, P.O. (2004) A Factor-Graph Approach to the Context-Tree Weighting Method. Proceedings of the Data Compression Conference (DCC’04), 571.
- Wainwright, M., Jaakkola, T. and Willsky, A. (2002) Tree-Based Reparameterization Analysis of Belief Propagation and Related Algorithms for Approximate Inference on Graphs with Cycles. ISIT2002, Lausanne, 30 June-5 July 2002.