当前位置：文档之家 › 信源编码--离散信源无失真编码概述

信源编码--离散信源无失真编码概述

  • 格式：ppt
  • 大小：460.06 KB
  • 文档页数：16

下载文档原格式

  / 16

合集下载

信息论基础第四章 离散信源的无失真编码

信息论基础第四章 离散信源的无失真编码

信源编码有关概念 （1）平均码长
L p(a i )l i
i 1
q
单位：码符号/信源符号 意义：每个源符号平均需要的码符号数。 编码后每个信源符号平均用 L个码符号表示。 （2）信息传输率（平均每个码符号携带的信息量）
R
H(X ) L
16
L 越短，信息传输率就越高。
（3）最佳码（紧致码） 最佳码：对于某一信源和某一码符号集，若有一唯一可 译码，其平均码长小于所有其他唯一可译码的 平均码长，则该码称为最佳码。（最短唯一可 译码） 无失真信源编码的基本问题就是找到最佳码，最 佳码的平均码长为理论极限。
i 1 i 1
证明：
q


i 1
q
r li p i log pi

i 1
q
r li pi ( 1) pi
r
i 1
q
li
pi 1 1 0
i 1
q
H(S) H ( S ) L log r 0 L log r
18i l i log r
等长非奇异码一定是唯一可译码 ak a1 a2 a3 a4 p(ak) 0.5 0.25 0.125 0.125 码A 00 01 10 11 码B 00 01 00 10
5
等长编码及其定理
对信源S的N次扩展信源SN进行等长编码 若S = { s1, s2,…, sq}，则N次扩展信源S N= { a1, a2,…, aqN}， 共有qN个符号序列。 设码符号集为X = { x1, x2,…, xr}，长度为l 的码符号序列Wi = (xi1 xi2 … xil), xi1, xi2,…, xil∈X。
异前缀码等价于即时码

2.4 离散信源的无失真编码

2.4 离散信源的无失真编码

信源编码的分类
无失真信源编码：把所有的信息丝毫不差地编码， 无失真信源编码：把所有的信息丝毫不差地编码，然后传送 信源编码 到接收端。 到接收端。 离散无失真信源编码：原始消息是多符号离散信源消息 无失真信源编码 是多符号离散信源消息， 离散无失真信源编码：原始消息是多符号离散信源消息， 按无失真编码的方法，编成对应的码序列。 按无失真编码的方法，编成对应的码序列。 限失真信源编码 允许不对所有的信息进行编码， 信源编码： 限失真信源编码：允许不对所有的信息进行编码，只对重要 信息进行编码，对其它不影响视听的信息进行压缩、丢弃， 信息进行编码，对其它不影响视听的信息进行压缩、丢弃， 但这种压缩失真必须在一定的限度以内 压缩失真必须在一定的限度以内， 但这种压缩失真必须在一定的限度以内，因此称为限失真信 源编码。 源编码。 离散限失真信源编码 离散限失真信源编码 连续限失真信源编码 连续限失真信源编码
本章主要内容
2.1单符号离散信源 2.1单符号离散信源 2.2多符号离散平稳信源及熵 2.2多符号离散平稳信源及熵 2.3连续信源及熵 2.3连续信源及熵 2.4离散无失真信源编码定理 2.4离散无失真信源编码定理
2
2.4 离散无失真信源编码定理
信源涉及的重要问题： 信源涉及的重要问题：
信源输出的信息量有多少：即信源信息量的计算问题。 信源输出的信息量有多少：即信源信息量的计算问题。 如何更有效地表示信源输出的消息： 如何更有效地表示信源输出的消息：在尽量提高通信 效率的前提下，对信源所发送的消息进行变换， 效率的前提下，对信源所发送的消息进行变换，即信 源编码。 源编码。
已知：定长无失真离散信源编码定理： 已知：定长无失真离散信源编码定理：
原始信源长为L 原始信源长为L的平稳无记忆离散序列信源 每个符号的熵为H(X), H(X),即 XL=(X1X2……XL) ，每个符号的熵为H(X),即平均 X 符号熵为H(X),要想进行无失真的信源编码，需 符号熵为H(X),要想进行无失真的信源编码， H(X),要想进行无失真的信源编码 满足 令 →0, ε

