3.1离散无记忆信源等长编码

3.1离散无记忆信源等长编码

几乎无失真等长编码

选择L 足够长，使

其中，

为与L 有关的正数，且当时有,才能不损失信息。然而这样的编码不总能保证单义可译，但非单义可译所引起的错误可渐近为任意小。反之，若，编码误差变得任意大。

]

)([log L U H L D N ε+≥L ε∞→L 0→L ε])([log L U H L D N ε?<

3.2 离散无记忆（简单）信源的等长编码编码速率

R=N log D/L

R=N log D/L≥log K

关于编码速率的说明：

表示一个长度为N的D元码字给一个长度为L的消息的每个符号所提供的信息量。

一个消息序列U

L

每符号含有信息量算术平均为：信源的熵为H(U)

设I(u

l )的方差为

()/()/

L L l

l

I I L I u L

==∑

u

()

()()

()()

l k k

k

E I u p a I a H U

==

∑

2

I

σ

()

()()

()2 2()()

I l k k

k

D I u p a I a H U

σ==?

∑

3.2 离散无记忆（简单）信源的等长编码

例信源发出的消息序列长度L=8。

长为8的序列是(a 1+a 2)8的展开式的所有项，共28个。消息序列的概率是(p 1+p 2)8的二项展开式中的各项。

1

2~1/43/4l a a u ????

??

()()()12~1/4

3/4l I a I a I u ??

??

??()0.81H U bit

=()()()()2

2

()()0.471

I

l k k k

D I u p a I a H U σ==?=∑()()()

888111/8I a I a I a ==()()()()35

8121235/8

I a a I a I a =+

3.2.2 信源划分定理

?典型序列集的定义

?令H(U)是集的熵，，

?定义为给定信源U 输出长为L 的典型序列集

它称作弱ε典型序列集；相应地，

的补集为非典型序列集。

3.2 离散无记忆（简单）信源的等长编码

{})(,k a p U 0>ε{}

εεε+≤≤?=)()(:),(U H I U H L T L L U u ()

()/,L

L

L L I

I L U

=∈u u ),(εL T U

令u L 是信源的长为L 的输出序列，其中，是序列中出现的次数。称为强典型序列集。

例4次掷硬币试验强典型序列有{0011}, {1001}, {1100}, {1100}, {0011}, {1010}.

ε>{}

(,):[()][()]U L k k k T L L p a L L p a εεε=?≤≤+u k L k a {},()k U p a

例信源发出的消息序列长度L=8,对其二元随机编码。I 8的数值：

2, 1.80, 1.60, 1.41, 1.21, 1.01, 0.811, 0.61, 0.415

12~1/43/4a a U ??

??

??

()0.81H U bit

=87162534435261781121212121212122

a ,a a ,a a ,a a ,a a ,a a ,a a ,a a ,a

()()20.471

I k D I a σ==

()4435261781212

12

12

2

22

a a ,a a ,a a ,a a ,a 163/0.3679.

I

L σε

=若对共个序列编码,错误概率上限是

()()()()()()()8

7

6

2

5

3

01238

8

8

8

C 1/4C 1/43/4C 1/43/4C 1/43/40.027

e P =+++=261735121212

0.2a a ,a a ,a a

ε=弱典型序列是44352617812

12

12

12

2

0.4a a ,a a ,a a ,a a ,a

ε=弱典型序列是87162531121212

a ,a a ,a a ,a a

信息论与编码理论无失真信源编码历年考试解答

Equation Chapter 1 Section 1 第4章无失真信源编码 习题及其参考答案 4-1 有一信源，它有六个可能地输出，其概率分布如下表所示，表中给出了对应地码A、B、C、D、E和F （1）求这些码中哪些是唯一可译码； （2）求哪些码是及时码； （3）对所有唯一可译码求出其平均码长. 4-2 设信源.对此次能源进行m元唯一可译编码，其对应地码长为（l1,l2,…,l6）=(1,1,2,3,2,3)，求m值地最好下限.（提示：用kraft不等式） 4-3设信源为，编成这样地码：（000，001， 010，011，100，101，110，111）.求 （1）信源地符号熵； （2）这种码地编码效率； （3）相应地仙农码和费诺码. 4-4求概率分布为信源地二元霍夫曼编码.讨论此码对于概率分布为 地信源也是最佳二元码. 4-5有两个信源X和Y如下：

（1）用二元霍夫曼编码、仙农编码以及费诺编码对信源X和Y进行编码，并计算其平均码长和编码效率； （2）从X，Y两种不同信源来比较三种编码方法地优缺点. 4-6设二元霍夫曼码为（00，01，10，11）和（0，10，110，111），求出可以编得这样 霍夫曼码地信源地所有概率分布. 4-7设信源为，求其三元霍夫曼编码. 4-8若某一信源有N个符号，并且每个符号等概率出现，对这个信源进行二元霍夫曼编码，问当N=2i和N=2i+1（i是正整数）时，每个码值地长度是多少？平均码长是多少？ 4-9现有一幅已离散量化后地图像，图像地灰度量化分成8级，如下表所示.表中数字为相应像素上地灰度级. （1）不考虑图像地任何统计特性，对图像进行二元等长编码，这幅图像共需要多少个二元符号描述？ （2）若考虑图像地统计特性，求这幅图像地信源熵，并对每个灰度级进行二元霍夫曼编码，问平均每个像素需用多少二元符号表示. 4-10在MPEG中为了提高数据压缩比，采用了____方法. A．运动补偿与运行估计 B.减少时域冗余与空间冗余 C．帧内图像数据与帧间图像数据压缩 D.向前预测与向后预测 4-11 JPEG中使用了____熵编码方法.

第3章_离散信源()题与答案

该信源发出的信息序列为(202 120 130 213 001 203 210 110 321 010 021 032 011 223 210)。求： (1)此消息的自信息量是多少？ (2)此消息中平均每符号携带的信息量是多少？ 解： (1) 此消息总共有14个0、13个1、12个2、6个3,因此消息发出的概率是： 此消息的信息量是：I二-log p =87.811 bit 3.2某一无记忆信源的符号集为｛0, 1｝，已知信源的概率空间为 ;x 口0 1: ]P(X)」J/4 3/4： (1)求信息符号的平均熵； ⑵ 由100个符号构成的序列，求某一特定序列(例如有m个“0”和(100 - m个“1”) 的自信息量的表达式； ⑶计算⑵中序列的熵。 解： (1) 丁"133、 H(X)二一p(X|) log p(X|) log log 0.811 bit i\_4 4 4 4 J 100 -m 3 —,100 4 3〔00 -m l(xj - -log p(xj - -log 10厂=41.5 1.585m bit 4 H(X100) =100H(X) =100 0.811 =81.1 bit 其概率空间为 ；X L X1 = 0 X2 =1 X3 = 2 X4 = 3 J P(X)J '、3/8 1/4 1/4 1/8 离散无记忆信源 ⑵ 此消息中平均每符号携带的信息量是: I /n =87.811/45=1.951 bit z-m 100 -m g盯(4〕

3.5某信源的消息符号集的概率分布和二进制代码如题表 3.2所列

(1)求信息的符号熵； (2)求每个消息符号所需要的平均二进制码的个数或平均代码长度。进而用这一结果求码序列中的一个二进制码的熵； (3)当消息是由符号序列组成时，各符号之间若相互独立，求其对应的二进制码序列中出现 0和1的无条件概率P o和P i，求相邻码间的条件概率P o/1、P l/0、P i/1、P o/o。 解： (1) 「1 1 1 1 1 1 1 1 \ H(X) - p(xjlogp(x) log log log log 1.75 bit i(2 2448888 丿 ⑵ - 丁1111 L =E(h)=為p(x)h 1 ——2 — 3 — 3=1.75 i 2 4 8 8 1 1 H N(X) H (X) H(X) =1 bit N L 设消息序列长为N，则u0、u1、u2、u3的个数分别为N/2, N/4, N /8, N/8个。 N N N N 7N 则0的个数为一1 — 1 — 1 — 0 =—— 2 4 8 8 8 N N N N 7N 而1的个数为0 1 2 3 = 2 4 8 8 8 因而p0 = p1 = 0.5 P0/1 二P10 / P1 =屮P 0/0 = P00 / P0 P1/0 二p 01 / p 1 二2__2 1 P1/1 二 p 11 / p 1

第5章_无失真信源编码题与答案

第5章_无失真信源编 码题与答案 本页仅作为文档封面，使用时可以删除 This document is for reference only-rar21year.March

有一信源，它有6个可能的输出，其概率分布如题表所示，表中给出了对应的码 E D C B A ,,,, 和 F 。 (1) 求这些码中哪些是唯一可译码； (2) 求哪些是非延长码（即时码）； (3) 对所有唯一可译码求出其平均码长L 。 解： (1) 唯一可译码：A ，B ，C A 是等长码，码长3，每个码字各不相同，因此是唯一可译码。 B 是非即时码，前缀码，是唯一可译码。 C 是即时码，是唯一可译码。 D 是变长码，码长}4 ,4 ,4 ,3 ,2 ,1{，不是唯一可译码，因为不满足Kraft 不等式。 10625.132******** 321≥=??? ? ??+??? ??+??? ??+??? ??=∑-i l i r E 是变长码，码长}4 ,4 ,4 ,4 ,2 ,1{，满足Kraft 不等式，但是有相同的码字， 110053==W W ，不是唯一可译码。 1142121214 21≤=??? ? ??+??? ??+??? ??=∑-i l i r F 是变长码，码长}3 ,3 ,3 ,3 ,3 ,1{，不满足Kraft 不等式，不是唯一可译码。 1125.1521213 1≥=??? ? ??+??? ??=∑-i l i r (2) 非延长码：A ，C (3)

3125.1616 1 5161416131612411213 =?+?+?+?+?+?= ?===∑i i i C B A l p L L L

第5章_无失真信源编码 题与答案

有一信源，它有6个可能的输出，其概率分布如题表所示，表中给出了对应的码E D C B A ,,,, 和 F 。 (1) 求这些码中哪些是唯一可译码； * (2) 求哪些是非延长码（即时码）； (3) 对所有唯一可译码求出其平均码长L 。 解： (1) 唯一可译码：A ，B ，C A 是等长码，码长3，每个码字各不相同，因此是唯一可译码。 B 是非即时码，前缀码，是唯一可译码。 C 是即时码，是唯一可译码。 D 是变长码，码长}4 ,4 ,4 ,3 ,2 ,1{，不是唯一可译码，因为不满足Kraft 不等式。 10625.132******** 321≥=??? ? ??+??? ??+??? ??+??? ??=∑-i l i r ） E 是变长码，码长}4 ,4 ,4 ,4 ,2 ,1{，满足Kraft 不等式，但是有相同的码字，110053==W W ，不是唯一可译码。 1142121214 21≤=??? ? ??+??? ??+??? ??=∑-i l i r F 是变长码，码长}3 ,3 ,3 ,3 ,3 ,1{，不满足Kraft 不等式，不是唯一可译码。 1125.1521213 1≥=??? ? ??+??? ??=∑-i l i r

(2) 非延长码：A ，C (3) 3125 .16161 5161416131612411213 =?+?+?+?+?+?=?===∑i i i C B A l p L L L 设离散信源的概率空间为 % ???? ??=??????05.010.015.020.025.025.0654321 s s s s s s P S 对其采用香农编码，并求出平均码长和编码效率。 解： ()%7.897 .2423 .2)( 423.205.0log 05.0...25.0log 25.0log )(7 .2505.041.0315.032.0225.0225.0=== =?++?-=-==?+?+?+?+?+?=?=∑∑L S H bit p p S H l p L i i i i i i η 设无记忆二元信源，其概率995.0 ,005.021==p p 。信源输出100=N 的二元序列。在长为 100=N 的信源序列中只对含有3个或小于3个“1”的各信源序列构成一一对应的一组等长码。 (1) 求码字所需要的长度； (2) 考虑没有给予编码的信源序列出现的概率，该等长码引起的错误概率E p 是多少 } 解： (1)

第3章_离散信源(1)题与答案

3.1 设有一离散无记忆信源，其概率空间为 ??? ? ??=====??????8/14/1324/18/310)(4321x x x x X P X 该信源发出的信息序列为(202 120 130 213 001 203 210 110 321 010 021 032 011 223 210)。 求： (1) 此消息的自信息量是多少？ (2) 此消息中平均每符号携带的信息量是多少？ 解： (1) 此消息总共有14个0、13个1、12个2、6个3，因此消息发出的概率是： 6 2514814183?? ? ?????? ?????? ??=p 此消息的信息量是：bit p I 811.87log =-= (2) 此消息中平均每符号携带的信息量是：bit n I 951.145/811.87/== 3.2 某一无记忆信源的符号集为{0, 1}，已知信源的概率空间为 ???? ??=??????4/34/110 )(X P X (1) 求信息符号的平均熵； (2) 由100个符号构成的序列，求某一特定序列（例如有m 个“0”和（100 - m ）个“1”）的自信息量的表达式； (3) 计算(2)中序列的熵。 解： (1) bit x p x p X H i i i 811.043log 4341log 41 )(log )()(=??? ??+-=-=∑ (2) bit m x p x I x p m i i m m m i 585.15.4143 log )(log )(4 34341)(100 100100 100100+=-=-==? ? ? ?????? ??=--- (3) bit X H X H 1.81811.0100)(100)(100=?== 3.5 某信源的消息符号集的概率分布和二进制代码如题表3.2所列。 题表 3.2

(完整版)计算离散信源的熵matlab实现

实验一：计算离散信源的熵 一、实验设备: 1、计算机 2、软件：Matlab 二、实验目的: 1、熟悉离散信源的特点； 2、学习仿真离散信源的方法 3、学习离散信源平均信息量的计算方法 4、熟悉 Matlab 编程； 三、实验内容: 1、写出计算自信息量的Matlab 程序 2、写出计算离散信源平均信息量的Matlab 程序。 3、掌握二元离散信源的最大信息量与概率的关系。 4、将程序在计算机上仿真实现，验证程序的正确性并完成习题。 四、实验报告要求 简要总结离散信源的特点及离散信源平均信息量的计算,写出习题的MATLAB 实现语句。 信息论基础： 自信息的计算公式 21()log a I a p = Matlab 实现：I=log2(1/p) 或I=-log2(p) 熵（平均自信息）的计算公式 22111()log log q q i i i i i i H x p p p p ====-∑∑ Matlab 实现：HX=sum(-x.*log2(x))；或者h=h-x(i)*log2(x(i)); 习题： 1. 甲地天气预报构成的信源空间为： 1111(),,,8482 X p x ??????=???????? 小雨 云 大雨晴 乙地信源空间为： 17(),88 Y p y ??????=???????? 小雨晴 求此两个信源的熵。求各种天气的自信息量。 案：() 1.75;()0.5436H X H Y ==

运行程序： p1=[1/2,1/4,1/8,1/8];%p1代表甲信源对应的概率p2=[7/8,1/8];%p2代表乙信源对应的概率 H1=0.0; H2=0.0; I=[]; J=[]; for i=1:4 H1=H1+p1(i)*log2(1/p1(i)); I(i)=log2(1/p1(i)); end disp('自信息量分别为：'); I disp('H1信源熵为：'); H1 for j=1:2 H2=H2+p2(j)*log2(1/p2(j)); J(j)=log2(1/p2(j)); end disp('自信息量分别为：'); J disp('H2信源熵为：'); H2

离散信源无失真信源编码

离散信源无失真信源编码 目的： 熟练掌握无失真信源编码的方法；熟练掌握Huffman 编码的平均码长和编码效率的 Huffman 编码的基本原理及特点： Huffman 编码是一种可变长编码算法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码。Huffman 编码一般利用二叉树结构实现，其基本原理是频繁使用的数据用较短的代码代替，较少使用的数据用较长的代码代替，每个数据的代码各不相同。 Huffman 编码在信源符号表示平均所需要的比特数方面是最优的，而且也满足前缀条件（即唯一可译码）。 在编码效率方面，Huffman 编码是基于二叉树算法的特点以及性质。从书本的例题看出Huffman 编码方法得到的码是不唯一的。不同的排序准则以及不同的符号分配都会影响到最后的结果，虽然编码的效率相同，但是影响到了编码的质量。从课本上的例题可以看出，二叉树的层数较少的，编码质量较高（从码方差得出）。在编码的时候，要尽量避免二叉树的稀疏性给编码质量带来的影响。要减少二叉树的稀疏性就要提高二叉树的利用率，减少二叉树的层数。 Huffman 编码基本步骤，画出程序流程图： Huffman 编码步骤： （1）将信源符号按概率递减的次序排序 （2）将两个最小概率的分支分别标记为‘1’和‘0’，他们的结合点为两分支概率之和 （3）将上面的概率和看作一个新符号的概率。 （4）重新排列后，重复上面的步骤。 （5）从最后的节点开始读取，到要找的符号，路径的分支标号就是码字 流程图：

输入数据： 输入编码： 当输入为例题中数据时，输出为：当输入是习题中数据时，输出为： 讨论不同的Huffman 编码的平均码长如何变化，码字长度偏离平均码长对编码性能的影响。 答：不同的Huffman编码方法得到的平均码长是相同的，编码效率也相同。但是，不同的编码方法对码的质量会产生影响。通过求码方差可知，码方差越小，编码质量越高。从树的结构方面来看，就是树的层数较少的编码方法质量较高。

离散信源题与答案

离散信源题与答案 Last revision date: 13 December 2020.

3.1 设有一离散无记忆信源，其概率空间为 该信源发出的信息序列为(202 120 130 213 001 203 210 110 321 010 021 032 011 223 210)。求： (1) 此消息的自信息量是多少？ (2) 此消息中平均每符号携带的信息量是多少？ 解： (1) 此消息总共有14个0、13个1、12个2、6个3，因此消息发出的概率是： 此消息的信息量是：bit p I 811.87log =-= (2) 此消息中平均每符号携带的信息量是：bit n I 951.145/811.87/== 3.2 某一无记忆信源的符号集为{0, 1}，已知信源的概率空间为 (1) 求信息符号的平均熵； (2) 由100个符号构成的序列，求某一特定序列（例如有m 个“0”和（100 - m ）个“1”）的自信息量的表达式； (3) 计算(2)中序列的熵。 解： (1) (2) (3) 3.5 某信源的消息符号集的概率分布和二进制代码如题表3.2所列。 (1) (2) 求每个消息符号所需要的平均二进制码的个数或平均代码长度。进而用这一结果求码序列中的一个二进制码的熵； (3) 当消息是由符号序列组成时，各符号之间若相互独立，求其对应的二进制码序列中出现0和1的无条件概率0p 和1p ，求相邻码间的条件概率1/0p 、0/1p 、1/1p 、0/0p 。 解： (1) (2) (3) 设消息序列长为N ，则0u 、1u 、2u 、3u 的个数分别为8/ ,8/ ,4/ ,2/N N N N 个。 则0的个数为 8 708181412N N N N N =?+?+?+? 而1的个数为8738281402N N N N N =?+?+?+?

实验三 无失真信源编码

实验三 无失真信源编码 一、[实验目的] 1、理解香农第一定理指出平均码长与信源之间的关系； 2、加深理解香农编码具有的重要的理论意义。 3、掌握霍夫曼编码的原理； 4、掌握霍夫曼编码的方法和步骤； 二、[实验环境] windows XP,MATLAB 7 三、[实验原理] 香农第一定理： 设离散无记忆信源为 12 (1) (2)....()S s s sq P p s p s p sq ????=???????? 熵为H(S)，其N 次扩展信源为 12 (1) (2)....()N q S p p p q P αααααα????=???????? 熵为H(S N )。码符号集X=（x1,x2,…,xr ）。先对信源N S 进行编码，总可以找 到一种编码方法，构成惟一可以码，使S 中每个信源符号所需的平均码长满足： 1N L H S H S N N +>≥（）（）logr logr 当N →∞时 lim ()N r N L H S N →∞= N L 是平均码长 1 ()N q N i i i L p αλ==∑ i λ是i α对应的码字长度 四、[实验内容] 1、在给定离散无记忆信源 S P s1 s2 s3 s4 1/8 5/16 7/16 1/8 =

条件下，实现二进制霍夫曼编码，求最后得到的码字并算出编码效率。 五、[实验过程] 每个实验项目包括：1)设计思路2)实验中出现的问题及解决方法； 某一离散信源概率分布：p=[1/2,1/4,1/8,1/16,1/16] 求信源的熵，并对该信源进行二元哈夫曼编码，得到码字和平均码长以及编码效率。 Matlab程序： function [h,l]=huffman(p) p=[1/2 1/4 1/8 1/16 1/16]; if length(find(p<0))~=0, error('Not a prob.vector,there is negative component') end if abs (sum(p)-1)>10e-10 error('Input is not a prob.vector,the sun of the components is not equal to 1') end n=length(p); q=p; m=zeros(n-1,n); for i=1:n-1 [q,l]=sort(q); m(i,:)=[l(1:n-i+1),zeros(1,i-1)]; q=[q(1)+q(2),q(3:n),1]; end for i=1:n-1 c(i,:)=blanks(n*n); end c(n-1,n)='0'; c(n-1,2*n)='1'; for i=2:n-1

离散信源题与答案

? ?? ???=====??????8/14/1324/18/310)(4321x x x x X P X 该信源发出的信息序列为(202 120 130 213 001 203 210 110 321 010 021 032 011 223 210)。 求： (1) 此消息的自信息量是多少 (2) 此消息中平均每符号携带的信息量是多少 解： (1) 此消息总共有14个0、13个1、12个2、6个3，因此消息发出的概率是： 6 2514814183?? ? ?????? ?????? ??=p 此消息的信息量是：bit p I 811.87log =-= (2) 此消息中平均每符号携带的信息量是：bit n I 951.145/811.87/== 某一无记忆信源的符号集为{0, 1}，已知信源的概率空间为 ???? ??=??????4/34/110 )(X P X (1) 求信息符号的平均熵； (2) 由100个符号构成的序列，求某一特定序列（例如有m 个“0”和（100 - m ）个“1”）的自信息量的表达式； (3) 计算(2)中序列的熵。 解： (1) bit x p x p X H i i i 811.043log 4341log 41 )(log )()(=??? ??+-=-=∑ (2) bit m x p x I x p m i i m m m i 585.15.414 3 log )(log )(4 34341)(100 100100 100100+=-=-==? ? ? ?????? ??=--- (3) bit X H X H 1.81811.0100)(100)(100=?== 某信源的消息符号集的概率分布和二进制代码如题表所列。 题表

离散信源题与答案

设有一离散无记忆信源，其概率空间为 ??? ? ??=====??????8/14/1324/18/310)(4321x x x x X P X 该信源发出的信息序列为(202 120 130 213 001 203 210 110 321 010 021 032 011 223 210)。 求： (1) 此消息的自信息量是多少？ (2) 此消息中平均每符号携带的信息量是多少？ 解： (1) 此消息总共有14个0、13个1、12个2、6个3，因此消息发出的概率是： 6 2514814183?? ? ?????? ?????? ??=p 此消息的信息量是：bit p I 811.87log =-= (2) 此消息中平均每符号携带的信息量是：bit n I 951.145/811.87/== 某一无记忆信源的符号集为{0, 1}，已知信源的概率空间为 ???? ??=??????4/34/110 )(X P X (1) 求信息符号的平均熵； (2) 由100个符号构成的序列，求某一特定序列（例如有m 个“0”和（100 - m ）个“1”）的自信息量的表达式； (3) 计算(2)中序列的熵。 解： (1) bit x p x p X H i i i 811.043log 4341log 41 )(log )()(=??? ??+-=-=∑ (2) bit m x p x I x p m i i m m m i 585.15.4143 log )(log )(4 34341)(100 100100 100100+=-=-==? ? ? ?????? ??=--- (3) bit X H X H 1.81811.0100)(100)(100=?== 某信源的消息符号集的概率分布和二进制代码如题表所列。 题表

第5章_无失真信源编码 题与答案资料

5.1 有一信源，它有6个可能的输出，其概率分布如题 5.1表所示，表中给出了对应的码 E D C B A ,,,, 和 F 。 (1) 求这些码中哪些是唯一可译码； (2) 求哪些是非延长码（即时码）； (3) 对所有唯一可译码求出其平均码长L 。 解： (1) 唯一可译码：A ，B ，C A 是等长码，码长3，每个码字各不相同，因此是唯一可译码。 B 是非即时码，前缀码，是唯一可译码。 C 是即时码，是唯一可译码。 D 是变长码，码长}4 ,4 ,4 ,3 ,2 ,1{，不是唯一可译码，因为不满足Kraft 不等式。 10625.132******** 321≥=??? ? ??+??? ??+??? ??+??? ??=∑-i l i r E 是变长码，码长}4 ,4 ,4 ,4 ,2 ,1{，满足Kraft 不等式，但是有相同的码字，110053==W W ，不是唯一可译码。 1142121214 21≤=??? ? ??+??? ??+??? ??=∑-i l i r F 是变长码，码长}3 ,3 ,3 ,3 ,3 ,1{，不满足Kraft 不等式，不是唯一可译码。 1125.1521213 1≥=??? ? ??+??? ??=∑-i l i r (2) 非延长码：A ，C (3) 3125.1616 1 5161416131612411213 =?+?+?+?+?+?= ?===∑i i i C B A l p L L L

5.7 设离散信源的概率空间为 ???? ??=??????05.010.015.020.025.025.0654321 s s s s s s P S 对其采用香农编码，并求出平均码长和编码效率。 解： ()%7.897 .2423 .2)( 423.205.0log 05.0...25.0log 25.0log )(7 .2505.041.0315.032.0225.0225.0=== =?++?-=-==?+?+?+?+?+?=?=∑∑L S H bit p p S H l p L i i i i i i η 5.8 设无记忆二元信源，其概率995.0 ,005.021==p p 。信源输出100=N 的二元序列。在长为100=N 的信源序列中只对含有3个或小于3个“1”的各信源序列构成一一对应的一组等长码。 (1) 求码字所需要的长度； (2) 考虑没有给予编码的信源序列出现的概率，该等长码引起的错误概率E p 是多少？ 解： (1) 码字中有0个“1”，码字的个数：10 100=C 码字中有1个“1”，码字的个数：1001100=C 码字中有2个“1”，码字的个数：49502100=C 码字中有3个“1”，码字的个数：1617003 100=C 18 35.17166751log log 166751 161700495010013100210011000100===≥≥=+++=+++=i r i l l q l q r C C C C q i

第章离散信源题与答案

设有一离散无记忆信源，其概率空间为 该信源发出的信息序列为(202032)。求： (1)此消息的自信息量是多少？ (2)此消息中平均每符号携带的信息量是多少？ 解： (1) 此消息总共有14个0、13个1、12个2、6个3，因此消息发出的概率是： 此消息的信息量是：bit p I 811.87log =-= (2) 此消息中平均每符号携带的信息量是：bit n I 951.145/811.87/== 某一无记忆信源的符号集为{0,1}，已知信源的概率空间为 (1)求信息符号的平均熵； (2)由100个符号构成的序列，求某一特定序列（例如有m 个“0”和（100-m ）个“1”）的自信息量的表达式； (3)计算(2)中序列的熵。 解： (1) (2) (3) 某信源的消息符号集的概率分布和二进制代码如题表所列。 (1)(2)求每个消息符号所需要的平均二进制码的个数或平均代码长度。进而用这一结果求码序列中的一个二进制码的熵； (3)当消息是由符号序列组成时，各符号之间若相互独立，求其对应的二进制码序列中出现0和1的无条件概率0p 和1p ，求相邻码间的条件概率1/0p 、0/1p 、1/1p 、0/0p 。 解： (1) (2) (3) 设消息序列长为N ，则0u 、1u 、2u 、3u 的个数分别为8/ ,8/ ,4/ ,2/N N N N 个。 则0的个数为 8 708181412N N N N N =?+?+?+? 而1的个数为8738281402N N N N N =?+?+?+?

因而5.010==p p 设有一个信源，它产生0，1序列的信息。该信源在任意时间而且不论以前发生过什么消息符号，均按P(0)=，P(1)=的概率发出符号。 (1)试问这个信源是否是平稳的； (2)试计算H(X 2),H(X 3/X 1X 2)及H ∞； (3)试计算H(X 4)并写出X 4信源中可能有的所有符号。 解： (1) 这个信源是平稳无记忆信源。因为有这些词语：“它在任意时间．．．．而且不论以前发生过什么符．．．．．．．．．．号． ……” (2) (3) 有一马尔可夫信源，已知转移概率为3/2)/(11=S S p ，3/1)/(12=S S p ，1)/(21=S S p ，0)/(22=S S p 。试画出状态转移图，并求出信源熵。 解： 黑白传真机的信息元只有黑色和白色两种X ={黑，白}，一般气象图上黑色出现的概率为P(黑)=，白色出现的概率为P(白)=，黑白消息前后没有关联，其转移概率为P(白/白)=，P(黑/白)=，P(白/黑)=，P(黑/黑)=。求该一阶马尔可夫信源的不确定性H(X/X)，并画出该信源的状态转移图。 解： 设信源产生A,B,C 三种符号2/1)/(=B B p ，4/1)/()/(==B C p B A p ，8/5)/(=A A p ，4/1)/(=A B p ，8/1)/(=A C p ，8/5)/(=C C p ，4/1)/(=C B p ，8/1)/(=C A p 。试计算冗余度。 解： 一阶马尔可夫信源的状态图如下图所示。信源X 的符号集为{0,1,2}。 (1)求平稳后信源的概率分布； (2)求信源的熵H ∞。 解： (1) (2)

通信原理第三章-离散信源及信息测度

第三章 离散信源及其信息测度 3.1 信源的数学模型及分类 信源是信息的来源，是产生消息或消息序列的源泉。信息是抽象的，而消息是具体的。消息不是信息本身，但它包含着和携带着信息。我们不研究信源的内部结构，不研究信源为什么产生和怎样产生各种不同的、可能的消息，而只研究信源的各种可能的输出，以及各种可能消息的不确定性。 在通信系统中收信者在未收到消息以前，对信源发出什么消息是不确定的，是随机的，所以可用随机变量、随机矢量或随机过程来描述信源输出的消息。不同的信源输出的消息不同，可以根据消息的不同的随机性质来对信源进行分类。 1）信源输出的单符号消息可用随机变量描述 在实际情况中，有些信源可能输出的消息数是有限的或可数的，而且每次只输出其中一个消息，如书信文字、计算机的代码、电报符号、阿拉伯数字码等。这些信源输出的都是单个符号的消息，它们符号集的取值是有限的或可数的。我们可用一维离散型随机变量X 来描述这些信源的输出。这样的信源称为离散信源。它的数学模型就是离散型的概率空间 121 2(), ,(),(),()q q X P x a a a P a P a P a =???????????? （3-1） 显然，()(1,2,,)i P a i q =应满足 1()1q i i P a ==∑ （3-2） 式中，{}i a 是离散信源可能的输出符号；()1(1,2,,)0i P a i q ≤=≤是信源输出符号 (1,2,,)i a i q =的先验概率。 有的信源虽然输出的是单个符号（代码）的消息，但其可能出现的消息数是不可数的无限值，即输出消息的取值是连续的，或取值是实数集(,)-∞∞。例如，语音信号、热噪声信号某时间的连续取值数据，遥控系统中有关电压、温度、压力等测得的连续数据。这些数据取值是连续的，但又是随机的。我们可用一维的连续型随机变量X 来描述这些消息，则这种信源称为连续信源，其数学模型是连续型概率空间 ()(x)X P x p =?????????? ??R （3-3） 并满足 ()d 1b a p x x =? 或()d 1p x x =?R 式中，R 表示实数集(,)-∞∞；()p x 是随机变量X 的概率密度函数。 上述离散信源和连续信源是最简单、最基本的情况，信源只输出一个消息（符号），所

信息论与编码理论-第4章无失真信源编码-知识题解答-2007120

第4章无失真信源编码 习题及其参考答案 4-1 有一信源，它有六个可能的输出，其概率分布如下表所示，表中给出了对应的码A、B、C、D、E和F （1）求这些码中哪些是唯一可译码； （2）求哪些码是及时码； （3）对所有唯一可译码求出其平均码长l。 4-2 设信源 6 126 1 126 ()1 ()()() ()i i s s s X p s p s p s p s P X = ?? ?? == ?? ?? ???? ∑。对此次能源进行m元唯一 可译编码，其对应的码长为（l1,l2,…,l6）=(1,1,2,3,2,3)，求m值的最好下限。（提示：用kraft不等式）

4-3设信源为1 234567 811111111()2 4 8 16 3264128128s s s s s s s s X p X ?? ????=???? ??? ??? ，编成这样的码：（000，001，010，011，100，101，110，111）。求 （1）信源的符号熵； （2）这种码的编码效率； （3）相应的仙农码和费诺码。 4-4求概率分布为11122 (,,, ,)3551515 信源的二元霍夫曼编码。讨论此码对于概率分布为 11111 (,,,,)55555 的信源也是最佳二元码。 4-5有两个信源X 和Y 如下： 1 234567()0.200.190.180.170.150.100.01X s s s s s s s p X ????=???????? 1 23456789()0.490.140.140.070.070.040.020.020.01Y s s s s s s s s s p Y ????=???????? （1）用二元霍夫曼编码、仙农编码以及费诺编码对信源X 和Y 进行编码，并计算其平均码长和编码效率； （2）从X ，Y 两种不同信源来比较三种编码方法的优缺点。 4-6设二元霍夫曼码为（00，01，10，11）和（0，10，110，111），求出可以编得这样 霍夫曼码的信源的所有概率分布。 4-7设信源为1234 5678()0.40.20.10.10.050.050.050.05X s s s s s s s s p X ????=???????? ，求其三元霍夫曼编 码。 4-8若某一信源有N 个符号，并且每个符号等概率出现，对这个信源进行二元霍夫曼编码，问当 N =2i 和N =2i +1（i 是正整数）时，每个码值的长度是多少？平均码长是多少？ 4-9现有一幅已离散量化后的图像，图像的灰度量化分成8级，如下表所示。表中数字为相应像

离散信源题与答案完整版

离散信源题与答案集团标准化办公室：[VV986T-J682P28-JP266L8-68PNN]

3.1 设有一离散无记忆信源，其概率空间为 该信源发出的信息序列为(202 120 130 213 001 203 210 110 321 010 021 032 011 223 210)。求： (1) 此消息的自信息量是多少？ (2) 此消息中平均每符号携带的信息量是多少？ 解： (1) 此消息总共有14个0、13个1、12个2、6个3，因此消息发出的概率是： 此消息的信息量是：bit p I 811.87log =-= (2) 此消息中平均每符号携带的信息量是：bit n I 951.145/811.87/== 3.2 某一无记忆信源的符号集为{0, 1}，已知信源的概率空间为 (1) 求信息符号的平均熵； (2) 由100个符号构成的序列，求某一特定序列（例如有m 个“0”和（100 - m ）个“1”）的自信息量的表达式； (3) 计算(2)中序列的熵。 解： (1) (2) (3) 3.5 某信源的消息符号集的概率分布和二进制代码如题表3.2所列。 (1) (2) 求每个消息符号所需要的平均二进制码的个数或平均代码长度。进而用这一结果求码序列中的一个二进制码的熵； (3) 当消息是由符号序列组成时，各符号之间若相互独立，求其对应的二进制码序列中出现0和1的无条件概率0p 和1p ，求相邻码间的条件概率1/0p 、0/1p 、1/1p 、0/0p 。 解： (1) (2) (3) 设消息序列长为N ，则0u 、1u 、2u 、3u 的个数分别为8/ ,8/ ,4/ ,2/N N N N 个。 则0的个数为 8 708181412N N N N N =?+?+?+? 而1的个数为8738281402N N N N N =?+?+?+?

信息论与编码理论-第4章无失真信源编码-习题解答-20071202

第4章 无失真信源编码 习题及其参考答案 4-1 有一信源，它有六个可能的输出，其概率分布如下表所示，表中给出了对应的码A 、B 、C 、D 、E 和F （1）求这些码中哪些是唯一可译码； （2）求哪些码是及时码； （3）对所有唯一可译码求出其平均码长l 。 4-2 设信源6 1 261 126()1() () ()()i i s s s X p s p s p s p s P X =????==???? ???? ∑。对此次能源进行m 元唯一 可译编码，其对应的码长为（l 1,l 2,…,l 6）=(1,1,2,3,2,3)，求m 值的最好下限。（提示：用kraft 不等式） 4-3设信源为1 234567 811111111()2 4 8 16 3264128128s s s s s s s s X p X ?? ????=???? ??? ??? ，编成这样的码：（000，001，010，011，100，101，110，111）。求 （1）信源的符号熵； （2）这种码的编码效率； （3）相应的仙农码和费诺码。 4-4求概率分布为11122 (, ,,,)3551515 信源的二元霍夫曼编码。讨论此码对于概率分布为11111 (,,,,)55555 的信源也是最佳二元码。 4-5有两个信源X 和Y 如下： 1 234567()0.200.190.180.170.150.100.01X s s s s s s s p X ????=???????? 123456789()0.490.140.140.070.070.040.020.020.01Y s s s s s s s s s p Y ????=????????

常见无失真信源编码算法及Matlab实现比较

毕业论文基本要求 1．毕业论文的撰写应结合专业学习，选取具有创新价值和实践意义的论题。 2．论文篇幅一般为8000字以上，最多不超过15000字。 3．论文应观点明确，中心突出，论据充分，数据可靠，层次分明，逻辑清楚，文字流畅，结构严谨。 4．论文字体规范按《本科生毕业论文写作规范》和“论文样板”执行。 5．论文应书写工整，标点正确，用用微机打印后，装订成册。

本科毕业论文（设计）诚信声明 本人郑重声明：所呈交的本科毕业论文（设计），是本人在指导老师的指导下，独立进行研究工作所取得的成果，成果不存在知识产权争议，除文中已经注明引用的内容外，本论文不含任何其他个人或集体已经发表或撰写过的作品成果。对本文的研究做出重要贡献的个人和集体均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学生签名： 时间：年月日 关于论文（设计）使用授权的说明本人完全了解关于收集、保存、使用学位论文的规定，即： 1.按照学校要求提交学位论文的印刷本和电子版本； 2.学校有权保存学位论文的印刷本和电子版，并提供目录检索与阅览服务，在校园网上提供服务； 3.学校可以采用影印、缩印、数字化或其它复制手段保存论文； 本人同意上述规定。 学生签名： 时间：年月日

摘要 随着科学技术的发展，人类已经进入高速发展的信息时代。无论是在经济、政治、生活还是军事领域，信息的重要性已经不言而喻，有关信息的理论越来越受到重视。信息论与编码是信息、通讯、电子工程类专业的基础，对于理论研究和工程运用均有重要的指导作用。而无失真信源编码理论是信息论的理论基础，主要运用在离散信源或数字信号的研究，如文本、表格及工程图纸等信源，对其进行无失真地数据压缩，且完全能够无失真地可逆恢复。 本文首先在于讲述无失真信源编码的运用领域，研究无失真信源编码的意义。紧接着详细介绍了无失真信源编码中常见的三种编码方法及其Matlab实现过程，并将此三种方法进行对比。最后对此三种方法进行归纳总结，并举例说明其在日常生活中的运用。 在信息化、网络化、高科技化的特殊时代环境背景下，无失真信源编码的发展迎来了新的机遇与挑战，其应用领域越来越广，越来越普及，由此推进了编码方法的进一步深入研究。 [关键字]：Shanon编码；Fano编码；Huffman编码

连续信源与无记忆Gaussian信源的比较及若干强偏差定理

２０００年８月 第２９卷第４期 河北工业大学学报ＡｕｇｕＳｔ２０００ＪｏＵＲＮＡＬｏＦＨＥＢＥＩＵＮＩＶＥＲＳＩ丁ＹＯＦＴＥＣＨＮＯＬｏＧＹＶｂｌ，２９Ｎｏ．４ 文章锅亏：ｌｕｕ＾２ｊ“（ｚ【ＪＩＪｕＪ阱。ｕｕ，，一∽ 连续信源与无记忆Ｇａｕｓｓｉ舳信源的比较 及若干强偏差定理 汪忠志１，徐付霞２，司兴华３ ｛ｌ华东冶金学院数理系，安徽马鞍山２４３００２；２唐山师范专科学校数学系，河北唐山０６３０００；ｊ粱山一中，山 荒颦￡【ｌ２７２６００、 摘要：引八相对熵密度偏差作为一般连续信源相对无记忆Ｇａｕｓｓｊａｎ信源的偏差的一种随机 性度量，利用似然比构造几乎处处收敛的上鞅，结合文献［１，４】中提出的分析方法，得到 了任意连续型随机变量序列平方和的一类强偏差定理，其中包含连续信源相对熵密度的若干 极限定理． 关键词：连续信源；ＧａｕＳｓｉａｌｌ信源：相对熵密度；强偏差定理；似然比：上鞅；微分熵 中图分类号：０２１１．４文献标识码：Ａ Ｏ引言 设｛疋，＂≥１）是连续信源．其联合分布密度函数为 ｐ【ｘ－，…，矗）＞Ｏ，置∈月，１≤ｆ≤Ｈ，＂＝１，２，…（１） 令 工（∞）＝一Ｈ－。ｌｏｇｐ（拍，…，矗）（２） 其中ｌｏｇ是自然对数，五∞）称为信源在对刻Ｈ的相对熵密度． 考虑信源｛五，Ｈ≥１＞的渐进均匀分割性，亦即研，ｎ≥１）在一定意义下的极限情况是信息论中的一个重要课题，以往许多学者在诸如遍历性，平稳性，渐进平稳性的假设下作了大量研究．近年来，刘文，杨卫国引入了任意离散信源与无记忆信源及马氏信源的相对熵密度偏差的概念”Ｉ，对信源在没有任何限制的条件下，作了深入的研究，取得了一系列有意义的结果．本文的目的是要利用鞅论的有关结果及刘文的分析方法”’“，就任以连续信源来研究Ｕ，Ｈ≥ｌ｝与强极限定理之间的关系，得到了同离散信源类似的结果． １定义及基本引理 定义１设ｍ，ｄ＞０，令 咖，ｍ㈡２志“ｐ｛一％笋）（３）表示参数为（ｍ，一）的Ｇａｕｓｓｉａｆｌ分布的密度函数，｛咒，ｎ≥１）是具有分布密度（１）的连续信源，如果｛疋，ｎ≥１）是无记忆Ｇａｕｓｓｉａｎ信源且参数为（（碥，矿），Ｈ≥１），则这时 胁）－．”叫哩亟（志ｅｘｐ［一％笋¨＝一唱压ａ＋南砉（＊刊２（４） 收稿日期：２００州．０９ 作者简介：汪忠志（１９６’），男（汉族），安徽安庚＾．华东冶金学院副敦授 　万方数据