信息论与编码A_第6章信道编码概述.ppt

《信息论与编码A_第6章信道编码概述.ppt》由会员分享，可在线阅读，更多相关《信息论与编码A_第6章信道编码概述.ppt（62页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1第第6章章 信道编码概述信道编码概述信息论与编码 Information and Coding Theory 西南交通大学西南交通大学 信息科学与技术学院信息科学与技术学院2第第6 6章章 信道编码信道编码6.1 6.1 信道差错概率信道差错概率6.2 6.2 信道编码概念信道编码概念6.3 6.3 信道信道译码准则信道信道译码准则6.4 6.4 码的检错与纠错能力码的检错与纠错能力6.5 6.5 信道编码定理信道编码定理36.1 信道差错概率信道差错概率l信道差错信道差错 在通信过程中，传送的最小信号波形是符号，编码后也称为码元。由于噪声干扰，码元在信道传输过程中会发生变化，信宿方接收到的

2、码元符号不一定是信源发出的码元符号.YXXY信道信道干扰干扰46.1.1 随机差错信道随机差错信道l信道中，各码元是否出现差错，与其前、后码元是否出现差错无关，每个码元独立地按一定概率产生差错。这类信道称为随机差错信道.l随机差错是由加性高斯白噪声引起.l主要参数:码元差错概率码元差错概率，简称为误码率误码率56.1.1 随机差错信道随机差错信道lDMC的差错概率的差错概率u信道输入X：A=a1,a2,aqu信道输出Y：B=b1,b2,bs u信道差错规律：条件概率描述 66.1.1 随机差错信道随机差错信道lDMC的平均误码率的平均误码率u码元码元ai正确传输概率为：正确传输概率为：u码元码

3、元ai出错概率为：出错概率为：u信道先验概率分布为信道先验概率分布为：u信道因噪声干扰产生的平均错误概率为：信道因噪声干扰产生的平均错误概率为：76.1.2 突发差错信道突发差错信道l信道中，差错成片出现，一个差错成片称为一个突发信道中，差错成片出现，一个差错成片称为一个突发差错。差错。l突发差错总是以差错码元开头、且以差错码元结尾，突发差错总是以差错码元开头、且以差错码元结尾，头尾之间并不是每个码元都错，而是码元差错概率超头尾之间并不是每个码元都错，而是码元差错概率超过了某个标准值。过了某个标准值。l通信系统中的突发差错是由突发噪声（如雷电、强脉通信系统中的突发差错是由突发噪声（如雷电、强脉

4、冲、时变信道的衰落等）引起的。冲、时变信道的衰落等）引起的。l存储系统中，磁带、磁盘物理介质的缺陷或读写头接存储系统中，磁带、磁盘物理介质的缺陷或读写头接触不良等造成的差错均为突发差错。触不良等造成的差错均为突发差错。8第第6 6章章 信道编码信道编码6.1 6.1 信道差错概率信道差错概率6.2 6.2 信道编码概念信道编码概念6.3 6.3 信道信道译码准则信道信道译码准则6.4 6.4 码的检错与纠错能力码的检错与纠错能力6.5 6.5 信道编码定理信道编码定理96.2 信道编码概念信道编码概念l信道编码器是一个映射f，它把信源符号序列m变换成信道符号序列c=f(m)，f称为信道编码函数

5、信道编码函数，或称为纠纠错编码函数错编码函数。信道编码也称为纠错编码纠错编码。106.2 信道编码概念信道编码概念l符号集：A=a1,a2,aq l信源符号序列：m=m1m2mk(mi A)l信道编码函数f：c=f(m)=c1c2cn(cj A)l信息元：m1,m2,mkl信息位长度：kl码字(codeword)：cl码字长度:n l设S是全体信源符号序列构成的集合，C=f(m)|m S 称为信道码信道码，或称为纠错码纠错码，简称为码码(code)。116.2 信道编码概念信道编码概念l系统码 u信道编码函数f：c=f(m)=m1m2,mk d1d2,dr(dj A)u信息元：m1m2,mku

