6.004 笔记

项目	说明
首页	https://computation-structures.github.io/course/

量化信息 Quantifying Information

什么是信息

信息是一些数据，这些数据的特点是可以帮助消除不确定性

什么是信息量

如果一个数据消除的不确定性越多，那么包含的信息量越大

\[ I_(x_i) = log_2(\frac{1}{p_i}) \]

信息量意味着什么

在计算机中，信息量就意味着要编码这个信息需要多少 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 位错误怎么办

  首先概率很低，舍弃该可能性

总结

• 熵：量化信息内容
• 补码；模运算
• 可变长编码；哈夫曼算法
• 汉明距离，错误检测，错误校正