第4章 无失真信源编码 (1)总结
- 格式：ppt
- 大小：1.11 MB
- 文档页数：43
下载文档原格式
合集下载
信息论基础第四章 离散信源的无失真编码
信源编码有关概念 （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。
异前缀码等价于即时码
无失真的信源编码
7/13/2013 7/31
[例]有一单符号离散无记忆信源
对该信源编二进制香农码。其编码过程如表所示。 二进制香农编码
xi x1 x2 x3 x4 x5 x6 p(xi) 0.25 0.25 0.20 0.15 0.10 0.05 pa(xj) 0.000 0.250 0.500 0.700 0.85 0.95 ki 2 2 3 3 4 5 码字 00 01 100 101 1101 11110 0.000 =(0.000)2 0.250 =(0.010)2 0.500 =(0.100)2 0.700 =(0.101)2 0.85 =(0.1101)2 0.95 =(0.11110)2
7/13/2013 4/31
信源编码概述
信源的原始信号绝大多数是模拟信号，因此，信源编码的 第一个任务是模拟和数字的变换，即：A/D，D/A。 抽样率取决于原始信号的带宽：fc = 2 w，w为信号带宽。 抽样点的比特数取决于经编译码后的信号质量要求： SNR ＝ 6 L(dB)，L为量化位数 但是，由于传输信道带宽的限制，又由于原始信源的信号 具有很强的相关性，则信源编码不是简单的A/D，D/A， 而是要进行压缩。为通信传输而进行信源编码，主要就是 压缩编码。 信源编码要考虑的因素：
只含(n－2)个符号的缩减信源S2。
重复上述步骤，直至缩减信源只剩两个符号为止，此时所剩两个符 号的概率之和必为1。然后从最后一级缩减信源开始，依编码路径向
前返回，就得到各信源符号所对应的码字。
7/13/2013 16/31
[例] 设单符号离散无记忆信源如下，要求对信源编二进制哈夫曼码。
7/13/2013
7/13/2013
2/31
信源编码：提高通信有效性。通常通过压缩信源的
[例]有一单符号离散无记忆信源
对该信源编二进制香农码。其编码过程如表所示。 二进制香农编码
xi x1 x2 x3 x4 x5 x6 p(xi) 0.25 0.25 0.20 0.15 0.10 0.05 pa(xj) 0.000 0.250 0.500 0.700 0.85 0.95 ki 2 2 3 3 4 5 码字 00 01 100 101 1101 11110 0.000 =(0.000)2 0.250 =(0.010)2 0.500 =(0.100)2 0.700 =(0.101)2 0.85 =(0.1101)2 0.95 =(0.11110)2
7/13/2013 4/31
信源编码概述
信源的原始信号绝大多数是模拟信号，因此，信源编码的 第一个任务是模拟和数字的变换，即：A/D，D/A。 抽样率取决于原始信号的带宽：fc = 2 w，w为信号带宽。 抽样点的比特数取决于经编译码后的信号质量要求： SNR ＝ 6 L(dB)，L为量化位数 但是，由于传输信道带宽的限制，又由于原始信源的信号 具有很强的相关性，则信源编码不是简单的A/D，D/A， 而是要进行压缩。为通信传输而进行信源编码，主要就是 压缩编码。 信源编码要考虑的因素：
只含(n－2)个符号的缩减信源S2。
重复上述步骤，直至缩减信源只剩两个符号为止，此时所剩两个符 号的概率之和必为1。然后从最后一级缩减信源开始，依编码路径向
前返回，就得到各信源符号所对应的码字。
7/13/2013 16/31
[例] 设单符号离散无记忆信源如下，要求对信源编二进制哈夫曼码。
7/13/2013
7/13/2013
2/31
信源编码：提高通信有效性。通常通过压缩信源的
信息论.第4章无失真信源编码
S N
1
P
p(1 )
2 ... p(2 ) ...
qN
p(qN )
扩展信源熵为H(SN)，
5
用码符号集X=(x1,…,xr)对SN 编码，则总可以找到
一种编码方法，构成唯一可译码，使信源S中的一
个信源符号所需要的码字平均长度满足
H (S) 1 LN H (S) log r N N log r
N log r 则当N足够大时，译码错误概率趋于1。
3
信源编码效率 编码速率：对于定长编码，编码速率定义为
R L log r N
编码效率：
H(S)
R
4
变长无失真信源编码定理（香农第一定理）
设离散无记忆信源
S
P
s1 p( s1 )
s2 p(s2 )
... ...
sq
p(
sq
)
其信源熵为H(S)，它的N次扩展信源SN为
l log q log r
2
定长信源编码定理
设有离散无记忆信源，熵为H(S) ，若对信源的长为N 的符号序列进行定长编码，设码字是从r个码符号集中选 取L个码元构成，对于 > 0 只要满足
L H(S)
N log r 则当N足够大时，可实现译码错误概率任意小的等长编
码，近似无失真编码。
反之，若 满足 L H (s) 2
i 1
克拉夫特证明不等式为即时码存在的充要条件； 麦克米伦证明不等式为唯一可译码存在的充要条件。
1
简单信源S存在唯一可译定长码的条件为：
q r l l log q
log r
N次扩展信源SN存在唯一可译定长码的条件为：
qN rL
L log r N log q来自L log q N log r
第4章_无失真信源编码-zuoye
第一节 引言
信源编码理论是信息论的一个重要分支，其理论基础是信源编码的两个 定理。从编码结果使信源消息的信息量有无损失角度 无失真信源编码定理：香农第一定理 是离散信源/数字信号编码的基础； 限失真信源编码定理：香农第三定理 是连续信源/模拟信号编码的基础。 信源编码的分类：离散信源编码、连续信源编码和相关信源编码三类。 离散信源编码：独立信源编码，可做到无失真编码； 连续信源编码：独立信源编码，只能做到限失真信源编码； 相关信源编码：非独立信源编码。
l •定理5.3的条件式也可写成： N log r H ( S ) l ' R log r 称之为编码信息率。可见，编码信息 令： N
率大于信源的熵，才能实现无失真编码。
第三节 等长信源编码定理
H (S ) H (S ) l R' log r N
为了衡量编码效果，引进
最佳编码效率为： R'
第四节 变长信源编码定理
定理5.8 无失真变长信源编码定理（香农第一定理） 离散无记忆信源S的N次扩展信源 S N ，其熵为 H (S N ) ，并且
{1 , 2 ,..., q } 对信源 S N 进行编 编码器的码元符号集为A：
码，总可以找到一种编码方法，构成唯一可译码，使信源S 中每个符号si所需要的平均码长满足 H ( S ) L N H ( S ) 1
li r 1 i 1 q
反之，若码长满足上式，则一定存在这样的即时码 。 可以根据即时码的树图构造法来证明。 后来，B.McMillan证明了对于唯一可译码也必须满足 上面的不等式，
第四节 变长信源编码定理
定理5.6 若存在一个码长为 l1 , l2 , , lq 唯一可译码，则一 定存在一个同样长度的即时码。 这说明，其他唯一可译码在码长方面并不比即时码 占优。所以在讨论唯一可译码时，只需要讨论即时码就 可以了。
无失真信源编码
第4节 平均码长与编码有效性
讨论：
符号 s1
s2
s3
s4
概率 1/2 1/4 1/8 1/8
码字 000 001 01 1
码长 3
3
2
1
平均码字长度 信息率
q
21
n i1 pini 8
R H ( X ) 11 n 21
第4节 平均码长与编码有效性
从上面两种情况的对比得出，要使非延长码的平均码长n尽量小，使无 失真信源编码尽量有效，必须遵循码字长度与信源概率空间的概率分量之间 的正确搭配原则：
无失真信源编码
2020年4月20日星期一
第4节 平均码长与编码有效性
3、码率
1) 信源的熵
q
H ( X ) pi log pi 比特 / 信源符号
i 1
平均每个信源符号所携带的信息量
2) 信息传输率（码率）
R
平均每信源符的信息量 平均信源码字长度
H(X n
)
比特/信源码符号
平均每个信源信源码符号携带多少比特的信息量
这种方法能否使每个信源符号 si :i 1, 2,...,所q需要的 平均码长有所下降？也就是
说，能否用扩展信源的手段，达到数据压缩的目的呢？
第6节 信源扩展与数据压缩
以下，我们分别就信源S无记忆和有记忆两种情况来讨论和回答这个问题。
（一）信源S无记忆 设离散无记忆信源S的信源空间为
S [S P] P(S)
单独地赋予一个码字 wi :i 1, 2,..., q ，编出来的非延长码（单义可译码）
W : w1, w2 ,..., wq 的平均码长 n的下限值在数量上有信源S的熵值Hr S
所决定。如果进一步降低非延长码的平均码长 n，提高无失真信源编码的
第4章无失真信源编码
x1 p( x1
)
x2 ... p(x2 ) ...
xN p(xN
)
对单个信源符号 x1，x2，，xN 编码，码字分别为W1，W2，，WN ，各码字对应的码 长分别为 n1，n2，nN 。
因为信源符号与码字一一对应，所以
由此，码的平均码长可以写为：
p(Wi ) p(xi )
L p(ni )ni
则可以使传输几乎无失真。反之，当 L H N (X ) 时，不可能构成无失真的编码，也就是不可能做 一种编码器，能使接收端译码时差错概率趋于零。 L H N (X ) ：某信源有 8 种等概率符号， N 1，则信源序列的最大熵为：
H1 (X ) log 2 8 3 比特
设 X i (X1, X 2 ,, X l ,, X N ) 是信源序列的样本矢量， X l {a1, a2 ,, ai ,, an} ，则共有 n N 种样本，我们把它分为两个互补的集 Aε 和 AεC，集 Aε 中的元素（样本矢量）有与之对应的不 同码字，而集 AεC 中的元素没有与之对应的输出码字，因而会在译码时发生差错。
可以用 LN 个符号 Y1,Y2 ,,Yk ,,YN L ，(每个符号有 m 种可能值)进行定长编码。对任意 ε>0，δ>0，只要
LN N
log r
≥ HN (X) + ε
则当 N 足够大时，必可使译码差错小于 δ；反之，当
(4-2)
LN N
log r ≤ H N (X ) + 2ε
(4-3)
时，译码差错一定是有限值，而当 N 足够大时，译码几乎必定出错。
其中： H 2 ——二元代码的码元熵；
H 2max——二元代码的码元最大熵，且 H 2max=1 比特/符号。
信息论与编码第四章
r li ⒄1
i 1
码长 li ，码符号集中符号个数r，信源符号个数q，称作kraft
不等式。
说明：唯一可译码一定满足不等式，反之，满足不等 式的码不一定是唯一可译码。
• 充分性证明：假定满足不等式的码长为 l1,l2 , ，,lq 在q个码字
中可能有长度相同的码字。设码长为1的有n1个，长度为2
111111
同价码：每个码符号（元）所占的传输时间都相
同
§4.2 等长码和等长信源编码定理
实现无失真编码的条件：
1、信源符号与码字一一对应 2、任意一串有限长的码符号序列与信源s的符号序列也 是一一对应，即N次扩展后仍满足一一对应关系。 同时满足上述条件称为唯一可译码
s : s1 s2 s3 s4 w j c : 0 10 00 01
N
N
I (ai ) log p(ai ) log pik I (sik )
k 1
k 1
E[I (ai )] H (S N ) NH (S )
E(x) xP （x） m H(s)
x
D[I (ai )] ND[I (si )] N{E[I 2 (si )] [H (s)2 ]
q
n
r li
nl m ax
Ajr j
i 1
jn
q
n
r
li
nl max
r j •rj
上界 ⑻
1 (N, ) p(G) MG • max p(ai ) ⑼
max p(ai ) 2 N[H (s) ]
下界 M G [1 (N , )]2 N[H (⑽ s) ]
我们可以只对集G中MG个信源序列进行一一对应的等长编码，
这就要求码字总数不小于MG就行，即
第4章 信源无失真编码
5种不同的码
U u1 u2 u3 u4
P (ui )
1 1 1 1 2 4 8 8
W1 00 01 10 11
W2 00 00 10 11
W3 1 00 01 10
W4 0 10 110 111
W5 0 01 1,00,10,01 u1u 2 u 4 u 3 011 1001001 10,01,00,1 u 4 u 3u 2 u1 1,00,1,00,1 u u u u u 1 2 1 2 1 111
W1：定长码。 非奇异码。 定长非奇异码肯定是UDC。 W2：定长码。 奇异码。 奇异码肯定不是UDC。
W3：变长码。 非奇异码。 续长码。 非即时码。 不是UDC。 即时码。 W4：变长码。 非奇异码。 非续长码。 非续长码肯定是UDC。 W5：变长码。 非奇异码。 续长码。 非即时码。 是UDC。
i 1
q
平均码长是衡量码的 性能的重要参数，“平均 码长小”说明平均一个码 元所携带的信息量大，信 息的冗余就小。
例：编码
设DMS的概率空间为
U u1 u2 u3 u4 P 1 2 1 4 1 8 1 8 U
信 源
U
{u1 ,u2 ,u3 ,u4 }
编码器 f
U
信源 编码
W
信源 译码
ˆ U
信 宿
f
f 1
• f为一一对应的变换只是无失真编码的必要条件，并不充分; • 要保证将码元序列无失真地恢复成信源符号序列，还要求编
出的码自身具有独特的结构。
• 有实用价值的码应该具有唯一可译性，即能从码字序列（也 是码元序列）唯一地恢复成信源符号序列。
1、唯一可译码（UDC，Uniquely Decodable Code） • 唯一可译码（UDC）：该码的码字组成的任意有限长码字序 列都能恢复成唯一的信源序列。否则称为非唯一可译码。 • 码是唯一可译码的充分必要条件是：由码中的码字组成的 任意有限长的码字序列（也是码元序列），都能唯一划分 成一个个的码字，且任一码字只与唯一一个信源符号对应。 • 奇异码：含相同码字的码。否则称为非奇异码。 • 非续长码：码中任一码字都不是另一码字的续长（延长）。 否则为续长码。 • 非即时码：如果接收端收到一个完整的码字后，不能立即 译码，还需等下一个码字开始接收后才能判断是否可以译 码。否则为即时码。
第4章无失真信源编码
是信源编码
码的分类-I
(1) 定长码：码中所有码字的长度都相同， 变长 码：码中的码字长短不一
信源 信源符号出
码表
符号ai 现概率p(ai) 码1 码2
a1
p(a1)
00 0
a2
p(a2)
01 01
a3
p(a3)
10 001
a4
p(a4)
11 111
表4-1 变长码与定长码
码的分类-II
(2)非奇异码:若信源符号和码字一一对应的 奇异码:反之。下表码1是奇异码，码2是非奇异码。
将这两个概率相加作为一个新字母的概率，与未分 配的二进符号的字母重新排队。 3. 对重排后的两个概率最小符号重复(2)的过程。 4. 重复上述过程，直到最后两个符号配以0和1为止。 5. 从最后一级开始，向前返回得到各个信源符号所对 应的码元序列，即相应的码字。
例 对以下信源进行哈夫曼编码
信源符号ai 概率p(ai) 码字Wi
H(S) L H(S) 1
log r
log r
离散平稳无记忆序列变长编码定理：对于平均符号 熵为H(S)的离散平稳无记忆信源，必存在一种无失真 编码方法，使平均信息率满足不等式
H (S) LN H (S) 1 log r N log r N
将定理进行改写：
H (S )
LN N
log r
H(S)
通常可用码树来表示各码字的构成
0
1
0
1
0
1
01
01
01
01
0 1 0 10 10 1 0 10 10 1 0 1
二进制码树(满树)
即时码的码树表示(2)
0
1
第四章 常用无失真信源编码方法
100%
$4.2 费诺编码
§4.2 费诺编码
* (1) 将信源符号按概率从大到小依次排列。设排序后的
编码步骤如下： 消息分别记为x1, x2, …, xn。 (2) 将信源符号按概率分成若干组，使每组的概率的 和尽量接近或相等。若编二元码就分两组，编m 元码 就分成m 组。 (3) 给每组分配一位码元，码元的分配是任意的。
0 log p( x j ) 1 1 log p( x j ) 2 2 log p( x j ) 3 3 log p( x j ) 4 4 log p( x j ) 5
kj 1 kj 2 kj 3 kj 4 kj 5
$4.1 香农编码
' ' ' ' ' ' x1 , x2 , x3 , x4 , x5 , x6 例4.1.1 对信源 0.2, 0.15, 0.1, 0.25, 0.25, 0.05 编香农码。
解: (1) 按概率从大到小依次排列
x2 , x3 , x4 , x5 , x6 x1 , 0.25, 0.25, 0.2, 0.15, 0.1, 0.05
计算编码效率
要求平均每个信源 符号传递的信息量 折算后，平均每个信源
符号的最大可能载信量
H (X ) L log m N
x1 , X 1 P , 码字 2 0
x2 ,
x5 , 1 1 1 1 , , , , 4 8 16 16 10 110 1110 1111 x3 , x4 ,
(5) 计算编码效率
log log log log H (X ) 1 1 1 1 log 2 L log m ( 1 2 3 2 4) 2 4 8 16 1 N
$4.2 费诺编码
§4.2 费诺编码
* (1) 将信源符号按概率从大到小依次排列。设排序后的
编码步骤如下： 消息分别记为x1, x2, …, xn。 (2) 将信源符号按概率分成若干组，使每组的概率的 和尽量接近或相等。若编二元码就分两组，编m 元码 就分成m 组。 (3) 给每组分配一位码元，码元的分配是任意的。
0 log p( x j ) 1 1 log p( x j ) 2 2 log p( x j ) 3 3 log p( x j ) 4 4 log p( x j ) 5
kj 1 kj 2 kj 3 kj 4 kj 5
$4.1 香农编码
' ' ' ' ' ' x1 , x2 , x3 , x4 , x5 , x6 例4.1.1 对信源 0.2, 0.15, 0.1, 0.25, 0.25, 0.05 编香农码。
解: (1) 按概率从大到小依次排列
x2 , x3 , x4 , x5 , x6 x1 , 0.25, 0.25, 0.2, 0.15, 0.1, 0.05
计算编码效率
要求平均每个信源 符号传递的信息量 折算后，平均每个信源
符号的最大可能载信量
H (X ) L log m N
x1 , X 1 P , 码字 2 0
x2 ,
x5 , 1 1 1 1 , , , , 4 8 16 16 10 110 1110 1111 x3 , x4 ,
(5) 计算编码效率
log log log log H (X ) 1 1 1 1 log 2 L log m ( 1 2 3 2 4) 2 4 8 16 1 N
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
号空间，然后针对变换后的信号进行编码。包括DCT、DFT、DWT。
识别编码识别编码主要用于印刷或打字机等有标准形状的文字符
号和数据的编码，比如文字和语音的识别。
后两种信源编码均为有失真的信源编码。 无失真信源编码针对离散信源，连续信源在量化编码的过程 中必然会有量化失真，连续信源只能近似地再现信源的消息。
奇异码与非奇异码 定义4.2 若一种分组码中的所有码字都不相同，则称此
分组码为非奇异码，否则称为奇异码。 奇异码：信源符号与码字是一一对应的，不存在不同信 源符号对应一个码字的问题。 (0,11,00,11)奇异码； (0,10,00,01)非奇异码
4.1.2 码的分类
唯一可译码与非唯一可译码
定义4.3 任意有限长的码元序列，如果只能唯一地分割 成一个个码字，便称为唯一可译码。 唯一可译码的物理含义是指不仅要求不同的码字表示不 同的信源符号，而且还要求对由信源符号构成的符号序 列进行编码时，在接收端仍能正确译码而不发生混淆。 唯一可译码首先是非奇异码，且任意有限长的码字序列 不会雷同。
4.1 信源编码的相关概念
4.1.1 编码器
信源输出的符号序列，需要变换成适合信道传输的符号序列， 一般称为码序列，对信源输出的原始符号按照一定的数学规 则进行的这种变换称为编码，完成编码功能的器件，称为编 码器。接收端有一个译码器完成相反的功能。 信源编码器的输入是信源符号集 S {s1, s2 , sq } ，共有q个信源 符号。同时存在另一个符号集 X {x1, x2 , xr } ，称为码符号集， 共有r个码符号，码符号集中的元素称为码元或码符号，编 si , i 1, 2, q 码器的作用就是将信源符号集S中的符号 变换成由 li个码符号组成的一一对应的码符号序列。编码器输出的码 wi , i 来表示，它与信源符号 1, 2, , q 符号序列称为码字，并用 S {s1 , s2 , sq } 之间是一一对应的关系，如图 4.1所示。
N H (S )
4.1.2 码的分类
分组码和非分组码 定义4.1 将信源符号集中的每个信源符号固定地映射成
一个码字，这样的码称为分组码。 用分组码对信源符号进行编码时，为了使接收端能够迅 速准确地将码译出，分组码必须具有一些直观属性。与 分组码对应的是非分组码，又称为树码、树码编码器输 出的码符号通常与编码器的所有信源符号都有关。
非分组码（树码） 码 分组码（块码） 奇异码
非唯一可译码 即时码
唯一可译码 非即时码
非奇异码
4.2 定长码及定长编码定理
若对一个有q个信源符号的信源S进行定长编码，那么信源S q 存在唯一可译定长码的条件是 K
(4.1) 其中，r是码符号集中的码元数，l是定长码的码长。 如果对信源S的N次扩展信源 S N 进行定长编码，若要编得的 定长码是唯一可译码，则必须满足
(4.2) q N 是信源S的N次扩展信源 S N 其中，q是信源S的符号个数， 的符号个数，r是码符号集X的码符号数。 唯一可译码存在的充分必要条件
qr
l
i 1
ห้องสมุดไป่ตู้
r
i
1
q r
N
l
4.2 定长码及定长编码定理
定长编码的信息传输效率是很低的。提高信息传输效率的方 法有： 方法1 考虑符号之间的依赖关系，对信源S的扩展信源 进行编码。 方法2对于概率等于0或非常小的符号序列不予编码。 定理4.2 离散无记忆信源的熵为H(S)，若对信源长为N的序 列进行定长编码，码符号集X中有r个码符号，码长为l，则 对于任意 0 ，只要满足 l log r
4.1.1 编码器
码字的集合C称为码，即 C {w1, w2 , , wq } 。信源符号 si 对应 li 称为码字长度，简称码长。 的码字wi 包含li 个码符号， 所以，信源编码就是把信源符号序列变换到码符号序列的一 种映射。 若要实现无失真编码，那么这种映射必须是一一 对应的、可逆的。 一般来说，人们总是希望把信源所有的 信息毫无保留地传递到接收端，即实现无失真传递，所以首 先要对信源实现无失真编码。
即时码与非即时码
定义4.4 无需考虑后续的码符号就可以从码符号序列中 译出码字，这样的唯一可译码称为即时码。 （1,10,100,1000），（1,01,001,0001）
4.1.2 码的分类
下面讨论唯一可译码成为即时码的条件。 定义4.5 设 wi xi , xi xi 为一码字，对于任意的 1 j l ， 称码符号序列的前j个元素 xi , xi xi 为码字的前缀。 按照上述的前缀的定义，有下述结论：
第4章 无失真信源编码
重庆交通大学信息科学与工程学院 通信工程系 黄大荣
1
第4章 无失真信源编码
信源编码的任务：减少冗余，提高编码效率。 信源编码的基本途径：解除相关性；概率均匀化 4.1 信源编码的相关概念 4.2 定长码及定长编码定理 4.3 变长码及变长编码定理 4.4 变长码的编码方法 4.5 实用的无失真信源码方法
图4.1
信源编码器
4.1.1 编码器
信源编码有以下3种主要方法： 匹配编码 根据信源符号的概率不同，编码的码长不同：概率大的
信源符号，所编的代码短；概率小的信源符号所编的代码长，这样 使平均码长最短。这类编码主要有香农编码、哈夫曼编码、费诺码 都是概率匹配编码，都是无失真信源编码。
变换编码 先对信号进行变换，从一种信号空间变换为另一种信
1 2 l
1 2 l
定理4.1 一个唯一可译码成为即时码
的充要条件是其中任何一个码字都不是 其他码字的前缀。 即时码可以用树图来构造．图5.2是一个 二元即时码的树图．
图5.2 二元即时码的树图
4.1.2 码的分类
树是没有回路的图，所以它也是由节点和弧构成的．树中最 顶部的节点称为根节点，没有子节点的节点称为叶子节点。 所有根节点的子节点称为一阶节点，所有一阶节点的子节点 n 阶节点最多有r n 个。节点的阶 称为二阶节点，依此类推。 次又称为节点的深度。 综上所述，可将信源编码作如下分类：
识别编码识别编码主要用于印刷或打字机等有标准形状的文字符
号和数据的编码，比如文字和语音的识别。
后两种信源编码均为有失真的信源编码。 无失真信源编码针对离散信源，连续信源在量化编码的过程 中必然会有量化失真，连续信源只能近似地再现信源的消息。
奇异码与非奇异码 定义4.2 若一种分组码中的所有码字都不相同，则称此
分组码为非奇异码，否则称为奇异码。 奇异码：信源符号与码字是一一对应的，不存在不同信 源符号对应一个码字的问题。 (0,11,00,11)奇异码； (0,10,00,01)非奇异码
4.1.2 码的分类
唯一可译码与非唯一可译码
定义4.3 任意有限长的码元序列，如果只能唯一地分割 成一个个码字，便称为唯一可译码。 唯一可译码的物理含义是指不仅要求不同的码字表示不 同的信源符号，而且还要求对由信源符号构成的符号序 列进行编码时，在接收端仍能正确译码而不发生混淆。 唯一可译码首先是非奇异码，且任意有限长的码字序列 不会雷同。
4.1 信源编码的相关概念
4.1.1 编码器
信源输出的符号序列，需要变换成适合信道传输的符号序列， 一般称为码序列，对信源输出的原始符号按照一定的数学规 则进行的这种变换称为编码，完成编码功能的器件，称为编 码器。接收端有一个译码器完成相反的功能。 信源编码器的输入是信源符号集 S {s1, s2 , sq } ，共有q个信源 符号。同时存在另一个符号集 X {x1, x2 , xr } ，称为码符号集， 共有r个码符号，码符号集中的元素称为码元或码符号，编 si , i 1, 2, q 码器的作用就是将信源符号集S中的符号 变换成由 li个码符号组成的一一对应的码符号序列。编码器输出的码 wi , i 来表示，它与信源符号 1, 2, , q 符号序列称为码字，并用 S {s1 , s2 , sq } 之间是一一对应的关系，如图 4.1所示。
N H (S )
4.1.2 码的分类
分组码和非分组码 定义4.1 将信源符号集中的每个信源符号固定地映射成
一个码字，这样的码称为分组码。 用分组码对信源符号进行编码时，为了使接收端能够迅 速准确地将码译出，分组码必须具有一些直观属性。与 分组码对应的是非分组码，又称为树码、树码编码器输 出的码符号通常与编码器的所有信源符号都有关。
非分组码（树码） 码 分组码（块码） 奇异码
非唯一可译码 即时码
唯一可译码 非即时码
非奇异码
4.2 定长码及定长编码定理
若对一个有q个信源符号的信源S进行定长编码，那么信源S q 存在唯一可译定长码的条件是 K
(4.1) 其中，r是码符号集中的码元数，l是定长码的码长。 如果对信源S的N次扩展信源 S N 进行定长编码，若要编得的 定长码是唯一可译码，则必须满足
(4.2) q N 是信源S的N次扩展信源 S N 其中，q是信源S的符号个数， 的符号个数，r是码符号集X的码符号数。 唯一可译码存在的充分必要条件
qr
l
i 1
ห้องสมุดไป่ตู้
r
i
1
q r
N
l
4.2 定长码及定长编码定理
定长编码的信息传输效率是很低的。提高信息传输效率的方 法有： 方法1 考虑符号之间的依赖关系，对信源S的扩展信源 进行编码。 方法2对于概率等于0或非常小的符号序列不予编码。 定理4.2 离散无记忆信源的熵为H(S)，若对信源长为N的序 列进行定长编码，码符号集X中有r个码符号，码长为l，则 对于任意 0 ，只要满足 l log r
4.1.1 编码器
码字的集合C称为码，即 C {w1, w2 , , wq } 。信源符号 si 对应 li 称为码字长度，简称码长。 的码字wi 包含li 个码符号， 所以，信源编码就是把信源符号序列变换到码符号序列的一 种映射。 若要实现无失真编码，那么这种映射必须是一一 对应的、可逆的。 一般来说，人们总是希望把信源所有的 信息毫无保留地传递到接收端，即实现无失真传递，所以首 先要对信源实现无失真编码。
即时码与非即时码
定义4.4 无需考虑后续的码符号就可以从码符号序列中 译出码字，这样的唯一可译码称为即时码。 （1,10,100,1000），（1,01,001,0001）
4.1.2 码的分类
下面讨论唯一可译码成为即时码的条件。 定义4.5 设 wi xi , xi xi 为一码字，对于任意的 1 j l ， 称码符号序列的前j个元素 xi , xi xi 为码字的前缀。 按照上述的前缀的定义，有下述结论：
第4章 无失真信源编码
重庆交通大学信息科学与工程学院 通信工程系 黄大荣
1
第4章 无失真信源编码
信源编码的任务：减少冗余，提高编码效率。 信源编码的基本途径：解除相关性；概率均匀化 4.1 信源编码的相关概念 4.2 定长码及定长编码定理 4.3 变长码及变长编码定理 4.4 变长码的编码方法 4.5 实用的无失真信源码方法
图4.1
信源编码器
4.1.1 编码器
信源编码有以下3种主要方法： 匹配编码 根据信源符号的概率不同，编码的码长不同：概率大的
信源符号，所编的代码短；概率小的信源符号所编的代码长，这样 使平均码长最短。这类编码主要有香农编码、哈夫曼编码、费诺码 都是概率匹配编码，都是无失真信源编码。
变换编码 先对信号进行变换，从一种信号空间变换为另一种信
1 2 l
1 2 l
定理4.1 一个唯一可译码成为即时码
的充要条件是其中任何一个码字都不是 其他码字的前缀。 即时码可以用树图来构造．图5.2是一个 二元即时码的树图．
图5.2 二元即时码的树图
4.1.2 码的分类
树是没有回路的图，所以它也是由节点和弧构成的．树中最 顶部的节点称为根节点，没有子节点的节点称为叶子节点。 所有根节点的子节点称为一阶节点，所有一阶节点的子节点 n 阶节点最多有r n 个。节点的阶 称为二阶节点，依此类推。 次又称为节点的深度。 综上所述，可将信源编码作如下分类：