2.4 离散无失真信源编码定理

2.4 离散无失真信源编码定理
信源 编码器 码表 信道
一、 信源的符号集和符号序列
1. 信源符号集: 信源发出的符号消息的集合，记为X，
设 X 有n个符号：X ={ a1 , a2 , … , an }. 2. 信源符号序列:由信源符号集合 X 中的符号组成长度 为L的符号序列， 记为 X ( X1 X 2 X l X L ) L为信源符号序列长 , 不同的符号序列共有 nL。 若L=1，则信源符号序列为信源符号集合中的符号。
单符号对应变长码的平均码长为
K p(ai ) Ki
i 1 n
码符/信源符号
K 是每个信源符号平均需用的码元数。
②符号序列信源空间XL
X L X 1L L L p( X i ) p( X 1 ) X 2L p( X 2L )
L X nL L p( X n L )
码字Yi 的码元个数 Ki 称为码字Yi的码长。
所有码字Yi 的码长 Ki 均相等称为定长码。 码字Yi 的码长 Ki 不全相等称为变长码。
三、编码与译码
1. 信源编码：将信源符号 xi 或符号序列 Xi 按一种规则
映像成码字Yi的过程。 2. 无失真编码：信源符号到码字的映射必须一一对应。
3. 译码：从码符号到信源符号的映射。
变换的要求: (1)能够无失真或无差错地从Y恢复X，也就是能正确地进行 反变换或译码(惟一可译码)。 (2)传送Y时所需要的信息率最小 。
由于Yk可取m种可能值，即平均每个符号输出的最大信息量为
log2m，K长码字的最大信息量为Klog2m。用该码字表示L长的 信源序列，则送出一个信源符号所需要的信息率平均值为
★香农信息论三大定理 :
1. 第一极限定理: 无失真信源编码定理。

第三章-无失真信源编码

第三章-无失真信源编码

相对熵 —— 信源的实际信息熵与具有同样符 号集的最大熵的比值。
H(X ) = H(X )
H max ( X ) H0 ( X )
信源的冗余度E —— 1减去相对熵。
E 冗余度 1 H (X ) 1 H (X ) 1
Hmax ( X )
H0(X )
信源最大可能熵与实际熵的差定义为内熵：
内熵 Hmax ( X ) H ( X )
或 H0(X ) H(X )
英语的熵率
• 英语是稳恒的各态历经信源吗？
这个很难无法回答，但是我们仍可以从统计角度上对英语语言进行分析 假定源消息含有26个字母和1个空格，忽略标点符号和大小写字母出现
的概率是不同的，E最大（13%），Q和Z最小（大约0.1%） 两个字母的组合也是非等概的，TH出现最频繁（3.7%） 由此，我们可以构建高阶的概率转移模型，但是实际上这是不可行的。
将序列进行分割
信源编码的基础是什么?
信源编码的基础是：两个编码定理，即无失真编码定理和限失真 编码定理。
说明：
1）无失真编码是可逆编码，即信源符号转换成代码后，可从代码 无失真的恢复原信源符号。只适用于离散信源。
2）对于连续信源，编成代码后就无法无失真地恢复原来的连续值， 因为后者的取值可有无限多个。此时只能根据率失真编码定理在 失真受限制的情况下进行限失真编码
输过程中出现错误时，可从它的上下关联中纠正错误，因此 从提高信息传输可靠性观点出发，总是希望增加信源冗余度。 信源编码就是通过减少或消除信源冗余度来提高通信的传输 效率，即提高通信的有效性。 信道编码则是通过增加信源的 冗余度来提高通信的抗干扰能力，即提高通信的可靠性。
3.3 无失真信源编码
离散、无失真、无记忆信源编码的一般模型：

第三章 无失真离散信源编码解析

第三章 无失真离散信源编码解析

