发布时间 : 星期二 文章信息理论与编码课后答案第5章更新完毕开始阅读d0cbd8dc18e8b8f67c1cfad6195f312b3169ebd4
对于二元对称信道，设信源有M个消息{s1,s2,,sM}，输入和输出符号集分别为A?{0,1}和,?2N},?2N}B?{0,1}，其N次扩展信道的入口符号集AN和出口符号集BN中都含有2N个N长二元符号串，即
AN?{?1,?2,B?{?1,?2,从A中选择M个符号串当作码字组成码C：
NN
C?{c1,c2,,cM}
按极大似然译码规则进行译码时，可以推导出等价于以下规则，称为最小（汉明）距离译码规则：
*N?F(?)?c?C,??Bjjj? （5.9） F:?*N??D(ci,?j)??,ci?C?A?D(cj,?j)?min?其含意是：将接收序列?j译为与之最相似的输入序列（码字）c*j。
5.2.5有噪信道编码定理（香农第二定理）
5.2.5.1有噪信道编码定理
若信道是离散、无记忆、平稳的，且信道容量为C，只要待传送的信息率R?C，就一定能找到一种信道编码方法，使得码长N足够大时，平均差错率Pe任意接近于零。 有噪信道编码定理实际上是一个存在性定理，它指出：在R?C时，肯定存在一种好的信道编码方法，用这种好码来传送消息可使Pe逼近零。但香农并没有给出具体编码方法。 对有噪信道编码定理的证明要用到联合典型序列。所谓典型序列，是指那些平均自信息量逼近熵的序列。联合?典型序列，是指那些平均联合自信息量逼近联合熵的序列。
离散无记忆信源X发出N长序列xi?xi1xi2xiN，若
I(xi)?H(X)?? （5.10） N则称xi为X的?典型序列，否则称为X的非?典型序列。
若xi和yj分别是X和Y的N长?典型序列，且
I(xi,yj)N?H(XY)?? （5.11）
则称序列对(xi,yj)为X与Y的联合?典型序列，否则称为非联合?典型序列。 5.2.5.2有噪信道编码逆定理
若信道是离散、无记忆、平稳的，且信道容量为C，如果信息率R?C，则肯定找不到一种信道编码方法，使得码长N足够大时，平均差错率Pe任意接近于零。
对有噪信道编码逆定理的证明，要用到Fano不等式。
Fano不等式：
H(X|Y)?H(Pe,1?Pe)?Pelog(r?1) （5.12）
式中r是信道输入符号个数。
5.2.6 线性分组码
5.2.6.1 基本概念
信道编码的目的是为了降低平均差错率。纠错编码理论几乎与信息论同时创立，创始人是汉明
（R.W.Hamming），他与信息论创始人香农都在贝尔实验室工作。
纠错编码的基本思路是在信息序列中引入可控冗余，或称校验码元，组成一个相关的码元序列——码字，译码时利用码元之间的相关性质来检测错误和纠正错误。
分组码：先将信息序列分成K个符号一组，称为信息组，然后在信息组中加入一些校验码元组成N长码字，由此得到的码称为(N,K)分组码，校验位数目为r?N?K。
线性码：线性码满足线性特性，即码中任意两个码字的和仍为码字。否则为非线性码。
循环码：循环码是线性码的一个子集。循环码中任一码字循环移位后仍为该码的码字。否则为非循环码。
5.2.6.2 生成矩阵和校验矩阵
编码函数f可用矩阵表示成
c?mG （5.13）
其中m是K维信息组行矩阵，c是N维码字行矩阵，G是码的生成矩阵。
m??m1m2c??c1c2mK?,mi?{0,1} （5.14） cN?,ci?{0,1} （5.15）
通过生成矩阵，可将信息组变换为相应的码字。
如果码字的前（或后）K位照搬信息组的K个信息元，这样形成的码称为系统码。 对于前K位为信息元的系统码，生成矩阵G可分块成
G??IK?K?10?01AK?r???????0000a11a21a12a22aK21aK1a1r?a2r?? （5.16） ??aKr??校验方程的矩阵形式则为
cHT?0或HcT?0 （5.17）
式中H为r?N一致性校验矩阵，r?N?K为校验位数目。
5.2.6.3 汉明距离和码的纠检错能力的关系
(1) 一个码能够检测出td个错误的充要条件是dmin?td?1； (2) 一个码能够纠正tc个错误的充要条件是dmin?2tc?1；
(3) 一个码能够纠正tc个错误，同时又能够检测出td?tc个错误的充要条件是
dmin?2tc?1和dmin?tc?td?1。
其中，dmin表示码的最小汉明距离，是衡量其纠、检错能力的重要参数。 5.2.6.4 伴随式与伴随式译码
用一致性校验矩阵H对接收序列y进行检验，检验结果记为s，则
s=yHT?(c+e)HT?eHT （5.18）
式中c为发送码字。如果s?0，则表明有错误存在。s是传输是否出错的标志，称为伴随式。e称为差错图样。当码字第i位发生错误时，ei?1，否则ei?0。
?： 通过接收序列y可以确定发送码字c的估计值c?=y?e=y?e （5.19） c
教材习题参考答案
5.1 译码规则与错误概率
5.1.1 （陈杰，红皮书，p139，例5.1）
?0.5?例5.1 已知信道矩阵P??0.2??0.30.30.2?0.30.5??，求pE。 0.30.4?? 解：根据极大似然译码准则选择译码函数B
?F?b1??a1? B：?F?b2??a3
?F?b??a2?3又设输入符号为等概率分布p?a??则有
pE?11p?ba??[?0.2?0.3???0.3?0.3???0.2?0.4?]?3Y,X?a?3
1 3 =0.567
若按下述译码函数A计算平均错误概率p?E
?F?b1??a1?A： ?F?b2??a2 ?F?b??a33?得
p?E?1p?ba? ?3Y,X?a?1 ?[?0.2?0.3???0.3?0.3???0.2?0.5?]?0.600
3可见p?E?pE (平均错误概率)，即得以下结论：
（1） 平均错误概率pE与译码规则有关； （2） 极大似然译码准则B优于A。
?，用2元11100,01001,10010,001115.1.2（原5.3）设码为C??c1,c2,c3,c4???对称信道传送（错误概率p?0.01）。如果码字概率为
?Pc???0.50.1250.1250.25?，试找出一种译码规则，使平均差错率pe最
小。 答案：王虹老师 5.2 两种典型的译码规则
5.2.1 （原5.1） 设有DMC其转移矩阵如下
?121316??161213?P? YX?? ??131612????若信道输入概率为?PX???0.50.250.25?，试确定最佳译码规则和极大似然译码规则并计算出相应的平均差错率。 答案：王虹老师 解：
11?P(x1)?,P(x2)?P(x3)?，
24?1?4??1?信道的联合概率矩阵为?24?1??1211?612??11?812? 11??248?根据最小错误概率准则（其实就是最大联合概率译码准则），在联合概率矩阵中，每列选一最大值（矩阵中带下划线的值），译为