读改变未来的九大算法笔记03_纠错码.png
1. 真正根源
1.1. 在电报和电话等通信系统中出现的
1.2. 理查德·汉明创造了第一批纠错码：一种近乎神奇的能侦测并纠正计算机数据中错误的算法
2. 信息理论学的一部分
2.1. Information Theory
2.2. 香农通过数学展示了有可能从根本上通过一个嘈杂的、引发错误的链接实现错误率极低的通信
2.3. 即便是极端不可靠的通信频道也可以以极低的错误率传输数据
2.4. 没有纠错码，计算机和通信系统就会比现在慢很多，功能弱许多，可靠性也会差很多
3. 计算机三项基本工作
3.1. 执行计算
3.2. 存储数据
3.3. 传输数据
4. 错误侦测及纠正的需求
4.1. 计算机要无误地存储和传输的信息量绝对是海量
4.2. 精确度达到99.999 9%也还是不够好
4.3. 必须能在存储和传输数十亿“块”信息的情况下，不犯任何一个错误
5. 杂项
5.1. overhead
5.2. 为确保消息被正确接收而发送的多余信息
5.3. 一个纠错系统的“杂项”就是在发送消息本身以外要发送的额外信息量
6. 重复把戏
6.1. 同时侦测和纠正数据中错误的方法
6.2. 要确保一些信息被正确地传输，只需重复几次该信息
6.3. 通过重复一条不可靠的消息足够多次，就可以让消息的可靠性高到让你满意为止
6.4. 假设错误随机发生。相反，如果一个恶意实体故意干扰传输，并选择制造某些错误，重复把戏都会变得不可靠
6.5. 通过使用重复把戏，不可靠通信的问题能够被解决，错误基本上能被消灭
6.6. 你发送的额外东西就是更多份原始消息
6.6.1. 杂项数量巨大，因为必须发送数份完整消息
7. 代码字
7.1. code words
7.2. 示例
7.2.1. “one”（一）、“two”（二）、“three”（三）
8. 冗余把戏
8.1. The Redundany Trick
8.2. 同时侦测和纠正数据中错误的方法
8.3. 基本原则
8.3.1. 你不能只发送原始消息，你要发送一些多余的东西以增加可靠性
8.4. 示例
8.4.1. “5 213.75”
8.4.1.1. five two one three point seven five
8.4.1.2. fiqe kwo one thrxp point sivpn fivq
8.4.1.3. 使用了一条冗余消息，所以对消息中的任何单个变化进行可靠侦测及纠正变得可行
8.4.2. 数字“367”代表了一个数
8.4.2.1. 因为这条消息中没有冗余，其中一个数字被替换，就没办法知道原始数字是多少
8.5. （7，4）汉明代码（Hamming code）
8.5.1. 理查德·汉明于1947年在贝尔实验室发明的代码之一
8.5.2. 所有事情都通过0和1完成
8.5.2.1. 现实生活中使用的所有代码也限用这两个数字
8.5.3. 在编码时，每一组4位数字都加入了冗余，由此产生了一个7位数的代码字
8.5.4. 在解码时，你首先要为接收的7位数寻找完全匹配，如果寻找完全匹配失败，就选择最接近的匹配
8.5.5. 7位数代码字中的任何错误都能得到确定无疑的纠正
8.5.6. 只能纠正7位数代码字中的一个错误
9. 校验和把戏
9.1. 不管纠错，而是将精力集中在侦测错误上
9.2. The Checksum Trick
9.3. “check”（校验）消息的“sum”（和）就是术语“checksum”（校验和）的由来
9.4. 假设我们所有的消息都只由数字组成会更方便些
9.4.1. 这是一个非常真实的假设，因为计算机用数字存储所有的信息，只有在向人展示信息时，才把数字转译成文本或图像
9.5. 简单校验和
9.5.1. Simple Checksum
9.5.2. 只需将消息中的所有数字相加，只保留结果的最后一位数，剩下的数字就是你的简单校验和
9.5.3. 只需在发送原始消息前，将原始消息的校验和附加到消息末尾即可
9.5.4. 如果只有一个错误，简单校验和绝对能保证侦测到它
9.5.5. 两个或更多错误，简单校验和或许能侦测到它们，但也有可能侦测不到
9.5.6. 示例
9.5.6.1. 4 6 7 5 6
9.5.6.2. 4+6+7+5+6=28
9.5.6.3. 只保留最后一位数8
9.5.6.4. 4 6 7 5 6 8
9.5.7. 只能保证对相对较短的消息奏效（少于10位数）
9.6. 阶梯校验和
9.6.1. Staircase Checksum
9.6.2. 像之前一样把数字相加，但每个数都要和该数字所在位阶数相乘，每个数都比前一个数大一个位阶
9.6.2.1. 楼梯台阶编号为1、2、3……依此类推
9.6.3. 示例
9.6.3.1. 4 6 7 5 6
9.6.3.2. （1×4）+（2×6）+（3×7）+（4×5）+（5×6）=4+12+21+20+30=87
9.6.3.3. 只保留最后一位数7
9.6.3.4. 4 6 7 5 6 7
9.6.4. 只能保证对相对较短的消息奏效（少于10位数）
9.7. 首先是简单校验和，其次是阶梯校验和
9.7.1. 4 6 7 5 6
9.7.2. 4 6 7 5 6 8 7
9.7.3. 可以保证这条消息要么是正确的，要么至少有三处错误
9.7.4. 只要错误不超过两处，你就都能够侦测到错误
9.7.5. 只能保证对相对较短的消息奏效（少于10位数）
9.8. 加密哈希函数（Cryptographic Hash Function）的特定校验和
9.8.1. 软件包的校验和比不上软件包大小的十万之一
9.8.2. 使用这种长度的校验和侦测错误，其失败的概率极其微小，在现实中几乎不可能失败
9.8.2.1. 尤其是在恶意敌人而非糟糕信道的随机变动对信息做出改变时
10. 定位把戏
10.1. The Pinpoint Trick
10.1.1. 能让你迅速定位一处错误
10.2. 二维奇偶校验码
10.2.1. Two-Dimensional Parity
10.2.2. 被形容为二维，是因为消息被放在有两个维度的表格（行和列）中
10.3. 如果你有一条长消息，就将其打碎成16位数长的“块”，并单独处理每“块”数据
10.4. 如果消息比16个数字短，就用0把它补成16位数
10.5. 示例
10.5.1. 4 8 3 7 5 4 3 6 2 2 5 6 3 9 9 7
10.5.2.
4 8 3 7
5 4 3 6
2 2 5 6
3 9 9 7
10.5.2.1. 重新排列成一个从左往右、自上向下读的方框
10.5.3.
4 8 3 7 2
5 4 3 6 8
2 2 5 6 5
3 9 9 7 8
10.5.3.1. 算每一行的校验和，并添加在每行的右侧
10.5.4.
4 8 3 7 2
5 4 3 6 8
2 2 5 6 5
3 9 9 7 8
4 3 0 6
10.5.4.1. 算每一栏的简单校验和，并将其添加在每列的底部
10.5.5. 4 8 3 7 2 5 4 3 6 8 2 2 5 6 5 3 9 9 7 8 4 3 0 6
10.5.5.1. 重新排列所有数，让其能以一次一个数的方式被存储或传输
10.5.5.2. 从左往右、自上向下的方式读数
10.5.6. 4 8 3 7 2 5 4 3 6 8 2 7 5 6 5 3 9 9 7 8 4 3 0 6
10.5.7.
4 8 3 7 2 2
5 4 3 6 8 8
2 7 5 6 5 0
3 9 9 7 8 8
4 3 0 6
4 8 0 6
网友评论