第六章 有噪信道编码

1、信息论与编码信息论与编码第六章第六章有噪信道编码有噪信道编码 信息论与编码信息论与编码6.1 译码准则 与译码错误概率 有噪声信道编码的主要目的是提高传输可靠性，增加抗干扰能力，因此也称为纠错编码或抗干扰编码。 信源编码之后的码字序列抗干扰能力很脆弱，在信道噪声的影响下容易产生差错，为了提高通信系统的有效性和可靠性，要在信源编码器和信道之间加上一个信道编码器，信息论与编码信息论与编码6.1.1 译码准则的含义译码准则的含义一个例子一个例子影响通信系统可靠性的一个重要问题是译码方式，可以通过一个例子看一下；有一个BSC信道，如图所示。信息论与编码信息论与编码对于这样一个信道，如果采用自然的译码准

2、则，即收0判0，收1判1；这时可以明显看到，当信源先验概率的等概时p(0)=p(1)=1/2；这时收到Y判X的后验概率等于信道转移概率，系统正确的译码概率为1/4，错误译码概率为3/4。但如果采用另一种译码准则，收0判1，收1判0；则系统正确的译码概率为3/4，错误译码概率为1/4，通信的可靠性提高了。译码准则译码准则信息论与编码信息论与编码 这时定义一个收到yj后判定为xi的单值函数，即： F(yj)=xi (i=1,2,n; j=1,2,m)；这个函数称为译码函数。它构成一个译码函数组，这些函数的值组成了译码准则。 对于有n个输入，m个输出的信道来说，可以有nm个不同的译码准则。例如上面例

3、子中有4中译码准则分别为： A:F(0)=0;F(1)=0 B:F(0)=0;F(1)=1 C:F(0)=1;F(1)=0 D:F(0)=1;F(1)=1信息论与编码信息论与编码6.1.2译码错误概率 译码准则确定之后，当接收端收到一个yj后，则按译码准则译成F(yj)=xi，这时如果发送的为xi则为正确译码，如果发送的不是xi则为错误译码。所以接收到yj后正确译码的概率就是接收端收到yj后，推测发送端发出xi的后验概率： Prj=PF(yj)=P(xi/yj) 而错误译码的概率为收到yj后，推测发出除了xi之外其它符号的概率：Pej=Pe/yj=1-PF(yj)=xi/yj 信息论与编码信息

4、论与编码 其中e表示除了xi之外的所有其它信源符号的集合。然后对所有的yj取平均，则平均正确译码概率为：PP yPp yp F yxyrjrjjmjjijjm()() ()/11同样可以得到平均错误译码概率为：Pp yP eyp yP F yxyejjjjijjmjm() /()()/111信息论与编码信息论与编码6.1.3最大后验概率准则最大后验概率准则 由平均错误译码概率的表达式可以看出，错误译码概率与信道输出端随机变量Y的概率分布p(yj)有关，也与译码准则有关。当信道信道转移概率p(yj/xi)确定后，而且信源统计特性p(xi)确定之后，信道输出端的p(yj)也就确定了。因为：p(xi

5、,yj)=p(xi)p(yj/xi); 而p(yj)可以由p(xi,yj)的(i=1,2, n)求和得到。 因此，在这种情况下，平均错误译码概率只与译码准则有关了。通过选择译码准则可以使平均译码概率达到最小值。 当式中的每一项的PF(yj)=xi/yj达到最大值时，平均错误译码概率就可以为最小值。 设信源X的信源空间为：信息论与编码信息论与编码 收到每一个yj(j=1,2,m)后，推测发送为xi(i=1,2,n)的后验概率共有n个，为：p(x1/yj),p(x2/yj),p(xn/yj)。这其中必有一个为最大的，设其为：p(x*/yj)，即有：p(x*/yj)p(xi/yj) (对一切的i)这

6、表明：收到符号yj后就译为输入符号x*，即译码函数选为：F(yj)=a* (j=1,2,m)这种译码准则称为“最大后验概率准则”。信息论与编码信息论与编码 这个表达式平均错误译码概率的最小值，是把每一个yj对应的后验概率排除后再连续求和。 从表达式中可以看到，这个最小值与信源先验概率和信道转移概率有关，特别是信道转移概率，如果除了p(yj/x*)外，其它的项多很小，错误译码概率会减小。信息论与编码信息论与编码6.1.4 最大似然准则最大似然准则 使用最大后验概率译码准则必须已知后验概率，但信道的统计特性描述总是给出信道转移概率，因此利用信道转移概率的译码准则。 由概率中的贝叶斯定理可有：p x

