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

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

1、第第6章章 信道编码概述信道编码概述王永容王永容 机械与电气工程学院机械与电气工程学院 信息论与编码 Information and Coding Theory 1第第6 6章章 信道编码信道编码6.1 6.1 信道差错概率信道差错概率6.2 6.2 信道编码概念信道编码概念6.3 6.3 信道信道译码准则信道信道译码准则6.4 6.4 码的检错与纠错能力码的检错与纠错能力6.5 6.5 信道编码定理信道编码定理26.1 信道差错概率信道差错概率l信道差错信道差错 在通信过程中，传送的最小信号波形是符号，编码后也称为码元。由于噪声干扰，码元在信道传输过程中会发生变化，信宿方接收到的码元符号不一

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

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

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

5、称为纠纠错编码函数错编码函数。信道编码也称为纠错编码纠错编码。96.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)。106.2 信道编码概念信道编码概念l系统码 u信道编码函数f：c=f(m)=m1m2,mk d1d2,dr(dj A)u信息元：m1m2,mku校验（监督）元：d

6、1d2,druk：信息位长度ur:校验位长度，或称为冗余位长度un=k+r:码字长度116.2 信道编码概念信道编码概念l按码元数分类 uq元码，或q进制码u2元码，或2进制码l按照编码函数f的线性性u线性码：编码函数f(f1,f2,fn)是线性函数 u非线性码：否则，称为非线性码。126.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、理方法:分组码分组码与卷积码卷积码136.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码率：146.2 6.2 信道编码概念信道编码概念l分组码分组码u循环码循环码 如果一个码的全体码字可以分为若干组，使得每组中任一码字的码元循环移位后仍是该组的码字，这样的分组码称为

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

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

10、=000,111。对重复码，可以采用大数准大数准则译码则译码。即如果接收序列中0的个数多于1的个数，则译为0；否则，译为1。u例如，2元3次重复码的编码规则如下：“0”“000”，“1”“111”。它是一个2元(3,1)分组码C=000,111。21第第6 6章章 信道编码信道编码6.1 信道差错概率信道差错概率6.2 信道编码概述信道编码概述6.3 信道译码准则信道译码准则6.4 码的检错与纠错能力码的检错与纠错能力6.5 信道编码定理信道编码定理226.3 信道译码准则信道译码准则l汉明（汉明（Hamming）距离）距离 两个长为n的码字x与y之间汉明（汉明（Hamming）距离）距离是指

11、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。236.3 信道译码准则信道译码准则l设 x=x1x2xn,y=y1y2yn是两个二元码字，容易验证以下等式成立:其中是模二加法l汉明距离的性质 定理定理6-1 设x、y与z是长为n的码字，那么汉明距离满足以下性质：(1)非负性：d(x,y)0。且d(x,y)=0的充分必要条件是x=

12、y；(2)对称性：d(x,y)=d(y,x)；(3)三角不等式：d(x,y)d(x,z)+d(z,y)。246.3 信道译码准则信道译码准则l如果译码函数如果译码函数g将二元序列将二元序列r译成二元码字译成二元码字c，那么，那么r与与c之之间的汉明距离间的汉明距离d(r,c)就是译码出错的位数。就是译码出错的位数。译码出错的位数尽可能小！l最小汉明距离译码最小汉明距离译码 称为最小汉明距离译码函数最小汉明距离译码函数，简称为最小距离译码函数最小距离译码函数。u最小汉明距离译码与信道转移概率无关256.3 信道译码准则信道译码准则l例例6-3 对n次重复码C=000,111进行最小距离译码。u设

13、接收的序列为r，如果d(r,000)d(r,111)，则将r译为111。u如果d(r,000)=d(r,111)，则不能正常译码，只能发现差错。u注意到，当d(r,000)d(r,111)时，序列r中1的个数多于0的个数，所以n次重复码的最小距离译码与大数准则译码相同。266.3 信道译码准则信道译码准则l费诺不等式费诺不等式 设信道输入符号集为A=a1,a2,aq，输出符号集为B=b1,b2,bs。输入符号是A上的一个随机变量X，输出符号是B上的一个随机变量Y。信道转移概率为：设信道译码函数F为:那么，F的平均译码错误概率PE满足：27第第6 6章章 信道编码信道编码6.1 信道差错概率信道

