第11章-差错控制编码-电信

第11章过失控制编码本章知识点:1、了解过失控制技术种类2、掌握纠错编码原理、最小码距和检错、纠错之间关系；了解奇偶监督码、恒比码编码方法。3、掌握线性分组码编码和译码方法4、掌握循环码编码和译码方法11.1概述11.2纠错编码的根本原理11.3纠错编码的性能11.4简单的实用编码11.5线性分组码11.6循环码11.7卷积码11.8Turbo码11.9低密度奇偶校验码11.10网格编码调制11.11小结第11章过失控制编码2024年1月7日3为保证运送途中不出现打碎灯泡的情况——有效性——可靠性11.1概述2024年1月7日4

通信中的情况：针对乘性干扰针对加性干扰合理选择调制/解调方法，增大发射功率—采用均衡等措施11.1概述2024年1月7日511.1概述过失控制编码2024年1月7日611.1概述信道分类(从过失控制角度看)：随机信道：错码的出现是随机的。突发信道：错码是成串集中出现的。混合信道：既存在随机错码又存在突发错码。过失控制技术的种类：检错重发前向纠错反响校验检错删除信道编码分类：线性码和非线性码分组码和卷积码系统码和非系统码2024年1月7日711.1概述

不同的编码方法，有不同的检错或纠错能力。多余度：就是指增加的监督码元多少。例如，假设编码序列中平均每两个信息码元就添加一个监督码元，那么这种编码的多余度为1/3。编码效率(简称码率)：设编码序列中信息码元数量为k，总码元数量为n，那么比值k/n就是码率。

冗余度：监督码元数(n-k)和信息码元数k之比。理论上，过失控制以降低信息传输速率为代价换取提高传输可靠性。监督码元：在4种过失控制技术中除第3种外，都是在接收端识别有无错码。所以在发送端需要在信息码元序列中增加一些过失控制码元，它们称为监督码元。2024年1月7日811.2纠错编码的根本原理1、分组码根本原理将信息码分组，为每组信息码附加假设干监督码的编码称为分组码。在分组码中，监督码元仅监督本码组中的信息码元。

卷积码又称连环码。卷积码编码器把k比特信息段编成n比特的码组，但所编的n长码组不仅同当前的k比特信息段有关，而且还同前面的(N-1)个(N>1,整数)信息段有关联。分组码卷积码2024年1月7日911.2纠错编码的根本原理1、分组码根本原理规那么：使码组中“1〞的个数为偶数情形1：没有冗余——不能发现错误情形2：参加冗余——可以发现错误

冗余⤎另外4个码组许用码组禁用码组2024年1月7日1011.2纠错编码的根本原理1、分组码根本原理规那么：使码组中“1〞的个数为偶数情形1：没有冗余——不能发现错误情形2：参加冗余——可以发现错误

冗余⤎另外4个码组许用码组禁用码组

只能检出一个码组中1个和3个(奇数)错码的情况，不能发现2个(偶数)错码的情况，也不能纠正错误。2024年1月7日1111.2纠错编码的根本原理1、分组码根本原理情形1：没有冗余——不能发现错误情形2：参加冗余——可以发现错误许用禁用2024年1月7日1211.2纠错编码的根本原理1、分组码根本原理这时，能够发现2个以下错码，或者纠正

1位错码。2024年1月7日1311.2纠错编码的根本原理1、分组码根本原理综上所述不同的编码方法，检错或纠错能力也不同。2024年1月7日1411.2纠错编码的根本原理1、分组码根本原理分组码的一般结构：分组码的符号：(n,k)n－码组的总位数，又称为码组的长度(码长);k－码组中信息码元的数目;n–k＝r－码组中的监督码元数目，或称监督位数目。2024年1月7日1511.2纠错编码的根本原理2、码重和码组码重(w)：码距(d)：把码组中“1〞的个数目，简称码重。把两个码组中对应位上数字不同的位数，即两个码组对应位模2和的重量，称为码组的距离，简称码距。码距又称汉明距离。码长(n)：码组(码字)中的码元个数。“011011〞的距离为3

码重为

