《最大似然译码.docx》由会员分享，可在线阅读，更多相关《最大似然译码.docx（7页珍藏版）》请在三一办公上搜索。
1、最大似然译码分组码定义：将信源的信息序列按照独立的分组进行处理和编码，称为分组码。编码时将每k个信息位分为一组进行独立处理，变换成长度为n的二进制码组。 简单实用编码包括奇偶监督码、二维奇偶监督码、恒比码、正反码，其中奇偶监督码和分组码又同属于代数码。分组码一般用符号表示，其中n是码组的总位数，又成为码组的长度，k是码组中信息码元的数目，nk= r 为码组中的监督码元数目。在分组码中，把码组中“1”的个数目称为码组的重量，简称码重。把两个码组中对应位上数字不同的位数称为码组的距离，简称码距。码距又称汉明距离。 最大似然译码 前面我们介绍了信道编码的基本概念，下面将详细分析有关译码的一些理论依据
2、。 M = 输入编码器C = 输出图5-6 信道编码器结构框图 已知信道编码器的框图如图5-6所示，设任一个信息序列M是一个k位码元的序列，通过编码器按一定的规律产生若干监督元，形成一个长度为n的序列即码字(一种按特定规则排列并具有唯一含义的码序列)，每一个信息序列将形成不同的码字与之对应，在二进制下，k长序列共有2k种组合，因此编码输出的码字集合共有2k个码字，而二进制下的n重共有2n种，显然编码输出的码字仅是所有二进制n重中的一部分，编码实际上就是从这2n种不同的n重数组中按一定规律选出2k个n重代表2k个不同的信源原始信息。 经编码后产生的(n,k)码送信道传输，由于信道干扰的影响将不可
3、避免地发生错误，这种错误有两种趋势： 许用码字变成禁用码组，这种错误一旦出现，由于接收到的码组不在编码器输出的码字集合中，译码时可以发现，所以这种错误模型是可检出的。 许用码字变成许用码字，即发端发生某一码字Ci经传输后错成码集中的另一码字Cj，这时收端无法确认是否出错，因此这是一种不可检出的错误模型。 可见，一个n重二进制码字C在传输中由于信道干扰的影响，到接收端可能变成2n种n重中的任一个，为了能在接收端确认发送的是何消息，就需要建立一定的判决规则以获得最佳译码。一般来说，译码器要完成比编码器更为复杂的运算，译码器性能的好坏、速度的快慢往往决定了整个差错控制系统的性能和成本。译码正确与否的
4、概率主要取决于所使用的码、信道特征及译码算法。对特定码类如何寻找译码错误概率小、译码速度快、设备简单的译码算法，是纠错编码理论中一个重要而实际的课题。下面我们讨论当码类和信道给定时，应采用什么样的算法使译码错误概率最小。 由图5-2可知，信道输出的R是一个二进制序列，而译码器的输出是一个信息。 序列M的估值序列M译码器的基本任务就是根据接收序列R和信道特征，按照一套译码规则，由接收序列R。给出与发送的信息序列M最接近的估值序列M由于M与码字C之间存在一一对应关系，。= C时，M = M，所以这等价于译码器根据R产生一个C的估值序列C显然，当且仅当C这时译码器正确译码。 C，则译码器产生了错误译
5、码。之所以产生错误译码是由于：首如果译码器输出的C先，信道干扰很严重，超过了码本身的纠错能力；其次，由于译码设备的故障。 当给定接收序列R时，译码器的条件译码错误概率定义为 C | R) P(E | R)= P(C所以译码器的错误译码概率 PE = P(E|R)P(R) RP(R)是接收序列R的概率，与译码方法无关，所以译码错误概率最小的最佳译码规则是使 CR) minP=minP(ER)=minP(CERRCR)maxP(C=CR) minP(Ci = C | R）因此，如果译码器对输入的R，能在2k个码字中选择一个使P(C最大的码字Ci作为C的估值序列C称这种译码规则为最大后验概率译码。
6、由贝叶斯公式 P(Ci|R)=P(Ci)P(R|Ci) P(R)可知，若发端发送每个码字的概率P(Ci)均相同，且由于P(R)与译码方法无关，所以 maxP(Ci|R)maxkP(R|Ci) i=1,2,.,2ki=1,2,.,2对DMC而言 P(R|Ci)=这里码字 Ci = i=1，2，2 k 一个译码器的译码规则若能在2k个码字C中选择某一个C i并使式成为最大，则这种译码规则称为最大似然译码，P(R|C)称为似然函数，相应的译码器称为最大似然译码器。由于logbx与x是单调关系，因此式与式可写成 |cij）i=1，2，2kmaxlogbP(R|Ci)=maxk i=1，22logP(r
7、bj=1nj|cij) 称logbP(R|C)为对数似然函数或似然函数。对于DMC信道，MLD是使译码错误概率最小的一种最佳译码方法，但此时要求发端发送每一码字的概率P(Ci)均相等，否则MLD不是最佳的。在以后的讨论中，都认为P(Ci)均近似相等，因而MLD算法是一种最佳的译码算法。 例5.1 一个码由00000，00111，11100与11011四个码字组成。每个码字可用来表示四种可能的信息之一。可以算出该码的最小距离d 0 = 3，由定理5.3可知，它可纠正在任何位上出现的单个误码。同时我们注意到，码长为5的二进制码组共有2 5=32种可能的序列，除了上述4个许用码组外，其余28个为禁用
8、码组。为了对该码进行纠错处理，需将28种禁用码组的每一个与4种许用码字作“最邻近性”的比较。这种处理意味着要建立一个“译码表”，所以译码的本质就是对码组进行分类，即先将所有与每个许用码字有一位差错的各个可能接收序列列在该码字的下面，这样，就得到表5-1中以虚线围起的部分。除了这一部分之外，我们应注意到尚有8个序列未被列入。这8个序列与每个码字至少差二位。但是，它们与上述序列不同，没有惟一的方法可把它们安排到表内。例如，既可将序列10001放在第4列，也可将它放在第l列。在译码过程中使用此表时，可将所接收序列与表内各列对照，当查到该序列时，将该列第一行的码字作为译码器的输出。 表5-1 四个码字
9、的译码表 00000 10000 01000 00100 00010 00001 10001 10010 11100 01100 10100 11000 11110 11101 01101 01110 00111 10111 01111 00011 00101 00110 10110 10101 11011 01011 10011 11111 11001 11010 01010 01001 用这种方式建立的表具有很大的优点。设信道误比特率为Pe，出现任何一种具有i个差i5-i1/2，即信道的信噪比足够大时，可以看到： 错特定模式的概率是Pe(1Pe)。当Pe Pe(1Pe)4 Pe(1Pe)
10、即不出错概率大于出错概率；一个特定的单个差错模式要比一个特定的两个差错模式更容易出现。因此，译码器将所收到的一个特定码组译为在汉明距离上最邻近的一个码字时，实际上是选择了最可能发送的那个码字。这就是MLD的具体应用，它实际上就是根据接收序列R，在2k个码字集中，寻找与R的汉明距离最小的码字Ci，作为译码输出，因为它最可能是发送的码字。这种译码方法又称为最小汉明距离译码，执行这种译码规则的译码器就叫做最大似然译码器。在上述条件下，其序列差错概率最小。当用译码表进行译码时，为了实现最大似然译码，可用上述方法列表对码字进行分类。但遗憾的是，表的大小随码组长度按指数关系增加，故对长码来说，直接使用译码表是不切合实际的。但对说明分组码的某些重要性质而言，译码表仍是一种很有用的概念性工具。
