论文部分内容阅读
近年来,为了提高分布式存储系统(Distributed Storage System,DSS)的修复效率,局部修复码(Locally Repairable Codes,LRC)被提出并已经实现应用。局部参数为r的LRC码是一种能由最多r个其他编码符号恢复任一编码符号的(n,k)纠删码。在DSS中使用二元局部修复码(Binary Locally Repairable Codes,BLRC),可以消除高代价的乘法计算,显著降低编码复杂度。目前,关于BLRC码的构造方面的研究得到了广泛关注,大量的研究提出最优的BLRC码构造方法,例如基于校验矩阵的构造,基于生成矩阵的构造,局部维度扩展构造等。本文在现有研究的基础上,提出一种基于校验矩阵的BLRC码构造方法。在BLRC码的译码方面,相关的研究较少。已有研究提出用低密度奇偶校验码(Low Density Parity-Check Codes,LDPC)构造BLRC码的方法,然而将BLRC码的译码算法与LDPC码相结合的研究较少。因此,本文结合两种码的共性,以LDPC码的译码算法实现了二进制删除信道(Binary Erasure Channel,BEC)下BLRC码的删除译码算法。本文主要研究BLRC码的构造和译码算法,主要创新点及研究内容如下:首先,本文提出一类最小距离d为4且(r+1)|n的基于校验矩阵的BLRC码的构造方法。在现有的基于校验矩阵的BLRC码构造中,校验矩阵的结构比较单一。为了研究不同结构的校验矩阵对BLRC码性能的影响,本文基于数学统计和分析,提出了一种更优的BLRC码校验矩阵的搜索算法。对于码参数相同而校验矩阵结构不同的BLRC码,可以通过该码对特定故障块的恢复百分比来表征其性能。通过仿真发现,本文构造的BLRC码在r∈{4,5}时对于特定故障块的恢复百分比相较于已有的BLRC码有所提高。其次,本文提出了BEC信道下的BLRC码的分布式译码算法。在BLRC码的删除译码算法的基础上,根据分布式系统的实际需求,进一步提出了一种BLRC码的分布式译码算法,该算法能够显著减少恢复故障节点所需的平均访问节点数。本文从串行和并行两个方面设计BLRC码的分布式译码算法。通过程序仿真,统计了特定个故障发生时,每种译码算法的平均访问节点数和故障修复率,并计算了不同删除概率下的误比特率(Bit Error Rate,BER)及误帧率(Frame Error Rate,FER)。仿真结果表明,相较于删除译码算法,无论是串行还是并行,分布式译码算法都能够显著降低恢复故障节点所需的平均访问节点数。