6、校验（监督）元：d1d2,druk：信息位长度ur:校验位长度，或称为冗余位长度un=k+r:码字长度126.2 信道编码概念信道编码概念l按码元数分类 uq元码，或q进制码u2元码，或2进制码l按照编码函数f的线性性u线性码：编码函数f(f1,f2,fn)是线性函数 u非线性码：否则，称为非线性码。136.2 信道编码概念信道编码概念l分组码 设k,n是正整数，k n，则把从EAk到An的编码函数 f:EAn 称为一个(n,k)分组码编码器，或称为(n,k)编码函数。全体码字构成的集合 C=c=f(m):mE 称为一个q元(n,k)分组码(block code)，或简称为(n,k)码。l按照

7、编码函数对信息元处理方法:分组码分组码与卷积码卷积码146.2 信道编码概念信道编码概念u设M=|E|，q元(n,k)分组码的信息传输率信息传输率，或称为码率、码率、速率：速率：u当E=Ak时pq元(n,k)分组码C包含有qk个码字，称为许用码字许用码字p长度为n的符号序列共有qn个，其中有qk个是许用码字，其余qnqk个称为禁用码字禁用码字p一个(n,k)分组码编码器其实就是确定一个规则，以便从qn个n重符号中选出qk个许用码字p码率：156.2 6.2 信道编码概念信道编码概念l分组码分组码u循环码循环码 如果一个码的全体码字可以分为若干组，使得每组中任一码字的码元循环移位后任是该组的码字

8、，这样的分组码称为循环码u非循环码非循环码 不是循环码的分组码，称为非循环码166.2 6.2 信道编码概念信道编码概念l卷积码卷积码(n,k,m)把信源符号序列分成长为k的段，依次对每段进行编码，码字长度都为n。如果每个码字的码元不但与该段的k位信息元有关，还与之前m段的信息元有关，这样得到的信道码称为(n,k,m)卷积码卷积码。即卷积码码字的码元与(m+1)k位信息元有关。176.2 6.2 信道编码概念信道编码概念186.2 6.2 信道编码概念信道编码概念l译码函数译码函数 信道译码器的主要功能就是确定一套译码规则g，由接收到的符号序列r给出信源符号序列c的一个最接近的估计g(r)。g

9、称为译码函数译码函数，由r求g(r)的过程称为信道信道译码译码。如果g(r)=c，说明信道译码器译码正确。如果g(r)c，说明信道译码器译码错误。196.2 6.2 信道编码概念信道编码概念l在接收到符号序列r的条件概率，译码器译码错误的条件概率定义为：l译码器平均译码错误概率定义为206.2 6.2 信道编码概念信道编码概念lP(r)是译码器接收符号序列r的概率分布：l信道因噪声干扰产生的平均错误概率为l使用信道编码技术的主要目的就是使 PE PC.216.2 6.2 信道编码概念信道编码概念l例例6.1 重复码重复码 重复码是一个(n,1)分组码，其编码规则是将每位信息元重复n 1次，也称

10、为n次重复码。即C=000,111。对重复码，可以采用大数准大数准则译码则译码。即如果接收序列中0的个数多于1的个数，则译为0；否则，译为1。u例如，2元3次重复码的编码规则如下：“0”“000”，“1”“111”。它是一个2元(3,1)分组码C=000,111。226.2 6.2 信道编码概念信道编码概念u译码器接收符号序列r及译码结果236.2 6.2 信道编码概念信道编码概念u假设使用一个具有错误概率为p 1/2的无记忆二元对称信道传输一个信源符号，且信源发出符号0和1的概率均为1/2。p计算接收符号序列r的概率分布P(r)。246.2 6.2 信道编码概念信道编码概念l当三个符号在传输

11、过程中有一位或二位出错时，译码器能够发现接收到的序列有错，但不知道那些位出了错。但当三个符号在传输过程中都出错时，译码器不能发现错误。即分组码C最多能检出最多能检出2位错误位错误。l如果采用大数准则大数准则译码方法，当传输的符号序列有一位出错时，能正确纠正。即分组码分组码C能纠正能纠正1位错误位错误。256.2 6.2 信道编码概念信道编码概念u译码错误条件概率266.2 6.2 信道编码概念信道编码概念l译码器平均译码错误概率为l如果不使用信道编码，直接传输信源符号，则信宿方接收到符号0时译为0，接收到符号1时译为1，其信道错误概率为l因为PE PC，所以3次重复码的使用提高了信道的可靠性。