10
3.2 离散无失真信源编码定理
一、香农理论对数据压缩的指导意义
1、数据压缩的途径 途径一：使序列中的各个符号尽可能地互相
独立，即解除相关性，去冗余； 途径二：使编码中各个符号出现的概率尽可
能地相等，即概率均匀化。
2、数据压缩的理论极限
11
3.2 离散无失真信源编码定理
二、编码的指标
1. 平均码长
第三章 无失真离散信源编码
1
3.1 基本概念
例1：
N个消息集合 X={a、b、c… z、空格…}
信源 编码器
信道基本 符号(0、1)
N个代码组集合 C={c1、 c2、…cN}
2
3.1 基本概念
一、信源编码的定义：
信源编码是以提高通信的ቤተ መጻሕፍቲ ባይዱ效性为目的编码。
信源编码
适合信道传输 减少冗余度
3
3.1 基本概念
5
3.1 基本概念
二、信源编码的分类
(1) 二元码和r元码 若码符号集 X {0,1}，编码所得码字为一些
适合在二元信道中传输的二元序列，则称二元码。 二元码是数字通信与计算机系统中最常用的一种 码。若码符号集共有 r 个元素，则所得之码称为 r 元码。
6
3.1 基本概念
二、信源编码的分类
(2) 基本源编码和N次扩展源编码 (3) 无失真编码 和有失真编码
• 信源熵： H ( X ) = 1/4 log4 +3/4 log3/4 = 0. 811 bit / 信源符号
若用二元定长编码 (0,1) 来构造一个即时码：
• 平均码长： • 编码效率：
二元码符号 / 信源符号 L1 1
R H (x) 0.811L bit/code

离散无失真信源编码

离散无失真信源编码
第五章
离散无失真信源编码
5.1 离散信源编码 5.2 离散无失真信源编码定理 5.3 香农编码 5.4 费诺编码 5.5 哈夫曼编码
5.1
2.1.1 2.1.2离来自信源编码信源编码概述 码字唯一可译的条件
2
信源编码概述(续)
两类信源编码 无失真信源编码：编码运算能够完全恢复原来的数据 信息，保证信源产生的全部信息无失真地传送给信 宿，适用于离散信源 限失真信源编码：编码运算允许有一定的误差，在允 许误差的条件下，寻找信源的最小“消息体积”；适 用于连续信源 无失真信源编码只对信源的冗余度进行压缩，不改变信 源熵；而限失真信源编码是通过压缩信源熵来减小消息 的“体积” 无失真信源编码由于信源符号与码字一一对应，编码器 的输出概率分布与输入概率分布完全相同，因此编码前 后的熵保持不变
信源编码概述(续)
用树图法可以方便地构造即时码。从树根开始，树中每个中间 节点都伸出 1 至 r 个树枝，不同的树枝标记不同的码元。 将所有的码字都安排在终端节点上就可以得到即时码 每个中间节点都正好有 r 个分枝的树称为整树(满树) 所有终端节点的阶数都相等的树为完全树，对应于定长码
r=2
8
信源编码概述(续)
码1 00 01 10 11
码2 0 10 110 111
平均码长越小，则平 均一个码元所携带的 信息量越大，信息的 冗余度越小。使平均 码长最小的编码称为 最佳编码 采用变长编码能使平 均码长缩短
4
l1 = 2 × (0.5 + 0.25 + 0.125 + 0.125) = 2 码元/单信源符号 l2 = 1 × 0.5 + 2 × 0.25 + 3 × 0.125 + 3 × 0.125 = 1.375 码元/单信源符号

信息理论与编码 第四章 离散无记忆信源无失真编码


