RS类纠删码的译码方法

RS(Reed-Solomon)码可以根据应用环境构造出任意容错能力的码字,有很好的灵活性,且使用RS纠删码作为容错方法的存储系统能达到理论最优的存储效率.但是,与异或(exclusive-OR, XOR)类纠删码相比,RS类纠删码译码计算的时间开销过大,这又很大程度上阻碍了它在分布式存储系统中的使用.针对这一问题,提出了一类RS纠删码的译码方法,该方法完全抛弃了当前大多RS类纠删码译码方法中普遍使用的矩阵求逆运算,仅使用计算复杂度更小的加法和乘法,通过构造译码变换矩阵并在此矩阵上执行相应的简单的矩阵变换,能够直接得出失效码元由有效码元组成的线性组合关系,从而降低译码计算复杂度.最后,通过理论证明了该方法的正确性,并且针对每种不同大小的文件,进行3种不同大小文件块的划分,将划分得到的数据块进行实验,实验结果表明：在不同的文件分块大小情况下,该新译码方法较其他方法的译码时间开销更低.     

纠删码的分析与研究

纠删码是一种以数据包为单位进行前向纠错的技术,对提高网络通信的质量和可靠性有着重要的意义。本文首先概述了纠删码的原理及其研究进展,将其系统的分为三类,RS类纠删码、级联低密度纠删码和数字喷泉码。详细介绍了这三类纠删码的编译码过程,分析了其产生的背景及特点。讨论了纠删码在多播传输、广播信道、深空通信、网络通信与数据传输等领域中的应用,并对其发展方向进行了展望。     

一种基于短LT码的级联编译码算法

针对实时无线通信对短纠删码的需求,提出一种短码长LT码与传统纠错码的级联方案。在综合考虑算法复杂度与纠错性能的情况下,选取RS码和卷积码的级联(RS-CC码)以构造等效删除信道,并采用实时性高的短LT码实现纠删功能。文中设计了一种适合短LT码的译码算法,同时给出了编码度分布的选取方法。仿真结果表明,与已有短喷泉码相比,文中短LT码成功译码时所需编码冗余更少,应用到级联方案后的数据传输可靠性明显提高。     

分布式系统中纠删码容错机制的研究与实现

为降低分布式系统中容错机制的存储开销,在分布式文件系统中使用纠删码容错机制。本文总结纠删码容错机制实现的几个理论基础,并分析其系统可靠性,在阐明实现该机制的具体步骤后对几个关键算法模块进行了说明,最后对该机制在分布式系统环境下进行实验。实验结果表明,该机制能够有效地恢复受损数据。在合理的缓存块大小和文件分块数策略下,该机制的编、译码率能够较好地匹配局域网中的网络传输速率,且能够节省存储空间。     

基于稀疏随机矩阵的再生码构造方法

针对已有的再生码编码方案的运算是基于有限域GF（q）、运算复杂度高、效率低的问题,提出了一种将GF（2）上的稀疏随机矩阵和乘积矩阵框架相结合的再生码构造方法。首先,将文件数据矩阵式排布后根据编码矩阵进行行异或运算;其次,节点失效后,参与帮助节点根据失效节点的编码向量编码本地数据并发送至修复节点;最后,修复节点根据接收到的数据译码出失效节点原有的数据。实验结果表明修复带宽至多只有传统纠删码修复方案的1/10,相比基于传统范德蒙编码矩阵的再生码,编码速率提升了70%,译码恢复速率提升了50%,方便了再生码在大规模存储系统中的应用。     

分布式存储系统中的纠删码容错方法研究

HRC码是一种具有存储效率高、计算复杂度低等优点的纠删码,但其存在编解码计算开销大、实现较为复杂等不足。通过对HRC码的译码算法进行优化,提出一种新型的纠删码HRCSD。采用内外层分层结构,内部的冗余由HRC码的编码结构组成,外层采用偏移复制策略,将原始信息进行旋转存储,能够实现并行读写。实验结果表明,与三副本技术和S~2-RAID纠删码相比,HRCSD纠删码具有容错性能高、修复开销低等优势,可满足大规模分布式存储系统的容错需求。     

提高T-DMB系统纠错能力的方法

通过对手机电视地面数字多媒体广播（T-DMB）系统外部编码方式的分析,利用TS流中填充字节为固定值的特性,在RS译码前首先检测填充字节区域并预先纠正该区域内的误码;在此基础上,利用解交织前后码元符号间的位置对应关系,对常规纠错RS译码不可译的TS包进行错误位置预测,利用预测结果进行纠错纠删RS译码。实验结果表明,该算法与常规RS码纠错算法相比,能进一步提高系统的纠错能力,改善视音频的播放质量。     

