信息论与编码（第4版）课件 第6章-信道编码

第6章信道编码信息论与编码（第4版）信道编码主要内容6.1有扰离散信道的编码定理6.2纠错编译码的基本原理与分析方法6.3线性分组码6.4卷积码信道编码信道编码

1948年,信息论的奠基人C.E.Shannon在他的开创性论文“通信的数学理论”中,提出了著名的有噪信道编码定理。他指出：对任何信道,只要信息传输速率R不大于信道容量C,就一定存在这样的编码方法：在采用最大似然译码时,其误码率可以任意小。有噪信道编码定理在理论上给出了对给定信道通过编码所能达到的编码增益的上限,并指出了为达到理论极限应采用的译码方法。在信道编码定理中,香农提出了实现最佳编码的三个基本条件：(1)采用随机编码方式;(2)编码长度Ｌ→∞,即分组的码组长度无限;(3)译码采用最佳的最大似然译码算法。香农认为在满足这三个条件的前提下,有噪信道中可以实现无差错传输。指出：在编码速率小于信道容量的条件下，通过编码可以使译码错误概率任意小，从而达到可靠通信。说明：香农编码定理只说明存在一种编码方式，其误码率随着码长L的增长趋于任意小。未指明：如何构造可实现的可靠传输的编码方法。信道编码/纠错编码/差错控制：就是为解决这一问题而产生的学科，目的是寻找在实际上易于实现且能达到可靠通信的编译码方法。

信道编码信道编码

信道编码信道编码和信源编码

信源编码的基本思想是用尽可能短的码字来表示信息，提高通信的有效性缺点：未考虑信道中存在噪声干扰，将引起误码，降低通信的可靠性信道编码的基本思想是增加多余码元（监督码元/校验位），具有检纠错能力，提高通信的可靠性缺点：增加多余码元，降低通信的有效性信道编码噪声信道的编码问题

信道编码是以信息在信道上的正确传输为目标的编码，可分为两个层次上的问题：如何正确接收载有信息的信号——线路编码如何避免少量差错信号对信息内容的影响——纠错编码6.1 有扰离散信道的编码定理6.1.1差错和差错控制系统分类6.1.2矢量空间与码空间6.1.3随机编码6.1.4信道编码定理6.1.5联合信源信道编码定理差错类型6.1 有扰离散信道的编码定理差错符号由符号发生差错引起，也叫信号差错，信号差错概率用误码元率表示差错比特由信息比特发生差错引起，也叫信息差错，信息差错概率用误比特率表示对于二进制传输系统，符号差错等效于比特差错；对于多进制系统，一个符号差错到底对应多少比特差错却难以确定。因为一个符号由多个比特组成。差错图样6.1 有扰离散信道的编码定理为了定量地描述信号地差错，定义收、发码之“差”为差错图样（errorpattern）：

差错图样E＝发码C－收码R

（模M）例：8进制(M=8)码元，

若发码

C=（0,2,5,4,7,5,2）

收码变为

R=（0,1,5,4,7,5,4）

差错图样

E=C－R=（0,1,0,0,0,0,6）（模8）对于二进制码，有：

E=C

R或

C=R

E

，

此时差错图样中的“１”既是符号差错也是比特差错。差错图样类型6.1 有扰离散信道的编码定理随机差错：差错图样上各码位的取值既与前后位置无关又与时间无关，即差错始终以相等的概率独立发生于各码字、各码元、各比特；主要来源于设备、传播媒介的热噪声。

如：AWGN信道、双绞线、同轴电缆、光纤、微波、卫星、深空通信等信道中的典型差错突发差错：错误前后相关、突然、成串出现。突发差错总是以差错码元开头、以差错码元结尾，头尾之间并不是每个码元都错，而是码元差错概率超过了某个额定值；

如：通信中雷电、强脉冲、电火花造成的突发差错；存储中的读写头抖动、接触不良、介质缺陷等造成的差错。纠错码的分类6.1 有扰离散信道的编码定理按码的功能分为检错码：能自动发现错误纠错码：能自动纠正错误按码结构中对信息序列的处理方式不同分为：分组码：校验位只由每组k个信息位按一定规律产生，而与其他组的信息无关卷积码：校验位不仅与本组k个信息位有关，还与其前面L组的信息位有关纠错码的分类6.1 有扰离散信道的编码定理按码元与信息位的关系分为线性码：所有码元均是原始信息元的线性组合，编码器不带反馈回路非线性码：码元不都是信息元的线性组合，可能还与前面已编的码元有关，编码器可能带反馈回路按码适用的差错类型纠随机差错码：用于随机差错信道，其纠错能力用码组或码段内允许的独立差错的个数来衡量纠突发差错码：用于突发差错信道，其纠错能力由可纠突发差错的最大长度来衡量介于中间的纠随机/突发差错码按照构码理论分代数码、几何码、算术码、组合码差错控制系统分类6.1 有扰离散信道的编码定理前向纠错（ForwardErrorCorrection，FEC）反馈重发（automaticrequestforrepeat，ARQ）混合纠错（HybridErrorCorrection，HEC）

差错控制系统分类6.1 有扰离散信道的编码定理前向纠错（ForwardErrorCorrection，FEC）：

发端信息经纠错编码后传送，收端通过纠错译码自动纠正传递过程中的差错，但当错误个数大于纠错能力时，译码会出现错误。应用：语音、图像、计算机存储系统、磁盘、光盘等优缺点：实时性好无需反向信道，但是译码设备复杂，纠错能力有限。差错控制系统分类6.1 有扰离散信道的编码定理反馈重发（automaticrequestforrepeat，ARQ）：

收端通过检测接收码是否符合编码规律来判断，如判定码组有错，则通过反向信道通知发端重发该码应用：计算机局域网、分组交换网优缺点：编码设备简单，检错能力较高，但增加反馈通道，控制复杂，而且由于出错反馈重发，实时性差。差错控制系统分类6.1 有扰离散信道的编码定理混合纠错（HybridErrorCorrection，HEC）：

前向纠错和反馈重发的结合，发端发送的码兼有检错和纠错两种能力应用：移动通信、卫星通信优缺点：介于上述两者之间，误码率低，设备复杂度适中，实时性和连贯性较好。矢量空间与码空间6.1 有扰离散信道的编码定理F表示码元所在的数域，对于二进制码，F代表二元域{0,1}设n重有序元素的集合V={Vi

},若满足条件：V中矢量元素在矢量加运算下构成加群；V中矢量元素与数域F元素的标乘封闭在V中；分配律、结合律成立则称集合V是数域F上的n维矢量空间，或称n维线性空间，n维矢量又称n重(n-tuples)。矢量空间与码空间6.1 有扰离散信道的编码定理

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

线性相关：

其中任一矢量可表示为其它矢量的线性组合线性无关或线性独立：一组矢量中的任意一个都不可能用其它矢量的线性组合来代替。矢量空间中矢量的关系:线性组合、线性相关、线性无关矢量空间与码空间6.1 有扰离散信道的编码定理一组线性无关的矢量，线性组合的集合就构成了一个矢量空间V，这组矢量就是这个矢量空间的基底。n维矢量空间应包含n个基底基底不是唯一的，例：线性无关的两个矢量（1,0）和（0,1）以及（-1,0）和（0,-1）可张成同一个两维空间。理解要点：维数：基底矢量个数重数：矢量内元素数一个n维的矢量空间由n个n重的基底张出，基底不唯一。自然基底：矢量元素中只含有一个“1”，其余矢量元素为“0”矢量空间与码空间6.1 有扰离散信道的编码定理二元域GF(2)上三重矢量空间以（100）为基底可张成一维三重子空间V1，含21=2个元素，即以(010)(001)为基底可张成二维三重子空间V2，含22=4个元素，即以(100)(010)(001)为基底可张成三维三重空间V,含23=8个元素，V1和V2都是V的子空间。矢量空间与码空间6.1 有扰离散信道的编码定理每个矢量空间或子空间中必然包含零矢量两个矢量正交：V1V2＝0两个矢量空间正交：某矢量空间中的任意元素与另一矢量空间中的任意元素正交正交的两个子空间V1、V2互为对偶空间

(DualSpace)，其中一个空间是另一个空间的零空间（nullspace，也称零化空间）。矢量空间与码空间6.1 有扰离散信道的编码定理

输入序列长：k

(n,k)

输出码字长：n

序列共有

qk

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

k维k重矢量

n维n重矢量

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

输入序列长：k

(n,k)

输出码字长：n

序列共有

qk

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

k维k重矢量

n维n重矢量编码器将在这qn个可用码字中选择qk个码字分别代表原始信源中的qk个码字，信道编码码字空间的这M=qk个码字称为“许用码字”，而另外的qn-qk个码字称为“禁用码字”。为了实现纠错编码，一定有qn>M。这M个许用码字也称为一个码组，或称为码字集合。随机编码6.1 有扰离散信道的编码定理

输入序列长：k

(n,k)

输出码字长：n

序列共有

qk

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

k维k重矢量

n维n重矢量码集点数M占矢量空间总点数qn的比例是：

当n、k差值拉大，码字分布稀疏，码距加大，平均差错变小随机编码时，全部码集的平均差错概率为：

差错概率6.1 有扰离散信道的编码定理假设XN中某码集{C}

m的某个码字

经DMC信道传输后变成接收码字接收端收到r译码出Ck

的差错概率为：其中：差错概率6.1 有扰离散信道的编码定理接收端收到r译码出Ck

的差错概率为：其中：Gallager界，它指出了码字的误码上界：(ρ是人为加入的修正因子，ρ取值范围为[0,1]

)平均差错概率6.1 有扰离散信道的编码定理平均差错概率:(码字概率等于组成该码字的各码元概率之积)为找到差错概率规律，找到平均差错概率，两边取平均：6.1 有扰离散信道的编码定理改变上式平均差错概率的写法：

Pe的上界仅与信道有关而与编码方式无关。M=qK是信息组合数N是每码字的码元数R表示每码元携带的信息量定义函数平均差错概率平均差错概率:6.1 有扰离散信道的编码定理为找到差错概率规律，要找到平均差错概率，两边取平均：定义可靠性函数：（也叫误差指数）

综上可得：平均差错概率平均差错概率:

Pe的上界仅与信道有关而与编码方式无关。平均差错概率6.1 有扰离散信道的编码定理结论：1.译码平均差错概率趋于零的速度与码长N成指数关系 2.可靠性函数E(R)与信息传输率R的关系是一条下凸函数曲线，如下图：

R在[0,R0]区间时，E(R)~R曲线是斜率为-1（-45

）的直线，E(R)反比于R；而当R=C时E(R)=0即可靠性为零。

平均差错概率:有扰离散信道的信道编码定理6.1 有扰离散信道的编码定理只要传信率R小于信道容量C，总存在一种信道码（及解码器），可以以所要求的任意小的差错概率实现可靠的通信。信道编码逆定理信道容量是可靠通信系统传信率R的上边界，如果R＞C，就不可能有任何一种编码能使差错概率任意小。

两个定理常被写在一起，统称为有扰或噪声信道的信道编码定理。纠错编码的基本思路6.2纠错编译码的基本原理与分析方法差错控制的途径之一

从信道编码定理出发，不强调物理意义，只从数学角度分析：减小误差的方法有: 1.增大可靠性函数E(R) 2.增大编码长度N纠错编码的基本思路差错控制的途径之一

从信道编码定理出发，不强调物理意义，只从数学角度分析：减小误差的方法有: 1.增大可靠性函数E(R)

2.增大编码长度NR不变时，信道容量C大者其E(R)大C不变时，码率R小者其E(R)大(1)增大信道容量C(2)减小码率R↑E(R)的方法：6.2纠错编译码的基本原理与分析方法↑E(R)的方法：(1)增大信道容量：

方法：①扩展带宽W

②加大功率Ps③降低噪声N0(2)减小码率R

对与（N,K）线性分组码，有方法：①

q，N不变而减小K，即降低信源速率。 ②

q，K不变而增大N，即提高符号速率，需更大带宽 ③

N，K不变而减小q，即减小信道的输入、输出符号

集，在发送功率固定时提高信号间的区分度，从而提

高可靠性。6.2纠错编译码的基本原理与分析方法纠错编码的基本思路差错控制的途径之一

从信道编码定理出发，不强调物理意义，只从数学角度分析：减小误差的方法有:

1.增大可靠性函数E(R) 2.增大编码长度N

随着N增大，矢量空间XN以指数量级增大，从统计角度而言码字间距离也将加大，从而可靠性提高。

另外，码长N越大，其实际差错概率就越能符合统计规律。6.2纠错编译码的基本原理与分析方法纠错编码的基本思路差错控制的途径之二

从概念上分析纠错编码的原理，纠错能力的获取方法有：

1.利用冗余度 2.噪声均化(随机化)6.2纠错编译码的基本原理与分析方法纠错编码的基本思路差错控制的途径之二

从概念上分析纠错编码的原理，纠错能力的获取方法有：

1.利用冗余度

2.噪声均化(随机化)冗余度：在信息流中插入冗余比特,这些冗余比特与信息比特之间存着特定的相关性。冗余的资源：时间、频带、功率、设备复杂度6.2纠错编译码的基本原理与分析方法纠错编码的基本思路差错控制的途径之二

从概念上分析纠错编码的原理，纠错能力的获取方法有： 1.利用冗余度

2.噪声均化(随机化)噪声均化:让差错随机化，以便更符合编码定理的条件从而得到符合编码定理的结果。基本思想:设法将危害较大的、较为集中的噪声干扰分摊开来，使不可恢复的信息损伤最小。噪声均化的方法：①增加码长N②卷积③交错(或称交织)6.2纠错编译码的基本原理与分析方法纠错编码的基本思路差错控制的途径之二

从概念上分析纠错编码的原理，纠错能力的获取方法有： 1.利用冗余度

2.噪声均化(随机化)噪声均化的方法：①增加码长N②卷积③交错(或称交织)【例】BSC信道误码率Pe=0.01，设编码后纠错能力为10%，设码长N=10，求差错概率解：若保持上述条件及码率R不变，增加码长至N=40，求差错概率解：6.2纠错编译码的基本原理与分析方法纠错编码的基本思路差错控制的途径之二

从概念上分析纠错编码的原理，纠错能力的获取方法有： 1.利用冗余度

2.噪声均化(随机化)噪声均化的方法：①增加码长N②卷积③交错(或称交织)

卷积码在一定约束长度内的若干码字之间也加进了相关性，译码时不是根据单个码字、而是一串码字来作判决。6.2纠错编译码的基本原理与分析方法纠错编码的基本思路差错控制的途径之二

从概念上分析纠错编码的原理，纠错能力的获取方法有： 1.利用冗余度

2.噪声均化(随机化)噪声均化的方法：①增加码长N②卷积③交错(或称交织)

信道噪声造成的符号流中的突发差错，有可能被均化而转换为码流上随机的、可纠正的差错。带交错器的传输系统6.2纠错编译码的基本原理与分析方法纠错编码的基本思路差错控制的途径之二

从概念上分析纠错编码的原理，纠错能力的获取方法有： 1.利用冗余度

2.噪声均化(随机化)噪声均化的方法：①增加码长N②卷积③交错(或称交织)

5×7行列交错器工作原理示意图图中，采用交错方法，去交错后差错分摊在5个码字上。6.2纠错编译码的基本原理与分析方法译码方法—最优译码与最大似然译码译码器的任务：从接收序列中尽可能正确地恢复出原信息。译码算法的已知条件：实际接收到的码字序列{r},r=(r1,r2,…,rN)发端所采用的编码算法和该算法产生的码集XN,满足信道模型及信道参数。可能已受损6.2纠错编译码的基本原理与分析方法译码方法—最优译码与最大似然译码译码过程最佳译码，也叫最大后验概率译码(MAP)在已知r的条件下找出可能性最大的发码ci作为译码估值即令后验概率缺点：实际译码时，定量地找出后验概率值比较困难。6.2纠错编译码的基本原理与分析方法译码方法—最优译码与最大似然译码最大似然译码(MLD：MaximumLikelihooddecoding)定义为已知r的条件下使先验概率最大的译码算法：如果构成码集的2K个码字以相同概率发送，满足p(ci)=1/2K

，i=1,2,…,2K

p(r)对于任何r都有相同的值，满足p(r)=1/2K

则p(ci/r)最大等效于p(r/ci)的最大，在此前提下最佳译码等效于最大似然译码。也叫似然函数6.2纠错编译码的基本原理与分析方法译码方法—最优译码与最大似然译码最大似然译码(MLD：MaximumLikelihooddecoding)对于无记忆信道，

BSC信道的最大似然译码可以简化为最小汉明距离译码。汉明距离译码是一种硬判决译码。由于BSC信道是对称的，只要发送的码字独立、等概，汉明距离译码也就是最佳译码。6.2纠错编译码的基本原理与分析方法汉明重量：码字中非零码元的个数,表示为译码方法—最优译码与最大似然译码汉明距离：两个码字之间对应位置不同码元的个数6.2纠错编译码的基本原理与分析方法d(ci，cj)二元序列：d(000，111)=3 d(111，001)=2 d(100，101)=1 d(100，001)=2四元序列：d(1320120，1332201)=5 d(3221233，3221230)=1

注意：本章后面都将采用二元序列为分析对象

w(ci)w(000)=0 w(111)=3 w(100)=1 最小汉明距离译码

逐比特比较收、发码元，相同与不同的概率记为：若将r和ci的N个码元比较后，有d个不同，则似然函数为：其中，

6.2纠错编译码的基本原理与分析方法译码方法—最优译码与最大似然译码两种译码准则比较（1）最大后验概率准则能使译码平均错误概率最小，因而是最佳准则，但求后验概率很不方便。（2）在输入为等概率分布时，最大似然译码准则等效于最大后验概率准则，可使译码平均错误概率最小。（3）输入不是等概率分布时，最大似然译码准则不一定能使译码平均错误概率最小，因而是次最佳准则。（4）应用最大似然译码准则时，只需根据信道矩阵进行判断，应用很方便，因而成为最常用的准则。6.2纠错编译码的基本原理与分析方法译码方法—最优译码与最大似然译码6.2纠错编译码的基本原理与分析方法译码方法—最优译码与最大似然译码6.2纠错编译码的基本原理与分析方法（1）最大后验概率译码准则译码方法—最优译码与最大似然译码6.2纠错编译码的基本原理与分析方法（1）最大后验概率译码准则译码方法—最优译码与最大似然译码此时，可以确定最佳译码规则为：在此规则下的译码平均错误概率为：

6.2纠错编译码的基本原理与分析方法（2）最大似然译码准则译码方法—最优译码与最大似然译码则可以确定最佳译码规则为：在此规则下的译码平均错误概率为：6.2纠错编译码的基本原理与分析方法主要内容6.3 线性分组码6.3.1线性分组码的生成矩阵和校验矩阵6.3.2伴随式与标准阵列译码6.3.3码距、纠错能力、MDC码及重量谱6.3.4完备码6.3.5循环码回顾码空间6.3 线性分组码N维矢量空间

由n维n重线性无关的矢量张出来。码空间

由n维n重线性无关的码矢（码字）张出来。线性分组码

码空间的一个子空间，是由k维n重线性无关的码矢（码字）张出来。6.3 线性分组码码集C能否构成n维n重矢量空间的一个k维n重子空间？如何寻找最佳的码空间？qk个信息元组以什么算法一一对应映射到码空间。码率－－编码效率：Rc

=klogq/n

输入消息序列m (n,k)输出码字c

m=(mk-1,…,m1,m0)

分组编码器

c=(cn-1,…,c1,c0)

qk<qn输出码字长度输入信息序列长度n位线性分组码由k位信息位与生成矩阵线性运算得到。线性分组码的形成6.3 线性分组码

输入消息序列m (n,k)输出码字c

m=(mk-1,…,m1,m0)

分组编码器

c=(cn-1,…,c1,c0)

qk<qn

1×n1×k

k×n

码字消息生成矩阵

c

＝mG线性分组码的形成输出码字长度输入信息序列长度n位线性分组码由k位信息位与生成矩阵线性运算得到。6.3 线性分组码

1×n1×k

k×n

码字消息生成矩阵

c

＝mG线性分组码的形成

c=

mk-1

gk-1+…+

m1

g1+m0g0

码空间的所有元素（即码字）都可以写成k个基底的线性组合由于k个基底即G的k个行矢量线性无关，矩阵G的秩一定等于k当信息序列m确定后，码字c仅由G矩阵决定，称这k×n矩阵G为该(n,k)线性分组码的生成矩阵。

G＝[gk-1…g1g0]T，有k个(1×n)行矢量，如何选择呢？生成矩阵G6.3 线性分组码c=

mk-1

gk-1+…+

m1

g1+m0g0

c

＝mG要想保证(n,k)线性分组码能够构成k维n重子空间，G

的k个行矢量gk-1,…,g1,g0必须是线性无关的，只有这样才符合作为基底的条件。由于基底不是唯一的，所以G也就不是唯一的。不同的基底有可能生成同一码集，但因编码涉及码集和映射两个因素，码集一样而映射方法不同也不能说是同样的码。生成矩阵的每一个基底（行失）都是一个码字。

生成矩阵G6.3 线性分组码c=

mk-1

gk-1+…+

m1

g1+m0g0

c

＝mG生成矩阵G一般形式如下：生成矩阵G6.3 线性分组码

(n,k)码的任何生成矩阵都可以通过行运算和列置换简化成“系统形式”。Ik是k×k单位阵，用于把信息组m原封不动搬到码字的前k位P是k×(n-k)矩阵，用于通过产生n-k位冗余位或一致校验位。利用系统形式的G生成的（n,k）码叫做系统码，形如：利用非系统形式的G生成的码叫是非系统码把非系统形式的G系统化并不改变码集，只改变了映射规则

空间构成6.3 线性分组码n维n重空间V中有相互正交的n个基底选择V中的k个基底排列成一个k×n的生成矩阵G，构成码空间C，产生(n,k)线性分组码选择另外的

(n–k)个基底排列成一个(n-k)×n生成矩阵H，构成码空间C的对偶空间D，可产生(n,n-k)线性分组码，称为(n,k)的对偶码。

n维n重空间V

映射

k维k重k维n重n-k维n重信息组码空间C对偶空间D

空间mGH(n-k)×n大小k×n大小校验矩阵H6.3 线性分组码

由于码空间C的基底和对偶空间D的基底相互正交，因此这两个空间也正交，互为零空间。C内的任意码字c也必正交于D内的任意码字，当然也正交于H的任意一个行矢量，既有：

cHT=0

或HcT=0

可见，H可用于检验接收码字的正确性，称为码空间C的校验矩阵

则表示接收正确接收码字r，若rHT＝0生成矩阵和校验矩阵的关系6.3 线性分组码码空间C的生成矩阵G是对偶空间D的校验矩阵对偶空间D的生成矩阵H是码空间C的校验矩阵

由于生成矩阵G的每一行都是一个码字，因此有：

HGT=0

或GHT=0

生成矩阵和校验矩阵的关系6.3 线性分组码由于HGT=0,因此

：

系统码的校验矩阵H可以写成分块矩阵：Q为(n-k)×k的一般矩阵，I为(n-k)×(n-k)的单位阵。所以，Q=–PT，对于二元码Q=PT

H=[PT

I]系统码的生成矩阵和校验矩阵分别为：例题16.3 线性分组码一个（6,3）线性分组码，生成矩阵求：（1）计算码集，列出信息组与码字的映射关系；（2）将G系统化，计算系统码集，列出信息位与码字的映射关系。（3）计算系统码的校验矩阵H，若收码r=[100110],检验是否为发码？（4）根据系统码的生成矩阵，画出编码器电路原理图。例题16.3 线性分组码一个（6,3）线性分组码，生成矩阵解：（1）由c=mG,计算得码字,信息组码字000000000001011101010110001011101100信息组码字100111010101100111110001011111010110m=(m2m1m0)

c=(c5c4c3c2c1c0)以信息组m=(101)为例：c=mG=(101)=(100111)例题16.3 线性分组码一个（6,3）线性分组码，生成矩阵解：（2）经过初等运算，将G系统化得到Gs：由c=mGs,计算得系统码字：

+

+

+

+

信息组码字000000000001001011010010110011011101信息组码字100100111101101100110110001111111010例题16.3 线性分组码一个（6,3）线性分组码，生成矩阵解：（3）计算系统码的校验矩阵H,由Gs可得：

这部分即为P这部分即为PT转置利用H检验收码r=[100110]是否为发码

：所以，r不是发码说明传输过程中出错了例题16.3 线性分组码一个（6,3）线性分组码，生成矩阵解：（4）根据系统码生成矩阵Gs画编码器电原理图：

，由c=mGs得：画出编码电路图如下：

输出码字“m2m1m0c2c1c0”例题26.3 线性分组码设二元(7,3)线性分组码c=(c6c5c4c3

c2c1c0

)

，其中，c6c5c4为信息组，c3

c2c1c0为校验位，校验位可用下列方程得到：

求生成矩阵解：依据HcT=0，将校验位方程改写成矩阵形式： c6c5c4

In-kPT即为H例题26.3 线性分组码设二元(7,3)线性分组码c=(c6c5c4c3

c2c1c0

)

，其中，c6c5c4为信息组，c3

c2c1c0为校验位，校验位可用下列方程得到：

求生成矩阵解：由,可得生成矩阵G：

In-kPTIkP转置例题36.3 线性分组码设二元(7,3)线性分组码c=(c6c5c4c3

c2c1c0

)

，其中，c6c5c4为信息组，c3

c2c1c0为校验位，校验位可用下列方程得到：

求生成矩阵解：依据cHT=0，将校验位方程改写成矩阵形式,得到H：改变了例题2中校验方程的书写方式即为HT转置例题26.3 线性分组码设二元(7,3)线性分组码c=(c6c5c4c3

c2c1c0

)

，其中，c6c5c4为信息组，c3

c2c1c0为校验位，校验位可用下列方程得到：

求生成矩阵解：由,可得生成矩阵G：

In-kPTIkP转置改变了例题2中校验方程的书写方式伴随式6.3 线性分组码回顾差错图样E的定义：收、发码之“差”即为差错图样：

差错图样E＝发码C－收码R

（模M）对于二进制码，模2加与模2减等同，有：E=C

R或

R=C

E利用CHT=

0，重写检验接收序列R的正确性过程：

m

C=(cn-1,…,c1,c0)R=(rn-1,…,r1,r0)(n,k)信道RHT＝(C＋E)HT＝CHT＋EHT=EHT=0，收码无误≠0，收码有误在HT固定的前提下，RHT仅与差错图样E有关，与发送码C无关。伴随式6.3 线性分组码RHT＝(C＋E)HT＝CHT＋EHT=EHT=0，收码无误≠0，收码有误定义RHT

的运算结果为伴随式S

S=(sn-k-1,…,s1,s0)=RHT=EHT物理意义上，伴随式S并不反映发送的码字是什么，只反映信道对码字造成怎样的干扰。差错图样E是n重矢量，共有2n种形式，伴随式S是(n-k)重矢量，只有2n-k种形式，因此不同差错图样可能有相同伴随式。译码：收到R后，因HT已知，求出S＝RHT；若能知道对应的E，则通过C=R＋E而求得C。只要E正确，译出的码也就是正确的。伴随式6.3 线性分组码差错图样E的求解通过解线性方程求解E：S=(sn-k-1,…,s1,s0)=EHT=(en-1,…e1,e0)得到线性方程组：

sn-k-1=en-1h(n-k-1)(n-1)+…+e1h(n-k-1)1+e0h(n-k-1)0

s1=en-1h1(n-1)+…+e1h11+e0h10

s0=en-1h0(n-1)+…+e1h01+e0h00方程组中有n个未知数en－1,…e1,e0

，却只有n-k个方程，因此，方程组有多解。伴随式6.3 线性分组码差错图样E的求解S的解：有理数或实数域中，少一个方程就可能导致无限多个解；二元域中，少一个方程导致两个解，少两个方程四个解，以此类推，少n-(n-k)=k个方程导致每个未知数有2k个解，即每一个S，对应2k个差错图样。E的估值：2k个差错图样，到底取哪一个作为附加在收码R上的差错图样E的估值呢？概率译码：把所有2k个解的重量(差错图样E中1的个数)作比较，选择其中最轻者作为E的估值。该方法概念上很简单但计算效率不高。伴随式6.3 线性分组码概率译码依据：若BSC信道的差错概率是p，则长度n的码中错误概率：

0个错1个错2个错…n个错

(1-p)n

p(1-p)n-1

p2(1-p)n-2

pn

由于p<<1,(1-p)n

>>

p(1-p)n-

>>

p2(1-p)n-2

>>…>>pn

出错越少的情况，发生的概率越大，E的重量也越轻。该译码方法实际上体现了最小汉明距离译码准则，即最大似然译码。（对于BSC信道，最小距离译码准则等价于最大似然译码准则）由于E=R+C，所以E的汉明重量(E中1的个数)等于R和C之间的汉明距离。于是，最小汉明距译码就转化为选择重量最小的差错图样E进行译码。标准阵列译码6.3 线性分组码标准阵列译码表构建思想：

伴随式S的总为2n-k个，预先把不同S下的方程组解出，把各种情况下的最大概率译码输出列成一个码表。实时译码时就象查字典那样查一下码表就完成译码。

为避免每接收一个码R不但要解一次线性方程，还要并从2k个解中找出重量最小的E带来的高运算量，实际应用时，采用标准阵列译码表，通过查表译码，简单快捷标准阵列译码6.3 线性分组码标准阵列译码表构建方法：

表中所列码字都是有可能接收到的码字R；将无差错的收码R(即R=C)放在第一行，对应的差错图样为全零E0=(0,0…0)，伴随式为全零S0=(0,0…0)。这样的收码有2k个，故码表有2k列。将错1位的收码放在第2~n+1行，对应差错图样重量为1。将错2位的收码放在第n+1行之后（需满足(1+n)<2n-k，即伴随式数量比(1+n)大）以此类推……直到放满2n-k行（即行数等于伴随式的数目）标准阵列译码6.3 线性分组码每行称一个陪集行首称陪集首每行伴随式相同每列是一个子集列首称子集首每列的发码相同译码方法：①在表中搜索收码R，把R所在列的子集首Cj作为译码结果输出②由R求出S，找到S所在行的R，把R的子集首Cj作为译码结果③由R求出S，找到S所在行的陪集首Ei，译码结果为R+Ei。例46.3 线性分组码一个(5,2)系统线性码的生成矩阵是求:(1)构造标准阵列译码表(2)设收码R=(10101)，译出发码的估值解：(1)构造标准阵列译码表。

首先利用C=mG,求出信息组对应的码字:信息组码字0000000011011110011011111010例46.3 线性分组码一个(5,2)系统线性码的生成矩阵是求:(1)构造标准阵列译码表(2)设收码R=(10101)，译出发码的估值解：(1)构造标准阵列译码表。

由,求出校验矩阵H(题中G是系统化生成矩阵)列出伴随式方程组：S=(sn-k-1,…,s1,s0)=RHT=EHT例46.3 线性分组码一个(5,2)系统线性码的生成矩阵是求:(1)构造标准阵列译码表(2)设收码R=(10101)，译出发码的估值解：(1)构造标准阵列译码表。伴随式有2n-k＝23＝8种组合，构成方式:

1种 5种 2种

无差错的差错图样错1位的差错图样错2位的差错图样

Ej

:(00000) (10000) (00011)

(01000) (00110)

(00100) (00010) (00001)错2位的差错图样有10种,只能挑选其中的两种，挑选方法不唯一例46.3 线性分组码一个(5,2)系统线性码的生成矩阵是求:(1)构造标准阵列译码表(2)设收码R=(10101)，译出发码的估值解：(1)构造标准阵列译码表。分别把Ej

代入伴随式方程组,解出对应的伴随式Sj例46.3 线性分组码一个(5,2)系统线性码的生成矩阵是求:(1)构造标准阵列译码表(2)设收码R=(10101)，译出发码的估值解：(1)构造标准阵列译码表。例46.3 线性分组码一个(5,2)系统线性码的生成矩阵是求:(1)构造标准阵列译码表(2)设收码R=(10101)，译出发码的估值解：(2)可选以下三种方法之一译码：

直接搜索码表，查得(10101)所在列的子集头是(10111)，因此译码输出取为(10111)。

先求伴随式RHT=(10101)

HT=(010)=S4,沿着S4所在行，对码表作一维搜索找到(10101),输出(10101)子集头(10111)。

先求伴随式

RHT=(10101)

HT=(010)=S4,确定S4所对应的陪集首（差错图案）E4=(00010)，将陪集首与收码相加得到码字：

C=R+E4=(10101)+(00010)=(10111)

接收码R=(10101)译码为(10111)讨论6.3 线性分组码例题4中，在制定标准阵列译码表的过程中，由S决定差错图样E时，只有前6行真正体现了最大似然译码。当码字发生0或1位错误时可予以纠正，得到正确译码结果。第7、8行的差错图案选择不是唯一的，选择不同的陪首集E，译码结果也不同，所以出现2位及以上错误时就会出现译码错误。简化的译码表6.3 线性分组码标准阵列译码缺点：需将2n个R存入译码器，存储量大，所以可以构造简化的译码表。（1）简化译码表只建立Si和Ei的对应关系，译码器只需存2n-k个伴随式和2n-k个差错图案。（2）译码时，根据R先求出S，在简化表中找到S对应的E，译码结果为R+E。码字子集和码字6.3 线性分组码N重码矢c=(cn-1,cn-2,…c1,c0)对应于N维矢量空间XN中的一个点，全体码字所对应的点构成矢量空间里的一个子集

发码及传输无误时的收码也必位于该子集当出现传输差错时，接收的N重矢量:可能对应到子集外空间某一点可能对应到该子集的另一点上C1C2C3C4C5黑色的表示为发码Ci灰色的码字表示非发码码距、最小码距、纠错能力6.3 线性分组码码距：码字之间的距离，用汉明距离表示。最小码距dmin：码集C不同码字之间码距的最小值。检错能力：如果一个分组码能检出总位数不大于e个码元差错，称码的检错能力为e纠错能力：如果分组码能纠正总位数不大于t个码元差错，称码的纠错能力为t。

定理6.1

任何最小距离dmin的线性分组码，其检错能力为（dmin-1）,纠错能力t为要点：

若要能检测e位随机差错，要求dmin≥

e+1

，

此时t=0

若要能纠正t位个随机差错，要求dmin≥

2t+1

，此时t=e

若要能同时检测e位、纠正t位错误时，dmin≥

t+e+1，此时t≤

e纠错能力相关定理6.3 线性分组码向下取整eett纠错能力相关定理6.3 线性分组码定理6.2

线性分组码的最小距离等于码集中非零码字的最小重量

dmin=min{w(Ci)} Ci

C

及Ci

0

证明过程：利用群的封闭性，由于分组码时群码，任意两个码字之和仍然是码字：

Ci

Cj=Ck

C任意两个码字间的汉明距离必然是另一个码字的重量： d(Ci，Cj)=w(Ci

Cj)}=Ck

C

因此有：

dmin=mind(Ci，Cj)=min{w(Ck)}

纠错能力相关定理6.3 线性分组码

如果码的最小距离为dmin，则码字C中码元cn-1…c0中至少有dmin个1，即上式中至少有dmin个列矢量之和才能线性组合出0，少一列dmin-1列都不能线性组合出0，所以H有dmin-1列线性无关。纠错能力相关定理6.3 线性分组码定理6.4

(n,k)

线性分组码的最小距离必定小于等于

(n-k+1)dmin

(n-k+1)证明过程：因为矩阵H是(n-k)×n的矩阵，该矩阵的秩最大值为(n-k)，又因为H的列秩为dmin-1，所以dmin-1

n-k，即dmin

(n-k+1)各列都不相同，任意2列之和不等于0，至少有3列才能组合出一个0，所以线性无关的列数为2，dmin=3极大最小距离码(MDC–MaximizedminimumDistanceCode)

6.3 线性分组码dmin=n-k+1的码称为极大最小距离码

因为(n,k)线性分组码码最小距离dmin的上边界是n-k+1，若设计的（n,k）线性码的dmin达到了n-k+1，就是达到了设计性能的极点。二进制码中，只有(n,1)重复码是MDC码。非二进制码中，MDC码是存在的，如RS(Reed-Solomon)码总体的、平均的纠错能力不但与最小距离有关，而且与其余码距或者说与码字的重量分布特性有关。称为重量谱或距离谱完备码(PerfectCode)6.3 线性分组码任何一个二元(n,k)线性分组码都有2n-k个伴随式。若该码的纠错能力是t，则对于任何一个重量不大于t的差错图样，都应有一个伴随式与之对应，即伴随式数目满足：上式称作汉明限，任何一个纠t码都应满足上述条件。完备码：伴随式和不大于t个差错的差错图样数目相等的二元(n,k)线性分组码，即伴随式数目满足下式：此时，标准译码阵列中能将所有重量不大于t的差错图样选作陪集首，而没有一个陪集首的重量大于t，这时能校验位得到最充分的利用。汉明码(HammingCode)6.3 线性分组码汉明码不是指一个码，而是代表一类码。汉明码的纠错能力t=1，既有二进制的，也有非二进制的。二进制时，汉明码码长n和信息位k服从以下规律：

(n,k)=(2m-1,2m-1-m)，其中m=n-k，是正整数

当m＝3、4、5、6、7、8…时，有汉明码(7,4)、(15,11)、 (31,26)、(63,57)、(127,120)、(255,247)…。汉明码是标准阵列最规则因而译码最简单的码，但不一定是纠错能力最强的码。汉明码是完备码汉明码(HammingCode)6.3 线性分组码

构造汉明码：n-k个码元共能构成2n-k-1种形式,恰好和汉明码校验矩阵的列数n=2m-1相等二元(n,k)码的校验矩阵大小(n－k)×n，每列有n-k个码元汉明码的校验矩阵H具有特殊的性质，能使构造方法简化因此，只要先排列n-k个码元构成的所有列，再通过列置换将矩阵H转换成系统形式，就可以生成矩阵G。

(n,k)=(2m-1,2m-1-m)，其中m=n-k，是正整数例56.3 线性分组码构造一个m=3的二元(7，4)汉明码。解：先利用汉明码的特性构造一个(7，4)汉明码的校验矩阵H，再通过列置换将它变为系统形式：

列置换

=[PT

I3]

再得生成矩阵G为

G=[I4

P]=

高莱（Golay）码6.3 线性分组码是二进制(23,12)线性码最小距离dmin＝7，纠错能力t=3是完备码在(23,12)码上添加一位奇偶位即得二进制线性(24,12)扩展高莱码，其最小距离dmin＝8

循环码(CyclicCode)6.3 线性分组码循环码是线性码的一个子类循环移位特性：码集C中任何一个码字的循环移位仍是码字一般(n,k)线性分组码k个基底基底间不存在规则的联系由这k个基底组成生成矩阵G(n,k)循环码k个基底由同一个基底循环k次得到将这个基底用码多项式g(x)描述用生成矩阵生G成码字用码多项式g(x)生成码字C=(cn-1,…,c1,c0)C=(cn-1,…,c1,c0)循环码(CyclicCode)6.3 线性分组码循环码的码多项式定义把码字C＝(cn-1cn-2

…c1c0)与一个不大于n-1次的码多项式C(x)对应起来。码多项式C(x)定义为：对于二进制码，ci

{0,1},i=0,…，n-1。C(x)

=cn-1xn-1+cn-2

xn-2

+…+c1x+c0循环码(CyclicCode)6.3 线性分组码循环码的循环移位循环移一位：C0=(cn-1cn-2

…c1c0)C1=(cn-2

…c1c0cn-1)

对应码多项式：C0(x)=cn-1xn-1+cn-2xn-2+…+c1x+c0

C1(x)=

cn-2xn-1+cn-3xn-2+…+c0x+cn-1观察码多项式，可用如下多项式运算来表达循环移位：移1位：

C1(x)=xC0(x) mod(xn

+1)

移2位：

C2(x)=xC1(x)=x2C0(x) mod(xn

+1)

移n-1位：Cn-1(x)=xCn-2(x)=xn-1C0(x)mod(xn

+1)

循环码(CyclicCode)6.3 线性分组码根据码空间的封闭性，码字的线性组合仍是码字。C(x)=a0C0(x)+a1xC0(x)+a2x2C0(x)+…+an-1xn-1C0(x) =(a0+a1x

+a2x2+…+an-1xn-1)C0(x) =A(x)C0(x)mod(xn

+1) 其中C0(x)是一个码多项式，而A(x)是次数不大于n-1的任意多项式。对于二进制码，ai

{0,1},i=0,…，n-1。观察上式，若：C0(x)是n-k次码多项式A(x)是k-1次信息多项式，k个系数对应k个信息元，有2k种组合则若C0(x)不变，恰好可产生2k个码字,C0(x)就起到了生成多项式的作用。

这样的C0(x)是否存在？循环码(CyclicCode)6.3 线性分组码g(x)不唯一，但一定是(xn+1)的因子；g(x)是(n-k)次的首一码多项式，即(n-k)次项的系数为1

。码多项式信息多项式生成多项式C(x)=A(x)C0(x)mod(xn

+1)C(x)=m(x)g(x)信息多项式：m(x)＝mk-1x

k-1

+mk-2x

k-2+…+m2x2+m1x+m0生成多项式：g(x)＝x

n-k

+gn-k-1x

n-k-1+…+g2x2+g1x+1生成多项式码多项式：C(x)=cn-1xn-1+cn-2

xn-2

+…+c1x+c0g(x)如何获取？循环码(CyclicCode)6.3 线性分组码构造(n,k)循环码的方法（1）对(xn+1)作因式分解，找出(n-k)次因式；（2）以(n-k)次因式为生成多项式g(x)，与信息多项式m(x)相乘，可得码多项式C(x)=m(x)g(x)。例56.3 线性分组码解：(1)

对(x7+1)作分解，找出n-k次因式。

x7+1＝(x+1)(x3+x2+1)(x3+x+1)

n-k因式g(x)对偶式h(x) 循环码

1(x+1) (x3+x2+1)(x3+x+1) (7,6)3(x3+x2+1)(x+1)(x3+x+1) (7,4)3(x3+x+1)(x+1)(x3+x2+1) (7,4)4(x+1)(x3+x2+1)(x3+x+1) (7,3)4(x+1)(x3+x+1)(x3+x2+1) (7,3)6(x3+x2+1)(x3+x+1)

(x+1) (7,1)研究一个长度n=7的循环码的构成方法例56.3 线性分组码解：(2)构成(7,3)循环码：

选g(x)=(x+1)(x3+x+1)=(x4+x3+x2+1)，

则C(x)=m(x)g(x)=(m2x2+m1x+m0)(x4+x3+x2+1),对应码字：

研究一个长度n=7的循环码的构成方法信息组m(m2m1m0)码字C(c6c5c4c3c2c1c0)00000101001110010111011100000000011101011101001001111110100110100110011101010011如何校验？循环码(CyclicCode)6.3 线性分组码多项式xn+1可因式分解为

的形式；如果g(x)代表(n，k)循环码的生成多项式，则h(x)代表该循环码的一致校验多项式，其阶次为k。h(x)的校验作用表现在：任何码多项式C(x)与h(x)的模xn+1乘积一定等于0，而非码字与h(x)的乘积必不为0。 C(x)h(x)=m(x)g(x)h(x) =m(x)(xn+1) =0mod(xn+1)校验多项式xn+1＝g(x)h(x)循环码(CyclicCode)6.3 线性分组码生成多项式

生成矩阵设是某个(n,k)循环码的生成多项式，由于，对应k个码字，且它们线性无关，则一定是生成矩阵,写成多项式形式为:k-1个0生成多项式的系数系统循环码G内关系：第1行逐步向右移动1位构成第2行及以后各行。循环码(CyclicCode)6.3 线性分组码系统循环码码字的前k位为信息位而后(n－k)位为校验位：其生成矩阵必定有如下形式第i行对应的多项式为：C(x)=xn-km(x)+r(x)ri(x)是次数小于n-k的多项式循环码(CyclicCode)6.3 线性分组码系统循环码的生成矩阵循环码生成矩阵各行gi(x)必定能被生成多项式g(x