下载文档原格式
第三章 信源编码——离散信源无失真编码本章分析问题：在信宿要求无失真接收时，或所有信源信息无损的条件下，离散信源输出的表示——即信源编码问题。
内容：信源分类，信息速率的计算，编码定理，有效编码方法等。
一、信源及其分类 1． 离散信源和连续信源离散信源表示：…Ｕ－２Ｕ－１Ｕ０Ｕ１Ｕ２…其中ＵＬ随机变量，取值范围：Ａ＝｛ａ１，ａ２，…ａｋ｝ ２．无记忆源和有记忆源无记忆源：各ＵＬ彼此统计独立简单信源：各ＵＬ彼此统计独立且服从同一概率分布 Ｐ（ＵＬ＝ａｋ）＝Ｐｋ，ｋ＝１，２，…，Ｋ∑=Kk 1Ｐｋ＝１有记忆源：各ＵＬ取值相关。
ＵＬ＝（Ｕ１，Ｕ２，…，ＵＬ）∈ＵＬ，其概率分布由Ｌ维随机矢量表示，Ｐ（ＵＬ＝ａ）＝Ｐ（Ｕ１＝ａｋ１，…，ＵＬ＝ａｋＬ） ３．平稳信源：概率分布与起始下标无关Ｐ（Ｕ１＝ａｋ１，…，ＵＬ＝ａｋＬ）＝Ｐ（Ｕｔ＋１＝ａｋ１，…，ＵＬ＝ａｋＬ）４．各态历经源：信源输出的随机序列具有各态历经性。
５．有限记忆源：用条件概率Ｐ（ＵＬ，ＵＬ－１，ＵＬ－２，ＵＬ－ｍ）表述。
ｍ为记忆阶数。
６．马尔可夫源：有限记忆源可用有限状态马尔可夫链描述，当ｍ＝１时为简单马尔可夫链。
７．时间离散的连续源：各随机变量ＵＬ取值连续。
８．随机波形源：时间和取值上均连续的信源；由随机过程ｕ（ｔ）描述，时间或频率上有限的随机过程可展开成分量取值连续的随机矢量表示，即时间上离散，取值连续的信源。
９．混合信源二、离散无记忆源的等长编码离散无记忆源：ＤＭＳＬ长信源输出序列：ＵＬ＝（Ｕ１，Ｕ２，…，ＵＬ），Ｕｌ取值｛ａ１，ａ２，…ａｋ｝，共ＫＬ种不同序列。
对每个输出序列用Ｄ元码进行等长编码，码长为Ｎ，则可选码共有ＤＮ个。
１．单义可译码或唯一可译码：条件：ＤＮ≥ＫＬ＝Ｍ，即Ｎ≥ＬｌｏｇＫ／ｌｏｇＤＮ／Ｌ：每个信源符号所需的平均码元数；Ｎ／Ｌ→３．３２２；２．信息无损编码要求：设每个信源符号的信息量为Ｈ（Ｕ），则Ｌ长信源序列的最大熵值为ＬＨ（Ｕ），编码时由于Ｄ个码元独立等概时携带信息量最大，使码长最短。
第三章信源编码定理与信道编码定理通信系统的两个基本问题问题一：数据压缩的理论极限是什么。
问题二：通信传输速率的理论极限是什么。
问题一（理论）：如何度量信源产生信息无失真信源编码定理离散无记忆信道离散无记忆信道容量计算时间离散的无记忆连续信道为什么要对信源进行编码?由于信源符号之间存在分布不均匀和相关性，使得信源存在冗余度。
信源编码的主要任务就是减少冗余，提高编码效率。
具体说，就是针对信源输出符号序列的统计特性，寻找一定的方法把信源输出符号序列变换为最短的码字序列。
为什么还要引入有失真编码呢？感觉无失真编码应该优于有失真编码编码器可以看作这样一个系统，它的输入端为原始信源U，其符号集为U:{u1,u2,…,u q}；而信道所能传输的码符号集为X:{x1,x2,…,x r}；编码器的功能是用符号集X中的元素，将原始信源的符号ui 变换为相应的码字符号Wi，(i=1,2,…,q)，所以编码器输出端的符号集为W:{W1,W2,…,W q}。
码的类型信源的类型离散无记忆信源的等长编码无失真等长编码中文电报的汉字编码就是一种等长编码。
这里N=4,D=10 ，即每个汉字用4位十进制数表示。
例如，“西安”编码后就成为4687 16180。
此外，0, 1, 2, ... , 9这10个数字采用如右边的编码方法。
右边的表格中的码字有什么特点？A频率在［0.19,0.21 ］的序列的概率和A频率在［0.19,0.21 ］序列的比例结论●某些特定的信源序列的出现概率可能高于某个特定“常见”序列的出现概率；●随着序列长度的增加，常见序列构成的集合的总体概率趋于1 。
（弱大数定律）想法－渐近无失真编码•如果这些“常见”序列的概率之和接近于1，并且它们的数目相对2L小得多，那么我们就可以只对这些“常见”序列进行编码。
其他序列不做考虑。
•随着L 的增加，其它序列几乎不发生。
这样，这种编码方法也就几乎没有失真了。
如何用数学工具来描述“常见”序列弱典型序列渐进等同分割性质定理：如果U 1,U 2，…是独立离散随机变量,分布服从p (u )，则等价表述：设离散无记忆稳恒信源输出的一个特定序列u 1u 2…u L 。
信源编码定理的内容和其意义
信源编码定理（Source Coding Theorem）是信息论的基本定理之一，由克劳德·香农于1948年提出。
该定理指出，对于一个字符的离散无记忆源，其熵是它的平均编码长度的下限。
具体来说，设X为离散无记忆源，其有N个可能输出符号
x_1, x_2, ..., x_N，相应的输出概率分布为P(X=x_1),
P(X=x_2), ..., P(X=x_N)。
则X的熵H(X)定义为：
H(X) = -Σ(P(X=x_i) * log2(P(X=x_i)))
信源编码定理表述如下：
对于给定的源，如果存在一种编码方式，使得该编码方式满足以下两个条件：
1. 平均编码长度L满足L ≤ H(X) + ε，其中ε为正数。
2. 随着编码长度的增加，编码方式的错误率趋近于0。
那么，对于任意小的ε和δ，当信号序列长度n足够大时，就能以概率大于1-δ找到一种编码方式，使得产生的编码序列长度为n的平均长度小于L+ε，并且错误率小于δ。
信源编码定理的意义在于，它告诉我们通过对信息进行适当的编码，可以将信息压缩到接近其熵的程度，从而提高信息的传输效率。
例如，在通信领域中，信源编码定理的应用可以帮助
我们设计更高效的编码算法，减小数据传输所需的带宽和存储空间，提高数据压缩的效果。
此外，信源编码定理也为信息论的其他重要结果提供了基础，如信道编码定理等。
信源编码贺志强信源编码：将信源符号序列按一定的数学规律映射成由码符号组成的码序列的过程。
成由码符号组成的码序列的过程信源译码：根据码序列恢复信源序列的过程。
信源译码根据码序列恢复信源序列的过程无失真信源编码：即信源符号可以通过编码序列无差错地恢复。
无差错地恢复（适用于离散信源的编码）限失真信源编码：信源符号不能通过编码序列无差错地恢复。
差错地恢复（可以把差错限制在某一个限度内）信源编码的目的：提高传输有效性，即用尽可能短的码符号序列来代表信源符号。
号序列来代表信源符号无失真信源编码定理证明，如果对信源序列进行编码，当序列长度足够长时，存在无失真编码使得传送每信源符号存在无失真编码使得传送每信源符号所需的比特数接近信源的熵。
因此，采用有效的信源编码会使信息传输效率得到提高。
会使信息传输效率得到提高概述一、信源编码器二、信源编码的分类三分组码三、分组码分组码单符号信源编码器符号集符号集AA 1{,,}q a a ii c a 编为1{,,}q c c 编码器码字集合信源序列码符号集1{,}r b b分组码单符号译码器1{,,}q c c 信源序列码字集合1{,,}q a a 译码器1{,}r b b 码符号集简单信源编码器摩尔斯信源编码器将英文字母变成摩尔斯电码将摩尔斯电码变成二进码信源编码器信源编码器（1）信源符号{英文字母英文字母}}（2）二进信道码符号集点、划、字母间隔、单词间隔信道基本符号{0，1}符号点划字母间隔单词间隔电平+ -+++ ---------二进代码 1 0111000000000摩尔斯信源编码器原信源的次扩展码原信源的N N将N个信源符号编成一个码字。
相当于对原信源的N次扩展源的信源符号进行编码。
例信源X={0,1}的二次扩展源的二次扩展源X X 2的符号集为：信源X={0,1}。
对X X2编码，即为原信源编码，即为原信源X X的二{00,01,10,11}。
对{00,01,10,11}编码即为原信源X {00011011}对即为原信源次扩展码。
§3.3信源编码定理由于信源具有渐进等分割性这一很有意义的性质，这使得它在数据压缩及图像压缩中发挥了巨大作用，下面我们引入信源编码定理。
设u = {u 1,u 2,u 3…u n }是服从分布p(u)的无记忆信源产生的n 长序列，我们总是希望找到一种有效的编码方法来描述这些序列，使得编码以后码子数长尽可能少，但又要使从码字复原原序列的错误概率尽可能小。
一个行之有效的方法是将║χ║n个序列序列分成典型序列与非典型序列两部分，对u ∈)(n W ε的每一个序列u 赋予一个编号，称每个编号为一个码字，码字集合I = ｛1，2，…，M ｝，M = ║)(n W ε║，对于那些序列u ∈)(n W ε，统一编号为字母α，这样，在从编码后的码字复制原序列时，如果收到码字是i ∈I,则可唯一的复原成某个u ∈)(n W ε，否则如果收到的是α，则原序列无法正确复制。
我们记这种编码的码率为M n log 1(bit)，其误差概率为e P= p{u ∈)(n W ε}。
为了给出信源编码正定理，我们作以下预备。
设N 长信源序列集合为S ，典型序列集合为)(n W ε，则 1 =∑∈su u p )(≥∑∈W u p n u )()(ε≥∑∈+-W n u U H n )(2])([εε =║)(n W ε║.2])([ε+-U H n ，从而 ║)(n W ε║≤2])([ε+-U H n 。
又因为1-δ< p(u)≤║)(n W ε║.max)()(u p W n u ε∈≤║)(n W ε║.2])([ε--U H n故有 ║)(n W ε║≥()2])([1εδ--⋅-U H n这样就有 ()2])([1εδ--⋅-U H n ≤║)(n W ε║≤2])([ε+U H n 。
于是其码率满足()ε-1log 1n +()U H -ε≤)(log 1n W nε≤()ε+U H 误差概率为}{εε<∈=)(n e W u P P令0→ε，当∞→n 时，码率接近()U H 而0→e P 。