基于多斜率码链的阵列纠删码

针对当前大多阵列纠删码容错能力偏低以及构造时需要满足的约束条件较强的问题,提出一类基于码链构造的阵列纠删码。该阵列纠删码使用不同斜率码链组织数据元素和校验元素间的关系,从而能达到理论上不受限制的容错能力;而在构造时避开了类似素数约束的强约束条件,易于实用和扩展。仿真实验结果表明,相对于RS（Reed-Solomon）码,基于多斜率码链阵列纠删码在运算效率上的提升超过了2个数量级;在固定的容错能力下,存储效率能随着条块尺寸的增加而提高。此外,该类阵列码的修复代价和更新代价为一个固定常量,不会随着系统规模的扩大或容错能力的提高而增加。     

LT码的性能分析与研究

LT码（Luby Transform Codes）属于数字喷泉码,是一类新型前向纠错编码算法,适用于基于包通信的删除信道环境。本文概述了LT码的编译码原理及实现方法,对LT码的理想孤子度分布算法和鲁棒孤子度分布算法进行了仿真验证,分析了LT码在包删除信道下的性能,讨论了实际应用中的参数优化规则,研究结果对提高实时纠删应用的性能具有重要的实用价值。     

RS译码优化及卫星通信CCSDS下RS译码仿真

针对里德所罗门(RS)译码的关键步骤错误值求解不灵活的问题提出一种更加通用的求解算法。该算法融入多种本原元运算,使得对不同参数都普遍适用;针对该算法在求解错误值多项式时计算量过大,根据伽罗华域的特征提出了一种优化方法,从而省去一半运算以及节省存储资源;针对RS译码另一个步骤求解错误位置多项式时迭代复杂度过高的问题,经过对补偿差值的详细分析,给出了一种快速搜索迭代次数的算法,且迭代复杂度由O(n²)下降了一个数量级到O(n)。以卫星通信中的国际空间数据系统咨询委员会(CCSDS)标准下RS(255,223)为具体研究对象,结合优化后的译码算法进行了数据仿真分析和误比特率测试。实验结果表明,采用改进的求错误值算法和优化的迭代次数搜索算法,可以有效快速地解码。     

适用于空间机器人遥操作系统数据通信的纠错编码

本文首先介绍了一般机器人遥操作系统在通信中使用的差错控制技术,接着根据空间机器人遥操作系统中通信信道的特点,提出采用Reed-Solomon（RS）码作为空间机器人遥操作系统的遥测数据和遥控数据的纠错编码,用软件实现了基于有限域GF(2^8) 的通用编译码算法,最后分析了在空间遥操作原型系统中应用RS码后的误码性能。     

RS柯西码编码算法改进研究

针对RS(Reed-Solomon)算法编码过程涉及有限域运算,复杂度高,效率低,运算代价难以被大规模分布式存储系统所接受等问题,提出了一种RS柯西码编码改进算法。该算法用贪心算法选取局部最优柯西矩阵,减少柯西码的计算量。同时,引入二进制矩阵替换柯西矩阵中的有限域元素进行阵列化,将有限域运算转换为异或运算,并对阵列进行运算优化,进一步减少计算量,增加柯西码的编码效率。根据仿真实验表明,改进后RS柯西码与通过遍历得到的最优柯西矩阵的柯西码相比,计算量更小,与编码效率著称的阵列码中的EVENODD码和STAR码相比,编码效率更高。并且具有类似阵列码性质,能够选择更简单高效的译码方法,在一定程度上提高解码效率。     

基于之字形解码算法优化的高效低存储ZD码

ZD码(ZigZag-decodable codes)是基于之字形解码算法设计生成的一类纠删码, 它仅需要少量的计算即可修复存储系统中的故障数据, 但需要存储相对其他纠删码更多的冗余数据以保证系统的高可靠性. 为了降低ZD码产生的存储开销, 本文通过分析当前在存储系统中使用的之字形解码的思想, 提出了一种优化的之字形解码算法. 新的解码算法能够更充分利用校验数据中的信息来完成数据修复. 基于新的解码算法, 本文相应的提出了一种新的ZD码编码方案, 由于新算法更高的信息利用率, 新的编码方案能够用更少的存储开销来满足存储系统的高可靠性. 实验结果表明, 本文提出的ZD码编码方案具有最优的存储开销, 且编解码性能远高于目前广泛使用的RS码.     

