最优局部修复码的构造

局部修复码(Locally Repairable Codes, LRCs)作为纠删码的一种,被广泛应用于分布式存储系统中。针对目前局部修复码在满足最小距离最优界时码率不高且局部性的参数限制大的问题,本文提出一种基于方形网络的最优局部修复码构造方法,利用方形网络构造局部修复码的校验矩阵,从校验矩阵入手构造局部修复码,达到了最优码率界,但是其局部性不高。进一步将方形网络水平方向和垂直方向上的关联矩阵进行扩展,所构造的局部修复码在局部性上的性能有所提升。和现有局部修复码进行对比分析,构造的局部修复码不仅满足最小距离最优界,同时达到了局部修复码的码率最优界,可适用于任意局部性的情况,对二元最优局部修复码的构造具有借鉴意义。     

基于sunflower的局部修复码构造

针对目前构造达到C-M界的二元局部修复码（LRC）的相关研究已经较为充分,但在一般域上还相对较少的问题,研究了一般域上LRC的构造。首先,提出了通过射影几何理论确定sunflower中元素个数的方法。其次,通过不相交局部修复组刻画LRC,从而清楚地描述LRC的码长、维数和局部度等参数。最后,在具有不相交局部修复组的校验矩阵的基础上,利用sunflower构造了两类一般域上最小距离为6的LRC,其中很多LRC是最优或拟最优的。相较于现有利用子域子码、广义级联码和代数曲线等方法构造的LRC,所构造得到的两类码在相同的码的最小距离和局部度下提升了信息率。这些结果说明所提方法可应用于一般域上其他LRC的构造。     

基于循环差集的低密度奇偶校验码的构造

基于组合设计中的循环差集,提出一种构造准循环低密度校验(Quasi-Cyclic LDPC)码的方法。所构造的正则Quasi-Cyclic LDPC码的校验矩阵中不存在长度为4的环,并且可以用简单线性移位寄存器实现编码。仿真结果表明,在和积迭代译码下,采用该方法构造的码具有较好的性能。     

高性能准循环LDPC码构造方法的改进

高性能准循环低密度奇偶校验码构造的1/2码率的码的度分布存在一定局限性。针对该问题,重新布置校验矩阵中单位循环移位矩阵的分布,改进构造校验矩阵的方法。仿真结果表明,改进方法具有有效的编码算法,使度分布能满足1/2码率的最佳度分布,且能在同等码长的情况下得到更优的性能。     

高性能准循环LDPC码构造方法的改进

高性能准循环低密度奇偶校验码构造的1/2码率的码的度分布存在一定局限性。针对该问题,重新布置校验矩阵中单位循环移位矩阵的分布,改进构造校验矩阵的方法。仿真结果表明,改进方法具有有效的编码算法,使度分布能满足1/2码率的最佳度分布,且能在同等码长的情况下得到更优的性能。     

大围长结构化LDPC码构造方法

在LDPC码的构造中,校验矩阵拥有大围长对于改善码的性能有着重要的意义.结构化是提高码实用性的关键.提出一种低复杂度的基于列差搜索法(Column-Difference Search AIgorithm)的准循环LDPC码构造方法,用以设计大围长和任意码率的规则QC-LDPC码(以下称为CDS-LDPC码).该方法可线性编码,易于IC实现.仿真结果表明,该方法构造的各种码率CDS-LDPC码在BER性能上均优于对应的随机码,与同属QC-LDPC码的Tanner码和Array码相比明显提高了0.79～3.28dB,并且在码长、码率等参数设计上更为灵活.     

基于LTE-Advanced标准的LDPC码编码器设计与实现

针对LTE-Advanced标准,在分析其低密度奇偶校验(LDPC)码校验矩阵构造基础上,设计了一种低成本高吞吐率的准循环LDPC码编码器结构。通过分析校验矩阵的子矩阵结构,将整个校验矩阵划分为全零子矩阵及循环移位单位子矩阵的块状结构,进行串行编码。实验结果表明,与同类方法相比,设计的编码器编码时间约为同类最理想时间的32%,资源消耗约为同类最理想情况的33%,在编码时间和资源消耗上达到平衡,满足LTE-Advanced标准低成本高传输的要求。此外,改变校验矩阵存储单元的参数,可实现不同码长码率的LDPC码编码。     

面向卫星导航系统的多进制LDPC码的构造

面向卫星导航系统应用,设计一种性能优越且编码复杂度低的多进制低密度奇偶校验(LDPC)码。结合渐进边增长(PEG)算法与准循环扩展的半随机构造法,并优化非零元素的选择,构造与新一代卫星导航系统IS-GPS-800接口标准中参数一致的多进制LDPC码。进一步,通过将校验矩阵转换为重复累加码(RA)码的校验矩阵结构,实现低复杂度编码。仿真结果表明,与卫星导航系统IS-GPS-800接口标准中码长码率相同的二进制LDPC码相比,多进制LDPC码有明显的编码增益,且其编码复杂度较低。     

