第五章有噪信道编码

第五章有噪信道编码5.1译码规则与错误概率为了提高信息传输的可靠性,可在信道的前端和后端分别加入信道编码器和信道译码器,从而组成一个新的信息传输通道——编码信道:信道编码器f信道信道译码器FUXYU^信道编码的目标：提高通信的可靠性。信道编码，就是按照一定的规则给信源编码后的码符号序列增加一些冗余信息，使其变成具有一定数学规律的码符号序列。信道译码，就是按与信道编码器相同的数学规律去掉接收到的码符号序列中的冗余符号。通常来说，增加的冗余符号越多，检错和纠错能力就越强。但是，增加的冗余符号越多，传输效率就越低。译码规则对错误概率的影响例5.1：二进制对称信道

0101译码规则对错误概率的影响译码规则1：信道译码器收到符号“0”——>译为“0”

概率0.1；信道译码器收到符号“1”——>译为“1”

概率0.1；正确译码概率0.1，错误译码概率0101译码规则2：信道译码器收到符号“0”——>译为“1”

概率0.9；信道译码器收到符号“1”——>译为“0”

概率0.9；正确译码概率0.9，错误译码概率定义5.1信道译码函数F是从输出符号集B到输入符号集A的映射:F(bj)=aj*∈A,j=1,2,…,s其含义是:将接收符号bj∈B译为某个输入符号aj*∈A,译码函数又称译码规则。译码规则是由人来制定的,对于同一个信道可以制定出多种译码规则。在信道输出端接收到符号bj时,按照译码规则F(bj)=aj*∈A,译为aj*,若此时输入刚好为aj*,则称为译码正确,否则称为译码错误。bj的译码正确概率是后验概率:上式意味着,在输入等概率分布的条件下,译码错误的概率等于除去信道矩阵中每列对应于F(bj)=a*的元素求和。译码规则例5.2：设一个信道的信道矩阵为，根据此信道矩阵，设计译码规则。解：译码规则A译码规则B对于有r个输入符号，s个输出符号的信道，总共可以设计出种译码规则，到底哪一种译码规则最好？依据什么标准来选择译码规则？问题：译码规则5.2两种典型的译码规则平均差错率Pe与译码规则有关,使Pe达到最小的译码规则称为最佳译码规则。由可以看出,要减少Pe,可增大各个接收符号的译码正确概率P[F(bj)|bj]。译码正确的概率与译码规则有关,如果所有的P[F(bj)|bj]都是最大的,那么Pe最小定义选择译码函数F(bj)=aj*,使之满足条件:则称为最大后验译码规则。该译码规则等价于:它又称为最大联合概率译码规则。使用起来较为方便。最佳译码规则对应的平均差错率最小。但实际应用中常常只知道信道的统计特性,而不知道信源的统计特性,既然只知道转移概率,就只能按转移概率的某种约束条件制定译码规则。我们有:定义选择译码函数F(bj)=aj*,使之满足条件:则称为极大似然译码规则。它不是最佳的,但容易找到。例5.3已知信道矩阵，制定译码规则，求出错误概率．解：根据最大似然译码准则选择译码函数(1)另讨论选择译码规则由最大似然译码准则，仍选第(1)组时要使最小，必须使用最小错误概率准则当输入不是等概率分布译码函数为：当输入不是等概分布时，最大似然译码准则的平均错误概率不是最小的．5.3平均差错率与信道编码平均差错率Pe的大小与所选择的编码规则有关,但即使选择了最佳译码规则,也只能使Pe有限地缩小,难以满足信息传递系统的高可靠性要求。要进一步降低Pe,必须先对信源送来的序列进行可靠性变换——信道编码。5.3.1“简单重复”编码现采用简单重复码,规定信源为“0”(或“1”)时,则重复发送三个“0”(或“`1”),如此构成的信道可以看成是二元对称信道的三次扩展信道。如下图:u1=a1=000000=b1a2=001001=b2a3=010010=b3a4=011011=b4

a5=100100=b5a6=101101=b6a7=110110=b7u2=a8=111111=b8

所对应的信道转移矩阵为:这实际上是一种择多译码方法。相应的译码平均差错率为:信道编码对信息传输速度的影响：信道编码后地信息率为R=H（U）/Nbit/码元如果信源为等概率分布，则R=logM/Nbit/码元其中M代表信源符号的个数。5.3.2对符号串编码在一个二元信道的N次扩展信道中，输入端有2N个符号序列可以作为消息。如果选出其中M个作为实际信号传递，则当M大一些，Pe也就跟着增大，R也增大，反之M取小一些，Pe也降低，而R也要降低。5.4汉明距离定义5.2两个等长符号序列x与y之间的汉明距离,记为D(x,y),是x与y之间对应位置上不同符号的个数。不难证明汉明距离D(x,y)满足如下的距离公理:(1)非负性:D(x,y)≥0,x=yD(x,y)=0(2)对称性:D(x,y)=D(y,x);(3)三角不等式:D(x,z)+D(z,y)≥D(x,y)例：求下面两个码字之间的汉明距离。解：对于二元序列x,x中含有“1”的个数称为x的汉明重量,记为W(x)。若记ON为N个“0”符号组成的字符串,则W(x)=D(x,ON)码是码字的集合,码字则是由码元组成的符号序列,对于等长码,码字之间存在着汉明距离。汉明距离大的码抗干扰能力强。二元对称信道,可以由汉明距离来决定译码规则。设

和

表示两个长度为n的码符号序列，为信道的输入，为信道的输出。和的汉明距离为D。汉明距离码的最小距离与极大似然译码准则对于离散平稳无记忆二元对称信道，有通常情况下，，，D越小，就越大。根据极大似然译码准则，极大似然译码准则就等价于，当接收到一个长为n的码符号序列时，在输入码字集中寻找一个，使最小距离译码准则由此得到二元对称信道的译码规则:由此有:定理5.6对一个二元对称信道,最大后验概率译码准则应为最小汉明距离译码。总结：编码方法：使选取的M个码字中任意两两不同码字的距离尽量大。译码方法：把译成与它最邻近的那个发送码字，即使尽量小。5.5有噪信道编码定理定理5.1（香农第二定理）设有一离散无记忆平稳信道，其信道容量为C，只要待传送的信息传输率R<C，当码长N足够大时，则至少存在一种编码，使译码错误概率任意小。上述定理的含义是:设信道有r个输入符号和s个输出符号,其信道容量为C,由于输入符号序列长度为N,因此可以构成rN个可供选择的输入符号。从rN个符号集中可以找到M≤2N(C－ε)个码字组成一组码。这样编码后,信道的传输率为R=(logM)/N,只要R<C,就可以在有噪信道中以任意小的错误概率传输信息。而且当N足够大时,可使R任意接近C在概率论中有一条大数定律：对于独立同分布的序列{Xn}，其前n项的算术均值随着n的增大逼近Xi的平均值。在信息理论中，也有一个类似的定理：渐进同分割定理，它把随机序列的样本分成两部分，一部分为典型序列，另一部分为非典型序列，随着n的增加非典型序列出现的概率为0，从而在信息理论中，只需要对典型序列进行编码即可。5.5.1联合典型序列

|XN|GX典型序列集合，总概率接近1信源的典型序列和非典型序列由此可见,离散无记忆信源序列可分为两类:GX和GXc,在GX中每个序列出现的概率相等,且总和趋向于1。这类典型序列也称为高概率集，而非典型序列集合称为低概率集。值得注意的是：个别非典型序列出现的概率不一定比典型序列出现的概率小；同样，非典型序列的总概率小但其数目不一定少。现在可以只对少数典型序列进行一一对应的等长编码，这样，码字总数将减少，这个事实对数据压缩有重要意义。定理5.1~5.3表明(1)两个随机变量情况下，信源和联合信源都具有渐进等分割性。随着n的增大，典型序列集出现的概率增大，且趋于等概分布。(2)典型序列是扩展信道输入端高概率出现的序列；典型序列是扩展信道输出端高概率出现的序列；联合典型序列对是那些信道输入和输出间密切关联，经常出现的序列对。定理5.4表明（1）随机选择序列对是统计独立的联合典型序列对的概率约等于。（2）对某一典型序列，与它统计独立的联合典型序列对可能有个。有噪信道编码定理证明方法的基本思路:(1)在N次无记忆扩展信道中讨论,使大数定律有效;(2)随机地选取码字,也就是在XN的符号序列中随机地选取经常出现的高概率序列作为码字;(3)采用极大似然译码准则,也就是将接收序列译成与其距离最近的那个码字;(4)在随机编码的基础上,对所有的码书计算其平均概率,当N充分大时,Pe→0,由此证明至少一种好码存在。5.6Fano不等式和有噪信道编码逆定理Shannon第二定理指出:R<C时,一定存在Pe逼近零的好码,但R>C时如何?引理5.1(Fano不等式)对于离散无记忆信道:{X,PY|X,Y}平均差错率Pe与信道疑义度之间满足下列Fano不等式:

H(X|Y)≤H(Pe,1－Pe)+Pelog(r－1)

H(X|Y)logrH(Pe)+Pelog(r-1)log(r-1)Pe和H（X|Y）的许用区域（r-1）/p

Pe

Fano不等式的曲线图由Fano不等式知：接收到Y后关于X的平均不确定性可分为两部分：一是接收到Y后是否产生Pe错误的不确定性；二是错误Pe发生后到底是那个输入符号发送而造成错误的最大不确定性Pelog（r-1）。定理5.5(信道编码逆定理)设有一离散无记忆平稳信道,信道容量为C,如果信息率R>C,则肯定找不到一种信道编码方法,使得码长N足够大时,平均差错率Pe任意接近于零。Shannon定理的几点认识：（1）纠正了人们认为的提高可靠性必须要降低有效性的传统观念，提出了高效（接近容量）和高可靠性（Pe任意小）编码的存在性；（2）仅指出存在性，并未给出具体编码方法；（3）指出了信息传输率不能大于信道容量是可靠传输的必要条件。5.7线性分组码

线性分组码是最有实用价值的码之一。它的编码方式是将信息序列进行分组,称其为信息组,每个信息组由相继的K位信息数字组成,然后按照一定的编码规则,把信息组成N(N>K)位的二进制数字序列,形成码字。其中非信息位的N－K=r位组成的数字序列称为校验位,每一位校验位是所有信息位的线性组合。信息码字校验码字纠错编码1纠错码的分类2纠错码的基本概念3线性分组码4汉明码5循环码*7卷积码概述香农第二定理证明，当时的码存在。证明过程采用的是随机编码的方法：随机编码所得的码集很大，通过搜索得到好码的方法在实际上很难实现；即时找到了好码，这种码的码字也没有规律，不便于译码。真正实用的信道编码方法还需要通过各种数学工具来构造，使码具有好的结构性以便于译码。近世代数是道编码理论用到的最重要的数学工具，它包括群论、环论、域论、格论、线性代数等许多分支。

广义信道编码包括：调制、成形滤波、扩频、上下变频等。纠错编码是提高传输可靠性的最主要的措施之一。概述纠错编码的基本思路：根据一定的规律在待发送的信息码元中人为的加入一些冗余码元，这些冗余码元与信息码元之间以某种确定的规则相互关联（约束）。在接收端按照既定的规则检验信息码元与监督码元之间的关系。如果传输过程出错，则信息码元与监督码元之间的关系将受到破坏，从而可以发现错误乃至纠正错误。概述(3)按信息码元与监督码元之间的约束方式不同分：分组码：本码组的监督码元仅和本码组的信息元相关。卷积码：本码组的监督码元不仅和本码组的信息元相关，而且与前面码组的信息码元有关。(4)按信息码元在编码后是否保持原形式不变：系统码：信息码元与监督码元在分组内有确定位置，编码后的信息码元保持不变；非系统码：信息位打乱，与编码前不同。1纠错码的分类纠错码按结构分类如下：

纠错码的分类分组码的表示方法：（二元分组码）信息码组由k

个信息码元组成，共有2k

个不同的信息码组；信息位

附加

个校验码元，每个校验码元是该信息码组的某些信息码元模2和；校验位或监督位

编码器输出长度为n的码字；，码字的数目共有2k

；这2k

个码字的集合称为(n,k)

分组码；信息传输率（码率），编码效率

线性分组码5.7.1线性分组码的校验矩阵与生成矩阵(1)校验矩阵由校验方程，得到生成矩阵线性分组码写成矩阵形式:令则有HCT=0或CHT=0式中H称为一致校验矩阵。一旦建立了校验矩阵,校验元与信息元的关系就确定了,码也就随之确定。其中为维矩阵，为维单位矩阵。被称为生成矩阵。对线性分组码，生成矩阵为维矩阵。对于系统码，生成矩阵可以表示为3线性分组码定义对于K位信息位N长的线性分组确,如有下面的关系式存在:C=mG(mod2)其中C为N维向量,m为K维向量,则称矩阵G=[gij]K×N为线性分组码C的生成矩阵。对上述的(7,3)分组线性码,生成矩阵为:把生成矩阵的每一行用一个行向量来表示，则生成矩阵可以表示为令，则线性分组码由于生成矩阵G的每一行都是一个码字，所以G的每行都满足

，则有对于标准形式的校验矩阵和监督矩阵，有(3)校验矩阵和生成矩阵的关系3线性分组码线性分组码的封闭性：线性分组码中任意两个码字之后仍然是该码的码字。证明：设和分别是码中的两个码字，因此有即满足监督方程，所以是码中的一个码字。线性分组码例：3重复码是一个（3,1）线性分组码。其生成矩阵为线性分组码例：（4,3）偶校验码是一个（4,3）线性分组码，其生成矩阵为线性分组码例已知生成矩阵为

求生成的线性分组码及由H生成的线性分组码。线性分组码

线性分组码11111111111100111011100011101110101011001100000101110110111010101011010011001101100010000100111011100101100110100010101011110100010010100110011110001000100110001000100000000000Cm线性分组码上式表明,码字C为信息组m和生成矩阵G各行的的线性组合。特别地,当信息组m只有一个非零元素时,码字为生成矩阵的某一行,即生成矩阵的每一行都是一个码字。如果码字的前(或后)K位为信息组的K个信息元,这样形成的码称为系统码。对于前K位为信息元的系统码,生成矩阵为G=[IK×K,AK×r]如果不是系统码,生成矩阵的前K×K子阵一般不是单位阵。但由矩阵理论,对生成矩阵进行变换后所产生的码与原来的码在性能上等价。故可只研究系统码。系统码与非系统码按照信息码元在编码后是否保持原来的形式不变，可划分为系统码和非系统码。在差错控制编码中，通常信息码元和监督码元在分组内有确定的位置。在系统码中，编码后的信息码元保持原样不变，而非系统码中信息码元则改变了原来的信号形式。系统码的性能大体上与非系统码的相同，但是在某些卷积码中非系统码的性能优于系统码。由于非系统码中的信息位已经改变了原有的信号形式，这对观察和译码都带来麻烦，因此很少应用，而系统码的编码和译码相对比较简单，所以得到广泛的应用。系统化非系统码的G可通过系统化(行初等变换和列置换)转变为系统码的G。若通过行运算和列置换能将两个生成矩阵G互等，则称这两个G等价。等价的两个G生成的两个(n,k)线性码也是等价的。任何一个(n,k)线性分组码都等价于一个系统码。例设有下列两个生成矩阵上表所示的码，虽然用了不同形式的生成矩阵，但都属于同一个(n，k)码的码字空间，因此它们的检错和纠错能力是一样的。理解：系统化不改变码集，只是改变了映射规则。系统码与非系统码的主要区别在于选择了不同的基底向量、即：生成矩阵。例二元（7，3）码的生成矩阵为：则由G2生成的（7，3）码如下表：与上例生成的码（系统码）相同信息组000001010011100101110111码字00000001110100101001101001111001110011101000111011101001分组码的码率在二元无记忆对称信道中，(N,K)分组码的许用码字数为M=2K,也就是信道输入的消息数为M。在研究信道编码时，信道输入的信息流可以认为已经是去除新源剩余度后满足无记忆等概率的信息流，此时信道的传输率（又称为码率）为：R=logM/N=log2K/N=K/N5.7.2汉明距离和码的纠、检错能力由生成矩阵所产生的码字在信道传输过程中,由于干扰的存在,使得一些码元发生错误,接收端通过编码规则进行译码,如能发现错误,则称为检错;如能纠正错误,称为纠错。码能纠、检错误码元的个数称为该码的纠、检错能力。定理5.7线性分组码的最小距离等于非零码字的最小重量。证明由线性分组码的封闭性可得定理5.8(汉明距离的纠、检错能力)对于(N,K)分组线性码,设dmin为最小汉明距离,则有下列性质:(1)这组码具有纠正u个错误的充分必要条件是:dmin≥2u+1(2)这组码具有检测出l个错误的充分必要条件是:dmin≥l+1(3)这组码具有纠正t个错误,同时发现l(l>u)个错误的充分必要条件是:dmin≥u+l+1关于码的最小距离与纠、检错能力的关系有以下结论：对于（n，k）线性分组码，设为最小汉明距离则（１）这