计算机网络校验码_计算机类十大含金量证书「建议收藏」

目录

校验码

 校验码原理

奇偶校验码

海明校验码

循环冗余校验码

校验码

计算机系统在运行过程中，需要进行信息交换，为确保信息在传输过程中无误，通常使用效验码，对接收到的数据进行效验，常见的效验码有三种：奇偶效验码、海明效验码、循环冗余效验码。

 校验码原理

对于如下编码表：

A电脑要传输’C'(10)给B电脑，若在传输过程中发生意外，传输信息发生错误导致10变成了11，则B电脑就会获得到11的编码，由于11是一种合法的编码，解码后接收到信息D。

但对于下列的编码表：

A电脑要传输’C'(010)给B电脑，若在传输过程中发生意外，传输信息发生错误导致010变成了011（发生了一位错误），则B电脑就会获得到011的编码，由于011不是一种合法的编码，B电脑就会判断出信息发生错误，会让A电脑重新发送。若010变成了111（发生了2位错误），由于111(‘D’)是合法编码，导致B电脑会接收这个错误的信息。

引入如下概念：

码字：由若干代码组成的一个字（如编码1的11，10，编码2的101）。

 两个码字之间的距离：将2个码字逐位对比，不同位的个数称为两个码字之间的距离。

码距：各合法码字之间最小的距离。（编码1的码距为1，编码2的码距为2）

由于编码2的码距为2，即最小要改变2位才会变为另一个合法编码，也就是如果发生1位错误，则肯定是非法编码。

对于码距为k的编码表，若错误位数大于等于k，编码可能会变为另一合法编码，接收方则会接收错误信息；若错误位数小于k则会变为非法编码，被接收方判定为错误编码。

奇偶校验码

奇校验码：整个校验码（有效信息位和奇偶校验位）中“1”的个数为奇数
偶校验码：整个校验码（有效信息位和奇偶校验位）中“1”的个数为偶数

设置最高位为奇偶校验位，对于1101010的7个有效信息位的编码其奇校验码为：11101010（5个1）；偶校验码为：01101010（4个1）

假设采用的是偶校验的编码，编码为：11001010，发生错误后变为11001011（改变了1位），该编码有奇数个‘1’（5个），不满足偶校验，由此确认这个编码发生了错误，要求重新发送。若发生错误后变为11100010（改变了2位），该编码有偶数个‘1’（4个），是符合偶校验的，会被认定为有效编码。

由此可见若偶数个位发生了错误，则奇偶校验是无法判断出来的。

计算机硬件对于奇偶校验的实现（以偶校验为例）：将各个位进行异或运算，所得结果为0则符合偶校验规则，为1则不符合。
对于10001编码，他的偶检验位为，即偶校验码为010001；
对于11001编码，他的偶检验位为，即偶校验码为111001。

所以可以根据异或运算的以上性质来实现。

海明校验码

1. 海明码最多只能检测出2位错，纠正1位错
2. 海明码默认进行偶校验(除非特殊说明使用奇校验)。
3. 海明码是一串由0和1组成的序列

偶校验只能发现奇数位的错误，但无法确定是哪一位发生了错误，而海明校验码则可以确定哪一位发生了错误。

设计思路：将信息位分组进行偶校验->具有多个校验位->能标注出错位置

如何确定有多少个校验位呢？假设我们现在有n位的信息位和k位的校验位，那么k个校验位总共可以表示种状态。由于一个位置出错（纠正1位错）都需要有一种状态来表示，就要求n+k+1″>（+1的1表示正确的状态）

对于信息位1010

1. 确定海明码的位数：n+k+1 , n= 4 \Rightarrow k=3″>设信息位(1010)，共4位，检验位，共3位，对应的海明码为 
2. 确定校验位的分布
   校验位放在海明位号为的位置上，信息位按顺序放到其余位置上
   

   1	0	1		0

3. 分组
   我们需要确定是负责校验哪些位置的，我们将1,2,4的二进制码写出来，保持位数相同
   1:001     2:010   4:100 ，若将0写成’*’表示通配符，如下表：
   

   001	010	100
   **1	*1*	1**

   将1-7根据统配规则填入表中

   1	2	4
   **1	*1*	1**
   001(1)	010(2)	100(4)
   011(3)	011(3)	101(5)
   101(5)	110(6)	110(6)
   111(7)	111(7)	111(7)

   可以看出
   **1可以管理1,3,5,7
   *1*可以管理2,3,6,7
   1**可以管理4,5,6,7