12、276.2 6.2 信道编码概念信道编码概念l例如，当PC=p=102时，有l使用简单的重复编码方法，已将错误概率降低了接近二个数量级!286.2 6.2 信道编码概念信道编码概念l当重复次数n增加时，平均错误概率将进一步降低，但码率也随之降低。29第第6 6章章 信道编码信道编码6.1 信道差信道差错概率概率6.2 信道信道编码概述概述6.3 信道信道译码准准则6.4 码的的检错与与纠错能力能力6.5 信道信道编码定理定理306.3 信道译码准则信道译码准则l最小错误概率译码最小错误概率译码u译码函数g应该具有最小平均译码错误概率PE。u定义g(r)的值满足：u译码函数g称为最小错误译码函数

13、最小错误译码函数，或称为最大后验最大后验概率译码概率译码。u选择最大后验概率译码函数g 316.3 信道译码准则信道译码准则u平均译码错误概率u信源服从均匀分布时，P(c)也是均匀分布，设码字总数为M=|C|，则有P(c)=M1，326.3 信道译码准则信道译码准则l最大似然译码最大似然译码(MLD)定义g(r)的值满足：u译码函数g称为最大似然译码最大似然译码，P(r|c)称为似然函数似然函数u最大似然译码函数只与信道转移概率有关，与信源概率分布无关。u最大似然译码函数g由下式确定336.3 信道译码准则信道译码准则u当信源服从均匀分布时 因此，在信源服从均匀分布情况下，最大后验概率译码与最

14、大似然译码是相同的，其平均译码错误概率为最小。346.3 信道译码准则信道译码准则l例例6-2.有一个离散信道，输入符号集为A=a1,a2,a3，接收符号集为B=b1,b2,b3，信道矩阵为 （1）求最大似然译码函数 因为信道矩阵P的第一列中P(b1|a1)=0.5为最大，第三列中P(b3|a2)=0.5为最大，第二列中P(b2|a1)=P(b2|a2)=P(b2|a3)=0.3，所以最大似然译码函数为：g(b1)=a1,g(b2)=a3,g(b3)=a2.356.3 信道译码准则信道译码准则如果输入不是等概率分布，设l例例6-2（续（续1）如果输入是等概率分布：P(a1)=(a2)=P(a3

15、)=1/3 366.3 信道译码准则信道译码准则l例例6-2（续（续2）（2）求最大后验概率译码函数h 首先计算接收符号r概率分布P(r)计算后验概率P(c|r):376.3 信道译码准则信道译码准则l例例6-2（续（续3）（2）求最大后验概率译码函数h 最大后验概率译码函数h:h(b1)=a3,h(b2)=a3,h(b3)=a3 输入不是等概率分布时，最大似然译码函数的平均错输入不是等概率分布时，最大似然译码函数的平均错误概率不是最小的误概率不是最小的!386.3 信道译码准则信道译码准则l汉明（汉明（Hamming）距离）距离 两个长为n的码字x与y之间汉明（汉明（Hamming）距离）距

16、离是指x与y之间对应位置上不相同码元的个数，用符号d(x,y)表示。l汉明重量：汉明重量：码字x中非零码元的个数称为x的汉明重量汉明重量，用符号w(x)表示。u例如:对于两个二元码字:x=101111，y=111100 有d(x,y)=3。u又如:对于两个码字:x=1320120,y=1223310 有d(x,y)=4。396.3 信道译码准则信道译码准则l设 x=x1x2xn,y=y1y2yn是两个二元码字，容易验证以下等式成立:其中是模二加法l汉明距离的性质 定理定理6-1 设x、y与z是长为n的码字，那么汉明距离满足以下性质：(1)非负性：d(x,y)0。且d(x,y)=0的充分必要条件

