第14讲信道编码与译码2014

信道编码与译码,第十四讲,第三章讨论无失真信源编码，给出无失真编码所需最小速率RH(U)/logD.信道给定，以任意小的错误概率实现可靠通信的最大传输速率为多少？Shannon于1948年提出并证明了信道编码定理，揭示了在什么条件下可以实现可靠通信，在什么情况下不能实现。后来很多研究者给出了更严格、更一般化的证明，指出了各种信道和编码条件下所能达到的编码定理的上、下限。这些理论的进展为合理设计实际通信系统提供了理论依据。,什么条件？RC,信道,信源,信源编码,信道编码,调制器,干扰源,信宿,信源译码,信道译码,解调器,数字通信系统模型,信道编码,信道编码（纠错编码）的任务是将输入的信息数字序列变换成另一个数字序列送入有扰离散信道。人为的按一定规则增加多余度，以便纠正传送过程中可能出现的错误，以尽可能小的错误概率恢复原来的信源序列。,00011011,00000101011101001111,r=11110,11010(10),0,1,1-p,1,0,1-p,p,p,假设p0.5,不编码，误码率pb=p,编码，pe=3p2+p3-6p4+3p5,信道编码器模型,每个信息数字持续时间为秒,编码器通常对信息数字进行分段，称为信息段，设其长度为.,在时间段内，编码器计算出个编码数字送入信道，称为码段。,编码数字持续时间为秒,信道编码分类,通常纠错码被分为两类，分组码和格状码。,（N,K)分组码：每K个信息数字为一组，计算出N个编码数字构成一个分组，一个分组又称为一个码字。码字之间是不相关的。,格状码：输出的码段不仅依赖于当前的K0位信息数字，还依赖于前m个信息段的信息数字，即总共与（m+1)K0个信息数字有关。,称（m+1)K0为编码约束长度。,称或为纠错码的编码速率或简称码率,要求纠错能力越强，所需多余度越大，码率就越低。,1101,1111110010,1101,11010100,实例,分组码(5,2),卷积码(2,1,3),分组码的译码准则,以分组码为例讨论信道编码的译码问题。,长为K的二元信息序列总数为个，而长为N的二元数字序列总数为个。,分组编码就是从个N长数字序列中选出个码字，分别用于代表M个不同的信息序列。任何一种指定方案就给定了一种编码方案。,令是信道输入相应的信道输出。,分组码的译码准则,纠错译码器的作用就是根据接收到的y和编码规则，对发送的是M个可能序列中的哪一个做出判决。,设译码器在收到y后将它译为。若，就出现了错误。这种事件出现的概率是误组率。,其中是第k位出现错误的概率,一个码字发生错误意味着N长二元数字序列中至少有一位错。,误比特率是译码后错误比特数与总比特数之比,分组码的译码准则,译码准则就是猜测规则，即当信道的输出值为y时，将其译为哪个码字m最合理？,最大后验概率准则,对特定接收序列y，,译码时要求最小,若有一个以上的m，使取同样的最大值时，我们可从其中任选一个，而不会影响平均错误概率,最小错误概率译码准则,分组码的译码准则,最大似然译码准则,最大后验概率,若所有可能消息序列的先验概率相等，则最大后验概率准则可进一步简化为,最大后验概率译码,最大似然译码（当消息先验概率相等时）,译码准则的对数形式,后验概率,【注2】在消息先验等概条件下，它等价于最大后验概率译码，因而也是最佳的。但若消息先验概率不确知时，采用最大似然译码就不一定保证译码错误概率最小。,【注1】它并不要求消息的先验概率。,【注3】实际系统中，信源发出的序列传送到信道之前都已进行信源编码，经过有效的信源编码，输出码元的概率分布会均匀化，所以信道的输入近似为等概，因此在工程应用中采用最大似然译码尽管不会使错误概率达到最小，但也接近最小。,最大似然译码准则,例题,设有一个离散信道，其转移概率矩阵为,并设，试分别按最小错误概率准则与最大似然译码准则确定译码规则，并计算相应的译码错误概率？,根据最大似然译码准则，译码函数为,在输入等概分布时的采用最大似然译码准则的平均错误概率：,在输入分布为（0.25,0.25,0.5）时的采用最大似然译码准则的平均错误概率：,根据最小错误概率译码准则，译码函数为,在输入分布为（0.25,0.25,0.5）时的采用最大似然译码准则的平均错误概率：,可见，在输入不等概分布时的采用最大似然译码准则的平均错误概率不是最小。,平均错误概率Pe与译码规则有关，而译码规则又由信道特性来决定。,由于信道存在噪声和干扰，使得接收到输出符号后，对发送的是什么符号还存在不确定性。,可见，Pe与信道怀疑义度H(X/Y)是有一定关系，也即满足Fano不等式。,Fano不等式,证明：,定义随机变量,Fano不等式,证明：,由Fano不等式，可得,由引理2,两边对l求和，得,综上,即,Fano不等式,对于给定的信源、信道及编译码规则，即给定了联合空间，则信道的含糊度就可被确定，这个值就给定了译码错误概率的下限。,分组码的译码,分组码编码：消息空间UL到输出空间YN的一种映射译码规则可以看成是YN到UL的一种映射，即将空间YN按译码准则划分成不相交的判决空间。,最大后验概率译码,最大似然译码,其中,若接收矢量，就将y判为消息m。若，就将y作为删除或检错处理。,令,表示,的补集，当发送消息为m，而接收y落入,中就会产生译码错误。,若消息m的先验概率为Q(m)，则平均译码错误概率为,分组码的译码,若消息m的先验概率为Q(m)，则可检测译码错误概率为,给定m时的不可检测译码错误概率为,定义：和的汉明距离为,其中,当所有码字为等概时，信道为BSC，最大似然译码为,对所有的,在对称信道条件下，离散输入序列的最大似然译码等价于最小汉明距离译码。,二元对称信道（BSC）的译码,0,1,1-p,1,0,1-p,p,p,假设p0.5,假设p0.5，可化简为,例题,设M=2且两个消息等概，令，。通过转移概率为p1/2的BSC信道传送。(1)若采用完备译码，试根据最大后验概率准则划分译码区间并给出相应的译码错误概率。(2)若可以划分三个区间，试确定译码规则并给出译码错误概率和有错不能判决的概率？,解：消息等概，最大后验概率准则等效最大似然译码准则。,1.若采用完备译码，即对任何情况都必须做出判决。,判决空间划分,Y1=0000，0001，0010，0100，1000，0011，1100，1001,Y2=1111，1110，1101，1011，0111，1010，0101，0110,这时不难算出错误概率为：,2.若可以划分三个区间，可将Y划分成：,0000，0001，0010，0100，1000,1111，1110，1101，1011，0111,0011，1100，0110，1001，1010，0101,这时不难算出错误概率为：,发现有错而不能判决的概率为：,连续序列的译码,此时以转移概率密度描述信道的转移特性。最大后验概率准则为找寻m，使,由贝叶斯公式，等价于,若各信号为等概的，则最大后验概率准则就转化为最大似然准则，即,高斯白噪声信道的译码准则,若加性信道噪声是均值为0，双边功率谱密度为的高斯白噪声，则信号转移概率密度可以表示为,即在高斯白噪声信道条件下，最大似然译码等价于最小平方欧氏距离译码。,如果对于所有的m,有都相等，即所有发送信号是等能量的，上式化简等价为,译码准则变为对接收序列y在所有发送码字中找使其最大。该规则称为最大相关译码。,两边取对数，化为,此时最大似然译码规则化简可以得到,作业,5.1,设有一DMC，其转移概率矩阵如下，若Q(x1)l/2，Q(x2)Q(x3)