eeiit的个人空间 https://blog.eetop.cn/63271 [收藏] [复制] [分享] [RSS]

空间首页 动态 记录 日志 相册 主题 分享 留言板 个人资料

日志

RAID中的信道编码

已有 1936 次阅读| 2006-12-15 06:05 |个人分类:信道编码

天气: 晴朗
心情: 高兴

1978年,冗余独立硬盘阵列(RAID:Redundant Array of Independent Disks)的思想出现在IBM的专利中(见 http://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO1&Sect2=HITOFF&d=PALL&p=1&u=%2Fnetahtml%2FPTO%2Fsrchnum.htm&r=1&f=G&l=50&s1=4,092,732.PN.&OS=PN/4,092,732&RS=PN/4,092,732),日后的RAID-5是以这项专利为基础的。而RAID的概念是1987年被提出(http://www.eecs.berkeley.edu/Pubs/TechRpts/1987/CSD-87-391.pdf),不过最初RAID是指冗余低价(inexpensive)硬盘阵列。

RAID的简介和各RAID等级的比较可见http://www.stor-age.com/zhuanti/htm2004/04033017YS4Y.asp,当前应用最广的是RAID-0,1,5。从信道编码的角度,不同等级的RAID采用了不同的编码方案:

  • 重复码(repetition code): RAID-1中采用(2,1,2)重复码,所以可以纠正一个错误(错误的位置已知)。(在信道编码理论中,线性分组码以(n,k,d)表示,n为码字长度,k为信息字长度,(n-k)为冗余字长,d为最小汉明距。纠错是通过计算错误的值及其位置来进行,而当错误的位置已知时,仅需计算错误的值是什么。所以,如果错误的位置已知,可纠正错误的数量是错误的位置未知时的两倍。而最小汉明距表征了线性分组码的纠错能力,如错误的位置未知时,可纠正错误的数量不大于(d-1)/2。)当然这里(2,1,2)信息字单位是指一个数据块或一个硬盘,当一个硬盘出错时,可以通过另一个硬盘来恢复。

                        

  • 汉明码(Hamming code):RAID-2采用(2^m-1, 2^m-1-m, 3)的汉明码,m是比特位数。由於汉明码的最小汉明距为3,所以可以纠正位置未知的1个错误。不过由於编解码都是以单个比特为单位,限制了数据的更新和恢复速度,从而限制了RAID-2的应用。汉明码的校验矩阵的(2^m-1)列是数字1到2^m-1的二进制表示,它的对称码(dual code)是最大周期伪随机序列,被广泛应用于CDMA中。
  • 单冗余校验码(SPC:single parity-check code):RAID-3,4,5采用(n,n-1,2)单冗余校验码,可以纠正位置已知的1个错误。显然,(2,1,2)重复码可以看作是一种特殊的SPC,即n=2。

 

如图所示,Ap是A1,A2,A3的校验块,即A1,A2,A3,Ap的模2和为零。如果4个硬盘中的一个出错,可由另外3个硬盘的内容来恢复出错盘。

  • 双校验码: RAID-6采用(n,n-2,3)码,可以纠正位置已知的2个错误。

    

如图所示,Ap是A1,A2,A3的校验块,即A1,A2,A3,Ap的模2和为零。B1,B2,B3,Bp的模2和为零,C1,C2,C3,Cp的模2和为零。Ap,Bp,Cp,Dp可以看作是信息阵列(A1,A2,A3; B1,B2,B3; C1,C2,C3; D1,D2,D3)的横向校验,而Aq,Bq,Cq,Dq的一种实现方案是对阵列进行纵向校验,即A1,B1,C1,D1,Aq的模2和为零,..., A3,B3,C3,D3,Dq的模2和为零。

单冗余校验码和双校验码的共同特点是编解码非常简单,通过模2和就可实现,而且它们的最小汉明距为冗余字长加1,d=n-k+1, 从而也被称为最大距离可分码(Maximum distance separable: MDS),即给定冗余字长, MDS码有最佳的纠错能力。可容许大於2个硬盘错误的方案也已被提出(扩展阵列码:Array code),不过,实现尽可能简单的编解码是这些理论研究成果走向应用的前提。


点赞

评论 (0 个评论)

facelist

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

  • 关注TA
  • 加好友
  • 联系TA
  • 0

    周排名
  • 0

    月排名
  • 0

    总排名
  • 0

    关注
  • 1

    粉丝
  • 0

    好友
  • 0

    获赞
  • 20

    评论
  • 访问数
关闭

站长推荐 上一条 /1 下一条

小黑屋| 关于我们| 联系我们| 在线咨询| 隐私声明| EETOP 创芯网
( 京ICP备:10050787号 京公网安备:11010502037710 )

GMT+8, 2024-4-28 21:58 , Processed in 0.014220 second(s), 11 queries , Gzip On, Redis On.

eetop公众号 创芯大讲堂 创芯人才网
返回顶部