电脑基础知识41-抗干扰编码的基本概念

第四章抗干扰二元编码§4.2检错码§4.1抗干扰编码的基本概念§4.3用于单向信道的简单纠错码§4.4纠一位错误的汉明码§4.6纠独立错误的卷积码§4.5循环码§4.7纠突发错误的编码§4.1抗干扰编码的基本概念一、引言二、几个名词三、最小码距与纠错能力的关系

四、抗干扰编码的基本原理五、抗干扰编码的分类一、引言信号通过信道进行传递时，由于噪声的干扰，使得收到的信号受到破坏，称为信道编码。值得注意的是，抗干扰编码不仅仅用于通信，其应用的广泛程度是当初抗干扰编码的创始者们万万没有想到的。身份证的校验改造(即抗干扰编码)，使信号具有抗干扰性。

条形码的校验

DVD

纠错计算机中的奇偶校验货币中的防伪编码……………因此，常常需要对待传递的信号进行编码抗干扰编码又一、引言1.基本思想有效性编码是尽可能降低信号内部的关联性，而抗干扰编码则是通过某种运算方式使得信号(码字)的内部结构具有破坏，就可以发现错误，甚至纠正错误。更强的规律性或者关联性。抗干扰编码的输出码字一般都采用等长码。一旦这种规律性或者关联性遭到一、引言2.编码对象(1)直接针对消息或者字符；(2)针对(已经过有效性编码后的)二元序列。本章中除了定比码是直接针对消息或者字符之外，其余的工作都是围绕二元序列进行的。3.引例方案一2

位不相同若收到0

1或1

0，则能够发现错误；(检错)但不能纠正错误。(纠错)则上述编码方案得到一个相当好的检错码。事实上，如果假定每两位同时出错的概率非常小，注考虑某二元序列：编码后的序列：一、引言方案二若出现一位错，则能够发现错误；(检错)但不能纠正错误。(纠错)由于每两位只增加一位，因此与方案一相比具有优势。

注编码后的序列：2222222位不相同3.引例一、引言考虑某二元序列：方案三3

位不相同若收到0

0

1，则能够发现错误；(检错)还“可以”纠正为0

0

0。(纠错)事实上，由于错一位的概率远远小于错两位的概率，

注因此通常采用

最小距离准则

进行

自动纠错。编码后的序列：3.引例一、引言考虑某二元序列：方案四若出现一位错，则能够发现错误；(检错)且能够纠正错误。(纠错)43333位不相同4编码后的序列为：由于每两位只增加三位，因此与方案三相比具有优势。

注3.引例一、引言考虑某二元序列：小结(1)码字之间相差一个码元

(2)码字之间相差两个码元

(3)码字之间相差三个码元

或者纠正一位错误。(4)码字之间相差四个码元

一、引言不能发现错误。

——可以发现一位错误。

——可以发现两位错误；

——

——?1.许用码字与禁用码字二、几个名词许用码字抗干扰编码后实际使用的码字(或码组)。例如某抗干扰编码为：

全体许用码字构成码字集合。禁用码字抗干扰编码后不使用的码字(或码组)。若收到的码字为禁用码字，则发现有错。许用码字

禁用码字

2.码距与最小码距二、几个名词码距两个码字之间对应位置的不同码元的个数。码距有时也称为汉明(Hamming)码距。具体设有两个码字分别为：其中则(汉明)码距为模

2

加：如果引入模

2

加，则有2.码距与最小码距二、几个名词最小码距码字集合中各个码字之间码距的最小值。码重码字中码元为

“1”

的个数；码重又称为汉明码重。

例如码字的码重为

3。例如最小码距为

2最小码距为

32222222编码方案(一)343334编码方案(二)三、最小码距与纠错能力的关系

则

最小码距必须满足条件：(1)若要发现e位错误，

结论(2)若要纠正t位错误，则必须满足条件：(3)若要纠正t位错误，且“发现”e位错误，其中则必须满足条件：(如何理解?)①检错三、最小码距与纠错能力的关系

(1)对于编码方案:

例如最小码距为3。能够发现2位错。②

纠错

能够纠正1位错。(纯粹进行检错)(采用最小距离准则自动纠错)

问题：如果出现2位错，会怎么样？结果：不能发现，而是自动纠“错”了，比如发送的是收到的是即将自动地纠“错”为纠正

1

位错误。

当最小码距为

3

时，其纠错能力为：①检错三、最小码距与纠错能力的关系

最小码距为4。②

纠错

能够发现3位错。(纯粹进行检错)能够纠正1位错。(采用最小距离准则自动纠错)

问题：(1)如果出现2位错，会怎么样？结果：(1)无法自动纠错，只能报告出来;(2)对于编码方案:

例如(2)如果出现3位错，又会怎么样？(2)不能发现，而是自动纠

