ECC, Hamming Distance, Odd-weight _比特

本文目的
理解什么是汉明距离，SEC-DEC 码和汉明距离的关系，如何从直觉构造 SEC-DEC 码，如何构造 odd-- 码来降低关键路径延时。
错误检测/纠正码
如果在传输数据过程中，额外添加一些比特，在数据传输或者存储过程中出现错误，能够进行检测和纠正，对应的编码就是错误检测码或者错误纠正码。
奇偶校验码
最简单的错误检测机制就是奇偶校验码，通过计算数据比特中 1 的总数是奇数还是偶数实现错误检测。例如，对于 4 比特数据 4'b1001，“1” 的个数为2，那么对应校验码为 1 ^ 0 ^ 0 ^ 1 = 0 。这个校验码会跟随数据存储或者传输。在接受到或者读出数据时，重新对数据做一次校验，和接受到或者读出的校验码比较，如果不同，那么数据有错误。例如读出数据为4'b1101，对应校验码应为 1 ^ 1 ^ 0 ^ 1 = 1 ，但是存储的校验码为 0，所以数据有错误。
奇偶校验码只能检测奇数个比特出现错误，并且无法指出错误发生的位置，也就无法纠错。但是由于实现电路简单，时序不长，所以当数据位宽比较少，或者需要快速检错的时候常使用奇偶校验，例如缓存中的 tag 常用奇偶校验机制保护。
单比特纠错 - 两比特检错码（SEC-DEC，ErrorandError ) 和汉明距离（）汉明距离
汉明距离标记两个编码之间的差异。
SEC-DED 与汉明距离的关系
如果希望实现SEC（ Error ），那么两个没有错误的编码之间最小汉明距离为3. 如果希望实现SEC-DED（ Error ,Error ），那么两个没有错误的编码之间最小汉明距离为4 。
对于 SEC 编码，和之间有两个编码，那么的汉明距离就是 3 (从到需要反转 3 个比特）。假如发生了 1 比特错误，变成了，就可以推断出正确值应该是。
对于 SEC-DED 编码，和之间有三个编码，那么的汉明距离就是 4 (从到需要反转 3 个比特）。假如发生了 1 比特错误，变成了，就可以推断出正确值应该是，如果发生了 2 比特错误，变成，可以检测到错误，但是由于到和到距离一样，无法进行纠正。
SEC-DED 的原理
对于 SEC ，如果有d 比特数据，假设对应的校验为有 p 比特，这 p 比特需要表示下面两大类情况
那么可以得到下式
= 1 + (d+p)" src="http://www.kingceram.com/post/;%20%28d+p%29" />
对于 d = 11，p 最小为 4 。如果需要DED，则需要额外一个 bit，一共 5 比特。
对于 d = 64 ， p 最小为 7 。如果需要DED，则需要额外一个 bit，一共 8 比特。
下面用 d = 10，p =4 举例说明 SEC 原理。
C0
C1
C2
C3
R0
D0
D1 (4'b0001) (p0)
D2 (4'b0010) (p1)
D3 (4'b0011) (d0)
R1
D4 (4'b0100) (p2)
D5 (4'b0101) (d1)
D6 (4'b0110) (d2)
D7 (4'b0111) (d3)
R2
D8 (4'b1000) (p3)
D9 (4'b1001) (d4)
D10 (4'b1010)(d5)
D11 (4'b1011) (d6)
R3
D12 (4'b1100) (d7)
D13 (4'b1101) (d8)
D14 (4'b1110) (d9)
D15 (4'b1111) (d10)
将数据比特 d0-d10 和校验比特 p0-p3 按照一定顺序规律标记为 D1-D15 。例如 p0 放在 D1 的位置，d0 放在 D3 的位置。“一定顺序规律”指的是校验位放在索引为 2 的整数幂的位置，例如 D1, D2, D4, D8 分别对应 p0, p1, p2, p3，其余位置按照顺序放数据比特。
然后，我们用 d0, d1, d3, d4, d6, d8, d10 的奇偶校验得到p0 。
用 d0, d2, d3, d5, d6, d9, d10 的奇偶校验得到 p1 。
用 d1, d2, d3, d7, d8, d9, d10 的奇偶校验得到 p2 。
用 d4, d5, d6, d7, d8, d9, d10 的奇偶校验得到 p3 。
问题是，为什么需要如此排序，为什么需要如此计算得到校验位？
我们可以用二分法来理解。
假如 d1 发生错误，那么 p0 可以指示有错误发生在 C1 和 C3，p1 可以指示 C2 和 C3 没有错误。所以错误的比特一定在 C1，但是不确定行数。p2 可以指示错误在 R1 和 R3，p3 可以指示 R2 和 R3 没有错误，所以错误发生在 R1 。综合 p0-p3 的结果，错误在 C1R1，即 d1 发生了错误。（如果是校验位 p0-p3 出现了错误，也是类似，可以通过二分法找到错误的位置并修正。）
我们再来观察 p0-p3 所在 D 的索引，即D1, D2, D4, D8，它们的二进制表示是 4'b0001, 4'b0010, 4'b0100, 4'b1000，都是独热码。p0 表示的是索引二进制最低位为 1 的位置的奇偶校验码，即D3, D5, D7, D9, D11, D13, D15 (3, 5, 7, 9, 11, 13, 15 二进制表示的最低位都为 1 ）。p1-p3 以此类推，表示索引二进制次低位为 1 ，次高位为 1，最高位为 1 的奇偶校验码，所以
由 p0-p3 就可以得到错误位置索引的最低位，次低位，次高位和最高位是否为 1，也就确定了错误发生的位置。
例如 d1 发生错误，存储的校验位为 {p3, p2, p1, p0}，读出数据后重新计算的校验位为 {p3', p2', p1', p0'}，那么 {p3, p2, p1, p0} ^ {p3', p2', p1', p0'} = {1'b0, 1'b1, 1'0, 1'b1} 。存储校验位和重新计算校验位做异或得到的结果叫做，它指示发生错位的位置为 D5 。
额外多加一个比特就可以在 SEC 基础上实现 DED 。额外多加的校验位记作 p4，p4 是 D1-D15 的奇偶校验结果。
[3:0] 没有指示错误，[4] 没有指示错误
数据正确
[3:0] 指示错误， [4] 没有指示错误
发生双比特错误
[3:0] 没有指示错误，[4] 指示错误
发生单比特错误

文章插图
或者等价地，需要满足
= d+p" src="http://www.kingceram.com/post/;p" />
然后将 d 和 p 按照一定顺序排列，p 放在位置为 2 的整数幂的位置，d 插空按顺序排列，组成 D，挑出 D 的索引最低位为 1，次低位为 1……的数据比特，计算对应的 p 即可。
Odd-- SEC-DED Code
Odd-- SEC-DED 是一种速度更快计算 SEC-DEC code 的方法。速度更快是指异或门的级数更少。
首先，上一节提到的 DEC-DED 编码的计算方法可以写成一个 H。
C0
C1
C2
C3
C4
C5
C6
C7
C8
C9
C10
C11
C12
C13
C14
C15
d0
d1
d2
d3
d4
d5
d6
d7
d8
d9
d10
p0
p1
p2
p3
p4
SUM
R0
R1
R2
R3
R4
16
R0 表示计算的最低位所需要的比特，分别是数据 d0, d1, d3, d4, d6, d8, d10 和校验位 p0 。R1-R3 依次类推。R4 是计算是否存在双比特错误所需的比特。如果是计算 DEC-DED 的校验位编码，那么可以不考虑 (R0, C11) (R1, C12) (R2, C13) (R3, C14) (R4, C15) 所在的 1 。我们可以看到 R0-R4 所需的比特数分别为 8，8，8，16，对应而输入异或门的级数是 3，3，3，4 。异或门级数并不均衡，时序最差路径是 4 级异或门。
Odd-- 就是要解决各个校验位计算时门级数不均衡问题，构造 odd-- 的 H ，有如下的约束：
没有列为 0所有的列互不相同所有的列都是奇数个 1
第 1 点和第 2 点保证了构造的 H 矩阵能够让编码的汉明距离为 3，支持 SEC 。可以想象，由于所有的列不同，没有列为空，那么不同位置出现 1 比特错误，所呈现的会完全不一样。
第 3 点保证可以区分奇数比特错误和偶数比特错误。如果是奇数比特错误，那么会有奇数个 1 ，如果是偶数个比特错误，那么会有偶数个 1 。
那么如何构造 odd-呢：
所有 1-odd-，即只有 1 个 1 的列都给校验位从 3-odd-（有 3 个 1 的列）开始，由p 个位置组合任意 3 个位置，一共
种情况。如果不够用，就利用 5-odd- （有 5 个 1 的列），直到所有的列都有对应的

文章插图
。Odd-要求每一列的 1 个数都是奇数，不能是偶数，似乎一下子就少了一半的可能性（即排除了每一列 1 的个数为偶数的编码方法）， p 个比特的 odd- 个数能够不小于 (d+p) 吗？
p 个比特的 even-（包含0-）, odd- 个数是
，可以想象 p 个比特的二进制数， 1 的个数为 0 的数有 1 个， 1 的个数为 1 的数有 p 个，以此类推，
就是 p 个比特能表示的数的个数，即
。由于组合数奇数项和偶数项的和相同，所以 odd- 一共有
个，不小于 (d+p)，用 odd- 编码 SEC-DED 是足够的。
结论
如果想要实现单笔特纠错（SEC），需要编码之间的汉明距离最小为 3 。
如果想要实现单笔特纠错，双比特检错（SEC-DEC），需要编码之间的汉明距离最小为 4 。
SEC 的基本想法就是利用二分法来对不同组的数值计算校验位，通过比特指示错误数值的位置。SEC-DED 的基本想法就是在 SEC 基础上，对 SEC 所有的数值和校验位再做一次校验，从而能识别出两比特错误的情况。
Odd-- 可以构造出逻辑级数更少的产生校验位的方法，关键是 DED 不需要将 SEC 所有的数值和校验位再做一次校验，只需通过的奇偶性就可以判断是否发生两比特错误。
【ECC, Hamming Distance, Odd-weight】 Bruce Jacob,Ng, and David Wang. 2007.: Cache, DRAM, Disk.Inc., San , CA, USA. .But what arecodes? Theof error .()M. Y. Hsiao. 1970. A class ofodd-- SEC-DED codes. IBM J. Res. Dev. 14, 4 (July 1970), 395–401. lpls1.二项式展开式系数和、二项式展开式奇偶项系数和的相关定理及证明.数论,图论,数学-CSDN博客