计算机网络ppt第8章

《计算机网络ppt第8章》由会员分享，可在线阅读，更多相关《计算机网络ppt第8章（32页珍藏版）》请在金锄头文库上搜索。

1、第二部分 数据传输-第8章 可靠性与信道编码主讲教师: 王兴芳2012.2 本章目的讨论通过信道编 码，如何检测发现传 输中出现的差错以及 差错控制技术，以达 到传输的可靠性。第8章 可靠性和信道编码3内容的组织 8.1 引言 8.3 传输差错对数据的影响 8.2 传输差错的三个主要源头 8.4 处理信道差错的两种策略8.5 分组码和卷积码8.6 分组差错编码举例：单奇偶校验8.7 分组码数学与（n，k）表示8.11 采用纵横奇偶校验的纠错8.12 用于因特网的16位校验和8.13 循环冗余校验码8.14 用硬件高效实现CRC8.15 自动重传请求（ARQ）机制 8.8 编码强度的测量：汉明距

2、离8.9 码簿中码字之间的汉明距离 8.10 差错检测与代价之间的权衡纠错查错48.1 传输差错引言 所有数据通信系统对差错都是敏感的。 有些问题来源于广义物理学的内在原因。而有些问题则是由仪器故障或设备没有达到工程 标准要求而引起的。 在传输中出现的往往是难以检测的小差错，并不是 完全的损坏。 许多计算机网络专注于控制差错发生以及从这种差 错中恢复过来的方法。 58.2 传输差错对数据的影响 教材P81图8.1列举了传输差错影响数据的三种主要途径 ，也指出了潜在的传输差错通常会通过特定的数据差错 表现出来。例如，一种称为毛刺（Spike）的干扰，持续时间特别 短，这种干扰往往是出现单个位错误

3、的原因。 持续时间稍长的干扰或失真则会产生突发性错误。 有时信号难以清晰区分是0还是1，而是落在一个模糊 区域，这种差错被称为擦除（erasure）。 对于突发性差错，突发尺寸或突发长度被定义为从第一 个错误码位到最后一个错误码位的总位数。教材P81图 8.2表示出这个定义。 8.3 传输差错三个主要源头 传输差错主要有三类：干扰、失真、衰减 干扰（Interference）：设备的电磁辐射（例如电 动机和背景宇宙辐射）所导致的噪声会扰乱无线电 波的传输和导线的信号传输。 失真（Distortion）：所有物理系统都会导致信号 失真。 光脉冲在光纤中传播，会出现色散。金属导 线具有电容和电感特

4、性。 衰减（Attenuation） ：信号通过介质传输后，信 号强度会变弱。 78.3 传输差错的三个主要源头 香农定理提示了一种减少差错的方法：增加信噪比（ 通过增加信号或者降低噪声） 诸如屏蔽导线这样的机 制有助于降低噪声；但物理传输系统对差错总是敏感 的，也不太可能改变传输系统的信噪比。 虽然噪声/干扰不能被完全消除，但是很多传输差错 都是可以被检测到的。在一些情况下，系统可以自动 纠正差错。 所有对差错的处理实际上是设计者要做出的权衡措施 ，系统设计者必须仔细考虑差错是否可能发生，以及 发生差错后的后果是什么。88.4 处理信道差错的两种策略 这些技术可以分为两种主要类型 :前向纠错

5、（FEC）机制分组码（例子：单奇偶校验）卷积码自动重传请求（ARQ）机制 信道编码：为了克服数据差错从而增加可靠性，人们 开发了多种数学技术，这些技术被统称为信道编码。98.4 处理信道差错策略1前向纠错 前向纠错的基本思想非常直接: 发送时在数 据中增加冗余信息，接收方收到数据后可以 根据冗余信息校验所接收数据是否正确，甚 至在有可能的时候进行纠错。 基本的差错检测机制（error detection mechanisms）能使接收方及时检测到差错的 发生。前向纠错机制则能使接收方准确判定 哪个位被改变并计算出正确的值。8.4 处理信道差错策略1前向纠错 有两类前向纠错技术：分组码、卷积码分

