信息与编码理论第六章

第六章有噪信道编码,6.1译码规则与错误概率,1.信道编码模型,图6-1信道编码模型,2.译码规则,例6-1在二元对称信道中，单个符号的错误传递概率是p,正确传递概率为1-p，信道输入符号概率分布:,信道输出概率分布,现在进行译码过程，首先设立两个译码规则：（1）0译成0,1译成1.则译码错误概率为：,平均译码错误概率,（2）0译成1,1译成0.则译码错误概率为：,定义6.1设信道输入符号集合X=x1,x2,xr，输出符号集合Y=y1,y2,ys，若对每一个输出符号yj，都有一个确定的函数F(yj)，使yj对应于唯一的一个输入符号xi，则F(yj)为译码规则，记为对于r个输入，s个输出的信道,译码规则共有rs种。,(6.1.1),平均译码错误概率,因此，译码错误概率与信道统计特性和译码规则有关。,例6-22元信道译码规则可设置如下：,图6-22元信道模型,例6-3一离散单符号信道信道矩阵如下：,可设计译码规则A和B:,3.平均译码错误概率在确定译码规则F(yj)后，信道输出端在收到符号yj，则一定译成xi。如果发送端发送的确实就是xi，就是正确译码；反之，若发送端发送的不是xi，错误译码。译码正确概率为,译码错误概率为,平均译码错误概率为,进一步写成,(6.1.2),(6.1.3),(6.1.4),(6.1.5),或,平均译码错误概率PE表示经过译码后平均接收到一个符号所产生的错误大小。若输入等概，则pF(yj)=1/r,则,例6-4求例6-2中4种译码规则的平均译码错误概率。,解：设信道输入信源概率为：,信道矩阵为：,(6.1.6),(6.1.7),4.两种典型译码规则（1）最佳译码规则,联合概率矩阵为：,平均译码错误概率为：,其他3种译码规则的平均译码错误概率为：,平均译码错误概率PE与译码规则有关，使PE最小的译码规则称为最佳译码规则。,(6.1.8),最佳译码规则也称为最大后验概率译码规则。也有：,又称最大联合概率译码规则。,例6-5求例6-2中2元信道的最佳译码规则。,解：联合概率矩阵为：,所以，译码规则选为,平均译码错误概率最小，为PE=0.14.,（2）最大似然译码规则,(6.1.9),输入等概时，最佳译码规则与最大似然译码规则等价。,例6-6求例6-1中信道按最大似然译码规则的平均译码错误概率。,解：按最大似然译码规则设置译码规则为：,即：,（1）若输入等概，则,或,（2）若输入非等概，设输入信号符号概率分布为：,若采用最佳译码规则，我们有：,j=1,j=2,j=3,仍然采用上面的最大似然译码规则，则PE为,平均译码错误概率PE与译码规则有关。由于信道噪声或干扰，导致输出码元发生传输错误，在接收到输出符号后，对于发送的是什么符号存在不确定性，可见PE与信道疑义度是有一定关系，有下列不等式：,按照最佳译码规则设置的译码规则为：,平均译码错误概率PE为：,5.费诺不等式,其中，H(PE)是错误概率PE的熵，表示产生错误概率PE的不确定性。,费诺不等式表明，接收到Y后关于X的平均不确定性分为两部分：第一部分H(PE)指接收到Y后是否产生错误的不确定性。第二部分PElog(r-1)是当错误PE发生后，判断是哪个输入符号造成错误的最大不确定性，是(r-1)个符号不确定性的最大值与PE的乘积。,图6-3费诺不等式曲线图,(6.1.10),1.简单重复编码,6.2信道编码的选取规则,例：二元对称信道为：,则,若设置译码规则为：,两个信源符号重新编码如下：0000,1111重新编码的码字X3送入信道，信道矩阵变为：,依据最大似然规则，设置译码规则为：,可见，3次重复编码能够纠正一位码元传输错误，译错的可能性减少，平均译码错误概率降低。若重复编码5、7、9次，则,在信道矩阵中表现如下：,则,则PE1=210-2,PE2=2.2810-2,可见，n很大时，PE很小是可能的。但信息传输率会降低，定义编码后信道的信息传输率（码率）为：,其中，M为输入消息（许用码字）的个数。,重复编码可使PE降低，但信息传输率也跟着下降。,解决上述困境的一种可能方案为：增加信源符号数目M,精选码字。如M=4,编成二元3次扩展码，如下：（1）000,011,101,110（2）000,001,010,100信道矩阵为48.,可见，错误概率与编码方法有很多关系。,（5，2）线性码中，信源符号M=2，码长n=5，信息传输率R=logM/n=log4/5=2/5设输入符号为X=xi1xi2,输出码字为C=(ci1ci2ci3ci4ci5),信道编码器按如下规律产生码字,2020/5/1,（5,2）线性码,当信源符号取00,01,10,11时，码字为00000,01101,10111,11010.采用最大似然译码准则，有00000,00001,00010,00100,01000,10000,10001,00011译成00000。,平均译码错误概率为,信息率虽然有所降低，但PE降低的更多，编码方式是可取的。,2.码的最小距离,（1）定义：设两个n长序列i=(i1i2in)和j=(j1j1jn)，i和j之间的距离指i和j对应位置上不同码元的个数。用D(i,j)表示，通常称为汉明距离。对于二元码，有,2020/5/1,（2）最小码距dmin码组C中，任意两个码字之间汉明距离的最小值。,例：判断两组码组的最小码距。（1）000,011,101,110；（2）000，001,010,100。,因此，愈使转移概率最大，则使汉明距离最小，因此极大似然译码规则可等价为最小汉明距离译码规则。在二元对称无记忆信道中，平均译码错误概率PE也可以用汉明距离表示，有,2020/5/1,（3）极大似然译码准则与最小码距设信道发送端发送的码字i=(i1i2in)，输出端输出的序列为j=(j1j2jn)。设i和j的汉明距离为D(i,j).,有,3纠错编码,信道编码的目的是提高信号传输的可靠性，纠错编码是提高传输可靠性的最主要措施之一。（1）信道分类由于信道中干扰和噪声的存在，使得经信道传输后的接收码字与原来的发送码字存在着差异，也就是差错。一般信道中噪声干扰越大，码字产生错误的概率也越大。信道中的干扰和噪声一般分为两种形式：一是随机噪声，主要来源于设备的热噪声和散弹噪声以及传播媒介的热噪声，是通信系统中的主要噪声。二是脉冲干扰和信道衰落，它的特点是突发出现，主要来源于雷电、通电开关、负荷突变或设备故障等。,根据信道中干扰和噪声的形式，可将信道分为3类：随机信道、突发信道和混合信道。特点是各码元是否发生错误是随机的，且相互独立，因而不会出现成片的错误只产生随机错误的信道称为随机信道。脉冲干扰和信道衰落产生的错误是成串出现的，错误间具有相关性，这类错误称为突发错误。产生突发错误的信道称为突发信道。有些实际信道既有随机错误又有突发错误，称为混合信道。根据不同的信道类型设计的信道编码分为纠随机错误码、纠突发错误码和纠混合错误码。4.差错控制类型在通信系统中，纠检错的工作方式有反馈重传纠错、前向纠错和混合纠错等。,（1）反馈重传纠错图6-3即反馈重传纠错模型发送端发出的是能够发现错误的检错码，接收端对接收到的码字进行译码，发现有错时，通过反馈系统向发送端请求重传已发送的全部或部分码字，直到接收端认为没有错误为止，我国的电报系统就是一种反馈重传纠错系统。,图6-3反馈重传纠错,（2）前向纠错图6-4即前向纠错模型前向纠错也称为自动纠错。发送端发出的是具有纠错能力的纠错码，接收端根据编码规则进行解码。当误码个数在码的纠错能力范围之内时，译码器可以自动纠正错误。,图6-4前向纠错,（3）混合纠错对发送端进行适当的编码，当错误不严重时，在码的纠错能力之内，采用自动纠错，当产生的差错超出码的纠错能力时，则通过反馈系统向发送端要求重发，这种同时具有反馈重传纠错和自动纠错工作方式的纠错称为混合纠错。检错码和纠错码在不加区别时统称为纠错码。5.纠错码分类,25,(1)从功能角度讲,差错码分为：检错码和纠错码检错码纠错码纠错码与检错码在理论上没有本质区别,只是应用场合不同,而侧重的性能参数也不同。,(2)按照对信息序列的处理方法,有分组码和卷积码分组码：将k个信息码元分成一组,由这k个码元按照一定规则产生r个监督码元,组成长度n=k+r的码字,卷积码：先将信息序列分组,不同的是编解码运算不仅与本组信息有关,而且还与前面若干分组有关。,26,(3)按照码字码元与信息码元的关系,分为线性码：所有码元均是信息码元的线性组合,编码器不带反馈回路。非线性码：码元并不都是信息元的线性组合,可能还与前面已编的码元有关,编码器可能含反馈回路。由于非线性码的分析比较困难,早期实用的纠错码多为线性码,但当今发现的很多好码恰恰是非线性码。,(4)按照适用的差错类型,分成:纠随机差错码:用于随机差错信道,其纠错能力用码组内允许的独立差错的个数来衡量。纠突发差错码:针对突发差错而设计,其纠错能力主要用可纠突发差错的最大长度来衡量,27,6.检错与纠错原理,例：天气两种状态：0:晴,1:雨若10,01。收端无法发现错误,00晴,10,01,11,00,11雨,能发现一个错误,禁用码组,插入1位监督码元后具有检出1位出错码元的能力,但不能予以纠正。,28,000晴,010,001,111,000,111雨,晴,在只有1位出错码元的情况下,可以判决哪位是错码并予以纠正,可以检出2位或2位以下的出错码元。,100,011,101,110,雨,29,最大似然译码：将接收到的码字译码为与之差别最小的许用码字,并且认为这个许用码字就是所对应的发送码字,从而在码字纠错能力内实现自动纠错。纠错编码之所以具有检错、纠错能力,是因为在信息码元之外加入了监督码元。监督码元不载信息,只用来监督信息码元传输中有无差错。纠错编码提高的可靠性,是以牺牲信道利用率作为代价。监督码元引入越多,检错和纠错能力越强,但信道传输效率下降也越多。,具体而言，传输冗余比特必然要动用冗余的资源。时间：比如一个比特重复发几次,或一段消息重复发几遍,或根据收端的反馈重发受损信息组。,30,频带：插入冗余比特后传输效率下降,若要保持有用信息的速率不变,方法之一是增大符号传递速率(比特率),结果就占用了更大的带宽。功率：采用多进制符号,用8进制ASK符号代替4进制ASK符号来传送2比特信息,可腾出位置另传1冗余比特。8进制ASK符号的平均功率肯定比4进制时要大,这就是动用冗余的功率资源来传输冗余比特。设备复杂度：加大码长,采用网格编码调制,是在功率、带宽受限信道中实施纠错编码的有效方法,代价是算法复杂度的提高,需动用设备资源。,31,7.码距与检错、纠错能力,纠错编码的检纠错能力,取决于码组的码距。码距越大,检错纠错能力越强。,若纠错码的最小距离为dmin，其与纠错能力关系如下：可以检测出任意小于等于l=dmin1个差错可以纠正任意小于等于个差错,可以检测出任意小于等于l同时纠正小于等于t个差错，其中l、t满足：l+tdmin1tl,第32页,2020/5/1,1.线性分组码的基本概率,（1）线性分组码的编码：编码过程分为两步：把信息序列按一定长度分成含有k位信息码组。编码器按照预定的编码规则，把信息码组变换成n重（nk）码字，其中(nk)个监督码元是由信息码元的通过编码规则产生的。（2）线性分组码的码字数目：信息码组长k位，有2k个不同的信息码组，有2k个码字与它们一一对应。（3）码矢：一个n长的码字可以用矢量来表示：C=(cn1,cn2,c1,c0)（4）编码效率（编码速率/码率/传信率）：R=k/n,6.3线性分组码,第33页,2020/5/1,例6-1：设计n=7,k=3的(7,3)二元线性分组码。假设码字为：(c6,c5,c4,c3,c2,c1,c0)，其中c6,c5,c4为信息码元，c3,c2,c1,c0为监督码元，编码规则如下，写出（7,3）的码字。,解：设信息码元矢量为,信息码元矢量共有2k个排列组合：000,001,010,111.,若m=(110),m2=1,m1=1,m0=0,则根据编码规则，输出码字码元为：c6=m2=1;c5=m1=1;c4=m0=0;c3=1+0=1;c2=1+1+0=0;c1=1+1=0;c0=1+0=1,当信息码元矢量m=(110)时,输出码字为：c=(1101001)。,2.线性分组码的编码,上例可以用矩阵表示。如码字各码元,所以,令,则,G称为（7,3）码的生成矩阵。,式（6.2.1）也可写成,由此看出，生成矩阵G可由3个线性无关的行矢量排列组成。对于(n,k)线性分组码，生成矩阵的一般形式为：,系统码生成矩阵,(6.2.1),(6.2.2),(6.2.3),第36页,2020/5/1,3.一致校验矩阵（监督矩阵）上例中，对编码规则改写为：,则：HCT=0T或CHT=0CT、HT、0T分别表示C、H、0的转置矩阵。,(6.2.4),一致校验矩阵的一般形式为：,由于生成矩阵G中的每一行都是许用码字，因此有：,对于例6-1中的（7,3）系统码，校验矩阵为,(6.2.5),(6.2.6),上例中，若信道输出端接收到一个序列R=(1101000),试判断该接收序列是否是码字：解：,因此：,或,结果不满足一致校验方程，接收序列R不是许用码字。,例6-4已知(5,2)系统线性码的生成矩阵，设接收码R=(11011)，写出该码的一致校验矩阵，并判断是否是有无传错。,(6.2.6),译码就是要从接收序列R中求出差错图案E，从而得到码字的估计值C=RE。,例如，R=(110000)，而C=(100001)，则E=R-C=RC=(010001)，可知接收序列R中的第1位和第5位出现了错误。即第1和5传输出现错误。,（2）伴随式,（1）差错图案设发送码字C=(cn1,cn2,c1,c0)，信道输出端接收序列为R=(rn1,rn2,r1,r0),码字C和接收序列R之间的差别定义为：,4.线性分组码译码,(6.2.7),(6.2.8),对于一致检验矩阵（监督矩阵）可写成：,设(n,k)码的一致校验矩阵为H,R是发送码字为C时的接收序列，则称S=RHT=EHT为接收序列R的伴随式(或校正子）显然，若错误图样E=0，则S=0，那么接受序列R就是发送的码字C；若E0，则S0，那么C在传输过程中有出错，如果从S得到E，则可从C=R+E恢复发送的码字。,(6.2.9),对于上例的（7,3）系统码，伴随式可写为：,可见，伴随式S是一致校验矩阵H的线性组合，如果错误图样中有一些分量不为0，则在S中正好就是E中不为0的那几列组合而成。由于是r维的列向量，所以伴随式S也是一个r维向量。,所以，伴随式可写成：,(6.2.10),例：对于上例中的（7,3）码，若接收序列分别为R1=(1010011),R2=(1110011),R3=(0011011),试计算各自伴随式，并判断各自的第几个码元传错。解：,（1）标准阵列译码表构造方法标准阵列译码表是一个2nk行、2k列的阵列。先将2k个码字排成一行，作为标准阵列的第一行，并将全0码字C1=(000)放在最左面的位置上；然后在剩下的(2n1)个n重中选取一个码重为1的n重E2放在全0码字C1下面，再将E2分别和其余各个码字相加，放在对应码字下面构成阵列第2到n+1行。再次选取重量为2的n重E3，放在E2下面，并将E3分别与各码字相加，结果放入第n+2行到n+1+行。，继续重复做下去，直到2（n-k)行全部用完。,5.标准阵列译码表,在标准阵列中，一个陪集的所有2k个n重码字有相同的伴随式，不同的陪集伴随式互不相同。每一列包含2nk个元素，最上面的一个是码字，其它元素是陪集首和该码字之和。,例6.5已知(5,2)系统线性码的生成矩阵，设接收码R=(11011)，请先构造该码的标准阵列译码表，然后译出发送码的估计码字。,若发送码字是Cj，信道干扰的错误图样是陪集首，接收序列必在Dj中，此时接收序列R通过倒查可正确译为发送码字Cj。当且仅当错误图样为陪集首时，译码才是正确的。这2nk个陪集首称为可纠正的错误图样。,解：分别以信息组m=(00),(01),(10),(11)及已知的G代入式码字生成公式，求得4个许用码字为C1=(00000),C2=(10111),),C3=(01101),C4=(11010)。,标准阵列译码表构造完成后，通过查表，可直接进行译码。例如，若接收码R=(11011)，(1)直接对码表作行、列两维搜索，找到(11011)，它所在列的子集首是(11010)，因此译码输出为(11010)。,对于(n,k)线性分组码，有2(n-k)伴随式，若能够纠正t个随机错误，应满足：,6.汉明码,称为汉明限。,能够纠正一个错误的（n,k）线性分组码，称为汉明码。,汉明码有：（7,4），（15,11）等。,编码效率为：,(6.2.11),(6.2.12),(6.2.13),6.3有噪信道编码定理,1.有噪信道编码定理定理6.1(有噪信道编码定理)设离散无记忆信道，其信道容量为C。当信道信息传输率Rchannel时，只要码长N足够长，总可以在输入XN符号集中找到M(=2NRchannel)个码字组成一组码(2NRchannel,N)和相应的译码规则，道使译码的平均错误概率任意小。这个定理称为有噪信道编码定理，又称为香农第二定理。定理6.2(有噪信道编码逆定理)设离散无记忆信道，其