文件类型：PDF/Adobe Acrobat 文件大小：字节
1
4 Statistical Coding (统计编码)
Most computer files are not allowed to lose information
during the process of compression, in this chapter, we
discuss the reversible compressing methods which are
common to various kinds of sources
Entropy coding(熵编码)
( Statistical coding (统计编码) or
probability matching coding (概率匹配编码))
Entropy coding(熵编码)
( Statistical coding (统计编码) or
probability matching coding (概率匹配编码))
Make use of the probability distribution character of
information or information sequence, look for the
optimal matchingbetween probability and code length.
Make use of the probability distribution character of
information or information sequence, look for the
optimal matchingbetween probability and code length.
2
For audio, image and video etc. signals, it
permits us to get higher data compressing
ratio by a certain restoring distortion.
Entropy compression(熵压缩)
(inreversiblecompressing methods
introduced in chapter 5 and 6)
Entropy compression(熵压缩)
(inreversiblecompressing methods
introduced in chapter 5 and 6)
The final step of various kinds of entropy
compression methods, is often put in
summary to statistical coding techniques.
The final step of various kinds of entropy
compression methods, is often put in
summary to statistical coding techniques.
3
4.1Basic principle (基本原理)
Computer files
Character set, such as text
Binary character set, such as data
(0,1code)
The restored files are not allowed
to have any distortion.
The restored files are not allowed
to have any distortion.
4
For text fileFor text file
Logical Compression (逻辑压缩)Logical Compression (逻辑压缩)
由数据自身特点及设计者技巧来决定的"压缩表示
法",这种技巧在数据库的数据结构设计中特别有效.
Our discussing
content
Our discussing
contentPhysical Compression (物理压缩)Physical Compression (物理压缩)
The statistical coding method which reduce
the internal redundancyof computer files ( 减
少计算机文件内部冗余度的统计编码方法) .
5
Redundancy type of file (文件的冗余度类型)
Redundancy(冗余度),专指对数据解释一无
所知时由数据流中即可观察到的,与具体应
用背景无关.
了解文件的冗余度,意在考
虑有针对性的编码方法.
了解文件的冗余度,意在考
虑有针对性的编码方法.
6
TypeType
Character Distribution (字符分布)Character Distribution (字符分布)
在典型的字符串中,某些符号要比其他符号出现的更频
繁,在一份具体的文件中字符不会以等概率出现,字符
的分布明显地因文件而异,影响到字符的统计特性.
例如ASCII-8码中,例如ASCII-8码中,
256个可能的符号组合中只有95用于表示非
控制符号,可以压缩;
这95个非控制符号,在一个具体文件中也
不是等概率出现的(如英文中,"e"和"空格"最
常见)…
7
Character Repetition (字符重复)Character Repetition (字符重复)
对于字符重复所形成的符号串常常有更紧凑的编码方式,
格式化文件中的空白
报表中的空格串和零串
业务图表中的线图包含成片的空白等…
例如:例如:
8
High-usage Patterns (高使用率模式)High-usage Patterns (高使用率模式)
某些符号序列会以较高的频率反复出现,可用较少的位
数表示,从而得到时间和空间的净节约.
例如在英文中,例如在英文中,
一个句号后面跟两个空格要比大多数其他3
个字符组合更常见,可用较少的位数编码;
许多字母成对出现(如ZE)的概率要比孤
立出现的概率更高,对其联合编码比对两个字
母单独编码更节约;
而不大可能出现的字母对(GC),则可采
用更长的编码位表示…
9
Positional Redundancy(位置冗余)Positional Redundancy(位置冗余)
若某些字符总是在各数据块中可预见的位置上出现,那
么这些字符至少是部分冗余的.
例如:例如:
光栅扫描图像中若含有竖线,那么在每一行的同一
个位置就会有一个标记,就可以更紧凑地编码;
报表文件中的某些字段的记录几乎总是相同的;
这四类冗余度之间有重叠这四类冗余度之间有重叠
10
零件名: HEX NUT 1/4 20
说明: STEEL, STANDARD THREAD
颜色码:
仓库: 45thSTREET
货位: 4R9
存货量: 0020
再进货量:0010
文字长度可变,字母分布不同;
空字段
同样的名字在文件中多次出现;
数值字段, 有限的字符变化;
×
图4.1一份零件报表中的冗余度的类型
11
Mathematical description of coder
(编码器的数字描述)
对实际信源的编码过程:对实际信源的编码过程:
X ={x1, ···, xn}W ={w1, ···, wn}
A ={a1, ···, am}
编码器
图4.2 编码器的描述
12
消息集X:
元素x 叫做信号单元或消息;(Message)
消息集X:
元素x 叫做信号单元或消息;(Message)
输出集W (代码,码组或码书):(Code)
元素w叫做码字;(Codeword)
输出集W (代码,码组或码书):(Code)
元素w叫做码字;(Codeword)
码字的符号集A:
元素a 叫做码元或者符号.(Symbol,Character)
码字的符号集A:
元素a 叫做码元或者符号.(Symbol,Character)
Coding processCoding process
①以符号A 构建代码W;
②建立X~W 对应关系;
13
Example
4-1
Example
4-1
X ={x1, x2,x3}, A ={0, 1}, W ={w1, w2, w3}
假设用A2={00, 01, 10, 11}
构成代码W , W 到A2的映射关系为(完成步骤①):构成代码W , W 到A2的映射关系为(完成步骤①):
R1={ (w1,01), (w2,10), (w3,11)}
建立X 与W 的映射关系为(完成步骤②):建立X 与W 的映射关系为(完成步骤②):
R2={(x1,w1), (x2,w2), (x3,w3)}
若Xi∈(dk,dk+1], 1≤i≤n, 0≤k≤J-1, 为一模拟信号,
该编码器实际就是一个量化器.
若Xi∈(dk,dk+1], 1≤i≤n, 0≤k≤J-1, 为一模拟信号,
该编码器实际就是一个量化器.
14
编码,就是将不同的消息用不同的码字来代替,或称为
从消息集到码字集的一种映射(分组编码或块码的概念).
编码,就是将不同的消息用不同的码字来代替,或称为
从消息集到码字集的一种映射(分组编码或块码的概念).
码长: 组成码字的符号个数;
例4-1中,Li=2, 1≤i≤3,
等长(或定长)编码: 采用相同长度的不同码字去
代表一个消息集合中的不同消息;
M元编码(或M进制):取M个不同字符来组成码字,
最常用的有二元编码(或二进制,采用0,1码).
15
Fundamental analysis of variable length code
(变长码的基本分析)
Variable length coding:Variable length coding:
对一个消息集合中的不同消息,采用不同长度的码字表示.
采用VLC(变长码) 可以提高编码效率,即对相
同的信息量所需的平均编码长度可以短一些.
采用VLC(变长码) 可以提高编码效率,即对相
同的信息量所需的平均编码长度可以短一些.
16
Average code length (平均码长) :Average code length (平均码长) :
1
()
n
jj
j
lPaL
=
=∑
对P(aj)大的aj用短码;
对P(aj)小的aj用长码;
当这些信息符号互不相关时,平均
码长比等长编码的码长短(例3-1).
当这些信息符号互不相关时,平均
码长比等长编码的码长短(例3-1).
17
In 1843,Morse telegraphy code(莫尔斯码电报码)In 1843,Morse telegraphy code(莫尔斯码电报码)
字母莫尔斯码铅字数
E 12000
T-9000
A -8000
I 8000
N- 8000
O---8000
S 8000
H 6400
R - 6200
D- 4400
L - 4000
U -3400
C- - 3000
字母莫尔斯码铅字数
M--3000
F - 2500
W --2000
Y- --2000
G-- 1700
P -- 1700
B- 1600
V -1200
K- -800
Q-- -500
J ---400
X- -400
Z-- 200
表
4.1
Morse
code
18
Formation of Morse code:Formation of Morse code:
首先找到各消息符号的统计特性;
再根据各符号出现的概率分布分
配不同长度的码字.
变长码在编码时要预先知道各种信息符号出
现的概率,解码也远比等长码复杂:
正确识别码字起点不容易;
存在唯一可译性问题;
译码实时性问题;
匀速输入输出匹配的缓存问题.
变长码在编码时要预先知道各种信息符号出
现的概率,解码也远比等长码复杂:
正确识别码字起点不容易;
存在唯一可译性问题;
译码实时性问题;
匀速输入输出匹配的缓存问题.
19
Monosemydecodable code (单义可译码)Monosemydecodable code (单义可译码)
[定义4-1]若W 中任一有限长的码字序列(即有限长的一
串W),可唯一地分割成一个一个码字,称为
单义可译(monosemydecodable) 或唯一可译
(uniquely decodable) 的,W 也叫做单义代码
(monosemycode).
20
Example 4-2Example 4-2Consider the following several kinds of VLC:
信源字母概率码A码B码C码D码E码F
a1
a2
a3
a4
1/2
1/4
1/8
1/8
0
0
1
10
0
1
11
111
0
10
110
111
0
01
011
0111
0
01
011
111
0
10
101
111
①码A不是一一对应;
②码B是一一对应,但构成的序列不能被唯一分割;
01110
(0,1,1,1,0) (0,1,11,0) (0,11,1,0) (0,111,0)
码D是在码B各码字(除了w1)之前加一个码元
"0",成为唯一可译的,但平均码长增加0.5bit.
21
③码C是唯一可译的;
信源字母码C码E
a1
a2
a3
a4
0
10
110
111
0
01
011
111
100111011010
(10, 0, 111, 0, 110, 10)
④码E的译码要求等到收到全部序列,才能从尾开
始进行判决,产生了时间上延时和存储容量的增加.
0111111 111
(a11111) (a2111) ( a311)
22
⑤码F 即使从尾开始判断,也不是唯一可译的;
101111010
(10, 111, 10, 10)(101, 111, 0, 10)
信源字母码F
a1
a2
a3
a4
0
10
101
111
问题: 什么样的码才是唯一可译的 问题: 什么样的码才是唯一可译的
23
Existence of uniquely decodable code
( 唯一可译码的存在)
目前还没有一个明确的判断唯一可译码的准
则, 只有一个判断不是唯一可译码的准则.
目前还没有一个明确的判断唯一可译码的准
则, 只有一个判断不是唯一可译码的准则.
[定理4.1(Kraft不等式)][定理4.1(Kraft不等式)]
长度为L1, L2, Ln的m 进制唯一可译码存在的充
分必要条件是:
1
1
≤∑=
n
i
Li
m(4.1-1)
含义:要求Li 比较大(码长不能过短),意味着
码字可能的组合数多,不为别的码字的字首.
含义:要求Li 比较大(码长不能过短),意味着
码字可能的组合数多,不为别的码字的字首.
24
Kraft不等式:只涉及唯一可译码的存在问题
而并不涉及具体的码.可用来判定某一组码
不是唯一可译的,但不能判定是唯一可译的.
Kraft不等式:只涉及唯一可译码的存在问题
而并不涉及具体的码.可用来判定某一组码
不是唯一可译的,但不能判定是唯一可译的.
不满足Kraft不等式的码肯定不是唯一可译
码,而满足的也不一定就是唯一可译的,
但可以肯定若按这样的Li 分配码组,则必存在有一
个唯一可译码(也可能不止一个)对应于信源符号.
25
Example 4-3Example 4-3For example 4-2, there are :
码A码B码C码D码E码F
的值
7/411/4115/1611
是否满足Kraft不
等式√√√√
是否唯一可译√√√
∑=
4
12i
Li
×
×
×
××
A,B不满足Kraft不等式,肯定不是唯一可译码;
C,D,E,F虽然满足Kraft不等式,不一定就都是唯
一可译,其中C,D,E是唯一可译,F不是唯一可译.
26
问题: 如何来确定码字长度
如何在确定了码字长度后找出唯一可译码
问题: 如何来确定码字长度
如何在确定了码字长度后找出唯一可译码
由kraft不等式可知,唯一可译码的要求只与码的结
构(n,m,li,i=1,2, …,n)有关,与信源的统计特性无关.
如果希望编出较高效率的唯一可译码,不仅从结构
上要求n,m,li满足Kraft不等式,而且要考虑到信源
的统计特性,合理而充分地利用信源的统计特性.
27
从通信的有效性考虑,当然希望平均码长越小越
好,但平均码长能够小到什么程度 有没有界限
信息论中的变长码定理就回答了这个问题.
[定理4.2((按符号)变长编码定理)][定理4.2((按符号)变长编码定理)]
对于符号熵为H(X)的离散无记忆信源进行m 进制不
等长编码, 一定存在一种无失真编码方法, 其码字平
均长度l 满足:
mX
H
l
mX
H
log
)
(
1
log
)
(
≥
>
+
小于上限的单义代码总是存在的.小于上限的单义代码总是存在的.
28
当m=2,有(二进制编码定理):当m=2,有(二进制编码定理):
(bit) )(1)(XHlXH≥>+(4.1-3)
此时l 叫编码速率, 有时又叫比特率.
对于m进制的不等长编码的编码速率定义为:对于m进制的不等长编码的编码速率定义为:
mlRlog =(4.1-4)
定理4.2改述为:定理4.2改述为:
若H(X)<R< H(X)+ε, 就存在唯一可译的变长码;
若R 1.75
L1
= 1,
L2
= 2,
L3
=
L
码长的一种设计为:满足上述码长设计的码如:例
4.2
中的码
C
足
Kraft
不等式).
如何做出具体的变长码是变长码的构造问题.如何做出具体的变长码是变长码的构造问题.
31
Construction of uniquely decodable code
(唯一可译码的构造)
唯一可译码的基本要求:
对码字序列能做出唯一正确的分割.对码字序列能做出唯一正确的分割.
充分条件充分条件
码字非续长码字非续长
32
[定义4-2][定义4-2]码字非续长
若W 中任一码字都不是另一个码字的字头,或
换句话说,任一码字都不是由另一个码字加上
若干个码元所构成,则W 就叫作非续长码字,
异字头码或前缀码(Prefix Condition Code).
33
In example 4-2:
信源字母概率码A码B码C码D码E码F
a1
a2
a3
a4
1/2
1/4
1/8
1/8
0
0
1
10
0
1
11
111
0
10
110
111
0
01
011
0111
0
01
011
111
0
10
101
111
码A,码B,码D,码E和码F都含有续长码,或同字头码;
码C是异字头码.
34
异字头条件保证译出的码字是唯一的
且具有"即时性",减少了译码延时.
异字头条件保证译出的码字是唯一的
且具有"即时性",减少了译码延时.
不过非异字头码也并非一定不是唯一可译,
码D和码E就唯一可译;
码D:各码组靠"逗号"(码元0)分开;
码E:为码C的"镜像",具有"异后尾",从
后向前即具有唯一可译性.
35
异字头性质只是码字可分离的充分条件,非
续长码也只是单义可译代码集合的一个子集.
异字头性质只是码字可分离的充分条件,非
续长码也只是单义可译代码集合的一个子集.
单义可译码
非续长码
图4.3单义可译码与非续长码
36
二进制编码中二进制编码中
通常可用二进码树(二叉树)来表示各码字的构成
A(根)
B(节点)1
1
1111
0
00
0000
1
图4.4 二进码树
C(节点)
D(节点)
串接的最大枝数为树的节数,图4.4的节数为3.
37
用码树表述任何一个代码W, 异字头条件就成为:
W中所有的码字wi均只对应地配置在终端节点上.W中所有的码字wi均只对应地配置在终端节点上.
根
0
0
1
1
1
0
0
10
110
111
根
01
1
1
0
(0)
(011)
(111)
1
1
(01)0
图4.5 码C的树结构
(异字头码)
码E的树结构(非异字头码)
38
异字头码是可以即时解码的,即时解码在应用上
比较简单,码E的解码要求接收到所有的码元后
才能开始进行解码(不是即时码),这样就产生
了时间上的延迟和存储容量的增加.
39
此时码C为用尽的异字头码, 有:
1
1
=∑=
n
i
Li
m
倘若有一码字为(0,10,110), 则该码为非用尽的
异字头码, 有:
1
1
<∑=
n
i
Li
m
40
按照Kraft 不等式的要求,对n个消息{x1, x2, ,xn}
分配了编码长度L1,L2, ,Ln, 即可用二进码树来生
成异字头码, 生成规律是:
按照Kraft 不等式的要求,对n个消息{x1, x2, ,xn}
分配了编码长度L1,L2, ,Ln, 即可用二进码树来生
成异字头码, 生成规律是:
①从根出发开始生出2枝;
②每一枝用一个码元aj∈A={0,1}来表示;
③枝尽节来,节外生枝;
④在第Li级端节点(Li级节点共有2Li个)上,配置信
号单元xi , i=1,2, , n ;
⑤从根开始直奔对应的端节点,沿途(联枝)所遇到
的码元aj所构成的符号,即为对应于该信号单元
xi 的码字wi.
异字头码无译码延时,构造简单.异字头码无译码延时,构造简单.
41
从信息论中证明Kraft不等式(单义可译定理)的充分性和必
要性过程中,长度为l1,l2, ,ln的M进制异字头码存在的
充要条件,也使Kraft不等式成立:
任何一个结构为(n,m,li, i=1,2, …,n) 单义可译码
一定满足Kraft不等式;
而满足Kraft不等式的(n,m,li, i=1,2, …,n)又至少
可以构成一种结构为(n,m,li, i=1,2, …,n)的非续长码.
42
所以我们得到一个重要的结论:任一单义可
译码可用一个结构相同的异字头码来代替,
因此我们只要考虑非续长码的构造即可.
所以我们得到一个重要的结论:任一单义可
译码可用一个结构相同的异字头码来代替,
因此我们只要考虑非续长码的构造即可.
异字头码虽然只是唯一可译码的一种,但它具有
代表性和普遍意义,在信息保持编码中广泛应用.
43
Shannon-Fanocode
Claude Shannon (Bell Laboratory)和
R. M. Fano(MIT) 几乎同时提出了最早
的对符号进行有效编码从而实现数据压
缩的Shannon-Fano编码方法.
Claude Shannon (Bell Laboratory)和
R. M. Fano(MIT) 几乎同时提出了最早
的对符号进行有效编码从而实现数据压
缩的Shannon-Fano编码方法.
44
For the source in example 4-2:
信源字母
概率
a1
a2
a3
a4
1/2=0.5
1/4=0.25
1/8=0.125
1/8=0.125
Shannon-Fano编码的核心是构造
二进码树,构造的方式非常简单.
45
Shannon-Fanocode steps:Shannon-Fanocode steps:
1)将给定符号按照其概率从大到小排序1)将给定符号按照其概率从大到小排序
a1 0.5
a2 0.25
a3 0.125
a4 0.125
2)将序列分成上下两部分,使得上部概率
总和尽可能接近下部概率总和,有:
2)将序列分成上下两部分,使得上部概率
总和尽可能接近下部概率总和,有:
a1 0.5
----------------
a2 0.25
a3 0.125
a4 0.125
46
3) 把第2步中划分出的上部作为二进码树的左子
树,记0,下部作为二进码树的右子树,记1.
3) 把第2步中划分出的上部作为二进码树的左子
树,记0,下部作为二进码树的右子树,记1.
a1 0.5 0
----------------
a2 0.25 1
a3 0.125
a4 0.125
4)分别对左右子树重复2 ,3两步,直到所有的符号都
成为二进码树的终端节点为止.现在如下的二进码树:
4)分别对左右子树重复2 ,3两步,直到所有的符号都
成为二进码树的终端节点为止.现在如下的二进码树:
a1 0.5 0
----------------
a2 0.25 10
---------------
a3 0.12510
---------------
a4 0.1251
47
于是得到了此信息的编码表:于是得到了此信息的编码表:
根
0
0
1
1
1
0
a1
a2
a3
a4
a1=0 a2= 10 a3= 110 a4= 111
得到的码表就是码C
48
Thanks !
·上一篇：信息论与编码课程教学大纲4 Statistical Coding (统计编码)
Most computer files are not allowed to lose information
during the process of compression, in this chapter, we
discuss the reversible compressing methods which are
common to various kinds of sources
Entropy coding(熵编码)
( Statistical coding (统计编码) or
probability matching coding (概率匹配编码))
Entropy coding(熵编码)
( Statistical coding (统计编码) or
probability matching coding (概率匹配编码))
Make use of the probability distribution character of
information or information sequence, look for the
optimal matchingbetween probability and code length.
Make use of the probability distribution character of
information or information sequence, look for the
optimal matchingbetween probability and code length.
2
For audio, image and video etc. signals, it
permits us to get higher data compressing
ratio by a certain restoring distortion.
Entropy compression(熵压缩)
(inreversiblecompressing methods
introduced in chapter 5 and 6)
Entropy compression(熵压缩)
(inreversiblecompressing methods
introduced in chapter 5 and 6)
The final step of various kinds of entropy
compression methods, is often put in
summary to statistical coding techniques.
The final step of various kinds of entropy
compression methods, is often put in
summary to statistical coding techniques.
3
4.1Basic principle (基本原理)
Computer files
Character set, such as text
Binary character set, such as data
(0,1code)
The restored files are not allowed
to have any distortion.
The restored files are not allowed
to have any distortion.
4
For text fileFor text file
Logical Compression (逻辑压缩)Logical Compression (逻辑压缩)
由数据自身特点及设计者技巧来决定的"压缩表示
法",这种技巧在数据库的数据结构设计中特别有效.
Our discussing
content
Our discussing
contentPhysical Compression (物理压缩)Physical Compression (物理压缩)
The statistical coding method which reduce
the internal redundancyof computer files ( 减
少计算机文件内部冗余度的统计编码方法) .
5
Redundancy type of file (文件的冗余度类型)
Redundancy(冗余度),专指对数据解释一无
所知时由数据流中即可观察到的,与具体应
用背景无关.
了解文件的冗余度,意在考
虑有针对性的编码方法.
了解文件的冗余度,意在考
虑有针对性的编码方法.
6
TypeType
Character Distribution (字符分布)Character Distribution (字符分布)
在典型的字符串中,某些符号要比其他符号出现的更频
繁,在一份具体的文件中字符不会以等概率出现,字符
的分布明显地因文件而异,影响到字符的统计特性.
例如ASCII-8码中,例如ASCII-8码中,
256个可能的符号组合中只有95用于表示非
控制符号,可以压缩;
这95个非控制符号,在一个具体文件中也
不是等概率出现的(如英文中,"e"和"空格"最
常见)…
7
Character Repetition (字符重复)Character Repetition (字符重复)
对于字符重复所形成的符号串常常有更紧凑的编码方式,
格式化文件中的空白
报表中的空格串和零串
业务图表中的线图包含成片的空白等…
例如:例如:
8
High-usage Patterns (高使用率模式)High-usage Patterns (高使用率模式)
某些符号序列会以较高的频率反复出现,可用较少的位
数表示,从而得到时间和空间的净节约.
例如在英文中,例如在英文中,
一个句号后面跟两个空格要比大多数其他3
个字符组合更常见,可用较少的位数编码;
许多字母成对出现(如ZE)的概率要比孤
立出现的概率更高,对其联合编码比对两个字
母单独编码更节约;
而不大可能出现的字母对(GC),则可采
用更长的编码位表示…
9
Positional Redundancy(位置冗余)Positional Redundancy(位置冗余)
若某些字符总是在各数据块中可预见的位置上出现,那
么这些字符至少是部分冗余的.
例如:例如:
光栅扫描图像中若含有竖线,那么在每一行的同一
个位置就会有一个标记,就可以更紧凑地编码;
报表文件中的某些字段的记录几乎总是相同的;
这四类冗余度之间有重叠这四类冗余度之间有重叠
10
零件名: HEX NUT 1/4 20
说明: STEEL, STANDARD THREAD
颜色码:
仓库: 45thSTREET
货位: 4R9
存货量: 0020
再进货量:0010
文字长度可变,字母分布不同;
空字段
同样的名字在文件中多次出现;
数值字段, 有限的字符变化;
×
图4.1一份零件报表中的冗余度的类型
11
Mathematical description of coder
(编码器的数字描述)
对实际信源的编码过程:对实际信源的编码过程:
X ={x1, ···, xn}W ={w1, ···, wn}
A ={a1, ···, am}
编码器
图4.2 编码器的描述
12
消息集X:
元素x 叫做信号单元或消息;(Message)
消息集X:
元素x 叫做信号单元或消息;(Message)
输出集W (代码,码组或码书):(Code)
元素w叫做码字;(Codeword)
输出集W (代码,码组或码书):(Code)
元素w叫做码字;(Codeword)
码字的符号集A:
元素a 叫做码元或者符号.(Symbol,Character)
码字的符号集A:
元素a 叫做码元或者符号.(Symbol,Character)
Coding processCoding process
①以符号A 构建代码W;
②建立X~W 对应关系;
13
Example
4-1
Example
4-1
X ={x1, x2,x3}, A ={0, 1}, W ={w1, w2, w3}
假设用A2={00, 01, 10, 11}
构成代码W , W 到A2的映射关系为(完成步骤①):构成代码W , W 到A2的映射关系为(完成步骤①):
R1={ (w1,01), (w2,10), (w3,11)}
建立X 与W 的映射关系为(完成步骤②):建立X 与W 的映射关系为(完成步骤②):
R2={(x1,w1), (x2,w2), (x3,w3)}
若Xi∈(dk,dk+1], 1≤i≤n, 0≤k≤J-1, 为一模拟信号,
该编码器实际就是一个量化器.
若Xi∈(dk,dk+1], 1≤i≤n, 0≤k≤J-1, 为一模拟信号,
该编码器实际就是一个量化器.
14
编码,就是将不同的消息用不同的码字来代替,或称为
从消息集到码字集的一种映射(分组编码或块码的概念).
编码,就是将不同的消息用不同的码字来代替,或称为
从消息集到码字集的一种映射(分组编码或块码的概念).
码长: 组成码字的符号个数;
例4-1中,Li=2, 1≤i≤3,
等长(或定长)编码: 采用相同长度的不同码字去
代表一个消息集合中的不同消息;
M元编码(或M进制):取M个不同字符来组成码字,
最常用的有二元编码(或二进制,采用0,1码).
15
Fundamental analysis of variable length code
(变长码的基本分析)
Variable length coding:Variable length coding:
对一个消息集合中的不同消息,采用不同长度的码字表示.
采用VLC(变长码) 可以提高编码效率,即对相
同的信息量所需的平均编码长度可以短一些.
采用VLC(变长码) 可以提高编码效率,即对相
同的信息量所需的平均编码长度可以短一些.
16
Average code length (平均码长) :Average code length (平均码长) :
1
()
n
jj
j
lPaL
=
=∑
对P(aj)大的aj用短码;
对P(aj)小的aj用长码;
当这些信息符号互不相关时,平均
码长比等长编码的码长短(例3-1).
当这些信息符号互不相关时,平均
码长比等长编码的码长短(例3-1).
17
In 1843,Morse telegraphy code(莫尔斯码电报码)In 1843,Morse telegraphy code(莫尔斯码电报码)
字母莫尔斯码铅字数
E 12000
T-9000
A -8000
I 8000
N- 8000
O---8000
S 8000
H 6400
R - 6200
D- 4400
L - 4000
U -3400
C- - 3000
字母莫尔斯码铅字数
M--3000
F - 2500
W --2000
Y- --2000
G-- 1700
P -- 1700
B- 1600
V -1200
K- -800
Q-- -500
J ---400
X- -400
Z-- 200
表
4.1
Morse
code
18
Formation of Morse code:Formation of Morse code:
首先找到各消息符号的统计特性;
再根据各符号出现的概率分布分
配不同长度的码字.
变长码在编码时要预先知道各种信息符号出
现的概率,解码也远比等长码复杂:
正确识别码字起点不容易;
存在唯一可译性问题;
译码实时性问题;
匀速输入输出匹配的缓存问题.
变长码在编码时要预先知道各种信息符号出
现的概率,解码也远比等长码复杂:
正确识别码字起点不容易;
存在唯一可译性问题;
译码实时性问题;
匀速输入输出匹配的缓存问题.
19
Monosemydecodable code (单义可译码)Monosemydecodable code (单义可译码)
[定义4-1]若W 中任一有限长的码字序列(即有限长的一
串W),可唯一地分割成一个一个码字,称为
单义可译(monosemydecodable) 或唯一可译
(uniquely decodable) 的,W 也叫做单义代码
(monosemycode).
20
Example 4-2Example 4-2Consider the following several kinds of VLC:
信源字母概率码A码B码C码D码E码F
a1
a2
a3
a4
1/2
1/4
1/8
1/8
0
0
1
10
0
1
11
111
0
10
110
111
0
01
011
0111
0
01
011
111
0
10
101
111
①码A不是一一对应;
②码B是一一对应,但构成的序列不能被唯一分割;
01110
(0,1,1,1,0) (0,1,11,0) (0,11,1,0) (0,111,0)
码D是在码B各码字(除了w1)之前加一个码元
"0",成为唯一可译的,但平均码长增加0.5bit.
21
③码C是唯一可译的;
信源字母码C码E
a1
a2
a3
a4
0
10
110
111
0
01
011
111
100111011010
(10, 0, 111, 0, 110, 10)
④码E的译码要求等到收到全部序列,才能从尾开
始进行判决,产生了时间上延时和存储容量的增加.
0111111 111
(a11111) (a2111) ( a311)
22
⑤码F 即使从尾开始判断,也不是唯一可译的;
101111010
(10, 111, 10, 10)(101, 111, 0, 10)
信源字母码F
a1
a2
a3
a4
0
10
101
111
问题: 什么样的码才是唯一可译的 问题: 什么样的码才是唯一可译的
23
Existence of uniquely decodable code
( 唯一可译码的存在)
目前还没有一个明确的判断唯一可译码的准
则, 只有一个判断不是唯一可译码的准则.
目前还没有一个明确的判断唯一可译码的准
则, 只有一个判断不是唯一可译码的准则.
[定理4.1(Kraft不等式)][定理4.1(Kraft不等式)]
长度为L1, L2, Ln的m 进制唯一可译码存在的充
分必要条件是:
1
1
≤∑=
n
i
Li
m(4.1-1)
含义:要求Li 比较大(码长不能过短),意味着
码字可能的组合数多,不为别的码字的字首.
含义:要求Li 比较大(码长不能过短),意味着
码字可能的组合数多,不为别的码字的字首.
24
Kraft不等式:只涉及唯一可译码的存在问题
而并不涉及具体的码.可用来判定某一组码
不是唯一可译的,但不能判定是唯一可译的.
Kraft不等式:只涉及唯一可译码的存在问题
而并不涉及具体的码.可用来判定某一组码
不是唯一可译的,但不能判定是唯一可译的.
不满足Kraft不等式的码肯定不是唯一可译
码,而满足的也不一定就是唯一可译的,
但可以肯定若按这样的Li 分配码组,则必存在有一
个唯一可译码(也可能不止一个)对应于信源符号.
25
Example 4-3Example 4-3For example 4-2, there are :
码A码B码C码D码E码F
的值
7/411/4115/1611
是否满足Kraft不
等式√√√√
是否唯一可译√√√
∑=
4
12i
Li
×
×
×
××
A,B不满足Kraft不等式,肯定不是唯一可译码;
C,D,E,F虽然满足Kraft不等式,不一定就都是唯
一可译,其中C,D,E是唯一可译,F不是唯一可译.
26
问题: 如何来确定码字长度
如何在确定了码字长度后找出唯一可译码
问题: 如何来确定码字长度
如何在确定了码字长度后找出唯一可译码
由kraft不等式可知,唯一可译码的要求只与码的结
构(n,m,li,i=1,2, …,n)有关,与信源的统计特性无关.
如果希望编出较高效率的唯一可译码,不仅从结构
上要求n,m,li满足Kraft不等式,而且要考虑到信源
的统计特性,合理而充分地利用信源的统计特性.
27
从通信的有效性考虑,当然希望平均码长越小越
好,但平均码长能够小到什么程度 有没有界限
信息论中的变长码定理就回答了这个问题.
[定理4.2((按符号)变长编码定理)][定理4.2((按符号)变长编码定理)]
对于符号熵为H(X)的离散无记忆信源进行m 进制不
等长编码, 一定存在一种无失真编码方法, 其码字平
均长度l 满足:
mX
H
l
mX
H
log
)
(
1
log
)
(
≥
>
+
小于上限的单义代码总是存在的.小于上限的单义代码总是存在的.
28
当m=2,有(二进制编码定理):当m=2,有(二进制编码定理):
(bit) )(1)(XHlXH≥>+(4.1-3)
此时l 叫编码速率, 有时又叫比特率.
对于m进制的不等长编码的编码速率定义为:对于m进制的不等长编码的编码速率定义为:
mlRlog =(4.1-4)
定理4.2改述为:定理4.2改述为:
若H(X)<R< H(X)+ε, 就存在唯一可译的变长码;
若R 1.75
L1
= 1,
L2
= 2,
L3
=
L
码长的一种设计为:满足上述码长设计的码如:例
4.2
中的码
C
足
Kraft
不等式).
如何做出具体的变长码是变长码的构造问题.如何做出具体的变长码是变长码的构造问题.
31
Construction of uniquely decodable code
(唯一可译码的构造)
唯一可译码的基本要求:
对码字序列能做出唯一正确的分割.对码字序列能做出唯一正确的分割.
充分条件充分条件
码字非续长码字非续长
32
[定义4-2][定义4-2]码字非续长
若W 中任一码字都不是另一个码字的字头,或
换句话说,任一码字都不是由另一个码字加上
若干个码元所构成,则W 就叫作非续长码字,
异字头码或前缀码(Prefix Condition Code).
33
In example 4-2:
信源字母概率码A码B码C码D码E码F
a1
a2
a3
a4
1/2
1/4
1/8
1/8
0
0
1
10
0
1
11
111
0
10
110
111
0
01
011
0111
0
01
011
111
0
10
101
111
码A,码B,码D,码E和码F都含有续长码,或同字头码;
码C是异字头码.
34
异字头条件保证译出的码字是唯一的
且具有"即时性",减少了译码延时.
异字头条件保证译出的码字是唯一的
且具有"即时性",减少了译码延时.
不过非异字头码也并非一定不是唯一可译,
码D和码E就唯一可译;
码D:各码组靠"逗号"(码元0)分开;
码E:为码C的"镜像",具有"异后尾",从
后向前即具有唯一可译性.
35
异字头性质只是码字可分离的充分条件,非
续长码也只是单义可译代码集合的一个子集.
异字头性质只是码字可分离的充分条件,非
续长码也只是单义可译代码集合的一个子集.
单义可译码
非续长码
图4.3单义可译码与非续长码
36
二进制编码中二进制编码中
通常可用二进码树(二叉树)来表示各码字的构成
A(根)
B(节点)1
1
1111
0
00
0000
1
图4.4 二进码树
C(节点)
D(节点)
串接的最大枝数为树的节数,图4.4的节数为3.
37
用码树表述任何一个代码W, 异字头条件就成为:
W中所有的码字wi均只对应地配置在终端节点上.W中所有的码字wi均只对应地配置在终端节点上.
根
0
0
1
1
1
0
0
10
110
111
根
01
1
1
0
(0)
(011)
(111)
1
1
(01)0
图4.5 码C的树结构
(异字头码)
码E的树结构(非异字头码)
38
异字头码是可以即时解码的,即时解码在应用上
比较简单,码E的解码要求接收到所有的码元后
才能开始进行解码(不是即时码),这样就产生
了时间上的延迟和存储容量的增加.
39
此时码C为用尽的异字头码, 有:
1
1
=∑=
n
i
Li
m
倘若有一码字为(0,10,110), 则该码为非用尽的
异字头码, 有:
1
1
<∑=
n
i
Li
m
40
按照Kraft 不等式的要求,对n个消息{x1, x2, ,xn}
分配了编码长度L1,L2, ,Ln, 即可用二进码树来生
成异字头码, 生成规律是:
按照Kraft 不等式的要求,对n个消息{x1, x2, ,xn}
分配了编码长度L1,L2, ,Ln, 即可用二进码树来生
成异字头码, 生成规律是:
①从根出发开始生出2枝;
②每一枝用一个码元aj∈A={0,1}来表示;
③枝尽节来,节外生枝;
④在第Li级端节点(Li级节点共有2Li个)上,配置信
号单元xi , i=1,2, , n ;
⑤从根开始直奔对应的端节点,沿途(联枝)所遇到
的码元aj所构成的符号,即为对应于该信号单元
xi 的码字wi.
异字头码无译码延时,构造简单.异字头码无译码延时,构造简单.
41
从信息论中证明Kraft不等式(单义可译定理)的充分性和必
要性过程中,长度为l1,l2, ,ln的M进制异字头码存在的
充要条件,也使Kraft不等式成立:
任何一个结构为(n,m,li, i=1,2, …,n) 单义可译码
一定满足Kraft不等式;
而满足Kraft不等式的(n,m,li, i=1,2, …,n)又至少
可以构成一种结构为(n,m,li, i=1,2, …,n)的非续长码.
42
所以我们得到一个重要的结论:任一单义可
译码可用一个结构相同的异字头码来代替,
因此我们只要考虑非续长码的构造即可.
所以我们得到一个重要的结论:任一单义可
译码可用一个结构相同的异字头码来代替,
因此我们只要考虑非续长码的构造即可.
异字头码虽然只是唯一可译码的一种,但它具有
代表性和普遍意义,在信息保持编码中广泛应用.
43
Shannon-Fanocode
Claude Shannon (Bell Laboratory)和
R. M. Fano(MIT) 几乎同时提出了最早
的对符号进行有效编码从而实现数据压
缩的Shannon-Fano编码方法.
Claude Shannon (Bell Laboratory)和
R. M. Fano(MIT) 几乎同时提出了最早
的对符号进行有效编码从而实现数据压
缩的Shannon-Fano编码方法.
44
For the source in example 4-2:
信源字母
概率
a1
a2
a3
a4
1/2=0.5
1/4=0.25
1/8=0.125
1/8=0.125
Shannon-Fano编码的核心是构造
二进码树,构造的方式非常简单.
45
Shannon-Fanocode steps:Shannon-Fanocode steps:
1)将给定符号按照其概率从大到小排序1)将给定符号按照其概率从大到小排序
a1 0.5
a2 0.25
a3 0.125
a4 0.125
2)将序列分成上下两部分,使得上部概率
总和尽可能接近下部概率总和,有:
2)将序列分成上下两部分,使得上部概率
总和尽可能接近下部概率总和,有:
a1 0.5
----------------
a2 0.25
a3 0.125
a4 0.125
46
3) 把第2步中划分出的上部作为二进码树的左子
树,记0,下部作为二进码树的右子树,记1.
3) 把第2步中划分出的上部作为二进码树的左子
树,记0,下部作为二进码树的右子树,记1.
a1 0.5 0
----------------
a2 0.25 1
a3 0.125
a4 0.125
4)分别对左右子树重复2 ,3两步,直到所有的符号都
成为二进码树的终端节点为止.现在如下的二进码树:
4)分别对左右子树重复2 ,3两步,直到所有的符号都
成为二进码树的终端节点为止.现在如下的二进码树:
a1 0.5 0
----------------
a2 0.25 10
---------------
a3 0.12510
---------------
a4 0.1251
47
于是得到了此信息的编码表:于是得到了此信息的编码表:
根
0
0
1
1
1
0
a1
a2
a3
a4
a1=0 a2= 10 a3= 110 a4= 111
得到的码表就是码C
48
Thanks !
·下一篇：上讲要点