1、奇偶校验和CRC

1.1、差错控制

• 数据传输中出现错误不可避免，因此需要采用差错控制方法。数据通信中常用的办法是检错和纠错。
  • 检错：接收方知道有差错发生，但不知道是怎样的差错，向发送方请求重传。
  • 纠错：接收方知道有差错发生，而且知道是怎样的差错。
  • 差错控制原理：传输k位，加入r位冗余(某种算法定义)，接收方收到进行计算比较。

1.2、奇偶校验

• 奇偶校验是最常用的检错方法，能检出一位错位。
• 原理：在7位ASCIl码后增加一位，使码字中1的个数成奇数(奇校验)或偶数(偶校验)。
  • 奇校验：整个校验码(有效信息位和校验位)中"1”的个数为奇数  1011010  加1
  • 偶校验：整个校验码(有效信息位和校验位)中"1”的个数为偶数  1011010  加0

1.3、CRC循环冗余校验码(Cyclic Redundancy Check)

末尾加入CRC循环冗余校验码能检错不能纠错，广泛用于网络通信和磁盘存储。

1.判断校验位数：生成多项式的最高次方是几，校验位就是几位；

2.补齐数据位后面的0（校验位有几位就补几个0）；

3.提取生成多项式的系数 ；比如下图所示：

4.用第二步的结果，除以第三步的结果(异或运算，相同为0不同为1)，余数就是CRC校验码，余数不够位，前面补0。

1.4、练习题

2、码距、海明不等式和海明码

2.1、海明码

海明(Hamming)码是通冗余数据位来检测和纠正差错的编码方式。

海明距离(码距)：一个码字要变成另一个码字时必须改变的最小位数，即两个码字之间不同的比特数。

2.2、海明码原理

• 海明码原理：在数据中间加入几个校验码，码距均匀拉大，当某一位出错，会引起几个校验位的值发生变化。
• 海明不等式：校验码个数为k，可以表示个信息，1个信息用来表示“没有错误”，其余个表示数据中存在错误，如果满足(m为信息位，m+k为编码后的数总长度)，则在理论上k个校验码就可以判断是哪一位出现了问题。

2.3、海明码编码

• 第(i=0,1，2，3...)位是校验位，其余位存放数据。
  • 假设传送信息1001011,把数据放在3,5,6,7,9,10,11位置，1,2,4,8留作校验位。

• 校验位与数据位的关系：3=2+1，5=4+1，6=4+2，7=4+2+1，9=8+1，10=8+2，11=8+2+1

(1)、3=2+1，5=4+1，6=4+2，7=4+2+1，9=8+1，10=8+2，11=8+2+1，则3，5，7，9，11号位（包含数字1的数据位）参加1位校验，本例题按偶校验（参与校验的数据中1的个数为偶数）计算，3，5，7，9，11号位共包含3个1，为奇数，则1号位为1。；

(2)、3=2+1，5=4+1，6=4+2，7=4+2+1，9=8+1，10=8+2，11=8+2+1，则3,6,7,10,11号位（包含数字2的数据位）参加2位校验，3,6,7,10,11号位共包含4个1，为偶数，则2号位为0；

(3)、3=2+1，5=4+1，6=4+2，7=4+2+1，9=8+1，10=8+2，11=8+2+1，则5,6,7号位（包含数字4的数据位）参加4位校验，5,6,7号位共包含1个1，为奇数，则4号位为1；

(4)、3=2+1，5=4+1，6=4+2，7=4+2+1，9=8+1，10=8+2，11=8+2+1，则9,10,11号位（包含数字8的数据位）参加8位校验，9,10,11号位共包含2个1，为偶数，则8号位为0，最终得出如下数据：

• 海明码编码按照上述方式计算，假设6号位传输过程中出错，那么数据会变成下图

• 

2.3、练习题

3、Internet Checksum计算

Internet Checksum计算方法是：将所有的二进制数加起来，之后取反码。如果遇到最高位进位，要把进的那一位加到尾部，之后取反码。