最大似然译码

1、分组码 k义：将信源的信息序列按照独立的分组进行处理和编码，称为分组码。编码时将每k个信息位分为一组进行独立处理，变换成长度为 n （n>k）的 二进制码组。简单实用编码包括奇偶监督码、二维奇偶监督码、包比码、正反码，其中奇偶监 督码和分组码乂同届丁代数码。分组码一般用符号（n, k）表示，其中n是码组 的总位数，乂成为码组的长度（码长），k是码组中信息码元的数目，n- k= r为 码组中的监督码元数目。在分组码中，把码组中“ 1”的个数目称为码组的重量， 简称码重。把两个码组中对应位上数字不同的位数称为码组的距离，简称码距。 码距乂称汉明距离。最大似然译码前面我们介绍了信道编码的基本概

2、念，下面将详细分析有关译码的一些理论依据。M =(mk-i ,mi mo)C = (Ck-1 ,ci co)输出输入图5-6信道编码器结构框图已知信道编码器的框图如图 5-6所示，设任一个信息序列 M是一个k位码元的序列，通 过编码器按一定的规律 （编码规则）产生若干监督元， 形成一个长度为 n的序列（n重数组） 即码字（，种按特定规则排列并具有唯一含义的码序列 |）,每一个信息序列将形成不同的码字 与之对应，在二进制下，k长序列共有2k种组合，因此编码输出的码字集合共有2*个码字，而二进制下的n重共有2n种，显然编码输出的码字仅是所有二进制n重中的一部分，编码实际上就是从这2种不同的n重数组

3、中按一定规律（编码规则）选出2k个n重代表2k个不同的信源原始信息。经编码后产生的（n,k）码送信道传输，由于信道干扰的影响将不可避免地发生错误，这种 错误有两种趋势： 许用码字变成禁用码组，这种错误一旦出现，由于接收到的码组不在编码器输出的码 字集合中，译码时可以发现，所以这种错误模型是可检出的。 许用码字变成许用码字，即发端发生某一码字G经传输后错成码集中的另一码字Cj,这时收端无法确认是否出错，因此这是一种不可检出的错误模型。可见，一个n重二进制码字C在传输中由于信道干扰的影响，到接收端可能变成2n种n重中的任一个，为了能在接收端确认发送的是何消息，就需要建立一定的判决规则以获得最佳译码

4、。一般来说，译码器要完成比编码器更为复杂的运算，译码器性能的好坏、速度的快慢往往决定了整个差错控制系统的性能和成本。译码正确与否的概率主要取决于所使用的 码、信道特征及译码算法。对特定码类如何寻找译码错误概率译码算法，是纠错编码理论中一个重要而实际的课题。下面我们讨论当码类和信道给定时，由图5-2可知，信道输出的R是一个二(或q)进制序列，而译码器的输出是一个信息 序列M的估值序列M?。译码器的基本任务就是根据接收序列R和信道特征，按照一套译码规则，由接收序列R给出与发送的信息序列 M最接近的估值序列 M?。由于M与码字C之间存在一一对应关系， 所以这等价于译码器根据R产生一个C的估值序列C。

5、显然，当且仅当C?= C时，M? = M,这时译码器正确译码。如果译码器输出的 C?则译码器产生了错误译码。之所以产生错误译码是由于：首先，信道干扰很严重，超过了码本身的纠错能力；其次，由于译码设备的故障(这点本书不 予讨论)。当给定接收序列R时，译码器的条件译码错误概率定义为P(E | R)= P(C?乒C | R)所以译码器的错误译码概率Pe =、 P(E|R)P(R)RP(R)是接收序列R的概率，与译码方法无关，所以译码错误概率最小的最佳译码规则是使min Pe =min P(E R) =min P(? =C R) RRmin P(? #C R)n maxP(? = C R)(5-1)因

6、此，如果译码器对输入的 R,能在2k个码字中选择一个使 P(C?i = C | R) (i = 1, 2, 2k)最大的码字Ci作为C的估值序列C?,则这种译码规则一定使译码器输出错误概率最小， 称这种译码规则为最大后验概率译码。由贝叶斯公式pP(Ci)P(R|G)P(R)可知，若发端发送每个码字的概率P(Ci)均相同，且由于P(R)与译码方法无关，所以maxP(G|R)n maXkP(R|G) (5-2)' iJ,2，,2ki；对DMC而言nP(R|Ci)=H p( rj|Cij)(5-3)这里码字 Ci = (Cii, G2, , Cin) i=1, 2,，2 k一个译码器的译码规

7、则若能在2k个码字C中选择某一个C i并使式(5-2)成为最大，则这种译码规则称为 最大似然译码(MLD ), P(R|C)称为似然函数，相应的译码器称为 最大 似然译码器。由于logbX与x是单调关系，因此式(5-2)与式(5-3)可写成ni2k logb P(R|Ci) = iJT2ax2 logbP(rj |Cj) (5-4)称logbP(R|C)为对数似然函数或似然函数。对于 DMC信道，MLD是使译码错误概率最小 的一种最佳译码方法，但此时要求发端发送每一码字的概率P(Ci) (i = 1 , 2,，2k)均相等，否则MLD不是最佳的。在以后的讨论中，都认为P(G)均近似相等，因而

8、MLD算法是一种最佳的译码算法。例5.1 一个码由00000 , 00111, 11100与11011四个码字组成。每个码字可用来表示 四种可能的信息之一。可以算出该码的最小距离d0 = 3,由定理5.3可知，它可纠正在任何位上出现的单个误码。同时我们注意到，码长为5的二进制码组共有 2 5=32种可能的序列，除了上述4个许用码组外，其余28个为禁用码组。为了对该码进行纠错处理，需将28种禁用码组的每一个与 4种许用码字作“最邻近性”的比较。这种处理意味着要建立一个“译码表”，所以译码的本质就是对码组进行分类，即先将所有与每个许用码字有一位差错的各个 可能接收序列列在该码字的下面，这样，就得到

9、表5-1中以虚线围起的部分。除了这一部分之外，我们应注意到尚有 8个序列未被列入。 这8个序列与每个码字至少差二位。但是， 它 们与上述序列不同， 没有惟一的方法可把它们安排到表内。例如，既可将序列10001放在第4列，也可将它放在第l列。在译码过程中使用此表时，可将所接收序列与表内各列对照， 当查到该序列时，将该列第一行的码字作为译码器的输出。表5-1四个码字的译码表000001110000111110111000001100101110101101000101000111110011001001100000011111110001011110001011100100001111010011

10、0110101000101101101100101010010011101010101001用这种方式建立的表具有很大的优点。设信道误比特率为 Pe,出现任何一种具有i个差错特定模式的概率是 pei(1- Pe)5-i°当Pe < 1/2 ，即信道的信噪比足够大时，可以看到：(1- Pe)5 > Pe(1- Pe)4 > R2-(1- Pe)3 > ,即不出错概率大于出错概率；一个特定的单个差错模式要比一个特定的两个(或多个)差错模式更容易出现。因此，译码器将所收到的一个特定码组译为在汉明距离上最邻近的一个码 字时，实际上是选择了最可能发送的那个码字(设各个码字的发送机会相同)。这就是MLD的具体应用，它实际上就是根据接收序列R,在2k个码字集中，寻找与 R的汉明距离最小的码字 G,作为译码输出，因为它最可能是发送的码字。这种译码方法又称为最小汉明距 离