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

LPDC(Low Density Parity Check，低密度奇偶校验)码是由Gallager于1962年首次提出的纠错码。近年来，随着计算机运算能力的快速增长，BP等重复译码算法开始应用于LDPC码。在本研究中，我们将LODC码应用于失真数据压缩，并对其性能进行了评估。2002年，我们提出了一种将LODC码应用于失真数据压缩的编码算法。此外，我们还证明了存在一个LODC码，它可以达到理论上的最优码率，即率失真函数。2003年，我们改进了证明，并将结果发表在IEEE信息理论学报上。在编码定理中，证明了如果LODC码的奇偶校验矩阵中的列权t对于码长n满足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.