当前位置:文档之家› 信息论与编码复习56

信息论与编码复习56


无失真信源编码
设信源符号序列的长度为L XX1X2 Xl XL
Xl a1,a2, ,ai, ,an
变换成由KL个符号组成的 Y Y1Y2 Yk YKL
码序列(码字)
Yk b1,b2, ,bj, ,bm
变换要求
能够无失真或无差错地从Y 恢复X,也就是
能正确地进行反变换或译码 传送Y 时所需要的信息率最小
法,使平均信息率 K 满足不等式
H L(X )KH L(X )
其中,ε为任意小正数。
香农编码步骤
1. 将信源消息符号按其概率从大到小排列
p x 1 p x 2 p x n
2. 确定满足下列不等式的整数码长Ki
lo g p x i K i lo g p x i 1
3. 令P1=0,计算第i个消息的累加概率
走过的路径上所对应的符号组成 当第i阶的节点作为终端节点,且分配码字,则码字的
码长为i 按树图法构成的码一定满足即时码的定义 树码的各个分支都延伸到最后一级端点,则称为满树,
否则为非满树 满树码是定长码,非满树码是变长码
克劳夫特不等式
唯一可译码存在的充分和必要条件为:各 码字的长度Ki 应满足下式。
较高,对编码设备的要求也比较简单,因此综合性能优 于香农码和费诺码。
限失真信源编码定理
设离散无记忆信源X的信息率失真函数为R(D) 当信息率 R>R(D)时,只要信源序列长度 L 足够长,一定存在一种编码方法,其译码失 真小于或等于 D+ε,ε为任意小的正数。 反之,若R<R(D) ,则无论采用什么样的编 码方法,其译码失真必大于D。
n
m Ki 1
i1
m是进制数,n是信源符号数
注意:克拉夫特不等式只是说明唯一可译码 是否存在,并不能作为唯一可译码的判据。
唯一可译码的判断法
将码C中所有可能的尾随后缀组成一个集合F,当且仅当集 合F中没有包含任一码字,则可判断此码C为唯一可译码。
集合F的构成方法 首先观察码C中最短的码字是否是其它码字的前缀。若 是,将其所有可能的尾随后缀排列出。而这些尾随后缀 又有可能是某些码字的前缀(或者某些码字是这些尾随 后缀的前缀),再将这些尾随后缀产生的新的尾随后缀 列出。依此下去,直到没有一个尾随后缀是码字的前缀 为止。 按照上述步骤将次短码字、…等等所有码字可能产生的 尾随后缀全部列出。最终得到码C的所有可能的尾随后 缀的集合F。
第5章 信源编码
重点掌握
分组码的属性 唯一可译码的判断方法 信源编码定理 香农编码、费诺编码、哈夫曼编码
一般了解
编码的术语 游程编码、算术编码
分组码属性
非分组码

奇异码
分组码
非唯一可译码
非奇异码
非即时码
唯一可译码
即时码(非延长码)
码树
中间节点不安排码字,只在终端节点安排码字 每个终端节点对应的码字由从根节点出发到终端节点
香农码、费诺码、哈夫曼码都考虑了信源的统计特性, 经常出现的信源符号对应较短的码字,使信源的平均码 长缩短,从而实现对信源的压缩。
香农码有系ห้องสมุดไป่ตู้的、惟一的编码方法,但在很多情况下编 码效率不是很高。
费诺码和哈夫曼码的编码方法都不惟一。 费诺码比较适合于对分组概率相等或接近的信源编码。 哈夫曼码对信源的统计特性没有特殊要求,编码效率比
单个符号变长编码定理
若一离散无记忆信源的符号熵为H(X), 每个信源符号用m进制码元进行变长编码, 一定存在一种无失真编码方法,其码字 平均长度满足下列不等式
H(X)KH(X)1
lom g
lom g
变长编码定理
离散平稳无记忆序列变长编码定理
对于平均符号熵为HL(X)的离散平稳无 记忆信源,必存在一种无失真编码方
反之,当 KLLlogmHLX2
时,译码差错一定是有限值,而当L足够大时,译码几乎 必定出错。
编码效率
差错概率
2(X ) Pe L 2
当信源序列长度L满足 L
就能达到差错率要求。
2(X 2
)
时,
编码效率 H L ( X )
K
最佳编码效率为
HL(X) , 0 HL(X)
变长编码定理
2. 取两个概率最小的符号分别配以0和1,并将这两个 概率相加作为一个新符号的概率,与未分配码元的 符号重新排队。
3. 对重排后的两个概率最小符号重复步骤2的过程。 4. 继续上述过程,直到最后两个符号配以0和1为止。 5. 从最后一级开始,向前返回得到各个信源符号所对
应的码元序列,即相应的码字。
三种编码的比较
唯一可译码判断方法和步骤
1. 首先,观察是否是奇异码。若是,一定不 是唯一可译码。
2. 其次,计算码长是否满足Kraft不等式。若 不满足,一定不是唯一可译码。
3. 按照树图的构造法则,若能将码画成码树 则是即时码,也就是唯一可译码。
4. 按唯一可译码判断法进行判断。
只有唯一可译码判断法能确切判断是否是唯一可译码
K KL log m
L
定长编码定理
定长编码定理:由L个符号组成的、每个符号的熵
为HL(X)的无记忆平稳信源符号序列X1X2…Xl…XL, 可用KL个符号Y1, Y2,…, Yk,…YKL(每个符号有m种 可能值)进行定长编码。
对任意ε>0,δ>0,只要
KL L
logmHLX
则当L足够大时,必可使译码差错小于δ;
接近或相等,并为每一组分配一位码元。如编 二进制码就分成两组,编m进制码就分成m组。 3. 将每一分组再按同样原则划分,重复步骤2,直 至概率不再可分为止。 4. 信源符号所对应的码字即为费诺码。
哈夫曼编码方法
哈夫曼编码的步骤
1. 将信源消息符号按其出现的概率大小依次排列 p(x1)≥p(x2)≥…≥ p(xn)
如果是二元信源,则对于任意小的ε>0,每一 个信源符号的平均码长满足如下公式:
R(D )KR(D )
第6章 信道编码
重点掌握
差错控制相关的基本概念 差错控制系统分类 检、纠错能力 有扰离散信道编码定理
i 1
Pi p xk k 1
4. 将累加概率Pi变换成二进制数,取小数点后Ki 位为该消息的码字
费诺编码方法
费诺编码属于概率匹配编码,不是最佳的 编码方法。编码过程如下:
1. 将信源消息符号按其出现的概率依次排列
p(x1)≥ p(x2)≥…≥ p(xn) 2. 按编码进制数将概率分组,使每组概率尽可能
相关主题