9.3 差错控制编码基础

差错控制编码基础§9.3赵小燕1、差错控制编码的分类按码的功能分为检错码：能自动发现错误纠错码：能自动纠正错误按码结构中对信息序列的处理方式不同分为：分组码：校验位只由每组k个信息位按一定规律产生，而与其他组的信息无关卷积码：校验位不仅与本组k个信息位有关，还与其前面L组的信息位有关1、差错控制编码的分类按码元与信息位的关系分为线性码：所有码元均是原始信息元的线性组合，编码器不带反馈回路非线性码：码元不都是信息元的线性组合，可能还与前面已编的码元有关，编码器可能带反馈回路按码适用的差错类型纠随机差错码：用于随机差错信道，其纠错能力用码组或码段内允许的独立差错的个数来衡量纠突发差错码：用于突发差错信道，其纠错能力由可纠突发差错的最大长度来衡量介于中间的纠随机/突发差错码矢量空间与码空间F表示码元所在的数域，对于二进制码，F代表二元域{0,1}设n重有序元素的集合V={Vi

},若满足条件：V中矢量元素在矢量加运算下构成加群；V中矢量元素与数域F元素的标乘封闭在V中；分配律、结合律成立则称集合V是数域F上的n维矢量空间，或称n维线性空间。2、差错控制编码的基本原理

对于域F上的若干矢量线性组合：

线性相关：

其中任一矢量可表示为其它矢量的线性组合线性无关或线性独立：一组矢量中的任意一个都不可能用其它矢量的线性组合来代替。矢量空间中矢量的关系:线性组合、线性相关、线性无关矢量空间与码空间2、差错控制编码的基本原理一组线性无关的矢量，线性组合的集合就构成了一个矢量空间V，这组矢量就是这个矢量空间的基底。n维矢量空间应包含n个基底基底不是唯一的，例：线性无关的两个矢量（1,0）和（0,1）以及（-1,0）和（0,-1）可张成同一个两维空间。理解要点：维数：基底矢量个数重数：矢量内元素数一个n维的矢量空间由n个n重的基底张出，基底不唯一。自然基底：矢量元素中只含有一个“1”，其余矢量元素为“0”矢量空间与码空间2、差错控制编码的基本原理

输入序列长：k

(n,k)

输出码字长：n

序列共有

qk

种分组编码器码字共有qn种

k维k重矢量

n维n重矢量

通常qn>>qk，分组编码的任务是要在n维n重矢量空间的qn种可能组合中选择其中的qk个构成一个码空间，其元素就是许用码的码集。分组编码的任务：1.选择一个ｋ维n重子空间作为码空间2.确定由k维k重信息空间到ｋ维n重码空间的映射方法。（码空间的不同选择方法，以及信息组与码组的不同映射算法，就构成了不同的分组码。）矢量空间与码空间2、差错控制编码的基本原理

输入序列长：k

(n,k)

输出码字长：n

序列共有

qk

种分组编码器码字共有qn种

k维k重矢量

n维n重矢量矢量空间与码空间2、差错控制编码的基本原理编码器将在这qn个可用码字中选择qk个码字分别代表原始信源中的qk个码字，信道编码码字空间的这M=qk个码字称为“许用码字”，而另外的qn-qk个码字称为“禁用码字”。为了实现纠错编码，一定有qn>M。这M个许用码字也称为一个码组，或称为码字集合。2、差错控制编码的基本原理最小码距与检纠错的关系码重：各个码元中“1”的个数最小码重：“码重”的最小值码距：两个码元对应位上数字不同的位数，也称为“汉明距离”最小码距：各个码元之间距离的最小值。

例如，码字“1001”和“1100”中“1”的个数都为2，所以码重为2；这两个码字对应位上数字不同的位数有2位，所以它们之间的码距也为2。2、差错控制编码的基本原理最小码距与检纠错的关系为检测e个错码，要求最小码距为纠正t个错码，要求最小码距为纠正t个错码，检测e个错码，要求最小码距3、几种简单差错控制编码方法1．恒比码

每组码元中含有相同数目的“0”和“1”，使“0”和“1”的数目比值保持恒定。接收端只要发现接收码元“0”和“1”的数目比值发生变化，则可判断产生误码。3、几种简单差错控制编码方法2．奇偶校验码一维奇偶校验码主要用来检测码元中是否发生奇数个错误，可分为奇校验码和偶校验码两类。一维奇偶校验码由n个信息位加1个监督位构成：1）一维奇偶校验码信息位监督位奇校验码：无误码：有误码：3、几种简单差错控制编码方法2．奇偶校验码一维奇偶校验码主要用来检测码元中是否发生奇数个错误，可分为奇校验码和偶校验码两类。一维奇偶校验码由n个信息位加1个监督位构成：1）一维奇偶校验码信息位监督位14偶校验码：无误码：有误码：3、几种简单差错控制编码方法2．奇偶校验码一维奇偶校验码主要用来检测码元中是否发生奇数个错误，可分为奇校验码和偶校验码两类。一维奇偶校验码由n个信息位加1个监督位构成：1）一维奇偶校验码信息位监督位奇偶校验码的监督式只能判断码元中存在奇数个错误的情况，对于偶数个错误不能识别，而且只能检错，不能纠错。3、几种简单差错控制编码方法二维奇偶校验码是对若干码元组成的方阵按行和列分别添加1位监督位2．奇偶校验码2）二维奇偶校验码二维奇偶校验码不仅可以检测奇数个错误，还可以检测偶数个错误。当一组码元发生偶数个错误时，虽然行监督位不能检测出来，但列监督位可以检测出来。当错码构成矩形区域时，二维奇偶校验码也检测不出了。对于仅在一行中有奇数个错误的二维奇偶校验码，不仅可以检错，也可以纠错。3．正反码正反码中监督位数目与信息位数目相同，当信息位中“1”的个数为奇数时，监督位与信息位一致，当信息位中“1”的个数为偶数时，监督位是信息位的反码。3、几种简单差错控制编码方法

例如：若信息位为10011，则正反码组为1001110011；若信息位为10001，则正反码组为1000101110。3．正反码长度为10的正反码，可以纠正1位错码，接收端纠错的具体步骤如下：（1）将接收码中信息位和监督位按位模2相加，得到5位合成码。若接收码的信息位中“1”的个数为奇数，则合成码为校验码；若为偶数，