面向大容量数据实时传输的块间4纠删编码

doi:1000-436X(2012)06-0040-10

摘要/Abstract

摘要：

现有纠删编码由于编解码运算复杂度及编码数据大小的限制，很难适用于面向大容量数据块或数据分组的实时传输中。在奇偶校验码的基础上，结合有限域GF(2＜sup＞8＜/sup＞)域的特性，提出一种新的面向大容量数据块实时传输的块间4纠删编码方案。该编码方案对一组连续的数据块使用4个冗余数据块，即可容忍任意4个数据块同时差错。编解码运算的复杂度与数据块的大小成线性关系，对数据块的大小没有限制。编码具有MDS性质，在同等冗余条件下达到最佳的纠删能力。理论和实验分析表明：该编码方案最大能够对连续27个数据块进行块间纠删编码。

关键词: 纠删编码, 大容量数据, 奇偶校验码, GF(2＜sup＞8＜/sup＞)域, MDS

Abstract:

Most of the existing erasure-correcting codes were limited by encoding/decoding complexities and encoded data size.They were not suitable for use in the real-time applications that orient bulk data based on blocks or packages.Therefore,a novel inter-block 4-erasure-correcting coding scheme for real-time bulk data transfer was presented.Based on single parity-check codes incorporated with the features of GF(2＜sup＞8＜/sup＞)field in finite field,the present coding scheme could tolerate simultaneous failures of four blocks with only four redundancy blocks for a group of continuous data.Meanwhile,its encoding/decoding complexities had linear relationship with respect to the size of data blocks and it supported arbitrary size of data.Furthermore,it was proved to have MDS property,thus achieving optimal erasure-correcting capability with the same redundancy information.Theoretical and experimental analysis showed that the present coding scheme could code with 27 continuous data blocks at most.

Key words: erasure-correcting codes, bulk data, parity-check codes, GF(2＜sup＞8＜/sup＞)field, MDS

陈钢,朱俊峰,张世乐,吴百锋. 面向大容量数据实时传输的块间4纠删编码[J]. 通信学报, 2012, 33(6): 40-49.

Gang CHEN,Jun-feng ZHU,Shi-le ZHANG,Bai-feng WU. Inter-block 4-erasure-correcting coding scheme for real-time bulk data transfer[J]. Journal on Communications, 2012, 33(6): 40-49.

图/表 7

表1

图1

图2

图3

图4

图5

表2

参考文献 26