6、组码：先把要发送的数据划分成一系列分组 ，然后 给每个分组添加额外信息（叫做冗余），对一个分组 的编码仅仅依赖于本组的位元，而与前面已发送的位 元无关。因为这种编码机制不用将一个分组数据的状 态信息携带给下一个分组，所以分组码是无记忆。 卷积码： 把数据作为一个位元序列来处理，并根据这 个连续的位元序列计算编码。因此，要计算出一组位 元编码既要依赖于当前的输入，也要依赖于此前输入 的部分位流 ，因而卷积码被称为有记忆的编码 。8.4 处理信道差错策略1 前向纠错：分组差错编码实例-单奇偶校验 使用单奇偶校验（SPC）机制冗余信息来实现差错检 测。 SPC先定义每8比特数据单元（即一个字节）为一

7、个分组在发送方传输每个字节之前，编码器在该字节中增加 一个额外的位，称为奇偶位（parity bit） 接收方收到分组后，去除奇偶位并用它校验接收字节 中的数据是否正确在使用奇偶校验前，发送方和接收方必须设定究竟是 使用偶（even）校验规则还是奇（odd）校验规则。 图8.4给出示例列举了数据字节以及使用奇 偶校验时添加的相应奇偶校验位的值。 128.4 处理信道差错策略1 前向纠错：分组差错编码实例-单奇偶校验 单奇偶校验是信道编码中能力较弱的一种形式，它 只能检测差错，不能纠正差错。 奇偶机制只能检测到奇数个位元被改变的情况。 如果9个位元（包括奇偶位）中的一个在传输期间 被改变，接收方

8、会判定接收字节无效。 然而，如果在传输期间由于突发差错引起2、4、6 或8个位元被改变，接收方则会误将接收字节归类 为有效的字节。 138.4 处理信道差错策略1 码簿：分组码数学与（n，k）表示 一个数据字集合：所有可能的消息集合。 一个编码字集合：所有可能的已编码消息。 如果一个数据字包含k个数据位和r个附加位形成一个码 字，我们就说这种编码结果是：(n, k) 编码方案，其 中n = k + r。以单奇偶校验为例：数据字分组包含8位的 任意可能组合 ，因此， k = 8，有28（或256）个可能的数 据字。发送数据含有 n = 9 位，因此有29（或512）种编码 字可能。然而，在512

9、个值中仅有一半是有效码字。 这种方案能实现成功检错的关键，在于从2n个可能的组 合中选择有效码字的子集，这个有效子集被称为码簿。148.4 处理信道差错策略1码簿 考虑n位的所有可能值集合以及形成码簿的有效子集。 如果传输中出现差错，在码字中会有1位或多位被改 变，这种变化有可能生成另一个有效码字，也有可能 生成一个无效的组合。例如，在上面讨论过的单奇偶 校验方案中，有效码字中单个位元被改变会生成一个 无效组合，但是改变两个位元则会产生另一个有效码 字。但，我们想要的是出现差错而产生无效组合的编码方 案。 理想的信道编码方案是：改变一个有效码字中的任 意位元，就产生一个无效组合。15纠错采用纵

10、横奇偶校验 纵横奇偶校验（RAC）码：在每行和每列分别增加一 个奇偶位。如图8.7示：这个RAC编码例子的 n=20，意味 着这是一个（20，12）编码方案。 16纠错采用纵横奇偶校验 纠错的原理：假定图8.7中的一个数据位在传输中被改变，接收方把接 收到的位串安排成为矩阵并重新计算奇偶位，显然有两个 计算结果将与原定的偶校验规则不相符。如图8.8所示， 单个位元差错将导致纵向奇偶位和横向奇偶位的计算结果 与原定的奇偶检验规则不相符，分别对应了出错码位所在 的行和列，从而可以唯一地确定出错码位的位置。 17纠错采用纵横奇偶校验 接收方使用计算的奇偶位判定哪个确切的数据 位有差错，然后纠正数据位

11、。因此，RAC可 以纠正所有单个数据位被改变的差错情况。 如果使用RAC编码的数据块中差错位多于一 个，会怎么样呢？ RAC只能纠正单个位差错。 当有两或三个位被改变时 ，使用RAC编码将能检测到奇数 个码位的差。检错用于因特网的16位校验和 因特网校验和：由一个16位的反码校验和构成，因 特网校验和不强求数据字要固定长度 ，这种算法允 许报文为任意长度，对整个报文计算校验和。 实质上，因特网校验和是把报文中的数据当作一系 列16位的整数来处理，如图8.9所示。 19检错用于因特网的16位校验和 发送方：把逐个16位整数值相加，最后对和值计算其反码作 为校验和 ，并将此结果发送出去。 接收方：