大列重低复杂度的QC-LDPC码构造

针对准循环低密度奇偶校验(QC-LDPC)码的校验矩阵列重较小,码率等参数不灵活的问题,该文提出了一种具有确定结构的大列重的构造方法。该方法利用指数矩阵元素之间差的关系,构造出的校验矩阵围长为8,具有准循环结构。在此基础上,使其与准双对角结构相结合,构造出的QC-LDPC码围长不会减小,且具有低复杂度可快速编码的双重特性。仿真结果显示在加性高斯白噪声(AWGN)和置信传播(BP)译码算法下,所提方法构造的QC-LDPC码在误码率为10e-6 时,信噪比优于GCD算法构造的QC-LDPC码接近 0.5dB,与随机构造法中经典的渐进边增长(PEG)算法相比,在误码率10e-5 时有0.2dB 的性能提升。     

码率自由且低误码平台QC-LDPC码的设计

为了提高无线通信系统的纠错能力,本文提出了一种可硬件实现的准循环低密度奇偶校验码的设计方法。这种方法通过改进密度进化算法得到任意码率的好的度分布对,然后采用改进后的PEG算法得到校验母矩阵,接着在置换序列填充校验母矩阵的过程中施加增大围长和ACE约束,使最后得到的QC-LDPC码不仅具有码率自由的优点,并且它的误码平台低。仿真结果表明采用本方法设计的QC-LDPC码与IEEE802.16e中对应码率的QC-LDPC码相比性能更好。     

异构部分重复码的构造

针对分布式存储系统部分重复(Fractional Repetition,FR)码大都是同构的问题,提出了基于Hadamard矩阵和基于[7,3,4]简单图形构造异构的FR码的两种新型构造设计算法,构造方法更加简洁.其中基于Hadamard矩阵构造存储容量异构的FR码可实现由同构经过简单变换为异构的编码方式;基于[7,3,4]简单图形构造可扩展异构FR码可实现扩展延伸.经过与RS码理论分析对比发现,设计的两种异构FR码的修复局部性、修复带宽开销进一步降低,且可以实现故障节点精确无编码修复,修复复杂度较低,修复效率较高,减少了修复故障节点的时间.     

分布式存储系统中的预测式纠删码研究

纠删码消耗的存储空间较少,获得的数据可靠性较高,因此被分布式存储系统广泛采用。但纠删码在修复数据时较高的修复成本限制了其应用。为了降低纠删码的修复成本,研究人员在分组码和再生码上进行了大量的研究。由于分组码和再生码属于被动容错方式,对于一些容易出现失效的节点,采用主动容错的方式能更好地降低修复成本,维护系统的可靠性,因此,提出了一种主动容错的预测式纠删(Proactive basic-Pyramid,PPyramid)码。PPyramid码利用硬盘故障预测方法来调整basic-Pyramid码中冗余块和数据块之间的关联,将预测出的即将出现故障的硬盘划分到同一小组,使得在修复数据时,所有的读取操作在小组内进行,从而减少读取数据块的个数,节省修复成本。在基于Ceph搭建的分布式存储系统中,在修复多个硬盘故障时,将PPyramid码与其他常用的纠删码进行对比。实验结果表明,相比basic-Pyramid码,PPyramid码能降低6.3%~34.9%的修复成本和减少7.6%~63.6%的修复时间,相比LRC码、pLRC码、SHEC码、DLRC码,能降低8.6%~52%的修复成本和减少10.8%~52.4%的修复时间。同时,PPyramid码构造灵活,具有很强的实际应用价值。     

分布式存储系统中的低修复成本纠删码

纠删码技术是分布式存储系统中典型的数据容错方法,与多副本技术相比,能够以较低的存储开销提供较高的数据可靠性;然而,纠删码修复成本过高的特点限制了其应用。针对现有纠删码修复成本高、编码复杂和灵活性差的问题,提出一种编码简单的低修复成本的纠删码——旋转分组修复码（RGRC）。RGRC首先将多个条带组合成条带集,然后利用条带之间的关联关系对条带集内的数据块进行分层旋转编码,以此得到相应的冗余块。RGRC大幅度地减少了单节点修复过程中所需要读取和传输的数据量,从而能节省大量的网络带宽资源。同时RGRC在解决单节点修复成本高的问题时,依然保留着较高的容错能力,且为满足分布式存储系统的不同需求,可以灵活地权衡系统的存储开销和修复成本。在分布式存储系统中进行的对比实验分析结果展示,与其他常用的RS（Reed-Solomon）码、LRC（Locally Repairable Codes）、basic-Pyramid、DLRC（Dynamic Local Reconstruction Codes）、pLRC（proactive Locally Repairable Codes）、GRC（Group Repairable Codes）、UFP-LRC（Unequal Failure Protection based Local Reconstruction Codes）相比,RGRC只需要增加少量的存储开销,就能降低单节点修复14%~61%的修复成本,同时减少14%~58%的修复时间。     

分布式存储系统中的低修复成本纠删码