14、差错概率6.2 信道编码概述信道编码概述6.3 信道译码准则信道译码准则6.4 码的检错与纠错能力码的检错与纠错能力6.5 信道编码定理信道编码定理286.4 码的检错与纠错能力码的检错与纠错能力l最小汉明距离最小汉明距离 设C是一个(n,k)分组码，C的任意两个码字汉明距离的最小值称为C的最小汉明距离最小汉明距离，简称为最小距离最小距离，记为l最小距离与纠错能力的关系 定理定理6.2.设C是一个(n,k)分组码，其最小汉明距离为d(C)，则有 (1)如果码字出现了e个随机错误，且d(C)e+1，则能够检测到出现的错误。(2)如果码字出现了t个随机错误，且d(C)2t+1，则能够纠正出现的错误

15、。(3)如果C既能纠正t个随机错误，又能检测e(t)个随机错误，则要求d(C)t+e+1。296.4 码的检错与纠错能力码的检错与纠错能力l 证明证明 (1)如果发送的码字c中出现了e个随机错误，且变成了另一个许用码字r，则这样的错误是不可能被检测出来的。反之，如果r是一个禁用码字，则这样的错误能够被发现。当d(C)=e+1时，由于d(r,c)e，所以r必须是禁用码字，因而能够被检测出来的。在图中，以c为圆心，e为半径的圆内，只有一个许用码字c。由于d(r,c)e，即r位于该圆内，所以r一定是禁用码字。306.4 码的检错与纠错能力码的检错与纠错能力l 证明证明 (2)如果发送的码字c出现了t

16、个随机错误变成了一个码元序列r，由已知得 设c c是任意一个码字 d(c,c)d(c,r)+d(r,c)，在C的所有码字中，c与 r 的汉明距离最小。使用最小距离译码方法时，必将 r 译为正确的码字c，即纠正了c在传输过程中出现的错误。316.4 码的检错与纠错能力码的检错与纠错能力l 例例6-4.码长为n的q元重复码为 C=000,111,(q1)(q1)(q1)。因为d(C)=n，所以码C既可以纠正(n1)/2 个错误，又可以检测n1个错误。l 例例6-5.偶校验码偶校验码 如下构造的(n,n 1)分组码称为奇偶校奇偶校验（监督）码验（监督）码:m=(m1m2mn1)c=(m1m2mn1c

17、0)，其中校验元c0=m1+m2+mn1 (mod 2).可知，奇偶校验码共有2n1个码字，每个码字都包含偶数个1。326.4 码的检错与纠错能力码的检错与纠错能力l 例例6-6.分析奇偶校验码在BSC上传送时的纠错性能，假设信道错误概率p=102，使用最小距离译码规则进行译码。(1)(2,1)奇偶校验码奇偶校验码 n=2，c0=m1(mod 2)，m1=0，1，C=00,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，11

18、0，d(C)=2，R=2/3，能发现一个错误。平均译码错误概率为33第第6 6章章 信道编码信道编码6.1 信道差错概率信道差错概率6.2 信道编码概述信道编码概述6.3 信道译码准则信道译码准则6.4 码的检错与纠错能力码的检错与纠错能力6.5 信道编码定理信道编码定理346.5 信道编码定理信道编码定理l定理定理6.3.设离散无记忆信道的信道容量为C，信息传输率为R，是一个任意小的正数。那么，只要R C，就存在码长为n，码字数目为M=2nR的码及相应的译码规则，使其平均译码错误概率PE C时，无论n多大，也不存在码长为n，码字数目为M=2nR的码，使其平均译码错误概率PE 。称为有噪信道编

19、码逆定理。356.5 信道编码定理信道编码定理l任何信道的信道容量是一个明确的分界点，当信息传输率小于信道容量时，能保证信道传输的可靠性；当信息传输率大于信道容量时，信道差错概率会变得很大。因此，任何信道的信道容量就是可达的、最大的可靠信息传输率。366.5 信道编码定理信道编码定理l香农第二定理只是一个存在性定理，它说明错误概率趋于零的好码是存在的。但香农并没有给出这种好码具有实用价值的构造方法。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码，已经非常接近信道编码定理给出的极限性能。37