TXYL通信原理(第11章)差错控制编码

TXYL通信原理(第11章)差错控制编码

通信原理第11章差错控制编码

TXYL通信原理(第11章)差错控制编码

第11章差错控制编码

11.1 概述

信道分类：从差错控制角度看随机信道：错码的出现是随机的 突发信道：错码是成串集中出现的 混合信道：既存在随机错码又存在突发错码

差错控制技术的种类检错重发 前向纠错 反馈校验 检错删除

TXYL通信原理(第11章)差错控制编码

第11章差错控制编码

差错控制编码：常称为纠错编码监督码元：上述4种技术中除第3种外，都是在接收 端识别有无错码。所以在发送端需要在信息码元序 列中增加一些差错控制码元，它们称为监督码元。 不同的编码方法，有不同的检错或纠错能力。 多余度：就是指增加的监督码元多少。例如，若编 码序列中平均每两个信息码元就添加一个监督码元， 则这种编码的多余度为1/3。 编码效率(简称码率) :设编码序列中信息码元数量 为k,总码元数量为n,则比值k/n 就是码率。 冗余度：监督码元数(n-k) 和信息码元数 k 之比。 理论上，差错控制以降低信息传输速率为代价换取 提高传输可靠性。

TXYL通信原理(第11章)差错控制编码

第11章差错控制编码

自动要求重发(ARQ)系统

3种ARQ系统

发送码组

停止等待ARQ系统3ACK

11

2 2

3NAK

4ACK

5ACK

5NAK

6ACK

ACK 接收码组

t

3有错码组

3

4

5有错码组

5 t

数据按分组发送。每发送一组数据后发送端等待接 收端的确认(ACK)答复，然后再发送下一组数据。 图中的第3组接收数据有误，接收端发回一个否认 (NAK)答复。这时，发送端将重发第3组数据。 系统是工作在半双工状态，时间没有得到充分利用， 传输效率较低。4

TXYL通信原理(第11章)差错控制编码

第11章差错控制编码

拉后ARQ系统3 4 5 6 7

重发码组

重发码组

发送数据

1

2

5

6

7

8

9 10 11 9 10 11 12NAK9

ACK1

NAK5

ACK5

接收数据

1

2

3

4

5

6

7

5

6

7

8

9 10 11 9 10 11 12

有错码组

有错码组

发送端连续发送数据组，接收端对于每个接收到的数 据组都发回确认(ACK)或否认(NAK)答复。例如，图中第5组接收数据有误，则在发送端收到第5 组接收的否认答复后，从第5组开始重发数据组。 在这种系统中需要对发送的数据组和答复进行编号， 以便识别。显然，这种系统需要双工信道5

TXYL通信原理(第11章)差错控制编码

第11章差错控制编码

选择重发ARQ系统重发码组 重发码组

发送数据

1

2

3

4

5

6

7

5

8

9 10 11ACK5

9 12 13 14ACK9

ACK1 接收数据

NAK5

NAK9

1

2

3

4

5

6

7

5

8

9 10 11有错码组

9 12 13

14

有错码组

它只重发出错的数据组，因此进一步提高了传输效率。

TXYL通信原理(第11章)差错控制编码

第11章差错控制编码

ARQ的主要优点：和前向纠错方法相比

监督码元较少即能使误码率降到很低，即码率较高； 检错的计算复

杂度较低； 检错用的编码方法和加性干扰的统计特性基本无关， 能适应不同特性的信道。

ARQ的主要缺点：

需要双向信道来重发，不能用于单向信道，也不能用 于一点到多点的通信系统。 因为重发而使ARQ系统的传输效率降低。 在信道干扰严重时，可能发生因不断反复重发而造成 事实上的通信中断。 在要求实时通信的场合，例如电话通信，往往不允许 使用ARQ法。7

TXYL通信原理(第11章)差错控制编码

第11章差错控制编码

ARQ系统的原理方框图

在发送端，输入的信息码元在编码器中被分组编码(加入 监督码元)后，除了立即发送外，还暂存于缓冲存储器中。 若接收端解码器检出错码，则由解码器控制产生一个重发 指令。此指令经过反向信道送到发送端。由发送端重发控 制器控制缓冲存储器重发一次。 接收端仅当解码器认为接收信息码元正确时，才将信息码 元送给收信者，否则在输出缓冲存储器中删除接收码元。 当解码器未发现错码时，经过反向信道发出不需重发指令。 发送端收到此指令后，即继续发送后一码组，发送端的缓 8 冲存储器中的内容也随之更新。

TXYL通信原理(第11章)差错控制编码

第11章差错控制编码

11.2 纠错编码的基本原理

分组码基本原理：举例说明如下。

设有一种由3位二进制数字构成的码组，它共有8种不同 的可能组合。若将其全部用来表示天气，则可以表示8种 不同天气，例如：“000”(晴),“001”(云), “010”(阴),“011”(雨), “100”(雪),“101”(霜),

“110”(雾),“111”(雹)。

其中任一码组在传输中若发生一个或多个错码，则将变 成另一个信息码组。这时，接收端将无法发现错误。9

TXYL通信原理(第11章)差错控制编码

第11章差错控制编码

若在上述8种码组中只准许使用4种来传送天气，例如： “000”=晴 =雨

“011”=云 “101”=阴

“110”

这时，虽然只能传送4种不同的天气，但是接收端却 有可能发现码组中的一个错码。 例如，若“000”(晴)中错了一位，则接收码组将变 成“100”或“010”或“001”。这3种码组都是不准使 用的，称为禁用码组。 接收端在收到禁用码组时，就认为发现了错码。当发 生3个错码时，“000”变成了“111”,它也是禁用码 组，故这种编码也能检测3个错码。 但是这种码不能发现一个码组中的两个错码，因为发 10 生两个错码后产生的是许用码组。

