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

LPDC（低密度奇偶校验）码是一种纠错码，由Gallager于1962年首次提出。近年来，随着计算机能力的快速增长，BP（belief propagation）或其他重复译码算法开始适用于LDPC码。在本研究中，我们将LODC码应用于有失真的数据压缩，并对其性能进行了评价。2002年，我们提出了一种将LODC编码应用于失真数据压缩的编码算法。进一步，我们证明了存在一种LODC码可以达到理论最优速率，即速率失真函数。2003年，我们改进了证明，并将结果发表在IEEE信息理论学报上。在编码定理中，证明了对于码长为n的LODC码的奇偶校验矩阵中的列权t满足t=O(log n)，则该码可以渐近地获得率失真函数。进一步，如果t= 0 (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.