本文首发于稀土掘金。该平台的作者 逐光而行 也是本人。
参考书籍
- 《Computer Networks (the fifth edition) 》
（注：由于我看的是英文教材，以下内容为个人理解和翻译的内容，如有不恰当之处，还望多多包涵和指出）
差错检测和纠错
- 再次提醒！必须要牢记的是：虽然在数据链路层重点讲述了检错纠错，但是它并不仅仅是在该层出现！
- 检错纠错码要用到比较高深的数学知识，如果不是特别有把握（比如对稀疏矩阵很了解）还是不要去发明创造一个算法，很多现成的协议也是在重重复复用一类码。
- 本文的重点就是掌握典型的码的思想，以触类旁通。
概述
纠错码和检错码可从冗余信息的长度判断。
加入冗余信息足够多的，有纠错功能；只加适量冗余信息的，仅有识别错误功能。
纠错的一般应用是FEC(forward error correction,前向纠错，用于噪声信道）
对错误的建模
错误的特征：
- 影响正常信号的 错误 发生几率远大于仅仅是某个无关紧要的位发生了错误发生的几率
- 错误一般是集中而非分立的
- 在可擦除信道中，可知道错误的位置（因为可知道是哪一位发生了错误），这比那些直接丢掉位的信道好
纠错码分类
有以下四类：
- 汉明码
- 二进制卷积码
- Reed-Solomon Codes(是个人名，直译不太合适）
- 低密度奇偶校验码
本文要讨论的码是系统、线性的。
即：数据和冗余码一同被发送，且冗余码长度与数据位长度呈线性关系。
汉明距离
- 汉明距离:两个码字异或后1的个数
- 若检测d个错误，需要d+1位
- 若纠正d个错误，需要2d+1位
- 缺点：无法纠正2倍数的错误以及侦测4倍数的错误
纠正一位错误的汉明码纠错原理及应用
原理：假设数据正确位有m位，冗余位r位，传输过去的数据是n位
但实际数据的顺序肯定不是这样的。
如果这m位每一位都发生了错误，每个都需要n+1位去表示。
有如下等式成立：
$(n+1)2^m<=2^n$
又因为n=m+r，所以可推导出如下等式：
$(m+r+1)<=2^r$
汉明码是这么用的:
2的i次方的位为校验位，可以根据一些规则去设置（后面细说）；其余位为数据位。
如何确定一个数据位的校验位？
将其拆分为2的i次方相加的形式。
例如:$5=2^2+2^0$,第0位和第2位是该数据位的校验位。
那么这个概念有什么用呢？——————用于设置编码的校验位。
发送方设置发送含纠错信息的编码
前面提到，发送方可以与接收方约定好校验是以奇校验还是偶校验的形式，对于每一个仍待确定的校验位，检查所有能含有该校验位的数据位（用到了这个概念），计算1的数量，如果是偶校验，但是目前1的个数是奇数，说明该校验位还需要补一个1，反之则不能再补，只能填0.
以此类推，把所有的校验位补齐。
整个发送编码也就确定了。
接收方如何纠错
- 初始置counter为0，检查所有校验位。
- 如果校验位和奇偶规则不一致，则该校验位有问题，将校验位的值累加值counter。
- 最后，若counter为0，说明正确；若不为0，counter表示的数值指向的位为错误位。
应用
可以将k个码字按行排列成矩阵，按列发送矩阵，这样每行最多只有一个错误，可以使用该汉明码了。
但是要注意的是：这只适用于错误的总数不超过行数的情况。
看原文书籍和码字都不易，还望大家多多包涵！
