分布式存储中的再生码综述

分布式存储系统中通过引入冗余提高系统的可靠性,纠删码作为重要的冗余策略在分布式存储中得到越来越多的重视.分布式存储系统中,当某个存储节点失效后,需要引入新的节点来修复失效节点的数据.传统纠删码冗余策略在修复失效节点时需要传输的数据量较大近年来出现的再生码对传统纠删码进行改进以减少修复失效节点的带宽消耗.再生码引入网络编码的思想,在修复失效节点时,参与修复过程的节点首先将本节点内的数据作线性组合后再上传,最终修复带宽消耗最小 介绍了再生码的基本概念,然后介绍单节点修复再生码和合作修复再生码的编码策略,最后总结再生码的发展和研究方向     

基于网络编码的多媒体云存储系统单节点修复算法

针对现有多媒体云存储系统单节点修复算法中,有限域大,编解码复杂度高,磁盘I/O开销大,存储开销与修复带宽开销不均衡等问题,基于网络编码提出一种多媒体云存储系统单节点修复算法.该算法将系统中节点已分组的多媒体文件数据进行分组存储,并将组内数据在GF(2)有限域上进行异或编码,当部分节点失效时,新生节点只要连接同组中2~3个未失效节点即可精确修复失效节点中的数据.理论分析与仿真实验结果表明:该算法可减小编解码与修复的复杂度,降低磁盘I/O开销;在相同条件下,该算法存储开销与基于最小存储再生码(minimum storage regeneration codes,MSR)算法的存储开销一致,而修复带宽开销与最小带宽再生码(minimum bandwidth regeneration codes,MBR)算法接近.     

2类最优局部修复码的构造

局部修复码可以提高分布式存储系统中失效节点的修复效率,是分布式存储编码领域的研究热点。文章研究最优局部修复码的构造,利用二元常重量码构造了两类矩阵,并以这两类矩阵作为校验矩阵,构造了局部性为r、最小距离分别为d=5和d=6的两类最优局部修复码。     

低复杂度的最小冗余再生码的矩阵构造方法

针对现有的基于矩阵的最小冗余再生码的构造方法中存在的编码和重构复杂度高及参数选择受到限制的问题,设计了一种矩阵实现的最小冗余再生码的构造方法.该方法通过改变数据矩阵和修复向量的结构,能够有效地减少最小冗余再生码的编码和数据重构的复杂度,同时参数的选择更加简单和灵活.     

一种分布式存储系统环境下的数据持有性验证方法

为了在分布式环境下进行数据持有性验证并保持较低的修复带宽,该文在引入再生码的基础上,提出了一种分布式环境下的数据持有性验证方案。该方案利用再生码来进行数据持有性验证,并在修复阶段再次进行持有性验证以抵抗污染攻击。通过理论分析,该方案既保持了再生码修复带宽低的优势,且相比于经典方案降低了计算开销,节省了存储空间。该文还提供了方案的安全性证明,通过安全性及性能分析表明该方案是可行的。     

五维三元最优线性码的局部度

局部修复码(Locally Repairable Code)中每一码字的任意位发生错误可通过读取此码字的其它若干位予以修复。在应用了局部修复码的分布式存储系统中,任意节点发生损坏时均可通过读取较小数量的其它节点对其进行修复,给出了一些可以达到较小局部修复度的码的生成矩阵的构造方法。通过对相应最优码参数的分析,采用删截、扩展,并置等方法构造出了五维三元最优码的生成矩阵,分析了生成矩阵列向量之间的线性相关关系后,得到了许多具有较小局部度的五维三元最优码。     

低维四元局部修复码的构造

在分布式存储系统中,当节点发生故障时,局部修复码能够提高修复效率.四元距离最优码易于实现,当给定码长和维数时,四元距离最优码的纠错能力优于二元距离最优码,但目前利用四元距离最优码构造四元局部修复码的研究存在很多空白.设四元距离最优码的维数2≤k≤4,由给定维数的四元Simplex码与MacDonald码以及少量距离最优码的生成矩阵,利用扩展、删除与并置等组合方法,设法构造出任意码长n≥k+1且局部度较小的四元局部修复码.确定出达到Singleton-Like界或Cadambe-Mazumdar界的四元局部修复码.证明除55个四元局部修复码外,其余的四元局部修复码都是局部度最优的.     

