第五章 信源编码（第十讲）
（2课时）
主要内容：（1）编码的定义（2）无失真信源编码 重点：定长编码定理、变长编码定理、最佳变长编码。
难点：定长编码定理、哈夫曼编码方法。
作业：5。2，5。4，5。6；
说明：本堂课推导内容较多，枯燥平淡，不易激发学生兴趣，要注意多讨论用途。另外，注意，解题方法。多加一些内容丰富知识和理解。
通信的实质是信息的传输。而高速度、高质量地传送信息是信息传输的基本问题。将信源信息通过信道传送给信宿，怎样才能做到尽可能不失真而又快速呢？这就需要解决两个问题：第一，在不失真或允许一定失真的条件下，如何用尽可能少的符号来传送信源信息；第二，在信道受干扰的情况下，如何增加信号的抗干扰能力，同时又使得信息传输率最大。为了解决这两个问题，就要引入信源编码和信道编码。
一般来说，提高抗干扰能力（降低失真或错误概率）往往是以降低信息传输率为代价的；反之，要提高信息传输率常常又会使抗干扰能力减弱。二者是有矛盾的。然而在信息论的编码定理中，已从理论上证明，至少存在某种最佳的编码或信息处理方法，能够解决上述矛盾，做到既可靠又有效地传输信息。这些结论对各种通信系统的设计和估价具有重大的理论指导意义。
§3.1 编码的定义
编码实质上是对信源的原始符号按一定的数学规则进行的一种变换。
讨论无失真信源编码，可以不考虑干扰问题，所以它的数学描述比较简单。图3.1是一个信源编码器，它的输入是信源符号},,,{21q s s s S =，同时存在另一符号},,,{21r x x x X =，一般来说，元素xj 是适合信道传输的，称为码符号（或者码元）。编码器的功能就是将信源符号集中的符号s i （或者长为N 的信源符号序列）变换成由x j (j=1,2,3,…r)组成的长度为l i 的一一对应的序列。
输出的码符号序列称为码字，长度l i 称为码字长度或简称码长。可见，编码就是从信源符号到码符号的一种映射。若要实现无失真编码，则这种映射必须是一一对应的，并且是可逆的。
码符号的分类： 下图是一个码分类图
?
?
?
???
???
????
??
?
?
????
?即时码（非延长码）非即时码
唯一可译码非唯一可译码
非奇异码奇异码分组码非分组码码
下面，我们给出这些码的定义。 1. 二元码
若码符号集为X={0;1}，所有码字都是一些二元序列，则称为二元码。二元码是数字通信和计算机系统中最常用的一种码。
2. 等长码：
若一组码中所有码字的码长都相同，即l i =l(i=1,2,…q)，则称为等长码。 3. 变长码：
若一组码组中所有码字的码长各不相同，则称为变长码。 4. 非奇异码：
若一组码中所有码字都不相同，则称为非奇异码。 5. 奇异码：
若一组码中有相同的码字，则称为奇异码。 6. 唯一可译码：
若码的任意一串有限长的码符号序列只能唯一地被译成所对应的信源符号序列，则此码称为唯一可译码，否则就称为非唯一可译码。
7. 非即时码和即时码：
如果接收端收到一个完整的码字后，不能立即译码，还要等下一个码字开始接收后才能判断是否可以译码，这样的码叫做非即时码。
如果收到一个完整的码字以后，就可以立即译码，则叫做即时码。即时码要求任何一个码字都不是其他码字的前缀部分，也叫做异前缀码。
码树：
即时码的一种简单构造方法是树图法。对给定码字的全体集合C={W 1,W 2,…W q }来说，可以用码树来描述它。所谓树，就是既有根、枝，又有节点，如图5.2（80业）所示，图中，最上端A 为根节点，A 、B 、
C 、
D 、
E 皆为节点，E 为终端节点。A 、B 、C 、D 为中间节点，中间节点不安排码字，而只在终端节点安排码字，每个终端节点所对应的码字就是从根节点出发到终端节点走过的路径上所对应的符号组成，如图5.2中的终端节点E ，走过的路径为ABCDE ，所对应的码符号分别为0、0、0、1，则E 对应的码字为0001。可以看出，按树图法构成的码一定满足即时码的定义（一一对应，非前缀码）。
从码树上可以得知，当第i 阶的节点作为终端节点，且分配码字，则码字的码长为i 。
任一即时码都可以用树图法来表示。当码字长度给定后，用树图法安排的即时码不是唯一的。如图3.2中，如果把左树枝安排为1，右树枝安排为0，则得到不同的结果。
对一个给定的码，画出其对应的树，如果有中间节点安排了码字，则该码一定不是即时码。
每个节点上都有r 个分支的树称为满树，否则为非满树。
即时码的码树图还可以用来译码。当收到一串码符号序列后，首先从根节点出发，根据接收到的第一个码符号来选择应走的第一条路径，再根据收到的第二个符号来选择应走的第二条路径，直到走到终端节点为止，就可以根据终端节点，立即判断出所接收的码字。然后从树根继续下一个码字的判断。这样，就可以将接收到的一串码符号序列译成对应的信源符号序列。
?
克拉夫特（Kraft ）不等式
定理3.1 对于码符号为X={x 1,x 2,…x r }的任意唯一可译码，其码字为W 1,W 2,…W q ，所对应的码长为l 1,l 2…l q ，则必定满足克拉夫特不等式
11
≤∑=-q
i l i
r
反之，若码长满足上面的不等式，则一定存在具有这样码长的即时码。
注意：克拉夫特不等式只是说明唯一可译码是否存在，并不能作为唯一可译码的判据（可以排除，不能肯定）。如{0，10，010，111}满足克拉夫特不等式，但却不是唯一可译码。
例题：设二进制码树中X={x 1,x 2,x 3,x 4}，对应的l 1=1,l 2=2,l 3=2,l 4=3，由上述定理，可得
18
92
2
2
2
2
3
2
2
1
4
1
>=
+++=----=-∑i l i
因此不存在满足这种码长的唯一可译码。可以用树码进行检查。
?
唯一可译码的判断法（变长）：
将码C 中所有可能的尾随后缀组成一个集合F ，当且仅当集合F 中没有包含任一码字，则可判断此码C 为唯一可译码。
集合F 的构成方法：
首先，观察码C 中最短的码字是否是其它码字的前缀，若是，将其所有可能的尾随后缀排列出。而这些尾随后缀又有可能是某些码字的前缀，再将这些尾随后缀产生的新的尾随后缀列出，
然后再观察这些新的尾随后缀是否是某些码字的前缀，再将产生的尾随后缀列出，依此下去，直到没有一个尾随后缀是码字的前缀为止。这样，首先获得了由最短的码字能引起的所有尾随后缀，接着，按照上述步骤将次短码字、…等等所有码字可能产生的尾随后缀全部列出。由此得到由码C 的所有可能的尾随后缀的集合F 。
例题：设码C={0,10,1100,1110,1011,1101}，根据上述测试方法，判断是否是唯一可译码。
解：1. 先看最短的码字：“0”，它不是其他码字前缀，所以没有尾随后缀。 2. 再观察码字“10”，它是码字“1011”的前缀，因此有尾随后缀。
所以，集合F={11，00，10，01}，其中“10”为码字，故码C 不是唯一可译码。 §3.2 定长编码定理
前面已经说过，所谓信源编码，就是将信源符号序列变换成另一个序列（码字）。设信源输出符号序列长度为L ，码字的长度为K L ，编码的目的，就是要是信源的信息率最小，也就是说，要用最少的符号来代表信源。
在定长编码中，对每一个信源序列，K L 都是定值，设等于K ，我们的目的是寻找最小K 值。要实现无失真的信源编码，要求信源符号X i (i=1,2,…q)与码字是一一对应的，并求由码字组成的符号序列的逆变换也是唯一的（唯一可译码）。
定长编码定理：
由L 个符号组成的、每个符号熵为H L (X)的无记忆平稳信源符号序列X 1X 2X 3…X L 用K L 个符号Y 1Y 2…Y K L （每个符号有m 种可能值）进行定长变码。对任意0,0>>δε，只要
ε+≥)(log X H m L
K L L 则当L 足够大时，必可使译码差错小于δ；反之，当 ε2)(log -≤X H m L
K L L
时，译码差错一定是有限值，当L 足够大时，译码几乎必定出错。 式中，左边是输出码字每符号所能载荷的最大信息量
所以等长编码定理告诉我们，只要码字传输的信息量大于信源序列携带的信息量，总可以实现几乎无失真的编码。条件时所取得符号数L 足够大。
设差错概率为εP ，信源序列的自方差为 2
2
)]}()({[)(X x I E X i -=σ
则有： 2
2
)(ε
σεL X P ≤
当)(2X σ和2
ε均为定值时，只要L 足够大，εP 可以小于任一整数δ，即
δε
σ≤2
2
)(L X
此时要求： δ
εσ2
2
)(X L ≥
只要δ足够小，就可以几乎无差错地译码，当然代价是L 变得更大。
令
m L K K L log =
为码字最大平均符号信息量。 定义编码效率为： K
X H L )(=
η
最佳编码效率为 ε
η+=
)()(X H X H L L
无失真信源编码定理从理论上阐明了编码效率接近于1的理想编码器的存在性，它使输出符号的信息率与信源熵之比接近于1，但要在实际中实现，则要求信源符号序列的L 非常大进行统一编码才行，这往往是不现实的。
例如：
例题：设离散无记忆信源概率空间为
??
?
???=??????04.005
.006
.007
.01
.01
.018
.04
.087654321x x x x x x x x P X 信源熵为
符号/55.2log
)(8
1
2
bit p p X H i i i =-=∑=
自信息方差为
82
.7)]([)(log
)]
([log
)(2)(log }
)]([log
)(2){(log )]
(log
[})]()({[)(8
1
2
22
8
18
1
8
1
2
2
2
2
8
12
2
2
2
8
12
2
2
2=-=
++=++=--=
-=∑
∑
∑∑
∑
∑
======i i i i i i i
i i i i i i i i i i i i X H p p p X H p p X H p p X H p X H p p X H p p X H x I E X σ 对信源符号采用定长二元编码，要求编码效率%90=η，无记忆信源有)()(X H X H L =，因此%90)()(=+=
ε
ηX H X H
可以得到28.0=ε
如果要求译码错误概率6
10
-≤δ，则8
72
2
10108.9(≈?=≥
δ
εσ）X L
由此可见，在对编码效率和译码错误概率的要求不是十分苛刻的情况下，就需要
8
10=L 个信源符号一起进行编码，这对存储和处理技术的要求太高，目前还无法实现。
如果用3比特来对上述信源的8个符号进行定长二元编码，L=1，此时可实现译码无差错，但编码效率只有2.55/3=85%。因此，一般说来，当L 有限时，高传输效率的定长码往往要引入一定的失真和译码错误。解决的办法是可以采用变长编码。
§3.3 最佳编码
最佳码：对于某一信源和某一码符号集来说，若有一唯一可译码，其平均码长K 小于所有其他唯一可译码的平均长度。为此必须将概率大的信息符号编以短的码字，概率小的符号编以长的码字，使得平均码字长度最短。
能获得最佳码的编码方法： 香农（Shannon ） 费诺（Fano ） 哈夫曼（Huffman ） 1、香农编码方法
香农第一定理指出了平均码长与信源之间的关系，同时也指出了可以通过编码使平均码长达到极限值，这是一个很重要的极限定理。
香农第一定理指出，选择每个码字的长度K i 满足下式： K i = [i
p 1log
]——取整
即： －log 2p i ≤K i ≤1－log 2p i 就可以得到这种码。这种编码方法称为香农编码。 例：设无记忆信源的概率空间为：
????
??
????=??????818
14
12
1)(4321u u u u
u p U 计算各符号的码字长度： K 1= log2=1 K 2= log4=2 K 3= K 4 =log8=3
用图示码树，可得各自的码字：
u 1:（0），u 2:（10），u 3:（110），u 4:（111） 信息熵H(U):
75
.14
78
1log
8
18
1log
8
14
1log
4
12
1log
2
1)
(log )()(4
1
==-
-
-
-=-=∑=i i i u p u p U H
信源符号的平均码长:
75.1238
1241121=??+
?+
?=
K
编码效率
%10075
.175.1)(==
=
K
U H η
对于这种信源，香农编码是最佳编码。码树达到满树。
香农编码法多余度稍大，实用性不大，但有重要的理论意义。 编码方法如下：
⑴ 将信源消息符号按其出现的概率大小依次排列 p(u 1)≥p(u 2)≥…≥ p(u n ) ⑵ 确定码长K i (整数) ： K i = [i
p 1log
]——取整
⑶ 为了编成唯一可译码，计算第i 个消息的累加概率
∑
-==
1
1
)(i k k i u p p
⑷ 将累加概率P i 变换成二进制数。
⑸ 取p i 二进制数的小数点后K i 位即为该消息符号的二进制数。 例： ???
??
?=?
???05.005.02.03.04.0)(54321u u u u u u p U
以i = 3为例，计算各符号的码字长度： K 3 = [－log0.2] = 3
累加概率P 4 = 0.7 —— 0.10110… —— 101
由图，这些码字没有占满所有树叶，所以是非最佳码。
95
.105
.0log 05.022.0log 2.03.0log 3.04.0log 4.0)(=?----=U H 平均码长：
5
.22505.032.023.024.0)(5
1
=??+?+?+?==
∑
=i i
i K u p K 编码效率：
%785
.295.1)(==
=
K
U H η
为了提高编码效率，首先应达到满树；例如把u 4u 5换成A 、B 这些前面的节点，就可减小平均码长。所以不应先规定码长，而是由码树来规定码字，可得更好的结果。
2、费诺编码方法
费诺编码属于概率匹配编码，但它不是最佳的编码方法。编码过程如下：
⑴将信源符号接概率值分为两大组，使两个组的概率之和近于相同，并对各组赋予一个二进制码元“0”和“1”。
⑵将每一大组的信源符号进一步再分成两组，使划分后的两个组的概率之和近于相同，并又赋予两个组一个二进制符号“0”和“1”。
⑶如此重复，直至每个组只剩下一个信源符号为止。 信源符号所对应的码字即为费诺码。 例： ???
??
?=??????05.005.02.03.04.0)(54321u u u u u u p U
该费诺码的平均码长
1
.2)305.0(222.023.024.0)(7
1
=??+?+?+?==
∑
=i i
i K u p K
编码效率：
.%931
.295.1)(==
=
K
U H η
显然，费诺码比香农码的平均码长小，编码效率高。其实这样编码的效率还不是最高的，现用另一种分割方法：
该费诺码的平均码长
.2)405.0(232.023.014.0)(7
1
=??+?+?+?==
∑
=i i
i K u p K
编码效率：
%5.970
.295.1)(==
=
K
U H η
可见编码效率又有所提高。事实上这已是最佳编码，就是说编码效率已不能再提高。但这样试探寻找分割方法总不是办法，因而赫夫曼提出一种编码方法，并证明这种编码在块码中已是最佳的。
3、哈夫曼编码方法
哈夫曼编码也是用码树来分配各符号的码字。费诺码是从树根开始，把各节点分给某子集；若子集已是单点集，它就是一片叶而作为码字。而赫夫曼编码是先给每一符号一片树叶，逐步合并成节点直到树根。
哈夫曼编码的步骤如下：
⑴ 将信源消息符号按其出现的概率大小依次排列
p(u 1)≥p(u 2)≥…≥ p(u n )
⑵取两个概率最小的字母分别配以0和1两码元，并将这两个概率相加作为一个新字母的概率，与未分配的二进符号的字母重新排队。
⑶ 对重排后的两个概率最小符号重复步骤⑵的过程。 ⑷不断继续上述过程，直到最后两个符号配以0和1为止。
⑸ 从最后一级开始，向前返回得到各个信源符号所对应的码元序列，即相应的码字。 例： 给定离散信源如下：
??
????=??????01.010.015.017.018.019.020.0)(7654321
u u u u u u u u p U
61
.201.0log 01.010.0log 10.015.0log 15.017
.0log 17.018.0log 18.019.0log 19.02.0log 2.0)(=-------=U H
平均码长：
72
.2401.0410.0315.0317.0318.0219.022.0)(7
1
=?+?+?+?+?+?+?==
∑
=i i
i K u p K 编码效率 %96.9572
.261.2)(==
=
K
U H η
哈夫曼编码方法得到的码并非是唯一的。非唯一的原因：
·每次对信源缩减时，赋予信源最后两个概率最小的符号，用0和1是可以任意意的，所以可以得到不同的哈夫曼码，但不会影响码字的长度。
·对信源进行缩减时两个概率最小的符号合并后的概率与其它信源符号的概率相同时，
这两者在缩减信源中进行概率排序，其位置放置次序是可以任意的，故会得到不同的哈夫曼码。此时将影响码字的长度，一般将合并的概率放在上面，这样可获得较小的码方差。
例：给定离散信源如下：
??
?
???=??????1
.01
.02
.02
.04
.0)(54321u u u u u u p U 有两种哈夫曼编码方法如下图所示：
平均码长：
2
.2231.0222.024.0)(5
1
1=??+??+?==
∑
=i i
i K u p K
2
.2241.032.022.014.0)(5
1
2=??+?+?+?==
∑
=i i
i K u p K
因为这两种码有相同的平均码长，所以有相同的编码效率，但每个信源符号的码长却
不相同。
在这两种不同的码中，选择哪个码好呢？我们引进码字任度K i 偏离平均码长K 的方差σ2，即
∑
=-=
-=5
1
2
2
2
)
)((])[(i i i i K K u p K K E σ
分别计算上例中两种码的方差
16
.02
)2.23(1.02)2.22(2.0)2.22(4.02
2221=?-+?-+-=σ36
.12)2.24(1.0)2.23(2.0)2.22(2.0)2.21(4.02
2
2
2
22
=?-+-+-+-=σ
可见，第一种编码方法的方差要小许多。所以，对于有限长的不同信源序列，用第一种方法所编得的码序列长度变化较小。因此相对来说选择第一种编码方法要更好些。
由此得出，在哈夫曼编码过程中，当缩减信源的概率分布重新排列时，应使合并得来的概率和尽量处于是高的位置。这样可使合并的元素重复编码次数减少，使短码得到充分利用
从以上实例中可以看出，哈夫曼码具有以下三个特点：
⑴哈夫曼码的编码方法保证了概率大的符号对应于短码，概率小的符号对应于长码，即p i ＞p j 有K i ＜K j ，充分利用了短码。
⑵缩减信源的最后二个码字总是最后一位码元不同，前面各位码元相同（二元编码情况），从而保证了哈夫曼是即时码。
⑶每次缩减信源的最长两个码字有相同的码长。 这三个特点保证了所得的哈夫曼码一定是最佳码。
第五章信源编码（第十一讲）
（2课时）
主要内容：（1）限失真信源编码定理（2）常用信源编码方法简介（游程编码、矢量量化编码、算术编码）
重点：常用信源编码方法简介。
难点：限失真信源编码定理、限失真信源编码定理。
特别提示：运用
说明：本堂课推导内容较多，枯燥平淡，不易激发学生兴趣，要注意多讨论用途。另外，注意，解题方法。多加一些内容丰富知识和理解。
作业：灵活运用。课外仍以学生复习。
§限失真信源编码定理
定理（限失真信源编码定理）设R(D)为离散无记忆信源X的信息率失真函数，R为信息传输率，则当信息率R>R（D），只要信源序列长度L足够长，一定存在一种编码方法，其译码失真小于或等于D＋ε，ε为任意小的正数；反之，若R 如果是二元信源，对于任意小的ε>0，每一个信源符号的平均码长满足如下公式：≤<+ R D K R Dε ()() 该定理指出，在失真限度内使信息率任意接近R（D）的编码方法存在,然而，若信息率小于R（D），平均失真一定会超过失真限度D。 对于连续平稳无记忆信源，虽然无法进行无失真编码，但在限失真情况下，有与该定理一样的编码定理。 该定理只说明最佳编码是存在的，但对于如何进行编码却一无所知，因而就不能像无损编码那样从证明过程中引出概率匹配的编码方法，一般只能从优化的思路去求最佳编码。 这个定理证明了允许失真D确定后，总存在一种编码方法，使信息传输率R大于R（D）且可任意接近R（D），而平均失真小于允许失真D。反之，若R R（D）。由此可见，信息率失真函数R（D）确实是在允许失真度为D的情况下信源信息压缩的下限值。当信源给定后，无失真信源压缩的极限值是信源熵H（U）；有失真信源压缩的极限值是信息率失真函数R（D）。 在给定某D后，一般R（D） 同样，该定理只是一个存在定理。至于如何寻找最佳压缩编码方法，定理中并没有给出。在实际应用中，该定理主要存在以下两大类问题。 第一类问题是,符合实际信源的R(D)函数的计算相当困难。首先，需要对实际信源的 统计特性有确切的数学描述。其次，需要对符合主客观实际的失真给予正确的度量，否则不能求得符合主客观实际的R(D)函数。 例如，通常采用均方误差来表示信源的平均失真度。但对于图像信源来说，均方误差较小的编码方法，人们视觉感到失真较大。所以，人们仍采用主观观察来评价编码方法的好坏。因此，如何定义符合主客观实际情况的失真测度就是件较困难的事。第三，即便对实际信源有了确切的数学描述，又有符合主客观实际情况的失真测度，而信息率失真函数R(D)的计算还是比较困难的。 第二类问题是，即便求得了符合实际的信息率失真函数，还需研究采用何种实用的最佳编码方法才能达到R(D)。 目前，这两方面工作都有进展。尤其是对实际信源的各种压缩方法，如对语音信号、电视信号和遥感图像等信源的各种压缩方法有了较大进展。相信随着数据压缩技术的发展，限失真编码理论中存在的问题将会得到解决。 §限失真信源编码常用信源编码方法 一、游程编码 游程：指数字序列中连续出现相同符号的一段。 二元序列只有两种符号：“0”和“1”： 连“0”段称为“0”游程，游程长度为L(0) 连“1”段称为“1”游程，游程长度为L(1) 由于是二进制序列，“0”游程和“1”游程总是交替出现。若规定二元序列总是从“0”开始，第一个游程是“0”游程，则第二个游程必为“1”游程，第三个又是“0”游程……对于随机序列，游程的长度是随机的，其取值为1，2，3…自至无穷。 游程序列：用交替出现的“0”游程和“1”游程的长度，来表示任意二元序列。 例如二元序列 00010111001000l … 可变换成如下游程序列 31132131… 己规定游程序列从“0”开始，由上述游程序列，很容易恢复出原来的二元序列。 游程序列已是多元序列，各长度就可按哈夫曼编码或其它方法处理以达到压缩码率的目的。这种从二元序列转换成多元序列的方法，在实现时比以前的并元法简单；因为游程长度的计数比较容易，得到游程长度后就可从码表中找出码字输出，同时去数下一个游程长度。此外，在减弱原有序列的符号间的相关性方面采用游程变换一般也比并元法更有效。 当然，要对二元序列进行哈夫曼编码时应先测定“0”游程长度和“1”游程长度的概率分布，或由二元序列的概率特性去计算各种游程长度的概率。 设二元序列为独立序列，“0”和“1”的概率分别为p0和p1，则“0”游程长度L(0) 的概率为 11 )0(0 )]0([p p L p L -= 式中L(0)=1，2，…，游程长度至少是1。从理论上来说，游程长度可以是无穷，但很长的游程实际出现的概率非常小。 ∑ ∞ ==-= 1 )0(0 111)]0([L p p L p 则“1”游程长度L(1)的概率为 01 )1(1 )]1([p p L p L -= ∑ ∞ ==-= 1 )1(1 011)]1([L p p L p “0”游程长度的熵： 1 01 )0(11 )0(0 211 )0(0 1)0(2 )(][log )]0([log )]0([)]0([p p H p p p p L p L p L H L L L L = = - =∑ ∑ ∞ =--∞ = “0” 游程序列的平均游程长度 1 1 )0(11 )0(0 1 )0(01)0()]0([)]0([)]0([p p p L L p L L E l L L L = = - ==∑ ∑∞ =-∞ = 同理，“1”游程长度的熵和平均游程长度： 变换后的游程序列是独立序列 10 11)]1([)()]1([p L E l p p H L H = == )()()] 1([)]0([)(101 0p H p H l l L H L H X H ==++= 游程变换后符号熵没有变。因为游程变换是一一对应的可逆变换。所以变换后熵值不变。 由于游程变换有较好的去相关效果，因而对游程序列进行哈夫曼编码，可获得较高的编码效率。 假设“0”游程长度的哈夫曼编码效率为η0，“1”游程长度的哈夫曼编码效率为η1,由编码效率的定义得二元序列的编码效率 1 )] 1([)] 0([)]1([)]0([ηηηL H L H L H L H + += 假设η0＞η1，则有η0＞η＞η1 当“0”游程和“1”游程的编码效率都很高时，采用游程编码的效率也很高，至少不 会低于较小的那个效率。要想编码效率η尽可能高，应使上式的分母尽可能小，这就要求尽可能提高熵值较大的游程的编码效率，因为它在往分母中占的比重较大。 理论上来说游程长度可从1到无穷。要建立游程长度和码字之间的一一对应的码表是困难的。一般情况下，游程越长，出现的概率就越小；当游程长度趋向于无穷时，出现的概率也趋向于0。 按哈夫曼码的编码规则，概率越小码字越长，但小概率的码字对平均码长影响较小，在实际应用时常对长码采用截断处理的方法 取一个适当的n值，游程长度为1,2,…,2n-1, 2n，所有大于2n者都按2n来处理。然后按照哈夫曼码的编码规则，将上列2n种概率从大到小排队，构成码树并得到相应的码字。 二、矢量量化编码 要想得到性能好的编码，仅采用标量量化是不可能的。在最佳编码中，如将离散信源的多个符号进行联合编码可提高效率，这对连续信源也是如此。当把多个信源符号联合起来形成多维矢量，再对矢量进行标量量化时，自由度将更大，同样的失真下，量化级数可进一步减少，码率可进一步压缩。这种量化叫做矢量量化。 实验证明，即使各信源符号相互独立，多维量化通常也可压缩信息率。因而矢量量化引起人们的兴趣而成为当前连续信源编码的一个热点。可是当维数较大时，矢量量化尚无解析方法，只能求助于数值计算；而且联合概率密度也不易测定，还需采用诸如训练序列的方法。一般来说，高维矢量的联合是很复杂的，虽已有不少方法，但其实现尚有不少困难，有待进一步研究。 设矢量量化器输入集为X＝{X1，X2，…，X N}，X j∈X，X j＝（x j1，x j2，…,x j k），X ∈R k（k维欧几里德空间），把R k划分成J＝2 n个互不相交的子空间R1，R2，…，RＪ，求出每个子空间的质心Y i，所有的Y i构成Y＝{Y1，Y2，…，YＪ}，Y为量化器的输出空间，也叫码书（或码本），Y i叫码字或码矢，J叫码书的长度。 对J阶K维的矢量量化，实质上是判断输入X j∈R k属于哪个子空间R i，然后输出该子空间代表码字Y i，即： Y i＝Q（X j）, 1≤i≤J，1≤j≤N（4―42） 这里Y i就是X j的编码。 实际编码时，在发送端只需记录代表码字Y i的下标i，所以编码过程是把X映射到I ＝{1，2，…，J}；而译码过程是在接收端依据收到的I代码，查找码书Y，获得码字Y i，用来代替X j。由于总的码字个数J一般远小于总的输入信号N×K，所以矢量量化的压缩能力非常大。 传输或存储一个矢量所需比特为lbJ（一般J＝2n），它是一个K维矢量，就是K个输入信号，所以每个输入信号的平均比特只有lbJ/K，称之为压缩比。适当选取码书长度J 和码字维数K，可以获得很大压缩比。矢量量化中码书的码字越多，维数越大，失真就越 小。只要适当地选择码字数量，就能控制失真量不超过某一给定值，因此码书控制着矢量的大小。矢量量化时每输入一个 X j ，都要和J 个码字 Y i 逐一比较，搜索与其最接近的码字 Y i 。由于两者均为K 维矢量，所以工作量很大。矢量量化是定长码，容易处理。 矢量量化由码书 Y 和划分R i 的条件惟一确定。当码书确定后，通过最近邻域准则可以惟一确定区域分割。因此，最佳量化器的设计也就是最佳码书Y 的设计。前面，在讨论一维标量的最佳设计时，引入了Max L i vo d 的迭代算法，1980年L inde 、Bu zo 和G ray 将此算法推广到了多维空间，称作L B G 算法。因L B G 算法由于理论上的严密性和实现的简便性以及较好的设计效果而得到了广泛的应用，并成为各种改进算法的基础。有关L B G 算法等知识请参阅有关文献。 三、算术编码 1、算术码的主要概念： 把信源输出序列的概率和实数段[0，1]中的一个数ρ联系起来。设信源字母表为{a 1, a 2}，其发生概率为p(a 1)=0.6 ,p(a 2)=0.4。将[0，1]分成两个与概率比例相应的区间，[0，0.6] [0.6，l]当信源输出的第一个符号s 1 = a 1时，数ρ的值处在[0，0.6] ，s 1 = a 2时，[0.6，l]。 根据信源字母s 1的情况,把ρ所在的段再次按概率比例分成 [0，1] → [0，0.6] [0.6，l] [0,0.36] [0.36,0.6] [0.6,0.84] [0.84,1] s 1 = a 1 s 1 = a 2 根据信源输出的第二个字母s 2的取值情况，可以更精确地确定出数ρ所在的区间位置。在信源输出第n －1个符号后，若ρ所在的位置为 [A n -1 ，B n -1] 则当信源输出的第n 个符号为： s n = a 1时， s n = a 2 A n = A n -1 A n = A n -1+0.6( B n -1－A n -1) B n = A n -1+0.6(B n -1－A n -1) B n = B n -1 按照这一方法，序列的概率刚好等于ρ所在区间的长度。随着序列的长度不断增加，ρ所在区间的长度就越短，也就可以更加精确地确定ρ的位置。当信源字母序列长度趋于无限时，ρ所在区间成为一点。 2、累积概率 设信源字母表为A={ a 1, a 2,…,a i , …a m },字母a i 的概率p(a i ) 修正的累积概率为 )(2 1)()(1 1 k k i i k a p a p a F + = ∑ -= 定义字母a k 的累积概率为 ∑ -== 1 1 )()(k i i k a p a F F(a 1) = 0 ，F(a 2) = p(a 1) ，F(a 3) = p(a 1)+ p(a 2) p(a k ) = F(a k +1)－F(a k ) 当 A={0，l}二元信源时： F(0) = 0 ，F(1) = p(0) 计算信源序列s =（s 1,s 2,……,s n ）的累积概率 以二元无记忆信源为例： 初始时：在[0，l]由F(1)划分成二个子区间： [0，l] →[0,F(1)] [ F(1),1]， F(1) = p(0) 0 1 子区间[0,F(1)] [ F(1),1]的宽度为 A(0) = p(0) A(1) = p(1) 若输入序列的第一个符号为s =“0”，即落入对应的区间[0,F(1)] F(s =“0”) = F(0) = 0 当输入第二个符号为“1”, s =“01”对应的区间在[0,F(1)]中进行分割 A(00) = A(0) p(0) = p(0) p(0) = p(00) A(01) = A(0) p(1) = p(0) p(1) = p(01) = A(0) －A(00) “00”对应的区间[0,F(01)]；“01”对应的区间[F(01) , F(1)] s =“01”的累积概率 F(s =“01”) = F(01) = p(0) p(0) 当输入第三个符号为“1”， s1 =“011”，所对应的区间在[F(01) , F(1)]中进行分割 对应的区间[F(s) , F(s)+ A(s) p(0)] 对应的区间[F(s)+ A(s) p(0) , F(1)] A(010) = A(01) p(0) = A(s)p(0) A(011) = A(01) p(1) = A(s)p(1) = A(01) －A(010) = A(s) －A(s0) F(s1) = F(s)+ A(s) p(0) F(s0) = F(s) 现已输入三个符号串，将这符号序列标为s，接着输入第四个符号为“0”或“1”。可计算出s0=“0110”或s1=“0111”对应的子区间及其累积概率。 当已知前面输入符号序列为s，若接着再输入一个符号“0” 累积概率 区间宽度 F(s0) = F(s) A(s0) = A(s)p(0) 若接着输入的一个符号是“1”，对序列s1的累积概率为 F(s1) = F(s)+ A(s) p(0) A(s1) = A(s)p(1) = A(s)－A(s0) 由前分析又知，符号序列对应的区间宽度为 A(0) = p(0) A(1) = 1－A(0) = p(1) A(00) = p(00) = A(0)p(0)= p(0) p(0) A(01) = A(0)－A(00) = p(01) = A(0)p(1) = p(0) p(1) A(10) = p(10) = A(1)p(0) = p(1) p(0) A(11) = A(1)－A(10) = p(11) = A(1)p(1) = p(1) p(1) A(010) = A(01) p(0) = p(01)p(0) = p(010) A(011) = A(01)－A(010) = A(01)p(1) = p(01)p(1) = p(011) ┊ 信源符号序列s 所对应区间的宽度等于符号序列s 的概率p(s) 二元信源符号序列的累积概率的递推公式为 F(sr) = F(s) + p(s ) F(r) （r =0,1） 其中sr 表示已知前面信源符号序列为s 接着再输入符号为r 。而F(r) ：[F(0) = 0 ，F(1) = p(0)] 同样可得信源符号序列所对应区间的宽度的递推公式为 A(sr) = p(sr) = p(s ) p(r) （r =0,1） 已输入的二元符号序列为s =“011”，若接着输入符号为1得序列的累积概率： F(s1) = F(0111) = F(s =011) + p(011) p(0) = F(s =01) + p(01) p(0) + p(011) p(0) = F(s =0) + p(0) p(0) + p(01) p(0) + p(011) p(0) = 0 + p(00) + p(010) + p(0110) 其对应区间宽度 A(s1) = A(s =011) p(1) = p(011)p(1) = p(0111) 由于 F(sr) = F(s) + p(s ) F(r) A(sr) = p(sr) = p(s ) p(r) 是可递推运算，因此适合于实用。实际中，只需两个存储器，把p(s ) 和F(s)存下来，然后根据输入符号和上式，更新两个存储器中的数值。 因为在编码过程中，每输入一个符号要进行乘法和加法运算，所以称此编码方法为算术编码。 将上式推广到多元信源序列，得一般的递推公式 F(sa k ) = F(s) + p(s) F(a k ) A(sa k ) = p(sa k ) = p(s) p(a k ) 通过关于信源符号序列的累积概率的计算，F(s)把区间[0,1]分割成许多小区间，不同的信源符号序列对应于不同的区间为[F(s), F(s)+ p(s)]。可取小区间内的一点来代表这序列。 ??代表大于等于的最小整数。 ?? L L s F .0)(= 令 ??? ?? ? =)(1 l o g s p L 把累积概率F(s) 写成二进制的小数，取小数点后L 位，以后如果有尾数，就进到第L 位，这样得到一个数C 。 2-1、一阶马尔可夫链信源有3个符号 {}123,,u u u ，转移概率为：1 112 ()u p u =， 2112()u p u =，31()0u p u =，1213()u p u = ，22()0u p u =，3223()u p u =，1313()u p u =，2323()u p u =，33()0u p u =。画出状态图并求出各符号稳态概率。 解：由题可得状态概率矩阵为： 1/21/2 0[(|)]1/302/31/32/30j i p s s ????=?? ???? 状态转换图为： 令各状态的稳态分布概率为1W ，2W ，3W ，则： 1W = 121W +132W +133W ， 2W =121W +233W , 3W =23 2W 且： 1W +2W +3W =1 ∴稳态分布概率为： 1W = 25，2W =925，3W = 625 2-2.由符号集｛０，１｝组成的二阶马尔可夫链，其转移概率为：P(0|00)=0.8,P(0|11)=0.2,P(1|00)=0.2,P(1|11)=0.8,P(0|01)=0.5,p(0|10)=0.5,p(1|01)=0.5,p(1|10)=0.5画出状态图，并计算各符号稳态概率。 解：状态转移概率矩阵为： 令各状态的稳态分布概率为1w 、2w 、3w 、4w ，利用（2-1-17）可得方程组。 0.8 0.2 0 00 0 0.5 0.5()0.5 0.5 0 00 0 0.2 0.8j i p s s ?? ?? ? ?=?????? 111122133144113211222233244213 311322333344324411422433444424 0.80.50.20.50.50.20.50.8w w p w p w p w p w w w w p w p w p w p w w w w p w p w p w p w w w w p w p w p w p w w =+++=+??=+++=+?? =+++=+??=+++=+? 且12341w w w w +++=； 解方程组得：12345141717514w w w w ?=???=???=???=? 即：5(00)141(01)71(10)75(11)14 p p p p ? =???=?? ?=???=? 2-3、同时掷两个正常的骰子，也就是各面呈现的概率都是16 ，求： （1）、“3和5同时出现”事件的自信息量； （2）、“两个1同时出现”事件的自信息量； （3）、两个点数的各种组合的熵或平均信息量； （4）、两个点数之和的熵； （5）、两个点数中至少有一个是1的自信息量。 解：（1）3和5同时出现的概率为：1111 p(x )=26618 ??= 11 I(x )=-lb 4.1718 bit ∴= （2）两个1同时出现的概率为：2111 p(x )=6636 ?= 21 I(x )=-lb 5.1736 bit ∴= （3）两个点数的各种组合（无序对）为： (1,1),(1,2),(1,3),(1,4),(1,5),(1,6) (2,2),(2,3),(2,4),(2,5),(2,6) (3,3), (3,4),(3,5),(3,6) (4,4),(4,5),(4,6) 第一章 信息、消息、信号的定义？三者的关系？ 通信系统的模型？各个主要功能模块及作用？ 第二章 信源的分类？ 自信息量、条件自信息量、平均自信息量、信源熵、不确定度、条件熵、疑义度、噪声熵、联合熵、互信息量、条件互信息量、平均互信息量以及相对熵的概念？计算方法? 冗余度? 具有概率为)(x i p 的符号x i 自信息量：)(log )(x x i i p I -= 条件自信息量：)(log )( y x y x i i i i p I -= 平均自信息量、平均不确定度、信源熵：∑-=i i i x x p p X H )(log )()( 条件熵：)(log ),()(),()(y x y x y x y x j i j ij i j i j ij i p p I p Y X H ∑∑-== 联合熵：),(log ),(),(),()(y x y x y x y x j i j ij i j i j ij i p p I p Y X H ∑∑-== 互信息：) ()(log )()() ()(log ),();(y x y x y x y x y y x j i j i j ij i j i j j ij i p p p p p p p Y X I ∑∑= = 熵的基本性质：非负性、对称性、确定性 2.3 同时掷出两个正常的骰子，也就是各面呈现的概率都为1/6，求： (1) “3和5同时出现”这事件的自信息； (2) “两个1同时出现”这事件的自信息； (3) 两个点数的各种组合（无序）对的熵和平均信息量； (4) 两个点数之和（即2, 3, … , 12构成的子集）的熵； (5) 两个点数中至少有一个是1的自信息量。 解：(1) bit x p x I x p i i i 170.418 1 log )(log )(18 1 61616161)(=-=-== ?+?= (2) bit x p x I x p i i i 170.536 1 log )(log )(361 6161)(=-=-== ?= 信息论与编码习题参考答案 第一章 单符号离散信源 同时掷一对均匀的子，试求： (1)“2和6同时出现”这一事件的自信息量； (2)“两个5同时出现”这一事件的自信息量； (3)两个点数的各种组合的熵； (4)两个点数之和的熵； (5)“两个点数中至少有一个是1”的自信息量。 解： bit P a I N n P bit P a I N n P c c N 17.536log log )(36 1 )2(17.418log log )(362)1(36 662221111 616==-=∴====-=∴== =?==样本空间： * (3)信源空间： bit x H 32.436log 36 16236log 36215)(=??+?? =∴ bit x H 71.3636 log 366536log 3610 436log 368336log 366236log 36436log 362)(=??+?+?+??= ∴＋＋ (5) bit P a I N n P 17.111 36 log log )(3611333==-=∴== ? 如有6行、8列的棋型方格，若有两个质点A 和B ，分别以等概落入任一方格内，且它们的坐标分别为（Xa ，Ya ）, （Xb ，Yb ）,但A ，B 不能同时落入同一方格内。 （1） 若仅有质点A ，求A 落入任一方格的平均信息量； （2） 若已知A 已落入，求B 落入的平均信息量； （3） 若A ，B 是可辨认的，求A ，B 落入的平均信息量。 解： ！ bit a P a P a a P a I a P A i 58.548log )(log )()(H 48log )(log )(481 )(:)1(48 1 i i i i i ==-=∴=-=∴= ∑=落入任一格的概率 bit b P b P b b P b I b P A i 55.547log )(log )()(H 47 log )(log )(47 1 )(:B ,)2(48 1i i i i i ==-=∴=-=∴=∑=落入任一格的概率是落入任一格的情况下在已知 bit AB P AB P AB H AB P AB I AB P AB i i i i i i i 14.11)4748log()(log )()() (log )(47 1 481)()3(47481 =?=-=-=∴?=∑?=是同时落入某两格的概率 从大量统计资料知道,男性中红绿色盲的发病率为7%,女性发病率为%.如果你问一位男士：“你是否是红绿色盲”他的回答可能是：“是”，也可能“不是”。问这两个回答中各含有多少信息量平均每个回答中各含有多少信息量如果你问一位女士，则她的答案中含有多少平均信息量 解： 4-1 设有一个二元等该率信源{}1,0∈X ,2/110==p p ，通过一个二进制对称信道（BSC ）。其失真函数ij d 与信道转移概率ij p 分别定义为 j i j i d ij =≠???=,0,1 ，j i j i p ij =≠? ??-=,1,εε 试求失真矩阵d 和平均失真D 。 解：由题意得， 失真矩阵为d ??????=0110d ，信道转移概率矩阵为P ?? ????--=εεεε11)(i j 平均失真为ε εεεε=?-+?+?+?-= =∑0)1(211211210)1(21),()()(,j i d i j p i p D j i 4-3 设输入符号与输出符号X 和Y 均取值于{0,1,2,3}，且输入符号的概率分布为P(X=i)=1/4,i=0,1,2,3,设失真矩阵为 ????? ???????=0111101111011110d 求)(),(,,max min max min D R D R D D 以及相应的编码器转移概率矩阵。 解：由题意，得 0min =D 则symbol bit X H R D R /24log )()0()(2min ==== 这时信源无失真，0→0,1→1,2→2,3→3，相应的编码器转移概率矩阵为 ????? ???????=1000 010*********)j (i P ∑===30 3,2,1,0max ),()(min i j j i d i p D ，，14 1141041141141141141041min{?+?+?+??+?+?+?= }04 1141141141141041141141?+?+?+??+?+?+?， 43}43,43,43,43min{== 则0)(max =D R 此时输出概率分布可有多种，其中一种为：p(0)=1,p(1)=p(2)=p(3)=0 则相应的编码器转移概率矩阵为????? ???????=0001000100010001)(i j P 第一章 1.通信系统的基本模型: 2.信息论研究内容：信源熵，信道容量，信息率失真函数，信源编码，信道编码，密码体制的安全性测度等等 第二章 １.自信息量：一个随机事件发生某一结果所带的信息量。 ２.平均互信息量：两个离散随机事件集合X 和Y ，若其任意两件的互信息量为 I （Xi;Yj ），则其联合概率加权的统计平均值，称为两集合的平均互信息量，用I （X;Y ）表示 ３.熵功率：与一个连续信源具有相同熵的高斯信源的平均功率定义为熵功率。如果熵功率等于信源平均功率，表示信源没有剩余；熵功率和信源的平均功率相差越大，说明信源的剩余越大。所以信源平均功率和熵功率之差称为连续信源的剩余度。信源熵的相对率(信源效率)：实际熵与最大熵的比值 信源冗余度： 0H H ∞=ηη ζ-=1 意义：针对最大熵而言，无用信息在其中所占的比例。 ３.极限熵： 平均符号熵的N 取极限值，即原始信源不断发符号，符号间的统计关系延伸到无穷。 ４. ５.离散信源和连续信源的最大熵定理。 离散无记忆信源，等概率分布时熵最大。 连续信源，峰值功率受限时，均匀分布的熵最大。 平均功率受限时，高斯分布的熵最大。 均值受限时，指数分布的熵最大 ６.限平均功率的连续信源的最大熵功率： 称为平均符号熵。 定义：即无记忆有记忆N X H H X H N X H X NH X H X H X H N N N N N N )() ()()()()()(=≤∴≤≤ 若一个连续信源输出信号的平均功率被限定为p ，则其输出信号幅度的概率密度分布是高斯分布时，信源有最大的熵，其值为 1log 22 ep π.对于N 维连续平稳信源来说，若其输出的N 维随机序列的协方差矩阵C 被限定，则N 维随机矢量为正态分布时信源 的熵最大，也就是N 维高斯信源的熵最大，其值为1log ||log 222N C e π+ 7.离散信源的无失真定长编码定理： 离散信源无失真编码的基本原理 原理图 说明： （1） 信源发出的消息：是多符号离散信源消息，长度为L,可以用L 次扩展信 源表示为： X L =(X 1X 2……X L ) 其中，每一位X i 都取自同一个原始信源符号集合（n 种符号）： X={x 1，x 2，…x n } 则最多可以对应n L 条消息。 （2）信源编码后，编成的码序列长度为k,可以用k 次扩展信宿符号表示为： Y k =(Y 1Y 2……Y k ) 称为码字/码组 其中，每一位Y i 都取自同一个原始信宿符号集合： Y={y 1，y 2，…y m } 又叫信道基本符号集合（称为码元，且是m 进制的） 则最多可编成m k 个码序列，对应m k 条消息 定长编码：信源消息编成的码字长度k 是固定的。对应的编码定理称为定长信源编码定理。 变长编码：信源消息编成的码字长度k 是可变的。 8.离散信源的最佳变长编码定理 最佳变长编码定理：若信源有n 条消息，第i 条消息出现的概率为p i ，且 p 1>=p 2>=…>=p n ，且第i 条消息对应的码长为k i ，并有k 1<=k 2<=…<=k n 第一章信息论与基础 1.1信息与消息的概念有何区别？ 信息存在于任何事物之中,有物质的地方就有信息，信息本身是看不见、摸不着的，它必须依附于一定的物质形式。一切物质都有可能成为信息的载体，信息充满着整个物质世界。信息是物质和能量在空间和时间中分布的不均匀程度。信息是表征事物的状态和运动形式。 在通信系统中其传输的形式是消息。但消息传递过程的一个最基本、最普遍却又十分引人注意的特点是：收信者在收到消息以前是不知道具体内容的；在收到消息之前，收信者无法判断发送者将发来描述何种事物运动状态的具体消息；再者，即使收到消息，由于信道干扰的存在，也不能断定得到的消息是否正确和可靠。 在通信系统中形式上传输的是消息,但实质上传输的是信息。消息只是表达信息的工具，载荷信息的载体。显然在通信中被利用的（亦即携带信息的）实际客体是不重要的，而重要的是信息。 信息载荷在消息之中，同一信息可以由不同形式的消息来载荷；同一个消息可能包含非常丰富的信息，也可能只包含很少的信息。可见，信息与消息既有区别又有联系的。 1.2 简述信息传输系统五个组成部分的作用。 信源：产生消息和消息序列的源。消息是随机发生的，也就是说在未收到这些消息之前不可能确切地知道它们的内容。信源研究主要内容是消息的统计特性和信源产生信息的速率。 信宿：信息传送过程中的接受者，亦即接受消息的人和物。 编码器：将信源发出的消息变换成适于信道传送的信号的设备。它包含下述三个部分：(1)信源编码器：在一定的准则下，信源编码器对信源输出的消息进行适当的变换和处理，其目的在于提高信息传输的效率。(2)纠错编码器：纠错编码器是对信源编码器的输出进行变换，用以提高对于信道干扰的抗击能力，也就是说提高信息传输的可靠性。(3)调制器：调制器是将纠错编码器的输出变换适合于信道传输要求的信号形式。纠错编码器和调制器的组合又称为信道编码器。 信道：把载荷消息的信号从发射端传到接受端的媒质或通道，包括收发设备在内的物理设施。信道除了传送信号外，还存储信号的作用。 译码器：编码的逆变换。它要从受干扰的信号中最大限度地提取出有关信源输出消息的信息，并尽可能地复现信源的输出。 1.3 同时掷一对骰子，要得知面朝上点数之和，描述这一信源的数学 模型。 解：设该信源符号集合为X 第二章 信息量和熵 2.2 八元编码系统，码长为3，第一个符号用于同步，每秒1000个码字，求它的 信息速率。 解：同步信息均相同，不含信息，因此 每个码字的信息量为 2?8log =2?3=6 bit 因此，信息速率为 6?1000=6000 bit/s 2.3 掷一对无偏骰子，告诉你得到的总的点数为：(a) 7; (b) 12。问各得到多少信 息量。 解：(1) 可能的组合为 {1，6},{2，5},{3，4},{4，3},{5，2},{6，1} )(a p =366=6 1 得到的信息量 =) (1 log a p =6log =2.585 bit (2) 可能的唯一，为 {6，6} )(b p =361 得到的信息量=) (1 log b p =36log =5.17 bit 2.4 经过充分洗牌后的一副扑克（52张），问： (a) 任何一种特定的排列所给出的信息量是多少？ (b) 若从中抽取13张牌，所给出的点数都不相同时得到多少信息量？ 解：(a) )(a p =! 521 信息量=) (1 log a p =!52log =225.58 bit (b) ???????花色任选 种点数任意排列 13413!13 )(b p =13 52134!13A ?=1352 13 4C 信息量=1313 52 4log log -C =13.208 bit 2.9 随机掷3颗骰子，X 表示第一颗骰子的结果，Y 表示第一和第二颗骰子的 点数之和，Z 表示3颗骰子的点数之和，试求)|(Y Z H 、)|(Y X H 、 ),|(Y X Z H 、)|,(Y Z X H 、)|(X Z H 。 解：令第一第二第三颗骰子的结果分别为321,,x x x ，1x ，2x ，3x 相互独立， 则1x X =，21x x Y +=，321x x x Z ++= )|(Y Z H =)(3x H =log 6=2.585 bit )|(X Z H =)(32x x H +=)(Y H =2?( 361log 36+362log 18+363log 12+364log 9+365log 536)+36 6 log 6 =3.2744 bit )|(Y X H =)(X H -);(Y X I =)(X H -[)(Y H -)|(X Y H ] 而)|(X Y H =)(X H ，所以)|(Y X H = 2)(X H -)(Y H =1.8955 bit 或)|(Y X H =)(XY H -)(Y H =)(X H +)|(X Y H -)(Y H 而)|(X Y H =)(X H ，所以)|(Y X H =2)(X H -)(Y H =1.8955 bit ),|(Y X Z H =)|(Y Z H =)(X H =2.585 bit )|,(Y Z X H =)|(Y X H +)|(XY Z H =1.8955+2.585=4.4805 bit 2.10 设一个系统传送10个数字，0，1，…，9。奇数在传送过程中以0.5的概 率错成另外一个奇数，其余正确接收，求收到一个数字平均得到的信息量。 解： 8,6,4,2,0=i √ );(Y X I =)(Y H -)|(X Y H 因为输入等概，由信道条件可知， 设信源1 234567()0.20.190.180.170.150.10.01X a a a a a a a p X ????=???? ???? (1) 求信源熵H(X)； (2) 编二进制香农码； (3) 计算平均码长和编码效率. 解： (1) 7 21222222()()log () 0.2log 0.20.19log 0.19 0.18log 0.180.17log 0.170.15log 0.150.1log 0.10.01log 0.012.609/i i i H X p a p a bit symbol ==-=-?-?-?-?-?-?-?=∑ (2) (3) 7 1 ()0.230.1930.1830.1730.153 0.140.0173.141 ()()/ 2.609 3.14183.1% i i i K k p x H X H X K R η===?+?+?+?+?+?+?====÷=∑ 对习题的信源编二进制费诺码，计算编码效率. 解： a i p(a i )编码码字k i a1 0002 a2 1 00103 a310113 a4 1 0102 a5 1 01103 a6 1 011104 a7111114 对信源编二进制和三进制哈夫 曼码，计算各自的平均码长和编码效率. 解： 二进制哈夫曼码： x i p(x i)编码码字k i s61 s50 s41 s30 s21 x10102 x21112 x300003 x410013 x500103 s11 x6001104 x7101114 三进制哈夫曼码： x i p(x i)编码码字k i s31 s20 s11 x1221 x20002 x31012 x42022 x50102 x61112 x72122 一填空题（本题20分，每小题2分） 1、平均自信息为 表示信源的平均不确定度，也表示平均每个信源消息所提供的信息量。 平均互信息 表示从Y获得的关于每个X的平均信息量，也表示发X前后Y的平均不确定性减少的量，还表示通信前后整个系统不确定性减少的量。 2、最大离散熵定理为：离散无记忆信源，等概率分布时熵最大。 3、最大熵值为。 4、通信系统模型如下： 5、香农公式为为保证足够大的信道容量，可采用（1）用频带换信噪比；（2）用信噪比换频带。 6、只要，当N足够长时，一定存在一种无失真编码。 7、当R＜C时，只要码长足够长，一定能找到一种编码方法和译码规则，使译码错误概率无穷小。 8、在认识论层次上研究信息的时候，必须同时考虑到形式、含义和效用三个方面的因素。 9、1948年，美国数学家香农发表了题为“通信的数学理论”的长篇论文，从而创立了信息论。 按照信息的性质，可以把信息分成语法信息、语义信息和语用信息。 按照信息的地位，可以把信息分成客观信息和主观信息。 人们研究信息论的目的是为了高效、可靠、安全地交换和利用各种各样的信息。 信息的可度量性是建立信息论的基础。 统计度量是信息度量最常用的方法。 熵是香农信息论最基本最重要的概念。 事物的不确定度是用时间统计发生概率的对数来描述的。 10、单符号离散信源一般用随机变量描述，而多符号离散信源一般用随机矢量描述。 11、一个随机事件发生某一结果后所带来的信息量称为自信息量，定义为其发生概率对 数的负值 。 12、自信息量的单位一般有 比特、奈特和哈特 。 13、必然事件的自信息是 0 。 14、不可能事件的自信息量是 ∞ 。 15、两个相互独立的随机变量的联合自信息量等于 两个自信息量之和 。 16、数据处理定理：当消息经过多级处理后，随着处理器数目的增多，输入消息与输出消息之间的平均互信息量 趋于变小 。 17、离散平稳无记忆信源X 的N 次扩展信源的熵等于离散信源X 的熵的 N 倍 。 18、离散平稳有记忆信源的极限熵，=∞H )/(lim 121-∞→N N N X X X X H 。 19、对于n 元m 阶马尔可夫信源，其状态空间共有 nm 个不同的状态。 20、一维连续随即变量X 在[a ，b]区间内均匀分布时，其信源熵为 log2（b-a ） 。 21、平均功率为P 的高斯分布的连续信源，其信源熵，Hc （X ）=eP π2log 21 2。 22、对于限峰值功率的N 维连续信源，当概率密度 均匀分布 时连续信源熵具有最大值。 23、对于限平均功率的一维连续信源，当概率密度 高斯分布 时，信源熵有最大值。 24、对于均值为0，平均功率受限的连续信源，信源的冗余度决定于平均功率的限定值P 和信源的熵功率P 之比 。 信息论与编码习题参考答案 第一章 单符号离散信源 同时掷一对均匀的子，试求： (1)“2和6同时出现”这一事件的自信息量； (2)“两个5同时出现”这一事件的自信息量； (3)两个点数的各种组合的熵； (4)两个点数之和的熵； (5)“两个点数中至少有一个是1”的自信息量。 解： bit P a I N n P bit P a I N n P c c N 17.536log log )(361 )2(17.418log log )(362)1(36 662221111 616==-=∴====-=∴== =?==样本空间： (3)信源空间： bit x H 32.436log 36 16236log 36215)(=??+?? =∴ (4)信源空间： bit x H 71.3636 log 366536log 3610 436log 368336log 366236log 36436log 362)(=??+?+?+??= ∴＋＋ (5) bit P a I N n P 17.111 36 log log )(3611333==-=∴== 如有6行、8列的棋型方格，若有两个质点A 和B ，分别以等概落入任一方格内，且它们的坐标分别为（Xa ，Ya ）, （Xb ，Yb ）,但A ，B 不能同时落入同一方格内。 （1） 若仅有质点A ，求A 落入任一方格的平均信息量； （2） 若已知A 已落入，求B 落入的平均信息量； （3） 若A ，B 是可辨认的，求A ，B 落入的平均信息量。 解： bit a P a P a a P a I a P A i 58.548log )(log )()(H 48log )(log )(481 )(:)1(48 1 i i i i i ==-=∴=-=∴= ∑=落入任一格的概率Θ bit b P b P b b P b I b P A i 55.547log )(log )()(H 47 log )(log )(47 1 )(:B ,)2(48 1i i i i i ==-=∴=-=∴=∑=落入任一格的概率是落入任一格的情况下在已知Θ 4.5若将N 个相同的BSC 级联如题图4.5所示，各信道的转移概率矩阵为??????--p p p p 11。令Q t =P{X t =0}，t=0,1,…,N,且Q 0为已知。 题图 4.5 (a)求Q t 的表达式。 (b)证明N →∞时有Q N →1/2，且与Q 0取值无关，从而证明N →∞级联信道的信道容量C N →0，P>0。 解： (a)对于满足X N 为马氏链的串联信道，他们总的信道转移概率矩阵为各个串联信道矩阵的乘积，即P(X N |X 0)= P(X 1|X 0) P(X 2|X 1)……P(X N |X N-1) 由已知得，但各信道的转移概率矩阵为?? ?? ??--p p p p 11 则两个信道级联的转移概率矩阵为： P 2=??????--p p p p 11????? ?--p p p p 11=()()()()??????-+---+2222112p 12p 1p p p p p p 三个信道级联的转移概率矩阵为： P 3=()()()()???? ??????-+----+33331221211221211221211-2p 2121p p p 四个信道级联的转移概率矩阵为： P 4=()()()()???? ??????-+----+44441221211221211221211-2p 2121p p p 以此类推：可得N 个信道级联的转移概率矩阵为： P N =()()()()??????????-+----+N N N N p p p 122121122 1211221211-2p 2121 则 Q t =P{X t =0}=()()()()()000121221211122121122121Q p p Q p Q p t t t t -+--=-?? ????--+??????-+ I (X ;Y=1)= P(x/Y 1)I(x;Y 1) x P(x/Y 1)log P(x/Y 1) P(x) = P(X 0/Y 1)log P(X 0/Y 1) P(X 0) P(X 1/Y 1)log P(X 1/Y 1) P(X 1) 部分答案，仅供参考。 信息速率是指平均每秒传输的信息量点和划出现的信息量分别为log3Jog3， 2’ 一秒钟点和划出现的次数平均为 1 15 2 1 ~4 0.20.4 - 3 3 一秒钟点和划分别出现的次数平均为巴5 4 4 那么根据两者出现的次数，可以计算一秒钟其信息量平均为10 log 3 5 竺 5 4 2 4 4 2 解： ⑻骰子A和B，掷出7点有以下6种可能： A=1,B=6; A=2,B=5; A=3,B=4; A=4,B=3; A=5,B=2; A=6,B=1 概率为6/36=1/6，所以信息量 -log(1/6)=1+log3 ~ bit (b)骰子A和B,掷出12点只有1种可能： A=6,B=6 概率为1/36，所以信息量 -log(1/36)=2+log9 ~ bit 解： 出现各点数的概率和信息量： 1 点：1/21 , log21 ?bit ; 2 点：2/21 , log21-1 ?bit ; 3 点：1/7 , log7 4 点：4/21 , log21-2 5 点：5/21 , log (21/5 )~; 6 点：2/ 7 , log(7/2)? 平均信息量： (1/21) X +(2/21) X +(1/7) X +(4/21) X +(5/21) X +(2/7) 解： X=1:考生被录取；X=0考生未被录取； Y=1：考生来自本市；Y=0考生来自外地； Z=1:考生学过英语；z=o：考生未学过英语 P(X=1)=1/4, P( X=q=3/4; P( Y=1/ X=1)=1/2 ；P( Y=1/ X=0)=1/10 ；P(Z=1/ Y=1 )=1, P( Z=1/ X=0, Y=0 )=, P( Z=1/ X=1, Y=0 )=, P(Z=1/Y=0)= (a)P(X=0,Y=1)=P(Y=1/X=0)P(X=0)=, P(X=1,Y=1)= P(Y=1/X=1)P(X=1)= P(Y=1)= P(X=0,Y=1)+ P(X=1,Y=1)= P(X=0/Y=1)=P(X=0,Y=1)/P(Y=1)=, P(X=1/Y=1)=P(X=1,Y=1)/P(Y=1)= 信息论与编码 第四章 4.5判断以下几种信道是不是准对称信道 （1）?? ????3.02.05.05.03.02.0不是 （2）???? ??????7.03.06.04.03.07.0不是 （3）?? ????7.01.02.02.01.07.0是 （4）?? ????6/13/13/16/16/16/13/13/1 是 4.7计算以下离散无记忆信道DMC 的容量及最佳分布 （1）P=???? ??????---p p p p p p 101001 解： 此为对称信道，达到C 需要等概，则该信道的最佳分布为： X q （X ） = x1 x2 x313 13 13 所以该信道的容量为：C=log 3+（1-p ）log(1?p)+p log p =log3-H 2（p ） (2)P=??????----2/)1(2/)1(2/2 /2/2/2/)1(2/)1(p p p p p p p p 解: 易得该信道为一个准对称信道，假定最佳分布为： X q （X ） = x1 x2 13 13 s1= (1?p)/2p/2p/2(1?p)/2 s2= (1?p)/2p/2p/2(1?p)/2 C=log k - N s *log M s -H =log 2-(1/2*log 1/2+1/2*log 1/2)+(1-p)log(1?p)/2+p log p =log2+(1-p)log(1?p)/2+p log p =log2-H 2（p ） (5)P= 132323 13 解: C=log 2+13×log 13+23×log 23 =0.083 4.10给定离散信道的信道转移概率矩阵P=????? ???????----q q q q p p p p 100100001001,计算其信道容量C 解: 5.1 设信源1 234567()0.20.190.180.170.150.10.01X a a a a a a a p X ????=???? ???? (1) 求信源熵H(X)； (2) 编二进制香农码； (3) 计算平均码长和编码效率. 解： (1) 7 21222222()()log () 0.2log 0.20.19log 0.19 0.18log 0.180.17log 0.170.15log 0.150.1log 0.10.01log 0.012.609/i i i H X p a p a bit symbol ==-=-?-?-?-?-?-?-?=∑ (3) 7 1 ()0.230.1930.1830.1730.153 0.140.0173.141 ()()/ 2.609 3.14183.1% i i i K k p x H X H X K R η===?+?+?+?+?+?+?====÷=∑ 5.2 对习题5.1的信源编二进制费诺码，计算编码效率. 解： 5.3对信源编二进制和三进制 哈夫曼码，计算各自的平均码长和编码效率. 解： 二进制哈夫曼码： x i p(x i)编码码字k i s61 s50.610 s40.391 s30.350 s20.261 x10.20102 x20.191112 x30.1800003 x40.1710013 x50.1500103 s10.111 x60.1001104 x70.01101114 三进制哈夫曼码： x i p(x i)编码码字k i s31 s20.540 s10.261 x10.2221 x20.190002 x30.181012 x40.172022 5-10 设有离散无记忆信源}03.0,07.0,10.0,18.0,25.0,37.0{)(=X P 。 （1）求该信源符号熵H(X)。 （2）用哈夫曼编码编成二元变长码，计算其编码效率。 （3）要求译码错误小于3 10-，采用定长二元码达到（2）中的哈夫曼编码效率，问需要多少个信源符号连在一起编？ 解：（1）信源符号熵为 symbol bit x p x p X H i i i /23.203.0log 03.007.0log 07.010.0log 10.018.0log 18.025.0log 25.037.0log 37.0) (log )()(222222=------=-=∑ （2） 1 x 3x 2x 6 x 5x 4x 0.370.250.180.100.070.03 01 1 1 1 1 0.10 0.20 0.38 0.62 1.00 000111 10110001001 符号概率 编码 该哈夫曼码的平均码长为 符号 码元/3.2403.0407.0310.0218.0225.0237.0)(=?+?+?+?+?+?==∑i i i K x p K 编码效率为9696.03.223 .2)(=== K X H η (3)信源序列的自信息方差为 2 2 22) (792.0)]([)]()[log ()(bit X H x p x p X i i i =-=∑σ 7.00696.90)() (==+= εε η得，由X H X H 5 3 22210 2.6110)7.00(92.70)(?=?=≥-δεσX L 由切比雪夫不等式可得 所以，至少需要1.62×105个信源符号一起编码才能满足要求。 5-12 已知一信源包含8个消息符号，其出现的概率 }04.0,07.0,1.0,06.0,05.0,4.0,18.0,1.0{)(=X P ，则求： （1）该信源在每秒内发出1个符号，求该信源的熵及信息传输速率。 （2）对这8个符号作哈夫曼编码，写出相应码字，并求出编码效率。 （3）采用香农编码，写出相应码字，求出编码效率。 （4）进行费诺编码，写出相应码字，求出编码效率。 解：（1）信源熵 symbol bit x p x p X H i i i /55.204.0log 04.007.0log 07.01.0log 1.006.0log 06.005.0log 05.04.0log 4.018.0log 18.01.0log 1.0) (log )()(22222222=--------=-=∑ 信息传输速率为 s b i t R /55.2= （2）哈夫曼编码： 2 x 8 x 6 x 5x 4x 3x 1x 7x 0.40.180.10.10.070.060.05 0.04符号概率 码字 1 0.09 1 0.130.19 1 0.23 1 0.37 0 10.6 1 1.001 001 01100000100 0101 0001000011 信源各符号的对应哈夫曼曼码字如下： 0.1 0.18 0.4 0.05 0.06 0.1 0.07 0.04 011 001 1 00010 0101 0000 0100 00011 平均码长为 第五章 --习题答案 (2) 哪些码是非延长码？ (3) 对所有唯一可译码求出其平均码长和编译效率。 解：首先，根据克劳夫特不等式，找出非唯一可译码 31123456231244135236:621 63:222222164 63: 164 :22421:2521:2521 C C C C C C --------------?<+++++=<<++?=+?>+?< 5C ∴不是唯一可译码，而4C ： 又根据码树构造码字的方法 1C ，3C ，6C 的码字均处于终端节点 ∴他们是即时码 (1) 因为A,B,C,D四个字母,每个字母用两个码,每个码为0.5ms, 所以每个字母用10ms 当信源等概率分布时,信源熵为H(X)=log(4)=2 平均信息传递速率为bit/ms=200bit/s (2) 信源熵为 H(X)= =0.198bit/ms=198bit/s 5-5 (1) 1 2 1 4 1 8 1 16 1 32 1 64 1 128 1 128 H(U)= 1 2Log2() 1 4 Log4() + 1 8 Log8() + 1 16 Log16 () + 1 32 Log32 () + 1 64 Log64 () + 1 128 Log128 () + 1 128 Log128 () + 1.984 = (2) 每个信源使用3个二进制符号,出现0的次数为 出现1的次数为 P(0)= P(1)= (3) 相应的费诺码 （5）香农码和费诺码相同平均码长为 编码效率为： 5-11 （1）信源熵 （2）香农编码： 平均码长： 编码效率为 （3） 第二章 信息的度量 2.1 信源在何种分布时，熵值最大？又在何种分布时，熵值最小？ 答：信源在等概率分布时熵值最大；信源有一个为1，其余为0时熵值最小。 2.2 平均互信息量I(X;Y)与信源概率分布q(x)有何关系？与p(y|x)又是什么关系？ 答： 若信道给定，I(X;Y)是q(x)的上凸形函数； 若信源给定，I(X;Y)是q(y|x)的下凸形函数。 2.3 熵是对信源什么物理量的度量？ 答：平均信息量 2.4 设信道输入符号集为{x1,x2,……xk}，则平均每个信道输入符号所能携带的最大信息量是多少？ 答：k k k xi q xi q X H i log 1log 1)(log )() (=- =-=∑ 2.5 根据平均互信息量的链规则，写出I(X;YZ)的表达式。 答：)|;();();(Y Z X I Y X I YZ X I += 2.6 互信息量I(x;y)有时候取负值，是由于信道存在干扰或噪声的原因，这种说法对吗？ 答：互信息量) ()|(log ) ;(xi q yj xi Q y x I =，若互信息量取负值，即Q(xi|yj) 答： 由图示可知：4 3)|(4 1)|(32)|(31)|(41)|(43)|(222111110201= = == == s x p s x p s x p s x p s x p s x p 即： 4 3)|(0)|(4 1)|(31)|(32)|(0)|(0 )|(4 1)|(4 3)|(222120121110020100= == = ==== = s s p s s p s s p s s p s s p s s p s s p s s p s s p 可得： 1 )()()() (43)(31)()(31)(41)()(41)(43)(210212101200=+++ = +=+=s p s p s p s p s p s p s p s p s p s p s p s p 第5章有噪信道编码 5.1 基本要求 通过本章学习，了解信道编码的目的，了解译码规则对错误概率的影响，掌握两种典型的译码规则：最佳译码规则和极大似然译码规则。掌握信息率与平均差错率的关系，掌握最小汉明距离译码规则，掌握有噪信道编码定理（香农第二定理）的基本思想，了解典型序列的概念，了解定理的证明方法，掌握线性分组码的生成和校验。 5.2 学习要点 5.2.1 信道译码函数与平均差错率 5.2.1.1 信道译码模型 从数学角度讲，信道译码是一个变换或函数，称为译码函数，记为F 。信道译码模型如图5.1所示。 5.2.1.2 信道译码函数 信道译码函数F 是从输出符号集合B 到输入符号集合A 的映射： *()j j F b a A =∈，1,2,...j s = 其含义是：将接收符号j b B ∈译为某个输入符号* j a A ∈。译码函数又称译码规则。 5.2.1.3 平均差错率 在信道输出端接收到符号j b 时，按译码规则* ()j j F b a A =∈将j b 译为*j a ，若此时信道输入刚好是 *j a ，则称为译码正确，否则称为译码错误。 j b 的译码正确概率是后验概率： *(|)()|j j j j P X a Y b P F b b ??===?? （5.1） j b 的译码错误概率： (|)()|1()|j j j j j P e b P X F b Y b P F b b ????=≠==-???? （5.2） 平均差错率是译码错误概率的统计平均，记为e P ： {} 1 1 1 1 ()(|)()1()|1(),1()|()s s e j j j j j j j s s j j j j j j j P P b P e b P b P F b b P F b b P F b P b F b ====??==-?? ??????=-=-?????? ∑∑∑∑ （5.3） 5.2.2 两种典型的译码规则 两种典型的译码规则是最佳译码规则和极大似然译码规则。 图5.1 信道译码模型 }r a信息论与编码第二章答案解析
信息论与编码习题与答案第二章
信息论与编码习题参考答案(全)
信息论与编码习题与答案第四章
(完整版)信息论与编码概念总结
信息论与编码第一章答案
信息论与编码理论习题答案
信息论与编码第五章答案
信息论与编码试题集与答案(新)
信息论与编码习题参考答案(全)
王育民信息论与编码理论第四章答案2
信息论与编码理论第二章习题答案
信息论与编码 第四章 (1)
最新信息论与编码第五章答案
信息论与编码习题与答案第五章
信息论与编码-曹雪虹-第五章-课后习题答案
信息论与编码第二章答案
第5章-信息理论与编码课后答案
相关主题
文本预览