7
63
H (U ) i1 P(ui ) log P(ui ) 32 bit/符号
l l 3 码元/符号
c
H (U ) l log r
63 32
3 log 2
65.625%
提高编码效率的方法：对符号串进行编码，同时
引入一定的失真。
20
4、引入失真，提高编码效率
lN H (U )
N log r
4
11 11
l
P(ui )li
i 1
1 2 3 3 24 88
1.75 码元/符号
编码策略： 出现概率大的符
编码策略：采用等长
号采用较短的码字，出现概
的码字
率小的符号采用较长的码字7
3、信息率
信
U
源 {u1,u2 , ,uq}
编码器 f
W
X
{w1,w2 , ,wq} {x1,x2 , ,xr }
限定定长编码码长的最小值，因此最佳的定长编码效率为：
c
H (U ) l log r
H (U ) lN log r
H (U )
H (U )
(1c )H (U ) c
(4-3-9)
N
可以证明，差错率满足关系：Pe
2 (U N 2
)
信源自信息量的方差
2 (U ) E I (ui ) H (U )2 P(ui )log P(ui )2 H (U )2
f 是一 一对应 的映射
P(wi ) P(ui ) i 1,2, ,q
X
{x1,x2 , ,xr }
H(W ) H(U) bit/码字或 bit/符号
新信源X ：H (X ) H (W ) H (U ) bit/码元

信源编码--离散信源无失真编码概述(ppt 17页)

在一个固定的时刻，信源发出的是一个随机变量。 随着时间的延续，信源发出的是一个随机过程。 （因此，一般的信源种类太多，其统计性质太复杂。怎样做工
程实用的简化？）
2020/8/22
2
§3.1 信源及其分类
离散信源 信源每隔一个定长时间段就发出一个随机变量； 随着时间的延续，信源发出的是随机变量序列
pe= P{(U1U2…UL)=(u1u2…uL) | (u1u2…uL)的码字在译码时并不译为(u1u2…uL)}。
2020/8/22
8
§3.2 离散无记忆（简单）信 源的等长编码
（关于编码速率的说明：
编码速率本来是编码设备的性能指标。这就是说，首先有 了编码设备的编码速率R0，然后选择N和L，使得实际的编 码速率NlogD/L不能超过编码设备的编码速率R0 ： R=NlogD/L≤R0。
R<H(U1)≤logK。 （如果H(U1)=logK，则以上两种情形已经概括了全部情形。
但如果H(U1)<logK，则还有一种情形） 当logK>R>H(U1)时，虽然无论怎样编码都是有错编码，
但可以适当地编码和译码使译码错误的概率pe任意小。这 就是所谓“渐进无错编码”。
2020/8/22
10
2020/8/22
6
§3.2 离散无记忆（简单）信 源的等长编码
（3）如果限定码字的长度为N（即每个码字都是一个N维向 量），则称此编码为等长编码，能够选择的不同码字的个 数为DN。
（4）如果限定码字的长度为≤N（即每个码字都是一个≤N维 的向量），则称此编码为不等长编码，能够选择的不同码 字的个数为
2020/8/22
3
§3.1 信源及其分类
（总结：离散无记忆简单信源就是时间离散、事件离散、各 随机变量独立同分布的信源。课程学习所面对的信源将主 要是离散无记忆简单信源）

第三章_信源编码-离散信源无失真编码


思考
2
L ( H )
2
LH
2
L
1） 固定L，当ε→0时， 上式右边趋于1； 2） 固定ε，当L →0时， 上式右边趋于0；
编码效率
• 编码效率
H (U ) 1 R
• 由等长编码定理知
R H (U )
• 编码效率越接近1，编码越有效。
例3.2.3
定义： 满足如下条件的信源序列构成的集合称为强典型序列集。
0 1 2 3 4 5 6 7 8 9 01101 01011 11001 10110 11010 00111 10101 11100 01110 10011
等长编码能实现信源压缩吗？
• 例子：考虑离散无记忆信源
0 1
B C D A U 1/ 2 1/ 4 1/ 8 1/ 8
H(U) = 1.75 bits。
弱典型序列的特性
• 定理3： 证明：
(1 )2
L ( H )
TU ( L, ) 2
L ( H )
1 P (u L )
u L TU ( L , )

P (u L )
u L TU ( L , )

2 L ( H ) TU ( L, ) 2 L ( H )
• 如果Uk彼此独立且服从同一概率分布，则 称该信源为简单信源。
简单信源
本章的主要考察对象
• 简单信源可以建模为一个随机变量。 • 随机变量的取值空间---信源字母表
a1 , a 2 , , a K A p1 , p 2 , , p K
第2节 离出在幅度和时间上的连续与否：离散信 源、连续信源（波形信源）、时间离散连 续信源等。 • 时间离散信源：

