信息论基础教程8

1、QQ：316566035 定长信源编码定理定长信源编码定理 定理定理5.2 离散无记忆信源的熵为H(S)，若对信源长为N的序列进行定长编码，码符号集 X 中有 r 个码符号，码长为 l，则对于任意 ，只要满足 则当N足够大时，可实现几乎无失真编码，即译码错误概率任意小；反之，如果 则不可能实现几乎无失真编码，即当N足够大时，译码错误概率趋近于1。0 2logH SlNr 22logH SlNrQQ：316566035 编码速率编码速率 定义定义5.6 设熵为H(S)的离散无记忆信源，若对信源的长为N的符号序列进行定长编码，码符号集中码符号个数为r，设码字长为l，定义 比特/信源符号为编码速率编

2、码速率，它表示平均每个信源符号编码后能载荷的最大信息量。 这时，定理5.2的条件可表述为RH(S)+，即编码速率大于信源的熵才能实现几乎无失真编码。2loglRrN QQ：316566035 编码效率编码效率 定义定义5.7 定义 为编码效率编码效率。 ( )( )logH SH SlRrNQQ：316566035 编码效率编码效率 由定理5.2可得最佳编码效率为 。 在已知方差和信源熵的条件下，信源符号序列长度N与最佳编码效率和允许错误概率 的关系为： 当允许错误概率越小，编码效率又要高，那么信源符号序列长度N必须越长在实际情况下，要实现几乎无失真的定长编码，N需要的长度将会大到难以实现。(

3、 ),0( )H SH SEP2222 ( ) ( )( ) (1)iiD I sD I sNHS QQ：316566035 5.3 变长码及变长编码定理变长码及变长编码定理5.3.1 Kraft不等式和不等式和McMillan不等式不等式 定理定理5.3 设信源符号集为 ，码符号集为 ，对信源进行编码，得到的码为 ，码长分别为 。即时码存在的充要条件是 这称为Kraft不等式不等式。 由Kraft不等式可知，给定r和q，只要允许码字长度可以足够长，则码长总可以满足Kraft不等式而得到即时码12 ,qSs ss12 ,rXx xx12,qCw ww12, ,ql ll11iqlirQQ：31

4、6566035 即时码的构造即时码的构造图图：由若干节点以及这些节点之间的边所组成。树树：树是没有回路的图。QQ：316566035 即时码的构造即时码的构造 树中最顶部的节点称为根节点根节点，没有子节点子节点的节点称为叶子节点叶子节点。 根节点的子节点称为一阶节点一阶节点，一阶节点的子节点称为二阶节点二阶节点，依此类推。 在构造即时码的树图中，每个节点最多有r （码符号数）个子节点，在一个节点到其若干子节点的边上分别标注 显然，该树图中，n 阶节点的个数最多为 将从根节点到叶子节点的各条边上的码符号顺次连接，即可得到相应的码字。12,nx xxnr其中nrQQ：316566035 即时码的构

5、造即时码的构造 即时码的树图可以用来译码： 当接收到一串码符号序列后，首先从树的根节点出发，依据接收到的第一个码符号选择应走的第一条路径，如此继续下去，直到叶子节点。 每个即时码均对应一个树图，树图中叶子节点的个数就是码字的个数，从根节点到叶子节点的路径长度就是码长。QQ：316566035 Kraft不等式的证明不等式的证明定理定理5.3 设信源符号集为 ，码符号集为 ，对信源进行编码，得到的码为 ，码长分别为 。即时码存在的充要条件是12 ,qSs ss12 ,rXx xx12,qCw ww12, ,ql ll11iqlirQQ：316566035 Kraft不等式的证明不等式的证明11l

6、lr 阶,个节点121121,1qqqqqqqqqqqqlllllllqllllllllllrrrrrrrrr r阶,个节点但充分性：必要性：类似QQ：316566035 McMillan不等式 定理定理5.4 唯一可译码存在的充要条件是 r为码符号个数， 为码字长度，q为信源符号个数。 11iqlirilQQ：316566035 5.3.2 唯一可译码的判别准则唯一可译码的判别准则 设C为码字集合，按以下步骤构造此码的尾随后缀集合F： (1) 考查C中所有的码字，若 是 的前缀，则将相应的后缀作为一个尾随后缀码放入集合 中； (2) 考查C和 两个集合，若 是 的前缀或 是 的前缀，则将相应