17、是x=y；(2)对称性：d(x,y)=d(y,x)；(3)三角不等式：d(x,y)d(x,z)+d(z,y)。406.3 信道译码准则信道译码准则l如果译码函数如果译码函数g将二元序列将二元序列r译成二元码字译成二元码字c，那么，那么r与与c之之间的汉明距离间的汉明距离d(r,c)就是译码出错的位数。就是译码出错的位数。译码出错的位数尽可能小！l最小汉明距离译码最小汉明距离译码 称为最小汉明距离译码函数最小汉明距离译码函数，简称为最小距离译码函数最小距离译码函数。u最小汉明距离译码与信道转移概率无关416.3 信道译码准则信道译码准则l对于二元对称无记忆信道，设每个符号出错概率为p1/2，r=

18、(r1,r2,rn)，c=(c1,c2,cn)，那么u当r不变时，选择c使P(r|c)达到最大的充分必要条件是使d(r,c)达到最小。u对于二元对称无记忆信道，最小汉明距离译码与最大似然译码是相同的。426.3 信道译码准则信道译码准则l在二元对称无记忆信道中，平均译码错误概率可用汉明距离表示。设信源服从均匀分布，码字总数为M=|C|，有436.3 信道译码准则信道译码准则l例例6-3 对n次重复码C=000,111进行最小距离译码。u设接收的序列为r，如果d(r,000)d(r,111)，则将r译为111。u如果d(r,000)=d(r,111)，则不能正常译码，只能发现差错。u注意到，当d

19、(r,000)d(r,111)时，序列r中1的个数多于0的个数，所以n次重复码的最小距离译码与大数准则译码相同。446.3 信道译码准则信道译码准则l例例6-4.设一个离散信源有四个符号S=(s1,s2,s3,s4)，编码器输出的码为C=0000,1010,0111,1101。如果在一个具有单符号错误概率为p=102的BSC上传送码字，求最佳译码及平均译码错误概率。(1)如果信源服从均匀分布：采用最大似然译码。456.3 信道译码准则信道译码准则l例例6-4（续（续1）.(1)最大似然译码过程如下466.3 信道译码准则信道译码准则l例例6-4（续（续2）.(1)最大似然译码：译码正确概率为

20、平均译码错误概率为：476.3 信道译码准则信道译码准则l例例6-4（续（续3）.(2)如果信源服从以下分布：采用最小错误译码。486.3 信道译码准则信道译码准则l例例6-4（续（续4）.(2)最小错误译码 496.3 信道译码准则信道译码准则l例例6-4（续（续5）.(2)最小错误译码：译码正确概率为 平均译码错误概率为：506.3 信道译码准则信道译码准则l平均译码错误概率PE与与译码函数有关，而译码函数又与信道特性有关。由于信道存在噪声，导致符号传输发生错误，接收端收到符号后，对发送的是什么符号还存在不确定性。516.3 信道译码准则信道译码准则l费诺不等式费诺不等式 设信道输入符号集

21、为A=a1,a2,aq，输出符号集为B=b1,b2,bs。输入符号是A上的一个随机变量X，输出符号是B上的一个随机变量Y。信道转移概率为：设信道译码函数F为:那么，F的平均译码错误概率PE满足：52第第6 6章章 信道编码信道编码6.1 信道差信道差错概率概率6.2 信道信道编码概述概述6.3 信道信道译码准准则6.4 码的的检错与与纠错能力能力6.5 信道信道编码定理定理536.4 码的检错与纠错能力码的检错与纠错能力l最小汉明距离最小汉明距离 设C是一个(n,k)分组码，C的任意两个码字汉明距离的最小值称为C的最小汉明距离最小汉明距离，简称为最小距离最小距离，记为l最小距离与纠错能力的关系

22、 定理定理6.2.设C是一个(n,k)分组码，其最小汉明距离为d(C)，则有 (1)如果码字出现了e个随机错误，且d(C)e+1，则能够检测到出现的错误。(2)如果码字出现了t个随机错误，且d(C)2t+1，则能够纠正出现的错误。(3)如果C既能纠正t个随机错误，又能检测e(t)个随机错误，则要求d(C)t+e+1。546.4 码的检错与纠错能力码的检错与纠错能力l 证明证明 (1)如果发送的码字c中出现了e个随机错误，且变成了另一个许用码字r，则这样的错误是不可能被检测出来的。反之，如果r是一个禁用码字，则这样的错误能够被发现。当d(C)=e+1时，由于d(r,c)e，所以r必须是禁用码字，

