第五章信源编码(编码定义及定长编码)

i 1 2
28
5.2.3
最佳变长编码
最佳变长编码 凡是能载荷一定的信息量，且码字的 平均长度最短，可分离的变长码的码字集 合称为最佳变长码。
29
5.2.3
最佳变长编码
能获得最佳码的编码方法主要有：

香农（Shannon）


费诺（Fano）
哈夫曼（Huffman）等
30
5.2.3
最佳变长编码
2
2.83
7.11
Pe＝0.04 太大
16
5.2.1
定长编码定理
0.28
H(X ) ＝ 0.90, H(X )
2 8 i 1
( X ) D[ I ( xi )] pi (log pi ) 2 [ H ( X )]2 7.82(bit) 2
若要求译码错误概率 10－6
对于平均符号熵为 HL(X) 的离散平稳 无记忆信源，必存在一种无失真编码方法， 使平均信息率满足不等式
H L (X) K H L (X)
其中为任意小正数。
20
5.2.2
变长编码定理
用变长编码来达到相当高的编码效率， 一般所要求的符号长度 L可以比定长编码小得 多。 编码效率的下界:
编码。
12
5.2.1
定义
定长编码定理

H L ( X) K
为编码效率，即信源的平均符号熵为H(X)， 采用平均符号码长为 来编码，所得的效 K 率。 编码效率总是小于1，且最佳编码效率为
H L ( X) , 0 H L ( X)
13
5.2.1
定长编码定理
编码定理从理论上阐明了编码效率接 近1的理想编码器的存在性，它使输出符号 的信息率与信源熵之比接近于1，即

普通高等教育"十五"国家级规划教材《信息论与编码》 曹雪虹等编著
2
第5章 信源编码 章
信源编码的基础是信息论中的两个编码定理: 信源编码的基础是信息论中的两个编码定理: 无失真编码定理 限失真编码定理 编码定理不但证明了必定存在一种编码方法,可使代码 编码定理不但证明了必定存在一种编码方法, 的平均长度可任意接近但不低于符号熵, 的平均长度可任意接近但不低于符号熵,而且还阐明了 达到这一目的,就要使概率与码长相匹配. 达到这一目的,就要使概率与码长相匹配.
2
+2
2
+2
3
9 = >1 8
因此不存在满足这种K 的唯一可译码. 因此不存在满足这种 i的唯一可译码.
普通高等教育"十五"国家级规划教材《信息论与编码》 曹雪虹等编著
17
5.1 编码的定义
{1,01,001,000} 惟一可译码 {1,01,101,000}不是惟一可译码 不是惟一可译码 均满足克劳夫特不等式
15
5.1 编码的定义
唯一可译码存在的充分和必要条件 唯一可译码存在的充分和必要条件 存在
m -K i ≤ 1 各码字的长度K 应符合克劳夫特不等式 克劳夫特不等式: 各码字的长度 i 应符合克劳夫特不等式: ∑
i =1 n
其中m是进制数; 是信源符号数 是信源符号数. 其中 是进制数;n是信源符号数. 是进制数 如果码是唯一可译码,则必满足该不等式; 如果码是唯一可译码,则必满足该不等式; 如果满足不等式,则这种码长的唯一可译码一定存在, 如果满足不等式,则这种码长的唯一可译码一定存在, 但并不表示所有满足不等式的码一定是唯一可译码; 但并不表示所有满足不等式的码一定是唯一可译码; 该不等式是唯一可译码存在的充要条件, 该不等式是唯一可译码存在的充要条件,而不是唯一可 存在的充要条件 译码的充要条件. 译码的充要条件.

时分复用与时分多址接入技术tdmtdma频分复用与频分多址接入技术fdmfdma码分复用与码分多址接入技术cdmcdma波分复用wdm空分复用sdm统计复用statisticalmultiplex编码问题的一般概念与定义以上四类编码技术都有其专门的学科论述而信息论中仅定性定量地给出各种编码方法的理论极限和性能界限
log n = H0 ≥ H1 ≥ H2 ≥ ⋯ ≥ Hm+1 ≥ ⋯ ≥ H∞
§5. 2 定长编码及定长编码定理
上式表明对信源特性了解越多，则所需传输的信息量就越少。 因此我们对Hm感兴趣，若把L个消息符号排成一个序列，不论其 是否有记忆，只要统计出Hm的值，就对压缩序列的冗余有利。我 们可以仅从符号间相互独立的序列中看到这一特点。 从数学的大数定律中可以证明这样一个结论，如果对L个消 息符号可构成无记忆序列，则按每一个序列的出现概率可将所有 序列分成两大类：一类是高概率序列类 高概率序列类；另一类是低概率序列类 低概率序列类。 高概率序列类 低概率序列类 所谓高概率序列是指属于此集合的元素，大体上将以几乎相同的 概率出现。一般称为渐近等概率集合 渐近等概率集合，记AL。而且L越大这种等 渐近等概率集合 等 概率特性越明显。另一类集合中的序列，它的出现概率很低，几 概率特性越明显 C 乎为零。所以我们把这一部分序列集合称为低概率集合 低概率集合，记为 AL 低概率集合
§5. 1 编码问题的一般概念与定义
⒉ 限失真信源编码(Source coding with finite distortion) 此编码方式不能构成可逆编码，即编码后的码字序列 经解码(反变换)处理后，所恢复的消息序列与发端的原消 息序列存在有一定的失真。这种编码适合于连续信源模拟 信号的编码，因为对连续信源的信号无论做何种处理，都 无法避免信息的损失。比如语音信号，即使采用64Kbit/s 以上的速率量化，也会有相当的信息产生丢失，只不过有 时人耳察觉不到而已。实际工程中失真大量存在，而且在 允许失真的限度下进行编码处理对于大多数用户都是可以 接受的。因此对于信息量无限大的连续变量来说，按照熵 编码的原则压缩，信息丢失的程度应该是最小。

则有：
r l 2 N ( H ( S ) 2 )
即可以编码得到的码字总数不超过….?
根据MG的下界可知，此时码字的总数小于典型序列数目， 因此典型序列中有一些序列没有码字与之对应。将有码字 对应的信源序列的概率和记为P(β)，它必须满足：
P( ) r l max( p( j ))
编码器可以用下图表示： 信源 编码器 信道
码表 图5-1 信源编码器示意图 信源编码器的输入是信源符号集S={s1,s2,…sq}，共 有q个信源符号。 码表又称码符号集，记为 X={x1,x2,…xr},码符号集 中的元素称为码元或者码符号。 编码器的作用就是将信源符号集中的符号si变成由 li个码符号组成的一一对应的码符号序列，称为码字。 用ωi表示。对应的li称为码字长度或码长。
将信源符号集中的每一个符号都固定地映射成一个 码字，这个的码称为分组码。
与分组码对应的是非分组码，又称为树码。 2.奇异码与非奇异码
定义
若一个分组码中所有的码字都不相同，则称此码为 非奇异码。否则为奇异码。
例子见教材。
3.唯一可译码与非唯一可译码
定义
任意有限长的码元序列，如果只能唯一地分割成一 个个码字，便称为唯一可译码。
p( j ) 2
N H ( S )
p(G ) N H ( S ) MG [1 ( N , )]2 max( p( j ))
下界
对仅仅对典型序列进行编码，要求码字总数rl满足：
r l MG
根据典型序列的个数的上界和下界，得
r l 2 N ( H ( S ) )
i
q
注：上式考虑的是sjk所有不同的取值。 I(sjk)的方差为：