介绍

SECDED是single error correction, double bit detection的简称，也就是可以纠正1比特的错误，能够检测2比特的错误。

Hamming Code

原理是借助了hamming code,distance是3，也就是说任意两个codeword之间的差距起码是3，hamming distance的计算方法就是对比两个codeword不一样的地方，并进行累加

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
uint32 hamming_distance( unint32 a, unit32 b) {
    uint32 num = 0;
    uint32 diff;
    diff = a ^ b;
    while (diff) {
		num ++;
		diff = diff & (diff -1 ); //remove the leading 1
	}
	return num;
}

一个典型的hamming(7,4)的意思是原始数据长度是4,parity长度是3,编码后的消息长度是7. hamming编码有一定的规则产生生成矩阵，示意图如下，其中Pn代表parity, Dn代表的是数据从这张图，我们不难发现如下规律

Pn位于位置是2^i的地方，剩余的位置依次填充Dn
对于Pi行，如果index的i bit是1，则填充yes,否则填充No
从左到右, {p3,p2,p1}呈现从1到7依次递增的序列，这为后面的编码提供了基础
p1 = d1 ^ d2 ^ d4, p2 = d1 ^ d3 ^ d4, p3 = d2 ^ d3 ^ d4
解码的时候如果p1,p2,p3只有一个等式不成立，那出错的bit处于Pi上
解码的时候如果p1,p2,p3有超过一个等式不成立，那出错的bit处于Di上
如果 {p3,p2,p1} = x ( x != 0), 则依次很想查找{p3,p2,p1} =x的那一列，对应的列号就是出错的数据。例如，如果{p3,p2,p1}计算结果是6,那出错的数据就是d3,通过将d3进行flipping就可以把数据纠错回来。原因是p3=1,p2=1,所以出错的数据一定在同时可以被p2和p3 cover的行内，也就是d3和d4,如果是d4出错，那p1也会出错，所以只可能是d3. 对于hamming distance =3的纠错码，只能进行1bit的纠错，因为如果发生了2bit的错误，因为distance是3，有可能和另外一个码的distance是1从而导致误纠错。一般的，对于distance是d的纠错码，可纠错的bit数是(d-1)/2，可以检错的bit数是d-1

parity bits (m)和 data bits (k)以及码长(m)的关系如下

SECDED

为了能够实现检测两比特错误的功能，可以通过额外添加一比特全局parity来实现。还是以前面的例子为例，p4 = ^ { p1,p2,p3,d1,d2,d3,d4} 解码的时候计算p1,p2,p3,p4

^p4 == 0 : 但是p1,p2,p3有不为0的情况，这种时候就说明发生了两比特翻转的情况
^p4 == 0 : 并且p1,p2,p3也是0，这说明没有错误发生
^p4 == 1 : 这种时候说明发生了一比特的翻转,并且是可以纠回来的

SECDEC

介绍

Hamming Code

SECDED

Implementation

SW

HW