TXYL通信原理(第11章)差错控制编码

第11章差错控制编码

检错和纠错

上面这种编码只能检测错码，不能纠正错码。例如，当接 收码组为禁用码组“100”时，接收端将无法判断是哪一位 码发生了错误，因为晴、阴、雨三者错了一位都可以变成 “100”。 要

能够纠正错误，还要增加多余度。例如，若规定许用码 组只有两个：“000”(晴),“111”(雨),其他都是禁 用码组，则能够检测两个以下错码，或能够纠正一个错码。 例如，当收到禁用码组“100”时，若当作仅有一个错码， 则可以判断此错码发生在“1”位，从而纠正为“000” (晴)。因为“111”(雨)发生任何一位错码时都不会变 成“100”这种形式。 但是，这时若假定错码数不超过两个，则存在两种可能性： “000”错一位和“111”错两位都可能变成“100”,因而只 能检测出存在错码而无法纠正错码。 11

TXYL通信原理(第11章)差错控制编码

第11章差错控制编码

分组码的结构

将信息码分组，为每组信息码附加若干监督码的编码称 为分组码 。 在分组码中，监督码元仅监督本码组中的信息码元。 信息位和监督位的关系：举例如下

信息位

监督位

晴云 阴

0001 10

01 1

雨

11

012

TXYL通信原理(第11章)差错控制编码

第11章差错控制编码

分组码的一般结构

分组码的符号：(n, k) N - 码组的总位数，又称为码组的长度(码长), k - 码组中信息码元的数目， n – k = r - 码组中的监督码元数目，或称监督位数目。

TXYL通信原理(第11章)差错控制编码

第11章差错控制编码

分组码的码重和码距

码重：把码组中“1”的个数目称为码组的重量，简称码重。 码距：把两个码组中对应位上数字不同的位数称为码组的 距离，简称码距。码距又称汉明距离。 例如，“000”=晴，“011”=云，“101”=阴，“110”= 雨，4个码组之间，任意两个的距离均为2。 最小码距：把某种编码中各个码组之间距离的最小值称为 最小码距(d0)。例如，上面的编码的最小码距d0 = 2。

TXYL通信原理(第11章)差错控制编码

第11章差错控制编码

码距的几何意义(0,1,1)

a1

(0,1,0)

(1,1,0) (1,1,1)

(0,0,0)

(1,0,0) (1,0,1)

a2

a0

(0,0,1)

对于3位的编码组，可以在3维空间中说明码距的几何意义。 每个码组的3个码元的值(a1, a2, a3)就是此立方体各顶点的坐 标。而上述码距概念在此图中就对应于各顶点之间沿立方体 各边行走的几何距离。15

由此图可以直观看出，上例中4个准用码组之间的距离均为2。

TXYL通信原理(第11章)差错控制编码

第11章差错控制编码

码距和检纠错能力的关系

一种编码的最小码距d0的大小直接关系着这种编码的检错 和纠错能力 为检测e个错码，要求最小码距 d0 e + 1 【证】设一个码组A位于O点。若码组A中发生一个错码， 则我们可以认为A的位置将移动至以O点为圆心，以1为半 径的圆上某点，但其位置不会超出此圆。 若码组A中发生两位错码，则其位置不会超出以O点为圆 心，以2为半径的圆。因此，只要最小码距不小于3,码组 A发生两位以下错码时， 不可

能变成另一个准用 0 1 2 3 码组，因而能检测错码 A B 汉明距离 的位数等于2。 ed016

TXYL通信原理(第11章)差错控制编码

第11章差错控制编码同理，若一种编码的最小码距为d0,则将能检测(d0 - 1)个错 码。反之，若要求检测e个错码，则最小码距d0至少应不小于 ( e + 1)。

为了纠正t个错码，要求最小码距d0 2t + 1

【证】图中画出码组A和B的距离为5。码组A或B若发生不多于 两位错码，则其位置均不会超出半径为2以原位置为圆心的 圆。这两个圆是不重叠的。判决规则为：若接收码组落于以 A为圆心的圆上就判决收到的是码组A,若落于以B为圆心的 圆上就判决为码组B。

这样，就能够纠正两位错码。

0 A

1

2

3 4

B

5 汉明距离

td0

t17

TXYL通信原理(第11章)差错控制编码

第11章差错控制编码

若这种编码中除码组A和B外，还有许多种不同码组，但任两 码组之间的码距均不小于5,则以各码组的位置为中心以2为 半径画出之圆都不会互相重叠。这样，每种码组如果发生不 超过两位错码都将能被纠正。因此，当最小码距d0=5时，能 够纠正2个错码，且最多能纠正2个。若错码达到3个，就将 落入另一圆上，从而发生错判。故一般说来，为纠正t个错码， 最小码距应不小于(2t + 1)。

TXYL通信原理(第11章)差错控制编码

第11章差错控制编码

为纠正t个错码，同时检测e个错码，要求最小码距

d0 e t 1

(e t )

在解释此式之前，先来分析下图所示的例子。图中码组A和B 之间距离为5。按照检错能力公式，最多能检测4个错码，即 e = d0 – 1 = 5 – 1 = 4,按照纠错能力公式纠错时，能纠正2个 错码。但是，不能同时作到两者，因为当错码位数超过纠错 能力时，该码组立即进入另一码组的圆内而被错误地“纠正” 了。例如，码组A若错了3位，就会被误认为码组B错了2位造 成的结果，从而被 错“纠”为B。这就 是说，检错和纠错 公式不能同时成立0 A 1 2 3 4 B 5 汉明距离

td0

t19

或同时运用。

本文来源：https://www.bwwdw.com/article/1rpi.html