Applications of low density party check codes to data compression with distortion

LPDC（低密度奇偶校验）码是由Gallager在1962年首次提出的纠错码。近年来，由于计算机能力的快速增长，BP（置信传播）或其他重复解码算法变得适用于LDPC码。在本研究中，我们将LODC码应用于有失真的资料压缩，并评估其效能，在2002年，我们提出一种将LODC码应用于有失真资料压缩的编码演算法。进一步证明了存在一种LODC码可以达到理论上的最优码率，即，率失真函数在2003年，我们改进了证明，并发表在IEEE信息论交易的结果。在编码定理中，证明了对于码长n，若LODC码的校验矩阵的列权t满足t=O（logn），则该码可渐近地达到率失真函数。当t=O（n）时，它指数收敛于率失真函数，并通过仿真证明了在率失真编码情况下，LPDC码的BP纠错算法不能获得很好的性能。

A LPDC(low density parity check) code is an error correcting code that was first proposed by Gallager in 1962. Recently, BP(belief propagation) or other repeating decoding algorithms become applicable to the LDPC codes by rapid growth of computer power. In this research, we applied the LODC codes to data compression with distortion, and evaluated the performance.In 2002, we proposed an encoding algorithm to apply the LODC codes to data compression with distortion. Furthermore, we proved that there exits a LODC codes that can attain the theoretical optimal rate, i.e., rate-distortion function. In 2003, we improved the proof and published the results in the IEEE transactions on Information Theory. In the coding theorem, it is shown that if column weight t in the parity check matrix of a LODC codes satisfies t=O(log n) for code length n, the code can attain the rate-distortion function asymptotically. Furthermore, if t=O(n), then it converge to the rate-distortion function exponentially.We also show by simulation that the BP algorithm of LPDC codes for error correcting cannot attain a good performance in the case of rate-distortion coding.