信 源 编 码一、编码的意义
1、信源编码的目的；
2、编码的实质；
3、信源编码的基本思想；
信源编码的目的
提高信息传输的有效性；
将模拟信号转换为数字信号；
编码的实质
对信源的原始符号按一定的数学规则进行的一种可逆变换；
编码器信源 码字
M={m1,m2,…,m n} C={C1,C2,…,C n}符号集 A={a1,a2,…,a r}
编码器输入：信源符号 M = {m1,m2,…,m n}；
码符号（码元）：符号集 A={a1,a2,…,a r},一般元素 ai 是适合信道传输的；
编码器：将信源符号 mi 变换成由 aj (j=1,2,…,r) 组成的长度为 li 的一一对应的序列，即：
mi(i=1,2,…,m) => C i=(aj1,aj2,…,a jli)
这种码符号序列 Ci 称为码字，其长度 li 称为码字长度（码长），
所有这些码字的集合 C 称为码。
信源编码的基本思想
信源编码提高信息传输有效性的基本思想，
就是针对信源输出符号序列的统计特性，通过概率匹配的编码方法，将出现概率大的信源符号尽可能编为短码，从而使信源输出的符号序列变换为最短的码字序列。
二、编码定义
1、非奇异码和奇异码
2、等长码和变长码
3、单义码和非单义码
4、非续长码
5、码树
6、码字平均长度
7、编码效率非奇异码和奇异码
如果码中所有的码字都不相同，称为非奇异码，反之，则为奇异码；
等长码和变长码
码中各个码字都是由同样多个码元构成的，
称为等长码，反之，称为变长码；
单义码和非单义码
如果由码 C 的一组码字构成的任意长码序列，
只能有唯一的方式分割成若干前后连接的码字，叫单义码，反之，为非单义码；
例,
C1 = (1,01,00) 是单义码，如码字序列
10001101只可唯一划分为 1,00,01,1、
01;
C2 = (0,10,01) 为非单义码，如序列 01001
可划分为 0,10,01或 01,0,01。
非续长码
设 Ci={xi1,xi2,…,xim} 是码 C 中的任一码字，而其他码字
Ck={xk1,xk2,…,xkj} (j < m) 都不是码字 Ci 的前缀，则称此码为非续长码，也称为即时码。
非续长码一定是单义码；反之，单义码不一定都是非续长码。
例：对某个信源符号集合按照下面两种方式编码，试分析其异同。 信源符号 码 1 码 2
S1 1 1
S2 10 01
S3 100 001
S4 1000 0001
非续长码例子
相同点：码 1、码 2都是单义码；
不同点：
码 2中，每个码字都以,1”为终端，这样在接收过程中，只要一出现,1”时，就知道这是一个码字已经终结，新的码字就要开始，
因此当出现,1”后，就可以立即将收到的码元序列译成对应的信源符号；
码 1中，当收到一个或几个码元符号后，不能即时判断码字是否已经终结，必须等待下一个或几个码元符号收到后，才能作出判断。
例：码 1组成的序列,1000100101
码 2组成的序列,0001011001
结论：码 1是续长码，码 2是非续长码。这两种码的结构有重要区别。非续长码的性能要好于续长码。
码树
对给定的码字的全体集合 C={C1,C2,…,Cn}来说，可以用树来描述它。
码树的构造：对一棵树，给每个节点所伸出的枝分别标上码元符号 0,1,…,r-1,这样，
叶节点所对应的码字就是从根出发到叶节点经过的路径所对应的码元符号组成。
按树图法构成的码一定满足非续长码的充要条件，因为从根到叶所走的路径各不相同，
而且中间节点不安排为码字，所以一定满足对前缀的限制。
码树的例子该树的 5个叶节点 S1,S2,S3,S4,S5 分别表示 5 个二进制码字 0,100,111,1010,1011；
1
0
0
0
0
1
11
1S3
S1
S2
S4S5
码字平均长度
码字平均长度,设 N 个码字中的第 I 个码字的码长为 ni,它所代表的编码对象 xi 的出现的概率为 p(xi),则码字的平均长度为
i
N
i i
nxpL?
1
)(
编码效率
编码效率用最小平均码字长度 Lmin 和实际的编码平均长度 L 之比来表示；
当编码对象的平均信息量为 H(X),编码所用的符号数目为 D 时，有
D
XHL
lo g
)(
m in?
因此,编码效率为,DL XHLL lo g )(m in
剩余度为, 1R
例子已知信源符号集合的概率分布为
}
8
1,
8
1,
4
1,
2
1{)(
},,,{ 4321
XP
xxxxX
则 H(X) = 1.75 bits/符号如采用 2bit 等长编码 (如 x1— >00,x2— >01,x3— >10,
x4— >11),则 L = 2,η= 1.75/(2*log2) = 0.875；
如按照概率匹配原则编成如下非续长码：
x1— >0,x2— >10,x3— >110,x4— >111,
则 L = (1/2)*1+(1/4)*2+(1/8)*3+(1/8)*3=1.75,
η= 1.75/(1.75*log2) = 1；
三、非续长码存在定理
存在 N 个长度为 n1,n2,…,nN的非续长码字的充要条件为其中 D为编码符号的数目,N为码字的数目，
n1,n2,…,nN 为码字 C1,C2,… CN 分别对应的码长。
定理证明；
该定理给出了非续长码的存在性，但并未指出如何构造；
不等式 K r a f tDNi n i1 1
例子
14522222 22214 1i n i
1161522222 43214 1i n i
在码长 n1=1,n2=n3=n4=2 的条件下，一定不能构成非续长码，因为对于码长 n1=1,n2=2,n3=3,n4=4 的码可以有很多种，但可能构成的许多种码中至少可以找到一种是非续长的，因为信源符号 码 1 码 2
S1 1 1
S2 10 01
S3 00 001
S4 01 0001
例：
四、平均编码长度
设 X表示离散信源，其消息 Xi (i=1,2,…,N) 的出现概率为 p(xi),如将它用符号集 {a1,a2,…,aD}编成单义码，则码字平均长度 L满足不等式：
此外，存在 D元唯一可译码，其平均编码长度 L满足：
该定理给出了无失真编码的性能的极限。
编码符号的传信能力信源熵
N
i
ii D
XHnxpL
1 l o g
)()(
1l o g )()(
1
N
i ii D
XHnxpL
五、最佳编码方法
1、最佳编码定义
2、先农 -范诺编码方法
3、霍夫曼编码方法最佳码
对于某一个信源和某一码符号集来说，若有唯一可译码，其平均编码长度小于所有其他唯一可译码的平均编码长度，则该码为最佳码。
先农 -范诺编码方法
编码对象：离散信源概率集合
编码方法（对二元系统）
按概率递减的方式将消息及其概率排列起来；
将消息分成概率尽可能相同的两个子集，两个子集分别冠以码元符号,1”和,0”。
将每个子集再划分为概率尽可能相等的两个子集，并分别冠以 10,11和 00,01，依此类推，
直到子集只包括一个消息为止。
},.,,,,{)(
},.,,,,{
21
21
n
n
pppXP
xxxX
例子
将下列消息按二元先农 -范诺方法编码（如下页）
编码后可以计算得到：
}06 25.0,06 25.0,12 5.0,25.0,06 25.0,06 25.0,25.0,12 5.0{)(
},,,,,,,{ 87654321
XP
xxxxxxxxX
1
lo g
75.2)(
/75.2)(lo g)(
8
1
8
1
DL
H
nxpL
xpxpH
i
ii
i
ii
消息比特
X2
x5
x1
x6
x3
x4
x7
x8
0.25
0.25
0.125
0.125
0.0625
0.0625
0.0625
0.0625
0
1
00
01
10
11
110
111
100
101
1100
1101
1110
1111
00
01
100
101
1100
1101
1110
1111
消息 概率 编码 码字主要问题
当消息数目很多，而其概率又各不相同时，
如何把一个消息集逐次划分为概率尽可能相同的两个或多个子集。
该方法不能保证概率大的消息一定比概率小的消息能用较短的码字。
霍夫曼编码方法
编码对象：离散信源概率集合
},...,,{)(
},...,,{
21
21
n
n
pppXP
xxxX
编码方法（对二元系统）
将 N个信源符号按概率递减的方式排列起来；
用,0”，,1”码符号分别表示概率最小的两个信源符号，
并将这两个概率最小的信源符号合并成一个符号，从而得到只包含 N-1个符号的新信源，称为 S信源的缩减信源 S1；
将缩减信源 S1的符号仍按概率大小以递减次序排列，再将其最后两个概率最小的符号合并成一个符号，并分别用 0，
1码符号表示，这样又形成了 N-2个符号的缩减信源 S2；
依次继续下去，直到信源最后只剩下两个符号为止，将这最后两个符号分别用 0,1码符号表示，然后从最后一级缩减信源开始，向前返回，就得出各信源符号所对应的码符号序列，即得出对应的码字。
例子
将下列消息按二元霍夫曼方法编码编码后可以计算得到：
}01.0,1.0,15.0,17.0,18.0,19.0,2.0{)(
},,,,,,{ 7654321
XP
xxxxxxxX
96.0
lo g
72.2)(
/61.2)(lo g)(
7
1
7
1
DL
H
nxpL
xpxpH
i
ii
i
ii
消息比特
X1 0.20
x2 0.19
x3 0.18
x4 0.17
x5 0.15
x6 0.10
x7 0.01
S S1
1
0 0.11
1
0
0.26
S2
1
0
0.35
1
0
0.39
1
0 0.61
1
0
1.00
S3 S4 S5
11
10
011
010
001
0001
0000
码方差
码方差定义
δ2 = E[ (ni-L)2 ] = ∑p(xi)(ni-L)2
对信源进行缩减时，若两个概率最小的符号合并后的概率与其他信源符号的概率相同时，这两者在缩减信源中进行概率排序，其位置次序可以是任意的，
这种情况将影响码字的长度；
在进行编码时，为了得到码方差最小的码，应使合并的信源符号位于缩减信源序列尽可能高的位置上，
以减少再次合并的次数，充分利用短码；
码方差例子
设离散无记忆信源如下，分别按如下两种方式编码，分析哪种编码更好。
1.01.02.02.04.0
54321 xxxxx
P
X
Huffman编码 1
x1
x2
x3
x4
x5
0.2
0.2
0.2
0.4 0.4
0.4
0.2
0.6
0.4
1
0
1
0
1
0
1
0
1
1
01
000
0010
0011
信源符号 码字
Huffman编码 2
x1
x2
x3
x4
x5
1
0
1
00
10
11
010
011
信源符号 码字
0.2
0.2
0.2
0
1
0.4
0.2
0.4
1
0
0.4 0.6
0.4
0
1
编码 1,2的分析比较
这两种编码的平均码长和编码效率相同，分别为：
L=2.2 ; η=0.965
但它们的码方差不同。
对于方法 1,δ2=1.36,
对于方法 2,δ2=0.16
可见方法 2的码方差小，因此编码质量好霍夫曼编码方法编码的特点
霍夫曼编码方法得到的编码不是唯一的
每次对信源缩减时，赋予信源最后两个概率最小的符号，
用 0和 1可以是任意的。但这不会影响码字的长度；
对信源进行缩减时，若两个概率最小的符号合并后的概率与其他信源符号的概率相同时，这两者在缩减信源中进行概率排序，其位置次序可以是任意的；
霍夫曼编码方法保证了概率大的符号对应于短码，
概率小的符号对应于长码，充分利用了短码；
霍夫曼编码方法缩减信源的最后两个码字总是最后一位不同，从而保证了编码结果是非续长码；
六、先农第一基本定理
设 S为无记忆离散信源，其熵为 H(X)，经过一容量为 C比特 /符号的无干扰信道传送。总有可能将信源输出编成码字，使它在信道中的传信率任意地接近于信道容量 C。
1、信源编码的目的；
2、编码的实质；
3、信源编码的基本思想；
信源编码的目的
提高信息传输的有效性；
将模拟信号转换为数字信号；
编码的实质
对信源的原始符号按一定的数学规则进行的一种可逆变换；
编码器信源 码字
M={m1,m2,…,m n} C={C1,C2,…,C n}符号集 A={a1,a2,…,a r}
编码器输入：信源符号 M = {m1,m2,…,m n}；
码符号（码元）：符号集 A={a1,a2,…,a r},一般元素 ai 是适合信道传输的；
编码器：将信源符号 mi 变换成由 aj (j=1,2,…,r) 组成的长度为 li 的一一对应的序列，即：
mi(i=1,2,…,m) => C i=(aj1,aj2,…,a jli)
这种码符号序列 Ci 称为码字，其长度 li 称为码字长度（码长），
所有这些码字的集合 C 称为码。
信源编码的基本思想
信源编码提高信息传输有效性的基本思想，
就是针对信源输出符号序列的统计特性，通过概率匹配的编码方法，将出现概率大的信源符号尽可能编为短码，从而使信源输出的符号序列变换为最短的码字序列。
二、编码定义
1、非奇异码和奇异码
2、等长码和变长码
3、单义码和非单义码
4、非续长码
5、码树
6、码字平均长度
7、编码效率非奇异码和奇异码
如果码中所有的码字都不相同，称为非奇异码，反之，则为奇异码；
等长码和变长码
码中各个码字都是由同样多个码元构成的，
称为等长码，反之，称为变长码；
单义码和非单义码
如果由码 C 的一组码字构成的任意长码序列，
只能有唯一的方式分割成若干前后连接的码字，叫单义码，反之，为非单义码；
例,
C1 = (1,01,00) 是单义码，如码字序列
10001101只可唯一划分为 1,00,01,1、
01;
C2 = (0,10,01) 为非单义码，如序列 01001
可划分为 0,10,01或 01,0,01。
非续长码
设 Ci={xi1,xi2,…,xim} 是码 C 中的任一码字，而其他码字
Ck={xk1,xk2,…,xkj} (j < m) 都不是码字 Ci 的前缀，则称此码为非续长码，也称为即时码。
非续长码一定是单义码；反之，单义码不一定都是非续长码。
例：对某个信源符号集合按照下面两种方式编码，试分析其异同。 信源符号 码 1 码 2
S1 1 1
S2 10 01
S3 100 001
S4 1000 0001
非续长码例子
相同点：码 1、码 2都是单义码；
不同点：
码 2中，每个码字都以,1”为终端，这样在接收过程中，只要一出现,1”时，就知道这是一个码字已经终结，新的码字就要开始，
因此当出现,1”后，就可以立即将收到的码元序列译成对应的信源符号；
码 1中，当收到一个或几个码元符号后，不能即时判断码字是否已经终结，必须等待下一个或几个码元符号收到后，才能作出判断。
例：码 1组成的序列,1000100101
码 2组成的序列,0001011001
结论：码 1是续长码，码 2是非续长码。这两种码的结构有重要区别。非续长码的性能要好于续长码。
码树
对给定的码字的全体集合 C={C1,C2,…,Cn}来说，可以用树来描述它。
码树的构造：对一棵树，给每个节点所伸出的枝分别标上码元符号 0,1,…,r-1,这样，
叶节点所对应的码字就是从根出发到叶节点经过的路径所对应的码元符号组成。
按树图法构成的码一定满足非续长码的充要条件，因为从根到叶所走的路径各不相同，
而且中间节点不安排为码字，所以一定满足对前缀的限制。
码树的例子该树的 5个叶节点 S1,S2,S3,S4,S5 分别表示 5 个二进制码字 0,100,111,1010,1011；
1
0
0
0
0
1
11
1S3
S1
S2
S4S5
码字平均长度
码字平均长度,设 N 个码字中的第 I 个码字的码长为 ni,它所代表的编码对象 xi 的出现的概率为 p(xi),则码字的平均长度为
i
N
i i
nxpL?
1
)(
编码效率
编码效率用最小平均码字长度 Lmin 和实际的编码平均长度 L 之比来表示；
当编码对象的平均信息量为 H(X),编码所用的符号数目为 D 时，有
D
XHL
lo g
)(
m in?
因此,编码效率为,DL XHLL lo g )(m in
剩余度为, 1R
例子已知信源符号集合的概率分布为
}
8
1,
8
1,
4
1,
2
1{)(
},,,{ 4321
XP
xxxxX
则 H(X) = 1.75 bits/符号如采用 2bit 等长编码 (如 x1— >00,x2— >01,x3— >10,
x4— >11),则 L = 2,η= 1.75/(2*log2) = 0.875；
如按照概率匹配原则编成如下非续长码：
x1— >0,x2— >10,x3— >110,x4— >111,
则 L = (1/2)*1+(1/4)*2+(1/8)*3+(1/8)*3=1.75,
η= 1.75/(1.75*log2) = 1；
三、非续长码存在定理
存在 N 个长度为 n1,n2,…,nN的非续长码字的充要条件为其中 D为编码符号的数目,N为码字的数目，
n1,n2,…,nN 为码字 C1,C2,… CN 分别对应的码长。
定理证明；
该定理给出了非续长码的存在性，但并未指出如何构造；
不等式 K r a f tDNi n i1 1
例子
14522222 22214 1i n i
1161522222 43214 1i n i
在码长 n1=1,n2=n3=n4=2 的条件下，一定不能构成非续长码，因为对于码长 n1=1,n2=2,n3=3,n4=4 的码可以有很多种，但可能构成的许多种码中至少可以找到一种是非续长的，因为信源符号 码 1 码 2
S1 1 1
S2 10 01
S3 00 001
S4 01 0001
例：
四、平均编码长度
设 X表示离散信源，其消息 Xi (i=1,2,…,N) 的出现概率为 p(xi),如将它用符号集 {a1,a2,…,aD}编成单义码，则码字平均长度 L满足不等式：
此外，存在 D元唯一可译码，其平均编码长度 L满足：
该定理给出了无失真编码的性能的极限。
编码符号的传信能力信源熵
N
i
ii D
XHnxpL
1 l o g
)()(
1l o g )()(
1
N
i ii D
XHnxpL
五、最佳编码方法
1、最佳编码定义
2、先农 -范诺编码方法
3、霍夫曼编码方法最佳码
对于某一个信源和某一码符号集来说，若有唯一可译码，其平均编码长度小于所有其他唯一可译码的平均编码长度，则该码为最佳码。
先农 -范诺编码方法
编码对象：离散信源概率集合
编码方法（对二元系统）
按概率递减的方式将消息及其概率排列起来；
将消息分成概率尽可能相同的两个子集，两个子集分别冠以码元符号,1”和,0”。
将每个子集再划分为概率尽可能相等的两个子集，并分别冠以 10,11和 00,01，依此类推，
直到子集只包括一个消息为止。
},.,,,,{)(
},.,,,,{
21
21
n
n
pppXP
xxxX
例子
将下列消息按二元先农 -范诺方法编码（如下页）
编码后可以计算得到：
}06 25.0,06 25.0,12 5.0,25.0,06 25.0,06 25.0,25.0,12 5.0{)(
},,,,,,,{ 87654321
XP
xxxxxxxxX
1
lo g
75.2)(
/75.2)(lo g)(
8
1
8
1
DL
H
nxpL
xpxpH
i
ii
i
ii
消息比特
X2
x5
x1
x6
x3
x4
x7
x8
0.25
0.25
0.125
0.125
0.0625
0.0625
0.0625
0.0625
0
1
00
01
10
11
110
111
100
101
1100
1101
1110
1111
00
01
100
101
1100
1101
1110
1111
消息 概率 编码 码字主要问题
当消息数目很多，而其概率又各不相同时，
如何把一个消息集逐次划分为概率尽可能相同的两个或多个子集。
该方法不能保证概率大的消息一定比概率小的消息能用较短的码字。
霍夫曼编码方法
编码对象：离散信源概率集合
},...,,{)(
},...,,{
21
21
n
n
pppXP
xxxX
编码方法（对二元系统）
将 N个信源符号按概率递减的方式排列起来；
用,0”，,1”码符号分别表示概率最小的两个信源符号，
并将这两个概率最小的信源符号合并成一个符号，从而得到只包含 N-1个符号的新信源，称为 S信源的缩减信源 S1；
将缩减信源 S1的符号仍按概率大小以递减次序排列，再将其最后两个概率最小的符号合并成一个符号，并分别用 0，
1码符号表示，这样又形成了 N-2个符号的缩减信源 S2；
依次继续下去，直到信源最后只剩下两个符号为止，将这最后两个符号分别用 0,1码符号表示，然后从最后一级缩减信源开始，向前返回，就得出各信源符号所对应的码符号序列，即得出对应的码字。
例子
将下列消息按二元霍夫曼方法编码编码后可以计算得到：
}01.0,1.0,15.0,17.0,18.0,19.0,2.0{)(
},,,,,,{ 7654321
XP
xxxxxxxX
96.0
lo g
72.2)(
/61.2)(lo g)(
7
1
7
1
DL
H
nxpL
xpxpH
i
ii
i
ii
消息比特
X1 0.20
x2 0.19
x3 0.18
x4 0.17
x5 0.15
x6 0.10
x7 0.01
S S1
1
0 0.11
1
0
0.26
S2
1
0
0.35
1
0
0.39
1
0 0.61
1
0
1.00
S3 S4 S5
11
10
011
010
001
0001
0000
码方差
码方差定义
δ2 = E[ (ni-L)2 ] = ∑p(xi)(ni-L)2
对信源进行缩减时，若两个概率最小的符号合并后的概率与其他信源符号的概率相同时，这两者在缩减信源中进行概率排序，其位置次序可以是任意的，
这种情况将影响码字的长度；
在进行编码时，为了得到码方差最小的码，应使合并的信源符号位于缩减信源序列尽可能高的位置上，
以减少再次合并的次数，充分利用短码；
码方差例子
设离散无记忆信源如下，分别按如下两种方式编码，分析哪种编码更好。
1.01.02.02.04.0
54321 xxxxx
P
X
Huffman编码 1
x1
x2
x3
x4
x5
0.2
0.2
0.2
0.4 0.4
0.4
0.2
0.6
0.4
1
0
1
0
1
0
1
0
1
1
01
000
0010
0011
信源符号 码字
Huffman编码 2
x1
x2
x3
x4
x5
1
0
1
00
10
11
010
011
信源符号 码字
0.2
0.2
0.2
0
1
0.4
0.2
0.4
1
0
0.4 0.6
0.4
0
1
编码 1,2的分析比较
这两种编码的平均码长和编码效率相同，分别为：
L=2.2 ; η=0.965
但它们的码方差不同。
对于方法 1,δ2=1.36,
对于方法 2,δ2=0.16
可见方法 2的码方差小，因此编码质量好霍夫曼编码方法编码的特点
霍夫曼编码方法得到的编码不是唯一的
每次对信源缩减时，赋予信源最后两个概率最小的符号，
用 0和 1可以是任意的。但这不会影响码字的长度；
对信源进行缩减时，若两个概率最小的符号合并后的概率与其他信源符号的概率相同时，这两者在缩减信源中进行概率排序，其位置次序可以是任意的；
霍夫曼编码方法保证了概率大的符号对应于短码，
概率小的符号对应于长码，充分利用了短码；
霍夫曼编码方法缩减信源的最后两个码字总是最后一位不同，从而保证了编码结果是非续长码；
六、先农第一基本定理
设 S为无记忆离散信源，其熵为 H(X)，经过一容量为 C比特 /符号的无干扰信道传送。总有可能将信源输出编成码字，使它在信道中的传信率任意地接近于信道容量 C。
