基于矩阵译码算法的改进研究
|
摘要
编码理论最早始于通信领域,而纠删码最初是为了解决网络传输问题中多址传送而提出来的。后来人们开始将编码理论应用于一些不同的领域,例如存储系统。将纠删码作为一种容错技术应用于存储系统,可以在降低存储空间消耗的同时提供接近于复制备份的容错能力。对于纠删码而言,最重要的是编解码算法。每一类纠删码都有各自对应的解码算法,同时也有很多优秀的通用性解码算法,例如:矩阵译码算法和归并译码算法等,就可以适用于任意纠删码,尤其适用于阵列码。将针对矩阵译码算法进行描述,并对于矩阵译码算法的不足之处进行改进研究,最后经过试验得出其效率对比矩阵译码算法确实有提高,其拥有更简便的实用性。
The coding theory begins in the communication field,and the erasure code is originally proposed solving the multiple access transmission in the network transmission problem. Later,people began to apply coding theory to a number of diverse fields,such as storage systems. The erasure code is applicable to the storage system as a fault-tolerant technology,which can reduce the storage space consumption and provide fault tolerance close to the copy backup. The most important thing is the encoding and decoding algorithms for erasure code. Each class of erasure codes has their corresponding decoding algorithms. Meanwhile,there are many excellent general decoding algorithms,such as matrix decoding algorithm and merge decoding algorithm,which can be applicable to any erasure code,especially for array codes. In this paper,we described the matrix decoding algorithm,and researched for the improvement of the matrix decoding algorithm. It is concluded that the efficiency comparison matrix decoding algorithm has been enhanced by experiment,and it has a more simple and practical application.
The coding theory begins in the communication field,and the erasure code is originally proposed solving the multiple access transmission in the network transmission problem. Later,people began to apply coding theory to a number of diverse fields,such as storage systems. The erasure code is applicable to the storage system as a fault-tolerant technology,which can reduce the storage space consumption and provide fault tolerance close to the copy backup. The most important thing is the encoding and decoding algorithms for erasure code. Each class of erasure codes has their corresponding decoding algorithms. Meanwhile,there are many excellent general decoding algorithms,such as matrix decoding algorithm and merge decoding algorithm,which can be applicable to any erasure code,especially for array codes. In this paper,we described the matrix decoding algorithm,and researched for the improvement of the matrix decoding algorithm. It is concluded that the efficiency comparison matrix decoding algorithm has been enhanced by experiment,and it has a more simple and practical application.
引文
[1]Shannon C E.A mathematical theory of communication[J].Bell Labs Technical Journal,1948,27(4):379-423.
[2]Rizzo L.Effective erasure codes for reliable computer communication protocols[J].ACM SIGCOMM Computer Communication Review,1997,27(2):24-36.
[3]Tang Dan.Research of Methods for Lost Data Reconstruction in Erasure Codes over Binary Fields[J].Journal of electronic science and technology,2016,14(1):43-48.
[4]Hafner J L,Deenadhayalan V,Rao K K,et al.Matrix methods for lost data reconstruction in erasure codes[C]//Conference on Usenix Conference on File&Storage Technologies.2005:14-14.
[5]Hafner J L,Deenadhayalan V,Kanungo T,et al.Performance metrics for erasure codes in storage systems[J].Chaos An Interdisciplinary Journal of Nonlinear Science,2004,18(3):150-156.
[6]Huang C,Xu L.STAR:An efficient coding scheme for correcting triple storage Technologies[Z].Berkeley,CA:USE-NIX Association,2008:97-110.
[7]Blaum M,Brady J,Bruck J,et al.EVENODD:an optimal scheme for tolerating double disk failures in RAID architectures[J].IEEE Transactions on Computers,1995,44(2):245-254.
[8]Corbett P,English B,Goel A,et al.Row-diagonal parity for double disk failure correction[C]//Proceedings of the 3rd USENIX conference on File and storage technologies.USE-NIX Association,2004:1-1.
[2]Rizzo L.Effective erasure codes for reliable computer communication protocols[J].ACM SIGCOMM Computer Communication Review,1997,27(2):24-36.
[3]Tang Dan.Research of Methods for Lost Data Reconstruction in Erasure Codes over Binary Fields[J].Journal of electronic science and technology,2016,14(1):43-48.
[4]Hafner J L,Deenadhayalan V,Rao K K,et al.Matrix methods for lost data reconstruction in erasure codes[C]//Conference on Usenix Conference on File&Storage Technologies.2005:14-14.
[5]Hafner J L,Deenadhayalan V,Kanungo T,et al.Performance metrics for erasure codes in storage systems[J].Chaos An Interdisciplinary Journal of Nonlinear Science,2004,18(3):150-156.
[6]Huang C,Xu L.STAR:An efficient coding scheme for correcting triple storage Technologies[Z].Berkeley,CA:USE-NIX Association,2008:97-110.
[7]Blaum M,Brady J,Bruck J,et al.EVENODD:an optimal scheme for tolerating double disk failures in RAID architectures[J].IEEE Transactions on Computers,1995,44(2):245-254.
[8]Corbett P,English B,Goel A,et al.Row-diagonal parity for double disk failure correction[C]//Proceedings of the 3rd USENIX conference on File and storage technologies.USE-NIX Association,2004:1-1.