信息论与编码-第六章2

1、信息论与编码-最优译码和最大似然译码 最优译码和最大似然译码 信道的输入是一个二（或q）进制序列，而 译码器的输出时一个信息序列M的估值序 列 。如下图所示。 译码器的基本任务就是根据一套译码规则， 由接收序列R给出与发送的信息序列最接 近（最好是相同）的估值序列 M M 信息论与编码-最优译码和最大似然译码 信道 纠错编码器纠错译码器 干扰源 011 (,.,) k M m mm ),( 110N ccc C ),( 110N rrr R 011 (,.,) k M m mm 信源编码器输出 至信宿 分组码数字通信模型 信息论与编码-最优译码和最大似然译码 由于M与码字C之间存在一一对应关系

2、，所以 这等价于译码其根据R产生一个C的估值序 列 ， 显然，当且仅当 时， 。这时译码器 正确译码。 如果 ，则译码器产生错误译码。 当给定接收序列R时，译码器的条件译码错误 概率定义为 C CC MM CC )/ ()/(RCCPREP 信息论与编码-最优译码和最大似然译码 所以译码器的错误译码概率为 其中， 是接收R的概率，与译码方法无关， 译码错误概率最小的最佳译码规则是使 最 小，即 R E RpREPP)()/( )(Rp E P )/ (min)/(minminRCCPREPP E 信息论与编码-最优译码和最大似然译码 而 因此，如果译码器对输入的R，能在 个码字中 选择一个使

3、最大的码 字 作为C的估值序列 ，即 则这种译码规则一定能使译码器输出错误概率 最小，称这种译码规则为最大后验概率译码 MAP (maximum aposteriori),也叫做最佳译码。 是一种通过经验与归纳由收码推测发码的方法， 是最优的译码方法。 k 2 )2 , 2 , 1)(/ ( k i iRCCP i C C )/(max RCpC ii )/ (max)/ (minRCCPRCCP 信息论与编码-最优译码和最大似然译码 由贝叶斯公式 可知，如果发送端发送每一个码字的概率 均 相同,且p(R)对所有R也相等（信道对称均衡）， 则有 )( i Cp )/(max)/(max 2 ,

4、 2 , 12 , 2 , 1 i i i i CRpRCp kk )( )/()( )/( Rp CRpCp RCp ii i 信息论与编码-最优译码和最大似然译码 一个译码器如果能选择 即在已知R的情况下使先验概率最大，则 这种译码规则称为最大似然译码 （ML(MLD)：Maximum Likelihood)， 称为似然函数。相应的译码器称 为最大似然译码器。 )/(max 2, 2, 1 i i i CRpC k )/( i CRp 信息论与编码-最优译码和最大似然译码 由于logx与x是单调关系，因此最大似然 规则也可以写成 称logp(R/C)为对数似然函数。 N j ijj i i

5、 i crpCRp kk 1 2, 2, 12, 2, 1 )/(logmax)/(logmax 信息论与编码-最优译码和最大似然译码 对于DMC信道，如果发送端发送每一个码 字的概率 相等，则一般可认为 MLD就是译码错误概率最小的一种最佳 译码规则。 由于最佳译码要求知道后验概率p(R/C)，这 在很多时候是很困难的，所以经常使用 的是最大似然译码，在很多情况下，可 以认为最大似然译码就是最佳译码。 )( i Cp 信息论与编码-最优译码和最大似然译码 对于BSC信道，在译码的时候，如果我们逐比 特地比较发码和收码，就只有两种可能性： 相同或者不同，其概率分别是： 时 时 jij jij

6、ijj rc rc p p crp 1 )/( 信息论与编码-最优译码和最大似然译码 如果R中有d个码元与 不同，我们称R和 之间的距离为d，这样定义的距离称为汉明 距离。接收码字R和发送码字 之间的汉明 距离，就是二者模2加后的重量，即 i C i C i C N j ijjii crCRWCRdisd 1 )(),( 信息论与编码-最优译码和最大似然译码 此时的似然函数是 因为上述似然函数中 是常数， 可以看出，d越大，则似然函数越小，因此，求 最大似然函数问题就变成了求最小汉明距离问 题。 N d dNd N j ijji p p p ppcrpCRp)1 ( 1 )1 ()/()/(

7、1 N p)1 ( 1)1/( pp 信息论与编码-最优译码和最大似然译码 汉明距离译码是一种硬判决译码。只要在接收端 将接收码R与所有可能的发码逐比特进行比较， 选择其中汉明距离最小的码字作为译码结果 就可以了。当发送的码字互相统计独立且等 概时，汉明距离译码就是最佳译码。 信息论与编码-码距与检错、纠错能力 码距与检错、纠错能力的关系 码距：在随机编码中，我们曾说过，一个码字 可以看作是N维矢量空间的一个点，全部码字 所对应的点集合构成矢量空间的一个子集。子 集的任意两点之间都存在一定的距离，这个距 离叫做码字之间的码距。子集任意两点之间的 码距的最小值记为 。 欧氏距、汉明距 min d

8、 信息论与编码-码距与检错、纠错能力 检错能力：如果信道传输无误，接收到的N重矢量 一定是码字，在矢量空间中一定对应到码字子 集中的一个点上。当传输有误时，可能会发生 两种情况：一是不再对应码字子集上的一点， 而是对应到码字子集点相邻的的另一个空间点 上；第二种可能是仍然对应到码字子集中的一 个点上，但却是一个错误的点上。第一种情况 下，译码的时候一定可以判断出发生了误码； 而第二种情况却不能判断出发生了误码。 信息论与编码-码距与检错、纠错能力 对于一个最小码距为 的码字子集，如果传输 中发生误码后使得空间点的位置偏移小 于 ，则一定可以判断出发生了误码，因 为这时候由于误码不可能从一个空间

9、点偏移到 另一个空间点。换句话说，可以检测到错误。 而当由于误码使空间偏移大于 时，则有可 能偏移到另外的码字点上，也就有可能检不出 该错误来。因此，对于最小码距为 的码 子字集，其检错能力为 。 min d min d min d 1 min d min d 信息论与编码-码距与检错、纠错能力 纠错能力：如果我们采用最佳译码或最大似然译 码，那么当接收到的码字偏离其在N维空间中 原来的位置时，只要偏离得不太远，就可以根 据最大似然译码规则（或最佳译码规则）经过 译码得到正确的结果。但如果偏离得太远，以 至于离另外一个码字的空间点更近一些，则经 过最大似然译码，就会译成另一个码字，也就 是不能

10、纠正误码，或者说超出了该种编码的最 大纠错范围。那么纠错范围是多大呢？ 信息论与编码-码距与检错、纠错能力 我们可以设想以 个码字空间点为球心，分别做 一个超维的球体，且各个球体互不相交，那么， 如果由于误码使空间点的偏移没有超出所对应 的球体，则可以由最大似然译码纠正其错误， 也就是可以纠错。对于最小码距为 的码子 字集，球体半径的最小值为 ，考虑到 纠错能力为整数位，所以纠错能力应该写 为 。 例子:C=(000),(111) k 2 min d 2/ ) 1( min d 2/ ) 1( min d 信息论与编码-码距与检错、纠错能力 联合检错、纠错能力：对于最小码距为 的码字， 其单独

11、的检错能力为 ，单独的纠错能力 为 。 但如果联合考虑检错和纠错，则情况会有所变化，因为 如果单独考虑检错，只要不会偏移到另一个码字空 间点上，都可以检测出来，但当加了纠错以后，如 果偏移值过大，以至于偏移后更接近于另一个码字 空间点（即进入另一个超球体），则由于纠错的原 因，就会把它当成另一个码字，从而进行错误的纠 正（纠错后就认为没有错误了），以至于不能检测 出来其错误。 min d 2/ ) 1( min d 1 min d 信息论与编码-码距与检错、纠错能力 对于一个最小码距为 的码字子集，一般性 的结论是： 其中， 是纠错能力， 是检错能力。 dc cd ee dee 和 1 min c e d e min d 信息论与编码-码距与检错、纠错能力 例如：最小码距为7的码字子集，单独检错可以 检测6个码元的错误，单独纠错可以纠正3个 码元的错误。但如果想纠正3个码元的错误， 其检错能力减小为3，因为如果错误大于3， 就会因为进入另一个超球体的范围而被错误 地纠错。如果想检测4个错误，则纠错能力 要降低为2，也就是说，要把纠错的超球半 径降低为2。如果想检测5个错误，则纠错的 能力要降低为1。 例 重复码 (0000000),(1111111) 信息论与编码-码距与检错、纠错能力 从上面对纠错检错能力的分析可以看出，