1
1 绪论
• 信息的概念
• 信息的定义与性质
• 信息的分类
• 信息传输系统的组成及功能
• 模拟信息传输系统
• 数字信息传输系统
• 信息论研究对象和内容
• 信息论发展简史
2
信息的定义与性质
• 古时的通信：烽火台
• 信息传播五阶段：
• 手势和语言——文字——印刷术——电磁波——
计算机和通信
• 微电子技术、通信技术和计算机技术促进了信息
技术发展。
• 信息产业的发展促进了社会产业结构的变化与发
展。
3
信息的定义与性质
• 信息：认识主体所感受的或所表达的事物的运动
状态和运动状态的变化方式。
• （1）信息是普遍存在的。
• （2）信息与物质。
• （3）信息与能量。
• （4）人类认识事物，变革事物必须要有信息。
• 信息载体：运载信息的物质。
4
信息的定义与性质
• 消息：以文字、语音、图像等这些能够为
人们的感觉器官所感知的物理现象，把客
观物质运动和主观思维活动的状态表达出
来就成为消息。
信号：消息的表现形式和载体。同一信息
可用不同的信号来表示，同一信号也可表
达不同的信息。
5
信息的定义与性质
• 信息——十分抽象而又复杂的概念，是人
们对客观事物感触到的新认识。
• 消息——信息的载荷者，是描述信息的一
种表现形式，是对某个事物的描述和反应。
• 信号——运载或携带消息的任何物理量，
达到迅速有效地传递和交换信息的目的。
6
信息的定义与性质
• 性质：
• （1）普遍性：信息是普遍存在的。
• （2）无限性：信息是无限的。
• （3）相对性：对同一事物不同的观察者所获得的
信息量可能不同。
（4）转换性：信息可以在时间上或空间中从
一点转移到另一点。
（5）变换性：信息是可变的，它可以由不同
的载体或不同的方法来载荷。
7
信息的定义与性质
• （6）有序性：信息可以用来消除系统的不定性，
增加系统的有序性。
• （7）动态性：信息具有动态性质，一切活的信息
都随时间变化，具有时效性。
• （8）转化性：在一定条件下，信息可以转化为物
质、能量、时间等。
（9）共享性：同一信息可以被无限的人所获
得，可以交流而不会减少。
（10）可量度性：信息的数量与质量是可量度
的即信息量。
8
信息的分类
• （1）从性质分：语法信息、语义信息、
语用信息。
随机方式
模糊状态 半随机方式
确定型方式（模糊信息）连续状态
离散状态
无限状态
有限状态 随机方式（概率信息）
明晰状态 半随机方式（偶发信息）
确定型方式（确定信息）
语
法
信
息
9
信息的分类
• 举例说明，两个布袋中装有对人手感觉完
全一样的球，但颜色和数量不同，
• （1）50个红球和50个白球
• （2）红球、白球、黑球、黄球各25个
• 随意拿出一个球，被告知是红球所获得的
信息量。
10
信息的分类
• （2）按观察的过程分：实在信息、先验信息、实得信息。
• （3）按信息的地位分：客观信息、主观信息。
• （4）按作用分：有用信息、无用信息、干扰信息。
（5）按逻辑意义分：真实信息、虚假信息、
不定信息。
（6）按传递方向分：前馈信息、反馈信息。
11
信息的分类
• （7）按生成领域分：宇宙信息、自然信息、社会信息、
思维信息等。
• （8）按应用部门分：工业信息、农业信息、军事信息、
政治信息、科技信息、文化信息等。
（9）按信息源的性质分：语声信息、图像信息、文
字信息、数据信息、计算信息等。
（10）按载体性质分：电子信息、光学信息、生物信
息等。
（11）按携带信息的信号形式分：连续信息、离散信
息、半连续信息等。
12
模拟信息传输系统
• 该系统传递的是模拟信号，它在任意时刻
的取值是任意的，是时间的连续函数。基
本模型如图 所示：
信
息
源
噪声源
变
换
器
调
制
器
发
射
机
信道
接
收
机
解
调
器
反
变
换
器
信
息
宿
接收端发送端 信道
模拟信息传输系统的一般模型
13
模拟信息传输系统
• 信息源：产生含有信息的消息，是被传输
的对象。
• 信息宿：信息传送的目的地，即原消息的
归宿或接受者。
14
模拟信息传输系统
• 变换器：将非电量变换成宜于远距离传输
的电信号。
• 反变换器：将信息信号恢复成原消息。
15
模拟信息传输系统
• 调制器：将频率较低的信号调制到频率更
高的载波信号上。(调制方式有调幅AM、调
频FM、调相、单边带调制SSB等)。
解调器：从已调的高频载波信号中解调
出被传输的低频信息信号。
16
模拟信息传输系统
• 发射机：变频器和功率放大器，使已调载
波信号的频率和功率达到实际应用所要求
的数值。
接收机：低噪声高频放大器、混频器、中
频放大器，将微弱信号放大到解调器所需
强度的信号，并最大限度地降低信道噪声
的影响。
17
模拟信息传输系统
• 信道：消息的信号从发射端传到接受端的
媒质或通道。（有线信道：架空明线、同
轴电缆、波导、光纤等；无线信道：无线
电波、激光自由空间传播等）
噪声源：实际传输系统中客观存在的干扰
源，有内部噪声和外部干扰两方面。
18
数字信息传输系统
• 该系统中传输的是数字信号，它只能取有
限个离散值，且出现的时间也是离散的。
基本模型如图 所示：
信
息
源
噪声源
变
换
器
调
制
器
发
射
机
信道
接
收
机
解
调
器
反
变
换
器
信
息
宿
接收端发送端 信道
数字信息传输系统的一般模型
信
源
编
码
器
信
道
编
码
器
信
道
译
码
器
信
源
译
码
器
19
数字信息传输系统
• 调制方式有幅度键控ASK、频移键控FSK、
相移键控PSK等。
信源编码器：模/数（A/D）变换器，将模拟信
号变换成数字信号。
信源译码器：数/模（D/A）变换器，将数字信
号变换成模拟信号。
信道编译码器：提高传输系统的抗干扰能力。
20
数字信息传输系统
• 优点：
• （1）抗干扰能力强，特别在中继传输中尤为
明显。
• （2）可以进行差错控制，提高了信息传输的
灵活性。
（3）便于使用现代计算机技术对信号进行处
理、存储和变换。
（4）便于加密，实现保密信息传输。
21
数字信息传输系统
• （5）易于与其他系统配合使用，构成综合
业务信息传输网。
• （6）易于集成化和大规模生产，性能一致
性好且成本低。
缺点：
（1）占用信道频带较宽。
（2）要有一个复杂的同步系统。
22
信息论研究对象和内容
• 研究对象：消息传输系统即信息传输系统，
通信系统。
研究目的：提高通信系统的可靠性和有效性。
（1）可靠性高：使信源发出的消息经过传输后尽
可能准确地不失真地再现在接收端。
（2）有效性高：经济效果好，用尽可能短的时间
和尽可能少的设备传送一定数量的信息。
23
信息论研究对象和内容
• 研究内容：
• （1）通信的统计理论的研究。
• （2）信源的统计特性的研究。
• （3）收信者接受器官的研究。
（4）编码理论与技术。
（5）如何提高信息传输效率。
（6）抗干扰理论与技术。
（7）噪声中信号检测理论与技术。
24
信息论研究对象和内容
• 信息论的三个层次：
• （1）信息论基础（狭义信息论）：主要研究信息的测度、
信道容量、信源和信道编码理论等问题。
（2）一般信息论：主要研究信息传输和处理问题，除
香农理论外，还包括噪声理论、信号滤波和预测、统计
检测与估计理论、调制理论以及信息处理理论等。
（3）广义信息论：不仅包括上述两方面内容，还包括
与信息有关的领域，如心理学、遗传学、神经生理学、
语言学、语义学等。
25
信息论发展简史
• 电信系统的发展：
• 电磁理论和电子学理论的发展促进了电信系统
的创造发明或改进。
• 1823年-1835年，莫尔斯建立了电报系统。
• 1876年，贝尔发明了电话系统。
1895年，马可尼和波波夫发明了无线电通信。
1925年-1927年，建立起电视系统。
二次大战初期，微波通信系统和微波雷达系统迅速发展
起来。
20世纪60年代，人类进入光纤通信时代。
26
信息论发展简史
• 信息理论的发展：
• 1924年，奈奎斯特首先将信息率与信号带宽联系
起来。
• 1928年，哈特莱引入了非统计（等概率事件）信
息量概念。
20世纪40年代初期，维纳把随机过程和数理统
计的观点引入通信和控制系统中。
1948、1949年，香农用概率测度和数理统计的
方法，系统地讨论了通信的基本问题。
27
信息论发展简史
• 无失真信源编码的发展：
• （香农编码理论）惟一可译码——费诺码——哈
夫曼码（最佳码）——算术编码——LZ码（通用
信源编码）。
信道编码的发展：
纠错码——汉明码（代数编码）——卷积码
（概率编码）——并行极点卷积码。
28
2 信息的量度
• 自信息量和条件自信息量
• 互信息量和条件互信息量
• 离散集的平均自信息量
• 离散集的平均互信息量
• 例题
29
自信息量和条件自信息量
• 自信息量
• 条件自信息量
30
自信息量
• 信源发出的消息常常是随机的，其状态存
在某种程度的不确定性，经过通信将信息
传给了收信者，收信者得到消息后，才消
除了不确定性并获得了信息。
获得信息量的多少与信源的不确定性的
消除有关。
不确定度——惊讶度——信息量
31
自信息量
• （1）直观定义信息量为：
• 收到某消息获得的信息量=不确定性减少的
量=收到此消息前关于某事件发生的不确定
性-收到此消息后关于某事件发生的不确定
性
（2）无噪声时信息量为：
收到消息前获得的信息量=收到此消息前关
于某事件发生的不确定性=信源输出的某消息
中所含有的信息量
32
自信息量
• 举例说明，一个布袋中装有对人手感觉完
全一样的球，但颜色和数量不同，问下面
三种情况下随意拿出一个球的不确定程度
的大小。
• （1）99个红球和1个白球
• （2）50个红球和50个白球
• （3）红球、白球、黑球、黄球各25个
33
自信息量
• 事件发生的不确定性与事件发生的概率有
关，一般情况下，一个信源可以用一个概
率空间来描述，信源的不确定程度可以用
这个概率空间的可能状态数目及其概率来
描述。
34
自信息量
• 设信源X的概率空间为
• 其中：X是信源的状态空间，即随机事件的
状态数； 是随机事件可能状态的概率分
布，且 ，各状态是相互独立的。
• 通常记为
)()()()( 21
21
N
N
xpxpxp
xxx
xP
X
)(xP
1)( xP
)}(,{ xPX
35
自信息量
• 应用概率空间的概念分析上例，设取红球
的状态为x1，白球为x2，黑球为x3，黄球为
x4，则概率空间为：
• （1）
• （2）
• （3）
)(
21 xx
xP
X
)(
21 xx
xP
X
)(
4321 xxxx
xP
X
36
自信息量
• 结论：
• （1）不确定度与信源概率空间的状态数及
其概率分布有关。
（2）信源概率空间的概率分布为等概率
时不确定度最大。
（3）等概率时，不确定度与信源概率空
间的状态数或相应的概率有关。
37
自信息量
• 任意随机事件的自信息量定义为该事件发
生概率的对数的负值。若随机事件 出现的
概率为 ，那么它的自信息量为
• 通常取对数的底为2，单位为比特（bit）。
)( ixP
ix
)(
1
log)(log)(
i
ii
xP
xPxI
38
自信息量
• 三个单位间的转换关系为：
• 1奈特=log2e 比特
• 1哈特莱=log210 比特
• 自信息量非负且单调递减。
0 x1
log2x
f(x)
-log2x
0 x
1
f(x)
39
自信息量
• 例：某地的天气情况分布是：晴天占1/2，阴天占1/4，雨
天占1/8，雪天占1/8。求各种天气的自信息量。
• 解：设晴天、阴天、雨天、雪天的状态分别为x1,x2,x3,x4
bit
xP
xI
bit
xP
xI
bit
xP
xI
bit
xP
xI
38log
)(
1
log)(
38log
)(
1
log)(
24log
)(
1
log)(
12log
)(
1
log)(
4
4
3
3
2
2
1
1
40
自信息量
• 在二维联合集 上的元素 的联合自信
息量定义为
• 其中， 为元素 的二维联合概率。当
二者相互独立时 ，则
有 。元素 的不确定度
在数值上也等于他们的自信息量。
)(
1
log)(log)(
ji
jiji
yxP
yxPyxI
ji yxXY
)( ji yxP
)()()( jiji yPxPyxP
ji yx
)()()( jiji yIxIyxI ji yx
41
自信息量
• 例 在盒子中放入n个不同阻值的电阻，
随机取出一个并猜测阻值，概率空间为
• 其中xi代表阻值为 表示
取出电阻值为i 的电阻的概率。假定取出电
阻是等概率的，即
那么被告知取出阻值为i的电阻，所获得的
信息量为
)()()()( 21
21
n
n
xPxPxP
xxx
xP
X
)(,,,2,1 ixPni
,,,2,1,1)( ninxP i
nxPxI ii log)(log)(
42
自信息量
• 若盒中放入 个不同阻值的电阻，其中阻
值为1欧姆的1个，2欧姆的2个， n欧姆的n个。
概率空间为
• 其中xi代表阻值为 表示取出电
阻值为i 的电阻的概率。那么被告知取出阻值为i
的电阻，所获得的信息量为
2/)1(2/)1(
2
2/)1(
1
)(
21
nn
n
nnnn
xxx
xP
X
n
)(,,,2,1 ixPni
i
nn
xPxI ii
2
)1(
log)(log)(
2/)1( nn
43
条件自信息量
• 在联合集 对事件 ，设在条件 下，随
机事件 的条件概率为 ，那么其条件
自信息量定义为
• 三种自信息量的关系：
)|(
1
log)|(log)|(
ji
jiji
yxP
yxPyxI
ji yx ,XY
)|( ji yxPix
jy
)()(
)(1
1
)(
1
log
)(
)(
log
)|(
1
log)|(
jji
jji
ji
j
ji
ji
yIyxI
yPyxP
yxP
yP
yxP
yxI
44
条件自信息量
• 例 设在一正方形棋盘上共有64个方格，
如果甲将一粒棋子随机地放在棋盘中某方
格内让乙猜。
• （1）将方格按顺序编号，猜测顺序号；
（2）将方格按行和列编号并告知行或列编
号，猜测位置。
45
条件自信息量
• 解：由于棋子位置是二维等概率分布，故
• （1）在二维联合集 上的元素 的自信息量
为
• （2）在二维联合集 上，元素 相对 的条件
自信息量为
比特3
64/1
8/1
log
)(
)(
log)|(log)|(
ji
j
jiji
yxP
yP
yxPyxI
XY
64/1)( ji yxP
比特6
64
1
log)(log)( jiji yxPyxI
ji yx
jyixXY
46
互信息量和条件互信息量
• 互信息量
• 互信息量的性质
• 条件互信息量
47
互信息量
• （1）通常预先知道信源集合X的概率空间，
即
• 其中 为集合X中各个消
息的取值，概率 称为
先验概率。
)()()( 21
21
N
N
xPxPxP
xxx
P
X
Nixi ,,2,1,
NixP i ,,2,1),(
48
互信息量
),|( ji yxP
)()()( 21
21
M
M
yPyPyP
yyy
P
Y
Mjy j ,,2,1,
• （2）信宿收到的消息符号集合Y的概率空间为
• 其中 为集合Y中各个消息
的取值。当信宿收到集合Y中的一个符号消息
后，接收者重新估计关于信源各个消息Xi发生
的概率就成为条件概率 也称为后验概
率。
49
互信息量
• 对两个离散随机事件X和Y，事件 的出现给出关
于事件 的信息量定义为互信息量 ，即
)|()(
)|(
1
log
)(
1
log
)(
)|(
log);(
jii
jiii
ji
ji
yxIxI
yxPxPxP
yxP
yxI
);( ji yxIix
jy
互信息量定义为后验概率与先验概率比值的对
数，也等于自信息量减去条件自信息量。
当对数底分别为2、e、10时，互信息量的单位分
别为比特、奈特、哈特莱。
50
互信息量
• 例：当告知不是晴天时，某地的天气情况分
布是阴天占1/2，雨天占1/4，雪天占1/4。求不是
晴天时，获得的各种天气的互信息量。
• 解：设晴天、阴天、雨天、雪天的状态分别为
x1,x2,x3,x4。不是晴天的状态为y1
bit
xP
yxP
yxI
bit
xP
yxP
yxI
bit
xP
yxP
yxI
1
8/1
4/1
log
)(
)|(
log);(
1
8/1
4/1
log
)(
)|(
log);(
1
4/1
2/1
log
)(
)|(
log);(
4
14
14
3
13
13
2
12
12
51
互信息量
• 此时，各种天气的条件自信息量：
bit
yxP
yxI
bit
yxP
yxI
bit
yxP
yxI
24log
)|(
1
log)|(
24log
)|(
1
log)|(
12log
)|(
1
log)|(
14
14
13
13
12
12
52
互信息量的性质
• （1）互信息量的互易性——对称性
• 证：
);(
)(
)/(
log
)(
)(/)(
log
)(
)(
)(
)|(
log
)(
)|(
log);(
ij
j
ij
j
iji
i
j
j
ji
i
ji
ji
xyI
yP
xyP
yP
xPyxP
xP
yP
yP
yxP
xP
yxP
yxI
53
互信息量的性质
• （2）当事件xi和yj相互独立时，互信息量
为零。
• 证：由 得
01log
)()(
)()(
log
)()(
)(
log
)(
)|(
log);(
ji
ji
ji
ji
i
ji
ji
yPxP
yPxP
yPxP
yxP
xP
yxP
yxI
)()()( jiji yPxPyxP
54
互信息量的性质
• （3）互信息量可正可负
)|( ji yxP )( ixP
jy
ix
)|(
1
log
)(
1
log
)(
)|(
log);(
jiii
ji
ji
yxPxPxP
yxP
yxI
当后验概率 大于先验概率 时，
互信息量为正值，反之为负值。
互信息量为正意味着事件 的出现有助
于肯定事件 的出现，反之是不利的。
55
互信息量的性质
• （4）任何两个事件的互信息量不可能大于
其中任一事件的自信息量。
• 证：由于
• 故
)(
)(
1
log
)(
)|(
log);( i
ii
ji
ji xI
xPxP
yxP
yxI
)(
)(
1
log
)(
)|(
log);( j
jj
ij
ij yI
yPyP
xyP
xyI
1)|(,1)|( ijji xyPyxP
56
互信息量的性质
• 例 某人A预先知道他的三个朋友B、C、D中
有一人晚上到他家，且这三人来的可能性相同，
先验概率 P(B)= P(C)= P(D)=1/3 。
但上午A接到D的电话说不能来了，将这次
电话作为事件E，那么有后验概率
P(D|E)=0, P(B|E)= P(C|E)=1/2。
下午又接到C的电话说不能来，将此作为事
件F，则有P(C|EF)= P(D|EF)=0, P(B|EF)= 1。
57
互信息量的性质
• 在接到上午电话后，A获得关于B、C、D的互信
息量为
• 因为P(D|E)=0 ,故无需考虑事件D与事件E间的互
信息量。
• 在接到两次电话后，A获得关于B、C、D的互信
息量为
• 因为P(C|EF)= P(D|EF)=0,故无需考虑事件D与事
件E间的互信息量。
bit
BP
EBP
EBI
3/1
2/1
log
)(
)|(
log);(
bitEBIECI );();(
bit
BP
EFBP
EFBI
3/1
1
log
)(
)|(
log);(
58
条件互信息量
• 在联合集 ,在给定 的条件下， 之间
的互信息量。
• 在联合集 ,还存在 与 之间的互信息
量。
)|(
)|(
log)|;(
ki
kji
kji
zxP
zyxP
zyxI
ji yx ,XYZ
ix kj zy
kz
XYZ
)(
)|(
log);(
i
kji
kji
xP
zyxP
zyxI
)|;();(
)|(
)|(
log
)(
)|(
log
)|(
)|(
)(
)|(
log);(
jkiji
ji
kji
i
ji
ji
ji
i
kji
kji
yzxIyxI
yxP
zyxP
xP
yxP
yxP
yxP
xP
zyxP
zyxI
59
离散集的平均信息量
• 平均自信息量（熵）
• 熵函数的数学特性
• 条件熵
• 联合熵（共熵）
• 各种熵的性质
• 加权熵
60
平均自信息量（熵）
• 自信息量是一个随机变量，不能作为整个信源的
信息测度，故引入平均自信息量，即信息熵。
N
i
iiii xPxPxPExIEXH
1
)(log)()](log[)]([)(
信息熵H(X)是从整个信源的统计特性来考虑的，
是从平均意义上表征信源的总体特性。对某特定
的信源，其信息熵只有一个。
定义集X上，随机变量自信息I(xi)的数学期望
为平均自信息量H(X)即信息熵，简称熵。
61
平均自信息量（熵）
• 例 有一个布袋内放100个球，其中80
个红球，20个白球。随便摸一个球猜测是
什么颜色，求平均摸取一次获得的信息量。
• 解：设事件x1表示摸到红球，事件x2表示摸
到白球，则概率空间为
21 xx
P
X
62
平均自信息量（熵）
• 当告知摸出的是红球时，获得的信息量
• 当告知摸出的是白球时，获得的信息量
bitxPxI )(log)( 22
bitxPxI )(log)( 11
)()()()( 2211 xIxnPxIxnP
若每次摸出一个球后又放回去，进行第二次
摸取，那么摸取n次中，红球出现的次数为
nP(x1) ，白球出现的次数为nP(x2) 。则摸取n
次后获得的信息量为
63
平均自信息量（熵）
• 平均随机摸取一次所能获得的信息量为
2
1
2211
2211
)(log)(
)](log)()(log)([
)]()()()([
1
)(
i
ii xPxP
xPxPxPxP
xIxnPxIxnP
n
XH
64
平均自信息量（熵）
• 信息熵分别为
• 可见 H(Y)〉H(X)
符号比特/)( XH
符号比特/)( YH
例 比较两个信源
21 xx
P
X
21 yy
P
Y
65
平均自信息量（熵）
• 信息熵的三种物理含义：
• （1）表示信源输出后每个消息所提供的平
均信息量。
• （2）表示信源输出前信源的平均不确定性。
• （3）表征变量的随机性。
66
熵函数的数学特性
• 因为随机变量集的熵H(X)只是其概率分布
的函数，所以熵函数H(X)又可记为
i
q
i
iq PPPPPHPH log),,()(
1
21
1
1
q
i
iP由于概率的完备性 ， H(P)实际上
是(q-1)元函数。
如二元熵 H(P)=H[p,(1-p)]=H(p)。
67
熵函数的数学特性
• 设 为一多元函数，若对于
任意小于1的正数 以及函数定义域
内的任意两个矢量X1和X2有
• 则称f(X)为定义域上的上凸函数。
),,()( 21 nxxxfXf
)10(
)()1()(])1([ 2121 XfXfXXf
0 xx1 x2
f(x1)
f(x2)
f(x)
68
熵函数的数学特性
• （1）对称性
• 当概率矢量中的各个分量的次序任意互换时，熵函数的值
不变，即
• 例如两个信源
• 信息熵为
),,(),,(),,( 212321 qqqq PPPHPPPHPPPH
8/18/14/12/1
4321 xxxx
P
X
4/18/18/12/1
4321 yyyy
P
Y
8
2
4log
4
1
2log
2
1
)()( YHXH
69
熵函数的数学特性
• （2）非负性（离散信源）
• 等号成立的充要条件是当且仅当某Pi=1,其
余的 Pk=0 。这表明确定信源的熵
最小。
• 证：
0),,()( 21 qPPPHXH
0log10 ii PP
0log),,(
1
21
i
q
i
iq PPPPPH
)( ik
1
1
q
i
iP
)( ik
当每一项为零时等号成立，由于 ，故只
能有某一个Pi=1,其余的Pk=0
70
熵函数的数学特性
• （3）扩展性
• 证：因为
),,,(lim),,( 211
0
21
qqq PPPHPPPH
0loglim
0
说明信源的取值数增多时，若这些取值对应
的概率很小（接近于零），则信源的熵不变。
71
熵函数的数学特性
• （4）可加性
• 如果有两个随机变量X和Y，他们不是相互
独立的，则二维随机变量的熵H(XY)等于X
的无条件熵H(X)加上当X已给定时Y的条件
概率定义的熵的统计平均值H(Y|X) 。
• H(XY) =H(X) +H(Y|X)
• H(XY) =H(Y) +H(X|Y)
72
熵函数的数学特性
• （5）极值性
• 式中，n是集合X的元素数目。
• 上式表明，在离散情况下，集合X中的各事
件依等概率发生时，熵达到极大值，即最
大熵定理。
n
nnn
HPPPH n log)
1
,
1
,
1
(),,( 21
73
熵函数的数学特性
• （6）确定性
• 从总体看，信源虽然有不同的输出符号，
但当它只有一个符号几乎必然出现，而其
他符号都是几乎不可能出现时，那么这个
信源是一个确知信源，其熵等于零。
• （7）上凸性
的严格上凸函数。是概率分布 ),,(),,( 2121 qq PPPPPPH
74
条件熵
• 条件熵是在联合符号集XY上的条件自信息量的联
合概率加权统计平均值。
)|(log)()|()()|( xyPxyPxyIxyPXYH
XYXY
)|(log)()|()()|( yxPxyPyxIxyPYXH
XYXY
条件熵H(X|Y)表示收到全部输出符号后，对信道输
出符号集还存在的平均不确定性，称为信道疑义度。
条件熵H(Y|X)可以衡量信号通过信道后
损失信息量的多少。
75
联合熵（共熵）
• 联合熵是在符号集XY上的每个元素对xiyj的
自信息量的概率加权统计平均值，其定义
式为
n
i
ji
m
j
ji
n
i
ji
m
j
ji yxPyxPyxIyxPXYH
1 11 1
)(log)()()()(
76
各种熵的性质
• （1）联合熵与信源熵、条件熵的关系
• 若集X和集Y相互独立则有
• 表示熵的可加性。
• 称为熵的强可加性。
)|()()(
)|()()(
YXHYHXYH
XYHXHXYH
)()()( YHXHXYH
77
各种熵的性质
• 推广到多个随机变量构成的概率空间之间
的关系。设有N个变量 ，其联
合熵可表示为
• 若N个变量相互独立，则有
N
i
ii
NNN
XXXXH
XXXXHXXHXHXXXH
1
121
12112121
)|(
)|()|()()(
NXXX ,, 21
N
i
iN XHXXXH
1
21 )()(
78
各种熵的性质
• （2）联合熵与信源熵的关系
• 当且仅当两个集合相互独立时，上式取等号，此
时可得联合熵的最大值，即
)()()( YHXHXYH
)()()( max YHXHXYH
)()()()( 2121 NN XHXHXHXXXH
此性质同样可推广到N个变量构成的概率空间
等号成立的充要条件是概率空间相互独立。
79
各种熵的性质
• （3）信源熵与条件熵的关系
• 当且仅当两个集合相互独立时，上式取等号。
)()|(
)()|(
XHYXH
YHXYH
80
各种熵的性质
• 例 输入输出的联合分布如下表
Y
X
y1 y2 y3 y4
x1 0 0 0
x2 0 0
x3 0 0
x4 0 0
x5 0 0 0
81
各种熵的性质
• 例 P(x),P(y|x) ,P(xy)如下表
X A B C
P(x) 1/2 1/3 1/6
P(y|x
)
D 1/4 3/10 1/6
E 1/4 1/5 1/2
F 1/4 1/5 1/6
G 1/4 3/10 1/6
P(xy)
X
A B C
Y
D 1/8 1/10 1/36
E 1/8 1/15 1/12
F 1/8 1/15 1/36
G 1/8 1/10 1/36
82
各种熵的性质
• 例
P(ij)
i
0 1 2
j
0 1/4 1/18 0
1 1/18 1/3 1/18
2 0 1/18 7/36
P(j|i)
i
0 1 2
j
0 9/11 1/8 0
1 2/11 3/4 2/9
2 0 1/8 7/9
0 31 2
1/3
2/3
P(v)
5/9
v
一个连续信源的概率分布密度
83
加权熵
• 设有随机变量X，引入事件的重量后，其概率空
间为
• 其中
• 离散无记忆信源[X P W]的加权熵定义为
01
2,10)(
)()()(
1
21
21
21
i
n
i
i
ii
n
n
n
p
nixpp
xpxpxp
xxx
W
P
X
)/1log()(
1
ii
n
i
iW ppXH
84
加权熵
• 重要性质：
0)(
),,2,1(,
,,0,0,,0,04
0)(
,,,2,1,0)(1)(3
)()(2
0)(1
21
XH
JInJIJI
JjpIip
XH
jinixppxpp
XWHXHWWWW
XH
W
jjii
W
iijj
WN
W
则
为样本空间，并且
而）若（
则
而）确定性：若（
，则）若权重（
）非负性：（
85
离散集的平均互信息量
• 平均条件互信息量
• 平均互信息量
• 平均互信息量的性质
86
离散集的平均互信息量
• 以[X P]表示输入概率空间
1
2,10)(
)()()(
1
21
21
n
i
i
ii
n
n
p
nixpp
xpxpxp
xxx
P
X
87
离散集的平均互信息量
• 以[Y P]表示输出概率空间
1
2,10)(
)()()(
1
21
21
m
j
j
jj
m
m
p
mjxpp
ypypyp
yyy
P
Y
88
离散集的平均互信息量
• X和Y的联合空间
n
i
jij
m
j
jii
n
i
m
j
ji
jiji
yxpyp
yxpxp
yxp
mjniYyXxyxXY
1
1
1 1
)()(
)()(
1)(
}2,1;2,1,,;{
89
离散集的平均互信息量
• 以[XY p(xy)]表示联合概率空间，一般有
• 当事件xi和yj相互独立时有
• 若上式对所有的i,j成立，则称集X与Y统计
独立，否则称为统计相关。
0)(
)(
)(
)|(
0)(
)(
)(
)|(
j
j
ji
jiji
i
i
ji
ijij
yp
yp
yxp
yxpp
xp
xp
yxp
xypp
)()()( jiji yPxPyxP
90
平均条件互信息量
• 在联合集XY上，由yj提供的关于集X的平均条件互信息量
等于由yj提供的互信息量在整个X中的后验概率加权的平
均值，其定义式为
n
i i
ji
ji
n
i
jijij
xp
yxp
yxp
yxIyxpyXI
1
1
)(
)|(
log)|(
);()|();(
0);( jyXI联合集XY上的平均条件互信息量有
当且仅当集X中的各个xi都与事件yj相互独立时
取等号。
91
平均互信息量
• 互信息量在整个集上的概率加权平均值，称为平
均互信息量
n
i
m
j
jiji
n
i
m
j i
ji
ji
n
i
m
j i
ji
jij
m
j
jj
yxIyxp
xp
yxp
yxp
xp
yxp
yxpyp
yXIypYXI
1 1
1 1
1 1
1
);()(
)(
)|(
log)(
)(
)|(
log)|()(
);()();(
0);(2,1;2,1,0);( YXImjniyxI ji 且
当事件xi与yj相互独立时
92
平均互信息量的性质
• （1）非负性： 当且仅当事件xi与yj相
互独立时取等号。
n
i
m
j j
ij
ji
n
i
m
j ji
ji
ji
n
i
m
j ji
jji
ji
n
i
m
j i
ji
ji
XYI
yp
xyp
yxp
ypxp
yxp
yxp
ypxp
ypyxp
yxp
xp
yxp
yxpYXI
1 1
1 1
1 1
1 1
);(
)(
)|(
log)(
)()(
)(
log)(
)()(
)()|(
log)(
)(
)|(
log)();(
0);( YXI
（2）对称性
93
平均互信息量的性质
• （3）平均互信息与各类熵的关系
• 用维拉图表示为
)()()();(
)|()();(
)|()();(
XYHYHXHYXI
XYHYHYXI
YXHXHYXI
H(X
)
H(Y
)
H(X|Y) I(X;Y) H(Y|X)
H(XY)
94
平均互信息量的性质
• （4）极值性
)();(
)();(
YHYXI
XHYXI
（5）凸函数性
平均互信息量是信源概率分布p(x)和信道
传递概率p(x|y)的凸函数。
95
96
• 例1 有一个布袋内放100个球，其中80个红
球，20个白球。随便摸一个球猜测是什么
颜色，求平均摸取一次获得的信息量。
• 解：设事件x1表示摸到红球，事件x2表示摸
到白球，则概率空间为
21 xx
P
X
97
• 当告知摸出的是红球时，获得的信息量
• 当告知摸出的是白球时，获得的信息量
bitxPxI )(log)( 22
bitxPxI )(log)( 11
)()()()( 2211 xIxnPxIxnP
若每次摸出一个球后又放回去，进行第二次
摸取，那么摸取n次中，红球出现的次数为
nP(x1) ，白球出现的次数为nP(x2) 。则摸取n
次后获得的信息量为
98
• 平均随机摸取一次所能获得的信息量为
2
1
2211
2211
)(log)(
)](log)()(log)([
)]()()()([
1
)(
i
ii xPxP
xPxPxPxP
xIxnPxIxnP
n
XH
99
• 例2 某人A预先知道他的三个朋友B、C、D
中有一人晚上到他家，且这三人来的可能
性相同，先验概率 P(B)= P(C)= P(D)=1/3 。
但上午A接到D的电话说不能来了，将这次
电话作为事件E，那么有后验概率
P(D|E)=0, P(B|E)= P(C|E)=1/2。
下午又接到C的电话说不能来，将此作为事
件F，则有P(C|EF)= P(D|EF)=0, P(B|EF)= 1。
100
• 在接到上午电话后，A获得关于B、C、D的互信
息量为
• 因为P(D|E)=0 ,故无需考虑事件D与事件E间的互
信息量。
• 在接到两次电话后，A获得关于B、C、D的互信
息量为
• 因为P(C|EF)= P(D|EF)=0,故无需考虑事件D与事
件E间的互信息量。
bit
BP
EBP
EBI
3/1
2/1
log
)(
)|(
log);(
bitEBIECI );();(
bit
BP
EFBP
EFBI
3/1
1
log
)(
)|(
log);(
101
• 例3：某地的天气情况分布是：晴天占1/2，阴天占1/4，
雨天占1/8，雪天占1/8。求各种天气的自信息量。
• 解：设晴天、阴天、雨天、雪天的状态分别为x1,x2,x3,x4
bit
xP
xI
bit
xP
xI
bit
xP
xI
bit
xP
xI
38log
)(
1
log)(
38log
)(
1
log)(
24log
)(
1
log)(
12log
)(
1
log)(
4
4
3
3
2
2
1
1
102
• 例 在盒子中放入n个不同阻值的电阻，
随机取出一个并猜测阻值，概率空间为
• 其中xi代表阻值为 表示
取出电阻值为i 的电阻的概率。假定取出电
阻是等概率的，即
那么被告知取出阻值为i的电阻，所获得的
信息量为
1 2
1 2
...
( ) ( ) ( )... ( )
n
n
x x xX
P x P x P x P x
1,2, ... , , ( )ii n P x
( ) 1 , 1,2, ... , ,iP x n i n
nxPxI ii log)(log)(
103
• 若盒中放入 个不同阻值的电阻，其中阻
值为1欧姆的1个，2欧姆的2个， n欧姆的n个。
概率空间为
• 其中xi代表阻值为 表示取出电
阻值为i 的电阻的概率。那么被告知取出阻值为i
的电阻，所获得的信息量为
1 2 ...
1 2
...( )
( 1) / 2 ( 1) / 2 ( 1) / 2
nx x x
X
n
P x
n n n n n n
1,2, ... , , ( )ii n P x
i
nn
xPxI ii
2
)1(
log)(log)(
2/)1( nn
104
• 例 设在一正方形棋盘上共有64个方格，如
果甲将一粒棋子随机地放在棋盘中某方格
内让乙猜。
• （1）将方格按顺序编号，猜测顺序号；
• （2）将方格按行和列编号并告知行或列编
号，猜测位置。
105
• 解：由于棋子位置是二维等概率分布，故
• （1）在二维联合集 上的元素 的自信息量
为
• （2）在二维联合集 上，元素 相对 的条件
自信息量为
比特3
64/1
8/1
log
)(
)(
log)|(log)|(
ji
j
jiji
yxP
yP
yxPyxI
XY
64/1)( ji yxP
比特6
64
1
log)(log)( jiji yxPyxI
ji yx
jy
ixXY
106
第三章 信源编码-离散信源无失真编码
• 信源的数学模型及其分类
• 离散无记忆信源
• 离散无记忆信源的扩展信源
• 离散平稳信源
107
信源的数学模型及其分类
• 信源的数学模型
• 信源的分类
108
信源的数学模型
• (1) 离散信源
• 信源输出的是单个符号或代码的消息，信源符号
集的取值是有限的或可数的，可以用一维离散型
随机变量来描述，其数学模型是
1 2
1 2
1
...
( ) ( )... ( )
( ) 0 1,2...
( ) 1
q
q
i
n
i
i
x x xX
P p x p x p x
p x i q
p x
109
信源的数学模型
• (2) 连续信源
• 信源输出的是单个符号或代码的消息，信源符号
集的取值是连续的，可以用一维连续型随机变量
来描述，其数学模型是
• 其中p(x)为连续随机变量X的概率密度函数，
(a,b)为X的存在域。
1)(
0)(
)(
),(
b
a
dxxp
xp
xp
ba
P
X
110
信源的数学模型
• 若N维随机矢量 中
• 信源的N重概率空间为
1 1 1 1 1 2
1 1 1 1 1 2
( ... ), ( ... ),..., ( ... )
( ... ), ( ... ),..., ( ... )
q q q
q q q
x x x x x x x x xX
P p x x x p x x x p x x x
1 2
1 2
{ , ... }, 1,2...,
( ... )
i q
N
N
X x x x i N
X X X X X
则
1 2( ... )NX X X X
这个空间共有元素qN个，取决于序列长度N
和符号集的符号个数q 。
111
信源的分类
(1)按照消息取值集合以及取值时刻集合
的离散性和连续性，信源可分为数字信
源和模拟信源（波形信源）。
(2)按照某取值时刻消息的取值集合的离
散性和连续性，信源可分为离散信源和
连续信源。
112
信源的分类
• (3)按照信源输出消息所对应的随机序列的
平稳性，信源可分为平稳信源和非平稳信
源。
(4)按照信源输出的信息所对应的随机序列
中随机变量前后之间有无统计依赖关系，
信源可分为无记忆信源和有记忆信源。
113
信源的分类
• 在某些简单情况下，信源发出的一个个符
号是彼此统计独立的，并且它们具有相同
的概率分布，则N维随机矢量的概率分布满
足
• 其中，
• 这种信源称为离散无记忆信源。
1
( ) ( )
1,2,...,
i
N
k k
k
i
p x p X x
k q
可取
114
信源的分类
在通常情况下，信源发出的符号是彼此依
赖的，要引入条件概率分布来说明它们间
的关联，这种信源称为有记忆信源。
有记忆信源可用有限状态马尔可夫链来
描述。当信源记忆长度为m+1时，称为m
阶马尔可夫信源，即信源每次发出的符号
只与前m个有关,与更前面的符号无关。
115
离散无记忆信源
• 在信源X中，事件xi发生的概率为p(xi) ，则
xi所含的自信息量定义为
• I(xi) =-logp(xi)
q
i
iii xpxpxIEXH
1
)(log)()]([)(
信源输出各消息的自信息I(xi)的数学期望为
信源的平均自信息量H(X)即信源的信息熵。
116
离散无记忆信源的扩展信源
• 最简单的离散信源
• N次扩展信源
• N次扩展信源的熵
117
最简单的离散信源
• 最简单的离散信源的输出可用一维离散随机变量描述。
• 对于二进制信源，其数学模型为
1 2
1 2
1
...
( ) ( )... ( )
( ) 0 1,2...
( ) 1
q
q
i
n
i
i
x x xX
P p x p x p x
p x i q
p x
ppP
X 10
118
N次扩展信源
• （1）离散无记忆二进制信源X的二次扩展
信源
• 每两个二进制数字组成一组，新的等效信源的输出符号为
x1=00， x2= 01， x3= 10， x4= 11。
• 二次扩展信源的数学模型为
• 其中
2,1)1,0(
4,3,2,1)()()(
)()()()()(
21
4321
4321
kXx
ixpxpxp
xpxpxpxp
xxxx
xp
X
ki
iii
119
N次扩展信源
• （2）离散无记忆二进制信源X的三次
扩展信源
• 每三个二进制数字组成一组，新的等效信源的输
出符号为x1=000， x2= 001， x3= 100，… ，x8=
111。
• 三次扩展信源的数学模型为
• 其中 1 2 3
1 2 3 8
1 2 3 8
...
( ) ( ) ( ) ( )... ( )
( ) ( ) ( ) ( ) 1,2,...,8
(0,1) 1,2,3
k
i i i i
i
x x x xX
p x p x p x p x p x
p x p x p x p x i
x X k
120
N次扩展信源
• 以此类推，由N个二进制数字为一组构成的
新信源共有2N个符号，每个符号长度为N ，
称为二进制信源的N次扩展信源。
121
N次扩展信源
• （3）离散无记忆信源的N次扩展
• 设一个离散无记忆信源X的概率空间为
1 2 3
1 2 3
...
( ) ( ) ( ) ( )... ( )
q
q
x x x xX
p x p x p x p x p x
1 2
1 2 3
1 2 3
1
1
...
( ) ( ) ( )... ( )( )
( ) ( ) ( )... ( ) ,..., 1,2,...,
N
N
N k
N
q
q
N
i i i i i N
k
x x x xX
p x p x p x p xp x
p x p x p x p x p i i q
q为信源的符号个数，则信源X的N次扩展信源用XN表示，
它是具有qN个符号的离散信源，其N重概率空间为
122
N次扩展信源的熵
• 根据信息熵的定义，离散无记忆信源X的N
次扩展信源XN的熵等于信源X的熵的N倍，
即
• H(XN)=NH(X)
123
N次扩展信源的熵
• 例
4/14/12/1
321 xxx
P
X
X2信源符号xi x1 x2 x3 x4 x5 x6 x7 x8 x9
符号序列 x1 x1 x1 x2 x1 x3 x2 x1 x2 x2 x2 x3 x3 x1 x3 x2 x3 x3
概率p(xi) 1/4 1/8 1/8 1/8 1/16 1/16 1/8 1/16 1/16
124
离散平稳信源
• 定义
• N长信源序列的熵
125
定义
定义：
信源产生的随机序列 满足：
• 1）所有 都取值于有限的信源符
号集 ；
• 2）随机序列是平稳的，即对所有的非负整
数 有
, 1,2,...iX i
1 2( , ,..., )qX x x x
, 1,2,...iX i
1 2 1 2, ,..., , , , , , ,N Ni i i h x x x N及
1 2
1 2
1 2
1 2
( , ,... )
( , ,..., )
N
N
i i i N
i h i h i h N
P X x X x X x
P X x X x X x
126
定义
一维平稳信源：
• 任意两个不同时刻信源发出符号的概率分
布完全相同，即
其中，i,j为任意整数
1 2, ( , ,..., )qi j x X x x x
)()()( xpxXPxXP ji
127
定义
二维平稳信源：
• 除上述条件外，如果联合概率分布p(x1x2)
也与时间起点无关，即
其中，i,j为任意整数
1 2 1 2, ( , ,... )qi j x x X x x x
)(),(),( 212121 2121 xxpxXxXPxXxXP jjii
128
定义
完全平稳信源：
• 如果各维联合概率分布均与时间起点无关，
即当t=i,t=j,(i,j为任意整数且不相等）时有
1 1
1 1
( ) ( )
( ) ( )
...
( ... ) ( ... )
i j
i i j j
i i i N j j j N
P x P x
P x x P x x
P x x x P x x x
129
N长信源序列的熵
平稳有记忆信源
• 发出符号序列为 ，假设
信源符号间的依赖长度为N，则联合概率为
1 2 3
1 2 3
...
( ) ( ) ( )... ( )
q
q
x x x xX
P p x p x p x p x
1 2 1(... , ,..., , ,...)N NX X X X
1 2
1 2
1 2 1 2
1 2
( ... ) ( , ,..., )
( ... ) , ,..., 1,2,...,
N
N
N i i N i
i i i N
P x x x P x x x x x x
P x x x i i i q
简写成
130
N长信源序列的熵
1 2 1 2
1
1 2 1 2 1
1
1 2
,...,
1 1
1 2 1
1
1 2 1
,...,
1 2
( ) ( ... )
( ... ) log ( ... )
( | ) ( ... )
( | ... )
( ... ) log ( | ... )
1
( ) ( ...
N N
N
N N N
N
N
N
i i i i i i
i i
N
n n
n n
n
N N
i i i i i i i
i i
N
H X H X X X
P x x x P x x x
H X X X X X X
H X X X X
P x x x P x x x x
H X H X X X
N
联合熵
条件熵
平均
为
表示集合
为
为符号熵 )N
131
N长信源序列的熵
例：设有一信源，产生0,1序列的消息，且在
任意时间，不论前面发生过什么符号，均
按P(0)=, P(1)=的概率发出符号。
（1）试问这个信源是否是平稳的。
（2）计算
（3）计算H(X4)并写出X4信源中可能有的所
有符号。
)(lim),|(),( 213
2 XHXXXHXH N
N
132
N长信源序列的熵
解：
（1）依题意，信源发出符号的概率分布与时
间平移无关，且信源发出的序列之间也是彼
此无依赖的，故此信源是平稳信源，而且是
离散无记忆信源。
133
N长信源序列的熵
（2）信源概率空间为
可计算得
因为信源是平稳无记忆信源，所以
10
P
X
2
3 1 2 3
1 2
( ) 2 ( ) /
( | ) ( ) ( ) /
1
lim ( ) lim ( ... )
1
lim ( )
( ) /
N N
N N
N
H X H X
H X X X H X H X
H X H X X X
N
N H X
N
H X
比特 两个符号
比特 符号
比特 符号
符号比特/)( XH
134
N长信源序列的熵
（3）
X4信源中可能有的符号有16种
四个符号比特/)(4)( 4 XHXH
0000 0001 0010 0100
1000 0011 0110 1100
0101 1010 1001 1101
1110 0111 1011 1111
135
N长信源序列的熵
对于离散、平稳、有记忆信源，当 时，下
列结论成立：
（1）条件熵 随N的增加是非
递增的（即N的单调非增函数）；
（2）
（4）
1 2 1( | ... )N NH X X X X
1 2 1( ) ( | ... );N N NH X H X X X X
1 2 1
lim ( )
lim ( | ... )
N
N
N N
N
H H X
H H X X X X
极限熵 存在，并且
；
)(1 XH
（3）HN (X)是随N的增加是非递增的（即N的
单调非增函数）；
136
信源编码
无失真信源编码
编码器
分组码
等长信源编码定理
变长编码定理
限失真信源编码
常用的信源编码方法
137
• 例 中文电报对于汉字采用l=4,r=10的等长
编码,即每个汉字用4位十进制数字表示,
例如”中国北京”的代码是0022, 0948,
0554 ,0079
• 当 l=5,r=2时, 就是5单位的二元码
138
编码器
无失真信源编码可以不考虑抗干扰问题，其数学模型比较简
单，如图所示
1 2
1 2
1 2
S ( , ... ),
, 1,2,...,
( , ... ) ,
, 1,2,...,
( , ..., )
q
i
q
i
r
i
s s s
s i q
C W W W
W i q
X x x x
x
输入信源符号集
其元素 叫做信号单元或消息；
输出集 叫做代码（码组或码书）
其元素 称为码字；
另一符号集 是构成码字的符号集，
其元素 一般是适合信道传输的，称为码符号或码元。
1 2[ , ... ]qS s s s
1 2[ , ... ]rX x x x
1 2[ , ... ]qC W W W
编码器
信源编码器
139
编码器
编码器的作用就是将信源符号集中的符号
（或者长度为N的符号序列）变换成由基本
符号 组成的长度为N的一一对
应的输出符号序列。即
而码字
其中，长度 称为码字长度，简称码长。
1 2
1 2( , ... )
( , ... ) 1,2,...,
q
q
i i i i
C W W W
W x x x i q
, 1,2,...,is i q
, 1,2,...,jx j r
ji
140
编码器
二进制码
信源符号si 信源符号出现概率p(si) 码1 码2
s1
p(s1) 00 0
s2
p(s2) 01 01
s3
p(s3) 10 001
s4
p(s4) 11 111
如果码中所有码字含有的码符号个数相同，则
称为固定长度码或等长码，反之称为变长码。
141
编码器
1 2
NS ( , 1,2... ),
, 1,2... ...
( , 1,2... ),
, 1,2... , 1,2...
N
N
j
N
j j j j j
N N
j
N N
j j
S N a j q
a j q a s s s
C W j q
W j q a j q
信源 的 次扩展信源为
信源符号为 且 ；
经信源编码后有
码字 是和信源符号 一一对应的。
二次扩展信源符号
a1=s1 s1 00
a2= s1 s2 001
a3= s1s3 0001
a16= s4 s4 111111
, 1,2...16jW j 码字, 1,2...16ja j
...
142
分组码
同价码：每个码符号所占的传输时间都相同
的码。
对同价码而言，等长码中的每个码字的传输
时间相同，而变长码中的每个码字的传输
时间不一定相同。
143
分组码
信源编码过程可以抽象为一种映射，
即将信源符号集 中的每
一个元素si映射为码集合中的一个长度
为li的码字 ,这样的码称
为分组码。
( , 1,2,..., )iS s i q
, 1,2,...,iW i q
144
分组码
码字前缀的定义是：设
为一个码字，对于任意的 ，
称码符号序列的前j个元素
为码字Wi的前缀。
1 2
...
li i i i
W W W W
lj 1
1 2
...
ji i i
W W W
145
分组码
分组码的基本类型：
（1）奇异码
若分组码中的所有码字互不相同，则称此
分组码为非奇异码，否则称为奇异码。
信源符号si 信源符号出现概率p(si) 码1 码2
s1 p(s1) 00 0
s2 p(s2) 01 01
s3 p(s3) 00 00
s4 p(s4) 11 111
146
分组码
（2）惟一可译码
[1]若分组码对任意有限整数N，其N阶扩展
码均为非奇异的，则称之为惟一可译码。
[2]任意有限长的码元序列，只能被惟一的
分割成一个个的码字，便称为惟一可译码。
147
分组码
例如{0，10，11}是一种惟一可译码，
因为任意一串有限长码序列，如100111000
只能被分割成10，0，11，10，0，0
任何其他分割都会产生一些非定义的码字。
148
分组码
（3）即时码
无需考虑后续的码符号即可从码符号序列
中译出码字，这样的惟一可译码称为即时
码（瞬时码、非延长码或异前置码）。
已构成的码字的任何延长不再构成码字，故称
为非延长码。
任意一个码字都不是其他码字的前缀部分，也
称为异前缀码或异前置码。
149
分组码
定理：一个惟一可译码成为即时码的充要条
件是其中任何一个码字都不是其他码字的
前缀。
信源符号si 信源符号出现概率p(si) 码1 码2
S1 p(s1) 1 1
s2 p(s2) 10 01
s3 p(s3) 100 001
s4 p(s4) 1000 0001
150
分组码
即时码可以用树图法来构造。
树根 码字的起点
树枝数 码的进制数
节点 码字或码字
的一部分
终止节点
（端数）
码字
节数 码长
非满树 变长码
满树 等长码
A
1
C
1
E
G(111
)
F(110
)
D(10)
B(0)
1
0
0
0
非满树
A 1
B
1
C
G(11)
F(10)
E(01)
D(00
)
1
0
0
0
满树
151
分组码
综上所述，可将码作如下分类：
码
非分组码
分组码
奇异码
非奇异码
非惟一可译码
惟一可译码
非即时码
即时码
（非延
长码）
152
分组码
例：一个信源有六个可能的输出，其概率分布和对
应的编码如下表。求哪些是惟一可译码，哪些是
即时码。
符号si 概率p(si) A B C D E F
S1 1/2 000 0 0 0 0 0
S2 1/4 001 01 10 10 10 100
S3 1/16 010 011 110 110 1100 101
S4 1/16 011 0111 1110 1110 1101 110
S5 1/16 100 01111 11110 1011 1110 111
S6 1/16 101 011111 111110 1101 1111 011
153
分组码
判断方法：
对于变长码，计算出分组码中所有可能的尾
随后缀集合，观察其中有没有包含任一码
字，若没有则该分组码是惟一可译码，否
则就不是。
154
分组码
解：
码组A是等长码，其中没有相同的码字，所以是惟
一可译码。
其他码组是变长码，可采用惟一可译变长码的判断
法来判断。
码组B：最短码字为“0”，是其他码字的前缀，但
其尾随后缀都不是码字。同样对其他码字，其尾
随后缀都不是码字，所以是惟一可译码。
155
分组码
码组C：没有码字是其他码字的前缀，他们都
不存在尾随后缀，所以是惟一可译码。
码组D：最短码字为“0”，不是其他码字的
前缀，但码字“10”是码字“1011”的前缀，
其尾随后缀11是码字“110”的前缀，进一
步得到11的尾随后缀0,其中0是最短的码字。
所以D不是惟一可译码。
156
分组码
码组E：最短码字为“0”，不是其他码字的前
缀。码字“10”也不是其他码字的前缀，而
剩下四个码字是等长码，都不相同，所以E
是惟一可译码。
码组F：最短码字为“0”，是码字“011”的
前缀，其尾随后缀11是码字“110”的前缀，
进一步得到11的尾随后缀0和1，其中0是最
短的码字。所以F不是惟一可译码。
157
分组码
综上所述，码组A,B,C,E是惟一可译码，并且
码组A, C,E是即时码。
158
信源符号X={S1，S2，S3，S4}，其码字如表
符号si 概率p(si) 码0 码1 码2 码3 码4
S1 1/2 00 0 0 1 1
S2 1/4 01 11 10 10 01
S3 1/8 10 00 00 100 001
S4 1/8 11 11 01 1000 0001
159
奇异码: 码1
唯一可译码：
非唯一可译码： 码2
码3,码0,码4
等长码: 码0
160
满树：
每个节点上都有r个分枝的树——等长码
非满树：
变长码
用树的概念可导出唯一可译码存在的充分和必要
条件,即各码字的长度Ki应符合Kraft不等式
1
1
n
i
Kim
式中:
m是进制数
n是信源符号数
161
例：设二进制码树中X=(a1 , a2 , a3 , a4),
K1=1,K2=2,K3=2,K4=3,应用Kraft不等式,得：
1
8
9
22222 3221
4
1
i
Ki
不存在满足这种Ki的唯一可译码
如果将各码字长度改成K1=1,K2=2,K3=3,K4=3,则
122222 3321
4
1
i
Ki
162
必须注意：
Kraft不等式只是用来说明唯一可译码是否存在,
并不能作为唯一可译码的判据。
如码字{0，10，010，111}虽然满足Kraft不等
式,但它不是唯一可译码。
163
无失真信源编码
信源编码器输入的消息序列:
X=(X1 X2…Xl …XL),
Xl∈{a1,…an},
输入的消息总共有nL种可能的组合
输出的码字为:
Y=(Y1 Y2 …Yk… YK ) ,
Yk∈{b1,…bm}
输出的码字总共有mK种可能的组合。
信源编码器
码表
信源 信道
Y
L长序列
K长码字
X
164
实现无失真的信源编码,要求:
信源符号X1 X2…Xl …XL 是一一对应的
码字Y1 Y2…Yk… YK
能够无失真或无差错地从Y恢复X,也就是能正确地进行反
变换或译码 ;
传送Y时所需要的信息率最小
信息率最小就是找到一种编码方式使
1
log logL
K
R m M
L L
最小
165
定长编码定理
在定长编码中,K是定值。
我们的目的是寻找最小K值。
编码器输入X=(X1 X2…Xl …XL), Xl∈{a1,…an},
输入的消息总共有nL种可能的组合
输出的码字Y=(Y1 Y2 …Yk… YK ) , Yk∈{b1,…bm}
输出的码字总共有mK种可能的组合。
若对信源进行定长编码,必须满足: nL≤mK
信源编码器信源 信道X
Y
L长序列
K长码字码表
166
若对信源进行定长编码,必须满足:
m
n
L
K
mn KL
log
log
或
只有当K长的码符号序列数 mK大于或等于信源
的符号数nL时,才可能存在定长非奇异码。
例如英文电报有27个符号,n=27,L=1,m=2(二元编
码)
527log
log
log
2
2
2
m
n
LK
每个英文电报符号至少
要用5位二元符号编码
167
• 实际英文电报符号信源,在考虑了符号出现的概率
以及符号之间的依赖性后,平均每个英文电报符号
所提供的信息量约等于比特。
• 编码后5个二元符号只携带约比特信息量。
• 定长编码的信息传输效率极低。
168
等长信源编码定理
定理（等长信源编码定理）：设有离散无记忆信源，其熵
为H(S) ，若对信源长为N的符号序列进行等长编码，
设码字是从r个码符号集中选取l个码元构成，对于任
意 ， 只要满足
则当N足够大时，几乎可实现无失真编码。反之，当
时，不可能实现无失真编码，而当N足够大时，译码错误
概率近似等于1。
0
r
SH
N
l
log
)(
r
SH
N
l
log
2)(
169
等长信源编码定理
• 该定理是在平稳无记忆离散信源的条件下
论证的，但同样适于平稳有记忆信源，只
是要求信源的极限熵 和极限方差
存在，并将式中的H(S)改为 。)(SH
2
)(SH
q
N
l
SH
N
l
r
log
)()(2
分布时当信源符号具有等概率
时为二进制码当
170
等长信源编码定理
将定理中的条件改写成
l logr>NH(S)
左边表示长为l的码字符号序列能载荷的最大
信息量。
右边表示长为N的信源序列平均携带的信息量。
故只要码字传输的信息量大于信源序列携
带的信息量，总可以实现几乎无失真编码。
171
等长信源编码定理
编码速率：
编码效率：
取等号时得到最佳编码效率。
符号比特/
log
N
rl
R
rl
SNH
R
SH
log
)()(
0
)(
)(
)(
SH
SH
SHR
故
由定理知
172
等长信源编码定理
当允许错误概率 时，信源序列长度
必满足
2
2
2
2
)1()(
)]([
)1)((
)]([
SH
sID
N
SH
sID
N
i
i
故
由于
小于p
173
• 例5-2：设离散无记忆信源概率空间
87654321 aaaaaaaa
P
X
信源熵： 符号/)(log)()( bitxpxpXH
i
ii
方差：
若取差错率δ≤ , 编码效率为90%,则L应满足
7
622
2
)(
X
L
在差错率和编码效率要求并不十分苛刻的条件下,就需要
信源符号进行联合编码,这显然是很难实现的。
222
8
1
2 )]([)(log)( bitXHppX
i
ii
610
174
等长信源编码定理
例 设一简单离散信源如下
对其进行等长近似无失真编码，若取编码效
率为95%，差错概率 ，求信源符号
联合编码长度。
610
8
1
8
1
4
1
2
1
4321 ssss
P
S
175
等长信源编码定理
解：
6
2
2
2
22
1
4
1
)1()(
)]([
)]([])()[log()]([
)(log)()(
SH
SID
N
SHspspsID
spspSH
i
q
i
iii
i
ii
故
176
变长编码定理
• 在变长编码中码长K是变化的。
• 我们可根据信源各个符号的统计特性,如概率大的
符号用短码,概率小的用较长的码,这样在大量信源
符号编成码后平均每个信源符号所需的输出符号
数就可以降低,从而提高编码效率
177
变长编码定理
对一个信源中的不同符号采用不同长度的
码字表示，就称为变长编码或不等长编码。
要实现无失真的信源编码，变长码必须是
惟一可译码。为了能即时进行译码，变长
码还必须是即时码。
178
变长编码定理
基本思想：
一般离散无记忆信源输出的各消息概率是不
等的，若对概率大的采用较短的码字，对
概率小的采用较长的码字，使编码的平均
码长最短，也实现了与信源统计特性相匹
配。
179
变长编码定理
定理：对于熵为H(S)的离散无记忆信源
若用具有r个码符号的集 对其进行编
码，则一定存在一种编码方法构成惟一可译码，
其平均码长 满足：
1 2
1 2
...
( ) ( ) ... ( )
q
q
s s sS
P p s p s p s
1 2( , ,..., )rX x x x
r
SH
l
r
SH
log
)(
1
log
)(
180
定理：设离散无记忆信源S的熵为H(S)，其N次扩展信源为
SN
其信源熵为H(SN)。用码符号集 对SN进行编
码，总可以找到一种编码方法构成惟一可译码，使信源S
的每个信源符号所需的码字平均码长满足：
1 2
1 2
...
( ) ( ) ... ( )
N
N
N
q
q
a a aS
p a p a p aP
1 2( ... )rX x x x
)(lim
)(
1
)(
log
)(1
log
)(
SH
N
l
N
SH
NN
l
SH
r
SH
NN
l
r
SH
r
N
N
r
N
r
N
时，则当
或
181
变长编码定理
是无记忆N次扩展信源SN中每个信源符号ai所
对应的平均码长
式中， li是ai所对应的码字长度。
i
q
i
iN lapl
N
1
)(
Nl
l Nl N /
和 两者都是每个原始信源符号si所需
要的码符号的平均数。
前者是直接对单个信源符号si进行编码。
后者是对N次扩展信源SN符号序列ai进行编码。
182
变长编码定理
编码效率：
用来衡量各种编码距极限压缩值的情况。
码的剩余度：
r
R
l
SH
rl
SH
R
SH r
log
')(
log
)()(
l
SH r )(11
')(2 Rr 时二进制码当
183
变长编码定理
若对该信源进行变长编码
%100
2log
4
7
4
7
1
log
)(
4
7
3
8
1
3
8
1
2
4
1
1
2
1
)(
111110100
8
1
8
1
4
1
2
1
1
4321
rl
SNH
lspl
ssss
P
S
q
i
ii
编码效率：
平均码长：
变长码：
184
1
log
)(
log
)(
m
XH
K
m
XH
单个符号变长编码定理：
若一离散无记忆信源的符号熵为H(X),每个信源
符号用m进制码元进行变长编码,一定存在一种
无失真编码方法,其码字平均长度满足下列不等
式:
185
• 离散平稳无记忆序列变长编码定理
对于平均符号熵为HL(X)的离散平稳无记忆信源,必存在一
种无失真编码方法,使平均信息率 满足不等式
( ) (X) L LH X R H
其中ε为任意小正数
R
186
• 用变长编码来达到相当高的编码效率,一般所要求
的符号长度L可以比定长编码小得多。
• 编码效率的下界：
( ) ( )
log
( )
L L
L
H X H X
mR
H X
L
187
• 若对例5-2用变长码实现, 要求η＞90%,用二进
制,m＝2,log2m=l。
( ) ( )
log
( )
L L
L
H X H X
mR
H X
L
得L= 4
1
L
188
• 再对长度为L =2的信源序
列进行变长编码,其即时码
如表
ai p(ai) 即时码
a1 a1
a1 a2
a2 a1
a2 a2
9/16
3/16
3/16
1/16
0
10
110
111
平均码长为：
16
27
3
16
1
3
16
3
2
16
3
1
16
9
2 K
单个符号的平均码长
编码效率为
输出的信息效率
32
27
2
2
K
K
)(
2
K
XHL
二元码符号/ bitR
189
• 将信源序列的长度增加,L＝3或L=4,对这些信源序列X进
行编码,并求出其编码效率为 43
信息传输率分别为
二元码符号
二元码符号
/
/
4
3
bitR
bitR
如果对这一信源采用定长二元码编码,要求编码效
率达到96％时,允许译码错误概率δ≤10-5
自信息的方差
2
1
222 )]([)(log)(
i
ii XHppX
所需要的信源序列长度 7
52
2
2
)(
)(
L
190
• 信源编码：
–以提高通信有效性为目的的编码。
–通常通过压缩信源的冗余度来实现。采用的一般方法
是压缩每个信源符号的平均比特数或信源的码率。即
同样多的信息用较少的码率传送,使单位时间内传送的
平均信息量增加,从而提高通信的有效性。
• 信道编码：
–是以提高信息传输的可靠性为目的的编码。
–通常通过增加信源的冗余度来实现。采用的一般方法
是增大码率/带宽。与信源编码正好相反。
191
• 密码：
–是以提高通信系统的安全性为目的的编码。
–通常通过加密和解密来实现。从信息论的观点出发
“加密”可视为增熵的过程,“解密”可视为减熵的过程。
192
• 信源编码理论是信息论的一个重要分支,其理论基础是信源编码的两个
定理。
–无失真信源编码定理：
• 是离散信源/数字信号编码的基础；
–限失真信源编码定理：
• 是连续信源/模拟信号编码的基础。
• 信源编码的分类：
–离散信源编码：
• 独立信源编码,可做到无失真编码；
–连续信源编码：
• 独立信源编码,只能做到限失真信源编码；
–相关信源编码：
• 非独立信源编码。
193
信源符号
信源符号
出现概率 C1 C2
A 0 0 0
B 0 1 1 0
C 1 0 1 1 0
D 1 1 1 1 1 0
信源
{A, B, C, D}
信源
编码器
信道
Error: 10-4
解码 信宿
194
• 码字平均长度
n
i
ii KapK
1
)(
C1 和C2平均长度
K
C2 的效率比 C1高
C2的区分 ：0 表示码字的结束
195
• 信息率
m
L
K
R L log
编码效率
R
XH )(
196
• 最佳码：
–对于某一信源和某一码符号集来说,若有
一唯一可译码,其平均码长小于所有其他
唯一可译码的平均长度。
• 紧致码
–香农（Shannon）
–费诺（Fano）
–哈夫曼（Huffma ）
197
• 香农第一定理指出了平均码长与信源之间的关系,同时
也指出了可以通过编码使平均码长达到极限值,这是一
个很重要的极限定理。
• 香农第一定理指出,选择每个码字的长度Ki满足下式：
香农编码
)(
1
log
i
i
xp
K
或: －log2 p(xi)≤ Ki <1－log2 p(xi)
就可以得到这种码。
这种编码方法称为香农编码
198
• 二进制香农码的编码步骤如下：
⑴将信源符号按概率从大到小的顺序排列,
p(a1)≥ p(a2)≥…≥ p(an)
⑵确定满足下列不等式的整数Ki ,
－log2 p(ai)≤ Ki <1－log2 p(ai)
⑶令p(a1)=0,用Pi表示第i个码字的累加概率，
⑷将Pi用二进制表示,并取小数点后Ki位作为符号ai的编码。
199
例有一单符号离散无记忆信源
• 对该信源编二进制香农码。其编码过程如表所示
)(
54321 xxxxx
xp
X
信源
符号
xi
符号
概率
p(xi)
累加
概率
Pi
-log p(xi) 码长 码字
x1
0 2 00
x2 2 01
x3 3 101
x4 5 11100
x5 5 11101
以i = 3为例:
码字长度：
K4 = [－] = 3
累加概率
Pi= → …
200
• 香农码的平均码长
)(
5
1
i
ii KxpK
熵
)(
XH
编码效率
%78
)(
K
XH
x1
x2
x3
x4
x5
为提高编码效率,首先应达到满
树;如把x4x5换成前面的节点,可减
小平均码长。
不应先规定码长,而是由码树来
规定码字,可得更好的结果。
201
费诺编码
• 费诺编码属于概率匹配编码 。
• 编码步骤如下：
• 将概率按从大到小的顺序排列,令
p(x1)≥ p(x2)≥…≥ p(xn)
• 按编码进制数将概率分组,使每组概率尽可能接近
或相等。如编二进制码就分成两组,编m进制码就
分成m组。
• 给每一组分配一位码元。
• 将每一分组再按同样原则划分,重复步骤2和3,直
至概率不再可分为止。
202
• 例设有一单符号离散信源
)(
54321 xxxxx
xp
X
对该信源编二进制费诺码。
信源
符号
xi
符号
概率
p(xi)
第1
次
分组
第2
次分
组
第3
次
分组
码
字
码
长
x1
0
0 00 2
x4
1
0 010 3
x5
1 011 3
x2
1
0 10 2
x3
1 11 2
信源
符号
xi
符号
概率
p(xi)
第1
分组
第2
分组
第3
分组
第4
分组
码
字
码
长
x1 0 0 1
x2
1
0 10 2
x3
1
0 110 3
x4
1
0 1110 4
x5 1 1111 4
平均码长：K=
编码效率:
η=93%
平均码长：K=
编码效率:
η=%
203
• 平均码长
)()(
5
1
1
i
ii KxpK
)()(
5
1
2
i
ii KxpK
编码效率
%
)(
2
2
K
XH
费诺码比较适合于每次分组概率都很接近的信源
特别是对每次分组概率都相等的信源进行编码时,可达到理
想的编码效率。
204
• 平均码长
• 编码效率
• 费诺码比较适合于每次分组概率都很接近的信源
• 特别是对每次分组概率都相等的信源进行编码时,
可达到理想的编码效率。
)()(
5
1
1
i
ii KxpK
)()(
5
1
2
i
ii KxpK
%
)(
2
2
K
XH
205
例有一单符号离散无记忆信源
• 对该信源编二进制费诺码,编码过程如表:
二进制费诺编码
信源符号 概率 编码 码字 码长
x1 0 00 2
x2
0
1
01 2
x3 0 100 3
x4
0
1
101 3
x5 0 1100 4
x6
0
1 1101 4
x7 0 1110 4
x8
1
1
1
1 1111 4
206
• 信源熵为 H(X)=(比特/符号)
• 平均码长为
• 编码效率为
η=1
• 之所以如此,因为
每次所分两组的
概率恰好相等。
207
哈夫曼编码
• 哈夫曼编码也是用码树来分配各符号的码字。
• 费诺码是从树根开始,把各节点分给某子集,若子
集已是单点集,它就是一片树叶而作为码字。
• 哈夫曼编码是先给每一符号一片树叶,逐步合并
成节点直到树根。
• 哈夫曼(Huffman)编码是一种效率比较高的变长
无失真信源编码方法。
208
• 哈夫曼编码的步骤如下：
⑴ 将信源消息符号按其出现的概率大小依次排列
p(x1)≥p(x2)≥…≥ p(xn)
⑵取两个概率最小的字母分别配以0和1两码元,并
将这两个概率相加作为一个新字母的概率,与未
分配的二进符号的字母重新排队。
⑶ 对重排后的两个概率最小符号重复步骤⑵的过
程。
⑷不断继续上述过程,直到最后两个符号配以0和1
为止。
⑸ 从最后一级开始,向前返回得到各个信源符号
所对应的码元序列,即相应的码字。
209
例5-7 设单符号离散无记忆信源如下,要求对信
源编二进制哈夫曼码。编码过程如下表
)(
7654321 xxxxxxx
xp
X
信源符
号xi
符号概
率p(xi)
编码过程
x1
x2
x3
x4
x5
x6
x7
0
1
0
1
0
1
0
1
0
1
0
1
码字
10
11
000
001
010
0110
0111
在图中读取码字的时候,要
从后向前读,此时编出来的
码字是可分离的异前置码。
210
• 熵
)(
XH
• 平均码长为
)(
7
1
i
ii KxpK
• 编码效率
( ) ( )
96%
H X H X
R K
211
• 哈夫曼的编法并不惟一。
• 每次对缩减信源两个概率最小的符号分配“0”和
“1”码元是任意的,所以可得到不同的码字。只要
在各次缩减信源中保持码元分配的一致性,即能得
到可分离码字。
• 不同的码元分配,得到的具体码字不同,但码长Ki不
变,平均码长也不变,所以没有本质区别；
• 缩减信源时,若合并后的新符号概率与其他符号概
率相等,从编码方法上来说,这几个符号的次序可任
意排列,编出的码都是正确的,但得到的码字不相同。
• 不同的编法得到的码字长度Ki也不尽相同。
哈夫曼编码
212
• 例5-8单符号离散无记忆信源
信源
符号
xi
符号
概率
p(xi)
编码过程
x1
x2
x3
x4
x5
0
1
0
1
0
1
0
1
码字
1
01
000
0010
0011
码字
00
10
11
010
011
213
0
0
0
0
0
0
1
1
x
5
x
4
x
3
x
2
x
1
图 例的二进制哈夫曼码树(编法一)
1
0
0
0
0
1
0
1
1
x
5
x
4
x
3
x
2
x
1
图 例的二进制哈夫曼码树(编法二)
1
214
• 单符号信源编二进制哈夫曼码,编码效率主要
决定于信源熵和平均码长之比。
• 对相同的信源编码,其熵是一样的,采用不同的
编法,得到的平均码长可能不同。
• 平均码长越短,编码效率就越高。
• 编法一的平均码长为
)(
5
1
2
i
ii KxpK
)(
5
1
1
i
ii KxpK
• 编法二的平均码长为
• 两种编法的平均码长相同,所以编码效率相同。
215
• 讨论：哪种方法更好？
• 定义码字长度的方差σ2：
5
1
222 ))((])[(
i
iii KKxpKKE
)()()()( 222221
)()()( 22222
• 第二种编码方法的码长方差要小许多。
• 第二种编码方法的码长变化较小,比较接近于平
均码长。
哈夫曼编码
216
哈夫曼编码
• 第一种方法编出的5个码字有4种不同的码长；
• 第二种方法编出的码长只有两种不同的码长；
• 第二种编码方法更简单、更容易实现,所以更好。
• 结论：
• 在哈夫曼编码过程中,对缩减信源符号按概率由大到
小的顺序重新排列时,应使合并后的新符号尽可能排
在靠前的位置,这样可使合并后的新符号重复编码次
数减少,使短码得到充分利用。
217
m进制哈夫曼编码
• 在编m进制哈夫曼码时为了使平均码长最短,必须使最后
一步缩减信源有m个信源符号。
• 对于m进制编码,若所有码字构成全树,可分离的码字数
必为:
m＋k(m－l)
• 非全树时,有s个码字不用：
• 第一次对最小概率符号分配码元时只取(m－s)个,分别
配以0,1, …,m-s-1,把这些符号的概率相加作为一个新
符号的概率,与其它符号一起重新排列
• 以后每次取m个符号,分别配以0,1,…,m-1；如此下去,直
至所有概率相加得1为止,即得到各符号的m进制码字。
218
• 例:对如下单符号离散无记忆信源编三进制哈
夫曼码
这里：m =3，n =8
• 令k=3，m+k(m－1)=9，则 s = 9－n = 9－8
=1
• 所以第一次取m－s=2个符号进行编码。
219
3进制哈夫曼编码
信源符
号xi
符号概
率p(xi)
编码过程
x1
x2
x3
x4
x5
x6
x7
x8
0
1
0
1
2
0
1
2
0
1
2
码字
0
10
11
12
21
22
200
201
220
0
0
0
0 1
2
1
1
x
5
x
4
x
3
x
2
x
1
图 三进制哈夫曼码树图
2
2
1
x
6
x
8
x
7
221
• 平均码长为
• 信息率为
• 编码效率为
• 哈夫曼的编码效率相当高,对编码器的要求
也简单得多。
222
结论
• 香农码、费诺码、哈夫曼码都考虑了信源的统计特
性,使经常出现的信源符号对应较短的码字,使信源
的平均码长缩短,从而实现了对信源的压缩；
• 香农码有系统的、惟一的编码方法,但在很多情况
下编码效率不是很高；
• 费诺码和哈夫曼码的编码方法都不惟一；
• 费诺码比较适合于对分组概率相等或接近的信源编
码,费诺码也可以编m进制码,但m越大,信源的符号
数越多,可能的编码方案就越多,编码过程就越复杂,
有时短码未必能得到充分利用；
• 哈夫曼码对信源的统计特性没有特殊要求,编码效
率比较高,对编码设备的要求也比较简单,因此综合
性能优于香农码和费诺码。
223
习题
• 5-11
224
游程编码对象和性质
• 香农编码、费诺编码、哈夫曼编码主要是
针对无记忆信源。
– 当信源有记忆时上述编码效率不高；
• 游程编码对相关信源编码更有效；
• 香农编码、费诺编码、哈夫曼编码属于无
失真信源编码；
• 游程编码属于限失真信源编码。
225
游程编码
• 游程：
–数字序列中连续出现相同符号的一段。
• 二元序列的游程：只有“0”和“1”两种符号。
– 连“0”这一段称为“0”游程,它的长度称为游程
长度L(0)；
– 连“1”这一段称为“1”游程,它的游程长度用L(1)
表示。
226
游程编码
• 二元独立序列游程长度概率
• 若规定二元序列总是从“0”开始,第一个游程是“0”游
程,则第二个游程必为“1”游程,第三个又是“0”游
程……。
• 对于随机序列,游程长度是随机的其取值可为1,2,3,…，
直至无穷。
• 游程长度序列/游程序列：用交替出现的“0”游程和
“1”游程长度表示任意二元序列。
• 游程变换：
– 是一种一一对应的变换,也是可逆变换。
例如：二元序列000101110010001…
可变换成如下游程序列 31132131
227
分组码
定理（Kraft不等式）：设信源符号集
为 ，码符号集为 ，对
信源编码，相应的码字为 ，其
分别对应的码长为 ，则长度为
的r进制异前置码存在的充要条件是
1 2( , ,..., )rX x x x1 2( , ,..., )qS s s s
1 2( , ,..., )qW W W W
1 2, ,..., ql l l, 1,2,...,il i q
1
1
q
i
lir
228
等长信源编码定理
• 对于一个无记忆离散信源中的每一个符号，若采
用相同长度的不同码字代表相应的符号，就称为
等长编码。
• 若对一个简单的信源进行无失真编码，那么信源
存在惟一可译定长码时必须满足的条件是 ，
其中l是等长码的码长。
lrq
例：若信源S共有q=4个符号，进行二进制等长
编码，码符号个数为r=2，则S存在惟一可译定
长码时，码长l必须不小于2。
229
等长信源编码定理
1 2
N
N
1 2
S
S ( , 1,2... ), ...
( ... )
log
log
2( ) log
N
N
j j j j j
r
N l
q S N
a j q a s s s
X x x x
q r
l q
N r
l
r q
N
如果对有 个符号的信源 的 次扩展 进行编码，
信源符号 ；
码符号集为 。若要编得等长惟一可译
码，必须满足
两边取对数得
当 二进制码 时为
230
等长信源编码定理
定理（等长信源编码定理）：设有离散无记忆信源，其熵
为H(S) ，若对信源长为N的符号序列进行等长编码，
设码字是从r个码符号集中选取l个码元构成，对于任
意 ，只要满足
则当N足够大时，几乎可实现无失真编码。反之，当
时，不可能实现无失真编码，而当N足够大时，译码错误
概率近似等于1。
0
r
SH
N
l
log
)(
r
SH
N
l
log
2)(
231
等长信源编码定理
• 该定理是在平稳无记忆离散信源的条件下
论证的，但同样适于平稳有记忆信源，只
是要求信源的极限熵 和极限方差
存在，并将式中的H(S)改为 。)(SH
2
)(SH
q
N
l
SH
N
l
r
log
)()(2
分布时当信源符号具有等概率
时为二进制码当
232
等长信源编码定理
将定理中的条件改写成
l logr>NH(S)
左边表示长为l的码字符号序列能载荷的最大
信息量。
右边表示长为N的信源序列平均携带的信息量。
故只要码字传输的信息量大于信源序列携
带的信息量，总可以实现几乎无失真编码。
233
等长信源编码定理
编码速率：
编码效率：
取等号时得到最佳编码效率。
符号比特/
log
N
rl
R
rl
SNH
R
SH
log
)()(
0
)(
)(
)(
SH
SH
SHR
故
由定理知
234
等长信源编码定理
当允许错误概率 时，信源序列长度
必满足
2
2
2
2
)1()(
)]([
)1)((
)]([
SH
sID
N
SH
sID
N
i
i
故
由于
小于p
235
等长信源编码定理
例 设一简单离散信源如下
对其进行等长近似无失真编码，若取编码效
率为95%，差错概率 ，求信源符号
联合编码长度。
610
8
1
8
1
4
1
2
1
4321 ssss
P
S
236
等长信源编码定理
解：
6
2
2
2
22
1
4
1
)1()(
)]([
)]([])()[log()]([
)(log)()(
SH
SID
N
SHspspsID
spspSH
i
q
i
iii
i
ii
故
237
变长编码定理
若对该信源进行变长编码
%100
2log
4
7
4
7
1
log
)(
4
7
3
8
1
3
8
1
2
4
1
1
2
1
)(
111110100
8
1
8
1
4
1
2
1
1
4321
rl
SNH
lspl
ssss
P
S
q
i
ii
编码效率：
平均码长：
变长码：
238
变长编码定理
对一个信源中的不同符号采用不同长度的
码字表示，就称为变长编码或不等长编码。
要实现无失真的信源编码，变长码必须是
惟一可译码。为了能即时进行译码，变长
码还必须是即时码。
239
变长编码定理
基本思想：
一般离散无记忆信源输出的各消息概率是不
等的，若对概率大的采用较短的码字，对
概率小的采用较长的码字，使编码的平均
码长最短，也实现了与信源统计特性相匹
配。
240
变长编码定理
定理：对于熵为H(S)的离散无记忆信源
若用具有r个码符号的集 对其进行编
码，则一定存在一种编码方法构成惟一可译码，
其平均码长 满足：
1 2
1 2
...
( ) ( ) ... ( )
q
q
s s sS
P p s p s p s
1 2( , ,..., )rX x x x
r
SH
l
r
SH
log
)(
1
log
)(
241
变长编码定理
定理：设离散无记忆信源S的熵为H(S)，其N次扩展信源为
SN
其信源熵为H(SN)。用码符号集 对SN进行编
码，总可以找到一种编码方法构成惟一可译码，使信源S
的每个信源符号所需的码字平均码长满足：
1 2
1 2
...
( ) ( ) ... ( )
N
N
N
q
q
a a aS
p a p a p aP
)( 21 rxxxX
)(lim
)(
1
)(
log
)(1
log
)(
SH
N
l
N
SH
NN
l
SH
r
SH
NN
l
r
SH
r
N
N
r
N
r
N
时，则当
或
242
变长编码定理
是无记忆N次扩展信源SN中每个信源符号ai所
对应的平均码长
式中， li是ai所对应的码字长度。
i
q
i
iN lapl
N
1
)(
Nl
l Nl N /
和 两者都是每个原始信源符号si所需
要的码符号的平均数。
前者是直接对单个信源符号si进行编码。
后者是对N次扩展信源SN符号序列ai进行编码。
243
变长编码定理
• 编码速率：编码后平均每个信源符号能载荷的
最大信息量。
信源符号比特 /log
log
rl
N
rl
R
N
码符号比特等长码
码符号比特变长码
/
/
'
/
/
'
Nl
H
R
Nl
H
R
N
码率：编码后平均每个码符号携带的信息量，
即编码后信道的信息传输率。
244
变长编码定理
编码效率：
用来衡量各种编码距极限压缩值的情况。
码的剩余度：
r
R
l
SH
rl
SH
R
SH r
log
')(
log
)()(
l
SH r )(11
')(2 Rr 时二进制码当
245
变长编码定理
[1]香农编码方法
第一步：将信源发出的N个消息符号按其概率的递减次序排
列。
第二步：按下式计算第i个消息的二进制代码组的码长li并取
整
第三步：计算第i个消息的累加概率 。
第四步：将累加概率Pi变换成二进制数。
第五步：去掉小数点，根据码长取小数点后li位数作为第i个
消息代码组
1)(log)(log iii splsp
1
1
)(
i
k
ki spP
1)(log ii spl
246
变长编码定理
例：
信源符号si 符号概率p(si) 累加概率Pi -
logp(si)
代码组
长度li
二进制代
码组
S1 0 3 000
S2 3 001
S3 3 011
S4 3 100
S5 3 101
S6 4 1110
S7 7 1111110
7654321 sssssss
P
S
247
变长编码定理
该信源共有5个3位的码字，且各码字之间至少有
一位不相同，故是惟一可译码，同时这7个码
字都不是延长码，属于即时码。
码元比特码率：
符号码元平均码长：
/
)(
'
/)(
1
l
SH
R
lspl
q
i
ii
248
变长编码定理
[2]费诺码
第一步：将信源符号按其概率的递减次序排列；
第二步：将它们分成概率之和近似相等的两组，并
给予一定的编码规则，如下支路为1，上支路为0；
第三步：将每一大组的符号再分成概率之和近似相
等的两组，并各赋一个码元，如下支路为1，上支
路为0 ；
第四步：重复步骤3，直至每组只剩下一个信源符
号为止，所对应的码符号序列即为所编码字。
249
变长编码定理
例：
符号si 概率p(si) 第一次 第二次 第三次 第四次 二元码组
S1
0
0 00
S2 1 0 010
S3 1 011
S4
1
0 10
S5
1
0 110
S6 1 0
1
1110
S7 1111
7654321 sssssss
P
S
250
变长编码定理
码元比特码率：
符号码元平均码长：
/
)(
'
/)(
1
l
SH
R
lspl
q
i
ii
费诺码比香农码的平均码长小，消息传输率
大，编码效率高。
香农编码法冗余度较大，实用性不强，但具
有重要的理论意义。
251
变长编码定理
平均码长为最短的即时码称为最佳码，又称为紧致
码。
对于某个给定分布的离散信源，存在一个二元最佳
码，此码满足如下性质：
（1）概率大的信源符号所对应的码长必不大于概
率小的信源符号所对应的码长。
（2）两个最小概率的信源符号所对应的码字必具
有相同的码长，且其差别必是最后一位码元不同。
252
变长编码定理
[3]霍夫曼编码——最佳变长编码
第一步：将信源符号按其概率的递减次序排列；
第二步：从最小概率的两个消息开始编码，并给予
一定的编码规则，如下支路为1，上支路为0；
第三步：将已编码的两个消息对应概率合并，并重
新按概率大小排队，重复步骤2；
第四步：重复步骤3，直至合并概率达为止，划
出由每个信源符号概率到的路径，记下沿路径
的1和0；
第五步：编码按后编先出的方式进行。
253
变长编码定理
• 例：
8
1
8
1
4
1
2
1
4321 ssss
P
S
消息（U）概率（pi）
u1 1/2
u2 1/4
u3 1/8 0
u4 1/8 1
1/2
1/4 0
1/4 1
1/2 1
1/2 0
编码C’
1
01
000
001
254
变长编码定理
• 例：
si p(si) 编码过程 码组
S1
0
1
0
1
0
1
0
1
0
1
0
1
10
S2 11
S3 000
S4 001
S5 010
S6 0110
S7 0111
7654321 sssssss
P
S
255
变长编码定理
• 可见，哈夫曼码的平均码长最小，消息传输
率最大，编码效率最高。
码元比特码率：
符号码元平均码长：
/
)(
'
/)(
1
l
SH
R
lspl
q
i
ii
256
变长编码定理
哈夫曼编码方法得到的码不是惟一的，原因是：
（1）每次对信源缩减时，赋予信源最后两个概率
最小的符号，用0和1是任意的，所以可得到不同
的码，但不会影响码长。
（2）新合并的概率与其他符号的概率相等时，在
缩减信源时，其位置次序是任意的，故可得到不
同的码，并且对码长有影响。
257
变长编码定理
在编码中，将新合并的概率放在上支路，可
减少再次合并的次数，充分利用短码，缩
短码长的方差，编出的码更接近于等长码。
258
变长编码定理
哈夫曼码是用概率匹配方法进行信源编码的，
有两个明显的特点：
（1）该方法保证了概率大的符号对应于短码，
概率小的符号对应于长码，充分利用了短
码。
（2）缩减信源的最后两个码字总是最后
一位不同，从而保证了是即时码。
259
变长编码定理
误差扩散：噪声所影响的不仅是被干扰的码
元，而是一直要扩散下去影响后面的一系
列码元。
解决方法：定期清洗或加检错纠错码。
260
变长编码定理
速度匹配：信源输出速率是变化的，而信道
传送的信息率是固定不变的，因而存在速
率匹配问题。
解决方法：采用缓冲存储器。
261
变长编码定理
概率匹配：变长码是与信源统计特性相匹配
的无失真信源编码，信源统计特性的变化
对变长码影响很大。
解决方法：扩张信源。
262
变长编码定理
例：若有一信源
每秒钟发出个信源符号。将此信源的输
出符号送入某一个二进制信道中进行传输
（设信道是无噪无损的），信道每秒钟只
能传递2个二元符号。试问信源不通过编码
能否直接与信道连接？若通过适当编码能
否在此信道中实现无失真传输？若能连接，
试说明如何编码并说明原因。
21 ss
P
S
263
变长编码定理
• 解：信源熵和信源输出的信息速率为
• Rt=*H(S)= 比特/秒
符号比特 /)(log)()(
1
q
i
ii spspSH
信道的最大信息传输率为
C=1 比特/符号
Ct=2*C=2 比特/秒
264
变长编码定理
可见， Rt < Ct
根据无失真信源编码定理可知，总能对信源的输出
进行适当的编码，使此信源能在此信道中进行无
失真传输。
265
变长编码定理
如果不对信源进行编码，直接将信源符号s1
以“0”符号传送， s2以“1”符号传送，此
时因为信源输出为(二元信源符号/秒)，
大于2(二元信道符号/秒)，就会使信道输出
端造成信源符号的堆积，信息不能按时发
送过去。所以，不通过编码此信源不能直
接与信道连接。
266
变长编码定理
若要连接，必须对信源的输出符号序列进行
编码，也就是对此信源的N次扩展信源进行
编码。但扩展次数越大，编码越复杂，设
备代价越大，所以尽量使扩展次数小，又
能使信源在此信道中无失真地传输。
267
变长编码定理
先考虑对二次扩展信源进行霍夫曼编码，得
二元霍夫曼码为
0,11,100,101或0,10,110,111
得平均码长为 码符号/信源符号
22122111
2 ssssssss
P
S
268
变长编码定理
二次扩展编码后，送入信道的传输速率为
*= 码符号/秒
仍然大于 2 二元信道符号/秒
所以必须考虑三次扩展信源编码。
269
变长编码定理
二元霍夫曼码为
0,101,100,110,11100,11101,11110,11111
222122212221112121211111
3 ssssssssssssssssssssssss
P
S
270
变长编码定理
得平均码长为 码符号/信源符号
送入信道的传输速率为
*= 码符号/秒
小于 2 二元信道符号/秒
此时，就可以在信道中进行无失真传输了。
271
变长编码定理
r元哈夫曼码：
编码过程中构成缩减信源时，将r个概率最小
的符号合并，并且分别用0,1,…,(r-1)码符号
表示。
272
变长编码定理
为了使平均码长最短，必须使最后一个缩减
信源有r个信源符号，因此，信源符号个数
必须满足
若不满足则采用虚设方法，增补一些概率为
零的信源符号。
表示信源缩减的次数。其中，
rrq )1(
273
变长编码定理
[4]算术编码
分组码或块码是建立在符号与码字相对应的
基础上的，而且不考虑符号间的相关性。
这样会使信源编码的匹配原则不能充分满
足，编码效率会有所损失。
为克服这种局限性，需要研究非分组码的编
码方法，算术码即为其中之一。
274
变长编码定理
算术编码的基本思路是：从全序列出发，将
各信源序列的概率映射到[0，1]区间上，使
每个序列对应着区间内的一点，也就是一
位二进制小数。这些点把[0，1]区间分成许
多小段，每段的长度等于某一序列的概率。
再在段内取一个二进制小数，其长度可与
该序列的概率匹配，达到高效率编码的目
的。
275
变长编码定理
定义各符号的累积概率为
由上式可得 P1=0, P2= p1, P3= p1+ p2
而且 pr=Pr+1 –Pr
由于Pr和Pr+1 都是小于1的正数，可以用[0，
1]区间内的两个点来表示，则pr就是这两点
间小区间的长度。
1
1
r
i
ir pP
276
变长编码定理
如图所示，不同的符号就有不同的小区间，
它们互不重叠，所以可以用这种小区间内
的任一点作为该符号的代码。
p1 p2 p3
0(P1) P2 P3 P4 1...
...
277
变长编码定理
有一序列 S=011，这种3个二元符号的序列可
按自然二进制数排列，则它的累加概率为
P(S)= p(000)+ p(001)+ p(010)
如果S后接一个“0”，则累加概率
为
P(S,0)= p(0000)+ p(0001)+ p(0010)+
p(0011)+p(0100)+ p(0101)
= p(000)+ p(001)+ p(010)
=P(S)
278
变长编码定理
因为当4个二元符号的最后一位是“0”和
“1”时，根据归一律，它们的概率和应
等于前3位的概率，即
p(0000)+ p(0001)= p(000)
如果S后接一个“1”，则累加概率为
P(S,1)= p(0000)+ p(0001)+ p(0010)+
p(0011)+p(0100)+ p(0101) +p(0110)
= P(S) +p(0110)= P(S) +p(S) p0
279
变长编码定理
由于单符号的累加概率P0=0, P1= p0
上面两式可统一写作
P(S,r)=P(S) +p(S)Pr r =0,1
推广到多元序列得一般的递推公式
P(S,r)=P(S) +p(S)Pr
以及序列的概率公式
p(S,ar)=p(S)pr
280
变长编码定理
若采用累积概率Ps表示码字C(S) ，符号
概率p(S)表示状态区间A(S) ，则得到
算术编码的基础公式
C(S,x)=C(S) +A(S)Px
A(S,x)=A(S)px
281
变长编码定理
例: 已知信源
试对1011进行算术编码。
①二进制信源符号只有两个“0”和“1”，设
置
小概率Pc＝1/4，大概率Pe=1-Pc＝3/4
4/34/1
10
X
282
变长编码定理
②设C为子区的左端起始位置，L为子区的长度(
等效于符号概率)，根据①：
符号“0”的子区为[0,1/4)；
子区左端C＝0，
子区长L＝1/4；
符号“1”的子区为[1/4，1)；
子区左端C＝1/4，
子区长L＝3/4。
283
变长编码定理
③在编码运算过程中，随着消息符号的出现，子区
按下列规则缩小。
规则A： 新子区左端＝
前子区左端+前子区长度*当前子区左端；
规则B： 新子区长度=
前子区长度*当前子区的长度。
④初始子区为[0，1)，即0＜=x＜1
284
变长编码定理
步序 符号 C L
(1) 1 1/4 3/4
(2) 0 1/4+0*3/4=1/4 3/4*1/4=3/16
(3) 1 1/4+1/4*3/16=19/64 3/16*3/4=9/64
(4) 1 19/64+1/4*9/64=85/256 9/64*3/4=27/256
0 1/4
85/256 28/64
1
19/64
285
变长编码定理
最后的子区左端(起始位置)
C＝(85/256)d=()b
最后的子区长度
L＝(27/256)d＝()b
最后的子区右端(子区间尾)＝(112/256)d=()b
编码结果：子区间头尾之间取值，其值为，可编码为
011，原来4个符号1011被压缩为三个符号011。
286
6 信道编码
• 信道编码的基本概念
• 有噪信道编码
• 线性分组码
287
信道编码的基本概念
• （一）信道编码的地位和作用
• 数字通信系统的主要技术指标：
• （1）传输速率
[1]码元传输速率：
指携带数据信息的信号单元，每秒钟通
过信道传输的码元数称为码元传输速率，
单位是波特，故简称波特率，又称为调
制速率。
288
信道编码的基本概念
[2]比特传输速率：
每秒钟通过信道传输的信息量称为比特
传输速率.
单位是比特/秒，简称比特率。
289
信道编码的基本概念
• 对二进制来说，每个码元的信息含量为1
比特，因此，二进制的码元传输速率与比
特传输速率在数值上是相等的。
对M进制来说，每一码元的信息含量为
logM比特，如果码元传输速率为rs波
特，则相应的比特传输速率rb为rs
logM。
290
信道编码的基本概念
• （2）差错率
• [1]码元差错率：在传输的码元总数中发生
差错的码元数所占的比例（平均值），简
称误码率，用符号pE表示。
[2]比特差错率：在传输的比特总数中发生
差错的比特数所占的比例（平均值），用符
号pBE表示。在二进制传输系统中，码元差错
率就是比特差错率。
[3]码组差错率：在传输的码组总数中发生差
错的码组数所占的比例（平均值）。
291
信道编码的基本概念
（3）可靠性
在数字通信系统中信息的传输（或存储）遇
到的主要问题就是:
在传输过程中出现差错问题，也就是传输的
可靠性问题。
292
信道编码的基本概念
出错的主要原因是
(1)不同的传输系统有不同的性能以及在
传输过程中干扰不同；
(2)不同用户或不同的传输系统对差错率
的要求不同。
293
信道编码的基本概念
降低误码率通常有两种途径：
一是降低信道（包括调制解调器、传输媒介）
本身所引起的误码率；
二是采用信道编码，在数字通信系统中
增加差错控制设备。
294
信道编码的基本概念
降低信道所引起的误码率的主要方法有：一
是选择合适的传输线路；
二是改进传输线路的传输特性或增加发送信
号的能量；
三是用潜在抗干扰性较强的调制解调方案。
295
信道编码的基本概念
• 某些情况下，信道的改善可能较困难或不
经济，此时就要采用信道编码。
信
息
源
噪声源
变
换
器
调
制
器
发
射
机
信道
接
收
机
解
调
器
反
变
换
器
信
息
宿
接收端发送端 信道
有编码的数字通信系统框图
信
源
编
码
器
信
道
编
码
器
信
道
译
码
器
信
源
译
码
器
296
信道编码的基本概念
（二）信道编码的基本思想和分类
差错的基本形式：
一是随机错误，即数据序列中前后码元之间
是否发生错误彼此无关，产生这种错误的
信道称为无记忆信道或随机信道。
二是突发错误，即错误之间有相关性，
成串出现，称这类信道为突发差错信道。
297
信道编码的基本概念
• 设信道输入的发送序列为00000，由于干扰，
信道输出的接收序列为00100，相当于信道
中有一个差错序列00100
发送序列与接收序列对应位的模2和就是信
道的错误图样。
这个差错序列与发送序列逐为模2相加，
就得到了接收序列，称这个差错序列为
信道错误图样。
298
信道编码的基本概念
• 信息序列：信源编码器输出的数字序列M，
通常是由二元符号0和1组成，且符号0和1
是相互独立等概率的。
信道编码：按一定规律在待发送的信息码
中加入一些人为制作的码元，以保证传输
过程可靠性。
检错码：用于检测差错的信道码。
纠错码：可以检测和校正差错的信道码。
299
信道编码的基本概念
• 从原理分：
• 如果规则是线性的，即码元之间的关系是
线性关系，则称这类信道编码为线性码，
否则称为非线性码。
从信息序列所对应的编码方式分：
如果将信源的信息序列按照独立分组进
行处理和编码，则称为分组码，否则称为
非分组码。
300
信道编码的基本概念
• 在线性分组码中，通常把码组中所含“1”
的数目定义为码组重复（码重），记为
W(c)。
把两个码组中对应位置上不同分量数
目定义为码组距离，记为d(ci, cj)。
码组间最小距离dmin的大小直接决定
线性分组码的检错能力。
301
信道编码的基本概念
若要发现e个独立随机错误则要求：
若要纠正t个独立随机错误则要求：
若要发现e个独立随机错误，同时能纠正t个
独立随机错误则要求：
1min ed
12min td
1min etd
302
信道编码的基本概念
(n,1)重复码
（1）不重复：最简单但没有任何抗干扰能力，
既不能发现更不能纠正错误。
（2）重复一次：效率降低一倍但在传输过程
中允许错一位，能发现但不能纠正错误。
（3）重复两次：效率降低两倍，能发现两个
错误或纠正一个错误。
303
信道编码的基本概念
偶（奇）监督码
编码规则：
上式是模2相加和。这种偶数监督码，要保证
码组中“1”的个数是偶数，即满足在码组
中信息位和监督位模2和为0，能发现奇数
个差错。
),,,(
2
0
1210
n
i
inn cccccc
304
信道编码的基本概念
例：
同理可设计奇数监督码，只是码组中“1”的
个数是奇数。
这类偶（奇）监督码可记为(n,n-1)码。
c0 c1
0 0
0 1
1 0
1 1
c0 c1
0 0
0 1
1 0
1 1
c2
0
1
1
0
305
信道编码的基本概念
• (n,1)重复码和(n,n-1)偶（奇）监督码虽然
构造都很简单，但性能远不能满足既有可
靠性又有有效性的要求。
306
信道编码的基本概念
• 对(n,1)重复码，随着码长n增大，可靠性
虽可不断提高，但编码效率 在不断
降低。 n
1
1
1
n
n
对(n,n-1)偶（奇）监督码，随着码长n增
大，有效性很高即编码效率 ，但
抗干扰性很差。
307
信道编码的基本概念
线性分组码在构造时，
将输入信息分成k位一组进行编码，
按照一定线性规律加上人为多余的码元，
构成n(n>k)位一组的输出，
故可采用符号(n,k)表示。
308
信道编码的基本概念
• 其中n表示输出的码组长度，k表示输入信
息分组，即输出码中信息码位数，余下的
r=n-k位码元表示在编码过程中人为加入的
多余码元。
这些多余码元是供接收端检查、纠正
在传输中产生错误的码元，故称其为
监督码元或校验码元。
309
信道编码的基本概念
（三）差错控制基本方式
有两类：
一类是接收端检测到传输的码字有错后，收
端译码器自动地纠正错误；
另一类是收端接收到错误后，通过反馈信
道发送一个应答信号，要求发端重传有错
误的消息，从而达到纠正错误的目的。
310
信道编码的基本概念
• 在数字和数据的信息与通信系统中，利用信道编
码提高系统的可靠性，控制差错，主要方式有四
种：
• （1）前向纠错(FEC)
发端 收端
纠错码
优点：不要反馈信道，适于广播系统，译码延时
固定，较适于实时传输系统。
缺点：要求预先确定信道的差错统计特性。
311
信道编码的基本概念
• （2）反馈重传(ARQ)
发端 收端检错码
应答信号
优点：只需少量的多余码元就能获得极低的输
出误码率，检错码基本与信道的差错统计特性
无关。
缺点：要反馈信道，不能用于单项传输系统，
也难以用于同播系统，控制较复杂，不大适于
实时传输系统。
312
信道编码的基本概念
• （3）混合纠错(HEC)
发端 收端纠检错码
应答信号
具有FEC和ARQ的优点，避免了FEC方式所需
的复杂译码器及不能适应差错能力变化的缺点，
还能克服ARQ方式信息连贯性差，有时通信效率
低的缺点。特别选用于环路延时大的高速传输系
统（如卫星系统）中。
313
信道编码的基本概念
• （4）信息反馈(IRQ)
发端 收端数据信息
数据信息
优点：不需要纠错、检错编译码器，控制设备
和检错设备均较简单。
缺点：发端需要一定容量的存储器以存储发送
码组，适用于传输速率较低、数据信道差错率
较低、具有双向传输线路及控制简单的系统中。
314
有噪信道编码
• 信道的输入和输出端连接着编码器和译码
器，形成了一个新的信道，将这种变换后
具有新特性的信道称为编码信道。
编码器 信道
信源编码器
X
译码器
Y
信源译码器
编码信道
315
有噪信道编码
• 在有噪信道中传输消息是会发生错误
的，错误概率和信道的统计特性、译
码过程以及译码规则有关。
316
有噪信道编码
• 设信道输入符号集为 ，输出符
号集为 。若对每一个输出符
号yj都有一个确定的函数F(yj)，使yj对应惟
一的一个输入符号xi，则称这样的函数为译
码规则，记为
},2,1,{ rixX i
},2,1,{ sjyY j
sjrixyF ij ,2,1;,2,1)(
显然，对于有r个输入、s个输出的信道，
按上述定义可得到译码规则有rs种。
317
有噪信道编码
• 例：已知信道矩阵和两种译码规则
)()(
)]()()[(
3
1
)|(
3
1
)(
)]()()[(
3
1
)|(
3
1
)(
)(
)(
)(
)(
)(
)(
*,
*,
23
32
11
33
22
11
BpAp
xypBp
xypAp
xyF
xyF
xyF
B
xyF
xyF
xyF
AP
EE
xXY
E
xXY
E
318
有噪信道编码
在确定译码规则F(yj)=xi后，信道输出端接收
到的符号为yj，而发送的不是xi ，就认为有
错误，这种错误概率p(e|yj)称为条件错误概
率.
则译码的条件正确概率为
条件错误概率与条件正确概率间的关系
)|(]|)([ jijj yxpyyFp
]|)([1)|(1)|( jjjij yyFpyxpyep
319
有噪信道编码
• 因为译码过程有统计平均作用，经过译码
后的平均错误概率pE为
s
j
jjjE yepypyepEp
1
)|()()]|([
选择译码规则总的原则是使pE最小，
上式右边是非负项之和，应使每一项最小，
因为p(yj)与译码规则无关，故要使p(e|yj)
最小。
320
有噪信道编码
• 为了使p(e|yj)最小，就应使p[F(yj) |yj]最大，
即选择译码函数F(yj)=x*使之满足对所有i
)|()|*( jij yxpyxp
因此，如果采用的译码函数对于每一个输出译码符
号均译成具有最大后验概率的那个输入符号，则信
道错误概率就能最小。这个规则称为最大后验概率
规则或最小错误概率准则。
321
有噪信道编码
根据贝叶斯定律，上式可写成
为了便于计算，忽略信源的统计特性，选
择译码函数F(yj)=x*使之满足对所有i
称为极大似然译码规则。
)|(*)|( ijj xypxyp
)(
)()|(
)(
*)(*)|(
j
iij
j
j
yp
xpxyp
yp
xpxyp
322
有噪信道编码
• 平均错误概率
*,
1
1
1
)()*()(
])([)(
)])([1
)}|)([1){(
)|()(
xXYYXY
YXY
s
j
jj
s
j
jjj
s
j
jjE
xypyxpxyp
yyFpxyp
yyFp
yyFpyp
yepypp
323
有噪信道编码
用条件概率表示
如果p(x)是等概率的p(x)=1/r，则
此时译码错误概率可以用信道矩阵中的元素，去掉
每列中的F(yj)=x*项，求和来表示。
平均正确概率为
*,
)()|(
xXY
E xpxypp
YY
EE yxpyyFppp )*(])([1
*,
)|(
1
xXY
E xyp
r
p
324
有噪信道编码
费诺不等式
表明了平均错误概率pE与信道疑义度H(X|Y)
间的关系。
)1log()()|( rppHYXH EE
可知，接收到Y后关于X的平均不确定性分
为两部分：一是接收到Y后是否产生错误的
不确定性；二是错误发生后，到底是哪个输
入符号发送而造成错误的不确定性。
325
有噪信道编码
例：已知信道矩阵
并设p(x1)=1/2, p(x2)=p(x3)=1/4, 分别用最小
错误概率准则和最大似然译码准则确定相
应的译码规则，并计算平均错误概率。
2
1
6
1
3
1
3
1
2
1
6
1
6
1
3
1
2
1
P
326
有噪信道编码
解：由于输入符号不是等概率分布，所以对于最小
错误概率准则必须根据联合概率的大小来选择。
p(x1y1)=1/4, p(x2y1)=1/24,p(x3y1)=1/12
p(x1y2)=1/6, p(x2y2)=1/8,p(x3y2)=1/24
p(x1y3)=1/12, p(x2y3)=1/12,p(x3y3)=1/8
故译码规则是
F(y1)=x1, F(y2)=x1, F(y3)=x3
327
有噪信道编码
对于最大似然译码准则，可以直接从信道
矩阵的传递概率来选择，译码规则是
F(y1)=x1, F(y2)=x2, F(y3)=x3
平均错误概率为
pE=1/24+1/12+1/6+1/24+1/12 +1/12
=12/24
p’E=1/24+1/12+1/8+1/24+1/12 +1/12
=11/24< pE
328
有噪信道编码
• 选择最佳译码规则只能使错误概率pE有限
地减小，无法使其任意的小。要想进一步
减小错误概率，必须优选信道编码方法。
329
有噪信道编码
• （1）简单重复编码
X Y
a1=0
a2=1
b1=0
b2=1
1-p=
1-p
p
p
2
*,
2211
10)(
2
1
)|(
1
)(,)(
xXY
E xyp
r
p
xyFxyF最佳译码规则
330
有噪信道编码
000=b1
010=b3
100=b5
001=b2
011=b4
101=b6
110=b7
111=b8
a1 = 000
010=a3
100=a5
001=a2
011=a4
101=a6
110=a7
a8= 111
二元对称信
道的三次扩
展信道
未用
码字
许用
码字
输出端接
收序列
331
有噪信道编码
43222
2223
*,
88878615
84131211
103)
(
2
1
)|(
1
)(,)(,)(,)(
)(,)(,)(,)(
xXY
ijE abp
M
p
abFabFabFabF
abFabFabFabF
最佳译码规则
332
有噪信道编码
此时可采用“择多译多”的译码原则，即根
据信道输出端接收序列中0多还是1多，如
果0多译码器就判决为0，1多就判决为1。
同样可得
pE =错3个码元的概率
+错2个码元的概率
=3*10-4
333
有噪信道编码
• 如果进一步增大重复次数n，M仍取2，可得
pE能继续降低，但同时R=logM/n也要减小。
• 由此可见，利用简单重复编码来减小平均错
误概率是以降低信息传输率为代价的。
334
有噪信道编码
• （2）消息符号个数M
• 在一个二元信道的n次无记忆扩展信道中，
输入端共有2n个符号序列可能作为消息符
号，现仅选其中M个作为消息符号传递，则
当M选得大， pE也跟着大，R也大。
335
有噪信道编码
(1)n=3,M=2, pE=3*10
-4
R=logM/n=1/3比特/码符号
(2)n=3,M=4, pE=2*10
-2
R=logM/n=2/3比特/码符号
(3)n=3,M=8, pE=3*10
-2
R=logM/n=1比特/码符号
336
有噪信道编码
（3）(5,2)线性码
采用(5,2)线性码，并适当增大n和M，可以得
到低的平均错误概率和较好的信息传输速
率。
n=5,M=4, pE=*10
-4
R=logM/n=2/5比特/码符号
337
有噪信道编码
输入符号的4个码字采用如下编码方法：
所以，输入端发送序列为
00000，01101，10111，11010
35142132211
54321
,,,,
)(
iiiiiiiiiii
iiiiii
aaaaaaaaaaa
aaaaaa
338
有噪信道编码
00000
00100
10000
00001
01000
10001
00011
00010
00000 00000
扩展信道
译码规则发送码字 输出端接收序列
339
有噪信道编码
01101
01001
11101
01100
00101
11100
01110
01111
01101 01101
扩展信道
译码规则发送码字 输出端接收序列
340
有噪信道编码
10111
11111
10110
10101
00111
00110
10100
10011
10111 10111
扩展信道
译码规则发送码字 输出端接收序列
341
有噪信道编码
11010
11110
01010
11011
10010
01011
11001
11000
11010 11010
扩展信道
译码规则发送码字 输出端接收序列
342
有噪信道编码
（4）汉明距离
长度为n的两个二进制序列（码字） 之间
的距离是指 对应位置上码元取值不同
的个数，用符号 表示。
例如：
若令
ji 和
ji 和
),( jiD
3),(111100101111 jiji D
和运算。表示模其中
则
2
),(
),(),(
1
2121
n
k
jiji
jjjjiiii
kk
nn
yxD
yyyxxx
343
有噪信道编码
汉明距离满足以下性质：
（1）非负性
（2）对称性
（3）三角不等式
时等式成立。当且仅当 ji
jiD
0),(
),(),( ijji DD
),(),(),( jikjki DDD
344
有噪信道编码
在二进制码C中，任意两个码字的汉明距离的
最小值称为该码C的最小距离，即
最小距离Dmin越大，受干扰后，越不容易把
一个码字变为其他码字，因而平均错误概
率pE越小。
故在选择编码规则时，应使码字间的距离越
大越好。
CccccccDD jijiji ,)},(min{min
345
有噪信道编码
• （5）用汉明距离表示极大似然译码规则
• 设码字xi与yj之间的距离为D，则表示在
传输过程中有D个位置发生了错误，n-D
个位置没有错误。
)(
2211
)|()|()|()|(
Dn
nn
ppxypxypxypxyp Dijijijij
二进对称信道的传输错误概率为p，当信
道是无记忆时，编码后信道的传递概率为
当p<时，D越大 p(yj |xi)越小
346
有噪信道编码
极大似然译码规则可表示为：当收到码字yj
后，在输入码字集 中寻找一个
x*，使之与yj的距离（汉明距离）最短。
即选取译码函数F(yj)=x*使之满足
),()*,( min jij yxDyxD
},2,1,{ rixi
347
有噪信道编码
例：某二元码字
{111000,001011,010110,101110}
（1）如果码字等概率分布，求码率。
（2）采用最大似然准则，收到110110如何
译码。
348
有噪信道编码
解：
（1）码组的码率为
（2）采用最大似然准则，收到110110后，
与码字集中各码字的汉明距离分别为
3,5,1,2，故应译码为010110
6
4log)(
l
SH
R
349
有噪信道编码
（三）有噪信道编码定理
定理（香农第二定理）：设某信道有r个输入符号，
s个输出符号，信道容量为C 。当信息传输率R<C
时，只要码长n足够长，总可以在输入符号集中找
到M个码字（代表M个等可能性的消息）组成的一
个码（ 是一任意小的正数）和它相应的
译码规则，使信道输出的错误概率pE任意小。
,2 )( CnM
350
线性分组码
分组码是由码字或码组构成，码字是一组固
定长度的向量，其长度就是该向量的个数N。
一个码字的元素从q个元素的字符中选取。当
字符由元素0和1组成时，得到的码称为二
进制码，码字的元素称为比特。
351
线性分组码
在分组编码器中，k个比特信息被编成n个比
特，增加了n-k个冗余比特，其作用是检测
和纠正错码。
分组码也称为(n,k)码，其码率定义为
n
k
Rc
352
线性分组码
分组码的性质：
（1）线性：假设C1与C2是(n,k)分组码中的
两个码字，令 是从字符表中任意选择
的两个元素，则当且仅当 也是一
码字时，分组码是线性分组码。
21 和
2211 CC
一个线性码必定包含全零的码字，一个
固定码重的码是非线性的。
353
线性分组码
• （2）系统性：若一个码字，它前面的若干
比特等同于信息比特，剩余的比特是这些
信息比特的线性组合，则称之为系统码。
对一个(n,k)分组码，其前面k个比特等同
于信息比特，并且每个码字的剩余n-k比
特是k个信息比特的线性组合。
354
线性分组码
• （3）循环性：若 是一个码字，
且由C的循环移位得到的 也是
一个码字，则称码字具有循环特性。
],,,,[ 0121 ccccC nn
],,,,,[ 10132 nnn ccccc
循环码是线性码集合中满足循环移位特性的
一个子集合，即循环码的码字C的所有循环
移位都是码字。
355
线性分组码
令 是已被信道编码成的码字cm的k
个信息码元。用行向量分别表示k个信息码
元的向量和编码器输出向量为
],,,[
],,,[
21
21
mnmmm
mkmmm
cccc
xxxx
mkmm xxx ,,, 21
356
线性分组码
线性二进制分组编码器的编码运算可以用n个
方程组表示为
将其表示成矩阵形式为
这表明码字向量c是由信息码元向量x生成的，
故将G称作码字的生成矩阵。
Gxc mm
njgxgxgxc kjmkjmjmmj ,,2,12211
357
线性分组码
若令
则任何一个码字都可以表示为生成矩阵的行
向量的线性组合，即
knkk
n
n
k ggg
ggg
ggg
g
g
g
G
21
22221
11211
2
1
kmkmmm gxgxgxc 2211
这表明{gi}是(n,k)分组码的基向量，它不是
惟一的，故生成矩阵也不是惟一的。
358
线性分组码
• 一个(n,k)分组码的任何生成矩阵都可以表示成下
面的系统形式：
• 式中Ik是k*k单位矩阵，P是k*(n-k)矩阵，它决定
n-k个冗余码元即奇偶校验码元。
)(21
)(22221
)(11211
1000
0010
0001
][
knkkk
kn
kn
k
ppp
ppp
ppp
PIG
359
线性分组码
如果引入(n-k)*n矩阵H ，其转置矩阵HT和G
满足正交关系GHT=0 ，则知
也把H称作一致校验矩阵或一致监督矩阵。
][ kn
T IPH
360
线性分组码
例：某线性分组码生成矩阵为
（1）求n,k的值，并写出全部的码字，若收
到000110，判断其是否正确。
（2）求一致校验矩阵。
110100
011010
101001
G
361
线性分组码
• 解：生成矩阵是3行6列，可知n=6,k=3
110100
011010
101001
][ 321 mmmmGC
362
线性分组码
• 写出所有的码字为：
• 若收到000110则出错了。
316
325
214
33
22
11
mmc
mmc
mmc
mc
mc
mc
000000
001011
010110
100101
011101
101110
110011
111000
363
线性分组码
• 一致校验矩阵为
100101
010110
001011
]'[
IPH
364
马尔可夫信源
• 有限状态马尔可夫链
• 马尔可夫信源
365
有限状态马尔可夫链
• 设 为一随机序列，时间参数
集 ，其状态空间 ，
若对所有的 ，有
• 则称 为马尔可夫链。
},{ NnX n
{0,1,2,...}N 1 2{ , ,..., }JS s s s
Nn
},{ NnX n
1 2 1
1
1 2 1
1
( | , ,..., )
( | )
n n n
n n
n i n i n i i
n i n i
P X s X s X s X s
P X s X s
366
有限状态马尔可夫链
• 转移概率
• 性质：
SjiiXjXP
sXsXPnmp
mn
imjnij
,)|(
)|(),(
Sinmp
Sjinmp
Ij
ij
ij
1),()2(
,0),()1(
367
有限状态马尔可夫链
• 当n-m=1时，即pij(m,m+1)的情况下，将其
记为pij(m) ， 称为基本转移概率或一步
转移概率。
• 定义k步转移概率
• 规定零步转移概率
0m
SjiiXjXPmp mmij ,}|{)( 1
ji
ji
mp ijij
0
1
)(
)0(
SjiiXjXPmp mkm
k
ij ,}|{)(
)(
368
有限状态马尔可夫链
• 由于系统在任一时刻可处于状态空间中任
一状态，故转移概率是一个矩阵，也是一
个随机矩阵。
},),({
)(
SjimpP
k
ij
{0, 1, 2,...}S 一般情况下，状态空间 是一
个可数无穷集合，故转移矩阵是一个无穷
列的随机矩阵。
369
有限状态马尔可夫链
• 如果在马尔可夫链中
• 即从状态i转移到状态j的概率与m无关，则称这类
马尔可夫链为时齐马尔可夫链或齐次马尔可夫链，
也称为具有平稳转移概率的马尔可夫链。
SjipiXjXPmp ijmmij ,}|{)( 1
{0,1,2,..., }S n
{0, 1, 2,...}S 如果状态空间 是无穷集合，
则称为可数无穷状态的马尔可夫链。
如果状态空间 是有限的，
则称为有限状态的马尔可夫链。
370
有限状态马尔可夫链
• 对于具有m+r步转移概率的时齐马尔可夫链，存在切-柯
方程
• 利用该式就可以用一步转移概率表达多步转移概率。
• 但是转移概率不包含初始分布。
Ijippppp
Ijippp
Ik
m
kjik
Ik
kj
m
ik
m
ij
Ik
kjikij
,
,
)()()1(
)2(
Ijippp
rmPPP
r
Ik
kj
m
ik
rm
ij
rmrm
,
)1,(
)()()(
)()()(
371
有限状态马尔可夫链
• 若齐次马尔可夫链对一切i,j存在不依赖于i的极限
• 则称其具有遍历性，pj称为平稳分布，也是该马
尔可夫链的初始分布。
j
j
i
ijij
j
j
n
ij
n
p
ppp
p
pp
1
0
lim
0
)(
且满足
372
有限状态马尔可夫链
• 成为遍历马尔可夫链的充分条件是具有不
可约性和非周期性。
373
有限状态马尔可夫链
• 不可约性指对于任意一对i和j ，都存在至少
一个k，使pij(k)>0，即从si开始总可能到达
sj。
s1 s2
s3
1
可约马尔可夫链
374
有限状态马尔可夫链
s1 s2
s4 s3
周期性马尔可夫链
非周期性指所有pii(n)>0的n中没有比1大的公
因子。
375
有限状态马尔可夫链
• 对于一个有r个状态的马尔可夫链，若令
rj
pWpWpWpWW
SXPSntPW
rj
n
rjj
n
jj
n
j
nn
j
jnj
n
j
,2,1
}{}{
)1()1(
2
)1(
21
)1(
1
)(
)(
则可得
时刻的状态为
376
有限状态马尔可夫链
( ) ( ) ( ) ( )
1 2
( ) ( ) ( ) ( )
1 2
11 12 1 1
21 22 2 2
( 1) ( 1) ( 1) ( 1)
1 2
1 2
1 2
[ ... ]
[ ... ... ]
... ...
... ...
... ... ...
[ ... ... ]
... ...
... ... ...
... ...
n n n n
r
n n n n
j r
j r
j r
n n n n
j r
j j jj jr
r r rj rr
W W W W
W W W W
p p p p
p p p p
W W W W
p p p p
p p p p
设
则扩展后可得
( ) ( 1)
( ) ( 1) ( 2) 2 (0)...
n n
n n n n
W W P
W W P W P W P
即
经递推运算后得
377
有限状态马尔可夫链
• 对于有限状态马尔可夫链，如果存在一个数
集 ，且满足
• 则称该马尔可夫链的稳态分布存在，并有如下性
质：
• （1）完备性
rWWW ,,, 21
( )lim , 1,2,...,nij j
n
p W i j r
r
j
jW
1
1
W
（2）不变性 WP=W , 若W(0)=W 则
W(n)=W
（3）惟一性
378
马尔可夫信源
• 马尔可夫信源:
• 信源输出的符号序列和状态序列满足以下条件：
• （1）某一时刻信源符号的输出只与当时的信源状态有关，
而与以前的状态无关，即
1 1
1 2 1 2
( | , , ,...) ( | )
( , ,..., ), , ( , ,..., )
l k l j l k l i l k l j
k q i j J
p x a u S x a u S p x a u S
a A a a a S S S S S S
其中，输出 状态
),|( 1 jlklil SuaxSup
（2）信源状态只由当前输出符号和前一时刻信源的状
态惟一确定，即
379
马尔可夫信源
• 例 有一个二进制一阶马尔可夫信源X，其信
源符号集为[0,1]，条件概率为p(0|0)=,
p(1|0)=, p(0|1)=, p(1|1)=。求各状
态的稳态概率分布W1, W2 。
• 解：信源有两个状态S1=0, S2=1。
• 状态转移矩阵
P 0 1
0：
0：
1：
1：
状态转移图
380
马尔可夫信源
• 根据稳态分布的性质（1）和（2）可得：
1
1
2
1
221
121
21
21
W
W
WWW
WWW
WW
WWP
WW
381
马尔可夫信源
• 由于状态转移概率完全依赖于给定的条件概
率，故对一般的m阶马尔可夫信源
• 通过引入状态转移概率而转化为马尔可夫链。
1 1 2
1 2 ...
( | ... )
m m
q
i i i i
a a aX
p a a a aP
1 2 1 2
1 2
( ... ) , ,..., (1,2,... )
...
( | )
m
m
i i i i m
q
j i
S a a a i i i q
S S S
p S S
令
得到马尔可夫信源状态空间
)|( ij SSp
)|(
211 mm iiii
aaaap
),2,1(, mqji
其中，状态转移概率 由信源符号条件
概率 确定且 。
382
马尔可夫信源
• 当时间足够长后，遍历的m阶马尔可夫信
源可视为平稳信源来处理。又因为信源发
出的符号只与最近的m个符号有关，所以
1 2 1
1 1 2
1
lim ( | ... )
( | ... )
N N
N
m m
m
H H X X X X
H X X X X
H
383
马尔可夫信源
• 对于时齐、遍历的马尔可夫链，其状态
Sj由 惟一确定，因此有)( 1 mkk aa
1
,,,
;,,
),,|(
),,|(log),,(
),,|(log);,,(
,,
)|(),,|(
11
11
1111
11
1111
11
111
mkkk
kkkkk
S
kkkjkk
jkkk
jkkkk
HaaaH
aaapaap
aaapSaap
Saaa
Sapaaap
mm
kmkmk
mmm
jkmkmk
mmm
mm
mmm
，
左端
然后取负得
取统计平均，和，并对上式两端同时取对数，
384
马尔可夫信源
布。是马尔可夫链的平稳分其中
即
右端
，
)(
)|()(
)|()(
)|(log)|()(
)|(log);(
)|(log);,,(
1
;
;,,
1
11
1
11
11
111
j
S
jjm
S
jj
k S
jkjkj
S
jkjk
S
jkjkk
Sp
SXHSpH
SXHSp
SapSapSp
SapSap
SapSaap
j
j
m j
mm
jmk
mm
jkmkmk
mm
385
马尔可夫信源
• 例 有一个二进制二阶马尔可夫信源X，
其信源符号集为[0,1]，条件概率为p(0|00)=
p(1|11)= , p(1|00)= p(0|11)= ,
p(0|01)= p(0|10)=p(1|01)= p(1|10)=。
• （1）求各状态的稳态概率分布W1, W2 ,
W3, W4
• （2）求稳定后各符号的概率分布p(0)，
p(1)
• （3）求信源熵。
386
马尔可夫信源
• 解：信源有四个状态S1=00, S2=01, S3=10, S4=11 。
• 符号条件概率矩阵为
)|( ij SaP 01 10
1：
0：
11
0：
1：
1:
00
0:
s1
s4
s2 s3
0:
1：
状
态
转
移
图
387
马尔可夫信源
• （1）根据稳态分布的性质（1）和（2）可得：
7/1
14/5
1
1
32
41
442
342
231
131
4321
4321
WW
WW
WWW
WWW
WWW
WWW
WWWW
WWP
WWWW
)]|([ ij SSpP状态转移矩阵
388
马尔可夫信源
• （2）稳定后各符号的概率分布
14
5
7
1
7
1
14
5
)1(
14
5
7
1
7
1
14
5
)0(
)()|()(
4
1
p
p
SpSapap iij
i
j
389
马尔可夫信源
符号比特/
][
14
5
][
7
1
][
7
1
][
14
5
)|1()()|0()(
)|1()()|0()(
)|1()()|0()(
)|1()()|0()(
)|()(
4444
3333
2222
1111
1
SHSpSHSp
SHSpSHSp
SHSpSHSp
SHSpSHSp
SXHSpHH
jS
jjm
（3
）
信
源
熵
390
信源的相关性和剩余度
• 由于信源符号间的依赖关系使信源的熵减
小，就是信源的相关性。
• 如果信源输出符号间的相关性越长，则信
源熵减小，趋于极限熵 。H
若相关程度减小，信源实际熵增大。
只有当信源符号彼此间无依赖、等概
率分布时，信源的熵最大为H0。
391
信源的相关性和剩余度
• 一个信源输出的符号前后有相关性时，信源输出
的熵将减少，输出的总信息量也下降，这就是一
种形式的剩余或多余。
• 输出同样的信息量有剩余的信源输出的符号数要
比无剩余的信源多。
• 信源剩余度定义为 11
0H
H
R
H
其中， 为信源实际熵；H0= Hmax为信源最
大熵，当信源输出符号集有q个元素且为等
概分布时H0= Hmax=logq ； 称为相对率。
392
信源的相关性和剩余度
• 信源最大可能熵与实际熵的差值定义为内熵。
• 相对率、剩余度、内熵均可用来表示信源的
剩余情况。
• 信源的剩余度表示信源的可压缩程度。
从提高信息传输效率的观点出发，总是希望
减少或去掉剩余度（信源编码）。
从提高抗干扰能力的角度出发，总是希望增
加或保留剩余度（信道编码） 。
393
信源的相关性和剩余度
• 例：黑白气象传真图的消息只有黑色和白色两种，
黑色出现的概率为P(黑)= ，白色出现的概率
为P(白)= 。
• （1）假设图上黑白消息出现前后没有关联，求熵
H(X)。
• （2）假设消息前后有关联，其依赖关系为P(白|
白)=， P(黑|白)=， P(白|黑)=， P(黑|黑
)=，求熵H2。
• （3）分别求上述两种信源的剩余度，并比较
H(X)和H2的大小，说明其物理意义。
394
信源的相关性和剩余度
• 解： 设状态x1=黑，x2=白
• （1）假设图上黑白消息出现前后没有关联，
则等效为一个离散无记忆信源，概率空间
为
• 信息熵
21 xx
P
X
符号比特 /
)(log)()(
2
1
i
ii xPxPXH
395
信源的相关性和剩余度
• （2）假设消息前后有关联时，从其依赖关
系看出其满足一阶马尔可夫信源的定义，
状态空间为
• 状态转移矩阵
2,1,
)|( 21
21
12
kk
aaP
SS
kk
P
黑 白
状态转移图
S2 S1
396
信源的相关性和剩余度
• 由图可知，此马尔可夫链满足不可约性和
非周期性，其稳态分布存在，分别设为
P(S1)=W1， P(S2)=W2
3/1
3/2
1
1
2
1
221
121
21
21
W
W
WWW
WWW
WW
WWP
WW
397
信源的相关性和剩余度
• 信息熵
符号比特
黑白
黑白
/
),(
3
1
),(
3
2
)]|()|()[(
)]|()|()[(
)|()(
222
111
2
HH
SHSHSp
SHSHSp
SXHSpHH
jS
jj
398
信源的相关性和剩余度
• （3）两种信源的剩余度
212
2
2
1
,)(
2log
1
2log
1
2log
1
2log
)(
1
RRHXH
H
R
XH
R
结果说明，当信源的消息符号之间有依赖时，
信源输出消息的不确定性减弱。
信源剩余度反映了消息符号间依赖关系的强
弱，剩余度越大，符号间的依赖关系越大。
399
4 信道及其容量
• 信道的分类与描述
• 离散无记忆信道
• 离散无记忆的扩展信道
• 信道的组合
• 信道容量
• 信源与信道的匹配
400
信道的分类与描述
• 信道是所传信息的载体（消息）的具体形
式（信号）所要通过的通道或媒介。
• 信息是抽象的但信道是具体的。
在信息系统中，信道的主要作用是传输与存储
信息，而在通信系统中则主要是传输信息，对
其研究的主要目的是为了描述、度量、分析不
同类型信道，计算其容量。
401
信道的分类与描述
• （一）信道的分类
• （1）按传输媒介的类型划分
明线
市内电话的对称电缆
电缆 长途电话（小同轴，中同轴）
长波
中波
短波
超短波
微波（视距接力，卫星电缆，散射通信）
光波
传
输
媒
介
类
型
有线信道
无线信道
(空气介质
)
固体介质
混合介质（波导，光缆）
402
信道的分类与描述
• （2）按决定信道的信号与干扰的类型与描述划分
无源热噪声
线性叠加干扰 有源散弹噪声
天电脉冲干扰
离散-数字信道
连续-模拟信道
半连续或半离散
信
号
与
干
扰
类
型
干扰类型
信号类型
有干扰
无干扰
交调
乘性干扰 衰落
码间干扰
403
信道的分类与描述
• （3）按信道的物理性质（信道的统计特性）
划分
线性时变信道
非线性时变信道
信
道
参
量
性
质
恒参信道（时不变信道）
变参（随参）信道
404
信道的分类与描述
• （4）按用户类型划分
• （5）按信道的记忆特性划分
用户类型
二用户信道（点对点通信或两端通信）
多用户信道（通信网或多端通信）
记忆特性
无记忆信道
有记忆信道
405
信道的分类与描述
• （二）信道描述
• 三要素：
• （1）信道输入统计概率空间：[X,p(X)]
• （2）信道输出统计概率空间：[Y,p(Y)]
• （3）信道本身的统计特性，即转移概率矩阵：
p(y|x)
• 由此构成对信道整体的描述为：
• {[X,p(X)], p(y|x),[Y,p(Y)]}
• 简记为： {X, p(y|x),Y}
406
信道的分类与描述
• 对离散序列信源可以描述为：
• 其中：
• 信道转移概率为
ml
ml
nl
nl
pppp
yyyy
YP
Y
xyp
pppp
xxxx
XP
X
21
21
21
21
)(
)|(
)(
输出
信道
输入
干扰
},{},,{ 2121 mlnl yyyYyxxxXx
)|()|(
)|()|(
1
111
nmn
m
xypxyp
xypxyp
P
407
离散无记忆信道
• （一）离散信道的数学模型
NnByyyyy
YYYY
NnAxxxxx
XXXX
sjq
bbb
qip
aaa
nNn
N
nNn
N
j
s
i
q
1,},,,,{
},,{
1,},,,,{
},,{
,,2,1},{
},,{B
,,2,1},{
},,{A
1
21
1
21
21
21
其取值
相应输出序列为
其取值
信道输入序列为
。相应的概率分布为
输出空间
。相应的概率分布为
输入空间
408
离散无记忆信道
恒参的。则称此信道是平稳的或
还满足，和若对于任意
其数学模型为
，道，简记为则称它为离散无记忆信
长的输入、输出序列有若离散信道对任意
为信道的数学模型可表示
来描述信道特性可用转移概率
)|()|(
,,
}),|(,{
)|()|(
}),|(,{
),|,()|(
1
2121
ixjypixjyp
DMCBjAimn
YxypX
DMC
xypxyp
N
YxypX
xxxyyypxyp
mmnn
nn
N
n
nn
NN
409
离散无记忆信道
• 根据信道的统计特性不同，离散信道又可分为三
种情况：
• （1）无干扰信道。输入与输出之间有确定的一一
对应关系，即y=f(x)，
• （2）有干扰无记忆信道。
• （3）有干扰有记忆信道。
)(0
)(1
)|(
xfy
xfy
xyp
N
n
nnNN xypxxxyyypxyp
1
2121 )|(},|,()|(
410
离散无记忆信道
• （二）单符号离散信道
qsqq
s
s
ij
ij
s
j
ij
ij
s
q
ppp
ppp
ppp
P
sjqiabpP
sjqiabpqiabp
sjqiaXbYPxyp
bbbByY
aaaAxX
21
22221
11211
1
21
21
},,2,1;,,2,1),|({
,,2,1;,,2,10)|(;,,2,11)|(
,,2,1;,,2,1)|()|(
},{,
},,{,
或
称为信道矩阵
概率矩阵，故传递概率其实是一个由于干扰使传输出错，
且有
信道的传递概率为
，其取值相应输出符号为
其取值信道输入符号为
411
离散无记忆信道
• （1）二进制对称信道（二元对称信道—
BSC信道）
• 输入符号集A={0,1};输出符号集B ={0,1};传
递概率为
pppabp
ppabp
ppabp
pppabp
1)1|1()|(
)0|1()|(
)1|0()|(
1)0|0()|(
22
12
21
11
412
离散无记忆信道
• 且传递概率满足：
• 传递矩阵为
X Y
a1=0
a2=1
b1=0
b2=1
1-p
1-p
p
p
二元对称信道
1)|()|(
2
1
2
2
1
1
j
j
j
j abpabp
pp
pp
P
413
离散无记忆信道
• （2）二进制删除信道
• 输入符号集A={0,1};输出符号集B ={0,？,1}
• 传递矩阵为
• 且有
2,11)|(
3
1
iabp
j
ij
qq
pp
P
10
01
X Ya1=0
a2=1
b1=0
b2=1
p
q
1-p
1-q
二元删除信道
?
414
离散无记忆信道
• 提示：在离散信道中，一般概率关
系有：
• （1）若输入符号的概率已知，
• 则输入和输出符号的联合概率
• 而且
qiapaxP ii ,,2,1),()(
)(),( jiji bapbyaxP
)|()()|()()( jijijiji bapbpabpapbap
其中p(bj|ai)是信道传递概率，称为前向概率，
p(ai |bj) 称为后向概率，也是输入符号的后验概率，
p(ai) 是输入符号的先验概率。
415
离散无记忆信道
• （2）根据联合概率可得出输出符号的概率
• 或
• P为信道矩阵。
sjabpapbp
q
i
ijij ,2,1)|()()(
1
)(
)(
)(
)(
)(
)(
2
1
2
1
q
T
s
ap
ap
ap
P
bp
bp
bp
416
离散无记忆信道
• （3）根据贝叶斯定律可得后验概率
sjbap
sjqi
abpap
abpap
bp
bap
bap
q
i
ji
q
i
iji
iji
j
ji
ji
,2,11)|(
,2,1;,2,1
)|()(
)|()(
)(
)(
)|(
1
1
且得
417
离散无记忆信道
• （三）信道疑义度及平均互信息
• （1）信道疑义度
• 输入空间X对输出空间Y的条件熵为信道疑
义度，即
i j
jijij bapbapbXHEYXH )|(log)()]|([)|(
表示在输出端收到全部输出符号后，对于
输入符号集仍然存在的平均不确定性。
418
离散无记忆信道
• （2）平均互信息
• 定义：原始信源熵与信道疑义度之差为平
均互信息，即
• 特性：
• 1）交互性（对称性）
• 2）非负性
• 3）极值性
)|()();( YXHXHYXI
);();( XYIYXI
0);( YXI
)();( XHYXI
419
离散无记忆信道
• 4）平均互信息与各类熵的关系
。道中噪声源的不确定性称为噪声熵，反映了信
。所引起的信息量的损失
后符号通过有噪信道传输称为损失熵，表示信源式中
联合熵
)|(
)|(
)|()()|()()(
)()()(
)|()()|()();(
XYH
YXH
YXHYHXYHXHXYH
XYHYHXH
XYHYHYXHXHYXI
H(X
)
H(Y)
H(X|Y) I(X;Y) H(Y|X)
H(XY)
维
拉
图
420
离散无记忆信道
• 5）平均互信息I(X;Y)是信源概率分布p(x)
的上凸函数，是信道传递概率p(y|x)的下凸
函数。
• 例 参见教材82页
• 例 参见教材84页
421
离散无记忆的扩展信道
• （一）N次扩展信道数学模型
• 离散无记忆信道的数学模型基本同于单符
号离散信道的数学模型，用概率空间
[X,p(bj|ai),Y]来描述，但它的输入输出不是
单个随机变量X和Y ，而是随机序列，
• 传递概率等于对应时刻随机变量的传递概
率的乘积。
),(),,( 2121 NN YYYYXXXX
422
离散无记忆的扩展信道
• 因为输入序列中的每个变量
各取值于同一输入符号集X，而符号集X中
共有q个符号，所以随机矢量X的可能取值
有qN个，同理，随机矢量Y的可能取值有sN
个。根据信道无记忆特性有
N次扩展信道
)( khp
XN YN
)2,1( NiX i
N
i
iiNN xypxxxyyypxyp
1
2121 )|()|()|(
423
离散无记忆的扩展信道
NN
N
i
kh
kkkhhhkhkh
shhhhh
qkkkkk
N
s
h
kh
NN
khkh
sqqq
s
s
shqkabp
aaabbbpp
Nibbbbbbb
Niaaaaaaa
qk
shqkp
ii
NN
iN
iN
N
NNNN
N
N
2,1,2,1)|(
)|()|(
2,1},,{)(
2,1},,{)(
2,11
2,1,2,1)|(
][
1
21
21
1
21
22221
11211
2121
21
21
所以得
并满足
式中
信道矩阵为
424
离散无记忆的扩展信道
• （二）N次扩展信道平均互信息
• 定理1 若信道的输入随机序列为 ，通过信
道传输，接收到的随机序列为 。若信道是
无记忆的，即信道传递概率满足
• 式中Xi和Yi是随机序列对应的第i位随机变量。
N
i
ii
NN
N
i
khkh
N
i
ii
YXIYXI
shqkabpp
xypxyp
ii
1
1
1
);();(
2,1,2,1)|()|(
)|()|(
则存在
或写成
),( 21 NXXXX
),( 21 NYYYY
425
离散无记忆的扩展信道
• 定理2 若信道的输入随机序列为 ，
经信道传输接收到的随机序列为 。
信道传递概率为p(y|x)，若信源是无记忆的，即
满足
• 式中Xi和Yi是随机序列对应的第i位随机变量。
N
i
ii
N
N
i
kk
N
i
i
YXIYXI
qkapp
xpxp
i
1
1
1
);();(
2,1)()(
)()(
则存在
或写成
),( 21 NXXXX
),( 21 NYYYY
426
离散无记忆的扩展信道
• 若信道和信源都是无记忆的，则
• 一般情况，信道的输入随机序列 中的
随机变量 取值于同一信源符号集X，
并且具有同一概率分布，而且经相同的信道传输，
接收到的随机序列 中的随机变量
也取值于同一符号集Y ，因此有
• 式中N是随机序列的长度。
NiYXNIYXI
YXIYXIYXI
ii
N
i
ii
NN
2,1);();(
);();();(
1
2211
则
),( 21 NXXXX
),( 21 NYYYY )2,1( NiYi
)2,1( NiX i
N
i
ii YXIYXI
1
);();(
427
信道的组合
• （一）串联信道
信道1
p(y|x)
信道2
p(z|xy)
X ZY
1)|( xyp 1)|( xyzp
串联信道的示意图
。的传递概率为信道
的传递概率为信道
，的输出符号集为信道
的输入消息集合，同时它又是信道
，相应的输出符号集为
的输入符号集为信道
lkbacpxyzp
sjqiabpxyp
cccZ
bbbY
aaaX
jik
ij
l
s
q
,,2,1)|()|(2
,,2,1;,,2,1)|()|(1
},{2
2
},{
},,{1
21
21
21
428
信道的组合
• 定理1：级联信道中的平均互信息满足以
下关系：
时等式成立。
当且仅当对所有
)|()|(),|()|(
,,
);();();();(
xzpxyzpyzpxyzp
zyx
ZXIZXYIZYIZXYI
);();();();( ZYIZXIYXIZXI
定理2：若X,Y,Z组成一个马尔可夫链，则有
也称为数据处理定理，表明了信息不增性原理。
例 参见教材92页
429
信道的组合
• （二）并联信道
)';'();()';'(
)'(
)'|'()|(
log)'|'()|()'(
)'(
)'|'(
log)''()';'(
)'|'()|()'|'(
''
''
YXIYXIYYXXI
yyp
xypxyp
xypxypxxp
yyp
xxyyp
yyxxpYYXXI
xypxypxxyyp
YYXX
YYXX
并且
平均联合互信息量为
合条件概率为当信道相互独立时，联
信道1
信道2
x
yy’
y
两个独立信道的并联
x’ y’
Xx’
430
信道的组合
• （三）和信道
用概率。分别为每个分信道的使其中
互信息量为
21
2211222111
,
)loglog();();();(
kk
kkkkYXIkYXIkYXI
信道1
信道2
X1
Y= Y1+ Y2
Y1
和信道的模型
X2 Y2
X=X1+X2
431
信道容量
• （一）基本定义
• （1）信道的信息传输率R
• 信息传输率R是平均每个符号所能传送的信息
量，而平均互信息I(X;Y)就是接收到符号集Y后
平均每个符号获得的关于X的信息量，故信道
的信息传输率就是平均互信息量。
• R=I (X;Y)=H (X)-H (X|Y) 比特/符号
若平均传输一个符号需要t秒，则信道每秒钟平
均传输的信息量为
R=I (X;Y)/t 比特/秒
432
信道容量
• （2）信道容量C的定义
• 定义最大的信息传输率为信道容量C，即
• 其单位是比特/符号或奈特/符号，相应的
p(x)称为最佳输入分布。
)};({max
)(
YXIC
xP
)};({max
1
)(
YXI
t
C
xP
t
若平均传输一个符号需要t秒钟，则信道单
位时间内平均传输的最大信息量为
433
信道容量
• 二进制对称信道的平均互信息为
• 它对 存在一个极大值，
)()();( pHppHYXI
1)
2
1
()(2/1
HppH 时，当
因此它的信道容量为C=1-H(p),它只是信道
传输概率p的函数，与输入符号集的概率分
布p(x)无关。
434
信道容量
• （二）几种典型信道的容量计算
• （1）离散单个消息信道容量
• [1]有噪无损信道：一个输入对应多个互不相交
的输出。
a1
a2
a3
b1
b3
b5
b2
b4
b6
X
Y
有噪无损信道
B2
B1
B3
435
信道容量
• 信道的后向概率为
• 信道疑义度H(X|Y)=0。信源发生符号ai，并
不依一定概率取Bi中的某一个bj ，因此噪
声熵H(Y |X)>0 。
rXHYXIC
xPxP
log)(max)};({max
)()(
ij
ij
ji
Bb
Bb
bap
1
0
)|(
平均互信息为I(X;Y)=H(X)<H(Y)。故信
道容量为
436
信道容量
• [2]无噪有损信道：一个输出对应多个互不相交的
输入。
b1
b2
a1
a3
a5
a2
a4
X Y
无噪有损信道
A2
A1
437
信道容量
• 信道的传递概率为
• 噪声熵H(Y |X)=0。接收到某一个bj，并不
能判定是哪一个输入符号ai，因此信道疑义
度H(X|Y)>0
sYHYXIC
xPxP
log)(max)};({max
)()(
ji
ji
ij
Aa
Aa
abp
1
0
)|(
平均互信息为I(X;Y)=H(Y)<H(X)。故信
道容量为
438
信道容量
• [3]无噪无损信道：该信道的输入和输出一一对应，
其传递概率为
)(1
)(0
)|(
xfy
xfy
xyp
b1
b2
a1
a3
ar
a2
b3
X Y
无噪无损信道
br
439
信道容量
• 信道的后向概率和传递概率一致
• 噪声熵和损失熵相等，H(Y |X)=H(X|Y) =0。
• 平均互信息为I(X;Y)=H(Y)=H(X)。
• 故信道容量为
rXHYXIC
xPxP
log)(max)};({max
)()(
ji
ji
abpbap ijji
1
0
)|()|(
440
信道容量
• [4]离散对称信道
• 信道矩阵有很强的对称性，即信道矩阵[P]中
每一行都是由同一集 的元素不同排
列组成，并且每一列也是由集 的元
素不同排列组成。
• 例如
][
][
P
P
},,{ ''2
'
1 sppp
},,{ ''2
'
1 rqqq
441
信道容量
• 定理：若一个离散信道具有r个输入符号，s个输
出符号，则当输入为等概率分布时，达到信道容
量C ，且
• 其中， 为信道矩阵中的任一行。
• 例 参见教材100页
''
2
'
1 ,, sppp
),,,(log ''2
'
1 spppHsC
442
信道容量
• [5]强对称信道（均匀信道）：若输入和输出符
号个数相同都为r，且信道矩阵为
• 其中，
• 其信道容量为
p
r
p
r
p
r
p
r
p
r
p
p
r
p
r
p
r
p
r
p
p
P
111
111
111
1
pp
)()1log(log pHrprC
443
信道容量
• [6]准对称信道：信道矩阵是输入对称输出不对称，即
矩阵的每一行包含同样的元素，而各列的元素不同。
。个子矩阵的列元素之和是第
，个子矩阵的行元素之和是第
是子矩阵的个数，其中，
信道容量为
kM
kN
n
MNpppHrC
k
k
n
k
kks
1
''
2
'
1 log),,,(log
][
][ PP
444
信道容量
• [7]特殊信道：
a1=0
a2=1
b1=0
b2=1
1-p
1-q
p
q
二元非对称信道
)22log(
1
)()()(
1
)()()(
C
qp
qHpqHqpH
qp
pHpqHqpH
445
信道容量
• 当p=q时，此信道就是二元对称信道。
• 当p=0时，此信道就是二元Z信道，其信道
容量为
]
21
1
[
1
1
)1(
]
21
2
[
1
1
)0(
]21log[
)1/()(
)1/()(
)1/()(
)1/()(
qqH
qqH
qqH
qqH
q
p
q
q
p
C
0
1
0
1
1
1-q
q
Z信道
446
信道容量
• （2）离散无记忆N次扩展信道的信道容
量
• 式中 )};({max
);(max)};({max
);();(
)(
11
)()(
1
ii
xp
i
N
i
i
N
i
ii
xpxp
N
N
i
ii
YXIC
CYXIYXIC
YXIYXI
是某时刻通过离散无记忆信道传输的最大信息量，因
为是在同一信道中传输，得Ci=C，故CN=NC。
447
信道容量
• （3）组合信道的信道容量
• [1]串联信道
• 当N个独立信道并接或构成和信道时：
• [2]并联信道
• [3]和信道
)(log)};({max
)(
pHmYXIC
xP
N
i
iCC
1
)2log(
1
N
i
CiC
448
信源与信道的匹配
• 当信源与信道连接时，若信息传输速率达到了信
道容量，则称此信源与信道达到了匹配，否则认
为信道有剩余。信道剩余度定义为
• 信道剩余度=C-I(X;Y)
C
YXI
C
YXIC );(
1
);(
相对剩余度
其中， C是该信道的信道容量，I(X;Y)是信源通过该
信道实际传输的平均信息量。也可以用相对剩余度来
描述信源与信道的匹配程度。
449
信源与信道的匹配
• 在无损信道中，
• 可以看出它就是信源的剩余度。对于无损
信道，可以通过信源编码，减少信源的剩
余度，使信息的传输率达到信道容量。
r
XH
C
YXI
log
)(
1
);(
1 相对剩余度
450
信源与信道的匹配
• 信源编码就是将信源输出的消息变换成新
信源的消息来传输，而使新信源的熵接近
最大熵，这样，新信源的消息通过信道的
信息传输率接近最大值，信道剩余度接近
于零，信道得到充分利用，这就是香农无
失真信源编码理论。
451
5 信源编码
• 无失真信源编码
• 编码器
• 分组码
• 等长信源编码定理
• 变长编码定理
• 限失真信源编码
• 常用的信源编码方法
452
6 信道编码
• 信道编码的基本概念
• 有噪信道编码
• 线性分组码
453
信道编码的基本概念
• （一）信道编码的地位和作用
• 数字通信系统的主要技术指标：
• （1）传输速率
[1]码元传输速率：
指携带数据信息的信号单元，每秒钟通
过信道传输的码元数称为码元传输速率，
单位是波特，故简称波特率，又称为调
制速率。
454
信道编码的基本概念
• [2]比特传输速率：
• 每秒钟通过信道传输的信息量称为比
特传输速率.
• 单位是比特/秒，简称比特率。
455
信道编码的基本概念
• 对二进制来说，每个码元的信息含量为1
比特，因此，二进制的码元传输速率与比
特传输速率在数值上是相等的。
对M进制来说，每一码元的信息含量为
logM比特，如果码元传输速率为rs波
特，则相应的比特传输速率rb为rs
logM。
456
信道编码的基本概念
• （2）差错率
• [1]码元差错率：在传输的码元总数中发生
差错的码元数所占的比例（平均值），简
称误码率，用符号pE表示。
[2]比特差错率：在传输的比特总数中发生
差错的比特数所占的比例（平均值），用符
号pBE表示。在二进制传输系统中，码元差错
率就是比特差错率。
[3]码组差错率：在传输的码组总数中发生差
错的码组数所占的比例（平均值）。
457
信道编码的基本概念
• （3）可靠性
• 在数字通信系统中信息的传输（或存储）
遇到的主要问题就是:
• 在传输过程中出现差错问题，也就是传输
的可靠性问题。
458
信道编码的基本概念
出错的主要原因是
(1)不同的传输系统有不同的性能以及在
传输过程中干扰不同；
(2)不同用户或不同的传输系统对差错率
的要求不同。
459
信道编码的基本概念
• 降低误码率通常有两种途径：
• 一是降低信道（包括调制解调器、传输媒
介）本身所引起的误码率；
二是采用信道编码，在数字通信系统中
增加差错控制设备。
460
信道编码的基本概念
• 降低信道所引起的误码率的主要方法有：
一是选择合适的传输线路；
• 二是改进传输线路的传输特性或增加发送
信号的能量；
• 三是用潜在抗干扰性较强的调制解调方案。
461
信道编码的基本概念
• 某些情况下，信道的改善可能较困难或不
经济，此时就要采用信道编码。
信
息
源
噪声源
变
换
器
调
制
器
发
射
机
信道
接
收
机
解
调
器
反
变
换
器
信
息
宿
接收端发送端 信道
有编码的数字通信系统框图
信
源
编
码
器
信
道
编
码
器
信
道
译
码
器
信
源
译
码
器
462
信道编码的基本概念
• （二）信道编码的基本思想和分类
• 差错的基本形式：
• 一是随机错误，即数据序列中前后码元之
间是否发生错误彼此无关，产生这种错误
的信道称为无记忆信道或随机信道。
二是突发错误，即错误之间有相关性，
成串出现，称这类信道为突发差错信道。
463
信道编码的基本概念
• 设信道输入的发送序列为00000，由于干扰，
信道输出的接收序列为00100，相当于信道
中有一个差错序列00100
发送序列与接收序列对应位的模2和就是信
道的错误图样。
这个差错序列与发送序列逐为模2相加，
就得到了接收序列，称这个差错序列为
信道错误图样。
464
信道编码的基本概念
• 信息序列：信源编码器输出的数字序列M，
通常是由二元符号0和1组成，且符号0和1
是相互独立等概率的。
信道编码：按一定规律在待发送的信息码
中加入一些人为制作的码元，以保证传输
过程可靠性。
检错码：用于检测差错的信道码。
纠错码：可以检测和校正差错的信道码。
465
信道编码的基本概念
• 从原理分：
• 如果规则是线性的，即码元之间的关系是
线性关系，则称这类信道编码为线性码，
否则称为非线性码。
从信息序列所对应的编码方式分：
如果将信源的信息序列按照独立分组进
行处理和编码，则称为分组码，否则称为
非分组码。
466
信道编码的基本概念
• 在线性分组码中，通常把码组中所含“1”
的数目定义为码组重复（码重），记为
W(c)。
把两个码组中对应位置上不同分量数
目定义为码组距离，记为d(ci, cj)。
码组间最小距离dmin的大小直接决定
线性分组码的检错能力。
467
信道编码的基本概念
• 若要发现e个独立随机错误则要求：
• 若要纠正t个独立随机错误则要求：
• 若要发现e个独立随机错误，同时能纠正t
个独立随机错误则要求：
1min ed
12min td
1min etd
468
信道编码的基本概念
• (n,1)重复码
• （1）不重复：最简单但没有任何抗干扰能
力，既不能发现更不能纠正错误。
• （2）重复一次：效率降低一倍但在传输过
程中允许错一位，能发现但不能纠正错误。
• （3）重复两次：效率降低两倍，能发现两
个错误或纠正一个错误。
469
信道编码的基本概念
• 偶（奇）监督码
• 编码规则：
• 上式是模2相加和。这种偶数监督码，要保
证码组中“1”的个数是偶数，即满足在码
组中信息位和监督位模2和为0，能发现奇
数个差错。
),,,(
2
0
1210
n
i
inn cccccc
470
信道编码的基本概念
• 例：
• 同理可设计奇数监督码，只是码组中“1”
的个数是奇数。
• 这类偶（奇）监督码可记为(n,n-1)码。
c0 c1
0 0
0 1
1 0
1 1
c0 c1
0 0
0 1
1 0
1 1
c2
0
1
1
0
471
信道编码的基本概念
• (n,1)重复码和(n,n-1)偶（奇）监督码虽然
构造都很简单，但性能远不能满足既有可
靠性又有有效性的要求。
472
信道编码的基本概念
• 对(n,1)重复码，随着码长n增大，可靠性
虽可不断提高，但编码效率 在不断
降低。 n
1
1
1
n
n
对(n,n-1)偶（奇）监督码，随着码长n增
大，有效性很高即编码效率 ，但
抗干扰性很差。
473
信道编码的基本概念
• 线性分组码在构造时，
• 将输入信息分成k位一组进行编码，
• 按照一定线性规律加上人为多余的码元，
• 构成n(n>k)位一组的输出，
• 故可采用符号(n,k)表示。
474
信道编码的基本概念
• 其中n表示输出的码组长度，k表示输入信
息分组，即输出码中信息码位数，余下的
r=n-k位码元表示在编码过程中人为加入的
多余码元。
这些多余码元是供接收端检查、纠正
在传输中产生错误的码元，故称其为
监督码元或校验码元。
475
信道编码的基本概念
• （三）差错控制基本方式
• 有两类：
• 一类是接收端检测到传输的码字有错后，
收端译码器自动地纠正错误；
另一类是收端接收到错误后，通过反馈信
道发送一个应答信号，要求发端重传有错
误的消息，从而达到纠正错误的目的。
476
信道编码的基本概念
• 在数字和数据的信息与通信系统中，利用信道编
码提高系统的可靠性，控制差错，主要方式有四
种：
• （1）前向纠错(FEC)
发端 收端
纠错码
优点：不要反馈信道，适于广播系统，译码延时
固定，较适于实时传输系统。
缺点：要求预先确定信道的差错统计特性。
477
信道编码的基本概念
• （2）反馈重传(ARQ)
发端 收端检错码
应答信号
优点：只需少量的多余码元就能获得极低的输
出误码率，检错码基本与信道的差错统计特性
无关。
缺点：要反馈信道，不能用于单项传输系统，
也难以用于同播系统，控制较复杂，不大适于
实时传输系统。
478
信道编码的基本概念
• （3）混合纠错(HEC)
发端 收端纠检错码
应答信号
具有FEC和ARQ的优点，避免了FEC方式所需
的复杂译码器及不能适应差错能力变化的缺点，
还能克服ARQ方式信息连贯性差，有时通信效率
低的缺点。特别选用于环路延时大的高速传输系
统（如卫星系统）中。
479
信道编码的基本概念
• （4）信息反馈(IRQ)
发端 收端数据信息
数据信息
优点：不需要纠错、检错编译码器，控制设备
和检错设备均较简单。
缺点：发端需要一定容量的存储器以存储发送
码组，适用于传输速率较低、数据信道差错率
较低、具有双向传输线路及控制简单的系统中。
480
有噪信道编码
• 信道的输入和输出端连接着编码器和译码
器，形成了一个新的信道，将这种变换后
具有新特性的信道称为编码信道。
编码器 信道
信源编码器
X
译码器
Y
信源译码器
编码信道
481
有噪信道编码
• 在有噪信道中传输消息是会发生错误
的，错误概率和信道的统计特性、译
码过程以及译码规则有关。
482
有噪信道编码
• 设信道输入符号集为 ，输出符
号集为 。若对每一个输出符
号yj都有一个确定的函数F(yj)，使yj对应惟
一的一个输入符号xi，则称这样的函数为译
码规则，记为
},2,1,{ rixX i
},2,1,{ sjyY j
sjrixyF ij ,2,1;,2,1)(
显然，对于有r个输入、s个输出的信道，
按上述定义可得到译码规则有rs种。
483
有噪信道编码
• 例：已知信道矩阵和两种译码规则
)()(
)]()()[(
3
1
)|(
3
1
)(
)]()()[(
3
1
)|(
3
1
)(
)(
)(
)(
)(
)(
)(
*,
*,
23
32
11
33
22
11
BpAp
xypBp
xypAp
xyF
xyF
xyF
B
xyF
xyF
xyF
AP
EE
xXY
E
xXY
E
484
有噪信道编码
• 在确定译码规则F(yj)=xi后，信道输出端接
收到的符号为yj，而发送的不是xi ，就认为
有错误，这种错误概率p(e|yj)称为条件错误
概率.
• 则译码的条件正确概率为
• 条件错误概率与条件正确概率间的关系
)|(]|)([ jijj yxpyyFp
]|)([1)|(1)|( jjjij yyFpyxpyep
485
有噪信道编码
• 因为译码过程有统计平均作用，经过译码
后的平均错误概率pE为
s
j
jjjE yepypyepEp
1
)|()()]|([
选择译码规则总的原则是使pE最小，
上式右边是非负项之和，应使每一项最小，
因为p(yj)与译码规则无关，故要使p(e|yj)
最小。
486
有噪信道编码
• 为了使p(e|yj)最小，就应使p[F(yj) |yj]最大，
即选择译码函数F(yj)=x*使之满足对所有i
)|()|*( jij yxpyxp
因此，如果采用的译码函数对于每一个输出译码符
号均译成具有最大后验概率的那个输入符号，则信
道错误概率就能最小。这个规则称为最大后验概率
规则或最小错误概率准则。
487
有噪信道编码
• 根据贝叶斯定律，上式可写成
• 为了便于计算，忽略信源的统计特性，
选择译码函数F(yj)=x*使之满足对所有i
• 称为极大似然译码规则。
)|(*)|( ijj xypxyp
)(
)()|(
)(
*)(*)|(
j
iij
j
j
yp
xpxyp
yp
xpxyp
488
有噪信道编码
• 平均错误概率
*,
1
1
1
)()*()(
])([)(
)])([1
)}|)([1){(
)|()(
xXYYXY
YXY
s
j
jj
s
j
jjj
s
j
jjE
xypyxpxyp
yyFpxyp
yyFp
yyFpyp
yepypp
489
有噪信道编码
• 用条件概率表示
• 如果p(x)是等概率的p(x)=1/r，则
• 此时译码错误概率可以用信道矩阵中的元素，去
掉每列中的F(yj)=x*项，求和来表示。
• 平均正确概率为
*,
)()|(
xXY
E xpxypp
YY
EE yxpyyFppp )*(])([1
*,
)|(
1
xXY
E xyp
r
p
490
有噪信道编码
• 费诺不等式
• 表明了平均错误概率pE与信道疑义度
H(X|Y)间的关系。
)1log()()|( rppHYXH EE
可知，接收到Y后关于X的平均不确定性分
为两部分：一是接收到Y后是否产生错误的
不确定性；二是错误发生后，到底是哪个输
入符号发送而造成错误的不确定性。
491
有噪信道编码
• 例：已知信道矩阵
• 并设p(x1)=1/2, p(x2)=p(x3)=1/4, 分别用最
小错误概率准则和最大似然译码准则确定
相应的译码规则，并计算平均错误概率。
2
1
6
1
3
1
3
1
2
1
6
1
6
1
3
1
2
1
P
492
有噪信道编码
• 解：由于输入符号不是等概率分布，所以对于最
小错误概率准则必须根据联合概率的大小来选择。
• p(x1y1)=1/4, p(x2y1)=1/24,p(x3y1)=1/12
p(x1y2)=1/6, p(x2y2)=1/8,p(x3y2)=1/24
p(x1y3)=1/12, p(x2y3)=1/12,p(x3y3)=1/8
故译码规则是
F(y1)=x1, F(y2)=x1, F(y3)=x3
493
有噪信道编码
• 对于最大似然译码准则，可以直接从信
道矩阵的传递概率来选择，译码规则是
• F(y1)=x1, F(y2)=x2, F(y3)=x3
平均错误概率为
pE=1/24+1/12+1/6+1/24+1/12 +1/12
=12/24
p’E=1/24+1/12+1/8+1/24+1/12 +1/12
=11/24< pE
494
有噪信道编码
• 选择最佳译码规则只能使错误概率pE有限
地减小，无法使其任意的小。要想进一步
减小错误概率，必须优选信道编码方法。
495
有噪信道编码
• （1）简单重复编码
X Y
a1=0
a2=1
b1=0
b2=1
1-p=
1-p
p
p
2
*,
2211
10)(
2
1
)|(
1
)(,)(
xXY
E xyp
r
p
xyFxyF最佳译码规则
496
有噪信道编码
000=b1
010=b3
100=b5
001=b2
011=b4
101=b6
110=b7
111=b8
a1 = 000
010=a3
100=a5
001=a2
011=a4
101=a6
110=a7
a8= 111
二元对称信
道的三次扩
展信道
未用
码字
许用
码字
输出端接
收序列
497
有噪信道编码
43222
2223
*,
88878615
84131211
103)
(
2
1
)|(
1
)(,)(,)(,)(
)(,)(,)(,)(
xXY
ijE abp
M
p
abFabFabFabF
abFabFabFabF
最佳译码规则
498
有噪信道编码
• 此时可采用“择多译多”的译码原则，即
根据信道输出端接收序列中0多还是1多，
如果0多译码器就判决为0，1多就判决为1。
同样可得
• pE =错3个码元的概率
• +错2个码元的概率
• =3*10-4
499
有噪信道编码
• 如果进一步增大重复次数n，M仍取2，可得
pE能继续降低，但同时R=logM/n也要减小。
• 由此可见，利用简单重复编码来减小平均错
误概率是以降低信息传输率为代价的。
500
有噪信道编码
• （2）消息符号个数M
• 在一个二元信道的n次无记忆扩展信道中，
输入端共有2n个符号序列可能作为消息符
号，现仅选其中M个作为消息符号传递，则
当M选得大， pE也跟着大，R也大。
501
有噪信道编码
• (1)n=3,M=2, pE=3*10
-4
• R=logM/n=1/3比特/码符号
• (2)n=3,M=4, pE=2*10
-2
• R=logM/n=2/3比特/码符号
• (3)n=3,M=8, pE=3*10
-2
• R=logM/n=1比特/码符号
502
有噪信道编码
• （3）(5,2)线性码
• 采用(5,2)线性码，并适当增大n和M，可以
得到低的平均错误概率和较好的信息传输
速率。
• n=5,M=4, pE=*10
-4
• R=logM/n=2/5比特/码符号
503
有噪信道编码
• 输入符号的4个码字采用如下编码方法：
• 所以，输入端发送序列为
• 00000，01101，10111，11010
35142132211
54321
,,,,
)(
iiiiiiiiiii
iiiiii
aaaaaaaaaaa
aaaaaa
504
有噪信道编码
00000
00100
10000
00001
01000
10001
00011
00010
00000 00000
扩展信道
译码规则发送码字 输出端接收序列
505
有噪信道编码
01101
01001
11101
01100
00101
11100
01110
01111
01101 01101
扩展信道
译码规则发送码字 输出端接收序列
506
有噪信道编码
10111
11111
10110
10101
00111
00110
10100
10011
10111 10111
扩展信道
译码规则发送码字 输出端接收序列
507
有噪信道编码
11010
11110
01010
11011
10010
01011
11001
11000
11010 11010
扩展信道
译码规则发送码字 输出端接收序列
508
有噪信道编码
• （4）汉明距离
• 长度为n的两个二进制序列（码字） 之
间的距离是指 对应位置上码元取值不
同的个数，用符号 表示。
• 例如：
• 若令
ji 和
ji 和
),( jiD
3),(111100101111 jiji D
和运算。表示模其中
则
2
),(
),(),(
1
2121
n
k
jiji
jjjjiiii
kk
nn
yxD
yyyxxx
509
有噪信道编码
• 汉明距离满足以下性质：
• （1）非负性
• （2）对称性
• （3）三角不等式
时等式成立。当且仅当 ji
jiD
0),(
),(),( ijji DD
),(),(),( jikjki DDD
510
有噪信道编码
• 在二进制码C中，任意两个码字的汉明距离
的最小值称为该码C的最小距离，即
• 最小距离Dmin越大，受干扰后，越不容易
把一个码字变为其他码字，因而平均错误
概率pE越小。
• 故在选择编码规则时，应使码字间的距离
越大越好。
CccccccDD jijiji ,)},(min{min
511
有噪信道编码
• （5）用汉明距离表示极大似然译码规则
• 设码字xi与yj之间的距离为D，则表示在
传输过程中有D个位置发生了错误，n-D
个位置没有错误。
)(
2211
)|()|()|()|(
Dn
nn
ppxypxypxypxyp Dijijijij
二进对称信道的传输错误概率为p，当信
道是无记忆时，编码后信道的传递概率为
当p<时，D越大 p(yj |xi)越小
512
有噪信道编码
• 极大似然译码规则可表示为：当收到码字yj
后，在输入码字集 中寻找一个
x*，使之与yj的距离（汉明距离）最短。
• 即选取译码函数F(yj)=x*使之满足
),()*,( min jij yxDyxD
},2,1,{ rixi
513
有噪信道编码
• 例：某二元码字
{111000,001011,010110,101110}
• （1）如果码字等概率分布，求码率。
• （2）采用最大似然准则，收到110110如何
译码。
514
有噪信道编码
• 解：
• （1）码组的码率为
• （2）采用最大似然准则，收到110110后，
与码字集中各码字的汉明距离分别为
3,5,1,2，故应译码为010110
6
4log)(
l
SH
R
515
有噪信道编码
• （三）有噪信道编码定理
• 定理（香农第二定理）：设某信道有r个输入符号，
s个输出符号，信道容量为C 。当信息传输率R<C
时，只要码长n足够长，总可以在输入符号集中找
到M个码字（代表M个等可能性的消息）组成的一
个码（ 是一任意小的正数）和它相应的
译码规则，使信道输出的错误概率pE任意小。
,2 )( CnM
516
线性分组码
• 分组码是由码字或码组构成，码字是一组
固定长度的向量，其长度就是该向量的个
数N。
• 一个码字的元素从q个元素的字符中选取。
当字符由元素0和1组成时，得到的码称为
二进制码，码字的元素称为比特。
517
线性分组码
• 在分组编码器中，k个比特信息被编成n个
比特，增加了n-k个冗余比特，其作用是检
测和纠正错码。
• 分组码也称为(n,k)码，其码率定义为
n
k
Rc
518
线性分组码
• 分组码的性质：
• （1）线性：假设C1与C2是(n,k)分组码中的
两个码字，令 是从字符表中任意选择
的两个元素，则当且仅当 也是一
码字时，分组码是线性分组码。
21 和
2211 CC
一个线性码必定包含全零的码字，一个
固定码重的码是非线性的。
519
线性分组码
• （2）系统性：若一个码字，它前面的若干
比特等同于信息比特，剩余的比特是这些
信息比特的线性组合，则称之为系统码。
对一个(n,k)分组码，其前面k个比特等同
于信息比特，并且每个码字的剩余n-k比
特是k个信息比特的线性组合。
520
线性分组码
• （3）循环性：若 是一个码字，
且由C的循环移位得到的 也是
一个码字，则称码字具有循环特性。
],,,,[ 0121 ccccC nn
],,,,,[ 10132 nnn ccccc
循环码是线性码集合中满足循环移位特性
的一个子集合，即循环码的码字C的所有循
环移位都是码字。
521
线性分组码
• 令 是已被信道编码成的码字cm的
k个信息码元。用行向量分别表示k个信息
码元的向量和编码器输出向量为
],,,[
],,,[
21
21
mnmmm
mkmmm
cccc
xxxx
mkmm xxx ,,, 21
522
线性分组码
• 线性二进制分组编码器的编码运算可以用n
个方程组表示为
• 将其表示成矩阵形式为
• 这表明码字向量c是由信息码元向量x生成
的，故将G称作码字的生成矩阵。
Gxc mm
njgxgxgxc kjmkjmjmmj ,,2,12211
523
线性分组码
• 若令
• 则任何一个码字都可以表示为生成矩阵的
行向量的线性组合，即
knkk
n
n
k ggg
ggg
ggg
g
g
g
G
21
22221
11211
2
1
kmkmmm gxgxgxc 2211
这表明{gi}是(n,k)分组码的基向量，它不是
惟一的，故生成矩阵也不是惟一的。
524
线性分组码
• 一个(n,k)分组码的任何生成矩阵都可以表示成下
面的系统形式：
• 式中Ik是k*k单位矩阵，P是k*(n-k)矩阵，它决定
n-k个冗余码元即奇偶校验码元。
)(21
)(22221
)(11211
1000
0010
0001
][
knkkk
kn
kn
k
ppp
ppp
ppp
PIG
525
线性分组码
• 如果引入(n-k)*n矩阵H ，其转置矩阵HT和
G满足正交关系GHT=0 ，则知
• 也把H称作一致校验矩阵或一致监督矩阵。
][ kn
T IPH
526
线性分组码
• 例：某线性分组码生成矩阵为
• （1）求n,k的值，并写出全部的码字，若
收到000110，判断其是否正确。
• （2）求一致校验矩阵。
110100
011010
101001
G
527
线性分组码
• 解：生成矩阵是3行6列，可知n=6,k=3
110100
011010
101001
][ 321 mmmmGC
528
线性分组码
• 写出所有的码字为：
• 若收到000110则出错了。
316
325
214
33
22
11
mmc
mmc
mmc
mc
mc
mc
000000
001011
010110
100101
011101
101110
110011
111000
529
线性分组码
• 一致校验矩阵为
100101
010110
001011
]'[
IPH
