精华内容
下载资源
问答
  • 对一个节点发送到另一个物理上连接的临近节点的链路层帧中的比特损伤进行检测和纠正,他们是链路层提供的两种服务。 2、数据(D) 3、差错检测和纠正比特(Error-Detection and-Correction,EDC) 4、未检出比特差错...

    一、常见术语

    1、比特级差错检测和纠正(bit-level reeor detection and correetoin)
    对一个节点发送到另一个物理上连接的临近节点的链路层帧中的比特损伤进行检测和纠正,他们是链路层提供的两种服务。

    2、数据(D)

    3、差错检测和纠正比特(Error-Detection and-Correction,EDC)

    4、未检出比特差错(undetected bit error)

    二、差错检测

    1、基本原理
    发送方:信息数据+冗余数据
    接收方:检查信息数据和冗余数据的关系,发现差错
    在这里插入图片描述
    2、差错检测分类

    • 奇偶校验:用来描述差错检测和纠正背后隐含的基本思想
    • 检验和方法:通常用于运输层
    • 循环冗余检测:通常应用于适配器中的链路层

    三、奇偶校验(parity bit)

    奇偶校验其实是两个校验:奇校验和偶校验
    发送信息 D 有 d 比特

    1、奇校验
    发送方只需包含一个附加的比特,选择它的值,使得这 d+1 比特(初始信息加上一个校验比特)中的 1 的总数是奇数。

    2、偶校验(一般使用)
    发送方只需包含一个附加的比特,选择它的值,使得这 d+1 比特(初始信息加上一个校验比特)中的 1 的总数是偶数。

    如果采用偶校验方案中发现了奇数个值为 1 的比特,接收方知道至少出现了一个比特差错。(更精确的说法是:出现了奇数个比特差错)
    在这里插入图片描述

    一维奇偶校验只能查看是否出现错误,不知道哪里错了,也不能改正。

    3、二维奇偶校验(two-dimensional parity)
    对每行和每列都添加一个奇偶校验位
    原来 i 行 j 列,现在 i+1 行 j+1列
    在这里插入图片描述

    因此接收方不仅可以检查出现的单个比特差错,还能够识别并纠正

    在这里插入图片描述

    四、检验和方法

    1、发送方
    将段内容作为16比特整数序列来处理
    检查和: 段内容相加(补码和)
    发送方将检查和的值放入 UDP 检查和字段

    2、接收方
    计算接收到段的检查和
    检查是否计算的检查和等于 检查和字段的值:
    NO – 检测到差错
    YES – 没有检测到差错. 尽管如此,还可能有错。

    3、计算
    在这里插入图片描述
    求和,回卷,求反后的结果就是检验和。
    接收方:传送后,把全部的3个16bit(原始两个16bit、检验和)加在一起。如果该分组中没有出现错误,和的结果应该是 1111111111111111 。如果有 0,说明分组传送出现了错误。

    五、循环冗余检测

    1、循环冗余检测(Cyclic Redundancy Check,CRC)
    (1)CRC编码也被称为多项式编码(polynomial code),因为该编码能够将要发送的比特串看作是系数为 0 和 1 的一个多项式。对比特串操作被解释为多项式算术。

    (2)循环冗余校验码CRC是计算机网络和数据通信中使用最为广泛的检错码之一。

    • 检错能力强
    • (硬件)实现简单
    • 广泛用于实践中 (ATM, HDLC)

    2、CRC算法
    D:D数据拥有 d 比特
    G:发送方和接收方需要协商一个 r+1 比特模式,称为生成多项式(G),G的最高有效位的比特(最高位)是 1
    R:发送方选择 r 个附加比特,称为R

    R 附加到 D 上,一共有 d+r 个比特(二进制),用模 2 算术恰好能够被 G 整除(没有余数),即 (D+R)/G,如果余数为非 0,接收方知道出现了差错,否则认为数据正确而被接收。
    在这里插入图片描述

    所有 CRC 计算采用模 2 算术,即在加法中不进位,在减法中不借位,意味加法和减法是相同的,等价于操作数的按位异或(XOR)运算。
    例如:

    1011 - 0101 = 1110
    1011 XOR 0101 = 1110
    

    在这里插入图片描述在这里插入图片描述

    CRC标准有8、12、16、32比特生成多项式G,一般采用32比特。

    3、例子
    D = 101110,d = 6,G = 1001,r = 3
    在这种情况下传输 9 个比特是 101110011,即 R = 01。
    把 D+R 拼到一起传送,接收方接收到信息,让(D+R)/G 即可,余数为0表示无差错。
    在这里插入图片描述

    展开全文
  • 我们知道,数据报在链路层中传输时,可能会出现比特损失(如0变成1,1变成0),我们当然不想要传输错误的数据报,因此我们需要对数据进行差错检测和纠正。 差错检测一般和纠正同时实现,差错检测技术有以下几种 奇偶...

    差错检测和纠正技术

    我们知道,数据报在链路层中传输时,可能会出现比特损失(如0变成1,1变成0),我们当然不想要传输错误的数据报,因此我们需要对数据进行差错检测和纠正

    差错检测一般和纠正同时实现,差错检测技术有以下几种

    • 奇偶校验(用来描述差错纠正以及背后的思想)
    • 检验和方法(通常更多的应用于运输层)
    • 循环冗杂检测(通常更多的应用在适配器的链路层)

    纠正的作用:当我们一个数据报出错时,一般会要求重发,而发送方重发的开始需要收到一个NAK或者超时,而纠正技术就能减少这段时延,这样就能显著提高数据传输的速度


    奇偶校验

    奇偶校验基本思想:我们假设数据D有d个比特,如果我们用的是偶校验,这在这d个比特后再加一个校验比特(0或1),让这d+1个比特中1的个数为偶数个

    例:

    D: 1 1 0 1
    偶校验:校验比特:1
    奇校验:校验比特:0
    

    校验比特一般放在一个单独的字段

    在偶检验方案中,如果接收方检查到接受到的比特中1的个数为奇数个,这说明出现了奇数个比特错误

    显然,这种校验是不够健壮的,因为当出现偶数个时,他就没办法检测出来了,但是现在先不考虑更复杂的,我们先用这个理解一个纠正技术

    二维奇偶校验:我们将数据D中的比特扩展为一个二维的矩阵,然后每一行每一列计算校验值

    例:

    发送的数据D: 101011111001110
    扩展为二维矩阵           
    1 0 1 0 1 | 1
    1 1 1 1 0 | 0
    0 1 1 1 0 | 1
    -----------
    0 0 1 0 1   0
    接受的数据D: 101011011001110
    扩展为二维矩阵
    1 0 1 0 1 | 1
    1 0 1 1 0 | 0
    0 1 1 1 0 | 1
    -----------
    0 0 1 0 1   0
    

    我们观察一下,是不是就可以发现 第二行第二列位置(2,2) 的比特出错了,这时就可以纠正该 比特


    校验和方法

    校验和方法基本思想:d中的比特被当错k比特的数据处理,校验和就是这些这些k比特数据的和

    例:

    D中:
    0110011001100000
    0101010101010101
    1000111100001100
    前两个的和为
    0110011001100000
    0101010101010101
    ----------------
    1011101110110101
    前两个的和于第三个相加的和
    1011101110110101
    1000111100001100
    ----------------
    0100101011000001
    

    将结果进行反码运算,得到校验和=1011010100111110,当接收方将其接受到的数据的和跟校验和相加的结果应该为1111111111111111,如果结果有一个比特不为1,说明出现了比特错误


    循环冗杂检测

    现在计算机网络中广泛应用的差错检测技术基于循环冗杂检测编码(CRC),CRC编码也称为多项式编码,因为该编码能够将要发送的比特串看作为系数为0和1一个多项式,对比特串的操作被称为多项式算术

    CRC基本思想:d比特的数据D,发送节点要将其发送给接收节点,它们之间必须协商一个r+1比特模式,我们将其表示为G,我们将要求G的最高位有效比特是1,CRC的关键思想在于,一个d比特的数据加上一个r比特的R,得到的d+r比特模式用摸2除法恰好能被G整除,用CRC进行差错检测的原理很简单:接收方用G去除接收到的d+r比特,如果余数为非零,则表示数据出错了

    现在问题就是如何计算出R,因为R是发送方附加上去的r个比特

    我们前面可以看到,加上R之后,接收方使用G除于D余数为0,因此R满足:

    D * 2^r XOR R = nG  
    //*2^r表示左移r位,XOR R表示将R"拷贝"上去(XOR的特点,于0XOR后的值等于自身)
    

    我们对两边都进行R异或,得到

    D * 2^r = nG XOR R
    

    我们可以看到用G/D*2^r余数刚好是R,因此我们可以这样来计算R

    R = remainder(D*2^r/G) // 也就是D*2^r/G的余数
    

    我们看一个例子:

    D=101110, d=6, G=1001, r=3

    t6hApt.png

    上面的计算为模2除法

    简单介绍一下模2除法,因为模2除法不借位,因此,图中看到的操作其实都可以看作为异或计算,当被除数的位数小于除数(G)时,就结束计算,因此我们可以看到余数为0 1 1,这个就是R,发送方在发送D时会附加3个比特R(0 1 1),这样接收方用G除于D时余数就应该为0,当余数不为0时,说明出现了比特错误(只要有一个位置的比特出错,余数就不为0

    展开全文
  • 差错检测和纠错基本概念差错检测和纠正基本概念新的改变功能快捷键合理的创建标题,有助于目录的生成...问题一:链路层为什么需要差错检测和纠正? 答:当数据从一个结点通过链路传输到另一个结点时,随时可能会在途中

    链路层的差错检测和纠正

    差错检测和纠正基本概念

    首先需要对差错检测和纠正有一个基础的理解,只要能回答上以下问题就算合格。

    前导术语:
    干扰:对有用信号的接收造成损伤。

    问题一:为什么链路层会需要差错检测和纠正?
    :因为数据在链路传输过程中,会受到干扰的影响,从而改变信号的波形。所以需要差错检测和纠正的技术,让数据帧到达接收结点时可以保证有一个可接受的准确率。

    前导术语:
    单个位差错:在给定的数据单元中(例如一个字节、字符或分组)中仅有一位发生从1到0或从0到1的变化。
    突发性差错:在数据单元中有两位或更多位发生1到0或0到1的变化。

    问题二:现实中的差错一般是单个位差错还是突发性差错?
    :用一个例子来解释:假设某条链路的传输速率是10Mbps,那一个位的持续时间就是1/10000000s。这个时间远远低于干扰的持续时间。比如某段噪声的持续时间为1ms(1/1000s),那么在10Mbps的链路上,它可以影响10_000_000 / 1000 = 1w个比特,也就是会导致这1w个比特中的多个比特产生差错,这样的差错类型当然属于突发性差错。所以,本质上受干扰影响的位的数量取决于链路的传输速率和噪声的持续时间。链路的速率越高,噪声的持续时间越长,影响的位数越多。

    前导术语:
    冗余:冗余就是多余的意思,冗余位就是用多余的01比特串来实现检错或纠错的功能。

    问题三:检错和纠错的区别是什么?谁更难实现?
    答: 检错的回答是 是或者否,只要确定是否有错即可。纠错不仅需要发现错误,更重要的是要把错误的数据改变成正确的数据。纠错的难度是远远大于检错的,因此需要更多的冗余位。而且错误的位数越多,纠错的难度就越大。纠错需要找到错误的位的具体位置,比如你有8位的数据,如果只有1个差错,出错的位置就8种,如果有2位差错,出错的位置就有整整28种可能,如果有3位就整整168种可能。所以纠错是非常难的事情,这点需要提前有一个感性的认识。

    问题四:纠错有两种方式,什么是前向纠错?什么是重传纠错?
    :前向纠错(forward error correction)是接收方通过冗余位直接纠正错误的报文。重传纠错是接收方检测出有差错后,丢弃掉有差错的报文,并且让发送方重新发送报文的技术。

    问题五:发送方和接收方实现差错检测和纠错的基本逻辑是什么?
    答: 发送方通过给数据增加对应的冗余位来检错和纠错,纠错和纠错的核心是冗余位和数据位存在某种关系,如果接收方发现对应关系符合,就认为数据没错。如果接收方发现对应关系不符合,就认为数据出错。如何添加冗余位就是具体的编码方式,编码的优秀要看冗余位的开销和方法的健壮性(也就是成功检测出错误或者纠正错误的概率越大就健壮)。

    发送方和接收方的逻辑

    问题六:有算法可以保证一定能检测或者纠正错误么?
    :并没有!任何算法只能在某些情况下可以检测出错误,好的算法能够在更多的情况下检测出错误,但是理论上总会有错误无法被检测出来。
    原理很简单,检测错误实际依赖冗余位和数据位的关系,如果数据位和冗余位都出错,但是错误的两者竟然符合算法规定的关系,那么就检测不出来。这就好比数据位是函数的自变量,编码是某个函数,冗余位是函数的值。如果数据位和冗余位都改变了,也就是自变量和函数值都改变了,但是改变后两者还是满足这个关系,那么就检测不出来。
    由于冗余位是需要额外的数据开销的。所以算法一般会规定可能检测的最多差错位数,当某个数据单元产生的差错超过了最多位数,这个编码就可能不适用了。

      
      

    块编码

    块编码是一类常用的编码方式,还有一类称为卷积编码,超过了我需要掌握的范围。下面要介绍的内容可以对块编码的基本形式有一个粗浅的理解。

    前导术语:
    块编码:就是将数据分成块,每块都进行编码,实际传输的是编码后的值。
    数据字:把原始报文分成块,每块有k位,这k位01字符串就是数据字。
    冗余位:使用某种编码方式,对数据字生成对应的一串数字,用于检错和纠错,这串数字有r位,称为冗余位。
    码字:把k位数据字和r位冗余位加在一起,得到n = k + r 位字符串,称为码字。比如数据位是 01,冗余位是1,那么加在一起,码字就是011。

    问题一:块编码数据位和码位是一一对应的么?
    :是。 块编码是一对一的,相同的数据位总是编码成相同的码字。 这里有很有趣的地方。假设数据位是k位,那么一共有2k种可能的数据位,假设码字是n = k+r位,那么码字一共有2n种可能。也就是多了2n-2k种可能。

    前导术语:
    有效码字:我们对每种可能的数据字进行编码,得到的对应码字就是有效码字,把所有有效码字列在一起,就形成了有效码字表。很容易明白,如果数据字是k位,那么有效码字的数量是2k。这是因为数据字和码字是一一对应的。

    问题二:接收方怎么检查接收到的码字是否有出错?
    :接收方的思路很简单,接收方本身就存储有有效码字的列表,如果接收到的码字是有效码字,就认为没有出错,如果接收到的码字不在有效码字表里面,就认为传输过程中出错了。
    对于上面的问题进一步思考,很自然会发现有这种尴尬的情况。接收到的码字出错了,但是意外的是它居然从原本的有效码字变成了另一个有效码字,这样接收方就无法发现这个错误了。
    对此,每个编码方案的做出了聪明的设计,可以确保在有限的出错位数的前提下,比如一个数据单元的出错位数小于等于3位,码字不可能从一个有效码字变成另一个有效码字,因此就杜绝了这种情况的发生。
    (对于上面提到的这种设计思想,只要看完下一部分讲解的最小汉明距离就可以轻而易举的理解)

      
      

    汉明距离

    术语:
    汉明距离:两个相同长度的字符串的汉明距离指对应位不同的数量。用d(x,y)表示汉明距离,其中x和y是相同长度的字符串。
    举例:比如011和110就是两个相同长度的字符串,对应的第三位和第一位都不相同,所以汉明距离就是2。
    对于01字符串,只需要将两个字符串异或,1的数量就是不同位的数量,也就是汉明距离的值。

    最小汉明距离:对于所有的码字,两两进行计算汉明距离,所有可能对中最小的值就是最小汉明距离。用dmin表示。

    问题一:最小汉明距离和最多的差错个数有什么关系?
    :这个问题非常有意思。汉明距离的本质其实就是一对字符串不同的位数。发送的码字通过不可靠的传输可能会变成其他码字,比如发送的码字是011,接收到的码字却是101,第一位和第二位都出错了,出差错的个数是2。如果把发送的码字和接收到的码字看成一对,求汉明距离,当然也会得到2.
    所以,本质上差错的个数就是发送码字和接收码字的汉明距离。
    我们担心的是差错无法被检测,无法被检测的根源是某个有效码字出错了,但是却碰巧变成了另一个有效码字。
    注意:有趣的地方来了!如果对整个有效码字表求最小汉明距离,假设dmin = s+1。这就代表任意两个有效码字的差异都大于s位。如果我们保证最多的差错个数为s位,那么不管怎么出错,码字都没办法从一个有效码字变成另一个有效码字!这就保证了有效码字表在给定最多差错个数的前提下是绝对有效的。

    从几何意义上看待最多差错个数与最小汉明距离的关系。
    假设原本码字的值为x,出错的最多个数为s。那么所有出错的可能都在以x为圆心,s为半径的圆内部和边上。如果有效码字表的最小汉明距离为s+1,那么其余的有效码字一定在圆外,和出错的码字没有任何地方有重叠。
    差错检测中最小汉明距离的集合意义
    图片说明:x是发送的有效码字,y是任一其他有效码字。空心圆表示某个出错后的可能结果。由于出错的结果都在圆内,所以不可能从一个有效码字变成另外一个有效码字。

    问题二:纠错的最小汉明距离和最多出错位数的关系是什么?
    :先看下图,假设可能出错位数为t位,那么每个有效码字可能出错的结果就在以自身为中心,t为半径的圆内。比如下图的x区域和y区域。如果有效码字表的最小汉明距离大于2t,那么每个有效码字出错的结果就没有重叠。如果得到某个出错后的结果,就可以倒推出对应的唯一有效码字(也就是圆心的值)。这样就可以实现纠错了。

    图片说明:x和y代表任一有效码字,t为码字的最多可能出错位数。某个有效码字出错的可能结果(图中用空心圆代表)都在一个以自身为中心,半径为t的圆里面。只要有效码字表的最小汉明距离大于2t,那么任一两个有效码字可能的出错结果就没有重叠。

    问题三:任何编码方案需要的三个参数是什么?
    :这三个参数是 码字长度n,数据字长度k和最小汉明距离dmin,表示为C(n,k) 和单独的dmin表达式。
      
      

    线性块编码

    目前几乎所有的块编码都属于线性块编码。

    线性块编码的正式定义我不需要掌握,我只给出线性块编码的非正式定义。

    术语:
    线性块编码:任何两个有效码字的异或会产生另一个有效码字。

    需要记住的结论:线性块编码的最小汉明距离等于具有最小1的个数的非零有效码字中的1的个数。
    分析:这可能是一个好用的数学结论,因为直接用定义求最小汉明距离,需要求很多次异或。但如果已知这种编码是线性块编码,只需要找拥有最少1的个数的非零有效码字,然后看它有几个1就可以了。
      
      

    奇偶校验编码

    奇偶校验编码很适合用来理解差错检测和纠错具体是如何通过编码实现的,学会了这个编码,其他复杂的编码也能举一反三。

    简单奇偶校验编码有奇校验方案偶校验方案,两种方法本质是一样的,这里只解释偶校验方案。
    偶校验方案:假设数据字为k位,我们把数据字的每一位都加起来,准确说是做模2运算,如果得到的值为1,那么冗余位就是1,如果得到的值是0,那么冗余位就是0。这样的结果是码字的所有位进行模2运算结果一定是0(0是偶数,所以是偶校验方案)。

    补充:已知简单奇偶检验编码的偶校验方案是线性块编码
    问题一:简单奇偶校验编码的偶校验方案的最小汉明距离是多少?它检错的最大位数是多少?它能纠错么?
    :由于它是线性块编码,所以最小汉明距离是2,能检错的最大位数是1,不能纠错。
    补充:虽然奇校验方案不是线性块编码,但是它和偶校验方案各方面其实是差不多的。
    其实奇偶校验编码可以检测奇数位的差错,但是无法发现偶数位的差错,这点其实是不言而喻的。

    更好的奇偶校验编码其实是两维奇偶校验编码。

    用以下例子说明:这个例子一共有4x7位的数据字,将7位放在单独一行,就得到一个矩阵,分别对每一行每一列求奇偶校验位,可以得到一个5行8列的码字矩阵。
    行和列奇偶位的设计
    图片说明:将4x7位数据字分别放在单独的行中,形成一个矩阵。分别计算每行和每列的奇偶校验位,就会得到一个5行8列的码字矩阵。将整个矩阵发给接收方,接收方可以根据码字检测出任何位置的最多三个差错。

    允许最多单个位出错的情况

    图片说明:假设原本码字的第二行第三列的1变成了上图的0。这个错误会同时影响对应行对应列的2个奇偶校验位。接收方分别计算第二行和第三行的模2运算结果,就可以纠正这个错误。

    但特别注意:请看下图,如果出现了2个差错,而且两个差错都是在奇偶校验位,你会发现系统检测的结果和上图单个位出错系统检测的结果一模一样(注意箭头的位置和个数都一样)。这样就没办法区分到底是哪一种。
    这就说明,二维奇偶校验编码只能纠正单个位的错误,如果错误可能出现2个或者多个,单个位的纠错都不能保证准确了。

    图片说明:如果出现2个错误,而且都是奇偶校验位出错,就会和单个位出错混淆。


    图片说明:如果是单个奇偶校验位本身出错了,那么只会影响一处,也可以识别区分。(列的奇偶校验位出错的情况是类似的,我就不插入图片了)

    结论:如果最多出错可能是单个位,那么二维奇偶校验可以实现差错纠正。

    允许最多2个差错的情况

    图片说明:两个差错出现在不同行不同列,会出现4个两两并列的箭头。

    图片说明:两个差错出现在相同行不同列,会出现两个并列的箭头。(两个差错出现在不同行相同列情况类似)

    图片说明:如果一个错误在数据位,另一个错误在和数据位同行的奇偶校验位,就会出现一个箭头,这个情况和单个奇偶校验位出错的箭头情况一模一样,所以无法百分百成功纠错,但是可以成功检错


    图片说明:如果一个错误在数据位,另一个错误在不同行不同列的奇偶校验位,那么会出现3个箭头。


    图片说明:如果两个错误都出现在一列的奇偶校验位,那么会出现两个并列的箭头。这个情况和2个错误出现在同列的数据位一模一样

    图片说明:如果错误出现在不同行不同列的奇偶校验位,会和错误出现在单个数据位情况一模一样

    结论:经过繁琐严谨的讨论,如果最多错误位数是2个,仅仅可以检错,无法纠错。

    最多错误允许达到3个的情况
    在这里插入图片描述
    图片说明:下图你会发现一共产生了三个错误,但是计算每行每列的奇偶校验位,你会发现完全符合规定。也就是说,当错误达到3个,有可能无法检查错误。

    综合所有的讨论:二维奇偶校验位的检错能力是2位,纠错能力是最多1位。

      
      

    汉明编码(Hamming code)

    汉明编码的能力

    汉明码可以纠正单个错误,看起来和二维奇偶校验编码的能力差不多。但其实汉明码的算法远远比二维奇偶校验编码神奇。
    1.汉明码需要的冗余位要比二维奇偶校验码少得多。
    2.汉明码计算的校验子(也就是用来纠正错误的计算结果)刚好等于错误比特的位置
    比如:如果是第3位出错,接收方计算码字后,得到的校验子就是011,也就是十进制的3.
    如果是第7位出错,接收方计算码字后,得到的校验子就是111,也就是十进制的7.
    也就是说,汉明码用来实现单个错误的差错纠正简直太完美了,实现也会非常的容易!

    汉明码的计算方法

    为了便于理解,先只讲述7位码字的情况。

    7位码字的情况是:有4位数据字,3位冗余位,所以生成的有效码字是3+4 = 7位。也就是实际传输需要传输7位。这部分你目前就当作是已知条件。

    比如我们要传输的数据字是0011,问题是要如何生成对应的有效码字呢?
    答:问题其实分为2步,第一步:求出对应的3位冗余位。第二步:将对应的冗余位插入数据位的合适位置中。
     注意,我们先做第二步,假设冗余位是r1,r2,r4。然后把冗余位分别插入数据位的第1位,第2位和第4位。
    也就是第20位,第21位和第24位。
    然后对得到的码字进行从1到7的编号:

    图片说明:之后计算出来的冗余位会放到上图所示的第1,2,4位上。

    之后找出数据字中值为1的位置的二进制码,比如第6位是1,对应位置的二进制码是110(也就是十进制的6),第7位也是1,对应位置的二进制码是111(也就是十进制的7),其他位要么是没算出来的冗余位,要么就是0,就不用管。

    再将这些二进制数字进行异或运算。

    最后得到的001刚好就是r4,r2,r1对应的值。也就是r1 = 1,r2= 0,r4 = 0(注意是r4r2r1和001对应,不是r1r2r4和001对应)
    把r1,r2,r4的值带入到码字r1 r2 0 r4 0 1 1中,就等于 1 0 0 0 0 1 1 这7位码字。

    我们现在将这7位码字 1000011传输到不可靠信道中,假设得到的结果有1位出错了。
    比如我们假设第5位出错了,也就是码字从1000011变成了1000111.
    我们把码字中值为1的位置的二进制码找出来,分别是 第1位001,第5位101,第6位110,第7位111.
    将这些二进制数字进行异或运算。

    得到的结果是101,刚好就是第五位出错的位置!

    巧妙的是,你只要按照这个方法算,不管你假设哪位出错,都可以用这个方法得出出错比特的位置!
    比如你假设第4位出错,那么码字会从1000011变成1001011.
    将码字中值为1的位置的二进制码找出来,分别是 第1位001,第4位100,第6位110,第7位111.
    然后把找出的二进制数字都进行异或运算(这里我就不配图了),答案是100,刚好就对应第四位

    只要你按照我讲解的顺序算一遍,我想你就知道汉明编码的运算过程了。

    汉明编码的原理

    汉明编码的计算过程其实并不麻烦,而且很好实现。背后的原理其实很巧妙,但也不太好理解,我把它分成了几个层次,你按照我讲解的层次就很好理解了。

    实际上按照原理,汉明编码的冗余位并不是这么算的,前面讲的算法已经是利用了汉明码的性质进行的更简便巧妙的运算,我们来看原本稍微麻烦的运算过程:

    假设冗余位是r1,r2,r4。假设数据位是a3,a5,a6,a7。将数据位和冗余位按照特定的方式排列起来就得到码字:r1 r2 a3 r4 a5 a6 a7。
    注意:汉明码并不和其他代码一样将冗余位全部放到数据字的后面,**而是把冗余位按照第1位,第2位,第4位,第2i位插入到了特定的位置上!也就是说,冗余位的排放位置是非常关键的!
    计算冗余位r1r2r4的算法其实是:
    r1 = a3 ⊕ a5 ⊕ a7
    r2 = a3 ⊕ a6 ⊕ a7
    r4 = a5 ⊕ a6 ⊕ a7
    用之前的例子,假设数据字为0011,对应为码字是r1 r2 0 r4 0 1 1(这里就是将冗余位插入到对应的位置上)。
    得到a3 = 0, a5 = 0 ,a6 = 1, a7 = 1.
    所以
    r1 = 0 ⊕ 0 ⊕ 1 = 1
    r2 = 0 ⊕ 1 ⊕ 1 = 0
    r4 = 0 ⊕ 1 ⊕ 1 = 0
    所以计算出的有效码字是:1000011。

    现在将有效码字通过不可靠信道传输:得到的码字变为 r1’ r2’ a3’ r4’ a5’ a6’ a7’。
    (接收方接收到的码字r1’ r2’ a3’ r4’ a5’ a6’ a7’和原本的有效码字r1 r2 a3 r4 a5 a6 a7只有1个比特可能不同)。
    然后计算校正子s1s2s3为
    s1 = a3’ ⊕ a5’ ⊕ a7’ ⊕ r1’
    s2 = a3’ ⊕ a6 ⊕ a7’ ⊕ r2’
    s3 = a5’ ⊕ a6’ ⊕ a7’ ⊕ r4’
    也就是我们把冗余位也放到了等式右边进行异或
    假设没有出错,s1 s2 s3的值应该都等于0,也就是000.
    假设r1出错了,那么只会影响到s1的值,也就是s1会变成1,结果就是s3 s2 s1 = 001。刚好就是r1所在的位置!
    假设a3出错了,那么只会影响到s1和s2的值,也就是s1和s2会变成1,结果就是s3 s2 s1 = 011。刚好就是a3所在的位置!
    我们可以建立一个校正子和差错比特和差错位置对应的表。


    为什么会有这么巧合的情况呢?
    仔细观察下面这个核心等式:
    s1 = a3’ ⊕ a5’ ⊕ a7’ ⊕ r1’
    s2 = a3’ ⊕ a6 ⊕ a7’ ⊕ r2’
    s3 = a5’ ⊕ a6’ ⊕ a7’ ⊕ r4’
    我们按照我们想要的结果倒推这个等式:
    我们希望s3 s2 s1对应的二进制值就是对应出错比特的位置。
    如果不出错,s3 s2 s1应该= 000。假设r1出错了,我们希望校正子s3 s2 s1的值为001,要想达到这样的结果,我们只能让r1出现在第一个表达式里面,同时不出现在第二个和第三个表达式里面。
    也就是表达式有一部分是这样的:
    s1 = ⊕ ⊕ ⊕ r1’
    s2 = ⊕ ⊕ ⊕
    s3 = ⊕ ⊕ ⊕

    同理:假设a3出错了,我们希望校正子的值为011(这就是a3所在的位置),要达到这样的结果,我们只能让a3出现在第一个和第二个表达式里面,同时不出现在第三个表达式里面。
    也就是表达式一部分是这样的:
    s1 = a3’⊕ ⊕ ⊕ r1’
    s2 = a3’⊕ ⊕ ⊕
    s3 = ⊕ ⊕ ⊕
    如果我们对每个可能的错误都进行这样的计算,就可以得到完整的表达式:
    s1 = a3’ ⊕ a5’ ⊕ a7’ ⊕ r1’
    s2 = a3’ ⊕ a6 ⊕ a7’ ⊕ r2’
    s3 = a5’ ⊕ a6’ ⊕ a7’ ⊕ r4’

    这个表达式是我按照想要的设计去求的,当然符合这样的需求:
    比如,如果a7出错了,我们希望校正子等于111(也就是十进制的7),所以我们让a7能同时影响三个表达式,所以上面的表达式里面都有a7’。

    也就是类似下图:1的二进制是001,就只会影响第一个表达式(类似下图1没有和其他圆有交集),7的二进制是111,会影响三个表达式(类似下图7和三个圆都有交集),5的二进制是101,就会影响第一个和第三个表达式(类似下图和两个圆有交集)

    现在你应该明白为什么要让冗余位r4 r2 r1放到第4位,第2位,第1位。
    因为它们对应的二进制位就是100,010,001.这些值都只有一个1,也就是只会影响一个校正子的值

    海明编码冗余位的数量

    问题:冗余位的数量怎么算?
    假设数据字为k位,冗余位为r位,码字为n = k + r位。
    冗余位的公式为: 2r-1-r>= k
    为什么呢?下面是推理过程
    对于某个有效码字,由于限定了传输过程只能出一个错误(因为汉明码能使用的前提就是单个差错的纠正),由于码字有n = k+r位,所以出错的情况有n种,再加上没出差错的情况,一共就是n+1种。
    所以,对于单个码字,传输后接收方接收到的码字可能结果有(n+1)种。
    由于数据字有k位,可能的数据字就有2k种,由于码字和数据字是1对1的,所以有效码字同样也有2k种。
    因此,传输后接收方接收到的所有可能码字结果为(n+1)*2k种。
    所以,码字本身的容量必须能够包含这(n+1)*2k种可能。
    码字有n位,本身容量是2n种可能码字,所以有不等式:
    2n >= (n+1)*2k
    约分后为:
    2r>=n+1
    也就是
    2r-1- r >= k
    上述公式就是海明不等式

    举例说明该不等式的应用方法:
    假设数据字为4位,那么冗余位r必须至少等于3,才可以满足上述不等式。
    也就是说4为数据字至少需要3位冗余位,一共需要7位码字。

    假设数据字有9位,那么冗余位r必须是4位。也就是一共有13位码字。
    假设数据字是8位,冗余位还是至少需要4位,这样做相当于浪费了1位数据字没有传输。

    按照汉明编码原理的计算方式和实际计算方式的联系

    假设你已知4位数据字1100,你想求出对应的有效码字是多少?
    按照原理的计算,你必须先把冗余位插入到对应位置,得到:r1 r2 1 r4 1 0 0
    得到a3 = 1 ,a5 = 1,a6 = 0,a7 = 0
    然后再推导出求冗余位的表达式:
    r1 = a3 ⊕ a5 ⊕ a7
    r2 = a3 ⊕ a6 ⊕ a7
    r4 = a5 ⊕ a6 ⊕ a7
    然后你才可以带入表达式得到r1 = 0,r2 = 1, r4 = 1
    这样你才可以得到有效码字是 0111100.
    假设第5位a5从1变成了0,让接收方收到的码字变成了 0111000
    你必须利用校正子的表达式:
    s1 = a3’ ⊕ a5’ ⊕ a7’ ⊕ r1’
    s2 = a3’ ⊕ a6 ⊕ a7’ ⊕ r2’
    s3 = a5’ ⊕ a6’ ⊕ a7’ ⊕ r4’
    才可以得到s3 s2 s1 = 1 0 1,从而得到第五位出错了。

    也就是说,没有这个表达式,你就没办法快速的计算有效码字和对于接收码字进行纠错。
    没有表达式的情况你就必须按照原理一步步去推到正确的表达式,这样是非常麻烦的

    有一种快速求出表达式的办法:
    首先我们分析表达式:
    s1 = a3’ ⊕ a5’ ⊕ a7’ ⊕ r1’
    s2 = a3’ ⊕ a6 ⊕ a7’ ⊕ r2’
    s3 = a5’ ⊕ a6’ ⊕ a7’ ⊕ r4’
    要想校正子刚好等于出差错的位置,我们的推导逻辑是:
    假设r1出错了,它的值是001,所以它只能影响第一个表达式,假设a3出错了,它的值是101,要想校正子也为101,那它就只能影响第一个和第三个表达式。
    注意看,为什么r1和a3都出现在第一个表达式?
    那是因为r1和a3的二进制第一位都为1.
    仔细分析第一个表达式你会发现:
    a3 = 011
    a5 = 101
    a7 = 111
    r1 = 001
    它们的第一位都为1.
    同理你会发现,第二个表达式的a3,a6,a7,r2第二位都为1.
    同理你会发现,第三个表达式的a5,a6,a7,r4第三位都为1.

    所以,快速求表达式的办法就产生了:
    找出第一位都为1的二进制数,就可以得到第一个表达式
    ……
    找出第i为都为1的二进制数,就可以得到第i个表达式
    由此类推就可以得到所有的表达式

    但是一开始我讲了一种更简单的计算方法,它甚至没有依赖校正子的表达式。假设数据字是1100,将数据字放入合适的位置得到码字为:r1 r2 1 r4 1 0 0 。发现第3位和第5位是1。把对应位置的二进制位拿来做异或运算:
    也就是把011和101进行异或:得到110,所以,r4,r2,r1分别为 1 1 0。
    这样立刻可以得到有效码字0111000。

    为什么这么算可行呢?这其实利用了海明编码的特性:

    注意异或的特性是:0异或任何数等于它自身。
    分析下述表达式:
    r1 = a3 ⊕ a5 ⊕ a7
    r2 = a3 ⊕ a6 ⊕ a7
    r4 = a5 ⊕ a6 ⊕ a7
    和下述表达式完全等效:
    r1 = a3 ⊕ a5 ⊕ 0 ⊕ a7
    r2 = a3 ⊕ 0 ⊕ a6 ⊕ a7
    r4 = 0 ⊕ a5 ⊕ a6 ⊕ a7

    对于a3,a5,a6,a7中值为0的部分,它们对r4,r2,r1的值没有任何影响,可以省略掉。
    如果a3的值为1,带入进上述表达式,注意有a3的那一列,从下往上得到的刚好就是011,也就是a3的位置3.
    把表达式竖着写:

    每一列的异或结果刚好等于某个表达式!
    假设a3,a5,a6,a7的某个值为0,那么会在某一行得到3个0,也就是000,任何数异或000都相当于没有做异或,所以可以省略。
    假设a3的值为1,那么会在a3的那一行得到011,这就相当于把a3的位置第三位对应的二进制数011带入上图异或。

    所以,将数据字中为1的位置对应的二进制数进行异或与求冗余位的表达式是完全等价的!
    自然得到的结果就是r4,r2,r1的结果。

    这就证明了之前的计算方法:得到数据位后,只需要找出为1的数据元素位置的二进制数字,将它们进行异或,得到的值就是冗余位的值

    假设接收到了某个码字: r1’ r2’ a3’ r4’ a5’ a6’ a7’
    本来求校正子的表达式为:
    s3 = a5’ ⊕ a6’ ⊕ a7’ ⊕ r4’
    s2 = a3’ ⊕ a6 ⊕ a7’ ⊕ r2’
    s1 = a3’ ⊕ a5’ ⊕ a7’ ⊕ r1’

    这等价于
    s3 = 0 ⊕ 0 ⊕ 0 ⊕ r4’ ⊕ a5’ ⊕ a6’ ⊕ a7’
    s2 = 0 ⊕ r2’ ⊕ a3’ ⊕ 0 ⊕ 0 ⊕ a6’ ⊕ a7’
    s1 = r1’⊕ 0 ⊕ a3’ ⊕ 0 ⊕ a5’ ⊕ 0 ⊕ a7’
    如果没有任何错误,对r1’ r2’ a3’ r4’ a5’ a6’ a7’所有为1的位置的二进制进行异或,数据字部分会得到r4,r2,r1。和冗余位的r4,r2,r1异或就会得到000.
    这和我们的预期一样,没有任何错误,得到的结果是000.

    如果某位出现了错误,比如a3出错了,假设a3是1,a3’变为0.那么a3那一列会从011变成000.少了一个011,那么得到的结果自然就是011. 和预期校正子是011是符合的。
    如果a3是从0变为1,那么会多出一个011,那么异或后的结果自然就是011,和预期的结果也是符合的。

    怎么利用汉明编码解决突发性差错

    由于汉明编码只能纠正单个位差错,所以对于多个位的突发性差错,汉明编码是不适用的。
    为此,需要对码字进行设计,把多个差错问题,转化为单个纠错的问题

    一般数据通信通过数据分组或者数据帧传输数据。
    我们把帧分为k个码字,假设每个码字长度为n位。之后我们将单个码字放在一行,k个码字就排列成k行n列的表,如下图所示:
    图片说明:这里假设k = 4也就是有4个码字,n = 7,也就是码字长度为7.

    注意,传输时,按列传输,依次传输第一列,第二列,第三列以此类推:
    也就是 0011 0101 0101 1001 1111 0011 1001
    注意,只要突发性差错影响的位数小于等于 k,也就是小于一个数据分组中码字的数量。
    就可以把多个差错均匀的分布在每个码字中,平均每个码字最多分到一个差错,就可以用汉明编码纠正了。如下图:
    图片说明:第一行是传输通道应该传输的正确数据,第二行方框中是被影响的4个突发性差错。这对应码字列表的第三列后两个错误,和第四列前两个错误。如下图所示:
    图片说明:注意看,原本是连续4位突发性错误被均匀分配到了所有码字中,每个码字(也就是单行的数据)只有一个差错,可以用汉明编码纠正了!

    一般性的学习差错检验和纠正编码的框架

    通过学习前面2种类型的编码,我们可以总结出学习编码的框架如下:
    1.编码的定义(也就是怎么辨别这种编码,要能够和其他编码做区分)
    2.编码的性质(很多编码都有常见的特征可以帮助我们得到更多的信息量)
    3.通过该编码的算法计算码字的方法(也就是只需要知道怎么算,不用搞懂原理)
    4.编码的能力,包括差错检验和纠正能力。
    5.编码的常见应用场景。
    6.编码实现的难度和对资源的消耗(比如适合用硬件还是软件实现,对需要消耗的冗余位等)
    7.编码的实现原理(也就是为什么按照这种方式计算可以达到理想的检错和纠错效果)

    循环冗余校验(CRC)编码

    我们可以按照上面提到的编码的知识框架来学习编码:

    循环冗余校验编码的定义

    这种编码英文为*(cyclic redundancy check,CRC)*,最核心的特征就是:任一一个有效码字,循环移位后,会得到另一个有效码字
    比如0010110是一个有效码字,将其所有位左移,最高位则移动到第一位,得到0101100,那么得到的0101100也一定是一个有效码字。如果将0010110所有位右移,那么第一位会变成最后一位,得到0001011,那么0001011也是一个有效码字。
    任何一个有效码字,左移或者右移都可以得到另一个有效码字,这就是循环冗余校验编码的最核心特征。

    循环冗余校验编码的特征

    1.循环冗余校验编码的定义就是它的一个特征,也就是任一有效码字循环移位会得到另一个有效码字。
    2.循环冗余校验编码是线性块编码,所以具有线性块编码的线性特征:任何两个码字异或可以得到其他有效码字

    循环冗余校验编码的计算方法

    循环编码的计算方法其实很简单:
    1.你需要用某种方法生成一个特定的除数,比如1011。
    2.你需要在数据字后面加上除数位数减一个0,比如1011,那么就在后续加3个0.
    3.你得用加完0的数据字去除以除数,做的是模二除法(不是一般性的除法),得到的余数就是冗余位

    所以,整个过程最核心的问题有几步:
    1.生成除数的算法。
    2.怎么做模2除法。

    当得到有效码字后,怎么检查码字和纠错?
    1.译码器会执行和编码器相同的工作,也就是用相同的除数去除码字。
    2.得到的余数就是所谓的校正子,校正子会被传递给决策逻辑分析器,如果是全0,那么就是有效码字,否则就是无效码字。

    我们来讲述一下怎么使用模2除法:
    模二除法其实过程很简单:
    1.首先由于模2加法和减法是不进位的,结果其实相当于异或。
    模二除法其实就是一直做异或。
    2.模二除法用来异或的除数其实有讲究,如果被除数当下提供的用来做异或的数第一位是0,那么除数就是0;否则就是1。
    这样做某步异或的结果会有一个特点:最左边的一位(也就是最高位)一定是0,之后就必须把被除数的下一位落下来,补在最右边,之后继续和除数做异或即可。
    3.最后如果被除数没有数字可以落下来,得到的余数就是想要的结果,也就是实际的冗余位。

    顶部的商是0还是1由被用来做异或的除数是全0还是特定数字决定,如果是全0,那么顶部除数那一位是0,否则是1.
    每步用来异或的除数是全0还是特定的数,由前一步落下的结果最高位是0还是1决定。如果最高位是0,那么除数是全0, 否则是特定的数。
    最后的余数一定比特定的数少一位(最高位省略了),得到的余数就是想要的冗余位。

    假设你已经得到特定的除数,以及学会了模2除法,那么你将可以完成循环冗余编码的运算:
    1.对于任一数据字,只需要在末尾加上除数-1位的0,然后将生成的结果拿来做模2运算,得到的商抛弃,余数就是冗余位。
    比如数据子是0111,除数是1011,那么就在后面加3个0,得到被除数0111000,然后进行模2运算,得到冗余位010.

    2.对于接受到的任一码字,我都可以用模2除法生成校验子,检验传输过程是否产生差错。
    比如码字0111011,除数自然依旧是1011,进行模2运算后,余数(校正子)是001,不是000,那么说明码字出错了。
    如果码字是0111010,进行模2运算后,余数是000,说明结果正确了,码字是有效码字。

    如何用多项式表示01字符串

    注意,我们会用特定算法生成除数(这个算法和抽象代数有关,不需要掌握)。
    但是这个除数是用01字符串表示的,比如1011.这样做在除数特别长的时候会很麻烦,比如
    1000 0001,一共8位。
    我们可以把01字符串和多项式联系起来,多项式x的幂次表示01的位置,系数表示01的值。
    之后省去系数为0的多项式,就可以得到最终对应的多项式了。
    如下图所示:

    多项式的加减乘除
    多项式的次数:多项式的最高幂次+1就是二进制位模式的位数了。
    多项式的加减法:这里多项式的加减就不是数学上的多项式加减了。其实是对应01字符串的模2加减。规律如下:
    1.加和减本质相同,就是做异或。
    2.加减其实是删除相同项,把不同项合并在一起(你对照着异或思考很容易理解)
    多项式移位:实际应用会把二进制左移k位(k位是冗余位的位数),并且在后面加k个0.所以,多项式的移位就通过对每一项乘以xk来实现。
    多项式除法:本质是用来对应模二除法。具体步骤如下:
    1.把除数乘以xk(k是冗余位的位数),用来和被除数对齐。
    2.使用多项式的减法运算,得到对应的结果。
    3.如果得到的结果的最高幂次大于除数的最高幂次,那么就继续让除数乘以xi,使得除数的最高幂次和结果的最高幂次相同,并进行多项式的减法。
    4.直到得到的结果的最高幂次小于除数的最高幂次,结果多项式就是我们需要的冗余位对应的多项式表示。

    多项式表示的应用:一般多项式表示主要应用在生成的除数上,我们一般会用多项式表示生成的特定除数,称其为生成多项式

    生成多项式需要满足的标准

    注意,这个标准的求解过程比较复杂,这里只展示结论:
    1.它应该至少有两项。
    2.x0项的系数应该是1。
    3.它应该不能整除xt(t是2到n-1之间)。
    4.它应该有因子x+1。

    常用协议中CRC产生的标准多项式如表所示:
    CRC-8: x8+x2+x+1 ATM头部
    CRC-10: x10+x9+x5+x4+x2+1 ATM AAL
    CRC-16 x16+x12+x5+1 HDLC
    CRC-32 x32+x26+x23+x22+x16+x12+x11 LANs
    +x10+x8+x7+x5+x4+x2+x+1

    循环冗余编码的能力和常见应用场景

    循环冗余编码的能力:对于单个位差错,双差错,奇数个差错循环冗余编码都可以绝对检查出来。对于突发性差错,循环冗余也有非常高的概率可以检测到错误
    而且循环冗余码可以轻松用软硬件实现,特别是硬件实现速度很快。所以循环冗余码的应用场景非常多。比如局域网(LAN)和广域网(WAN)中。

    展开全文
  • 链路层概述 链路层提供的服务 任一链路层的基本服务是将数据报通过单一通信链路从一个结点移动到相邻结点,但不同链路层协议能提供不同服务细节: 成帧 几乎所有的链路层协议都要讲网络层数据... 差错检测和纠正...

    链路层概述

    链路层提供的服务

    任一链路层的基本服务是将数据报通过单一通信链路从一个结点移动到相邻结点,但不同链路层协议能提供不同服务细节:

    • 成帧  几乎所有的链路层协议都要讲网络层数据报用链路层帧封装起来。
    • 链路接入  媒体访问控制(MAC)协议规定了帧在链路上传输的规则。
    • 可靠交付  保证无差错的经链路层移动每个网络层数据报。链路层的可靠交付服务时通过确认和重传取得的
    • 差错检测和纠正  通过让发送结点在震中包括差错检测比特,让接受结点进行差错检查,以此完成这项工作

    链路层的实现

    在网络中,链路层是实现在路由器的线路卡中。主机的链路层主体部分是在网络适配器(网络接口卡)中实现的,但也有一些高层链路层功能是在链路层软件组建中实现的。所以链路层是硬件和软件的结合体,是协议栈中软件与硬件交接的地方

    差错检测和纠正技术

     

    奇偶校验

    差错检测最简单的方式就是用单个奇偶校验位。如下图所示

    只需要在发送数据后面添加一个附加比特,选择它的值使得这d+1个比特中1的总数为偶数个则为偶校验(奇数个则为奇校验)。接收方只需要数一数接收的d+1个比特中1的数目即可。 偶校验方案中出现了奇数个值为1的比特,则出现差错,反之亦然。但如果发生两个比特差错,则会有未检出的差错。

    对单个奇偶校验的一种简单改进是使用二维奇偶校验。将d个比特划分为i行j列。对每行每列计算奇偶值,产生的i+j+1奇偶比特构成了链路层帧的差错检测比特。如下如所示

    显然,二维就校验可以检测并纠正出一个比特差错,能检测出两个比特差错。

    检验和方法

    在检验和方法中,d比特数据作为一个k比特证书的序列处理。将这k比特整数加起来,并且用得到的和作为差错检测比特。这个和的反码形成了携带在报文段首部的因特网检验和。接收方通过对接收的数据(包括检验和)的和取反码,并且检测其结果是否为全1比特来检测加盐和。如果出现0,就可以指示出差错。

    循环冗余检测(CRC)

    CRC编码也称为多项式编码,因为该编码能够将要发送的比特串看为系数是0和1的一个多项式,对比特串的操作被解释为多项式算术。

    CRC编码的关键思想如下图所示:对于一个给定的数据段D,发送方要选择r个附加比特R,并将它们附加到D上,使得得到的d+r比特模式用模2算术恰好能被G(发送方和接收方协商的一个r+1比特模式,称为生成多项式,通常由国际标准决定)整除。检测过程也很简单:接收方用G去除接收到的d+r比特。如果余数为非零,接收方知道出现了差错,否则认为数据正确被接收。

    所有CRC计算采用模2算术来做,在加法中不进位,在减法中不借位。即这两种操作等价于操作数的按位异或(XOR) 。乘法和除法与在二进制中是相同的(乘以2^k)就是以一种比特模式左移k个位置。

    如何计算R使得G能够除以D*2^r XOR R没有余数?

    从上面式子可以推导出R为D*2^r除以G的余数

    在D=101110,d=6,G=1001和r=3的计算过程如下所示:

    可以看到,每个CRC标准都能检测小于r+1比特的突发差错,此外,在适当的假设下,长度大于r+1比特的突发差错以概率1-0.5^r被检测到。

    运输层使用检验和,链路层使用CRC进行差错检测。原因:运输层通常是在主机中作为用户操作系统的一部分用软件实现,采用简单而快速的差错检测方案是重要的。而链路层的差错检测在适配器中用专用的硬件实现,它能快速执行更复杂的CRC操作

    展开全文
  • 差错检测与纠正技术 即对从一个节点发送到另一个物理上连接的临近节点的链路层帧中的比特损伤进行检测和纠正——>通常是链路层提供的两种服务 错误检测: EDC= 差错检测和纠正位(冗余位) D = 数据由差错检测...
  • 1.比特在传输过程中受到...2.使用差错码来检测数据在传输过程中是否产生了比特差错。 以太网帧:在帧尾包含了一个长度为4字节的帧检验序列FCS字段。 PPP帧:帧尾也包含了一个长度为两字节的帧检验序列FCS字段。 ...
  • 看看链路层中的差错检测和纠正技术

    千次阅读 多人点赞 2020-06-08 12:37:55
    内容涉及奇偶检验,二维奇偶检验,检验和以及循环冗余检测CRC
  • 用来标志上一使用的是什么协议,以便把收到的MAC帧的数据上交给上一的这个协议。数据字段 (46-1500): 正式名称是MAC客户数据字段最小长度64 字节-18字节的首部和尾部 = 数据字段的最小长度。 FCS字段 (4 ...
  • 一. 封装成帧 透明传输 差错检测
  • 数据链路层差错控制ARQ

    千次阅读 2018-01-09 15:27:13
     差错控制时链路层一个非常重要的功能,链路层需要在不太可靠的物理层来尽量实现可靠的链路层传输,靠的就是差错控制。所谓差错控制,就是对传输的数据信息进行错误检测,并加以恰当的处理。这其中就包含了多个方面...
  • 数据链路层协议有许多种,但有三个基本问题则是共同的。这三个基本问题是:封装成帧、透明传输、差错检测。本文详细介绍数据链路层的三个基本问题。 ...
  • 封装成帧(framing)就是在一段数据的前后分别添加首部和尾部,这样就构成了一个帧,接收端在收到物理上交的比特流...现实的通信链路都不会是理想的,因此数据帧在传输中通常可能发生两种错误:比特差错和传输差错
  • 差错检测教案

    2017-12-08 22:16:55
    本资源是《计算机网络》(第七版)第三章数据链路层中数据链路层协议的三个基本问题中的差错检测,先从比特差错的概念引出教学重点循环冗余检验(CRC)的概念原理,在通过例题讲解的教学方法讲解CRC中冗余码的生成,...
  • 链路层

    2018-01-16 11:20:49
    链路层链路层中,有两种截然不同类型的链路层信道。 1. 由广播信道组成,常用在局域网(Local Area Network, LAN)、无线LAN、卫星网和混合光纤电缆接入网中。 2. 点对点通信链路,例如两台路由器之间的通信链路...
  • 数据链路层---差错检测和纠正 帧同步虽然可以区分每个数据帧的起始和结束,但是还没有解决数据正确传输的两方面问题:一、如果有帧出现了错误?二、如果有帧丢失了?这都是数据链路层确保向网络层提供可靠数据传输...
  • 6--链路层和局域网

    2020-09-17 12:27:15
    链路层和局域网 链路层概述 将运行链路层协议的任何设备均称为节点[主机/路由器/交换机/WiFi接入点] 将沿着通信路径连接相邻节点的通信信道称为链路 通过特定链路时,传输节点将数据报封装在链路层...- 差错检测
  • 差错检测

    2021-04-24 18:12:02
    使用差错检测码来检测数据在传输过程中是否产生了比特差错,是数据链路层要解决的重要问题之一。 检错方法 奇偶校验 在待发送的数据后面添加一位的奇偶校验位,是整个数据(包括所添加的校验位在内)中"1"的个数为...
  • 使用差错检测法来检测数据在传输过程中是否产生比特差错,是数据链路层索要解决的重要问题之一。 在一般的帧尾部分,都会包含FCS序列,就是让接收方的数据链路层检查帧在传输过程中是否产生误码。 奇偶校验 奇偶...
  • 计算机网络-链路层

    2020-03-22 15:51:32
    文章目录计算机网络计算机网络-链路层1.1 链路层介绍1.1.1 链路层概念1.1.2 相关术语1.2 链路层功能1.3 链路层需要解决的问题1.3.1 封装成帧1.3.2 透明传输1.3.3 差错检测1.4 链路层种类1.4.1 点对点协议(Point-to-...
  • 链路层和局域网

    2020-07-01 16:33:26
    差错检测和纠错技术 奇偶校验 校验和方法 循环冗余检测 多路访问协议 信道划分协议 随机接入协议 轮流协议 局域网 链路层编址 MAC地址 地址解析协议 以太网 以太网帧结构 CSMA/CD:以太网的多路访问协议 以太网技术 ...
  • 数据链路层差错检测 在数据链路层仅仅使用循环冗余检验CRC差错检测技术,只能做到对帧的无差错接受。    产生差错的帧会被丢弃,然而过去OSI的观点是:必须让数据链路层向上提供“可靠”传输,所以在CRC检测基础...
  • 这都是数据链路层确保向网络层提供可靠数据传输服务解决的问题,也就是数据链路层的差错控制功能。 要实现差错控制功能,就必须具备两种能力:一是具备发现差错的能力,二是具备纠正错误的能力。 一、差错检测 在...
  • 数据链路层的主要功能

    万次阅读 多人点赞 2019-05-28 11:03:46
    差错检测 数据传输 透明传输其实就是指无论是什么报文都可以传输。在数据链路将网络协议封装成帧时,会在首部和尾部分别添加SOH以及EOT这两个特殊字符,接收方是根据这两个字符来确定帧首和帧尾的,如果上层...
  • 链路层信道详解

    千次阅读 2021-04-08 09:07:04
    文章目录一、链路层概述链路层提供的服务链路层在何处实现二、差错检验和纠正技术奇偶校验检验和方法循环冗余检测三、多路访问协议信道划分协议时分多路复用(TDM):频分多路复用(FDM):码分多址(CDMA):随机接...
  • 数据链路CRC差错检测技术

    千次阅读 2020-11-19 17:47:15
    本科时老师照本宣科,没有搞懂CRC差错检测到底是怎么检测的。最近看到这块了,根据自己的理解在这里记录CRC差错检测技术。 现实的通信链路都不会是理想的。这就是说,比特在传输过程中可能会产生差错:1可能会变成0,...
  • 文章目录概述链路层服务链路层实现位置差错检验和纠正多路访问链路和协议 概述 节点 运行链路层协议的任何设备,如主机,路由器,交换机,WiFi接入点; 链路 沿通信路径链接相邻节点的通信信道 链路层信道 广播信道...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 15,405
精华内容 6,162
关键字:

差错检测链路层