差错控制

传输差错的特征

• 差错产生的主要原因

  • 热噪声：传输介质内的分子热运动
  • 冲击噪声：外界干扰

• 特征

  • 热噪声 : 干扰幅度小，持续性，对模拟通信影响大。
  • 冲击噪声：干扰幅度大，突发性，对数字通信影响大

• 计算机网络通信中，差错控制主要针对冲击噪声。

  如数据率为9600bps，一次闪电持续时间为10ms，则连续破坏96位。

差错控制方法

• 通过特殊的编码（差错控制码），使接收端能够发现甚至自动纠正错误。

常用的差错控制编码有两类

• 检错码

  • 能够发现差错，但无法自动纠正差错，通过发送方重传来获得正确的数据。

• 纠错码

  • 不但能过发现差错，而且能够知道哪里出错，从而自动纠正差错

码字

• 码字有信息位和校验位（冗余位）组成。
• 设信息位为m位，校验位为r位，则码字长度为n=m+r

两个码字的距离

• 两个码字的不同位数称为这两个码字的距离。
• 例：10001001和10110001的距离为3。

海明距离

• 给定某种编码算法，就能够造出包含全部合法码字的码字表（编码系统）。该码字表中必存在着两个码字之间的距离最小，这个最小距离称为该码字表（编码系统）的海明距离。

• 海明距离决定了编码系统的检错和纠错能力

循环冗余码（CRC)

• 在数据通信领域，**CRC（循环冗余检验码）**常用的一种查错校验码，它的信息字段和校验字段的长度可以任意选定。

  • 它主要是通过对要传输的数据进行多项式计算，然后将得到的结果附在数据帧的后面在进行传输，在收方收到数据帧后就可以利用CRC码对数据进行检查，那样就可以实现对数据的检错功能。

• 实现原理如下：

  • （N，K）码就是在K位的信息码后面加上R位的监督码元，整个码长度位N位，其中信息字段就是K位，所以校验字段（也叫作监督码元）的长度就是R=N-K位。

  • 对于一个给定的（N，K）码，可以证明存在一个最高次幂为 N-K=R的多项式G(x)。根据G(x)可以生成K位信息的校验码，而G(x)叫做这个CRC码的生成多项式。

• 校验码的具体生成过程为：

• 步骤

  • 先计算出 R，用 K + R <= $2^R$ - 1；然后把 M(X) 左移 R 位，空出 R 位给校验码，即 $x^R$M(X)
    • 根据 R 得到 G(X)，这个 G(X) 的最高次幂为 R，再把 G(X) 转换成对应的R+1位二进制数，即 G(X)
    • 用左移后的 $x^R$M(X) 模2不借位除 G(X)，然后取余数，这个余数就是校验码，即 R(X) = MOD($x^R$M(X)/G(X))
    • 用余数替换 M(X) 的最后 R 位
  • 例：信息位串为 1010001**，若**G(x)= $x^4$+$x^2$+x+1，求 CRC码。
    • 7 + R <= $2^R$ - 1，所以 R = 4，$x^R$M(X) = 10100010000
  • G(X) = 10110
    • 校验码 R(X) = MOD($x^4$M(x)/G(x))

• 接受方收到一个码字后

  • 用同一生成多项式**G(x)**除该码字多项式T′(x)
    • 若MOD(T′(x)/G(x)) =0 则正确
    • 若MOD(T′(x)/G(x)) ≠0 则出错，要求重发

• CRC码不能100%的发现错误，当余数为“0” 时可能发生错误。CRC检错率取决于生成多项式G(x)

  • 若G(x)中含有x+1因子，则能检测出所有的奇数位错。
  • 若G(x)中不含有x因子，或者说，G(x)含有常数项1，那么能检测出所有突发长度≦r的突发错。
  • 若G(x)中不含有x因子，且对任何0<e≤n-1 的**e,除不尽$x^e$+1,**则能检测出所有的双位错。
  • 若G(x)中不含有x因子，则对于突发长度为r+1的 突发错误的漏校率为2-(r-1)*8.
  • 若G(x)中不含有x因子**,** 则对突发长度大于r+1的突发错误的漏校率为**$2^{-r}$**.