12、为了验证报文是否出错，执行相同的计算过程即可 。 教材P85 算法8.1给出了计算的细节。 为什么校验和是计算总和的算术反码而不直接 使用和值呢？为了效率接收方可以使用与发送方相同的算法，相加 的整数中还包括校验和本身。 20检错循环冗余校验码 循环冗余检验码（CRC）：在高速数据网络中使用的一种信 道编码。 CRC码的三个关键特性：任意程度报文、出色的 检错能力、快速硬件实现。 n 在已经国际标准化的网络协议中，几乎都采用循环冗余校验 码（简称CRC码），它的检错能力比奇偶校验码高得多。n 编码原理简述如下：检错循环冗余校验码（续） 为了理解编码原理，举一个简单得例子：循环冗余校验码接收端处

13、理n在接收端，对CRC码的译码过程与发送端的编码 过程是一样的，然后加上一个出错判决即可： n（1）将收到的已编码字（包括信息码字和校验 码）放入寄存器中，用同样的生成多项式G(x)除 它； n（2）如果相除的结果余数R(x)=0，则表示该码 字未发生差错；否则，若R(x)不等于0，则表示 该码字已发生差错。应当注意 n 仅用循环冗余检验 CRC 差错检测技术只能做到无 差错接受(accept)。n “无差错接受”是指：“凡是接受的数据（即不 包括丢弃的数据），我们都能以非常接近于 1 的 概率认为这些帧在传输过程中没有产生差错”。n 也就是说：“凡是接收端接受的数据都没有传输 差错”（有差错

14、的帧就丢弃而不接受）。要做到 “可靠传输”（即发送什么就收到什么）就必须 再加上其它机制。 24检错用硬件高效实现CRC 计算CRC所需的硬件简单得令人惊奇，它只是一个带 有异或（exclusive or或xor）门的移位寄存器（ shift register）而已，其中在某些位之间插入的 异或门用来执行异或运算。 图8.13图示说明了图8.12中3位CRC计算所需要的硬 件。 268.4 处理信道差错策略2ARQ ARQ：需要发送方的合作发送方和接收方之间交换信 息，以确保接收方所接收的所有数据都是正确的。 ARQ特别适用于下层系统提供差错检测但不提供差错纠正 的情况。许多计算机网络使用CR

15、C检测传输差错,在传输方 案中增加ARQ机制（将在传输层TCP那一章讲到）即可确保 报文能正确传送到目的地。如果某报文发生了传输差错， 接收方将其丢弃，要求发送方重传该报文的一份副本. ARQ技术主要分为两类:停等式ARQ:连续ARQ 返回N组连续ARQ 选择重发连续ARQ停等式ARQ对应于协议停等 式流量控制，连续ARQ对应 于滑窗式流量控制，它们有 机地结合在一起，构成一个 可靠的数据传输过程。 返回278.5 编码强度的测量 ：汉明距离 没有哪种信道编码方案是完全理想的！对于实际方案， 就存在这样的问题：由一个有效码字转变为另一个有效 码字，最少要改变多少个位元？ 汉明距离：给定两个n位

16、的位串，汉明距离定义为两个位 串中对应位不同的数量（对两个位串进行异或（xor）运算 可得出）。图8.5说明了这个概念。 288.5 编码强度的测量 码簿中码字之间的汉明距离 差错能否将一个有效码字转换成为另一个有效码字 为了测量这样的转换，我们来计算一下给定码簿中所 有码字之间的汉明距离。 作为一个小例子，考虑对2位长的数据字应用偶校验。 图8-6列举了4个可能的数据字、4个添加奇偶位后的可 能码字以及码字之间的汉明距离。 我们使用dmin表示码簿中所有码字之间的最小汉明距离 （minimum Hamming distance）到底要多少位差错才会引起从一个有效码字转换成为 另一个有效码字？ 找到这个答案