第6章 信道编码定理.ppt

1、1,第六章 信道编码定理,错误概率 译码准则 信道编码定理,2,噪声信道的编码问题,在二进制数字通信系统中，编码器的编码过程分为两步： 信源编码：把信源的消息数据序列编成二进制数字构成的码序列； 信道编码：把二进制数据序列编成具有纠检错能力的二进制序列。 由于信源编码在构造上并未考虑抗干扰，如果把信源编码器的输出直接接入信道，由于信道中存在噪声干扰，将引起误码，降低通信可靠性。 因此提出了以提高通信可靠性为主要目的的信道编码，它对信源编码器输出的最佳码再进行一次编码，以提高其抗干扰能力。 信道编码研究消息通过信道传输时如何选择编码方案以减少差错。,3,信道编译码的理论基础,信道的特征是由信道传

2、递概率p(Y|X)来描述的。由p(Y|X)可以算出信道容量C，只要在信道中实际传送的信息率RC，在接收端就能够无差错地译出发端所输送的信息。 信道输入符号序列X代表M种信源符号，它也可以是已经经过信源编码的M种码字，从信道输出符号序列Y能正确地译出这M种码字， 问题：如何用X组成这M种码字，才能达到无差错地传送？这需要信道编码，它的实质上是希望信源与信道特性相匹配。,4,信道编译码的基本思想,信道编码的编码对象是信源编码器输出的数字序列M，又称为信息序列。通常是由二元符号0，1构成的序列，而且符号0和1是独立等概的。 信道编码按一定的规则给数字序列M增加一些多余的码元，使不具有规律性的信息序列

3、M变换为具有某种规律性的数字序列C，即码序列。码序列中信息序列的诸码元与多余码元之间存在相关性。 在接收端，信道译码器利用这种预知的编码规则来译码，或者检错(检验接收到的数字序列R中是否有错)，或者纠错(纠正其中的差错)。 信道编码的基本思想是就是根据相关性来检测和纠正传输过程中产生的差错。,5,通信的可靠性问题,通信的可靠性问题，即消息通过信道传输时如何选择编码方案以减少差错。 首先，通信的可靠性显然与信道的统计特性有关，因为杂噪干扰是造成错误的主要因素。 其次，编码方法和译码方法也将影响信息传输的可靠性。 在有噪信道中传输信息发生错误时，错误概率和信道统计特性、编译码过程以及译码规则有关。

4、,6,编码信道的概念,信道编码研究的对象是编码信道，如上图所示，它是由信道编码器、信道译码器和实际信道一起形成的一个新的信道。 编码信道：研究信道纠错编码和译码的一种模型。它可以是： 无线通信中的如发射机、天线、自由空间、接收机等全体； 有线通信中的如调制解调器、电缆等全体； 互联网的多个路由器、节点、电缆、低层协议等全体； 计算机的存储器如磁盘等的全体； 。,7,错误概率和译码规则,考虑一个二元对称信道，单符号错误传递概率是pb=0.9，其输入符号为等概率分布。 如果规定在信道输出端接收到符号0时，译码器把它译成0；接收到1时译成1，则译码错误概率为0.9。 反之，如果规定在接收到符号0时译

5、成1；接收到1时译成0，则译码错误概率为0.1。 可见，错误概率既与信道统计特性有关，也与译码规则有关。,8,无记忆二进制对称信道（BSC）,假定数字通信系统的编码信道是无记忆二进制对称信道： 二进制信道是指码字和接收向量均由二元序列表示的信道，即c=(c0,c1,cn-1) ci0,1 、 r=(r0,r1, ,rn-1) ri0,1。 二进制信道可用转移概率p(r/c)描述输入输出关系； 满足以下公式的二进制信道称为无记忆二进制信道： p(r/c)= p( ri / ci ) i=0n-1 满足以下对称特性的无记忆二进制信道称为无记忆二进制对称信道，简称BSC： p(0/1)= p(1/0

6、)= pb,接收向量r ri0,1,码字 c ci0,1,二进制信道 p(r/c),信源编码,信源译码,消息 m,消息 m,9,BSC的信道模型,只要噪声是白噪声，大多数二进制传输信道的模型可等效为一个BSC，其信道模型如下图所示。,二进制 无记忆,BSC编码信道,10,可将BSC的输入输出关系 等效为代数关系： r=c+e mod2 e=(e0,e1,en-1) 差错图案：随机序列(ei) 随机错误：ei =1, i 位 突发错误：第 i 至第 j 位之间有很多错误。,BSC的输入输出关系描述,11,译码规则,定义,12,译码规则-例,设有一离散无记忆信道，其信道矩阵为 则以下A和B是两个不