23、因而能够被检测出来的。在图中，以c为圆心，e为半径的圆内，只有一个许用码字c。由于d(r,c)e，即r位于该圆内，所以r一定是禁用码字。556.4 码的检错与纠错能力码的检错与纠错能力l 证明证明 (2)如果发送的码字c出现了t个随机错误变成了一个码元序列r，由已知得 设c c是任意一个码字 d(c,c)d(c,r)+d(r,c)，在C的所有码字中，c与 r 的汉明距离最小。使用最小距离译码方法时，必将 r 译为正确的码字c，即纠正了c在传输过程中出现的错误。566.4 码的检错与纠错能力码的检错与纠错能力l 例例6-5.码长为n的q元重复码为 C=000,111,(q1)(q1)(q1)。因

24、为d(C)=n，所以码C既可以纠正(n1)/2 个错误，又可以检测n1个错误。l 例例6-6.偶校验码偶校验码 如下构造的(n,n 1)分组码称为奇偶校验奇偶校验（监督）码（监督）码:m=(m1m2mn1)c=(m1m2mn1c0)，其中校验元c0=m1+m2+mn1 (mod 2).可知，奇偶校验码共有2n1个码字，每个码字都包含偶数个1。576.4 码的检错与纠错能力码的检错与纠错能力l 例例6-6.分析奇偶校验码在BSC上传送时的纠错性能，假设信道错误概率p=102，使用最小距离译码规则进行译码。(1)(2,1)奇偶校验码奇偶校验码 n=2，c0=m1(mod 2)，m1=0，1，C=0

25、0,11，d(C)=2，R=1/2，能发现一个错误,平均译码错误概率为PE=102。(2)(3,2)奇偶校验码奇偶校验码 n=3，c0=m1+m2(mod 2)，m1m2=00，01，10，11 C=000，011，101，110，d(C)=2，R=2/3，能发现一个错误。平均译码错误概率为58第第6 6章章 信道编码信道编码6.1 信道差信道差错概率概率6.2 信道信道编码概述概述6.3 信道信道译码准准则6.4 码的的检错与与纠错能力能力6.5 信道信道编码定理定理596.5 信道编码定理信道编码定理l定理定理6.3.设离散无记忆信道的信道容量为C，信息传输率为R，是一个任意小的正数。那么

26、，只要R C，就存在码长为n，码字数目为M=2nR的码及相应的译码规则，使其平均译码错误概率PE C时，无论n多大，也不存在码长为n，码字数目为M=2nR的码，使其平均译码错误概率PE 。称为有噪信道编码逆定理。606.5 信道编码定理信道编码定理l任何信道的信道容量是一个明确的分界点，当信息传输率小于信道容量时，能保证信道传输的可靠性；当信息传输率大于信道容量时，信道差错概率会变得很大。因此，任何信道的信道容量就是可达的、最大的可靠信息传输率。616.5 信道编码定理信道编码定理l香农第二定理只是一个存在性定理，它说明错误概率趋于零的好码是存在的。但香农并没有给出这种好码具有实用价值的构造方

27、法。l有噪信道编码定理具有根本性的重要意义。它有助于指导各种通信系统的设计，有助于评价各种通信系统和编码的效率。l在香农1948年发表经典论文通信的数学理论（C E Shannon.A Mathematical Theory of Communication.B.S.T.J.vol.27,July,and Oct.1948）后，科学家们致力于研究实际信道中易于实现的编码方法。在20世纪60至70年代，编码理论的研究非常活跃，出现了代数码、卷积码、循环码等。尤其是在1993年，C.Berrou等提出的Turbo码，已经非常接近信道编码定理给出的极限性能。62第第6 6章章 习习 题题lP.176:1,2,3,4