32024年1月7日1611.2纠错编码的根本原理2、码重和码组码重(w)：码距(d)：最小码距(d0)：把码组中“1〞的个数目，简称码重。把两个码组中对应位上数字不同的位数，即两个码组对应位模2和的重量，称为码组的距离，简称码距。码距又称汉明距离。把某种编码中各个码组之间距离的最小值称为最小码距(d0)。假设是线性码，d0就等于(非全零)码组的最小重量。一种编码的检错和纠错能力决定于最小码距d0。码长(n)：码组(码字)中的码元个数。2024年1月7日1711.2纠错编码的根本原理3、最小码距与纠检错能力(n,k)分组码，纠(检)错能力为：

(1)为检测e个错码，要求最小码距d0

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

2t+1(3)为纠正t个错码，同时检测e个错码，要求最小码距2024年1月7日1811.2纠错编码的根本原理3、最小码距与纠检错能力(n,k)分组码，纠(检)错能力为：

(1)为检测e个错码，要求最小码距d0

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

2t+1(3)为纠正t个错码，同时检测e个错码，要求最小码距2024年1月7日1911.2纠错编码的根本原理4、编码效率和编码增益编码效率简称码率：冗余度：编码增益：监督码元数(n-k)和信息码元数k的比值，即(n-k)/k。

信息码元数k与编码组的总码元数(即码长)n的比值。

在保持误码率恒定条件下，采用纠错编码所节省的信噪比称为编码增益。2024年1月7日2011.4简单的实用编码11.4.1奇偶监督码

奇偶监督码是最简单的检错码，监督位只有1位，因此码率Rc=(n-1)/n很高。设编码组为，其中前n-1位为信息码，第n位为监督码a0。

若a0的加入使码组中的“1”的数目为偶数，即满足条件：，则称为偶数监督码。

若a0的加入使码组中的“1”的数目为奇数，即满足条件：，则称为奇数监督码。这种编码能够检测奇数个错码。但对突发过失的漏检率接近于1/2。监督关系式校正子2024年1月7日2111.4简单的实用编码11.4.1奇偶监督码

奇偶监督码是最简单的检错码，监督位只有1位，因此码率Rc=(n-1)/n很高。设编码组为，其中前n-1位为信息码，第n位为监督码a0。

若a0的加入使码组中的“1”的数目为偶数，即满足条件：，则称为偶数监督码。

若a0的加入使码组中的“1”的数目为奇数，即满足条件：，则称为奇数监督码。适用：检测随机出现的零星过失。很高〔因为只有一位监督位〕。

码率：2024年1月7日2211.4简单的实用编码11.4.2二维奇偶监督码〔方阵码〕先把上述奇偶监督码的假设干码组排成矩阵，每一码组写成一行，然后再按列的方向增加第二维监督位。

纠检能力：有较强的检错能力，并有一定的纠错能力。

适用：适于检测长度不大于行数(或列数)的突发错误。2024年1月7日2311.4简单的实用编码11.4.3恒比码检测方法：计算接收码组中“1〞的数目，就可知是否有错。

适用：用于电报传输系统或其他键盘设备产生的字母和符号。编码规那么：个许用码组，可分别用来代表26个英文字母及其他符号。2024年1月7日2411.5线性分组码代数码：建立在代数学根底上的编码。

具有封闭性，即任意两个许用码组之和(逐位模2加)仍为一许用码组。

它的最小码距等于非全零码组的最小重量。线性码：按照一组线性方程构成的代数码。在线性码中信息位和监督位是由一些线性代数方程联系着的。线性分组码：按照一组线性方程构成的分组码。线性分组码的性质：2024年1月7日2511.5线性分组码1、汉明码假设要构造具有纠错能力的〔n，k〕码，那么需增加督元的数目。当“=〞成立时，构造的线性分组码称为汉明码

汉明码是一种能够纠正1位错码，且编码效率较高的一种线性分组码。

