Lossy Source Compression Using Belief Propagation with Decimation over Multi-Edge Type Factor Graphs of LDGM Codes

Abstract:

A low complexity approach for binary quantization is proposed. This approach uses a multi-edge type bipartite graph of the low density generator matrix (LDGM) code with the belief propagation algorithm to encode the informations. A damping decimation is developed for the algorithm convergence. Simulation results show that our algorithm achieves near Shannon capacity performance with reduced complexity.

• Periodical: Applied Mechanics and Materials (Volume 610)
• Pages: 437-442
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.610.437
• Online since: August 2014
• Authors: Wu Guan*, Li Ping Liang
• Keywords: Belief Propagation (BP), Decimation, Lossy Source Compression, Low-Density Generator Matrix (LDGM) Codes, Multi-Edge Type

References

[1] J. Fridrich, T. Filler, Practical methods for minimizing embedding impact in steganography, in Proceedings SPIE Electronic Imaging, Security, Steganography, and Watermarking of Multimedia Contents IX. San Jose, CA (2007) 02. 1–02. 15.

DOI: 10.1117/12.697471

[2] T.M. Cover, J.A. Thomas, Elements of Information Theory, 2nd ed., John Wiley and Sons Inc., (2006).

[3] Y. Matsunaga, H. Yamamoto, A coding theorem for lossy data compression by LDPC codes, IEEE Transaction on Information Theory. 49. 9 (2003) 2225-2229.

DOI: 10.1109/tit.2003.815805

[4] E. Martinian, J.S. Yedidia, Iterative quantization using codes on graphs, in Allerton Conference on Communications, Control, and Computing. (2003).

[5] T. Filler, J.J. Fridrich, Binary quantization using belief propagation with decimation over factor graphs of ldgm codes, in Allerton Conference on Communications, Control, and Computing. (2007).

[6] M.J. Wainwright, E.N. Maneva, E. Martinian, Lossy Source Compression Using Low-Density Generator Matrix Codes: Analysis and Algorithms, IEEE Transaction on Information Theory. 56. 3 (2010) 1351-1668.

DOI: 10.1109/tit.2009.2039160

[7] P. Günther, D. Schnfeld, A. Winkler, Efficient Implementation of Belief Propagation for Lossy Source Compression with LDGM Codes, in International ITG Conference on Source and Channel Coding (SCC). TU Dresden, Germany (2008) 1-6.

[8] H.A. Loeliger, F.R. Kschischang, B.J. Frey, Factor graphs and the sum-product algorithm, IEEE Transaction on Information Theory. 47. 2 (2001) 498–519.

DOI: 10.1109/18.910572

[9] T.J. Richardson, R.L. Urbanke, Multi-edge type LDPC codes, http: /www. epfl. ch/papers/ multiedge. ps.

[10] W. Guan, H. Xiang, Decoding and Design of LDPC codes for High-Order Modulations, Wireless Pers Commun. 56. 2 (2011) 237-253.

DOI: 10.1007/s11277-009-9830-0

[11] L. Cappellari, Lossy Source Compression of Non-Uniform Binary Source Using GQ-LDGM Codes, ITW, Dublin (2010).

DOI: 10.1109/cig.2010.5592821