7、同的译码规则： 由于n=3，m=3，m个输出符号中的每一个都可以译成 n个输入符号中的任何一个，故按此信道矩阵总共可设计出33=27种译码规则。 在所有的译码规则中，不是每一种译码规则都是合理的，因此要讨论选择译码规则的准则，其原则是使译码平均错误概率最小。,13,1、译码平均错误概率,若译码规则为 ，则信道输出端接收到符号yj时，一定译成 xi。 如果发送端发的就是xi，这就是正确译码，因此条件正确概率为 反之，如果发送端发的是 ，则是错误译码，因此条件错误概率为 经过译码后，平均到一个符号所产生的错误的大小，就是译码平均错误概率,14,译码平均错误概率的其它表达式,译码平均错误概率还可以写

8、成 若用条件概率表示，则可以写成 平均正确概率则可以写成,15,等概率分布时的译码平均错误概率,若输入为等概率分布，则 上式意味着，在输入为等概率分布的条件下，译码错误概率可用信道矩阵中元素的求和来计算：除去信道矩阵中每列对应于 的那一项后，计算其余元素之和。,16,2、译码规则,选择译码规则的总原则是使译码平均错误概率pE最小。 由于译码平均错误概率 为非负项之和，欲使译码平均错误概率最小，那么应使每一项 为最小。 由于 p(yj) 与译码规则无关，故欲使译码平均错误概率最小，即为使 最小，或者使为最大，于是引出最大后验概率准则。,17,最大后验概率译码准则-定义,18,最大后验概率准则-例

9、题,19,最大后验概率准则-例题（续）,20,后验概率与最大似然-译码准则,从最大后验概率译码规则可以很容易推出极大似然译码规则。,21,最大似然译码准则-定义,当信道输入符号为等概分布时，应用极大似然译码准则是很方便的，即将yj译成信道矩阵中第j列最大的那个元素。式中的条件概率即为信道矩阵中的元素。,22,最大似然译码准则-例题,当输入为等概率分布时，译码规则A就是依据最大似然译码准则而得的。,23,最大似然译码准则-例题（续）,输入为等概率分布时，两种译码规则所对应的平均错误概率分别为 可见 在输入为等概率分布时，最大似然译码准则是最优的。,24,费诺不等式,译码时发生错误是由信道中噪声引

10、起，因此平均错误概率与信道疑义度H(X|Y)有关，其关系由费诺不等式表示。 引理6.1.1 译码平均错误概率与信道疑义度H(X|Y)间满足以下关系 这个不等式称为费诺不等式。,25,费诺不等式的物理意义,虽然PE与译码规则有关，但不管采用什么译码规则费诺不等式均成立。 费诺不等式表示，当作了一次译码判决后所保留的关于信元的不确定性可以分成两部分： H(PE)和PE log(n-1)。 第二部分是当判决是错误的且错误概率为PE时，到底是n-1个输入符号中哪一个引起错误的最大不确定性，它是(n-1)个符号不确定性的最大值log(n-1)与PE的乘积。 第一部分是接收到Y后，判决是否发生错误的不确定

11、性H(PE)，其中H(PE )是译码平均错误概率PE的熵，表示产生错误概率PE的不确定性。,26,费诺不等式的几何含义,信道疑义度 是信源熵H(X)超过平均互信息I(X;Y)的部分。 若以H(X|Y)为纵坐标，PE为横坐标，则函数H(PE)+ PE log(n-1)随PE变化的曲线如图所示。 由图可知，当信源、信道给定时，信道疑义度H(X|Y)就给定了译码平均错误概率PE的下限。,27,小结,本节围绕信道编码的主要性能参数译码平均错误概率进行讨论： 给出了译码平均错误概率的定义与公式。 依据错误概率最小化的原则，给出了两种译码准则： 最大后验概率译码准则是最佳准则，总能使错误概率最小化。 最大

12、似然译码准则是次最佳准则，在输入等概率分布时与最大后验概率准则等效。 应用最大似然译码准则时，只需根据信道矩阵进行判断，应用很方便，因而成为最常用的准则。 给出了错误概率与信道疑义度的关系费诺不等式。,28,错误概率与编码方法,前面讨论了平均错误概率与译码规则的关系。选择最佳译码规则只能使错误概率有限地减小，无法使其任意地小。 要想进一步减小错误概率，必须优选信道编码方法。 现在讨论不同的编码方法对译码平均错误概率和信息传输率的影响。,29,错误概率与编码方法,1 简单重复编码 2 消息符号个数 3（5, 2）线性码 4 汉明距离,30,1 简单重复编码与错误概率,本节举例说明在采用简单重复编

