计算机网络(18)数据链路层:差错控制(奇偶校验码、循环冗余码、海明编码) |
您所在的位置:网站首页 › 奇偶校验位有什么用 › 计算机网络(18)数据链路层:差错控制(奇偶校验码、循环冗余码、海明编码) |
目录 1、差错控制简介 2、检错编码 2.1、奇偶校验码 2.2、循环冗余码 2.2.1、发送端发送 2.2.2、接收端接收 3、纠错编码 3.1、海明编码 3.2、纠错 1、差错控制简介概括来说,传输中的差错都是由噪声引起的。噪声有两大类:一类是信道所固有的、持续存在的随机热噪声;另一类是外界特定化的短暂原因所造成的冲击噪声。前者可以通过提高信噪比来减少或避免干扰,而后者不可能靠提高型号幅度来避免干扰造成的错差,是产生错差的重要原因。 通常利用编码技术来进行错差控制,主要有两类:自动重传请求(Automatic Retransmission reQuest,ARQ)和前向纠错(Forward Error Correction,FEC)。在ARQ方式中,接收端检测出差错时,就设法通知发送端重发,直到接收到正确的码字为止。在FEC方式中,接收端不但能发现差错,而且能确定二进制数码的错误位置,从而加以纠正。因此,差错控制又可分为检错编码(Error-etecting Code)和纠错编码(Error-Correcting Code) 2、检错编码检错编码都采用冗余编码技术,其核心思想是在有效数据被发送之前,按照某种关系附加一定的冗余位,构成一个符合某一规则的码字后再发送。当要发送你个的有效数据变化时,相应的冗余位也随之变化,使得码字遵从不变的规则。接收端根据收到的码字是否仍符合原规则来判断是否出错。常见的检错编码有奇偶校验码和循环冗余码。 2.1、奇偶校验码奇偶校验码是奇校验码和偶校验码的统称,是一种最基本的检错码。它由n-1位信息元和1位校验元组成,如果是奇校验码,那么在附加一个校验元后,码元为n的码字中“1”的个数为奇数,如果是偶数校验码,那么在附加一个校验元以后,码元为n的码字中“1”的个数为偶数。它又分为垂直校验、水平奇偶校验和水平垂直奇偶校验 注:简单来描述下就校验 比如原始码为 : 0110001 则奇校验码: 01100010 : 其中出现“1”的次数为3次 则偶校验码: 01100011 : 其中出现“1”的次数为4次 2.2、循环冗余码 2.2.1、发送端发送阅读此部分前,如果对于模2运算没有掌握的,可以点击模2运算 循环冗余码(Cyclic Redundancy Code,CRC)又称多项式码,基本思想是将传输的数据当做一个位数很长的数。将这个数除以另一个数。得到的余数作为校验数据附加到原数据后面。 任何一个由二进制数位串组成的代码都可以与一个只含有0和1两个系数的多项式建立一一对应关系。一个k位帧可以视为从X^(k-1)到X^0的k次多项式的系数序列,这个多项式的阶数为k-1,高位是X^(k-1)的系数,下一位是X^(k-2)的系数,以此类推。例如,1110011有7位,表示为多项式是X^6+X^5+X^4+X+1,而多项式X^5+X^4+X^2+X对应的位串是110110。 给定一个m bit的帧或报文,发送器生成一个r bit的序列,称为帧检验序列(FCS)。这样所形成的帧将由m+r比特组成。发送方和接收方事先商定一个多项式G(x)整除。接收方用相同的多项式去除收到的帧。如果无余数,那么认为无误差。 假设一个帧有m位,其对应的多项式为M(x),则计算冗余码的步骤如下: 加0.假设G(x)的阶为r,在待传输的数据帧的低位端加上r个0。模2除。利用模2除法,用G(x)对应的数据串去除上一步中用待传输数据串加完0之后得出的数据串,得到的就是冗余码。(共r位,前面的0不可忽略)FCS的计算过程如下: 冗余码的计算举例: 设G(x)=1101(即r=3),待传送数据M=101001(即m=6),经模2出发运算后的结果是:商Q=110101(这个商没什么用),余数R=001。所以发送出去的数据源为101001001,共有m+r位。 上式简单粗暴来说就是待原数据+冗余码(余数) 2.2.2、接收端接收现在发送端发送过去的数据是101001001 ,在接收端的G(x)=1101,用接收到的数据101001001去除以1101,如果能整除,说明数据没有出错,则原数据完整送达。不具备纠错能力 3、纠错编码 3.1、海明编码在数据通信的过程中,解决差错问题的一种方法是在每个要发送的数据块上附加足够的冗余信息,使得接收方能够推导出发送方实际发送出来的应该是什么样的比特串。最常见的纠错编码是海明码,它能发现双比特错,但只能纠正单比特错。 海明编码将码字内的位从左到右依次编号,第1位是1号,第2位是2号……第n位是n号,编号为2的幂的位(1号位、2号位、4号位、8号位等)是校验位,其余的位填入m位数据。每个校验位的取值应使得包含自身在内的一些位的集合服从规定的奇偶性(如偶性要求这些为的集合中的个数是偶数)。为了知道编号为k的数据位对哪些校验位有影响,将编号k改写为2的幂的和,如11=1+2+8,29=1+4+8+16.一个位只由扩展式所示编号的位检测,如编号11的 位只由编号为1、2和8的校验位检测。 m个信息位插入r个校验位组成m+r位码字,他们必须满足的关系是2^r >= m+r+1; 以典型的4位数据编码为例,海明码将加入3个校验码,从而实际传输7位码字: 数据位:1 2 3 4 5 6 7 代 码: p1 p2 D1 p3 D2 D3 D4 p为校验码,D为数据码 下面以数据吗1101为例子讲述海明码的编码原理。(代 码: p1 p2 1 p3 1 0 1) 此时D1=1,D2=1,D3=0,D4=1,对于数据位的编号,有3=1+2,5=1+4,6=2+4,7=1+2+4。于是p1对应数据位3、5、7,令二进制位中含有p1(2^0)的与或值为0,即p1⊕D1⊕D2⊕D4=0,得出p1=1; p2对应数据位3、6、7,即p2⊕D1⊕D3⊕D7=0,得p2=0;同理得到p3=0; 因此,海明编码的结果是 1010101。 3.2、纠错还是上面那个例子,接收方收到的正确码字应该是1010101,如果D3在传输中因为干扰编程了1,那么接收方就收到了1010111。 那么接收方如何检错并纠错呢? 其实也和简单,海明码是如何算出来的,那就再算一遍,如果与或结果算出来有不为0的,那就是出错了。 例如1010111: 第一位纠错代码:p1⊕D1⊕D2⊕D4=0; 第二位纠错代码:p2⊕D1⊕D3⊕D4=1; 第三位纠错代码:P3⊕D2⊕D3⊕D4=1; 将三个纠错代码由高到低排序为二进制编码110,换算成十进制数就是6,也就是说第6位数据错了,而数据D3在海明编码后的位置正好是第六位。
人,总是要有一点精神的,不是吗
|
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |