信息论与编码 第6章(2)(纠错)

2023/2/51第六章信道编码2023/2/52问题的提出愿望：信息传输多快好省。现实：（1）速度：受信道容量的限制，不可能无限大；（2）质量：受信道噪声的干扰，传输错误不可避免。衡量信息传输可靠性的指标：平均差错率Pe。Pe与信道的统计特性有关，不可能为零，有时甚至很大。降低Pe的方法：先对消息进行编码再送入信道传送，这种为降低平均差错率而进行的编码称为信道编码；在信道输出端加信道译码器进行信息还原。香农第二编码定理所给出的结论：只要信道编码和译码的方法得当，就可使平均差错率趋于零。

编码信道信道编码器f信道信道译码器F2023/2/536.1

有扰离散信道的编码理论6.2

纠错编译码的基本原理与分析方法6.3线性分组码6.4卷积码6.5

其它信道编码内容2023/2/546.1有扰离散信道的编码定理6.1.1差错和差错控制系统分类

6.1.2矢量空间与码空间

6.1.3随机编码与信道编码定理2023/2/556.1.1差错和差错控制系统分类差错率是衡量传输质量的重要指标之一,它有几种不同的定义。码元差错率/符号差错率指在传输的码元总数中发生差错的码元数所占的比例(平均值),简称误码率(Errorsymbolrate)。是指信号差错概率比特差错率/比特误码率(Errorbitrate)：在传输的比特总数中发生差错的比特数所占比例是指信息差错概率对二进制传输系统,符号差错等效于比特差错;对多进制系统,一个符号差错对应多少比特差错却难以确定2023/2/56为定量地描述信号的差错,定义差错图样E:

E=C－R(模M)最常用的二进制码可当作特例来研究,其差错图样等于收码与发码的模2加,即E=C⊕R

或C=R⊕E设发送的码字C1111111111

接收的码字R1001001111

差错的图样E

0110110000差错图样中的“1”既是符号差错也是比特差错,差错的个数叫汉明距离。差错图样类型随机差错,突发差错：差错图样2023/2/57纠错码分类从功能角度讲,差错码分为检错码和纠错码按照对信息序列的处理方法,有分组码和卷积码按照码元与原始信息位的关系,分为线性码和非线性码按照适用的差错类型,分成:纠随机差错码和纠突发差错码按照构造码的理论：代数码、几何码、算术码和组合码。2023/2/58信道编码的基本思想信道编码按一定规则给数字序列m增加一些多余的码元,使不具有规律性的信息序列m变换为具有某种规律性的数码序列C；码序列中的信息序列码元与多余码元之间是相关的；信道译码器利用这种预知的编码规则译码。检验接收到的数字序列R是否符合既定的

规则,从而发现R中是否有错,或者纠正其中的差错；根据相关性来检测/发现和纠正传输过程中产生的差错就是信道编码的基本思想。2023/2/59差错控制系统分类前向纠错(FEC)：发送端的信道编码器将信息码组编成具有一定纠错能力的码。自动请求重发(ARQ)：发端发送检错码,如CRC(循环冗余校验码)混合纠错(HEC)：是FEC与ARQ方式的结合。信息反馈(IRQ)：2023/2/5106.1.2矢量空间与码空间分组码的一个码字可以看作一个n重矢量，所以可以用矢量空间来分析和理解分组码。F表示码元所在的数域，对于二进制码，F代表二元域{0,1}。设n重有序元素的集合V={Vi

},

则称集合V是数域F上的n维矢量空间，或称n维线性空间，n维矢量又称n重(n-tuples)。线性空间的基底、自然基底、子空间、矢量正交、矢量空间正交、对偶空间“重数”：构成矢量的有序元素的个数；“维数”：张成矢量空间基底的个数；维数不可能大于重数，而当维数小于重数时说明这是个子空间。2023/2/511码空间和分组编码的任务

消息k长 (n,k)码字n长

qk

种分组编码器qn种

k维k重矢量n维n重矢量

通常qn>>qk，分组编码的任务是要在n维n重矢量空间的qn种可能组合中选择其中的qk个构成一个码空间，其元素就是许用码的码集。选择一个ｋ维n重子空间作为码空间。确定由k维k重信息空间到ｋ维n重码空间的映射方法。码空间的不同选择方法，以及信息组与码组的不同映射算法，就构成了不同的分组码。2023/2/5126.1.3随机编码与信道编码定理

如果不考虑编码的具体方法，而是运用概率统计的方法在特定信道条件下对编码信号的性能作出统计分析，求出差错概率的上，下限边界，其中最优码所能达到的差错概率上界称为随机码界。随机编码的含义2023/2/513错误概率的上界对于离散无记忆信道（DMC）。错误平均概率的上界为：E(R)为可靠性函数，也叫误差指数码率：R=(lbM)

/N

M是可能的信息组合数，M=qKN是每码字的码元数，R表示每码元携带的信息量，单位是每符号比特（bit/symbol）是全部码集的平均差错概率2023/2/514正定理：只要传信率R小于信道容量C，总存在一种信道码（及解码器），可以以所要求的任意小的差错概率实现可靠的通信。逆定理：信道容量C是可靠通信系统传信率R的上边界，如果R>C，就不可能有任何一种编码能使差错概率任意小。上述两定理统称为有扰或噪声信道的信道编码定理信道编码定理2023/2/5156.2纠错编译码的基本原理与分析方法6.2.1纠错编码的基本原理6.2.2译码方法---最优译码和最大似然译码2023/2/5166.2.1纠错编码的基本原理6.2.1纠错编码的基本思想一、从编码定理出发讨论纠错码的基本原理：从上面的公式可以看出：要减小Pe：（1）增大N;（2）增大Er(R)；1增大信道容量C（1）扩展带宽。（2）加大功率。（3）减小噪声功率。2减小码率R(=KlbQ/N)增大码长NC,R,K/N不变2023/2/517二、从冗余度和噪声均化讨论纠错码的基本原理：冗余度：就是在信息流中插入冗余比特，插入的冗余比特与信息比特存在着特定的相关性。这样如果在传输过程中有个别信息比特受损，也可以从冗余比特中恢复或发现受损比特。从而保证了信息传输的可靠性。传输冗余比特必然要动用冗余的资源:

时间,频带,功率,设备复杂度噪声均匀化：就是让差错随机化，以便符合编码定理的条件从而得到符合编码定理结果。其基本思想是设法将危害较大的，较为集中的噪声干扰分摊开来，使不可恢复的信息损伤最小。（1）增加码长。（2）卷积。（3）交织。2023/2/518译码算法的已知条件是要求已知：（1）实际接收到的码字序列{r},r=(r1,r2,…..rN)。（2）发送端所采用的编码算法和该算法产生的码集XN,满足（3）信道模型及信道参数。消息组m(N,K)编码器信道最佳/最大似然译码消息还原6.2.2译码方法---最优译码和最大似然译码2023/2/519

译码规则与错误概率信道编码是一个一一对应的变换或函数，称为编码函数f；信道译码也是一个函数，称为译码函数F。编码信道信道编码器f信道信道译码器F

由于

是一一对应变换，其反变换

唯一确定。因此，讨论译码函数时，只考虑从中还原出就可以了。平均差错率Pe与译码规则F有关。2023/2/520两种典型的译码规则两种典型的译码规则：最佳译码规则、极大似然译码规则

1、最佳译码规则：平均差错率最小的译码规则。DMC信道译码F

按“后验概率最大”原则定出，又称最大后验概率译码规则

按“联合概率最大”原则定出，又称最大联合概率译码规则

2023/2/5212、极大似然译码规则

按“转移概率最大”原则定出，称为极大似然译码规则。实际应用中，经常只知道信道的统计特性(转移概率)，而不知道信源的统计特性(输入概率)，这时求不出联合概率和后验概率，因此无法确定最佳译码规则。既然只知道转移概率，就只能按转移概率的某种约束条件制订译码规则。按最大转移概率条件来确定的译码规则，称为极大似然译码规则。2023/2/522极大似然译码规则与最佳译码规则等价的条件极大似然译码规则最佳译码规则结论：信道输入等概时，极大似然译码规则与最佳译码规则等价。证明：

输入等概（1）信道输入是近似等概的：因为信道前级有信源编码器存在。（2）极大似然译码规则近似最佳，可以放心使用。

注：2023/2/523最佳译码，也叫最大后验概率译码(MAP)最大似然译码(MLD)

消息组mi

码字ci

接收码r

估值

消息信道消息还原编码器译码2023/2/524码字的似然函数为了方便计算，可以利用对数运算将乘法运算转化为加法运算。即：2023/2/525BSC信道2023/2/526汉明距离译码是一种硬判决译码。由于BSC信道是对称的，只要发送的码字独立、等概，汉明距离译码也就是最佳译码。最大似然译码等效于最小汉明距离译码。2023/2/5276.3线性分组码6.3.1线性分组码的生成矩阵和校验矩阵6.3.2伴随式与标准阵列译码6.3.3码距,纠错能力,MDC码等6.3.4完备码,循环码,BCH和RS码6.3.5分组码的扩展,缩短和CRC2023/2/5286.3线性分组码(n,k)分组码是把信息流分割成一串前后独立的k比特信息组，再将每组信息元映射成n个码元组成的码字。如下图：m0m1m2……mk-1m0m1m2…..mk-1m0m1m2……mk-1….

C0C1C3………...Cn-1C0C1C3……....Cn-1C0C1C3………....Cn-1K个信息元可以写成矢量(mk-1,….m1,m0)或者矩阵的形式[mk-1,….m1,m0]。同样码字可以表示为(Cn-1,….C1,C0)或者[Cn-1,….C1,C0].(码矢,码字,码组)2023/2/529线性分组码中，必须考虑的问题：（1）码集C能否构成n维n重矢量空间的一个k维n重子空间。（2）如何寻找最佳的码空间。（3）qk个信息元组以怎样的算法一一映射到码空间。码率对于二元分组码(n,k),其码率定义为：RC=k/n对于q元分组码(n,k),其码率定义为：RC=klbq/n

消息m (n,k)码字c

m=(mk-1,…,m1,m0)分组编码器c=(cn-1,…,c1,c0)

qk<qn2023/2/5306.3.1 生成矩阵和校验矩阵

线性分组码的码空间C

是由k

个线性无关的基底

gk-1,，．．．g1，g0

张成的k维n重子空间，所有码字都可写成k个基底的线性组合，即 c=

mk-1

gk-1+…+

m1

g1+m0g02023/2/531生成矩阵

当信息元确定后，码字仅由G矩阵决定，因此我们称这k×n

矩阵G为该(n,k)线性分组码的生成矩阵。如果已知线性分组码的生成矩阵，则任何一个k位信息组对应的码字都可以由mG运算得到。

2023/2/532生成矩阵G(k×n)的特点想要保证(n,k)线性分组码能够构成k维n重子空间，G的k个行矢量gk-1,…,g1,g0必须是线性无关的，只有这样才符合作为基底的条件。由于k个基底即G的k个行矢量线性无关，矩阵G的秩一定等于k。由于基底不是唯一的，所以G也就不是唯一的。不同的基底有可能生成同一码集，但因编码涉及码集和映射两个因素，码集一样而映射方法不同也不能说是同样的码。2023/2/533例如2023/2/534系统形式的生成矩阵(n,k)码的任何生成矩阵都可以通过行运算（不改变码集，只改变映射规则）简化成“系统形式”。G=[Ik

P]=Ik是k×k单位矩阵，P是k×(n-k)矩阵。2023/2/535复习：定义

下面三种变换称为矩阵的初等行变换：1．

互换两行；2．

以数k

乘以某一行；3．

把某一行的k倍加到另一行上。若将定义中的“行”换成“列”，则称之为初等列变换，初等行变换和初等列变换统称为初等变换。2023/2/536系统码前k位由单位矩阵Ik决定，等于把信息组m原封不动搬到码字的前k位；

mG=m[Ik

P]=[mIk

mP]=[mmP]其余的n-k位叫冗余位或一致校验位，是前k个信息位的线性组合。这样生成的（n,k）码叫做系统码。若生成矩阵G不具备系统形式，则生成的码叫做非系统码。系统化不改变码集，只是改变了映射规则。2023/2/537由上面的生成矩阵生成的码字的特点：特点：码字的前面k位就是信息组中的k位，而后面的校验位为信息组的线性组合。2023/2/538空间构成n维n重空间有相互正交的n个基底选择k个基底构成码空间C选择另外的(n-k)个基底构成空间DC和D是对偶的

n维n重空间V

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

空间m

C

H

G2023/2/539校验矩阵将D空间的n-k个基底排列起来可构成一个(n-k)×n矩阵，称为校验矩阵H，也称监督矩阵。用来校验接收到的码字是否是正确的；即：若c为码空间C中的任意码字，则若不满足此等式，则c必定不是码空间C中的码字。2023/2/5402023/2/5412023/2/5422023/2/543校验矩阵G是(n,k)码的生成矩阵，H是它的校验矩阵；H是(n,n-k)对偶码的生成矩阵，它的每一行是对偶码的一个码字。G则是它的校验矩阵。GHT=0，H＝[－

PTIn-k]，二进制时，负号可省略。2023/2/544校验矩阵与生成矩阵的关系如果系统码的生成矩阵为G=[IK|P],则其对应的校验矩阵为H=[-PT|In-k]GHT=0或者HGT=02023/2/545例6-2

某线性分组码，其生成矩阵是

G=求：(1)计算码集，列出信息组与码字的映射关系。(2)将该码系统化处理后，计算系统码码集并列出映射关系。(3)计算系统码的校验矩阵H。若收码r=[100110],检验它是否码字？

(4)根据系统码生成矩阵画出编码器电原理图。

111010①110001②011101③2023/2/546例6-2码集与映射关系信息码字系统码字000000000000000001 011101 001011010 110001 010110011 101100 011101100 111010 100111101 100111 101100110 001011 110001111 010110 111010做初等行变换2023/2/547例6-2二元(6,3)线性分组码编码器m0

m1

m2

输入 输出

c0

c1

c22023/2/548下面是某线性二元码的全部码字：

。⑴求n,k的值；⑵构造这码的生成矩阵G；(找3个线性无关的码字构成G,并化为系统形式)⑶构成这码的一致校验矩阵H。

2023/2/5496.3.2伴随式与标准阵列译码mC=(cn-1,…,c1,c0)R=(rn-1,…,r1,r0)

(n,k)信道定义差错图案EE＝(en－1,…,e1,e0)＝R－C

＝(rn-1－cn-1,…,r1－c1,r0－c0)二进制码中模2加与模2减是等同的，因此有 E=R＋C及 R=C＋E 2023/2/550伴随式S的定义因为CHT=0所以RHT＝(C＋E)HT＝CHT＋EHT=EHT如果收码无误：必有R＝C即E＝0，则EHT=0RHT=0。如果收码有误：即E0，则RHT=EHT0。在HT固定的前提下，RHT仅仅与差错图案E有关，而与发送码C无关。定义伴随式SS=(sn-k-1,…,s1,s0)=RHT=EHT

2023/2/551从物理意义上看，伴随式S并不反映发送的码字是什么，而只是反映信道对码字造成怎样的干扰。差错图案E是n重矢量，共有2n个可能的组合，而伴随式S是(n-k)重矢量，只有2n-k个可能的组合，因此不同的差错图案可能有相同的伴随式。接收端收到R后，因为已知HT，可求出S＝RHT；如果能知道对应的E，则通过C=R＋E而求得C。

RHT=S ?C=R＋ERSEC

只要E正确，译出的码也就是正确的。伴随式S的意义2023/2/552译码过程框图

(R=B)2023/2/553例

一个(5,2)系统线性码的生成矩阵是G=设收码R=(10101)，构造标准阵列译码表，译出发码的估值解：(1)构造标准阵列译码表。分别以信息组m=(00)、(01)、(10)、(11)及已知的G求得4个许用码字为C1=(00000)、C2=(10111)、C3=(01101)、C4=(11010)。求出校验矩阵：

H=[PTI3]=2023/2/554列出方程组：由RHT确定S后，对应的E可以有2k(22=4)个解，究竟取哪一个作为差错图样E的解?最简单明了的处理方法是概率译码，即对所有2k个解的重量(差错图样E中1的个数)进行比较，选择重量最小的作为E的估值。由于E=R+C，E重量最小，就是R和C的汉明距离最小。2023/2/555依据：若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-1>>p2(1-p)n-2>>…>>

pn

出错越少的情况，发生概率越大，E的重量越轻，所以该译码方法实际上体现了最小距离译码准则，即最大似然译码。显然，在进行概率译码时，每接收一个码字就要解一次线性方程，非常复杂麻烦。但如果n－k不太大，我们可以预先把不同校正子S情况下的所有方程组都预先解出来，将各种情况下的最大概率译码输出列成一个标准阵列译码表。这样，在实际译码时就不必解方程，只要查译码表就可以了。2023/2/556伴随式有2n-k＝23＝8种组合，差错图案中代表无差错的有一种，代表一个差错的图案有种，已有6种。代表两个差错的图案有种。只需挑选其中的两个，挑选方法可有若干种，不是唯一的。先将Ej=(00000)、(10000)、(01000)、(00100)、(00010)、(00001)代入上面的线性方程组，解得对应的Sj分别是(000)、(111)、(101)、(100)、(010)、(001)。剩下的伴随式中，(011)所对应的差错图案是2k个即(00011)、(10100)、(01110)、(11001),其中(00011)和(10100)并列重量最轻，任选其中一个如(00011)。同样可得伴随式(110)所对应的最轻差错图案之一是(00110)。例6-3译码表的构成2023/2/557S0=000E0+C0=00000C1=10111C2=01101C3=11010S1=111E1=10000001111110101010S2=101E2=01000111110010110010S3=100E3=00100100110100111110S4=010E4=00010101010111111000S5=001E5=00001101100110011011S6=011E6=00011101000111011001S7=110E7=00110100010101111100例6-3标准阵列译码表2023/2/558例6-3将接收码R＝10101译码可选以下三种方法之一译码：直接搜索码表，查得(10101)所在列的子集头是(10111)，因此译码输出取为(10111)。先求伴随式RHT=(10101)HT=(010)=S4，确定S4所在行，再沿着行对码表作一维搜索找到(10101),最后顺着所在列向上找出码字(10111)。先求出伴随式RHT=(010)=S4并确定S4所对应的陪集首（差错图案）E4=(00010)，再将陪集首与收码相加得到码字C=R+E4=(10101)+(00010)=(10111)。2023/2/559差错图案E的求解(1)

可以通过解线性方程求解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+e0h002023/2/560上述方程组中有n个未知数en－1,…e1,e0

，却只有n-k个方程，可知方程组有多解。在有理数或实数域中，少一个方程就可能导致无限多个解，而在二元域中，少一个方程导致两个解，少两个方程四个解，以此类推，少n-(n-k)=k个方程导致这组未知数有2k组解。概率译码：把所有2k个解的重量(差错图案E中1的个数)作比较，选择其中最轻者作为E的估值。该方法概念上很简单但计算效率不高。差错图案E的求解(2)

2023/2/561标准阵列译码表

在伴随式S的数目是有限的2n-k个，如果n-k不太大，我们可以预先把不同S下的方程组解出来，把各种情况下的最大概率译码输出列成一个码表。这样，在实时译码时就不必再去解方程，而只要象查字典那样查一下码表就可以了。这样构造的表格叫做标准阵列译码表。表中所列码字是接收到的码字R；将没有任何差错时的收码R放在第一行，收码等于发码R=C(CCi,i=0,1,…2k-1),差错图案为全零E0=(0,0…0)，伴随式为全零S0=(0,0…0)。由于有2k个码字，码表有2k列。2023/2/562在第2到第n+1的n行中差错图案的所有重量为1(共n个)。如果(1+n)<2n-k，再在下面行写出全部带有2个差错的图案(共个)。标准阵列译码表的构成

如果总行数(1+n+)仍然小于2n-k，再列出带有3个差错的图案，以此类推，直到放满2n-k行，每行一个Ej,对应一个不同的伴随式Sj。这样，表的行数2n-k正好等于伴随式的数目。2023/2/563S0E0S1E1

SjEj

E0+C0=0+0=0E0+C1=C1E0+Ci=CiE1+C0=E1

E1+CiEj+C0=EjEj+C1Ej+Ci

标准阵列译码表

E1+C1

2023/2/564

在制定标准阵列译码表的过程中，由S决定差错图案E时只有前6行真正体现了最大似然译码准则，而第7、8行的差错图案选择不是唯一的。比如第7行可有(00011)和(10100)两个选择，如果当时选的不是(00011)而是(10100)，那么码表第7行就不是现在这样了。那么在译码时最后的结果也就不一样了。为什么会出现这种情况呢？伴随式的个数2n-k与n、k及纠错能力t

有一定的数量关系。对例6-3的分析2023/2/5656.3.3码距、纠错能力、MDC码及重量谱

N重码矢c=(cn-1,cn-2,…c1,c0)可与N维矢量空间XN中的一个点对应，全体码字所对应的点构成矢量空间里的一个子集发码一定在这个子集里，传输无误时的收码也一定位于该子集当出现差错时，接收的N重矢量:对应到子集外空间某一点

对应到该子集，却对应到该子集的另一点上

2023/2/566td=7dmin=3d=5C1C2C3C4C5码集各码字间的距离是不同的，码距最小者决定码的特性，称之为最小距离dmin这里dmin=3，纠错能力是1，检错能力是2码距2023/2/567定理6.1

任何最小距离dmin的线性分组码，其检错能力为（dmin-1）,纠错能力t为最小距离dmin表明码集中各码字差异的程度，差异越大越容易区分，抗干扰能力就越强，是衡量分组码性能的最重要的指标之一。定理6.2

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

dmin=min{w(Ci)} CiC及Ci

0 纠错能力2023/2/568定理6.3(n,k)线性分组码最小距离等于dmin的充要条件是：校验矩阵H中有（dmin-1)列线性无关。定理6.4(n,k)线性分组码的最小距离必定小于等于

(n-k+1),即

dmin

(n-k+1) 纠错能力

纠错能力

定理6.3（应为）：

对于(n,k)线性分组码：校验矩阵H中的任意t列线性无关而t+1列线性相关，则码的最小距离dmin或码字的最小重量为t+1.反之，若码字的最小重量或码的最小距离为t+1则H的任意t列线性无关而t+1列线性相关。见《信息论基础教程》，李亦农，李梅编著，北京邮电大学出版社。P1592023/2/5692023/2/570例：

H＝(7，4)线性码各列都不相同，任意2列之和不等于0，2列线性无关；任意2列之和一定等于矩阵中某一列，任意3列线性相关。所以该码的最小距离为3，小于n-k+1＝4。纠错能力

2023/2/571(2)为纠正t个错码，要求最小码距(1)为检测e个错码，要求最小码距最小码距与检错能力图示(3)为纠正t个错码，同时检测e个错码，要求最小码距(e>t)2023/2/572（n,k）线性码最小距离dmin的上边界是n-k+1。如果我们设计的（n,k）线性码的dmin达到了n-k+1，就是达到了设计性能的极点。因此，dmin＝n-k+1的码称为极大最小距离码

(MDC–MaximizedminimumDistanceCode)。

(1)二进制码中，除了将一位信息重复n次的（n,1）码外，不存在其它二进制MDC码；

(2)非二进制码中，MDC码是存在的，如RS码（reed-solomon)。MDC码（MaximizedminimumDistanceCode）2