下载文档原格式
第三章 信源编码——离散信源无失真编码本章分析问题：在信宿要求无失真接收时，或所有信源信息无损的条件下，离散信源输出的表示——即信源编码问题。
内容：信源分类，信息速率的计算，编码定理，有效编码方法等。
一、信源及其分类 1． 离散信源和连续信源离散信源表示：…Ｕ－２Ｕ－１Ｕ０Ｕ１Ｕ２…其中ＵＬ随机变量，取值范围：Ａ＝｛ａ１，ａ２，…ａｋ｝ ２．无记忆源和有记忆源无记忆源：各ＵＬ彼此统计独立简单信源：各ＵＬ彼此统计独立且服从同一概率分布 Ｐ（ＵＬ＝ａｋ）＝Ｐｋ，ｋ＝１，２，…，Ｋ∑=Kk 1Ｐｋ＝１有记忆源：各ＵＬ取值相关。
ＵＬ＝（Ｕ１，Ｕ２，…，ＵＬ）∈ＵＬ，其概率分布由Ｌ维随机矢量表示，Ｐ（ＵＬ＝ａ）＝Ｐ（Ｕ１＝ａｋ１，…，ＵＬ＝ａｋＬ） ３．平稳信源：概率分布与起始下标无关Ｐ（Ｕ１＝ａｋ１，…，ＵＬ＝ａｋＬ）＝Ｐ（Ｕｔ＋１＝ａｋ１，…，ＵＬ＝ａｋＬ）４．各态历经源：信源输出的随机序列具有各态历经性。
５．有限记忆源：用条件概率Ｐ（ＵＬ，ＵＬ－１，ＵＬ－２，ＵＬ－ｍ）表述。
ｍ为记忆阶数。
６．马尔可夫源：有限记忆源可用有限状态马尔可夫链描述，当ｍ＝１时为简单马尔可夫链。
７．时间离散的连续源：各随机变量ＵＬ取值连续。
８．随机波形源：时间和取值上均连续的信源；由随机过程ｕ（ｔ）描述，时间或频率上有限的随机过程可展开成分量取值连续的随机矢量表示，即时间上离散，取值连续的信源。
９．混合信源二、离散无记忆源的等长编码离散无记忆源：ＤＭＳＬ长信源输出序列：ＵＬ＝（Ｕ１，Ｕ２，…，ＵＬ），Ｕｌ取值｛ａ１，ａ２，…ａｋ｝，共ＫＬ种不同序列。
对每个输出序列用Ｄ元码进行等长编码，码长为Ｎ，则可选码共有ＤＮ个。
１．单义可译码或唯一可译码：条件：ＤＮ≥ＫＬ＝Ｍ，即Ｎ≥ＬｌｏｇＫ／ｌｏｇＤＮ／Ｌ：每个信源符号所需的平均码元数；Ｎ／Ｌ→３．３２２；２．信息无损编码要求：设每个信源符号的信息量为Ｈ（Ｕ），则Ｌ长信源序列的最大熵值为ＬＨ（Ｕ），编码时由于Ｄ个码元独立等概时携带信息量最大，使码长最短。
第4章离散无记忆信源无失真编码主要内容1、基本概念2、码的唯一可译性3、定长编码定理和定长编码方法4、变长编码定理5 变长编码方法6 几种实用的无失真信源编码1、基本概念信源发出的消息序列通常不能直接送给信道传输，需要经过信源编码和信道编码。
信道编码的目的是降低差错率，提高传送的可靠性。
信源编码的目的是为了降低冗余度，提高通信的有效性。
编码是一种映射，是将输入符号映射成码字。
无失真编码，映射一一对应，可逆。
编码器模型：码长：码字所含码元的个数定长编码：所有码字均有相同的码长，对应的码叫做定长码(FLC ，Fixed Length code)；否则为变长编码。
编码器12{,,,}q u u u 12{,,,}r x x x WU12{,,,}q w w w X信源平均码长：码中所有码字码长的统计平均，即码元/符号编码效率：编码后的实际信息率与编码后的最大信息率之比冗余度：l l l2、码的唯一可译性（1）基本概念奇异码：一组码中含相同码字。
非奇异码：所有的码字都不相同。
唯一可译性：码字组成的任意有限长码字序列都能恢复成唯一的信源序列。
续长码：有些码字是在另一些码字后面添加码元得来的。
及时码：码字的最后一个码元出现时，译码器能立即判断一个码字已经结束，可以立即译码。
非续长码：任一码字都不是其它码字的延长。
唯一可译码定长非奇异码非续长码非奇异码5种不同的码35124121142183184()00001000100001001101001110011111110111111i P u W W W W W U u u u u（2）码树和Kraft不等式从树根开始，生长r个树枝，在节点处再各自生长r个树枝。
节点：树枝与树枝的交点。
l阶节点：经过l根树枝到达的节点。
整树：节点长出的树枝数等于r定理：对于任一r进制非续长码，各码字的码长必须满足Kraft不等式：反过来，若上式成立，就一定能构造一个r 进制非续长码。
设信源输出符号集合，每次信源输
9
是⼀一个离散⽆无记忆信源，其概率空间为
其中
信源X的符号集合为
N次扩展信源X N符号集合为
15
的有记忆平稳信源（⼆二维平稳信源）输
23
当且仅当X 1和X 2统计独⽴立时等号成⽴立，此时信源相当于⼆二次⽆无记忆扩展；
当X 1和X 2之间相关时，联合熵⼩小于信息熵之和，即⼩小于单个消息符号X 熵的 2 倍。
由于
25
例：设某⼆二维离散信源X =的原始信源X 的信源模型为
中前后两个符号的条件概率
7/92/901/83/41/80
2/11
9/11
(1)若该信源为⼆二维⽆无记忆扩展信源，求信源的熵。
(2)若该信源为⼆二维平稳信源，如表，求信源的熵。
26
原始信源的熵为：
由条件概率确定的条件熵为：
由于符号之间的依赖性，条件熵⽐比信源熵减少了0.672bit
⼆二维离散⽆无记忆扩展信源的熵为：2H(X)=2*1.542=3.084(bit ）7/92/901/83/4
1/8
2/119/11
27
信源X=
平均每发⼀一个消息所能提供的信息量，即联合熵
则每⼀一个信源符号所提供的平均信息量
⼩小于信源X所提供的平均信息量H(X)=1.542bit，这是
由于符号之间的统计相关性所引起的。
28
维平稳信源输出序列每N个符号⼀一组；各
30
则有：
时：
随N的增加是⾮非递增的；
给定时，平均符号熵≥条件熵；
–平均符号熵随N增加是⾮非递增的；
34
解：
35
1,2,......,J 某时刻随机
……
43
44。
3、编码器的输出f 是一一对应的映射i i P w P u i q()()1,2,, H W H U ()()bit/码字或bit/符号H W H U H X l l()()()bit/码元新信源X ：编码后的信息率R ：平均一个码元携带的信息量。
H W H U H X l l()()()bit/码元平均码长越小，每个码元携带的信息量就越多，传输一个码元就传输了较多的信息。
R X{,,,}12r x x x 编码器f12{,,,}q u u u 12{,,,}r x x x WU12{,,,}q w w w X信源4、编码效率为了衡量编码效果，定义编码效率：编码后的实际信息率与编码后的最大信息率之比。
max max ()()()()log log c R H X H U l H U R H X r l r注：编码效率实际上也是新信源X 的信息含量效率或熵的相对率。
新信源的冗余度也是码的冗余度：1c c X{,,,}12rx x x 编码器f12{,,,}q u u u 12{,,,}r x x x WU12{,,,}q w w w X信源5种不同的码i P u W W W W W U u u u u 351241234()1200001001401000010011810100111001118111110111111W 1: 定长码。
W 3: 变长码。
奇异码。
定长非奇异码肯定是UDC u u u u u u u u u u u u u12434321121211,00,10,010110,01,00,11,00,1,00,1W 2: 定长码。
W 4: 变长码。
W 5: 变长码。
非奇异码。
非奇异码。
非奇异码。
非奇异码。
续长码。
非续长码。
续长码。
及时码。
非及时码。
奇异码肯定不是UDC不是UDC非续长码肯定是UDC 是UDC非及时码。
非续长码。
W 3：1001001唯一可译码定长非奇异码非续长码非奇异码码奇异码非奇异码非唯一可译码唯一可译码定长非奇异码变长非续长码（部分）变长续长码4.3 定长编码定理和定长编码方法1、对信源输出的符号序列进行编码DMS编码器f12{,,,}q u u u 12{,,,}r x x x WU 12{,,,}q w w w XX12{,,,}r x x x DMS编码器f 12{,,,}N q 12{,,,}r x x x WNU 12{,,,}Nq w w w XX12{,,,}r x x x 对信源U 的单个符号进行编码对信源U 的N 长符号串进行编码对扩展信源U N 的单个符号进行编码12i i i iNu u u 1212,,,{,,,}i i iN q u u u u u u2、定长编码定理r 进制定长编码,码长为l N , 可用的码字数目：Nl r Nl Nrq唯一可译max max ()log ()log log N r H U l q H U N r r信息传输率编码效率()()/N H U R H X l Nmax ()()()log c NH X H U l H X r Nbit/码元DMS编码器f 12{,,,}Nq 12{,,,}r x x x W NU 12{,,,}N q w w w XX12{,,,}r x x x定长无失真编码定理：用r 元符号表对离散无记忆信源U 的N 长符号序列进行定长编码，N 长符号序列对应的码长为l N ，若对于任意小的正数ε，有不等式:就几乎能做到无失真编码，且随着序列长度N 的增大，译码差错率趋于0。
信息论与编码实验一离散信源信息量的计算摘要：I.引言- 信息论与编码实验一的主题- 离散信源信息量的计算的重要性II.离散信源的定义- 离散信源的定义- 离散信源的特点III.信息量的计算- 信息量的定义- 离散信源信息量的计算方法- 计算实例IV.信息熵的定义- 信息熵的定义- 信息熵的性质- 计算实例V.编码与解码- 编码的过程- 解码的过程- 编码与解码的实例VI.总结- 离散信源信息量的计算的重要性- 对信息论与编码实验一的回顾正文：I.引言信息论与编码是通信工程中的重要内容，它旨在研究如何在传输过程中有效地传输信息。
在信息论与编码实验一中，我们主要关注离散信源的信息量的计算。
离散信源是我们日常生活中最常见的信源类型，例如文字、声音、图像等。
因此，了解离散信源信息量的计算方法对于理解和应用信息论与编码理论具有重要意义。
II.离散信源的定义离散信源是指信息以离散的方式存在的信源。
离散信源的特点是信息符号是离散的、不连续的，且每个符号的出现是相互独立的。
离散信源可以分为无记忆离散信源和有记忆离散信源。
无记忆离散信源是指信源发出的每个符号的概率分布与过去符号无关，而有记忆离散信源则与过去符号有关。
III.信息量的计算信息量是衡量信息的一个重要指标，它表示了接收者在接收到符号后所获得的信息。
对于离散信源，信息量的计算公式为：I(X) = -∑P(x) * log2(P(x))，其中X 表示离散信源，P(x) 表示符号x 出现的概率。
通过计算信息量，我们可以了解信源的信息程度，从而为后续的编码和解码提供依据。
IV.信息熵的定义信息熵是信息论中的一个重要概念，它表示了信源的平均信息量。
信息熵的定义为：H(X) = -∑P(x) * log2(P(x))，其中X 表示离散信源，P(x) 表示符号x 出现的概率。
信息熵具有以下性质：1）信息熵是信息量的期望；2）信息熵的值是有限的，且在0 到比特数之间；3）当信源的每个符号出现的概率相同时，信息熵最大。