4. 求校验位
   则可以让负责的校验，负责的校验，负责的校验。
   ，，
   由此则…..
   由此得出海明码：

   1	0	1	0	0	1	0

5. 查错
   或者或者中的一组不满足偶校验，则出错

6. 纠错
   首先理解一下为什么海明码能纠错

   

   若蓝色区域偶校验错误，则(1,3,5,7位中有一个发生了错误)
   1.黄色和红色区域的偶校验均正确，则说明(2,3,6,7)和(4,5,6,7)均正确，则1位置发生错误
   2.黄色区域正确，红色区域错误，则说明(2,3,6,7)正确，(4,5,6,7)中有一个错误，则5位置发生错误
   3.红色区域正确，黄色区域错误，则说明(2,3,6,7)中有一个错误，(4,5,6,7)正确，则3位置发生错误
   4.黄色和红色区域都错误，则说明(2,3,6,7)中一个错误，(4,5,6,7)中一个错误，则7位置发生错误
   同理可得其他各种情况。
   由于(1,3,5,7)是由**1负责的，所以若(1,3,5,7)发生错误，则错误位置的二进制的第3位置必然为1，若(2,3,6,7)发生错误，则错误位置的二进制的第2位置必然为1，若(4,5,6,7)发生错误，则错误位置的二进制的第1位置必然为1。
   若发生错误，设错误位置对应的二进制为
   则(若偶检验成功则为0，失败则为1)，同理可得，最终就能确定发生错误的位置

循环冗余校验码

奇偶校验会在每一个字符信息的首部或尾部添加一个奇偶校验码，对于大量传输的数据进行校验时，会增加大量的额外开销，尤其在网络通信中，传输的数据信息都是二进制比特流，因而没有必要将数据再分解成一个个字符，这样也就无法采用奇偶校验码，因此，通常采用CRC码进行校验。

CRC校验的基本原理

设生成多项式，信息码为101001

1. 增加冗余码 （校验码）
   
2. 生成多项式G(x)
   双方约定的一个(r+1)位二进制数，发送方利用G(x)对信息多项式做模2除运算，生成校验码。接收方利用G(x)对收到的编码多项式做模2除运算检测差错及错误定位。

   G(x)应满足的条件
   1.最高位和最低位必须为1
   2.当被传送信息(CRC码)任何一位发生错误时，被生成多项式做除后应该使余数不为0
   3.不同位发生错误时，模2除运算后余数不同
   4.对不为0余数继续进行模2除运算应使余数循环

   除2模运算

   除2模运算对于每一位，若不够则不用借位，即0-1=1，0-0=0，1-1=0，1-0=1，即异或运算操作。

   1.部分余数首位为1时，商为1，减除数
   2.部分余数首位为0时，商为0，减0
   3.当部分余数的位数小于除数的位数时，该余数即为最后余数

   

3. 移位相除确定CRC码
   将信息码左移r位，低位补0，对移位后的信息码，用生成多项式进行模2除运算，产生除数，CRC码为信息码+余数
   假设信息码为101001，生成多项式为1101，则余数为001，最终确定CRC码为101001 001
4. 检验与纠错
   接收方用接收到的信息与约定好的生成多项式进行模2除运算，若余数为0，则正确，不为0则发生错误。
   若接收方收到的信息为:101001 001与生成多项式（1101）进行运算得到的余数为0，则正确
   若接收方收到的信息为:101001 011与生成多项式（1101）进行运算得到的余数为010，则发生错误，错误位置为2，恰好为010的十进制数。但在这里并不能说所得余数就代表出错位置，如下表
   

   接受	余数	出错位
   101001000	001	1
   101001011	010	2
   101001101	011	3
   101000001	100	4
   101011001	101	5
   101101001	110	6
   100001001	111	7
   111001001	001	8
   001001001	010	9

   由上表可以看出出错位并不等于余数，但是有一定的联系。余数在001-111中循环出现，因为冗余码只有3位，只能表示8种情况，但是CRC码共有3+6=9位，无法表示完全。由于有r位校验位，即余数有r位，因此余数能表示种状态，为纠错范围能覆盖所有CRC码，则要求(1为正确的情况)。

因此当时，CRC码可以纠错一位，但是由于CRC码通常用于计算机网络，都是几千bit+几个校验位，因此主要为了检错，而非纠错。

黄大牙牙yyds

今天的文章计算机网络校验码_计算机类十大含金量证书「建议收藏」分享到此就结束了，感谢您的阅读。