(信息论)第5章无失真信源编码_图文

第 5 章 无失真信源编码

5.1 编码器

无失真信源编码：能够精确地复现信源的输出，保证 信源产生的全部信息无损地送给信宿，这时的信源编码就 是无失真信源编码。

输入

S ? ?s1 , s2 ,?, sq ?

编码器

输出

码字

代码组C或码C

信源符号集

X ? ?x1 , x2 ,?, xr ?

码元(码符号)

码符号集

无失真信源编码器数学模型图

1

码字

Wi ? xi1 xi2 ? xil

i

i ? 1, 2, ?, q

其中，长度 l i 称为码字长度，简称码长。

以上表述的无失真信源编码就是从信源符号到 输出码符号的一种映射。这种映射必须是一一对应 的、可逆的。

码的分类

定长码(固定长度码)

变长码(可变长度码)

2

? 奇异码：若码中所字都不相同，则称此码为非

奇异码。反之，称为奇异码。

? 同价码：每个码符号所占的传输时间都相同的码。定

长码中每个码字的传输时间相同。而变长码中的每个码 字的传输时间不一定相等。

表 5.1

信源符号si

信源符号出现概率 ?si ? p

s1 s2 s3 s4

码1

码2

00 01 10 11

0 01 001 111

3

表 5.2

信源符号si

信源符号出现概率 ?si ? p

s1 s2 s3 s4

二次扩展信源符号

码1

码2

0 11 00 11

码字

0 10 00 10

表 5.3 表5.1中的码2的2次扩展

? j , j ? 1,2, ? ,16 ? 1 ? s1 s1 ? 2 ? s1 s 2 ? 3 ? s1 s 3

W j , j ? 1,2, ? ,16 00 001 0001 ? 111111

4

? 16 ? s 4 s 4

5.2 分组码

定义 5.2.1 将信源符号集中的每个信源符号 si 映 射成一个固定的码字 Wi ，这样的码称为分组码。

分组码的性质

1、奇异性 定义 5.2.2 若一种分组码的所字都互不相同， 则称此分组码为非奇异码，否则称为奇异码。 分组码是非奇异的应是正确译码的必要条件，这是 由于非奇异码的分组码并不能保证能正确地译出，因为 当码字排在一起时还可能出现奇异性。

5

2、唯一可译性

定义 5.2.3 设信源符号 si , i ? 1,2,?, q 映射为一个固 定的码字 Wi , i ? 1, 2, ?, q 。则码 ? j ? ?s j , s j ,?, s j ? 映射 为 W j ? ?W j ,W j ,?,W j 展。

1 2 N

? 的分组码称为原分组码的N次扩

1 2 N

定义 5.2.4 一个分组码若对于任意有限的整数N, 其N阶扩展码均为非奇异的，则称之为唯一可译码。 唯一可译码的物理意义：它要求该分组码不同的码 字表示不同的信源符号，而且进一步要求对由信源符号 构成的信息序列进行编码时，在接收端仍能正确译码。

6

2、即时码

定义 5.2.5 无需考虑后续的码符号即可从码符号序 列中译出码字，这样的唯一可译码称为即时码(瞬时码、 逗点码、非延长码)。 唯一可译码成为即时码的条件

定义 5.2.6 设 Wi ? Wi Wi ?Wi 为一个码字，对于 任意的 1 ? j ? l ，称码符号序列的前 j 个元素 Wi Wi ?Wi

1 2 l

1

2

j

为码字 Wi 的前缀。

命题 5.2.1 一个唯一可译码成为即时码的充要条件 是其中任何一个码字都不是其他码字的前缀。

7

即时码或称瞬时码，有时又称非延长码，它是唯一

可译码的一类子码。故即时码一定是唯一可译码，反之， 唯一可译码不一定是即时码。因为有些非即时码(延长码)

具有唯一可译性，但不满足前缀条件，不能即时译码。

二元即时码树图构造法

A

0 0 0

000

1 1 0 10 10 1 1

三阶节点 111 一阶节点

二阶节点

1

0

001 010 011100 101110

8

A 0

一阶节点

2 1 0 1 2

整树

二阶节点

0

1 2

0 1 0 1 A 1

2 01 2

三阶节点

B 0

C

D 0

0 1

1

01

1

1

E

001

0001 ? W4

非整树

9

5.3 定长码

简单信源存在唯一可译定长码的条件

q ? rl

(5.1)

其中, q 是信源 S 的符号个数, r 是信道基本码符号 数, l 是定长码的码长.

表 5.6

信源符号

信源符号概率

s1 s2 s3 s4