信息论：第8章 无失真的信源编码讲解

这三种码的平均码长都比较短。 因为平均码长是各个码的概率平均，可以想象， 应该使出现概率大的信源符号编码后码长尽量短一 些。三种编码方法的出发点都是如此。
9
8.1 霍夫曼码
香农编码 • 香农编码严格意义上来说不是最佳码。 • 香农编码是采用信源符号的累计概率分布函数来
分配码字。
10
香农编码方法如下： (1)将信源消息符号按其出现的概率大小依次排列：
• 一般情况下，按照香农编码方法编出来的码，其平 均码长不是最短的，也即不是紧致码(最佳码)。只有 当信源符号的概率分布使不等式左边的等号成立时， 编码效率才达到最高。
19
8.1.1 二元霍夫曼码
1952年霍夫曼提出了一种构造最佳码的方法。它是一 种最佳的逐个符号的编码方法。其编码步骤如下： (1) 将信源消息符号按其出现的概率大小依次排列
上式。
36
注意: 对于r元码时，不一定能找到一个使式 q (r 1) r 成立。在不满足上式时，可假设一些信源符号： sq1 , sq2 ,..., sqt 作为虚拟的信源，并令它们对应 的概率为零，即：pq1 pq2 ... pqt 0
而使 q t (r 1) r 能成立，这样处理后得到
21
例8.1:
对离散无记忆信源 进行霍夫曼编码。

S p(si
)

