分布式二元编解码研究

发布时间：2020-05-05 10:57

【摘要】：相比传统的副本技术,在分布式存储系统中使用网络编码技术能以相同的冗余度提供更高的可靠性并消耗更少的存储空间。分布式存储系统通常采用具有MDS性质的网络编码,它将原数据等分为k个数据块后编码得到n个编码数据块,并分别存储于n个节点之中,使用任意k个节点中存储的数据即可恢复原数据。Zigzag-decodable编码具有最优的编解码复杂度,解码时不需要求解矩阵的逆,并且编解码过程仅使用移位与异或运算,具有较高的编解码效率,同时该编码具有MDS性质。但是受移位操作影响,Zigzag-decodable编码得到的校验序列长度都远远大于原数据序列。本文设计了一种编码矩阵,实现了对称的Zigzag-decodable编码。与之前的编码方案不同,本文的编码矩阵中各元素的指数形成了一个循环矩阵,得到的各校验序列增加的长度相同,使得其校验序列长度小于已知的构造。由于Zigzag-decodable编码的校验序列长度大于原数据序列,解码时帮助节点向Data Collector传输的数据量大于原数据大小。Fu等人提出的In-place解码方案解决了该问题,但它仅适用于编码矩阵具有increasing-difference性质的编码。本文证明了在Zigzag decoding算法运行过程中,一旦所有原数据序列被恢复的比特数大于0,那么可以按照一定的顺序迭代访问校验序列,所有原数据序列在每一轮访问中都可以恢复一个未知比特,直到原数据序列被完整恢复。结合Zigzag decoding算法,本文得到了一种改进的In-place解码方案,该方案适用于所有的Zigzag-decodable编码。最终的仿真结果表明,对称的Zigzag-decodable编码与之前的编码方案具有相同的编解码效率,改进的In-place解码方案也与原始的In-place解码方案具有相同的效率。
【学位授予单位】：西南交通大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP333

【相似文献】