计算机网络水平奇偶校验码

A. 奇偶校验原理

奇偶校验原理是通过计算数据中‘1’的个数是奇数还是偶数来判断数据的正确性。校验的数据后加—位校验位或校验字符用作校验码实现校验。校验位的生成方法。奇校验：确保整个被传输的数据中‘1’的个数是奇数个，即载荷数据中‘1’的个数是奇数个时校验位填‘0’否则填‘1’；偶校验：确保整个被传输的数据中‘1’的个数是偶数个，即载荷数据中‘1’的个数是奇数个时校验位填‘1’，否则填‘0’。

使用奇偶校验码校验的特点：

校验处理过程简单，但如果数据中发生多位数据错误就可能检测不出来，更检测不到错误发生在哪一位；主要应用于低速数字通信系统中，一般异步传输模式选用偶校验，同步传输模式选用奇校验。

方式：

垂直奇偶校验码：以一个字符作为校验单位纵向生成校验码位；

水平奇偶校验码：以多个字符作为校验单位横向生成校验码位；

水平垂直冗余校验码（方阵校验码）：以多个字符作为校验单位水平垂直两个方向共同生成校验字符。

B. 奇偶校验码的基本分类：

垂直奇偶校验又称为纵向奇偶校验,它是将要发送的整个信息块分为定长p位的若干段(比如说q段),每段后面按1的个数为奇数或偶数的规律加上一位奇偶位,如图2.19所示。各位信息(I11,I21,…,Ipl,I12,…,Ipq)中,每p位构成一段(即图中的一列),共有q段(即共有q列〉。每段加上一位奇偶校验冗余位,即图中的rio编码规则为
注意:此间的+指的是模二加,也即异或运算。
图中箭头给出了串行发送的顺序,即逐位先后次序为I11,I21,…,Ip1,r1,I12,…,Ipa,r2,…,儿,…,I间,rq。在编码和校验过程中,用硬件方法或软件方法很容易实现上述连续半加运算,而且可以边发送边产生冗余位;同样,在接收端也可边接收边进行校验后去掉校验位。
垂直奇偶校验方法的编码效率为R=p/(p+1)。通常,取一个字符的代码为一个信息段,这种垂直奇偶校验有时也称为字符奇偶校验。例如,在8位字符代码(即用8位二进制数位表示一个字符)中,p=8,编码效率便为8/9。
垂直奇偶校验方法能检测出每列中的所有奇数位错,但检测不出偶数位的错。对于突发错误来说,奇数位错与偶数位错的发生概率接近于相等,因而对差错的漏检率接近于1/2。 为了降低对突发错误的漏检率,可以采用水平奇偶校验方法。水平奇偶校验又称为横向奇偶校验,它是对各个信息段的相应位横向进行编码,产生一个奇偶校验冗余位,如图2.20所示,编码规则为
若每个信息段就是一个字符的话,这里的q就是发送的信息块中的字符数。
水平奇偶校验的编码效率为R=q/(q+1)。
水平奇偶校验不但可以检测出各段同一位上的奇数位错,而且还能检测出突发长度≦p的所有突发错误，因为按发送顺序从图2.20中可见，突发长度≦p的突发错误必然分布在不同的行中，且每行一位，所以可以检查出差错，他的漏检率比垂直奇偶校验方法低。但是实现水平奇偶校验码时，不论是采用硬件还是软件方法，都不能在发送过程中产生奇偶校验冗余位边插入发送,而必须等待要发送的全部信息块到齐后,才能计算冗余位,也就是一定.要使用数据缓冲器,因此它的编码和检测实现起来都要复杂一些。
同时进行水平奇偶校验和垂直奇偶校验就构成水平垂直奇偶校验,也称为纵横奇偶校实验,如图2.21所示。若水平垂直都采用偶校验,则
水平垂直奇偶校验的编码效率为R=pq/[(p+1)(q+1)]。.
水平垂直奇偶校验能检测出所有3位或3位以下的错误(因为此时至少在某一行或某一'列上有一位错)、奇数位错、突发长度<=p+1的突发错以及很大一部分偶数位错。测量表.明,这种方式的编码可使误码率降至原误码率的百分之一到万分之一。
水平垂直奇偶校验不仅可检错,还可用来纠正部分差错。例如数据块中仅存在1位错'时,便能确定错码的位置就在某行和某列的交叉处,从而可以纠正它。

C. 数据链路层的差错的检测和恢复(奇偶校验码，CRC校验，校验和)，各种运算

在原始的物理传输线路上传输数据信号是有差错的，存在一定的误码率，数据链路层存在的目的就是给原始二进制位流增加一些控制信息 ，实现如何在有差错的线路上进行无差错传输

数据设定为M位，冗余位设定为R位，如果位数满足即认为不出错，如果位数不满足即肯定出错

差错产生的原因
信道的电气特性引起信号幅度，频率，相位的畸变，信号反射，串扰，闪电，大功率电机的启停等

计算机网络中出现的差错是连续的还是离散的差错？ → 是连续的突发性的差错
比如传了一个这样的位串0001101001，连续的差错：比如一共出错了3位，连续的出错在一起。离散的差错：一共出错了3位，不是连续出的，是分散出的

保证帧正确，按序送交上层（顺序要对，不能重复也不能跳帧）。在接收方能够判断接收的数据是否正确，若错误还可能要恢复错误

纠错控制主要由接收方做，能检查出错并定位到是哪儿出错了

接收方通过反馈机制告诉发送方出错，发送方通过重发的方式恢复差错

☆自动纠错比检错反馈重发机制代价大，在发生数据丢失的情况下，只是自动纠错机制无法进行差错恢复，还是需要检错反馈重发机制

一个帧包括m个数据位，r个校验位（是冗余位，和m位的有效数据是无关的），称为n位码字（n=m+r），我们希望r尽量短，并且尽量有一个固定长度

加入了冗余位，使接收方知道有差错发生，但不知道什么差错，然后请求重发

加入了足够多的冗余位，使接收方不仅知道有差错发生，并知道哪些位发生差错

两个编码的海明距离： 两个编码不相同位的个数
例：0000000000与0000011111的海明距离是5
编码方案的海明距离： 编码方案中任两个编码海明距离的最小值
ASCII这样的连续编码的海明距离都是1

为检测d位错，编码方案的海明距离应至少为d+1
当发生d位错时，不会由一种合法编码变为另一种合法编码，也就是想要由一种合法编码变为另一种合法编码，需要d+1以上出错

对接收方来讲，它判定一个编码是否出错的唯一依据是这个编码是否是一个合法的编码。即使接收方收到了一个合法的编码，它也无法判断是否是一个合法编码，因为它不知道这个合法编码原本就是合法的，还是出错以后也依然是一个合法编码。因此需要海明距离应至少为d+1

在数据链路层一般是不用这种检错方法的，因为检错率太低

若接收方收到的字节奇偶结果不正确，就可以知道传输中发生了错误
增加奇偶校验位后海明距离由1变为2，因此根据“为检测d位错，编码方案的海明距离应至少为d+1”，可以检查出一位二进制位的差错
用这种方法，有一位出错时，就会由合法编码（奇校验时1的个数为奇数，偶校验时1的个数为偶数）变成一种非合法编码（奇数校验时1的个数为偶数，偶校验时1的个数为奇数）

为纠正d位错，编码方案的海明距离应至少为2d+1
当发生d位错时，出错编码仍然最接近于原始的正确编码

例：现在有一个编码方案，这个编码方案之中只有4种合法编码↓
0000000000
0000011111
1111100000
1111111111
它们之间的海明距离为5，按照定理，能够纠正2位错
假设接收方收到了这样的编码：0001100000，很明显这是个非法编码，怎么样纠正
呢？我们知道出错的位数是≤ 2位的，它和第一种的海明距离为2，和第二种为7，和
第三种为3，和第四种为8，离它最近的是第一种编码。它采用这种就近恢复的原则将
出错的编码恢复到原始编码

数据链路层用的最多的一种检错方法
但是高层（网络层，传输层）是不用这种检错方法的，而用检验和的方法

生成多项式G（x）
发方，收方事前约定。这里的约定是数据链路层的协议已经定义该协议使用什么生成多项式
生成多项式的高位和低位必须为1
生成多项式必须比传输信息对应的多项式短
（现在最多用的是CRC-32，生成多项式是32位，能否保证生成多项式比传输的对应的多项式短呢？从原始数据来讲保证不了，但是到数据链路层时加了传输层的头，网络层的头之后肯定能保证大于32位。比如现在的Internet网络，例如在传输层使用TCP加20个字节，在网络层IP又加了20个字节，已经超过32位了，所以肯定能保证）
理论上来讲生成多项式的阶越高，检错率越高
硬件实现CRC校验

四个多项式已经成为国际标准

CRC码（增加的r位冗余位检错码，即校验和）加在帧尾（效率比较高），使带CRC码的帧的多项式能被G（x）除尽：接收方接收时，用G（x）去除它，若有余数，则传输出错

• 模2加法运算定义为：（对应于逻辑异或）
0+0=0 0+1=1 1+0=1 1+1=0
例如0101+0011=0110
• 模2减法运算定义为：（对应于逻辑异或）
0-0=0 0-1=1 1-0=1 1-1=0
例如0110-0011=0101
• 模2乘法运算定义为：
0x0=0 0x1=0 1x0=0 1x1=1

• 模2除法运算定义为：
0 ÷1=0 1÷1=1
利用模2减求余数，余数最高位为1，则商1，否则商0，每商1位则余数减少1位，
直到余数位数少于除数位数

按位与运算：
按位与运算符”&”是双目运算符。其功能是参与运算的两数各对应的二进位相与。只有对应的两个二进位均为1时，结果位才为1，否则为0。参与运算的数以补码方式出现

例如： 9 & 5
00001001（9的二进制补码）
&
00000101 （5的二进制补码）
00000001
可见9 & 5 =1

最高位作为符号位，若符号位为0，则表示正数，若符号位为1，则表示负数
其余各位代表数值本身的绝对值（以二进制表示）
绝对值相同的正数和负数，它们除了符号位不同外，其他各位都相同

一个数如果值为正，则它的反码与原码相同
一个数如果值为负，则将其符号位置为1，其余各位为对原码相应数据位取反
（取反：二进制中有0和1两种状态，取反就是取与当前状态相反的状态，1取反等于0,0取反等于1）

正数的补码与反码，原码相同
负数的补码则将其最高位置为1，其余各位为对原码的相应数据位取反，再对整个数加1
即 X为负数时，【X】补 = 【X】反+1

（+0）补 = 00000000
（-0）反 = 11111111
（-0）补 = 11111111 + 1 = 100000000→进位1舍去→00000000

假设用一个字节表示一个数，补码的表示范围为：-128 ----- +127
用反码表示的最小值为：-128，其反码为：10000000
用反码表示的最大值为：+127，其反码为：01111111

按位或运算符”|”是双目运算符。其功能是参与运算的两数各对应的二进位相或。只要对应的两个二进位有一个为1时，结果位就为1.参与运算的两个数均以补码出现
例如：9|5
00001001
| 00000101
00001101（十进制为13）
可见9|5=13

~为单目运算符，具有右结合性。其功能是对参与运算的数的各二进位按位求反
例如：~9
~（0000000000001001）结果为：1111111111110110

按位异或运算符” ^ ”是双目运算符。其功能是参与运算的两数各对应的二进位相异或。当两对应的二进位相异时，结果为1。参与运算数仍以补码出现
例如：9^5
00001001
^ 00000101
00001100（十进制为12）

左移运算符” ＜＜ ”是双目运算符。其功能是把 ” ＜＜ ”左边的运算数的各二进位全部左移若干位，由” ＜＜ ”右边的数指定移动的位数，高位丢弃，低位补0
例如：a=00000011（十进制3），a ＜＜ 4，结果为：00110000（十进制48）

右移运算符” ＞＞ ”是双目运算符。其功能是把” ＞＞ ”左边的运算数的各二进制全部右移若干位，” ＞＞ ”右边的数指定移动的位数
例如：a=15（00001111），a ＞＞2，结果为00000011（十进制3）

计算方法例：

※CRC码计算还有一个好处：
我们希望不管m是多少位的，但是冗余位r是越短越好，而且最好位数是固定的。用这CRC码的好处就是生成多项式是多少阶的，那么最后的余数（冗余位）的位数就是多少位。如果是n阶的，那么最后就是4位

循环冗余校验法检验不出来的错的情况：收到的位串虽然是错误的，但是恰巧能被生成多项式整除，这个时候检测不出来

适用于高层协议，如IP，TCP，UDP等
校验码放在前面或后面影响都不大，所以绝大多数是放在前面的
检错率低于循环冗余校验法
在↓例子中，如果第1位和第9位同时出错，或者第2位和第10位同时出错···出错，那么它们取反相加的数是不变的，这个时候是检查不出错的。但是网络当中连续突发的错占绝大部分，这种跳跃性的出错概率很小，所以检验和的检错率还是比较高的
高层不用冗余校验法的原因是，冗余校验法主要采用除的计算方式，比累加的（校验和）计算方式效率要低，而数据链路层用这种方法可以用硬件实现，但是网络层和传输层一般只能通过软件实现，那么效率就降低了。而且数据链路层已经提供了比较可靠的支持，所以高层就可以用这种检错率相对低一点的检错法

检验字段初值置0，数据拆分成与检验字段等长的分片，不足部分补0，将所有分片逐位取反，并连续累加，丢弃最高进位，计算结果置于检验字段。接收端执行相同的过程（分段处理，取反累加，把累加出的校验和与校验码字段当中保存的校验和进行比对，如果是完全一致就没错），并将计算结果和传输过来的检验和进行比较以确定是数据是否出现差错

D. 什么是奇偶效验码

奇偶校验，内存中最小的单位是比特，也称为“位”，位有只有两种状态分别以1和0来标示，每8个连续的比特叫做一个字节（byte）。不带奇偶校验的内存每个字节只有8位，如果其某一位存储了错误的值，就会导致其存储的相应数据发生变化，进而导致应用程序发生错误。而奇偶校验就是在每一字节（8位）之外又增加了一位作为错误检测位。在某字节中存储数据之后，在其8个位上存储的数据是固定的，因为位只能有两种状态1或0，假设存储的数据用位标示为1、1、1、0、0、1、0、1，那么把每个位相加（1＋1＋1＋0＋0＋1＋0＋1＝1），结果是奇数，那么在校验位定义为1，反之为0。当CPU读取存储的数据时，它会再次把前8位中存储的数据相加，计算结果是否与校验位相一致。从而一定程度上能检测出内存错误，奇偶校验只能检测出错误而无法对其进行修正，同时虽然双位同时发生错误的概率相当低，但奇偶校验却无法检测出双位错误。
奇偶校验码是奇校验码和偶校验码的统称，是一种最基本的检错码。它是由n-1位信息元和1位校验元组成，可以表示成为（n，n-1）。如果是奇校验码，在附加上一个校验元以后，码长为n的码字中“1”的个数为奇数个；如果是偶校验码，在附加上一个校验元以后，码长为n的码字中“1”的个数为偶数个。设：如果一个偶校验码的码字用A=[an-1,an-2,…，a1,a0]表示，则：
Bk064553j-1.jpg
式中 为校验元，“+”为模二和（以后也这样表示，请注意）。式（1）通常被称为校验方程。利用式（1），由信息元即可求出校验元。另外，如果发生单个（或奇数个）错误，就会破坏这个关系式，因此通过该式能检测码字中是否发生了单个或奇数个错误。
其中，在实际应用中，又可分为垂直奇偶校验、水平奇偶校验和水平奇偶校验。

E. 计算机网络中的 奇偶校验问题

ls说的不太严谨，奇偶校验能够校验出奇数位的错误，注意是检错，不是纠错更不是防止。

F. 1．简述计算机网络的主要功能 2．什么是奇偶校验有何特点如果采用奇校验，数据“01000011”的校验位

主要功能：数据通信，资源共享，负载均衡与分布处理。
奇偶校验：是一种通过增加冗余位使得码字中“1”的个数恒为奇数或偶数的校验方法。
特点：是一种检错法，且查错能力只能是一位，无纠错能力（因为它不能指出出错的是哪一位）。
采用奇校验，数据“01000011”中“1”的个数为3，是奇数，故校验位为0（就是该数据中的最高位）

G. 奇偶检验码的工作原理和具体流程

一、工作原理

奇偶校验码由n-1位信息元和1位校验元组成，可以表示成为（n，n-1）。如果是奇校验码，在附加上一个校验元以后，码长为n的码字中“1”的个数为奇数个；如果是偶校验码，在附加上一个校验元以后，码长为n的码字中“1”的个数为偶数个。

设：如果一个偶校验码的码字用A=[an-1,an-2,…，a1,a0]表示，则：（1）式中 为校验元，“+”为模二和（以后也这样表示，请注意）。

式（1）通常被称为校验方程。利用式（1），由信息元即可求出校验元。另外，如果发生单个（或奇数个）错误，就会破坏这个关系式，因此通过该式能检测码字中是否发生了单个或奇数个错误。

二、流程

1、奇校验：就是让原有数据序列中（包括你要加上的一位）1的个数为奇数

1000110（0）必须添0。原来有3个1已经是奇数了所以添上0之后1的个数还是奇数个。

2、偶校验：就是让原有数据序列中（包括你要加上的一位）1的个数为偶数

1000110（1）必须加1。原来有3个1要想1的个数为偶数就只能再添加1。

(7)计算机网络水平奇偶校验码扩展阅读

校验码的存在：

计算机系统运行时，各个部之间要进行数据交换.交换的过程中，会有发生误码的可能（即0变成1或1变成0），由于计算机的储存是通过二进制代码来实现的的，误码会导致储存的内容发生改变。为确保数据在传送过程正确无误,常使用检验码。

优点：简单，易于硬件实现

缺点：如上述，只能检测出奇数个错误。

因为在某些场合，发生错误的情况下，绝大多数都是出现一个错误，所以奇偶校验码有着很大的实用性。

H. 奇偶校验码的特点是什么为什么说它是可靠性代码

奇偶校验码是 奇校验码 和 偶校验码 的统称.
它们都是通过在要校验的编码上加一位校验位组成.
如果是 奇校验 加上校验位后,编码中1的个数为 奇数个
如果是 偶校验 加上校验位后,编码中1的个数为 偶数个

例:
原编码 奇校验 偶校验
0000 0000 1 0000 0
0010 0010 0 0010 1
1100 1100 1 1100 0
1010 1010 1 1010 0
如果发生 奇数 个位传输出错,那么编码中1的个数就会发生变化.
从而校验出错误. 要求从新传输数据.

目前应用的 奇偶校验码 有3种.
水平奇偶校验码
对每一个数据的编码添加校验位,使信息位与校验位处于同一行.

垂直奇偶校验码
把数据分成若干组,一组数据排成一行,再加一行校验码.
针对每一行列采用 奇校验 或 偶校验
例: 有32位数据10100101 00110110 11001100 10101011
垂直奇校验 垂直偶校验
数据10100101 10100101
00110110 00110110
11001100 11001100
10101011 10101011
校验为00001011 11110100

水平垂直奇偶校验码
就是同时用水平校验和垂直校验
例:
奇校验 奇水平 偶校验 偶水平
数据 10100101 1 10100101 0
00110110 1 00110110 0
11001100 1 11001100 0
10101011 0 10101011 1
校验 00001011 0 11110100 1

I. 什么是奇偶校验

奇偶校验(Parity Check)是一种校验代码传输正确性的方法。根据被传输的一组二进制代码的数位中"1"的个数是奇数或偶数来进行校验。采用奇数的称为奇校验，反之，称为偶校验。采用何种校验是事先规定好的。通常专门设置一个奇偶校验位，用它使这组代码中"1"的个数为奇数或偶数。若用奇校验，则当接收端收到这组代码时，校验"1"的个数是否为奇数，从而确定传输代码的正确性。

奇偶校验需要一位校验位，即使用串口通信的方式2或方式3（8位数据位+1位校验位）。奇校验（odd parity）：让传输的数据（包含校验位）中1的个数为奇数。即：如果传输字节中1的个数是偶数，则校验位为“1”，奇数相反。以发送字符：10101010为例

数据和校验位发送给接受方后，接收方再次对数据中1的个数进行计算，如果为奇数则校验通过，表示此次传输过程未发生错误。如果不是奇数，则表示有错误发生，此时接收方可以向发送方发送请求，要求重新发送一遍数据。

优缺点：

• 奇偶校验的检错率只有50%，因为只有奇数个数据位发生变化能检测到，如果偶数个数据位发生变化则无能为力了╮(╯﹏╰）╭

• 奇偶校验每传输一个字节都需要加一位校验位，对传输效率影响很大。

• 奇偶校验只能发现错误，但不能纠正错误，也就是说它只能告诉你出错了，但不能告诉你怎么出错了，一旦发现错误，只好重发。

• 虽然奇偶校验有很多缺点，但因为其使用起来十分简单，故目前仍被广泛使用。

应用：

如何用编程确定一个字节中“1”个数的奇偶性？我们可以利用二进制数相加的特点：

0+0=0、1+0=1、1+1=0

可以看出，如果我们将一个字节的所有位相加

• 有奇数个“1”的字节的和为1

• 有偶数个“1”的字节的和为0

由此即可通过编程完成判断。实际应用中，实现方法很多，但这是相对简单的一种，这里不再赘述。