7、yp xp yxp yijijij(/)() (/)()p xyp xp yxp yjjj(/)() (/)()*信息论与编码信息论与编码这样，根据最大后验概率译码准则，如果 p(x*)p(yj/x*)p(xi)p(yj/xi) (i=1,2,n) 就等于：p(x*/yj)p(xi/yj) 则选择译码准则：F(yj)=x* (j=1,2,n) 这样，可以看到当信道输入符号集X的先验概率为等概时p(xi)=1/n，比较上面三个式子，最大后验概率可以用最大信道转移概率来取代。 这时，在X的先验概率为等概时，如果p(yj/x*)是yj相应的n个信道转移概率 p(yj/x1),p(yj/x2),p(y

8、j/xn)中的最大者，则我们就将yj译成x*，这种译码方法称为“最大似然译码准则”。 信息论与编码信息论与编码最大似然译码准则利用了信道转移概率，而不用后验概率，将会更方便。为了减小错误译码概率，主要方法是改变信道转移概率，信息论与编码信息论与编码6.2信道编码定理信道编码定理定理：有噪声信道编码定理（Shannon第二编码定理） 如一个离散有噪声信道有n个输入符号，m个输出符号，信道容量为C。当信道的熵速率RC时，只要码长足够长，总可以找到一种编码方法及译码准则，使信道输出端的平均错误译码概率达到任意小，pe=。当RC时，则不可能找到一种编码方法及译码准则，使信道输出端的平均错误译码概率达到

9、任意小。信息论与编码信息论与编码 编码定理的证明比较复杂，主要参考课本140页 这个定理是一个存在定理，指出错误率趋于0的编码方法是存在的。 定理表明，在错误率趋于0的同时，还可以使R趋于C，这是具有理论指导意义的。信息论与编码信息论与编码引入冗余 一个BSC信道，输入为X=0，1，且为等概分布，信道模型为：信息论与编码信息论与编码 按最大似然译码准则为：F(0)=0; F(1)=1; pe=0.01这里没有采用任何信道编码。 信息论与编码信息论与编码编译码方法将0编为000，1编为111。这时的可用码字为8；分别为：X1=000 X2=001 X3=010 X4=100X5=011 X6=1

10、10 X7=101 X8=111而许用码字为000和111，相当于信道输入为X1=000，X2=111，而信道输出端为：Y1=000；Y2=001；Y3=010；Y4=100Y5=011；Y6=110；Y7=101；Y8=111这时的信道转移矩阵为：信息论与编码信息论与编码这时如果按最大似然法则译码，将为：F(Y1)=F(Y2)=F(Y3)=F(Y4)=X1=000F(Y5)=F(Y6)=F(Y7)=F(Y8)=X2=111错误译码概率为：Pe 310-4可见简单重复码可以将错误译码概率下降两个数量级。这是三次方法；可以看出如果是五次重复码，误码率还要降低 信息论与编码信息论与编码 6.3 信

11、道编码信道编码信道编码又称为差错控制编码，简称为纠错编码，即在信息序列中按一定的规则附加若干监督码元，以便对信息传输（或存储）起检错检错与纠错纠错作用，目的在于提高通信（或存储）的可靠性，减低提高通信（或存储）的可靠性，减低误码率误码率。信息论与编码信息论与编码6.3.1分类信息论与编码信息论与编码几个基本概念码字空间： 如果原始信源空间有M个码字，对其进行q元等长码的信道编码，码长为N，信道码字空间的所有码字为qN个，编码器将在这qN个可用码字中选择M个码字分别代表原始信源中的M个码字，信道编码码字空间的这M个码字称为“许用码字”，而另外的qN-M个码字称为“禁用码字”。为了实现纠错编码，一

12、定有qNM。这M个许用码字也称为一个码组，或称为码字集合。信息论与编码信息论与编码汉明距离：(Hamming distance)在一个码组（码字集合）中，任意两个等长码字之间，如果有d个相对应的码元不同，则称d为这两个码字的汉明距离。 例如：和为码组X中的两个不同码字，X为一个长度为N的二元码组，其中： =a1,a2,aN ai0,1 =b1,b2,bN bi0,1 则与的汉明距离为： d=0表明为全同码，d=N表明为全异码，如果用模2加法的概念，有 模2 加法等同于“异或”运算 信息论与编码信息论与编码 最小码距： dabiiiN( ,) 1在一个码字集合中，任何两个码字之间的汉明距离组成一

