Lossy Source Compression of Non-Uniform Binary Source via Reinforced Belief Propagation over GQ-LDGM Codes

ETRI Journal

关键词: belief propagation;    LDGM codes;    lossy compression;    Source coding;   

Others  :  1185883
DOI  :  10.4218/etrij.10.0210.0204

【 摘 要 】

In this letter, we consider the lossy coding of a non-uniform binary source based on GF(q)-quantized low-density generator matrix (LDGM) codes with check degree d_c=2. By quantizing the GF(q) LDGM codeword, a non-uniform binary codeword can be obtained, which is suitable for direct quantization of the non-uniform binary source. Encoding is performed by reinforced belief propagation, a variant of belief propagation. Simulation results show that the performance of our method is quite close to the theoretic rate-distortion bounds. For example, when the GF(16)-LDGM code with a rate of 0.4 and block-length of 1,500 is used to compress the non-uniform binary source with probability of 1 being 0.23, the distortion is 0.091, which is very close to the optimal theoretical value of 0.074.

   

【 参考文献 】

• [1]A. Braunstein, M. Mézard, and R. Zecchina, "Survey Propagation: An Algorithm for Satisfiability," Random Structures and Algorithms, vol. 27, no. 2, Sept. 2005, pp. 201-226.
• [2]E. Martinian and J. Yedidia, "Iterative Quantization Using Codes on Graphs," Proc. Allerton Conf. Commun., Control, Computing, Monticello, IL, USA, 2003, pp. 110-122.
• [3]T. Murayama, "Thouless-Anderson-Palmer Approach for Lossy Compression," J. Phys. Rev. E: Stat. Nonlin. Soft Matter Phys., vol. 69, 2004, p.R035105.
• [4]M. J. Wainwright, E. Maneva, and E. Martinian, "Lossy Source Compression Using Low-Density Generator Matrix Codes: Analysis and Algorithms," IEEE Trans. Inf. Theory, vol. 56, no. 3, June 2010, pp. 1351-1368.
• [5]S. Ciliberti, M. Mézard, and R. Zecchina, "Lossy Data Compression with Random Gates," Phys. Rev. Lett., vol. 95, 2005, p. 038701.
• [6]T. Filler and J. Fridrich, "Binary Quantization Using Belief Propagation with Decimation over Factor Graphs of LDGM Codes," Proc. Allerton Conf. Commun., Control, Computing, Monticello, IL, USA, 2007, pp. 495-501.
• [7]P.A. Regalia, "A Modified Belief Propagation Algorithm for Code Word Quantization," IEEE Trans. Commun., vol. 57, no. 12, Dec. 2009, pp. 3513-3517.
• [8]L. Cappellari, "Lossy Source Compression of Non-Uniform Binary Source Using GQ-LDGM Codes," ITW, Dublin, 2010, available: arXiv:1004.2628.
• [9]Z. Sun et al., "Lossy Source Compression for Non-Uniform Sources Using LDGM Codes," 24th Queen’s Biennial Symp. Commun., Kingston, Ontario, Canada, June 2008.
• [10]A. Braunstein et al., "Encoding for the Blackwell Channel with Reinforced Belief Propagation," Proc. IEEE Int. Symp. Inform. Theory, Nice, 2007, pp. 1891-1895.
• [11]X.-Y. Hu, Low-Density Low-Complexity Error-Correcting Codes on Sparse Graphs, Doctoral dissertation, Swiss Federal Institute of Technology Lausanne (EPFL), 2002.
• [12]A. Braunstein, F. Kayhan, and R. Zecchina, "Efficient LDPC Codes over GF(q) for Lossy Data Compression," Proc. IEEE Int. Symp. Inform. Theory, Seoul, Korea, 2009, pp. 1978-1982.
• [13]X.-Y. Hu, E. Eleftheriou, and D.M. Arnold, "Regular and Irregular Progressive Edge-Growth Tanner Graphs," IEEE Trans. Inform. Theory, vol. 51, no. 1, Jan. 2005, pp. 386-398.