7、的后缀作为尾随后缀码放入集合 中； (3) 即为码C的尾随后缀集合； (4) 若F中出现了C中的元素，则算法终止，返回假(C不是唯一可译码)；否则若F中没有出现新的元素，则返回真。 iWjW1FiFiWCjiWFiiWFjWC1iFiiFFQQ：316566035 例子例子12345677, ,?s s s s s s sa c ad abb bad deb bbcde设消息集合共有 个元素分别被编码为判断是否唯一可译码CF1F2F3F4F5adebdebadcbbcdebcdeadabbbaddebbbcdeQQ：316566035 5.3.2 唯一可译码的判别准则唯一可译码的判别准则 定理

8、定理5.5 一个码是唯一可译码的充要条件是 的并集中没有C中的码字。12,F F QQ：316566035 例子例子12345677, ,?s s s s s s sa c ad abb bad deb bbcde设消息集合共有 个元素分别被编码为判断是否唯一可译码CF1F2F3F4F5adebdebadcbbcdebcdeadabbbaddebbbcdeQQ：316566035 5.3.3 无失真变长编码定理无失真变长编码定理 定义定义5.8 设有信源 编码后的码字分别为 ，各码字相应的码长分别为 定义此码的平均码长平均码长为 显然， 表示每个信源符号平均需用的码元数。 1212( )()(

9、)qqsssSPp sp sp s 12,qw ww12, ,ql ll1( )qiiiLp s l码符号/信源符号LQQ：316566035 编码后信源的信息传输率 定义定义5.9 编码后信源的信息传输率为 即：平均每个码元载荷的信息量。 如果传输一个码符号平均需要t秒时间，则编码后信源每秒钟提供的信息量为 显然， 越小，则 越大，信息传输率就越高。( )()H SRH XL比特/码符号( )tH SRLttRLQQ：316566035 紧致码紧致码 定义定义5.10 对于给定的信源和码符号集，若有一个唯一可译码，其平均码长 小于所有其他唯一可译码，则称这种码为紧致码紧致码或最佳码最佳码。

10、无失真信源编码的核心问题就是寻找紧致码LQQ：316566035 定理定理 定理定理5.6 若一个离散无记忆信源S，熵为H(S)，用拥有r个码符号的码符号集 对S进行无失真编码，则总可以找到一种唯一可译码，其平均码长满足 可以看到，平均码长的极限值与无失真定长信源编码定理中的极限值是一致的。12,rXx xx22( )( )1loglogH SH SLrr QQ：316566035 定理证明定理证明首先估计下界 22211( )logloglogqqiiiiiiH SLrp sp srp s l 2211loglogiqqliiiiip sp sp sr 21logilqiiirp sp s

11、2211loglog0iilqqliiiirp srp sQQ：316566035 定理证明定理证明 2,1.logH SLr 证明上界 即满足的唯一可译码存在 22log,1logiiiip slllr 可以看出 存在唯一的正整数使得 1,iillirp sr 于是 11,1,iqqliiiirp sl从而故可以构造唯一可译码 其码长为 1ilip sr 并且根据得到QQ：316566035 定理证明定理证明 1ilip sr 并且根据得到 12211loglogiqqliiiiip sp sp sr 2211, log1logqqiiiiiirp s lp sp s 即 2,1logH S

12、Lr于是QQ：316566035 5.3.4 香农第一编码定理香农第一编码定理 定理定理5.7 设离散无记忆信源S的信源熵H(S)，它的N次扩展信源 ，其熵 。并用码符号 对信源 进行编码，总可以找到一种唯一可译码，使信源S中每个信源符号所需的平均码长满足 其中 是扩展信源中每个符号的平均码长。12,NnSs ss()NH S12,rXx xxNS( )( )1loglogNLH SH SrNrNNLQQ：316566035 编码后信道的信息传输率信息传输率 定义定义5.11 编码后信道的信息传输率信息传输率为 这里， ，所以 2( )logNLH SLNr2logRr( )H SRL比特/码

13、符号比特/信源符号码符号/信源符号( )H SLQQ：316566035 编码后信道的信息传输率信息传输率 无失真信源编码的实质就是对离散信源进行适当变换，使变换后新的码符号信源(信道的输入)尽可能为等概率分布，使新信源的每个码符号平均所含的信息量达到最大，从而使信道的信息传输率R达到信道容量，实现信源与信道理想的统计匹配。这就是香农第一定理的物理意义。QQ：316566035 编码效率编码效率 定义定义5.12 设对信源S进行无失真编码所得到的平均码长为 ，则 ，定义 为编码效率编码效率， 对同一信源来说，码的平均码长 越短，越接近极限 ，信道的信息传输率越高，越接近无噪无损信道的信道容量，这时也越接