“错”

了。当最小码距为4时，其纠错能力为：纠正1

位错误，且“报告”2

位错误。三、最小码距与纠错能力的关系

最小码距为

5。①检错能够发现4位错。(纯粹进行检错)②

纠错

能够纠正2位错。(采用最小距离准则自动纠错)

(3)对于编码方案:

例如则不能发现，而是自动纠

“错”

了。如果出现3位错或者4位错，

纠正

2

位错误。

当最小码距为

5

时，其纠错能力为：问:如果最小码距为

5，但只纠1

位错，结果会如何？可以只纠正1

位错误，且“报告”3

位错误。答:三、最小码距与纠错能力的关系

纠正3位错且“报告”4位错纠正2位错且“报告”3位错纠正1位错且“报告”2位错

纠正3位错

纠正2位错

纠正1位错无无纠错能力发现7位错发现6位错发现5位错发现4位错发现3位错发现2位错发现1位错无检错能力87654321最小码距

关系表(部分)：通常会选择最小码距为奇数的编码方案。注1.基本方法四、抗干扰编码的基本原理(1)针对有效性编码后的二元序列每

k

个码元作为一组，对应到长度为

n(

>

k

)的一个码字。

通常的方法是在原始码组的基础上进行

“扩充”，原始二元序列…

…编码后的序列…

…某种规律，添加一些新的码元来构成相应的码字。这些新的码元称为

监督位；而原始码元称为

信息位。

抗干扰编码效率：抗即按照1.基本方法四、抗干扰编码的基本原理(2)针对消息(或者符号)

直接将原始信源中的每一个消息(或者符号)对应到一个

抗干扰编码效率：

抗(关于抗干扰编码效率的说明)长度为n

的等长的二元码字。

为了能够抗干扰，其码长肯定比所需的码长要长一些。其中，为原始信源的最大熵。2.代数编码四、抗干扰编码的基本原理例如设某编码方案为

代数编码

是指码字中的码元之间满足一定的代数关系。将码字记为生成阵监督阵信息码组监督位信息位(1)(生成)(2)(监督)则有2.代数编码四、抗干扰编码的基本原理

代数编码

是指码字中的码元之间满足一定的代数关系。除了代数编码之外，还有几何编码、算术编码以及组合(1)分组代数码，简称为

分组码

或者

块码；(2)卷积代数码，简称为

卷积码

或者

连环码。编码等等。

按照码组之间的关系，代数编码又可分为两类：

目前所使用的编码大部分都属于代数编码。2.代数编码四、抗干扰编码的基本原理(1)分组码信息序列…

…编码序列…

…方法将信息序列按k位一组分割后，

进行代数编码，从而对应到长度为n(

>

k)的一个码字；此时，分组码又称为

(

)码。n

,k每一个信息码组独立地2.代数编码四、抗干扰编码的基本原理(1)分组码特点分组码中的各个码组之间没有关联；当前输入的信息码组有关。显然，一个()分组码的许用码字共有个；

n

,k系统码如果在一个()分组码的码字中，信息码元安排在n

,k前k

位，监督码元安排在后位，组码为系统码(或

组织码)；否则称为非系统码。而禁用码字则有

个。即输出的码组仅与则称这种分

2.代数编码四、抗干扰编码的基本原理(2)卷积码方法将信息序列按位一组分割后，

前面个

信息码组

一起进行代数运算，

与当前信息

码

组

对应的一

个长

度

为

的码字；此时，卷积码又称为码。信息序列………编码序列……m

组每一个信息码组和它从而得到2.代数编码四、抗干扰编码的基本原理特点卷积码中的各个码组之间是相互关联的；不仅与当前输入的信息码组有关系，而且与前面输入的显然，对于同样的一个信息码组，由于其前面输入的信息码组不一样，因而所对应的码字也会不一样。(2)卷积码若干个信息码组有关系。因此，一个卷积码的许用码字的个数可能高达个。即输出的码组2.代数编码四、抗干扰编码的基本原理约束长度显然，当时，卷积码就是分组码。(2)卷积码对于一个卷积码，(1)称m

为编码器的约束长度或者编码约束长度，它反映了卷积码中相互制约的码组个数；它反映了卷积码中相互制约的码元个数。(2)称

为

卷

积

码的约束长

度，五、抗干扰编码的分类1.根据用途的不同进行分类

检错码单纯地用于检测错误。

采用检错码的通讯系统要有反馈信道，到的消息有错误时，通过反馈信道要求重发。适用于“一站发一站收”的情况。纠错码自动纠正差错。根据某种纠错原则直接纠错，不需要反馈信道。适用于“一站发多站收(即群发)”的情况。当发现收五、抗干扰编码的分类2.根据干扰性质的不同进行分类