一种用于时空体元编解码存储的低计算量优化方法

针对时空网格体对象的编解码占用存储空间大的问题,提出了一种用于时空体元编解码存储的低计算量优化方法。首先以十六叉树索引结构为基础,构建了时空网格体元编解码的数学模型,实现体元对象标识和时空位置索引,并借助3DGIS的自动编解码方法,实现了时空网格体元对象编解码存储表示的换算;其次,采用伽罗华有限域理论,构建了网格体元的二进制编码矩阵和存储的低计算量优化算法,实现了体元对象编解码存储过程中的优化计算;最后,以某矿山的矿床空间块体数据为例,对网格体元编解码模型、存储表示换算以及低计算量优化算法进了实际应用,并与八叉树索引结构的Morton码进行比较和分析,结果表明：该方法可有效降低30%的编解码存储计算量,提高了存储网格体元对象的时空效率。     

基于Reed-Solomon算法的PDF417码纠错研究

PDF417二维条码采用Reed-Solomon码作为纠错码,很好地解决了因条码破损和污染造成的识读问题。在介绍PDF417二维条码和RS纠错码的基础上,详细阐述了RS码的译码原理,包括伴随式的计算、错误位置多项式的计算、错误位置的确定和错误值的计算等。最后分析了RS码译码的算法复杂性。     

G3-PLC前向纠错编码的性能分析与改进

针对G3标准中卷积码的码率单一且码率较低,数据速率损失大的问题,分析了G3标准的正交频分复用(OFDM)低压电力线载波通信系统模型,提出了一种基于RS编码、卷积编码、增信删余编码以及重复编码和二维时频交织的前向纠错编码设计方案,并重点介绍了利用增信删余方式来提高码率的方法。最后通过对该方案的仿真实验得出,在该方案下卷积码的码率由1/2提高到了2/3,在不增加译码复杂度的情况下提高了数据速率,能够实现有效而可靠的通信,可广泛应用于低压电力线通信。     

用于GPRS无线传输的抗分组丢失算法

针对GPRS网络中IP信道的干扰问题,提出一种抗分组丢失算法。该算法将传输数据分段进行RS纠删编码,并采用交织技术对数据进行最优分组并传输,在纠删能力不变的同时获得近似线性的编解码时间。仿真结果表明,与原有RS编码方式相比,该算法可以更好地满足大数据编解码对实时性的要求。     

基于非零均值比的RS码盲识别方法

针对现有的RS码盲识别方法抗误码性能不佳的问题，提出了一种基于非零均值比的盲识别算法。该算法通过将截获到的RS码序列转化为GF(2 ^m )码元来构建分析矩阵，利用有限域的高斯约当算法获得分析矩阵的非零均值比，并以此来识别码长、符号数和本原多项式，最后通过伽罗华域傅里叶变换来完成信息位长及生成多项式的识别。仿真结果表明，本文提出的算法可以有效识别出本原RS码及缩短RS码的所有编码参数，抗误码性能较好，并给出了识别性能与信息位长与码长的关系：随着码长和信息位长的增加，识别性能逐渐下降。     

一种面向DDR3接口的新型Chipkill编码

Chipkill是动态随机存储器系统中先进的容错手段,Reed Solomon（RS）码是实现Chipkill技术的良好编码。以18片DDR3×8存储器芯片为研究对象,首先提出了一种快速构造RS码生成矩阵并对其优化的算法,获得了仅有1 728个“1”的生成矩阵;然后设计了一种纠单符号错RS码高效译码电路,实现了用纯组合逻辑完成检错、纠错操作。将所提出的RS码与传统的SEC/DED汉明码进行对比。开销方面,译码电路面积小19%~27%,延迟仅高出6%~27%。检错纠错能力方面,减少39.76%的可检不可纠错误,并且在实验中未出现不可检错误。     

高速RS编译码器的设计及其FPGA实现

在分析RS（Reed-Solomon）码编译码基本原理的基础上,对编码过程中的乘法电路实现进行了深入分析,对译码过程中用于错误位置多项式和错误值多项式计算的BM（Berlekamp-Massey）迭代算法进行改进,并设计了适合于FPGA硬件实现的伴随式计算策略和钱搜索电路。硬件实现结果表明,改进算法能有效节省硬件资源,在Xilinx公司的XC4VSX35 FPGA上仅需要总资源的15%就可以实现（31,15）RS码编译码器电路,且在200 MHz系统时钟频率时达到10 Mb/s的译码速率,实现了高速数据处理。