• 三个标准CRC生成多项式：

  • CRC-12= $x^{12}$+$x^{11}$+$x^3$+$x^2$+x+1

  • CRC-16=$x^{16}$+$x^{15}$+$x^2$+1

  • CRC-CCITT=$x^{16}$+$x^{12}$+$x^5$+1

其它差错控制编码

• 奇偶校验码
• 定比码
• 正反码

流量控制

• 链路层的流量控制是点对点的
• 传输层的流量控制是端对端的（端到端要经过多个点）

停—等协议

• 协议要求

  • 发送方发送一帧后，等待对方的应答。
  • 接收端收到一帧后，检查校验位串。若出错，返回“否认”信息；若无错，返回“确认”信息。
  • 发送端收到“确认”后，立即发送下一帧；收到“否认”则重发该帧。
  • 发送端发送一帧后，立即启动超时计时器。若超时中断，重发该帧。
  • 接收端应保存最近收到的帧序号，若下一个到达帧的序号与该序号相同，则丢弃并返回“确认”信息。

• 缺点：信道利用率低

• 优点：简单

• 信道最大利用率： U = (L/B) / (L/B + 2R)

  • B为信道速率，L为帧长，R为信号在信道中的单程传播延时，U为信道的最大利用率。

  • 如考虑由于差错造成的重发，以及帧头、校验和冗余信息，信道实际利用率达不到最大利用率，实际利用率见P

滑动窗口协议

• 基本思想

• 为提高信道利用率，允许发送方连续发送若干帧后再等待对方应答。

• 基本概念

  • 窗口：可容纳数据帧的缓冲区。
  • 发送窗口：发送方用来保存已发送但尚未经确认的数据帧。
  • 接收窗口：接收方用来保存已正确接受但尚未提交给主机**(网络层)**数据帧。
  • 窗口尺寸：窗口中可以保存的帧数目称为窗口尺寸。

• 帧序号

  • 为了保证接收方能按正确次序向主机递交数据帧而设立的临时帧序号。
  • 一般在帧控制字段中用若干位来表示帧序号。如果用3位来表示，则帧序号为0—7。当一次通信超过8帧时，则顺序重复使用这8个帧序号。

• 窗口号：对应帧序号。

• 收发规则

  
  • 只有帧序号落入当前窗口的帧才有资格发送，发送方收到对方确认信息后，将发送窗口向前滑动（顺序改变当前窗号）。
  • 只有帧序号落入当前窗口的帧才接收，否则丢弃，接收方接收窗口中的帧递交给主机后，接收窗口向前滑动（顺序改变当前窗号） 。

顺序接收管道协议（回退n)

• 接收窗口尺寸为1的滑动窗口协议，也称回退n协议。设发送窗口尺寸WT=n,接收窗口尺寸WR=1.

• 发送方可连续发送n帧而无需对方应答，但需要将已发出但尚未收到确认的帧保存在发送窗口中，以备由于出错或丢失而重发。

• 接收方将正确的且帧序号落入当前接收窗口的帧存入接收窗口，同时按序将接收窗口的帧送交给主机（网络层）。出错或帧序号未落入当前窗口的帧全部予以丢弃。

• 当某帧丢失或出错时，则其后到达的帧均丢弃，并返回否认信息，请求对方从出错帧开始重发。

• 发送方设置一个超时计时器，当连续发送n帧后，立即启动超时计时器。当超时计时器满且未收到应答，则重发这n帧

选择重传协议

• 顺序接收管道协议

  • 优点：仅需一个接收缓冲区
  • 缺点：当信道误码率较高时，会产生大量重发帧

• 另一种更好的方法：选择重传协议

  • 若某一帧出错，后面正确到达的帧虽然不能立即送网络层，但接收方可将其保存在接收窗口，仅要求发送方重传那个发错帧。其工作原理如P

三种协议总结

• 停—等协议 、顺序接收管道协议、选择重传协议都可以看成是滑动窗口协议，其差别仅在窗口的尺寸不同。

  

窗口尺寸受到的限制

• 帧序号的位数为m，则

  • WT ≥ WR
  • WT + WR ≤ 2m

• 分析：

  • 若WR > WT 会有 WR -WT 个窗口永远用不上。
  • WT+WR ≤ 2m 保证了上一轮帧序号和下一轮序号
    • 在 WT+WR 范围内不会出现重复，否则接收端无 法判断落入窗口的帧是上轮重发的还是新的帧。