1、中国矿业大学信电学院中国矿业大学信电学院School of Information and Electrical Engineering,CUMT,信息论基础信息论基础 尹洪胜尹洪胜 主讲主讲 中国矿业大学信电学院中国矿业大学信电学院School of Information and Electrical Engineering,CUMT 第六章第六章 有噪信道编码有噪信道编码 n 6.1 信道编码的相关概念信道编码的相关概念n 6.2 有噪信道编码定理有噪信道编码定理n 6.3 纠错编码（自学）纠错编码（自学）n*6.4 几种重要的纠错码（自学）几种重要的纠错码（自学）中国矿业大学信电学院中
2、国矿业大学信电学院School of Information and Electrical Engineering,CUMT 6.1 信道编码的相关概念信道编码的相关概念 信道编码又称为数据传输码或差错控制码，虽然和信源编码一样都是一种编码，但信源编码的作用是压缩冗余度以得到信息的有效表示，提高传输时的信息传输率。而信道编码的作用是提高信息传输时的抗干扰能力以增加信息传输的可靠性。在研究信道编码时，信源编码器和信源译码器分别归于信源和信宿。等效通信系统模型如图6.1所示。下面研究编码信道中的信道编码和译码。图6.1 等效通信系统模型中国矿业大学信电学院中国矿业大学信电学院School of I
3、nformation and Electrical Engineering,CUMT 6.1 信道编码的相关概念信道编码的相关概念有噪信道编码定理由香农在1948年给出，但没有进行严格的数学证明。在1955-1965包括香农本人在内，多人给出多种不同的数学证明。1、编码信道模型1）信源编码中国矿业大学信电学院中国矿业大学信电学院School of Information and Electrical Engineering,CUMT 6.1 信道编码的相关概念信道编码的相关概念2）编码信道模型）编码信道模型（1）信道特征：P（Y|X）描述（2）编码对象：数字序列M，又称信息序列中国矿业大学信电
4、学院中国矿业大学信电学院School of Information and Electrical Engineering,CUMT（3）编码器：按一定的规则给数字序列M增加一些多余的码元，使不具有规律性的信息序列M变换为具有某种规律性的数字序列C，又称为码序列。信息序列M与多余码元之间具有相关性。（4）译码器：利用预知的编码规则译码，能够检验接受的数字序列中是否有错，或者纠正其中的差错，将附加多余码元去掉，输出给信源译码器。6.1 信道编码的相关概念信道编码的相关概念中国矿业大学信电学院中国矿业大学信电学院School of Information and Electrical Enginee
5、ring,CUMT 2、错误概率和译码规则、错误概率和译码规则1）错误概率PE和信道统计特性、译码过程、译码规则有关。例 二元对称信道译码 规则：1.09.0101109.01010EEPP6.1 信道编码的相关概念信道编码的相关概念中国矿业大学信电学院中国矿业大学信电学院School of Information and Electrical Engineering,CUMT 6.1 信道编码的相关概念信道编码的相关概念2)译码规则：设信道输入符号集X=x1,x2,.,xr，输出符号集Y=y1，y2，ys。若对每一个输出符号yj都有一个确定的函数F（yj），使yj对应于唯一的一个输入符号xi
6、，则称这样的函数为译码规则。记为：F（yj）=xi（i=1，2，r；j=1，2，.，s）显然，总的译码规则共有rs种，并不是每一种译码规则都是合理的。中国矿业大学信电学院中国矿业大学信电学院School of Information and Electrical Engineering,CUMT 6.1 信道编码的相关概念信道编码的相关概念例题：设有一信道，信道矩阵4.03.03.05.03.02.02.03.05.0P译码函数为F，可设计为：A：F(y1)=x1,F(y2)=x2,F(y3)=x3B:F(y1)=x1,F(y2)=x3,F(y3)=x2C：F(y1)=x1,F(y2)=x2,
7、F(y3)=x1中国矿业大学信电学院中国矿业大学信电学院School of Information and Electrical Engineering,CUMT 3）错误概率：在确定译码规则F（yj）=xi*下，信道输出端接收到yj，则一定译成xi*。此时如果发送端发送的就是xi*，表明译码正确；否则就是译码错误。那么：正确译码概率：p（F(yj)|yj)=p(xi*|yj)错误译码概率：p（e|yj)=1-p(xi*|yj)平均错误概率：Pe=Ep（e|yj)=p(yj)p（e|yj)经过译码后，平均接受到一个符号所产生错误的大小。6.1 信道编码的相关概念信道编码的相关概念中国矿业大学信
8、电学院中国矿业大学信电学院School of Information and Electrical Engineering,CUMT 4）最佳译码规则（1）总体原则：使平均错误概率Pe最小。（2）最大后验概率准则：选择译码函数F（yj）=x*，使之满足条件P(x*|yj)=p(xi|yj)，对任意i 含义：它是选择这样一种译码函数，对于每一个输出符号yj均译成具有最大后验概率的那个符号x*，此时具有Pe最小值6.1 信道编码的相关概念信道编码的相关概念中国矿业大学信电学院中国矿业大学信电学院School of Information and Electrical Engineering,CUM
9、T 举例：举例：信源信源 ，信道矩阵，信道矩阵414121321xxxPX5.05.00001001|XYPn求最大后验概率准则下的译码方案。解：利用贝叶斯公式：1 收到y1:P(x1|y1)=2/3,P(x2|y1)=1/3,P(x3|y1)=0 所以F(y1)=x12 收到y2:F(y2)=x33 收到y3:F(y3)=x36.1 信道编码的相关概念信道编码的相关概念中国矿业大学信电学院中国矿业大学信电学院School of Information and Electrical Engineering,CUMT（3 3）最大联合概率准则：选择译码函数）最大联合概率准则：选择译码函数F F（
10、y yj j）=x=x*，使之满，使之满足条件足条件P(xP(x*y yj j)=p(x)=p(xi iy yj j)，对任意，对任意i i举例：举例：同上例同上例解：利用乘法公式解：利用乘法公式1 1 收到收到y1:y1:P(x1y1)=1/2,P(x2y1)=1/4,P(x3y1)=0 P(x1y1)=1/2,P(x2y1)=1/4,P(x3y1)=0 所以所以F(y1)=x1F(y1)=x12 2 收到收到y2:F(y2)=x3y2:F(y2)=x33 3 收到收到y3:F(y3)=x3y3:F(y3)=x36.1 信道编码的相关概念信道编码的相关概念中国矿业大学信电学院中国矿业大学信电
11、学院School of Information and Electrical Engineering,CUMT（4 4）最大似然译码准则：选择译码函数）最大似然译码准则：选择译码函数F F（y yj j）=x=x*，使，使之满足条件之满足条件P(yP(yj j|x|x*)=p(y)=p(yj j|x|xi i)，对任，对任i i举例：举例：同上例同上例解：通过观察可得：解：通过观察可得：1 F(y1)=x1 F(y2)=x3 F(y3)=x31 F(y1)=x1 F(y2)=x3 F(y3)=x32 F(y1)=x2 F(y2)=x3 F(y3)=x32 F(y1)=x2 F(y2)=x3 F
12、(y3)=x36.1 信道编码的相关概念信道编码的相关概念中国矿业大学信电学院中国矿业大学信电学院School of Information and Electrical Engineering,CUMT（5）平均错误概率）平均错误概率Pe*,*,111)|()()()()|*(1)()|*(1()|()()|(xXYxXYsjjjjsjjjsjjjexypxpxypypyxpypyxpyepypyepEP6.1 信道编码的相关概念信道编码的相关概念中国矿业大学信电学院中国矿业大学信电学院School of Information and Electrical Engineering,CUMT
13、 1）问题提出）问题提出传输信息的2个主要要求：（1）信息传输率尽可能快（效率）（2）平均错误概率尽可能低（可靠性）例 反复传送提高通信的可靠性。以BSC信道为例，设信源输出符号只有0和1，信道矩阵99.001.001.099.0Pa)信源输出0或1不重复传送：信源传1位，信道传1位此时：R=1bit/符号，Pe=0.016.2 有噪信道编码定理有噪信道编码定理中国矿业大学信电学院中国矿业大学信电学院School of Information and Electrical Engineering,CUMT b)信源输出信源输出0或或1重复传送重复传送3次：信源传次：信源传1位，信道传位，信道传
14、3位位此时：此时：R=1/3 bit/符号，符号，10-4c)进一步增大重传次数进一步增大重传次数n=5 R=1/5 bit/符号，符号，Pe=10-5 n=7 R=1/7 bit/符号，符号，Pe=4 10-7n=9 R=1/9 bit/符号，符号，Pe=10-8n=11 R=1/11 bit/符号，符号，Pe=5 10-106.2 有噪信道编码定理有噪信道编码定理中国矿业大学信电学院中国矿业大学信电学院School of Information and Electrical Engineering,CUMT 2）离散信道的编码定理）离散信道的编码定理 用文字叙述其内涵：只要传信率小于信道容
15、量C，总存在一种信道编码，可以以所要求的任意小的差错概率实现可靠通信-(香农第二香农第二编码定理编码定理)信道编码的逆定理：信道编码的逆定理：信道容量是可靠通信系统传信率的上边界，如果RC就不可能有任何一种编码使差错概率任意小。以上两个定理常被写在一起统称为有扰信道的信道编码定理。3）说明）说明a)该定理只解决了什么是理论极限，并指出在一定范围内与R、C有关，Pe随N增大而降低；b)在任何信道中，信道容量是可进行可靠传输的最大信息传输率；c)推动了编码理论的发展，实际的编码系统可根据该定理加以评价6.2 有噪信道编码定理有噪信道编码定理中国矿业大学信电学院中国矿业大学信电学院School of Information and Electrical Engineering,CUMT 已知信道矩阵设计 如下译码规则A：F(y1)=x1,F(y2)=x2,F(y3)=x3B：F(y1)=x1,F(y2)=x3,F(y3)=x2求信源输入等概时，A、B方案的平均错误概率Pe2/16/13/13/12/16/16/13/12/1|XYP作作 业业