二元局部修复码的新构造

局部修复码(Locally Repairable Codes,简记为LRCs)是一种可以减小分布式存储系统修复带宽的新型纠删码。依据二元最优码的不同距离特性而改变校验矩阵的方法,提出了由奇距离局部修复码扩展构造偶距离局部修复码的一种方法;而且提出了通过删截的方法构造新的性能优良的局部修复码。利用这两种方法,构造出四组码长为n≤24,维数为k≥8且距离为6≤d≤8具有较小局部修复度的码,这些码都达到了C-M界。这些结果对于研究更大距离的二元最优局部修复码以及一般域上的最优局部修复码的构造,将具有借鉴意义。     

一类基于极图理论的局部修复编码的性质及构造

由于分布式存储系统大量使用廉价的磁盘构建,磁盘故障往往不可避免导致数据丢失.数据编码是一种防止数据丢失的必要容错机制.局部修复码与经典的最大距离可分(MDS)码相比,以一定的存储空间开销,能够有效提高数据修复的效率,降低网络带宽占用.为了降低该码的存储空间开销,本文研究以极图理论来描述该类编码.将存储节点与编码块抽象为二分图中的X、Y两类顶点,从而存储空间占用最小化等价于计算二分图中边数的极小值.这种求极值问题可以归结为Zarankiewicz问题.本文使用极值二分图对局部修复码进行建模与分析,并给出了相应的构造算法.     

纠删码存储系统中数据修复性能优化研究进展与展望

纠删码被广泛应用于分布式存储系统以保存在线应用的用户数据。当部分存储节点发生故障时,纠删码存储系统需使用新的存储节点替换原有失效节点,并恢复失效的用户数据。由于需要执行数据编码、传输和读写等操作,纠删码存储系统通常需要消耗较长的时间执行数据修复操作,存储的用户数据将长期处于不可靠状态。为了保障存储数据的可靠性,研究学者提出了多种数据修复性能优化方案以减少数据修复时间。本文介绍了数据修复性能优化问题,分析了各个应用场景下主要的性能瓶颈和性能优化难点,总结了提升数据修复性能的主要技术方案和研究工作,并对数据修复性能优化研究领域的未来发展方向进行展望,为纠删码存储系统设计人员准确选择适合特定应用场景的数据修复性能优化方案提供思路。     

短码长的五元最优局部修复码

在分布式存储系统中,应用局部修复码(LRCs),可以提高修复错误节点的效率。研究了码长不大于31的五元最优LRCs,给出了4类五元最优LRCs及其具体刻画。首先利用距离最优的线性码和Simplex码等特殊码,构造了性能较好的LRCs的校验矩阵。对已得到的LRCs,通过矩阵变换、矩阵拼接和删截的方法,给出了其他LRCs。所构造的五元LRCs的最小距离为2≤d≤8和d=10,参数均达到了Singleton界。这些结果对于其他五元最优LRCs和一般域上最优LRCs的构造具有借鉴意义。     

LDPC编码的FPGA实现

低密度奇偶校验码（简称LDPC码）是目前距离香农限最近的一种线性纠错码，它的直接编码运算量较大，通常具有码长的二次方复杂度．为此，利用有效的校验矩阵，来降低编码的复杂度，同时研究利用大规模集成电路实现LDPC码的编码．在ISE8．2软件平台上采用基于FPGA的Verilog HDL语言实现了有效的编码过程，为LDPC码的硬件实现和实际应用提供了依据．     

QR code二维条码数据编码的研究

为了实现二维条码的超大容量和高效汉字表示,应用快速响应矩阵码(QR code)进行编码.QR code码可以对任何类型数据,如数字、字母、字节以及汉字等进行编码.汉字模式下输入字符被压缩成13 bit二进制数,然后将二进制数连接起来,并在前面加上模式指示符、汉字子集指示符和字符计数指示符.在对输入数据进行汉字编码时,发现国家标准(GB/T 18284-2000)中存在错误,生成的数据位流超出国标中规定的符号数据容量.提出了3种修订方法,修改了国标中汉字模式的数据容量.测试结果表明所提方法是可行和有效的.     