[1]	COSTELLO D J , HAGENAUER J , IMAI H ,et al. Applications of error-control coding[J]. IEEE Transactions on Information Theory, 1998,44(6): 2531-2560.
[2]	FLOYD S , JACOBSON V , MCCANNE S ,et al. A reliable multicast framework for light-weight sessions and application level framing[J]. IEEE/ACM Transactions on Networking, 1997,5(6): 784-803.
[3]	LIN J C , PAUL S . RMTP:A Reliable multicast transport protocol[A]. IEEE INFOCOM1996[C]. San Francisco,CA,USA, 1996. 1414-1424.
[4]	MCCANNE S , JACOBSON V , VETTERLI M . Receiver driven layered multicast[A]. IEEE INFOCOM1996[C]. San Francisco,CA,USA, 1996. 117-130.
[5]	RIZZO L . Effective erasure codes for reliable computer communication protocols[J]. ACM Computer Communication Review, 1997,27(2): 24-36.
[6]	REED I , SOLOMON G . Polynomial codes over certain finite fields[J]. Journal of the SIAM, 1960,8(2): 300-304.
[7]	BYERS J W , LUBY M , MITZENMACHER M ,et al. A digital fountain approach to reliable distribution of bulk data[J]. IEEE Journal on Selected Areas in Communications, 2002,20(8): 1528-1540.
[8]	PATTERSON D A , GIBSON G A , KATZ R H . A case for redundant arrays of inexpensive disks(RAID)[A]. ACM SIGMOD1988[C]. New York,NY,USA, 1988. 109-116.
[9]	PLANK J S , XU L . Optimizing Cauchy Reed-Solomon codes for fault-tolerant network storage applications[A]. IEEE NCA2006[C]. Cambridge,MA, 2006. 173-180.
[10]	BLAUM M , BRADY J , BRUCK J ,et al. EVENODD:an efficient scheme for tolerating double disk failures in raid architectures[J]. IEEE Transactions on Computers, 1995,44(2): 192-202.
[11]	XU L , BRUCK J . X-Code:MDS array codes with optimal encoding[J]. IEEE Transactions on Information Theory, 1999,45(1): 272-275.
[12]	XU L , BOHOSSIAN V , BRUCK J ,et al. Low density MDS codes and factors of complete graphs[J]. IEEE Transactions on Information Theory, 1999,45(6): 1817-1826.
[13]	HAFNER J L . HoVer Erasure Codes for Disk Arrays[R]. IBM Research Division,FJ10352(A0507-015), 2005.
[14]	HAFNER J L . WEAVER codes:Highly fault tolerant erasure codes for storage systems[A]. ACM FAST2005[C]. Berkeley,CA,USA, 2005. 211-224.
[15]	MACWILLIAMS F J , SLOANE N J A . The Theory of Error Correcting Codes[M]. North-holland Publishing Company, 1977.
[16]	FENG G L , DENG R , BAO F ,et al. New efficient MDS array codes for RAID,part I:reed Solomon like codes for tolerating three disk failures[J]. IEEE Transactions on Computers, 2005,54(9): 1071-1080.
[17]	FENG G L , DENG R , BAO F ,et al. New efficient MDS array codes for RAID,part II:rabin like codes for toleranting multiple(4)disk failures[J]. IEEE Transactions on Computers, 2005,54(12): 1473-1482.
[18]	MORELOS Z , ROBERT H . The Art of Error Correcting Coding[M]. John Wiley＆Sons Inc, 2006.
[19]	胡飞, 朱耀庭, 朱光喜 . 基于Galois域Reed-Sololmon码的数据分组层FEC编码软件实现[J]. 通信学报, 2003,23(3): 57-64. HU F , ZHU Y T , ZHU G X . A software implementation of packet-level FEC coding based on Reed-Solomon code over Galois field[J]. Journal on Communications, 2003,23(3): 57-64.
[20]	万武南, 吴震, 陈运 ,等. 一种基于3容错阵列码的RAID数据布局[J]. 计算机学报, 2007,30(10): 1721-1730. WAN W N , WU Z , CHEN Y ,et al. A data placement based on toleration on triple failures array codes in RAID[J]. Chinese Journal of Computers, 2007,30(10): 1721-1730.
[21]	LACAN J , FIMES J . Systematic MDS erasure codes based on Vandermonde matrices[J]. IEEE Communications Letters, 2004,8(9): 570-572.
[22]	AL-SHAIKHI A A , ILOW J . Packet loss recovery codes based on Vandermonde matrices and shift operators[A]. IEEE ISIT2008[C]. Toronto,ON,Canada, 2008. 1058-1062.
[23]	万哲先 . 代数和编码(第三版)[M]. 北京: 高等教育出版社, 2007. WAN Z X . Algebra and Coding[M]. Beijing: Higher Education PressPress, 2007.
[24]	刘建中 . 范德蒙行列式的一个性质的证明及其应用[J]. 河北大学学报(自然科学版), 2000,20(1): 83-85. LIU J Z . The proof of a property of Vandermonde determinant and applications[J]. Journal of Hebei University, 2000,20(1): 83-85.
[25]	HUANG C , XU L . Fast Software Implementations of Finite Field Operation[R]. Washington University, 2003.
[26]	董欢庆, 李战怀, 林伟 . RAID-VCR:一种能够承受三个磁盘故障的RAID结构[J]. 计算机学报, 2006,29(5): 792-800. DONG H Q , LI Z H , LIN W . RAID-VCR:A new RAID architecture for tolerating triple disk failures[J]. Chinese Journal of Computers, 2006,29(5): 792-800.

编码方案	编码效率	容忍数据块个数	复杂度
EVENODD	k/(k+2)	2	O(n²)
VCR	k/(k+3)	3	O(n²)
本文编码	k/(k+4)	4	O(n)