信息论与编码原理第六章解说.ppt

本章小结： 译码规则：设信道输入符号集X={ },输出符号集Y={ }。译码规则就是一个译码函数:F(bj)=(i=1,…,r;j=1,…,s)。 设信道的传递矩阵为（其中r=3，s=3） P 联合概率为 ，i=1,2,…,r,j=1,2,…,s。 联合概率矩阵为 P 最大后验概率准则(最小错误概率准则): 选择 ,使 即在收到bj的条件下,发出的是a*的概率最大,就将 bj 译为 a* ,这样就使得最小。 计算 pe的公式为 最大似然译码准则: 收到 bj 后,在信道矩阵的第j列中,译为该列最大那个元素所对应的ai。 编码原则: 选择M个消息所对应的码字时,应使码字集合的dmin尽可能增大。则只要码长n足够大时,就可以使很小,而信息传输率R保持一定。 香农第二定理： 对任意一个离散无记忆平稳信道，设信道容量C，则只要信息传输率RC′, 则对任意给定的正数ε，总存在一种分组长度为n的信道编码方案（n足够大），以小于的错误概率实现可靠通信。反之，RC时不可能找到一种编码，使错误概率pe趋于零。 汉明距离：长度为n的两个符号序列(码字) 和 之间的汉明距离为 和 对应位置上不同码元的个数, 汉明距离记为d( , )。 最小距离：在码集合C中,任意两个码字的汉明距离的最小值叫作该码集C的最小距离。 记作： dmin=min{d(,)；}。 对于线性分组码(n,k), 设dmin为最小汉明距离, 则 (1) 这组码可纠正t个错误dmin≥2t+1。 (2) 这组码可检测出s个错误dmin ≥ s+1。 (3) 这组码可纠正t个错误, 同时可检测出s (st) 个错误dmin ≥ t+s+1。 线性分组码(n,k)的性质: (1) 零向量(0,0,…,0)是一个码字； (2) 任意两个码字之和仍为码字； (3) 任意码字c是G的行向量的线性组合。 校验矩阵H的性质: (1) H与生成矩阵G可以相互转化； (2) 利用H和式 cHT = 0 或 HcT = 0. 判别是否码字； (3) H中列的线性相关性与纠错能力有关系。 伴随式s的性质: (1) s仅与e有关； (2) s用来判别错误: s = 0,无错; s0,出错； (3) e不同,则s不同。 标准阵列译码译码方法: (1) 由接收向量r, 求伴随式s = eHT。 (2) 由s确定ei。 (3) 由ei确定 = r + ei。 构造汉明码校验距阵H的方法: (1) 由已知k，从汉明不等式的等式中求出 ； (2) 在每个码字中，用作为校验位，剩下的位作为信息位。 (3) 用二进制数字表示列, 得到列和r行的H； (4) 用上一步形成的H根据,得出r个校验方程； (5) 将已知的信息代入方程组，然后由此求出校验位,从而确定码字。 循环码：设c是线性分组码的任一码字，如果c经循环移位c = (c1, c2,…, cn-1，cn)→c⑴ = (c2, c3,…, cn-1，cn，c1)后的序列仍然是码字, 那么称该线性分组码为循环码。 卷积码：信道中传输的每个k比特分组仍然眏为n比特分组，但这n比特输出并不仅仅取决于当前k比特输入，而与此前的输入信息比特也有关。 输出与先前输入比特的相关性决定了卷积码的编码器是一个有限状态机。 维特比译码算法: ⑴ 将接收序列分解为t个长度为n的子序列； ⑵ 画出深度为t的网格图，其最后的m级只要画出对应于全零输入序列的路径（因为输入序列的后面要附上km个0）； ⑶ 令i =1，初始全零状态的距离度量值为0； ⑷ 找出网格图上所有连接第i级状态到第i+1级状态的支路，求出接收序列的第i条子序列与它们的距离； ⑸ 将这些距离值添加原先i级状态的度量上，得到（i+1）级状态的累计度量的候选值，（i+1）级上的每个状态都有2k个度量候选值，与到达这一状态的每一条支路相对应； ⑹ 在每个（i+1）级的状态上，选择最小度量候选值所对应的分支称为幸存路径。 同时将最小度量作为（i+1）级的状态上的累计度量； ⑺ 如果i = t，则进入步骤 ⑻，否则i增加1，再回到步骤 ⑷； ⑻ 从终止级全零状态沿幸存路