注册 登录
电子工程世界-论坛 返回首页 EEWORLD首页 频道 EE大学堂 下载中心 Datasheet 专题

白丁的个人空间 http://home.eeworld.com.cn/space-uid-346593.html [收藏] [复制] [分享] [RSS]

日志

(转)存储系统中的纠删码(Erasure Codes)—XOR 码和RS 码(二)

已有 315 次阅读2017-9-22 23:16 |个人分类:存储管理

原文地址

纠删码(Erasure Codes)能够总体上分为XOR 码和RS 码两类,XOR 码基于有限域GF(2),编、解码只需要按位异或(bit-wise exclusive-OR)即可完成,速度较快;RS 码基于有限域GF(2 w ),编、解码需要有限域上(后面的文章将详细介绍)的运算,速度慢于XOR码。常见的XOR码有:

  • 低密度奇偶校验码(Low Density Parity Code, LDPC)
  • 柯西-里德所罗门码(Cauchy-Reed-Solomon Codes,CRS)
  • RAID码(如RAID5、RAID6)
  • 奇偶码(EVENODD)
  • X-码(X-code)

按照编码理论来说,RS码是一个字长为n,维度为k,码字间距为n-k+1 的最小距离可分码(MDS codes),但为了能够让读者能够更容易接受,我们这里的RS 码是基于有限域上GF(2 w )编解码运算的编码。

一、XOR 码和RS 码的生成矩阵

上一节中我们介绍了生成矩阵(Generator Matrix)定义了线性码的编码方法,XOR 码的生成矩阵中的元素只有0 和1,在RS 码中,生成矩阵的元素是从0到2 w -1 的整数。


图1 校验矩阵(Parity matrix)生成校验块

如图1,如果是XOR 码,左边的校验矩阵中m ij 为0或1,那么校验块的计算则只有数据块D0~D3的异或过程(有限域上加减法都是异或运算);反之如果是RS码,校验块的计算则包含了m ij 和数据块Dj 的乘法,有限域上的乘法是非常慢的,因为在有人则提出利用计算机GPGPU 或SIMD指令集加速m ij 和数据块Dj 的乘法。

在实际系统中往往更考虑性能,其次是一般性,虽然RS 码慢于XOR 码,但其具有更佳的一般性(generality),可以支持任意大小的n、k、m 参数。而XOR 码对于这些参数总有或多或少的限制,但总体来说真实系统中XOR 码应用要比RS 码应用更广泛(CRS 应用于oceanstore,RAID 码广泛应用于阵列)。

二、扁平和非扁平(Flat or not)

扁平和非扁平是纠删码所具有的特性。当一个编码方法是扁平的(flat),编码后每个条带上的存储节点中仅有一个编码块;当一个编码方法不是扁平的,则编码后每个条带上的存储节点中具有多个编码块。

(a)非扁平编码                                    (b)扁平编码     

图2 非扁平编码(r=4)和扁平编码

图2 给出了非扁平编码和扁平编码的两个例子:图2 (a) 中非扁平编码每个条带中将原始数据等分为k×r 块数据块(d 0,0 到d 5,3 ),编码为m×r 个大小的校验块(c 0,0 到c 1,3 ),图2 (b) 中扁平编码将原始数据块分为k 块,编码为m 块校验块。从生成矩阵的角度来看,扁平编码生成矩阵有n 行k 列,非扁平编码生成矩阵有n×r 行、k×r 列,图3 给出了CRS 码(非扁平XOR码)和Reed-Solomon 码(扁平RS码)生成矩阵的编码过程。

图3 k=3、m=2(、w=4)的非扁平码(CRS码、左)和扁平码(RS码、右)的编码过程,

其中红色部分为一个编码块的编码过程

常见的扁平和非扁平编码方法如下:

扁平(flat)
非扁平(non-flat)
XOR 码
LDPC 码
CRS 码,X-码,RDP码,STAR码,
SD码,PDMS码等
RS 码
RS码
Rotated-RS码,再生码等

其中,斜体 RS码 表示的是我们一般的Reed-Solomon 码,而不是用于统称表示所有有限域上计算的编码。它们四者的速度关系为:Flat XOR codes > Non-flat XOR codes > Flat RS codes > Non-flat RS codes 。

三、Flat XOR codes — 低密度奇偶校验码(LDPC, Low Density Parity Codes)

Flat XOR codes只有一类LDPC 码,因此Flat XOR codes 也可称为LDPC 码。LDPC 码广泛应用于通信领域,因为其编解码速度快,码率高(虽然不是MDS 码)。虽然它也是线性码,但不同构造编码矩阵和解码矩阵即可进行数据的编、解码。类似于生成矩阵,每个LDPC 码可以唯一地用一个双边图(bipartite graph)来表示。

图4 一个k=8,m=4 的LDPC 码的双边图

图4 中给出了一个k=8,m=4 的LDPC 码的双边图,左边方块表示分块后的八块原始数据块(u 1 ~u 8 ),右边的圆圈表示校验块,校验块(圆圈)与数据块(方块)的连线表示数据块参与了该校验块的异或运算,每个校验块(圆圈)是所有与其相连的数据块(方块)异或的结果。利用双边图还能够快速地进行丢失数据块的修复。


本文来自论坛,点击查看完整帖子内容。

评论 (0 个评论)

facelist doodle 涂鸦板

您需要登录后才可以评论 登录 | 注册

Archiver|手机版|小黑屋|电子工程世界 ( 京ICP证 060456 )

GMT+8, 2019-1-22 23:06 , Processed in 0.042886 second(s), 11 queries , Gzip On, MemCache On.

Powered by EEWORLD电子工程世界

© 2019 http://bbs.eeworld.com.cn/

返回顶部