关于纠删码的研究与进展

RESEARCH AND DEVELOPMENT ON ERASURE CODES

该文简述了几类纠删码的纠删原理,系统地综合分析了各类纠删码的优缺点及其相互区别与联系,证明了若选取MDS(Maximal Distance Separable)码作为纠删码,只要接收者接收到源数据个数的数据,就能恢复原来的源数据。分析结果表明:复损码以及旋风(Tornado)码不仅能以线性时间可编码和可成功地译码,而且能以任意接近删除信道容量的速率进行传输,最后指出了目前复损码的研究中需要解决的一些问题,这些分析和结论为进一步研究纠删码提供了理论基础和新的思路。

This paper describes the principles of a few types of erasure codes, and analyzes their merits, drawbacks and relationships systematically. It is shown that if MDS codes are chosen as erasure codes, a receiver can reconstruct the original source data once it receives any portion of the encoding data equal to the length of the message. The analysis shows that loss-resilient codes and Tornado codes can not only be both encoded and decoded successfully in linear time, but also can come arbitrarily close to the channel capacity. Finally, some problems on loss-resilient codes which remain to be solved are presented. These analyses and conclusions provide theoretical base and new ideas for further studying erasure codes.