理解什么是汉明距离，SEC-DEC 码和汉明距离的关系，如何从直觉构造 SEC-DEC 码，如何构造 odd-weight-column 码来降低关键路径延时。
如果在传输数据过程中，额外添加一些比特，在数据传输或者存储过程中出现错误，能够进行检测和纠正，对应的编码就是错误检测码或者错误纠正码。
最简单的错误检测机制就是奇偶校验码，通过计算数据比特中 1 的总数是奇数还是偶数实现错误检测。例如，对于 4 比特数据 4'b1001，“1” 的个数为2，那么对应校验码为 1 ^ 0 ^ 0 ^ 1 = 0。这个校验码会跟随数据存储或者传输。在接受到或者读出数据时，重新对数据做一次校验，和接受到或者读出的校验码比较，如果不同，那么数据有错误。例如读出数据为4'b1101，对应校验码应为 1 ^ 1 ^ 0 ^ 1 = 1，但是存储的校验码为 0，所以数据有错误。
奇偶校验码只能检测奇数个比特出现错误，并且无法指出错误发生的位置，也就无法纠错。但是由于实现电路简单，时序不长，所以当数据位宽比较少，或者需要快速检错的时候常使用奇偶校验，例如缓存中的 tag 常用奇偶校验机制保护。
汉明距离标记两个编码之间的差异。
如果希望实现SEC（Single Error Correction），那么两个没有错误的编码之间最小汉明距离为3. 如果希望实现SEC-DED（Single Error Correction, Double Error Detection），那么两个没有错误的编码之间最小汉明距离为4。
code_wo_error_A <--> code_w_error_A <--> code_w_error_B <--> code_wo_error_B
对于 SEC 编码，code_wo_error_A 和 code_wo_error_B 之间有两个编码，那么的汉明距离就是 3 (从code_wo_error_A 到 code_wo_error_B 需要反转 3 个比特）。假如 code_wo_error_A 发生了 1 比特错误，变成了code_w_error_A，就可以推断出正确值应该是 code_wo_error_A。
code_wo_error_A <--> code_w_error_A <--> code_w_error_A_B <--> code_w_error_B <--> code_wo_error_B
对于 SEC-DED 编码，code_wo_error_A 和 code_wo_error_B 之间有三个编码，那么的汉明距离就是 4 (从code_wo_error_A 到 code_wo_error_B 需要反转 3 个比特）。假如 code_wo_error_A 发生了 1 比特错误，变成了code_w_error_A，就可以推断出正确值应该是 code_wo_error_A，如果 code_wo_error_A 发生了 2 比特错误，变成 code_w_error_A_B，可以检测到错误，但是由于 code_w_error_A_B 到 code_wo_error_A 和到 code_wo_error_B 距离一样，无法进行纠正。
对于 SEC，如果有 d 比特数据，假设对应的校验为有 p 比特，这 p 比特需要表示下面两大类情况
那么可以得到下式
对于 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}。存储校验位和重新计算校验位做异或得到的结果叫做 syndrome，它指示发生错位的位置为 D5。
额外多加一个比特就可以在 SEC 基础上实现 DED。额外多加的校验位记作 p4，p4 是 D1-D15 的奇偶校验结果。
| syndrome[3:0] 没有指示错误，syndrome[4] 没有指示错误 | 数据正确 | |
| syndrome[3:0] 指示错误，syndrome[4] 没有指示错误 | 发生双比特错误 | |
| syndrome[3:0] 没有指示错误，syndrome[4] 指示错误 | 发生单比特错误 | 错误位置在 p4 |
| syndrome[3:0] 指示错误，syndrome[4] 指示错误 | 发生单比特错误 | 错误位置由 syndrome[3:0] 指示 |
如果是大于等于 3 的奇数个比特错误，那么结果是 “p0-p3 指示错误，p4 指示错误”，但是无法计算出错误位置。
如果是大于等于 4 的奇数个比特错误，那么结果是 “p0-p3 指示错误，p4 没有指示错误”，但是无法计算出错误位置。
如果数据有 d 比特，要实现 SEC-DED，所需校验位为 p 比特，并且 p = p' + 1，其中 p' 是实现 SEC 所需的校验位比特数，需要满足
或者等价地，需要满足
然后将 d 和 p 按照一定顺序排列，p 放在位置为 2 的整数幂的位置，d 插空按顺序排列，组成 D，挑出 D 的索引最低位为 1，次低位为 1……的数据比特，计算对应的 p 即可。
Odd-weight-column SEC-DED 是一种速度更快计算 SEC-DEC code 的方法。速度更快是指异或门的级数更少。
首先，上一节提到的 DEC-DED 编码的计算方法可以写成一个 H matrix。
| 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 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 8 | ||||||||
| R1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 8 | ||||||||
| R2 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 8 | ||||||||
| R3 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 8 | ||||||||
| R4 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 16 |
R0 表示计算 syndrome 的最低位所需要的比特，分别是数据 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-weight-column 就是要解决各个校验位计算时门级数不均衡问题，构造 odd-weight-column 的 H matrix，有如下的约束：
第 1 点和第 2 点保证了构造的 H 矩阵能够让编码的汉明距离为 3，支持 SEC。可以想象，由于所有的列不同，没有列为空，那么不同位置出现 1 比特错误，所呈现的 syndrome 会完全不一样。
第 3 点保证可以区分奇数比特错误和偶数比特错误。如果是奇数比特错误，那么 syndrome 会有奇数个 1，如果是偶数个比特错误，那么 syndrome 会有偶数个 1。
那么如何构造 odd-column weight matrix 呢：
下表是按照上述方法为 d = 10, p = 5 构造的 odd-column-weight matrix。C11-C15 的 1 个数为 1，均给校验位用，C0-C9 的 1 个数为 3，分别给 d0-d9 用，最后 C10 的 1 个数为 5，给 d10 用。可以看到，R0-R4 所需异或门的数量比前一章要均衡，特别是判断是否为两比特错误时，不需要把所有的 (d+p) 个比特做异或来计算校验位。
| 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 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 8 | ||||||||
| R1 | 1 | 1 | 1 | 1 | 1 | 1 | 6 | ||||||||||
| R2 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 8 | ||||||||
| R3 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 8 | ||||||||
| R4 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 8 |
| syndrome[4:0] 没有指示错误 | 数据正确 | |
| syndrome[4:0] 指示错误，syndrome[4:0] 有偶数个 1 | 发生双比特错误 | |
| syndrome[4:0] 指示错误，syndrome[4:0] 有奇数个 1 | 发生单比特错误 | 错误位置由 syndrome[4:0] 指示 |
上一章，我们推导出，对于 d 比特数据，p 比特校验位，要实现 SEC-DEC，需要满足。Odd-column weight 要求每一列的 1 个数都是奇数，不能是偶数，似乎一下子就少了一半的可能性（即排除了每一列 1 的个数为偶数的编码方法），p 个比特的 odd-weight 个数能够不小于 (d+p) 吗 ？
p 个比特的 even-weight（包含0-weight）, odd-weight 个数是 ，可以想象 p 个比特的二进制数，1 的个数为 0 的数有 1 个，1 的个数为 1 的数有 p 个，以此类推， 就是 p 个比特能表示的数的个数，即 。由于组合数奇数项和偶数项的和相同，所以 odd-weight 一共有 个，不小于 (d+p)，用 odd-weight 编码 SEC-DED 是足够的。
如果想要实现单笔特纠错（SEC），需要编码之间的汉明距离最小为 3。
如果想要实现单笔特纠错，双比特检错（SEC-DEC），需要编码之间的汉明距离最小为 4。
SEC 的基本想法就是利用二分法来对不同组的数值计算校验位，通过 syndrome 比特指示错误数值的位置。SEC-DED 的基本想法就是在 SEC 基础上，对 SEC 所有的数值和校验位再做一次校验，从而能识别出两比特错误的情况。
Odd-colunm-weight 可以构造出逻辑级数更少的产生校验位的方法，关键是 DED 不需要将 SEC 所有的数值和校验位再做一次校验，只需通过 syndrome 的奇偶性就可以判断是否发生两比特错误。
本文发布于:2024-01-31 00:49:01，感谢您对本站的认可！
本文链接：https://www.4u4v.net/it/170663403224179.html
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系，我们将在24小时内删除。
| 留言与评论（共有 0 条评论） |
