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.