大数据存储中的容错关键技术综述

不断增长的海量数据需要被可靠存储,而分布式存储系统庞大的节点规模和数据规模,大大提升了发生节点失效的概率,容错技术成为大数据存储中不可忽视的关键技术.文中介绍了数据容错的两种基本策略：复制和纠删码,并分别总结了将这两种容错策略具体应用于大数据存储时所面对的问题和相关解决技术,如与基于复制的容错技术相关的副本系数设置、副本放置策略、副本一致性策略、副本修复策略和纠删码领域的再生码技术等.     

MIMO-AF协作系统中继发射矩阵的优化及性能分析

为了提高MIMO放大前传（AF）协作中继系统的性能,文中提出在中继节点向目标节点发送信号之前,加入优化的发射矩阵.中继节点采用空时码,在发射功率受限的条件下,首先针对目标节点的接收信号运用最小均分误差MMSE准则,定义推导了求解最佳发射矩阵和接收端均衡器系数的优化问题.接着,为了降低解优化问题的计算复杂度,提出了梯度下降的迭代算法.然后通过推导误码率上限,从理论上证明了文中算法的有效性.仿真结果表明,在中继节点设置发射矩阵能够降低误码率上限,用文中方法对发射矩阵进行优化以后,与现有空时码相比,可以有效提高系统性能,且优化算法收敛性好,计算复杂度低.     

规则LDPC码构造的论述

LDPC码是一种线性分组码,它的校验矩阵是稀疏矩阵。如果校验矩阵的每列含有j个非0元素(一般要求j大于等于3),每行含有k个非0元素,则称这种含非0元素数目固定的校验矩阵所对应的LDPC码称为规则码。如果含非0元素数目不固定,则称为非规则码。规则码具有规则的二分图结构,即每个变量节点和恒定数目的校验节点相连并且每个校验节点又和恒定数目的变量节点相连,利用和积译码算法可以得到较好的性能。本章构造的LDPC码均是规则LDPC     

基于矩阵分解的有限几何LDPC码的研究

随机构造的LDPC（low density parity check codes）码长的增加,所需存储空间过大,编码复杂度过高.针对该问题,研究了具有代数结构的有限几何LDPC码.基于有限域几何空间的点和线来构造校验矩阵,并通过矩阵行列分解得到不同码率、码长的非规则QC-LDPC码.该类LDPC码是准循环码,其编码复杂度与码长成线性关系,对应的Tanner图没有4环存在.仿真结果表明：MSK调制、AWGN信道条件下,该类码与类似参数的随机码相比较,当信道误码率为10-6时,译码增益约为0.05～0.15dB.     

用Hadamard矩阵构造线性码

Hadamard矩阵在实验设计、编码、网络、逻辑电路等方面都有广泛的应用,并且通过多种方式可以构造Hadamard矩阵.本文主要利用反对称Hadamard矩阵构造出了一类二元和三元自对偶线性纠错码     

一种基于稀疏序列的量子CSS码的构造

量子CSS码是一种简单、有效的量子码构造方法,已被应用到各类特性的量子码的构造之中.针对低密度奇偶校验码(LDPC)的优异性能,利用稀疏序列构造LDPC码校验矩阵的方法,提出了一种构造量子低密度奇偶校验码校验矩阵构造方法,采用快速编码算法,获得相应的量子码.最后,以(3,8)(16,6)量子码为例给出量子低密度奇偶校验...     

分布式无线通信系统中的线性疏散码

研究了分布式无线通信系统(DWCS)中线性疏散码(LDC)的码字生成算法.由于传统LDC码字生成条件被破坏,故不适用于DWCS.为此提出了一种分布式协同的LDC码字基矩阵生成算法.该算法适合于地理上离散分布的多天线系统的联合协同通信,可以有效地利用移动台和基站间不同的大尺度衰落特性,并且该算法以最小化LDC线性变换矩阵的列相关性为准则,降低了码字基矩阵的生成复杂度.在单小区中的仿真结果表明,分布式LDC编码可以取得比传统LDC编码更好的性能.