纠删码技术是分布式存储系统中典型的数据容错方法，与多副本技术相比，能够以较低的存储开销提供较高的数据可靠性；然而，纠删码修复成本过高的特点限制了其应用。针对现有纠删码修复成本高、编码复杂和灵活性差的问题，提出一种编码简单的低修复成本的纠删码——旋转分组修复码（RGRC）。RGRC首先将多个条带组合成条带集，然后利用条带之间的关联关系对条带集内的数据块进行分层旋转编码，以此得到相应的冗余块。RGRC大幅度地减少了单节点修复过程中所需要读取和传输的数据量，从而能节省大量的网络带宽资源。同时RGRC在解决单节点修复成本高的问题时，依然保留着较高的容错能力，且为满足分布式存储系统的不同需求，可以灵活地权衡系统的存储开销和修复成本。在分布式存储系统中进行的对比实验分析结果展示，与其他常用的RS（Reed-Solomon）码、LRC（Locally Repairable Codes）、basic-Pyramid、DLRC（Dynamic Local Reconstruction Codes）、pLRC（proactive Locally Repairable Codes）、GRC（Group Repairable Codes）、UFP-LRC（Unequal Failure Protection based Local Reconstruction Codes）相比，RGRC只需要增加少量的存储开销，就能降低单节点修复14%~61%的修复成本，同时减少14%~58%的修复时间。     

基于差集的低密度校验码的构造

组合设计是构造好的低密度校验码的潜在有力工具,提出了利用差集来构造准循环低密度校验码（QC-LDPC）的新方法。该方法构造的QC-LDPC码,最小环长至少为6,码率的选择也具有很大的灵活性。由于其准循环结构,可以用简单线性移位寄存器完成编码。计算机仿真结果表明该方法构造的QC-LDPC码,在加性高斯白噪声信道中BPSK调制下用和积迭代译码性能很好。     

CRL: Efficient Concurrent Regeneration Codes with Local Reconstruction in Geo-Distributed Storage Systems

As a typical erasure coding choice, Reed-Solomon (RS) codes have such high repair cost that there is a penalty for high reliability and storage efficiency, thereby they are not suitable in geo-distributed storage systems. We present a novel family of concurrent regeneration codes with local reconstruction (CRL) in this paper. The CRL codes enjoy three benefits. Firstly, they are able to minimize the network bandwidth for node repair. Secondly, they can reduce the number of accessed nodes by calculating parities from a subset of data chunks and using an implied parity chunk. Thirdly, they are faster than existing erasure codes for reconstruction in geo-distributed storage systems. In addition, we demonstrate how the CRL codes overcome the limitations of the Reed-Solomon codes. We also illustrate analytically that they are excellent in the trade-off between chunk locality and minimum distance. Furthermore, we present theoretical analysis including latency analysis and reliability analysis for the CRL codes. By using quantity comparisons, we prove that CRL(6, 2, 2) is only 0.657x of Azure LRC(6, 2, 2), where there are six data chunks, two global parities, and two local parities, and CRL(10, 4, 2) is only 0.656x of HDFS-Xorbas(10, 4, 2), where there are 10 data chunks, four local parities, and two global parities respectively, in terms of data reconstruction times. Our experimental results show the performance of CRL by conducting performance evaluations in both two kinds of environments: 1) it is at least 57.25% and 66.85% more than its competitors in terms of encoding and decoding throughputs in memory, and 2) it has at least 1.46x and 1.21x higher encoding and decoding throughputs than its competitors in JBOD (Just a Bunch Of Disks). We also illustrate that CRL is 28.79% and 30.19% more than LRC on encoding and decoding throughputs in a geo-distributed environment.     

一类精确修复多个错误的Suh-Ramchandram码*

再生码因能有效的减少修复带宽更适用于分布式存储系统。利用干扰对齐技术,对于任意的参数 满足 且 ,Suh和Ramchandram构造了一类修复一个失效节点时,可达到最优修复带宽的最小存储再生码。 Chen和Shum证明了对于参数满足 的Suh-Ramchandram再生码,可以合作修复多个失效节点。基于Suh-Ramchandram再生码,给出了参数为 的编码结构,并说明这种参数为 的最小存储再生码为一类可修复多个失效节点的Suh-Ramchandram 再生码,而且这类码在修复单个或多个节点的失效时均可达到最优的修复带宽。     

可变码长LDPC码的GAU构造算法

考虑度分布、最小环长和环近似外信息度等因素,从减少短环和增加外信息度入手,提出了可变码长LDPC码的GAU(Girth ACE union)构造算法。该算法构造的校验矩阵能适应较大范围的码长变化,其短码的纠错性能与802.16e中的LDPC码相当,中长码的性能较后者略优。不同码长的码字具有结构相同的校验矩阵,便于编译码器对所有码长采用同一架构设计,能有效降低编译码器的实现复杂度。GA U算法适用于支持可变长度数据传输的各类通信系统的LDPC码设计,具有重要的理论意义和 实用价值。