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

1,第6章 信道编码概述,王永容 机械与电气工程学院,信息论与编码 Information and Coding Theory,2,第6章 信道编码,6.1 信道差错概率6.2 信道编码概念6.3 信道信道译码准则6.4 码的检错与纠错能力6.5 信道编码定理,3,6.1 信道差错概率,信道差错 在通信过程中，传送的最小信号波形是符号，编码后也称为码元。由于噪声干扰，码元在信道传输过程中会发生变化，信宿方接收到的码元符号不一定是信源发出的码元符号.YX,4,6.1.1 随机差错信道,信道中，各码元是否出现差错，与其前、后码元是否出现差错无关，每个码元独立地按一定概率产生差错。这类信道称为随机差错信道.随机差错是由加性高斯白噪声引起.主要参数:码元差错概率，简称为误码率,5,6.1.1 随机差错信道,DMC的差错概率信道输入X：A=a1,a2,aq信道输出Y：B=b1,b2,bs 信道差错规律：条件概率描述,6,6.1.1 随机差错信道,DMC的平均误码率码元ai正确传输概率为：,码元ai出错概率为：,信道先验概率分布为：,信道因噪声干扰产生的平均错误概率为：,7,6.1.2 突发差错信道,信道中，差错成片出现，一个差错成片称为一个突发差错。突发差错总是以差错码元开头、且以差错码元结尾，头尾之间并不是每个码元都错，而是码元差错概率超过了某个标准值。通信系统中的突发差错是由突发噪声（如雷电、强脉冲、时变信道的衰落等）引起的。存储系统中，磁带、磁盘物理介质的缺陷或读写头接触不良等造成的差错均为突发差错。,8,第6章 信道编码,6.1 信道差错概率6.2 信道编码概念6.3 信道信道译码准则6.4 码的检错与纠错能力6.5 信道编码定理,9,6.2 信道编码概念,信道编码器是一个映射f，它把信源符号序列m变换成信道符号序列c=f(m)，f称为信道编码函数，或称为纠错编码函数。信道编码也称为纠错编码。,10,6.2 信道编码概念,符号集：A=a1,a2,aq 信源符号序列：m=m1m2mk(mi A)信道编码函数f：c=f(m)=c1c2cn(cj A)信息元：m1,m2,mk信息位长度：k码字(codeword)：c码字长度:n,设S是全体信源符号序列构成的集合，C=f(m)|m S 称为信道码，或称为纠错码，简称为码(code)。,11,6.2 信道编码概念,系统码 信道编码函数f：c=f(m)=m1m2,mk d1d2,dr(dj A)信息元：m1m2,mk校验（监督）元：d1d2,dr,k：信息位长度r:校验位长度，或称为冗余位长度n=k+r:码字长度,12,6.2 信道编码概念,按码元数分类 q元码，或q进制码2元码，或2进制码,按照编码函数f的线性性线性码：编码函数f(f1,f2,fn)是线性函数 非线性码：否则，称为非线性码。,13,6.2 信道编码概念,分组码 设k,n是正整数，k n，则把从EAk到An的编码函数 f:EAn 称为一个(n,k)分组码编码器，或称为(n,k)编码函数。全体码字构成的集合 C=c=f(m):mE 称为一个q元(n,k)分组码(block code)，或简称为(n,k)码。,按照编码函数对信息元处理方法:分组码与卷积码,14,6.2 信道编码概念,设M=|E|，q元(n,k)分组码的信息传输率，或称为码率、速率：,当E=Ak时q元(n,k)分组码C包含有qk个码字，称为许用码字长度为n的符号序列共有qn个，其中有qk个是许用码字，其余qnqk个称为禁用码字一个(n,k)分组码编码器其实就是确定一个规则，以便从qn个n重符号中选出qk个许用码字码率：,15,6.2 信道编码概念,分组码循环码 如果一个码的全体码字可以分为若干组，使得每组中任一码字的码元循环移位后仍是该组的码字，这样的分组码称为循环码非循环码 不是循环码的分组码，称为非循环码,16,6.2 信道编码概念,卷积码(n,k,m)把信源符号序列分成长为k的段，依次对每段进行编码，码字长度都为n。如果每个码字的码元不但与该段的k位信息元有关，还与之前m段的信息元有关，这样得到的信道码称为(n,k,m)卷积码。即卷积码码字的码元与(m+1)k位信息元有关。,17,6.2 信道编码概念,18,6.2 信道编码概念,译码函数 信道译码器的主要功能就是确定一套译码规则g，由接收到的符号序列r给出信源符号序列c的一个最接近的估计g(r)。g称为译码函数，由r求g(r)的过程称为信道译码。如果g(r)=c，说明信道译码器译码正确。如果g(r)c，说明信道译码器译码错误。,19,6.2 信道编码概念,在接收到符号序列r的条件概率，译码器译码错误的条件概率定义为：,译码器平均译码错误概率定义为,20,6.2 信道编码概念,P(r)是译码器接收符号序列r的概率分布：,信道因噪声干扰产生的平均错误概率为,使用信道编码技术的主要目的就是使 PE PC.,21,6.2 信道编码概念,例6.1 重复码 重复码是一个(n,1)分组码，其编码规则是将每位信息元重复n 1次，也称为n次重复码。即C=000,111。对重复码，可以采用大数准则译码。即如果接收序列中0的个数多于1的个数，则译为0；否则，译为1。例如，2元3次重复码的编码规则如下：“0”“000”，“1”“111”。它是一个2元(3,1)分组码C=000,111。,22,第6章 信道编码,6.1 信道差错概率6.2 信道编码概述6.3 信道译码准则6.4 码的检错与纠错能力6.5 信道编码定理,23,6.3 信道译码准则,汉明（Hamming）距离 两个长为n的码字x与y之间汉明（Hamming）距离是指x与y之间对应位置上不相同码元的个数，用符号d(x,y)表示。汉明重量：码字x中非零码元的个数称为x的汉明重量，用符号w(x)表示。,例如:对于两个二元码字:x=101111，y=111100 有d(x,y)=3。又如:对于两个码字:x=1320120,y=1223310 有d(x,y)=4。,24,6.3 信道译码准则,设 x=x1x2xn,y=y1y2yn是两个二元码字，容易验证以下等式成立:,其中是模二加法汉明距离的性质 定理6-1 设x、y与z是长为n的码字，那么汉明距离满足以下性质：(1)非负性：d(x,y)0。且d(x,y)=0的充分必要条件是x=y；(2)对称性：d(x,y)=d(y,x)；(3)三角不等式：d(x,y)d(x,z)+d(z,y)。,25,6.3 信道译码准则,如果译码函数g将二元序列r译成二元码字c，那么r与c之间的汉明距离d(r,c)就是译码出错的位数。译码出错的位数尽可能小！最小汉明距离译码,称为最小汉明距离译码函数，简称为最小距离译码函数。最小汉明距离译码与信道转移概率无关,26,6.3 信道译码准则,例6-3 对n次重复码C=000,111进行最小距离译码。设接收的序列为r，如果d(r,000)d(r,111)，则将r译为111。如果d(r,000)=d(r,111)，则不能正常译码，只能发现差错。注意到，当d(r,000)d(r,111)时，序列r中1的个数多于0的个数，所以n次重复码的最小距离译码与大数准则译码相同。,27,6.3 信道译码准则,费诺不等式 设信道输入符号集为A=a1,a2,aq，输出符号集为B=b1,b2,bs。输入符号是A上的一个随机变量X，输出符号是B上的一个随机变量Y。信道转移概率为：,设信道译码函数F为:,那么，F的平均译码错误概率PE满足：,28,第6章 信道编码,6.1 信道差错概率6.2 信道编码概述6.3 信道译码准则6.4 码的检错与纠错能力6.5 信道编码定理,29,6.4 码的检错与纠错能力,最小汉明距离 设C是一个(n,k)分组码，C的任意两个码字汉明距离的最小值称为C的最小汉明距离，简称为最小距离，记为,最小距离与纠错能力的关系 定理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。,30,6.4 码的检错与纠错能力,证明(1)如果发送的码字c中出现了e个随机错误，且变成了另一个许用码字r，则这样的错误是不可能被检测出来的。反之，如果r是一个禁用码字，则这样的错误能够被发现。当d(C)=e+1时，由于d(r,c)e，所以r必须是禁用码字，因而能够被检测出来的。在图中，以c为圆心，e为半径的圆内，只有一个许用码字c。由于d(r,c)e，即r位于该圆内，所以r一定是禁用码字。,31,6.4 码的检错与纠错能力,证明(2)如果发送的码字c出现了t个随机错误变成了一个码元序列r，由已知得,设c c是任意一个码字 d(c,c)d(c,r)+d(r,c)，,在C的所有码字中，c与 r 的汉明距离最小。使用最小距离译码方法时，必将 r 译为正确的码字c，即纠正了c在传输过程中出现的错误。,32,6.4 码的检错与纠错能力,例6-4.码长为n的q元重复码为 C=000,111,(q1)(q1)(q1)。因为d(C)=n，所以码C既可以纠正(n1)/2 个错误，又可以检测n1个错误。,例6-5.偶校验码 如下构造的(n,n 1)分组码称为奇偶校验（监督）码:m=(m1m2mn1)c=(m1m2mn1c0)，其中校验元c0=m1+m2+mn1(mod 2).可知，奇偶校验码共有2n1个码字，每个码字都包含偶数个1。,33,6.4 码的检错与纠错能力,例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，110，d(C)=2，R=2/3，能发现一个错误。平均译码错误概率为,34,第6章 信道编码,6.1 信道差错概率6.2 信道编码概述6.3 信道译码准则6.4 码的检错与纠错能力6.5 信道编码定理,35,6.5 信道编码定理,定理6.3.设离散无记忆信道的信道容量为C，信息传输率为R，是一个任意小的正数。那么，只要R C，就存在码长为n，码字数目为M=2nR的码及相应的译码规则，使其平均译码错误概率PE。著名的香农第二定理，称为有噪信道编码定理。,定理6.4.设离散无记忆信道的信道容量为C，信息传输率为R，是一个任意小的正数。那么，当R C时，无论n多大，也不存在码长为n，码字数目为M=2nR的码，使其平均译码错误概率PE。称为有噪信道编码逆定理。,36,6.5 信道编码定理,任何信道的信道容量是一个明确的分界点，当信息传输率小于信道容量时，能保证信道传输的可靠性；当信息传输率大于信道容量时，信道差错概率会变得很大。因此，任何信道的信道容量就是可达的、最大的可靠信息传输率。,37,6.5 信道编码定理,香农第二定理只是一个存在性定理，它说明错误概率趋于零的好码是存在的。但香农并没有给出这种好码具有实用价值的构造方法。有噪信道编码定理具有根本性的重要意义。它有助于指导各种通信系统的设计，有助于评价各种通信系统和编码的效率。在香农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码，已经非常接近信道编码定理给出的极限性能。,