其特点是d0=3(能够纠正一个错码或检两个错码)，码长n与监督位数r＝n－k满足关系式n=2r-1。2024年1月7日2611.5线性分组码1、汉明码(7,4)汉明码例在(7,4)码中，n=7，k=4，r＝n－k=3。设码组为a6a5a0，其中信息码元为a6a5a4a3，监督码元为a2a1a0。用S1、S2和S3表示3个监督关系式中的校正子(又称校验子、伴随式)。假设S=0就认为无错码；假设S=1就认为有错码。2024年1月7日2711.5线性分组码1、汉明码(7,4)汉明码例仅当一位错码的位置在a2、a4、a5或a6时，校正子S1为1；否那么S1为0。同理：2024年1月7日2811.5线性分组码1、汉明码(7,4)汉明码例(A)2024年1月7日2911.5线性分组码1、汉明码(7,4)汉明码例(A)2024年1月7日3011.5线性分组码1、汉明码(7,4)汉明码例接收端译码——检错纠错过程2024年1月7日3111.5线性分组码1、汉明码一般来说，假设码长为n，信息位数为k，那么监督位数r＝n－k。如果希望用r个监督位构造出r个监督关系式来指示1位错码的n种可能位置，那么要求：对于汉明码，上式取等号。这说明用来纠正单个错误时，汉明码所用的监督位最少。与码长相同的其他纠正单个错误的码相比，其码率最高。

表中所列的(7,4)汉明码的最小码距d0=3。因此，这种码能够纠正1个错码或检测2个错码。由于码率k/n=(n-r)/n=1–r/n，故当n很大和r很小时，码率接近1。可见，汉明码是一种高效码。2024年1月7日3211.5线性分组码2、监督矩阵〔H矩阵〕

监督码元和信息码元之间的关系称为监督方程。将它改写为：可以表示成矩阵形式：简记为：H

AT=0T

或A

HT=0A=[a6

a5

a4

a3

a2

a1

a0]0=[000]右上标“T”表示将矩阵转置。将H称为监督矩阵。2024年1月7日3311.5线性分组码2、监督矩阵〔H矩阵〕讨论：(1)监督矩阵H是一个r×n阶(r行n列)矩阵。(2)任一发送码组A都满足式HAT=0T的关系。也就是说只要监督矩阵H给定，编码时监督位和信息位的关系就完全确定了。H的每行中的“1〞的位置表示相应码元之间存在的监督关系。例如，H的第一行1110100表示监督位a2是由a6a5a4之和决定的。(n,k)码的H矩阵必须有r=n-k行，且各行必须是线性无关的。2024年1月7日3411.5线性分组码2、监督矩阵〔H矩阵〕讨论：(3)H矩阵可以分成两局部：(4)典型H矩阵的各行一定是线性无关的。非典型形式的监督矩阵可以经过初等行运算化为典型阵。式中，P为r

k阶矩阵，Ir为r

r阶单位方阵。具有[PIr]形式的H矩阵称为典型监督矩阵。由典型监督矩阵及信息码元很容易算出各监督码元。(7，4)码r=32024年1月7日3511.5线性分组码3、生成矩阵〔G矩阵〕汉明码例子中的监督位公式为：也可以改写成矩阵形式：或者写成：式中，Q为一个k

r阶矩阵，它为P的转置，即：

上式表示，在信息位给定后，用信息位的行矩阵乘矩阵Q就产生出监督位。P阵Q阵

Q=PT

2024年1月7日3611.5线性分组码3、生成矩阵〔G矩阵〕将Q的左边加上1个k

k阶单位方阵，就构成1个矩阵G。G称为生成矩阵，因为由它可以产生整个码组，即有：或者2024年1月7日3711.5线性分组码3、生成矩阵〔G矩阵〕讨论：(1)生成矩阵G是一个k×n阶矩阵。(2)具有[IkQ]形式的生成矩阵称为典型生成矩阵，由它产生的分组码称为系统码。

(3)典型生成矩阵G和典型监督矩阵H之间由Q=PT或P=QT相联系。即：假设知H=[PIr]，那么由Q=PT，可得G=[IkQ]假设知G=[IkQ]，那么由P=QT，可得H=[PIr]2024年1月7日3811.5线性分组码3、生成矩阵〔G矩阵〕讨论：(4)任一码组A都是G的各行的线性组合。G的各行本身就是一个许用码组。(5)非典型形式的生成矩阵经过初等行运算也一定可以化为典型阵。(6)注意：H矩阵、G矩阵的各行应该线性无关的。2024年1月7日3911.5线性分组码4、校正子S与译码

错误图样假设ei=0，表示该接收码元无错；假设ei=1，那么表示该接收码元有错。设发送码组A=[a6

a5

a4

a3

a2

a1

a0]，接收码组，则错误图样(收发码组之差)为：B–A=E(模2)式中2024年1月7日4011.5线性分组码4、校正子S与译码

S和E的关系接收端计算校正子为：可以改写成

B=A+E(模2)S=B

HT=