13、个元素集合，D(,),这个集合中的最小值称为这个码字集合的最小汉明距离，简称最小码距，记为：dmin。dmin=mind(,) ,X 信息论与编码信息论与编码码字重量（汉明重量）(Hamming weight) 在二元编码的码字集合中，码字中“1”码元的个数称为这个码字的重量。记为：W() 信息论与编码信息论与编码举例: 气象台预报天气 信码 监督元 码字 （偶校验）传输中错一位 晴 00 0 （000）100，010，001 云 01 1 （011） 111，001，010 阴 10 1 （101） 001，111，100 雨 11 0 （110） 010，100，111 许用码字许用码字

14、禁用码组禁用码组 可检一位错，之所以能检错，是因为引入了可检一位错，之所以能检错，是因为引入了冗余（禁冗余（禁用码组）用码组）信息论与编码信息论与编码 例例2 可检查出2位错。附加两个监督元，设只有“晴”、“雨”两种信息: 信码 监督元 码字 传输中错一位 晴 0 00 （000）100，010，001 0 雨 1 11 （111） 011，101，110 1 可纠1位错（000）（111）许用码字许用码字 ,其他为禁用码字其他为禁用码字.在例2中，若编码规则为 晴 011， 雨 000， 则无纠错能力。当发生1位错时：（011）111，001，010（000） 001，100，010则不能纠

15、1位错，但仍能检1位错。信息论与编码信息论与编码纠、检错能力与最小距离纠、检错能力与最小距离d0之间的关系之间的关系 一个码能够检测出min1dtd个错误；只用于纠错，能纠正min12cdtmin1cdttd个错误；用于既纠tc个错，又检td个错信息论与编码信息论与编码6.3.2线性分组码 分组码是一种代数编码，它的基本关系一个码字包括独立的信息元和监督元，其监督元与信息元之间是一种代数关系，如果这种代数关系为线性的则称为线性分组码。分组码的编码器的模型为：信息论与编码信息论与编码 m为编码器的输入，称为信息码元（信息位），它由k位码元组成。C为编码器的输出，称为码字矢量，它由n位码元组成，其

16、中有k位信息元，r=n-k位监督元。 线性分组码：线性分组码：监督元与信息元之间的关系可用一组线性方程组来描述的(n, k)分组码。信息论与编码信息论与编码以(7,4)汉明码为例简单介绍 N=7,k=4,r=3.C=c6,c5,c4,c3,c2,c1,c0；其中c6,c5,c4,c3为信息位，c2,c1,c0为监督位。信息论与编码信息论与编码 由HCT=0可知：监督方程为：c2=c5+c4+c3c1=c6+c4+c3c0=c6+c5+c3其中加号为”模2和”规则.信息论与编码信息论与编码 根据这个方程组可以进行编码。例如信息码元m=1011，则有c2=c5+c4+c3=0+1+1=0c1=c6

17、+c4+c3=1+1+1=1c0=c6+c5+c3=1+0+1=0 则汉明码字C=1011010。 信息论与编码信息论与编码 假如接收码字为R=0100101可以看到：ST=HRT=0这时表明无差错；如果接收码字有一位差错，R=0110101；即错误图样E=0010000；接收码字的第三位错。这时校验子矢量为：信息论与编码信息论与编码 可见这时校验子ST不为0，译码器认为有错，且正好等于H的第三列，表明接收码字的第三位码元错了。这时判断发送码字位0100101，译码正确。信息论与编码信息论与编码 如果接收码字由两位差错，R=0111101；即错误图样E=0011000；接收码字的第三、四位错。这时校验子矢量为：信息论与编码信息论与编码 可见这时，校验子矢量不为0，但是如果这时接收机按原来的译码方法，将认为第7位出错。但如果接收机设计为检错系统，当校验子不为0，就认为有错。因为(7,4)汉明码的最小码距为3 (31+2+1)，其不具备一种方法同时具有纠错检错能力.信息论与编码信息论与编码 注意：纠错码的选用要小心，要根据信道注意：纠错码的选用要小心，要根据信道条件来确定，如果信道较差，而使用的纠条件来确定，如果信道较差，而使用的纠错码能力不够，可能使译码错误反而增加，错码能