s1 0.4
s2 0.2
s3 0.2
s4 0.1
s5 0.1
解:编码过程如表所示，
1)将信源符号按概率大小由大至小排序。
2)从概率最小的两个信源符号和开始1”，上面的信源符号（大概率）为“0”。若两 支路概率相等，仍为下面的信源符号为“1” 上面的 信源符号为“0”。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
R=NlogD/L≤R0。 当编码速率R比较高时，可以选择比较大的N，因此可供选
择的码字比较多，因此更容易设计出能够快速识别的码， 降低译码的难度。 当编码速率R比较低时，意味着使用低成本的编码设备。此 时只能选择不大的N，因此更需要编码的技巧。 ）
•2020/3/21
§3.2 离散无记忆（简单）信 源的等长编码
pe= P{(U1U2…UL)=(u1u2…uL) | (u1u2…uL)的码字在译码时并不译为(u1u2…uL)}。
•2020/3/21
§3.2 离散无记忆（简单）信 源的等长编码
（关于编码速率的说明： 编码速率本来是编码设备的性能指标。这就是说，首先有
了编码设备的编码速率R0，然后选择N和L，使得实际的编 码速率NlogD/L不能超过编码设备的编码速率R0 ：
（注意：在不等长编码中，并不能同时使用D(DN-1)/(D-1)个 不同的码字。一个长度为2的字母串究别。
在等长编码中不存在这样的识别问题 ）
•2020/3/21
§3.2 离散无记忆（简单）信 源的等长编码
（本节以下将专门讨论等长编码）
（5）编码速率
信源编码--离散信源无失 真编码概述
2020/3/21
§3.1 信源及其分类
信源的概念
（直观地理解，信源就是信息的来源。但是这里必须要注意两 点）：
在一个固定的时刻，信源发出的是一个随机变量。 随着时间的延续，信源发出的是一个随机过程。 （因此，一般的信源种类太多，其统计性质太复杂。怎样做工
程实用的简化？）
云阴），（阴晴），（阴云）， （阴阴）}。 用字母表{0, 1}对(U1U2)的事件进行2元编码如下： （晴晴）→0000，（晴云）→0001，（晴阴）→0011， （云晴）→0100，（云云）→0101，（云阴）→0111， （阴晴）→1100，（阴云）→1101，（阴阴）→1111。
•2020/3/21
一般的信源 连续信源：有时间连续的信源，也有事件连续的信源； 有记忆信源：信源在不同时刻发出的随机变量相互依赖； 有限记忆信源：在有限时间差内的信源随机变量相互依赖； 非简单信源：信源在不同时刻发出的随机变量具有不同的概
率分布。 马尔可夫信源：信源随机过程是马尔可夫过程。
•2020/3/21
§3.2 离散无记忆（简单）信 源的等长编码
R=NlogD/L。
（6能）够无实错现编无码错(编U1码U的2…充U要L)的条不件同是事DN件≥K用L。不（同即的编码码字速来率表示。 R=NlogD/L≥logK）
（7）有错编码 示。
(U1U2…UL)的有些不同事件用相同的码字来表
（8）有错编码的译码方法与 “译码错误”概率 当使用有错编 码时，必须给出译码方法（一个码字究竟翻译成哪个事件） 。“译码错误”的概率定义为
但可以适当地编码和译码使译码错误的概率pe任意小。这 就是所谓“渐进无错编码”。
•2020/3/21
§3.2 离散无记忆（简单）信 源的等长编码
（10）渐进无错编码 （简单地说就是：当R>H(U1)时，可以适 当地编码和译码使得译码错误的概率pe任意小。严格地说就 是：）
设给定了编码设备的编码速率R0，R0>H(U1)。则对任意的ε>0 ，总存在一个L0，使得对任意的L>L0，都有对(U1U2…UL)的 等长编码和对应的译码方法，满足
•2020/3/21
§3.1 信源及其分类
离散信源 信源每隔一个定长时间段就发出一个随机变量； 随着时间的延续，信源发出的是随机变量序列
其中
…U-2U-1U0U1U2…，
Uk为第k个时间段发出的随机变量； 每个Uk都是一个离散型的随机变量。 离散无记忆信源 离散无记忆信源是这样的离散信源：随机
（2母）串设来有表一示个(U含1DU个2…字U母L)的的事字件母，表每{b一1, 个b2,事…件, b都D}要。用需一要个用字字 母串来表示。
这种表示方法称为D元编码； 每一个事件所对应的字母串称为一个码字。
•2020/3/21
§3.2 离散无记忆（简单）信 源的等长编码
例：1离U散0U无1U记2…忆。简其单中信U源1的发事出件的有随3机个变：量{晴序, 列云为, 阴：}…。U-2U(U1U2)有9个事件 {（晴晴），（晴云），（晴阴），（云晴），（云云），（
（顺序地叙述以下的概念） （1）设有一个离散无记忆简单信源，信源发出的随机变量序
列：KL为{个a1：：, a…2, U…-2,Ua-K1U}，0U则1UL2维…信。源设随信机源向随量机(变U1量UU2…1的U事L)的件事有件K个有 {(u1u2…uL)|其中每个分量ul跑遍{a1, a2, …, aK}}。
变量…、U-2、U-1、U0、U1、U2、…相互独立。 离散无记忆简单信源 离散无记忆简单信源是这样的离散无
记有忆相信同源的：概率随分机布变量。…、U-2、U-1、U0、U1、U2、…具
•2020/3/21
§3.1 信源及其分类
（总结：离散无记忆简单信源就是时间离散、事件离散、各 随机变量独立同分布的信源。课程学习所面对的信源将主 要是离散无记忆简单信源）
§3.2 离散无记忆（简单）信 源的等长编码
（3）如果限定码字的长度为N（即每个码字都是一个N维向 量），则称此编码为等长编码，能够选择的不同码字的个 数为DN。
（4）如果限定码字的长度为≤N（即每个码字都是一个≤N维 的向量），则称此编码为不等长编码，能够选择的不同码 字的个数为 D1+D2+…+DN=D(DN-1)/(D-1)。
①实际的编码速率R=NlogD/L≤R0， ②译码错误的概率pe<ε。 （11）渐进无错编码的原理 大数定律。随着L的增加，
（9）在无错编码的前提下，编码的最低代价 当R≥logK时，能够实现无错编码。 当R<H(U1)时，无论怎样编码都是有错编码。这是因为
R<H(U1)≤logK。 （如果H(U1)=logK，则以上两种情形已经概括了全部情形。
但如果H(U1)<logK，则还有一种情形） 当logK>R>H(U1)时，虽然无论怎样编码都是有错编码，