文档介绍：第5章信源编码
香农编码
费诺编码
哈夫曼编码
游程(长度)编码
冗余位编码
算术编码
1
[引言]
编码
有效性——信源编码
目的——优化通信系统可靠性——信道编码
安全性——保密密码
信源编码:目的——提高通信有效性
方法——压缩信源冗余度
信道编码:目的——提高通信可靠性
方法——增加信源冗余度,增大码率
保密密码: 目的——提高通信安全性
方法——加密(增熵),解密(减熵)
2
[引言](续)
2. 信源编码
(1) 理论基础
无失真信源编码定理:离散信源或数字信号编码基础
限失真信源编码定理:连续信源或模拟信号编码基础
(2)分类
[本章介绍]
无失真离散信源编码
变长码(平均码长最短,有效性最高)
离散信源编码——无失真编码
连续信源编码—限失真编码,如:PCM,矢量量化
相关信源编码
预测编码—如DPCM,ADPCM
变换编码—如K-L变换,离散变换
3
香农编码
最佳编码——凡是能载荷一定信息量,
平均码长最短,
可分离的,
变长码的码集
可分离——接收端能分开(即时码)
关键——平均码长最短
大概率——短码
小概率——长码
码长~信源统计特性——匹配
[例]香农编码,费诺编码,哈夫曼编码
4
香农编码(续)
一、编码步骤
:p(x1) ≥ p(x2) ≥…≥ p(xn)
2. 确定的码长ki(整数):-log2p(xi)≤ki<1-log2p(xi)
(之前)的累加概率pa(xj)
[说明]
j=1时, pa(x1) = p(x0) =0
j=2时, pa(x2) = p(x1) + p(x0) = p(x1)
j=3时, pa(x3) = p(x2) + p(x1)
因而pa(xj)表示:xj之前(不含xj)的各概率之和
pa(xj)变为二进制数,
并取其小数点后ki位,即为xi的编码
5
香农编码(续)
二、[]()
[说明]
(1) 符合“大概率用短码”规律
(2) 平均码长
(3) 信息率
∵L=1(单符号),m=2 (二进制)
(4) 编码效率
(5) 码树
00
01
100
101
1101
11110
6
费诺编码
一、步骤
:p(x1) ≥ p(x2) ≥…≥ p(xn)
所有概率分为两组(m进制,为m组)
并使各组概率和接近或相等
然后对每组赋值0,1(m进制,为0,1,…,m-1)
(赋值可相反,但此后不变)
,并赋值(同2)….
直到每组只有一个信源符号为止
,即得码字
7
费诺编码(续)
二、[]()
[说明]
(1) 符合“大概率用短码”规律
(2) 平均码长
(3) 信息率
(4) 编码效率
∵H(X) =
∴= %
(5) 码树
00
01
10
110
1110
1111
8
哈夫曼编码
一、二进制哈夫曼编码
(1) 信源符号排序:p(x1) ≥ p(x2) ≥…≥ p(xn)
(2) 取两个最小的概率,分别赋以“0”,“1”
(也可相反,但此后不变)
然后把这两个概率值相加,作为新概率值
与其他概率重新排序
(3) 按重排概率值,重复(2)…,
直到概率和达到1为止
(4) 由后向前排列码序,即得哈夫曼编码
9
哈夫曼编码(续)
2. [] (1) 编码
01
01
01
01
01
01
01
0100 x5
0101 x6
00010 x7
00011 x8
011 x3
0000 x4
001 x2
1 x1
1
001
011
0101
0100
0000
00010
00011
10