差错控制（检错编码）
1、差错产生的原因
概括来说，传输中的差错都是由于噪声引起的。分为两种：
全局性噪声（随机热噪声）
1、由于线路本身电气特性所产生的随机噪声（热噪声），是信道固有的，随机存在的。
解决办法：提高信噪比来减少或避免干扰。（对传感器下手）
局部性噪声（冲击噪声）
2、外界特定的短暂原因所造成的冲击噪声，是产生差错的主要原因。（例如线路突然被挤了一下）
解决办法：通常利用编码技术来解决。
差错的种类：
链路层为网络层提供的服务：无确认无连接服务（用于通信质量好的有线传输链路），有确认无连接服务和有确认面向连接服务（用于通信质量差的无线传输链路）。
2、数据链路层的差错控制
目前只针对位错这种差错，帧错将会在后面的部分进行详细讲解。
针对该种类的差错，有两类的编码可以使用，包括检错编码和纠错编码。
值得一提的是数据链路层的编码和物理层的数据编码调制不是同一种东西。物理层编码针对的是单个bit，解决传输过程中bit同步等问题，如曼彻斯特编码。而数据链路层的编码针对的是一组bit，它通过冗余码的技术实现一组二进制bit串在传输过程中是否出现了差错。（单个bit与一组bit的关系）
这里提到了冗余编码，指在数据发送之前，先按照某种关系附加上一定的冗余位，构成一个符合某一规则的码字后再发送。当要发送的有效数据变化时，相应的冗余位也随之变化，使码字遵从不变的规则。接收端根据收到码字是否仍符合原规则，从而判断是否出错。
3、检错编码——奇偶校验码
如果是奇校验，包括一位校验元后“1”的个数为奇数；如果是偶校验，包括一位校验元后“1”的个数为偶数。
练习题：
奇偶校验码特点：只能检查出奇数个bit错误，检错能力为50%（1位错、3位错、5位错等奇数个位错都可以检验出来，但偶数个位错检验不出来）.
4、检错编码——CRC循环冗余码
循环冗余码校验英文名称为Cyclical Redundancy Check，简称CRC。它是利用除法及余数的原理来作错误侦测（Error Detecting）的。就相当于，我在发送端有一串需要传输的原始数据，同时我早就规定好了一串“生成多项式”，我根据这两串数据可以求解出一小串易传输的编码（冗余码/FCS帧检验序列（Frame Check Sequences）），我把这个FCS附加在原始数据编码的后面，在接收端收到后会自行拆解开，用规定好的那串“生成多项式”再算一次验证一下，如果计算结果跟后面的FCS一致，就认为传输没有出现位错。（相同意义的计算方法，不拆解直接做除法，如果余数是0就没有出现位错）需要指出：那个计算的过程可以分为两个步骤，下面有详细介绍。之所以里面有计算的过程，是因为要将原始数据跟冗余码形成关联，有一定的映射关系在里面。
冗余码计算步骤：
1、确定生成多项式的阶数
假设生成多项式是10011
2、给原始数据补位，补充位数等于阶数。
要发送的数据是1101011011，那么补位后就变为11010110110000
3、以补位后的结果作为被除数，生成多项式作为除数，进行二进制除法运算（模2除法：与算术除法类似，但每一位除的结果不影响其它位，即不向上一位借位，所以实际上就是异或。），余数就是FCS/冗余码。
4、把冗余码附加到补位后的编码上，得到最终发送的数据：
接收端收到数据后的检错过程：把收到的每一个帧都除以同样的除数（预先规定好的生成多项式），然后检查得到的余数R。
1、余数为0，判定这个帧没有差错，接受。
2、余数不为0，判定这个帧有差错（但无法确定具体出错的位置），直接丢弃。
FCS的生成以及接收端CRC检验都是由硬件实现，处理很迅速，因此不会延误数据的传输。（硬件原理详见数字电路基础，后面小概率开这个坑）
在数据链路层仅仅使用循环冗余检验CRC差错检测技术，只能做到对帧的无差错接收，即“凡是接收端数据链路层接受的帧，我们都以非常接近于1的概率认为这些帧在传输过程中没有产生差错”。接收端丢弃的帧虽然曾经收到过，但最终还是因为有差错被丢弃。“凡是接收端数据链路层接收的帧均无差错”（笼统说法）。
差错控制（纠错编码）
1、纠错编码——海明码
海明码的基本思路是，发送端首先有一串原始数据，然后会分别在准备发送的比特串的20、21、22、23......位置插入检验码（校验码个数满足海明不等式2r>=r+k+1），这个校验码分别对应的是xxxxx1、xxxx1x、xxxx1xx、xxx1xxx......的二进制数据位（当然他们的对应关系部分重合了，但要的就是这种效果），找到对应关系后，求出满足校验码与对应的所有比特位做异或运算等于0的校验码的值，这样就完成了校验码的赋值。在接收端收到信号后，会根据固定位置将校验码拆解出来在与固定位置的对应比特位做验证性的异或运算，如果结果是0，则认为没有出错，如果结果是1，则认为对应的这组比特位里出现位错了，最后根据哪几个里面没有错的同时哪几个里面有错将位错的位置推导出来并纠正。
海明码：发现双比特错，纠正单比特错。
工作原理：在固定的位置插入与对应区域原始数据存在一定关系的校验码，根据不同区域校验码之间的相互配合找出位错发生的位置（针对单个位错）或察觉到有位错但不知道具体位置（针对两个位错）
工作流程：
1、确定校验码位数r
举例：
2、确定校验码和数据的位置
校验码会放在结果编码的2^位置，个人认为这也是海明码后面能巧妙地尽量均匀涵盖所有数据位的原因之一（如果结果编码位数恰好为无限大的2^个，那么每个校验码所对应的数据量是完全相同的，妙啊！），所以校验码P1、P2、P3、......分别被安插在了第1、2、4、8位上，剩下的位置一次填充原始数据。
3、求出校验码的值
数据位此时应该用二进制表示，便于找出校验码与数据的位置对应关系。
在图中，P1对应所有的xxx1位（D1、D2、D4、D5），P2对应所有的xx1x位（D1、D3、D4、D6），P3对应所有的x1xx位（D2、D3、D4），P4对应所有的1xxx位（D5、D6）。找出对应关系后求出令校验码与所有对应比特位做异或运算等于0的P值，赋给当前校验码。
4、检错并纠错
假设接收端收到的数据第五位出错了，变为0010111101
后面怎么做很清晰了，把校验码拿出来跟刚才相同对应位置的数据做异或运算。（值得注意的是，下图中直接将异或结果逆序组合，直接得到0101位也就是第五位出现错误。首先从原理上来细说，P1与D1、D2、D4、D5做异或等于1 说明D1、D2、D4、D5里有一个错误（默认只错了一位）；P2与D1、D3、D4、D6做异或等于0说明D1、D3、D4、D6中没有错误，因此D1、D4都没有错误所以D2和D5中间会有一个错误；继续看后面，P3与D2、D3、D4做异或等于1说明D2、D3、D4里有一个错误，结合刚才的推论，错误锁定在D2，与后面的D5、D6没错误也不矛盾，因此错误出在D2也就是第五位。图中的这个办法涉及离散数学证明）