(A+E)HT

=A

HT+E

HT=E

HT由于A

HT=0，所以校正子S只E与有关，即S和错码E之间有确定的线性变换关系。2024年1月7日4111.5线性分组码4、校正子S与译码

译码

对接收码组B计算校正子：S=B

HT

；译码过程即纠错和检错的过程。其步骤如下：假设S=0(全0阵)，表示接收码组B无错；假设S≠0，那么由S=EHT解得错误图样E；

由B=A+E(模2)可得到纠错后的码组为A=B+E

。2024年1月7日4211.6循环码

循环码是(n,k)线性分组码的一个重要子类。

其编解码设备简单，检(纠)错能力较强。

有RS、BCH等高效子类码，实际应用广泛。

循环码除了具有线性分组码的一般性质外，还具有循环性。2024年1月7日4311.6循环码循环性：是指任一码组循环一位(即将最右端的一个码元移至左端，或反之)以后，仍为该码中的一个码组。表中的第2

码组向右移一位即得到第

5码组；(7,3)循环码表中的第6

码组向右移一位即得到第3码组。2024年1月7日4411.6循环码1、码多项式在代数编码理论中为了便于运算，常以多项式来表示码组。码字〔1100101〕的多项式可表示为： 多项式的系数就是码组中的各码元，x

仅是码元位置标记。n=7时

一个长度为n的码组A=[an-1

an-2

…a0]可以表示成多项式形式：2024年1月7日4511.6循环码1、码多项式码多项式的按模运算假设一个整数m可以表示为 〔Q为整数〕

m

p

(模n)那么在模n运算下，有2024年1月7日4611.6循环码1、码多项式码多项式的按模运算或那么式中，码多项式系数之间的加法和乘法仍按模2运算。2024年1月7日4711.6循环码1、码多项式码多项式的按模运算

解运算过程：即有那么有2024年1月7日4811.6循环码在循环码中，假设A(x)是一个长为n的许用码组，那么xiA(x)在按模xn+1运算下，也是该编码中的一个许用码组，即假设：那么A(x)也是该编码中的一个许用码组。1、码多项式2024年1月7日4911.6循环码2、生成多项式g(x)1)存在性

在一个(n,k)循环码中，有一个且仅有一个次数为(n–k)的多项式：这唯一的(n–k)次多项式g(x)为码的生成多项式。g(x)表示该循环码的前(k-1)位皆为“0〞的码组。2024年1月7日5011.6循环码(2)所有码多项式A(x)都可被g(x)整除，而且任意一个次数不大于(k-1)的多项式乘g(x)都是码多项式。

该条性质可用于编码，还可用于验证接收码组是否出错。2、生成多项式g(x)2)性质(1)g(x)是一个：

常数项为1；

最高次数为(n-k)次；

是xn+1的一个因式。

该条性质给我们提供了一种对于给定的(n,k)循环码，寻找或确定其生成多项式的方法。2024年1月7日5111.6循环码3、生成矩阵G在循环码中，一个(n,k)码有2k个不同的码组。假设用g(x)表示其中前(k-1)位皆为“0〞的码组，那么g(x)，xg(x)，x2g(x)，…，xk-1g(x)都是码组，而且这k个码组是线性无关的。因此它们可以用来构成此循环码的生成矩阵G。

由于此式不符合G=[IkQ]的形式，所以它不是典型阵。将其作线性变换，可化成典型阵。一旦确定g(x)，整个(n,k)循环码就被确定了。g(x)是循环码的核心。对于给定的k位信息码，由g(x)构造出G(x)，从而产生(n,k)循环码。2024年1月7日5211.6循环码4、循环码的编码方法一：对于给定的信息码m(x)，相应的码多项式A(x)=m(x)g(x)，它是非系统码。方法二：m(x)与G(x)相乘。此法得到的是非系统码；假设先将生成矩阵G(x)化为典型阵，那么可得到系统码。2024年1月7日5311.6循环码4、循环码的编码方法三：A(x)=xn-km(x)+r(x)，属系统码。编码步骤如下：(1)用xn-k乘m(x)。这一运算实际上是在信息码后附加上(n–k)个“0〞。(2)用g(x)除xn-km(x)，得到商Q(x)和余式r(x)，即：(3)编出的码组T(x)为：A(x)=xn-km(x)+r(x)

由以上编码步骤可见，编码