6.004 笔记
| 项目 | 说明 |
|---|---|
| 首页 | https://computation-structures.github.io/course/ |
量化信息 Quantifying Information
什么是信息
信息是一些数据，这些数据的特点是可以帮助消除不确定性
什么是信息量
如果一个数据消除的不确定性越多，那么包含的信息量越大
信息量意味着什么
在计算机中，信息量就意味着要编码这个信息需要多少 bit
熵
$$ H = \sum p_i log_2(\frac{1}{p_i}) $$ 熵表示编码信息所需 bit 的最低下限
编码
使用二叉树进行编码
定变长编码与可变长编码
- 为高频信息分配较短的编码，为低频率信息分配较长的编码可以更好利用资源
霍夫曼算法
如果自动构建最优的变长编码
错误修复
- 奇偶校验可以识别单比特错误
- 汉明编码可以修复比特错误
错误修复的现实世界
- L1 缓存仅使用奇偶校验，如果数据出错，从 L2 中重读
- L2/L3 使用汉明码加强版，可以修复 1 位错误，识别 2 位错误，如果 2 位错误直接崩溃
- 内存分级别，消费级崩溃，商业级自修
两个问题 - 为什么 L2/L3 失败不从内存中读取
因为 L2/L3 数据和内存数据存在时间不一致，可能是脏数据，设计更多的判断电路不划算
-
L1 如果出现 2 位错误怎么办
首先概率很低，舍弃该可能性
总结
- 熵：量化信息内容
- 补码；模运算
- 可变长编码；哈夫曼算法
- 汉明距离，错误检测，错误校正
奇偶校验
奇校验
x
x = x.append(0|1)
sumbit(x, 1) mod 2 = 1
偶校验 sumbit(x) mod 2 = 0
汉明距离
两个相同长度的编码，其对应数字不同的位置数量即为汉明距离。
汉明码如何修复错误
标准汉明码
标准汗汉明码，可以发现一位错误，并纠正该位错误
标准汉明码的原理，就是通过引入更多的校验位，来定位具体是哪一个数据出了问题 要引用多少校验位呢？
根据汉明不等式： $$ 2^r >= k + r + 1 $$
- k: 数据位数
- r: 校验位数
- n: k+r 总长度
假设一个四位数据 1011 k = 4，使得该不等式成立的最小 r = 3，即需要 3 个校验位，数据总长度为 7
数据排列规则 1. 汉明码坐落于 2 的幂次位置，也就是 1 2 4 2. 其他数据按序排列
上述数据排列结果如下
| 位置索引 (二进制) | 1 (001) | 2 (010) | 3 (011) | 4 (100) | 5 (101) | 6 (110) | 7 (111) |
|---|---|---|---|---|---|---|---|
| 类型 | $ p_1 $ | $ p_2 $ | $ d_1 $ | $ p_3 $ | $ d_2 $ | $ d_3 $ | $ d_4 $ |
| 含义 | 校验位1 | 校验位2 | 数据位1 | 校验位3 | 数据位2 | 数据位3 | 数据位4 |
| 数据 | 1 | 0 | 1 | 1 |
校验码计算规则，使用偶校验
-
p1 计算位置索引倒数第一位为 1 的位，并补足偶数
$ p_1 = d_1 \oplus d_2 \oplus d_4 $
-
p2 计算位置索引倒数第二位为 1 的位，并补足偶数
$ p_2 = d_1 \oplus d_3 \oplus d_4 $
-
p3 计算位置索引倒数第三位为 1 的位，并补足偶数
$ p_3 = d_2 \oplus d_3 \oplus d_4 $
至此，已经计算出了发送数据
| 位置索引 (二进制) | 1 (001) | 2 (010) | 3 (011) | 4 (100) | 5 (101) | 6 (110) | 7 (111) |
|---|---|---|---|---|---|---|---|
| 类型 | $ p_1 $ | $ p_2 $ | $ d_1 $ | $ p_3 $ | $ d_2 $ | $ d_3 $ | $ d_4 $ |
| 含义 | 校验位1 | 校验位2 | 数据位1 | 校验位3 | 数据位2 | 数据位3 | 数据位4 |
| 数据 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
校验
当校验方进行校验时，计算 3 个校验位与各自负责的数据，一旦有 1 位错误，那么该位就表示为 1。最终三个数字表示的位置，就是错误的位，其中 000 表示校验成功。
举例
假设错误位置索引为100，即第 3 个数据位。通过校验
- $ p_1 \oplus d_1 \oplus d_2 \oplus d_4 = 0 $
- $ p_2 \oplus d_1 \oplus d_3 \oplus d_4 = 1 $
- $ p_3 \oplus d_2 \oplus d_3 \oplus d_4 = 1 $
最终可得 110，恰好指向错误的数据位 3，可以进行修正
所以标准汉明码可以解决的一位错误并修正。
如果发生了两位错误
假设 d_2 d_3 均出错，那么通过计算得到的位置信号为 011，此时，汉明码认为是位置码 011 即数据位 d_1 出错。
假设此时把 d_1 纠错，此时 d_1 d_2 d_3 就全错了，那么得到的结果是 000。数学上成立，但是错误项已经变成了 3 个。
扩展汉明码
为了解决错误两位的情况，扩展汉明码