第八章差错控制编码要点

可以检测出某行或某列上偶数个错误 不能纠正差错数正好是4的倍数且位置在行列
矩阵/子矩阵的4个顶点上的差错
失效！！！
信息码元 11 1 0 0 1 11 0 1 0 0 10 0 0 0 1 00 0 1 0 0 11 0 0 1 1 01 1 0 1 1
监督码元（偶）
0
0
1
0
1
1
0
1
1
1
1
1
恒比码(定比码)
式中⊕表示模2加 n表示码组长度
aki和aji表示第k个码组和第j个码组的第i位码元 min表示最小值
最小距离实例
❖ 举例：
❖ 码 组 集 合 { （ 000 ） （ 001 ） （ 010 ） （ 011 ） （ 100 ） （ 101 ） （ 110 ） （111）} d0=1 没有检错能力。
差错控制实例
❖ 总结：（信息码+监督码=码组）构成的 信息序列通过降低信息传输效率来提高 传输的可靠性。
6. 编码效率
❖ 编码效率：指信息码在码组中所占的比重。 ❖ 假定n=k（信息码长）+r（监督码长），用R
表示编码效率 η=k/n=k/（k+r） ❖ 当n ↑ ❖ η↓ ❖ Pe ↓ 可靠性↑
❖ 几何表示：用3位码元构成的8个码组表示立 方体中各个顶点；
海明距离（码距）：就是从一个顶点移动到另一个顶点所经 历立方体的最少边数；
2.最小距离
❖ 2.最小距离：一个码组集合中，任何两个码组 间海明距离(即码距)的最小值称为码组集合的最 小距离。用d0或dmin表示:
n
d0/dminmin{(ajiak)i}表示 i1
差错控制的基本概念
❖ 所谓差错即为误码；差错控制的核心是抗 干扰编码，简称差错编码。
❖ 基本思想：是通过对信息序列作某种变换， 使原来彼此独立、互不相关的信息码元产 生某种规律性（相关性），从而在接收端 根据这种规律性来检查，进而纠正传输信 号序列中的差错。
❖ 变换的方法不同就构成了不同的编码，即 信道编码
信号在交到用户之前应当去掉监督码元。
❖插入监督码元的目的是使原来彼此独 立、互不相关的信息码元产生某种规 律性（相关性）从而使接收端能够根 据这种规律性来检测传输过程是否有 误。
7
2.差错控制的基本特点
❖ ①引入差错编码控制后，实际传输的 信息序列W=（hy信? 息码元+监督码元），称为码 组。
（an-1,an-2……,a1,c0）其中前n-1位为信息 位，第n位c0为监督位
① 奇 校 验 ： an-1⊕an-2⊕……⊕a1⊕c0=1 即 c0= an-1⊕an-2⊕……⊕a1⊕1
② 偶 校 验 ： an-1⊕an-2⊕……⊕a1⊕c0=0 即 c0= an-1⊕an-2⊕……⊕a1
实例
第八章-差错控制编码要点
❖ 必要性：
数据通信要求信息传输过程具有高度的可靠性 即误码率足够低；
然而信号在传输过程中由于传输损耗（噪声， 衰损，失真）不可避免要产生一些差错即出现 误码。
大体上分为：
❖随机差错：由信道的加性随机噪声引起的差 错
❖突发差错：某一段时间内出现一连串的差错 ❖混合差错：既有随机差错又有突发差错
数字
1 2 3 4 5
编码
01011 11001 10110 11010 00111
数字
6 7 8 9 0
编码
10101 11100 01110 10011 01101
正反码
❖ 多用于10单位电码的前向自动纠错设备中， 能纠正一位差错，发现大部分两位错。
n=k+r 且 k=r=5
❖ 1.编码规则：
Pe满足：
Pe<=A
e-n
E(R ) b
式中
香农信道编码定理
n—码字长度（码长） E（Rb）—误差指数（当Rb<=C时E（Rb ）
>0） A—正系数 Pe＝Ne／N误码率是指二进制码元在数据
传输系统中被传错的概率 ；N为传输的二 进制码元总数， Ne为被传错的码元数。
E（Rb）与Rb的关系如图所示：
方阵校验码
❖ 又称行列监督码，矩阵码，纵向冗余校验码 （LRC，Lognitudinal Redundancy Check），它的码元受到行和列两个方向奇 偶监督，又称二维奇偶校验码。
❖ 编码规则：使的每个码元受到纵向（列）和 横向两次监督；将欲发送的信息码按行排成 一个矩阵，每行的最后加上一个奇偶监督码 元；在每列最后也加上一个监督码元，进行 奇偶校验；最后按行或列码组的顺序发送。
1
督 码
11 0 0 1 1 1
1
元 01 1 0 1 1 1
1
发送端在发送时则按列(或行）的顺序传输：111010 110011 100001 010100 ……001111
接收端仍将码元恢复成发送时方阵形式，然后按行、 列进行奇偶校验
方阵校验码
❖ 特点：
可以检测出某行某列上的奇数个错误和长度不 大于行（列）数的突发错误。
❖ 写出下列二进制序列的偶校验码： ①1001110 10011100 ②0101111 01011111
写出下列二进制序列的奇校验码： ①1100101 11001011 ②0110010 01100100
奇偶校验编码
❖ 特点：
无论信息位为多少位，监督位只有一位。 只能检测信息码组中奇数个错误，对偶数个错
如果2种码组作为许用码组(000 111)， 任两个码距间的最小距离为3，记dmin =3;
所以码组集合中最小距离越大，其抗干扰 能力（包括检错和纠错能力）越强。
4.最小距离与抗干扰能力的关系
❖ 定理3.1若一种码的最小距离为d0 ，则它能检查传 输错误个数（检错能力）e应满足：d0>=e+1
❖ 码 组 集 合 { （ 000 ） （ 011 ） （ 101 ） （110）} d0=2 能检测出1位码位出错。
❖ 码组集合{（000）（111）} d0=3 能 检测出2位出错并能纠正1位错误。
如果8种码组都作为许用码组，任两个 码距间的最小距离为1，记dmin =1;
如果4种码组(000 011 101 110)作为 许用码组，任两个码距间的最小距离为 2，记dmin =2;
方阵校验码结构
XX X X X X X X XX X X X X X X X X X X X XX X X X X X X X X X X X X X X X X X
实例
信息码元
行监督码元（偶）
11 1 0 0 1 0
0
11 0 1 0 0 1
0
10 0 0 0 1 1
1
列 监
00 0 1 0 0 0
4.差错控制编码的基本原理
❖ 从而差错控制编码的基本原理就是：在保 持信息位数不变（信息码元）情况下，采 用增加码长的方法来降低误码率。
5.差错控制实例
❖ 信源发出的任何消息通过信源编码表达成二进制信 号“0”和“1”的形式。
Source
Channel
Destination
❖ Source→Destination传输A和B两个消息。
三 常用差错控制编码方法
❖ 1 奇偶校验编码 ❖ 2 方阵校验码 ❖ 3 恒比码 ❖ 4 正反码 ❖ 5 循环冗余校验编码（CRC） ❖ 6 卷积码
❖ 差错控制的核心就是抗干扰编码，为了 提高通信系统的检错和纠错能力，人们创造 出许多差错控制编码，比较常用的有奇偶校 验编码、循环冗余校验编码、卷积码等。
差错控制的基本概念
❖ 通俗地讲，差错控制方法：对要传送的二 进制数字信息中增加一些附加的信息，通 过增加冗余度使得原来的信息可以检错或 纠错。
❖ 一般来讲，加入的冗余度越多，检错纠错 能力（即差错控制能力）越强，传输效率 越低。
1.信息码和监督码
❖ 信息码（元）：发送用户端欲发送的信 息序列。
❖ 监督码（元）:为了使信息码元产生某种 规律性，可按照某种规则在用户信息序 列中插入一定数量的新码元，这种新码 元叫监督码（元）。
奇偶校验编码
❖ 编码规则：
发送端，将所要传输的数据码元分组，在分 组数据后面加一位监督码（校验位），使得 该组码连同监督码在内的码组中“1”的个数 为奇数（奇校验）或偶数（偶校验）。
接收端，按照编码规则检查如果发现不符， 就说明产生差错，但不能明确差错的具体位 置即不能纠错。
奇偶校验编码
❖公式表示：设码组长度为n，表示为
矛盾！ tradeof
f!
二 差错控制编码的特性和能力
1.海明（hamming）距离 2.最小距离 3.海明距离（码距） 4.最小距离与抗干扰能力的关系
1.海明（hamming）距离
❖ 1.海明（hamming）距离：指两个不同的码
组其对应码位（二进制位）的码元不同的个
数，简称码距 ；用d表示：
(1)当信息码中“1”的个数为奇数时，监督码与 信息码相同（正码）10101 10101
(2)当信息码中“1”的个数为偶数时，监督码与 信息码相反（反码）10100 01011
正反码
❖ 2.解码方法：
(1)将接收到信息码与监督码按相应的 码位模2加（异或），得到一个新的5 位码组。
力。
实例（P58）
解：最小距离
实例
❖ 检错和纠错能力 第一组：d0=2，e<=d0 –1=1，可检测出一个错，
（定理1） 第二组： d0 =3
e<=d0 –1=2 ，可检测出二个错，（定理1） t<=(d0-1)/2=1，可纠正一个错，（定理2） e+t<=d0-1=2 ，令（t<=e） e=1，t=1， 纠错、检错各1，（定理3）
❖ ②在信道容量既定的情况下，信息传输效率 有所降低，但信息传输的可靠性有所提高， 既差错控制编码用降低传输效率的代价来提 高传输的可靠性。