码1

码2

00 01 10 11

00 11 10 11

10

N 次扩展信源定长编码存在唯一可译码的条件

q

N

l

(5.2)

N

其中， q 是信源 S ? ?s1 , s 2 ,?, s q ? 的符号个数，q

? j ? ?s j , s j , ?, s j ?, s j ? S , k ? 1, 2, ?, N

1 2 N k

是

信源 S 的 N 次扩展信源 S N ? ?? 1 ,? 2 ,?,? qN ?的码符号个数， 。 r 是基本码符号

集 X ? ?x1 , x2 ,?, xr ? 的个数。l 是码字

W j ? x j1 , x j2 , ?, x jl , x j1 , x j2 , ?, x jl ? X

的长度。

11

S N 中平均每个原始信源符号所需要的码符号数

l log q ? ? log r q N log r

(5.3)

,z} 二进符号 码符号集{0， 1 } 信源编码器ii 码符号集{点/划/字母间隔/单词间隔} 2） 摩尔斯电码 2） 摩尔斯信源编码器 二进代码 10 符号 点 划 字母间隔 单词间隔 &mdash。 信息论与编码基础 香农三大定理 简介 2、 香农第一定理（可变长无失真信源编码定理） rshlognlnrshlogn)(1)(定理4.1 设 信源， 若对 n},...,,{21nqns为q元离散无记忆信源s的n次扩展 xxxx},...,,{21s 进行编码， 码符号集 r， 则总可以找 到一种编码方法构成惟一可译码， 使信源s中每个符号所需的平均 编码长度满足： 且当 n时有： )(log)(limnshrshnlrn信息论与编码基础 香农三大定理 简介 表述二： 若r>h(s)， 就存在惟一可译变长编码。香农第一定理的意义：将原始信源符号转化为新的码符号，使码符号尽量服从等概分布，从而每个码符号所携带的信息量达到最大，进而可以用尽量少的码符号传输信源信息。

l ? log r q ? log q ? log 32 ? 5

这就是说，每个英文电报符号至少要用5位二元符号进行 编码才能得到唯一可译码。 12

定长编码定理

定长信源编码定理讨论了编码的有关参数对译 码差错的限制关系

定理 5.3.1 设离散无记忆信源

的熵为H ?S ? ，其 N 次扩展信源为

N N

现在用码符号集 X ? ?x1 , x2 ,?, xr ? 对N次扩展信源 S N 进行长度为 l 的定长编码，对于 ?? ? 0, ? ? 0 ，只要满足

(5.6)

。

则当N足够大时，必可使译码差错小于 ? 反之，若

(5.7)

13

则当N足够大时，译码错误概率趋于1。

定理 5.3.2 设有离散无记忆信源，其熵为 H ?S ? ， 若对信源的长为N的符号序列进行定长编码，设码字是 从 r 个码符号集中选取 l 个码元构成，对于任意 ? ? 0无失真信源编码定理， 只要满足

则当 N 足够大时，译码错误概率为任意小，几乎可以实 现无失真编码。 反之，若满足

则不可能实现无失真编码。而当N足够大时，译码错误概 14 率近似等于1。

以上的定理5.3.1 和定理5.3.2实际上说明的是一个 问题，虽然该定理是在平稳无记忆离散信源的条件下 证明的，但它也同样适合于平稳有记忆信源，只要要 2 求有记忆信源的极限熵 H ? ?S ? 和极限方差 ? ? 存在 即可。对于平稳有记忆信源，式(5.6)和式(5.7 ) 中 H ?S ? 应该为极限熵 H ? ?S ? 。

例：仍以英文电报符号为例，来计算平均每个原 始信源符号至少需要的比特位数，这里极限熵

H ? ? S ? ? 1.4 比特/ 符号

。

二元符号/ 信源符号

15

l ? 1.4 N

将定理5.3.2的条件该写成

l log r ? NH ?S ?

(5.36)

设某信道有r个输入符号,s个输出符号,信道容量为c,当信道的信息传输率r码长n足够长,总可以在输入的集合中(含有r^n个长度为n的码符号 序列),找到m (m<=2^(n(c-a))),a为任意小的正数)个码字,分别代表m个等可能性的消息,组成一个码以及相应的译码规则,使信道输出端的最小平均 错误译码概率pmin达到任意小。 二、 香农第三定理（保真度准则下的信源编码定理） 信息论与编码基础 香农三大定理 简介 信 源 信 宿 限 失 真 信 源 编 码 器 限 失 真 信 源 译 码 器 无 失 真 信 源 编 码 器 无 失 真 信 源 译 码 器 信 道 编 码 信 道 译 码 a b c d 信道 e f g h 一般通信系统框图 信息论与编码基础 香农三大定理 简介 信息论与编码基础 香农三大定理 简介 总结： 香农第二定理（有噪信道编码定理） r &le。 信息论与编码基础 香农三大定理 简介 2、 香农第一定理（可变长无失真信源编码定理） rshlognlnrshlogn)(1)(定理4.1 设 信源， 若对 n},...,,{21nqns为q元离散无记忆信源s的n次扩展 xxxx},...,,{21s 进行编码， 码符号集 r， 则总可以找 到一种编码方法构成惟一可译码， 使信源s中每个符号所需的平均 编码长度满足： 且当 n时有： )(log)(limnshrshnlrn信息论与编码基础 香农三大定理 简介 表述二： 若r>h(s)， 就存在惟一可译变长编码。

l log r R? N

def

bit / 符号

(5.37)

16

为编码速率。

定义 5.3.2 称

(5.38)

为编码效率。

由(5.38)可知，编码效率 ? ? 1 。此外，由定理 5.3.2 得最 佳编码效率为

由式 知，当方差D ? I ?si ? ? 和 均为定值时，只 要 N足够大，错误概率 p E 就可以小于任意一正数 ? 。 如果，当允许错误概率 p E 小于 ? 时，信源序列长度N 必满足

(5.39)

(5.40)

17

由式(5.39)，(5.40)可得

度 N 与最佳编码效率 ? 和允许错误概率

(5.41)

上式给出了在已知方差和信源熵的条件下，信源序列长

pE

的关系。

对输入的英文大写字母序列进行统计概率，然后构建huffman树，输出按照概率降序排序输出huffman编码。哈夫曼编码是一种可变长的编码，它依据字符出现的概率来决定字符编码的长度，使得出现概率大的字符编码长度短，出现概率小的字符的编码长度长，于是可以减少整体的编码的长度。众所周知,在计算机当中,数据的存储和加工都是以字节作为基本单位的,一个西文字符要通过一个字节来表达,而一个汉字就要用两个字节,我们把这种每一个字符都通过相同的字节数来表达的编码形式称为定长编码.以西文为例,例如我们要在计算机当中存储这样的一句话:i am a teacher.就需要15个字节,也就是120个二进制位的数据来实现.与这种定长编码不同的是,哈夫曼编码是一种变长编码.它根据字符出现的概率来构造平均长度最短的编码.换句话说如果一个字符在一段文档当中出现的次数多,它的编码就相应的短,如果一个字符在一段文档当中出现的次数少,它的编码就相应的长.当编码中,各码字的长度严格按照对应符号出现的概率大小进行逆序排列时,则编码的平均长度是最小的.这就是哈夫曼编码实现数据压缩的基本原理.要想得到一段数据的哈夫曼编码,需要用到三个步骤:第一步:扫描需编码的数据,统计原数据中各字符出现的概率.第二步:利用得到的概率值创建哈夫曼树.第三步:对哈夫曼树进行编码,并把编码后得到的码字存储起来.因为定长编码已经用相同的位数这个条件保证了任一个字符的编码都不会成为其它编码的前缀,所以这种情况只会出现在变长编码当中,要想避免这种情况,我们就必须用一个条件来制约定长编码,这个条件就是要想成为压缩编码,变长编码就必须是前缀编码.什么是前缀编码呢。

无失真的定长编码，N 需要的长度将会大到难以实现。

18

例 5.3.2 设离散无记忆信源

其信息熵

1 3 4 H ? S ? ? log 4 ? log ? 0.811 比特 / 信源符号 4 4 3

其自信息的方差

2 2 2 i ?1

2

2

若对信源S 采取等长二元编码时，要求编码效率 ? ? 0.96 ?5 允许错误概率 ? ? 10 。则根据式(5.41)，求得

?0.811?2 0.04 2 ? 10 ?5

0.4715

? 4.13 ? 10 7

即信源序列长度需长 4.13 ? 10 7 以上，才能实现给定的要求， 这在实际中是很难实现的。因此，一般来说，当 N 有限时，

高传输效率的等长码往往要求引入一定的失真和误差，它不

象变长码那样可以实现无失真编码。

20

5.4 变长码

变长码为了实现无失真的信源编码，与定长码一样必 须是非奇异码，并且是任意长 N 次扩展也是非奇异码， 这样才是唯一可译码。为能即时译码必须是即时码。 5.4.1 码的分类和主要编码方法

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/tongxinshuyu/article-111067-1.html