Robustness of Source Coding

在某些情况下，例如在移动的通信中，需要通过噪声很大的信道发送压缩数据。 除非使用非常强大的差错控制编码技术，否则对于噪声很大的信道，误解码差错概率通常很高。由于使用非常强大的差错控制编码技术将抵消数据压缩中获得的大部分增益，这不是我们愿意做的。 另一方面，大多数有效的数据压缩算法对信道差错非常敏感。高解码错误概率与压缩算法的灾难性行为之间的矛盾是研究压缩数据在强噪声信道中传输需要解决的主要问题。 在这个项目中，我们正在研究解决这个问题的另一种方法。 我们不使用小块长度的源代码或强大的差错控制编码技术，而是开发鲁棒的数据压缩算法-对信道差错不敏感的算法。本文给出了无损数据压缩鲁棒性的两种定义--渐近平均鲁棒性和渐近平均半鲁棒性。我们使用的最重要的失真度量是汉明距离和所谓的插入-删除距离。在这个项目中，我们建议 1)研究渐近平均鲁棒无损数据压缩算法的存在性，该算法也是渐近最优的; 2）开发实用的渐近平均鲁棒（半鲁棒）无损数据压缩算法; 3）研究渐近平均鲁棒（半鲁棒）无损数据压缩算法的各种重要性质。

Under certain circumstances such as in mobile communication, one needs to transmit compressed data through a very noisy channel. Unless a very powerful error control coding technique is used, the misdecoding error probability for a very noisy channel is usually high. Since the use of very powerful error control coding technique will offset a large part of the gain obtained in data compression, this is not what we are willing to do. On the other hand, most of the efficient data compression algorithms are very sensitive to channel errors. The contradiction between high decoding error probability and catastrophic behavior of compression algorithms is the main problem we need to resolve in the study of transmission of compressed data through very noisy channels. In this project, we are examining an alternative approach to this problem. Instead of using source codes of small block length, or powerful error control coding techniques, we are developing robust data compression algorithms - algorithms which are insensitive to channel errors. We give two definitions of robustness of lossless data compression - the asymptotical mean robustness and the asymptotical mean semi-robustness - defined with respect to certain distortion measures. The most important distortion measures we use are Hamming distance and the so-called insertion-deletion distance. In this project, we propose 1) to study the existence of asymptotical mean robust lossless data compression algorithm that is also asymptotically optimal; 2) to develop practical asymptotically mean robust (semi-robust) lossless data compression algorithms; 3) to study various important properties of asymptotically mean robust (semi-robust) lossless data compression algorithms.