13、码时重复次数对译码平均错误概率和信息传输率的影响。 设有二元对称信道如图 其信道矩阵为 未编码时： 选择最佳译码规则为 在输入为等概率分布时，译码平均错误概率为,31,简单重复编码举例（续1）,采用简单重复编码，规定信源符号为0（或1）时重复发送三个0（或1）。输入符号和输出符号的关系如图：,32,简单重复编码举例（续2）,33,简单重复编码举例（续3）,在简单重复编码时，采用“择多译码”的译码规则等效于最大似然译码准则。 择多译码是根据接收序列中“0”和“1”的个数，如果是“0”多，则译码器就判决为“0” ，如果是“1”多，就判决为“1”。 采用简单重复编码方法，增大重复次数n，则会降低译码

14、平均错误概率，但信息传输率也要减小。 信息传输率表示平均每个码符号所携带的信息量，其中M为消息符号个数。,34,简单重复编码举例（续4）,重复次数对信息传输率和错误概率的影响如下 能否找到一种编码方法，使平均错误概率充分小，而信息传输率R又可以保持在一定水平上，这就是香农第二定理所要回答的问题。,35,错误概率与编码方法,1 简单重复编码 2 消息符号个数 3（5, 2）线性码 4 汉明距离,36,2 消息符号个数M,本节讨论消息符号个数M对错误概率和信息传输率的影响。 在一个二元信道的n次无记忆扩展信道中，输入端共有2n个符号序列可能作为消息符号，现仅选其中M个作为消息符号传递，见图。,37

15、,消息符号个数M的影响（续1）,设n=3，那么可供选择的消息符号数共有8个，发送端只选择其中M个作为输入消息符号传递，而接收端会接收到所有8个输出符号，然后从中译出M个消息符号。 以下假设输入为等概率分布p(x)=1/M，信道错误传递概率p=0.01，采用简单重复编码和最大似然译码准则。当n=3，M=2时，有：,38,消息符号个数M的影响（续2）,当n=3，M=4时，有 比特/码符号 M=4有不同的选取方法，代表不同的编码方法，其平均错误概率是不同的。,39,结论：,输入信息符号个数M增大时，平均错误概率显然是增大了，但信息传输率也增大了。反之，亦然。 输入信息符号个数M不变时，即信息传输率不

16、变时，不同的编码方法，其平均错误概率是不同的。,40,错误概率与编码方法,1 简单重复编码 2 消息符号个数 3（5, 2）线性码 4 汉明距离,41,3 （5，2）线性码,从前面两节的讨论看出： 增大简单重复编码次数n，虽然使平均错误概率pE下降，但信息传输率R也降低了。 增大输入消息符号个数M，尽管可使信息传输率R增大，但又增大了平均错误概率pE 。 当采用好的编码方法时，可以使平均错误概率pE和信息传输率R两个指标得到较好的折衷。 本节采用（5.2）线性码，说明采用好的编码方法时，适当增大n和M，可以得到低的平均错误概率pE和较高的信息传输率R。,42,（5，2）线性码的编码,设M=4，

17、n=5 则输入符号有M=4种，由的4个不同取值决定。 采用以下编码方法将输入符号编码成为5位码：,43,（5,2）线性码的编码（续）,由上述编码方法得到一种(5,2)线性码，如图所示:,44,（5,2）线性码的译码效果,采用最大似然译码准则，当p = 0.01时 正确译码概率为 平均错误译码概率为 信息传输率为 前述n=3，M=4的一种简单重复编码 平均错误译码概率为 信息传输率为,45,结论,与n=3，M=4的简单重复编码比较，（5,2）线性码的信息传输率R略有降低，但平均错误概率却好得多。 说明好的编码方法可以在错误概率和信息传输率两个性能上达到最佳折衷。,46,离散信道编码定理,信道编码

18、定理是一个理想编码的存在性定理。 信道容量是一个临界值，信息传输率不超过这个值，信道就可几乎无失真地把信息传过去，否则就会产生失真。,47,错误概率与编码方法,1 简单重复编码 2 消息符号个数 3（5, 2）线性码 4 汉明距离,48,4 汉明距离,定义：设 为两个n长的二元码字，则码字X和Y之间的汉明距离为 其中， 代表模二和运算。 上式的含义是，两个码字之间的汉明距离就是它们在相同位上不同码符号的数目的总和。 举例： 设 X=(1 0 1 1 1 1 )，Y=(1 1 1 1 0 0 ) ， 则D(X,Y)=3,49,汉明距离满足的性质,1、非负性 D(X,Y)0 当且仅当X=Y式等号成立。 2、对称性 D(X,Y)=D(Y,X) 3、三角不等式 D(X,Z)+D(Y,Z) D(X,Y),50,最小码距Dmin,定义：在二元码C中，任意两个码字的汉明距离的最小值，称为码C的最小码距