• 突发差错
– 一串串，甚至是成片出现的差错，差错之间有相关性， 差错出现是密集的 – 错误的信道称为有记忆信道或突发信道 – 如短波信道、散射信道 – 存储介质损坏或输出故障也可引发突发错误
一、差错分类和错误图样
• 发送数据序列： 000000001111111111 • 接收数据序列： 000010011111001011 • • • • 差错序列： 错误图样： 突发长度：12 练习： 发送数据序列：001000101111001111 接收数据序列：001000111111111111 • 错误图样：？ 突发长度：？ 1111111 7
一、检错和纠错的原理
• 码的差错和纠错能力是同信息量的冗余度 换取的 • 任何信息源发出的消息可以用“1”和“0”来 表示 • 对于最简单的只发送A和B两种消息，用“0” 代表A，“1”代表B
– 如果只传输一位二进制数，则无法判断是否为 错码
一、检错和纠错的原理
• 在信息码后添加一位监督码，形成11或00 两种码组，当接受端为10或01时则可判断 为错码； • 在信息码后添加两位监督码，形成111或 000，不仅可以判断错码，而且可以根据 “大数”法则纠正一个错误； • 以上例子中11、00或者111、000称为“许 用码组”，其余码组为“禁用码组”。
• 3种形式：
– 停发等候重发 – 返回重发 – 选择重发
• 停发等候 重发
• 返回重发
• 选择重发
（二）前向纠错
• 前向纠错系统（FEC）中，发送端的信道编码器 将输入数据序列变换成能够纠正错误的码，接收 端的译码器根据编码规律检验出错误的位置并自 动纠正。
– 优点：前向纠错方式不需要反馈信道，特别适合于只 能提供单向信道的场合。由于能自动纠错，不要求检 错重发，因而延时小，实时性好。 – 缺点:所选择的纠错码必须与信道的错误 特性密切配合， 否则很难达到降低错码率的要求；为了纠正较多的错 码，译码设备复杂，而要求附加的监督码元也较多， 传输效果就低。
（三）混合纠错检错
• 混合纠错检错方式是前向纠错方式和检错重发方 式的结合。
– 在这种系统中，发送端发出同时具有检错和纠错能力 的码，接收端收到码后，检查错误惰况，如果错误少 于纠错能力，则自行纠正；如果干扰严重，错误很多， 超出纠正能力，但能检测出来，则经反向信道要求发 端重发。 – 混合纠错检错方式在实时性和译码复杂性方面是前向 纠错和检错重发方式的折衷，
三、编码效率
• 编码效率是指一个码组中信息位所占的比 重，用R来表示 R=k/n
– k为信息码元的数目（信息位长度） – n为编码组码元的总数(编码后码组长度n=k+r) – r为监督码元的数目（监督位长度）。
四、纠错编码的分类
• 按码组的功能分
– 检错码 – 纠错码
• 按监督码与信息码元之间的关系分
二、码距与检错和纠错能力
• 码组中非零码元的数目为码组的重量，简称码重； • 两个码组中对应码位上具有不同二进制码元的位 数定义为两码组的距离，简称码距； • 任意两个码组间距离的最小值，即码组集合中任 意两元素间的最小距离称为汉明（Hamming）距 离，表示为dmin • 例：010和011的码重分别为1和2，码距为1。 • 练习：许用码组集合{111,001,010,100}中 • dmin =？ ，各个许用码组的码重分别为？ 2 3,1,1,1
五、恒比码
• 在恒比码中，每个码组中含“1”和含“0”数目的 比例是恒定的。由于恒比码备码组中的“1”（或 “0”）的个数是相同，因而也称等重码。 • 检测时，只要计算每个码组中“1”的数目是否对， 1” 就能判断有无错误。
五、恒比码
• 恒比码除了能检测出单个和奇数个错误， 还能部分检测出偶数个错误，但不能全部 检测出偶数个错误（如成对交换错误）。 • 恒比码的主要优点是简单，适于用来传输 电传机或其他键盘设备产生的字母和符号 • 但对于信源来的二进随机数字序列，恒比 码就不宜使用了。
真题练习
• 偶校验编码的码组中__的个数为偶数。 • 差错控制的基本原理是什么？ • 一般来说，引入监督码元越多，码的检错 纠错能力__。 • 常用的差错控制方法主要有哪些？ • 当最小码距dmin=4时，若只用于检错，则能 检出__位错码。 • 监督码不载荷信息，它的作用是用来监督 __在传输中有无差错。
• 某系统采用了选择重发的差错控制方式， 发送端要向接收端发送6个码组（序号0～ 5），其中2号码组出错，请在下图中示意 NAK信号。
• 系统码和非系统码 ，纠正随机错误的码和纠正突发错误 的码 ，二进制码与多进制码。
第三节 几种常用的简单差错控制码
• • • • • 奇偶监督码 水平奇偶监督码 水平垂直奇偶监督码 群计数码 恒比码
一、奇偶监督码
• 最简单的检错码，又称奇偶校验码，在计算机数 据传输中得到广泛应用。 • 先将所要传输的数据码元分组，在每组数据后面 附加一位监督位，使得该组码连同监督位在内的 码组中的“1”的个数为偶数（称为偶校验）或奇 数（称为奇检验），在接收端按同样的规律检查， 如发现不符就说明产生了差错，但是不能确定差 错的具体位置，即不能纠错。 • 例：1110011000偶校验的监督码为1 • 练习：1101001101偶校验的监督码为？ 0
二、码距与检错和纠错能力
• 检错纠错能力与最小码距的数量关系
– 在一个码组内能检测e个错码，则要求最小码 距dmin≥e+1，或者说，若一种编码的最小距离 为dmin ，则它能检出≤dmin-1个错码。 – 一个码组内能纠正t个错码，则要求最小码距为 dmin≥2t+1 ，或者说，若一种编码的最小码距为 dmin ，则它能纠正≤(dmin -1)/2个错码。 – 在一个码组内能纠正t个错码，同时能检测 e(e>t)个错码，则要求最小码距为dmin≥e+t+1
（四）信息反馈
• 信息反馈方式(简称IRQ)又称回程校验
– 收端把收到的数据序列全部由反向信道送回发端，发端比较 发送的数据序列与送回的数据序列，从而发现是否有错误， 并把认为错误的数据序列的原数据再次传送，直到发端没有 发现错误为止。 – 优点：不需要纠错、检错的编译器，设备简单。 – 缺点：需要和前向信道相同的反向信道，实时性差。另外， 发送端需要一定容量的存储器以存储发送码组，环路时延越 大，数据速率越高，所需存储容量越大。 – IRQ方式仅适用于传输速率较低，数据信道差错率较低，且 具有双向传输线路及控制简单的系统中。
• 下图表示采用停发等候重发差错控制方式 的系统的工作思路，已知2号码组出错，请 在错误处打×(图中的数字代表码组序号)。
• 采用水平奇校验所得监督码元如表所列， 请在表中下划线处填写缺省的信息码元。
• 若要纠正一个错码，则分组码的最小码距 dmin为： 。 • 常用的简单差错控制码有奇偶监督码、水 平奇偶监督码、水平垂直奇偶监督码、群 计数码和 码。 • 简述前向纠错方式的基本思路。 • 码的检错和纠错能力是用信息量的_ 来换 取的。
• 简述奇偶监督码的编码规则。 • 差错编码的纠错和检错能力是利用信息量 的__来换取的。 • 如图所示的返回重发过程中，试填出空格 处的数据包序号。
• 码距是两个码组中对应码位上具有不同二 进制码元的 。 • 要能纠正t个错码，同时能检测e个错码 （e>t），分组码的最小码距应 。 • 常用的简单差错控制码有哪些？ • 码重是码组中__的个数。 • 检错重发(ARQ)常用的三种实现形式是什么?
二、水平奇偶监督码
• 为了提高上述奇偶监督码的检错能力，特别是不能检测突 发错误的缺点，可以将经过奇偶监督编码的码元序列按行 排成方阵，每行为一组奇偶监督码，但发送时则按列的顺 序传输，接收端仍将码元排成发送时的方阵形式，然后按 行进行奇偶校验。 • 由于按行进行奇偶校验，因此称为水平奇偶监督码。 • 由于发端是按列发送码元而不是按码组发送码元，因此把 本来可能集中在某一个码组的突发错误分散在方阵的各个 码组，因而可得到整个方阵的行监督。 • 可以发现某一行上所有奇数个错误以及所有长度不大于方 阵中行数的突发错误。
第二节 检错和纠错的基本概念
• 香农的信道编码定理：
– 对于一个给定的有干扰信道，如信道容量为C， 只要发送端以低于C的速率R （R为编码器输入 的二进制码元速率），则一定存在一种编码方 法，使编码错误概率P随着码长n的增加，按指 数下降到任意小的值。 – 即可以通过编码是通信过程实际不发生错误， 或者使错误控制在允许的数值之下。
四、群计数码
• 监督码组中“1”的个数构成所谓群计数码。例如 一码组的信息码元为1010111，其中有5个“1”， 用二进制数字表示为“101”，将它作为监督码元 附加在信息码元之后，即传输码组为1010111101 • 群计数码有较强的检错能力，除了同时发生码组 中“1”变“0”和“0”变“1”的成对错误外，它能检 测出所有形式的错误。 • 为了提高检测突发错误的能力，也可仿照水平奇 偶监督方法，将信息码排成方阵，然后利用群计 数法来进行水平监督。
一、奇偶监督码
• 这种奇偶校验只能发现单个或奇数个错误，而不 能检测出偶数个错误，因而它的检错能力不高 • 绝大多数随机错误都能用简单奇偶校验查出，这 正是这种方法被广泛用于以随机错误为主的计算 机通信系统的原因 • 但这种方法难于对付突发差错，所以在突发错误 很多的信道中不能单独使用 • 奇偶校验码的最小码距为dmin=2
一、差错分类和错误图样
• 噪声大体分为两类：
– 随机噪声
随机差错 • 热噪声 • 散弹噪声 • 传输媒介引起的噪声等 突发差错 – 脉冲噪声 • 突然发生的噪声 • 如雷电、开关引起的瞬态电信号变化等
一、差错分类和错误图样
• 随机差错
– – – – 独立差错 独立地、稀疏地和互不相关地发生的差错 存在这种差错的信道称为无记忆信道或随机信道 如微波接力和卫星转发等信道