电子科大信息论与编码2016复习提纲

信息论复习提纲第一章1、信息的概念。

信息是事物运动状态或存在方式的不确定性的描述。

2、信息论的研究对象、研究目的。

对象：通信系统模型。

目的：找到信息传输过程的共同规律，以提高信息传输的可靠性、有效性、保密性和认证性，以达到信息传输系统最优化。

3、通信系统模型的组成，及各部分的功能（1）信息源：产生消息的源，消息可以是文字，语言，图像。

可以离散，可以连续。

随机发生。

（2）编码器：信源编码器：对信源输出进行变换（消去冗余，压缩），提高信息传输的有效性信道编码器：对信源编码输出变换（加入冗余），提高抗干扰能力，提高信息传输的可靠性（3）信道：信号从发端传到收端的介质（4）译码器：译码就是把信道输出（已叠加了干扰）的编码信号进行反变换。

（5）信宿：信宿是消息传送的对象，即接受消息的人或机器。

（6）干扰源：系统各部分引入的干扰，包括衰落，多径，码间干扰，非线性失真，加性噪声，主要研究的是统计特性。

4、消息，信号，信息三者之间的关系信息---可以认为是具体的物理信号、数学描述的消息的内涵，即信号具体载荷的内容、消息描述的含义。

信号---则是抽象信息在物理层表达的外延；消息---则是抽象信息在数学层表达的外延第二章1、信源的分类，着重单符号信源。

信源的概率空间的构成形式。

单消息（符号）信源，离散信源，连续变量信源，平稳信源，无/有记忆信源，马尔可夫信源，随机波形信源。

单消息（符号）信源：单消息（符号）信源－－离散信源单消息（符号）信源－－连续信源2、自信息的计算及物理含义，单位与底数的关系，含义。

计算：含义：当事件ai发生以前，表示事件ai发生的不确定性当事件ai发生以后表示事件ai所含有（所提供）的信息量单位与底数的关系：通信与信息中最常用的是以2为底，这时单位为比特（bit）；理论推导中用以e为底较方便，这时单位为奈特（Nat）；工程上用以10为底较方便，这时单位为哈特（Hart）。

它们之间可以引用对数换底公式进行互换。

信息论复习提纲第一章绪论1．通信系统模型；2．香浓信息的概念；3．信源、信道、信源编码和信道编码研究的核心问题。

第二章离散信源及信源熵1．离散信息量、联合信息量、条件信息量、互信息量定义；2．信源熵、条件熵、联合熵定义；3．平均互信息量定义、性质、三种表达式及物理意义，与其它熵的关系（不证明）；4．最大信源熵定理及证明；5．本章所有讲过的例题；第三章离散信源的信源编码1．信息传输速率、编码效率定义；2．最佳编码定理（即节定理：概率越大，码长越小；概率越小，码长越大）及证明；3．码组为即时码的充要条件；4．单义可译定理（Kraft不等式）及应用；5．费诺编码方法、霍夫曼编码方法应用（二进制，三进制，四进制）；6．本章所有讲过的例题；第四章离散信道容量1．利用信道矩阵计算信道容量（离散无噪信道、强对称离散信道、对称离散信道、准对称离散信道）；2．本章讲过的例题；第五章连续消息和连续信道1．相对熵的定义；2．均匀分布、高斯分布、指数分布的相对熵及证明；3．峰值功率受限条件下的最大熵定理及证明，平均功率受限条件下的最大熵定理及证明，均值受限条件下的最大熵定理及证明；4．香农公式及意义；5．本章所有讲过的例题；第六章差错控制1．重量、最小重量、汉明距离、最小汉明距离、编码效率的定义；2．最小距离与检错、纠错的关系（即节定理）；3．本章所有讲过的例题；第七章线性分组码1．线性分组码定义；2．线性分组码的最小距离与最小重量的关系及证明；3．生成矩阵、一致校验矩阵定义，给出线性方程组求出生成矩阵和一致校验矩阵的标准形式，生成矩阵与一致校验矩阵的关系；4．制作标准阵列并利用标准阵列译码；5．本章所有讲过的例题；第八章循环码1．生成多项式的特点，有关定理（三定理1，定理2，定理3）及证明；2． 生成矩阵、一致校验矩阵定义，如何获得生成矩阵、一致校验矩阵的典型形式；3．本章所有讲过的例题； 习题：1.已知随机变量X 和Y 的联合分布如下：计算：、I(X;Y)。

信源编码的问题是：①怎样保证编码和译码过程不丢失信息，即怎样实现无失真编码？②怎样有效地利用码字的每一个比特携带信息，即在编码过程中怎样用最少的比特数去表示信源的信息熵？解决了这些问题后，介绍几种无失真编码的具体方法。

一、无失真编码的基本思路单符号离散信源：⎭⎬⎫⎩⎨⎧=⎥⎦⎤⎢⎣⎡05.015.03.05.0x x x x )X (P X 43214i i i 1H(X)p(x )logp(x )0.5log0.50.3log0.30.15log0.150.05log0.05==−=−−−−∑其信息熵)symbol /bit (648.1≈要做到无失真编码，就要保证符号元与码字一一对应，此时用码序列表示的信源信息熵保持不变。

最简单的无失真编码是对信源符号进行4-2进制变换，即11x ,10x ,01x ,00x 4321→→→→该编码的码长K=2，码字的每一个比特携带信息的效率即编码效率进一步，如果对该信源的二次扩展信源进行无失真编码，一种能保证符号元与码字一一对应的不等长编码为⎭⎬⎫⎩⎨⎧=⎥⎦⎤⎢⎣⎡0025.00075.0015.0025.0x x x x x x x x 0075.00225.0045.0075.0x x x x x x x x 015.0045.009.015.0x x x x x x x x 025.0075.015.025.0x x x x x x x x )X (P X 4434241443332313423222124131211122111100x x ,0110x x ,010x x ,101x x 11100x x ,1100x x ,100x x ,00x x 4232221241312111→→→→→→→→与第二种编码相比，码字又压缩了约0.04个比特，编码效率提高了2.1%。

总结该例子，有以下几点结论与问题：①一般采用不等长编码，使平均码长接近信息熵，从而在无失真前提下提高编码效率；编码的基本原则是大概率符号元编成短码，小概率符号元编成长码。

其条件概率分布P(X2/X1)
求该信源的联合熵和平均符号熵。
解： H(X1 ) p(xi1 ) log p(xi1 )
3
H(X 2 / X1 ) p(x i1 xi2 )log p(xi 2 / log log log 4 4 9 9 36 36 1.542(bit / symbol)
1 H 2 ( X1 X 2 ) H ( X 1 X 2 ) H ( X1 ) 2
例1，已知二维离散平稳信源的符号 X1 , X 2 {x1 , x 2 , x 3 } ，其概率分布P(X1)
x2 x3 X1 x 1 P ( X ) 1 / 4 4 / 9 11 / 36 1
P( X k ) P( X l )
P( X k X k 1 ) P( X l X l 1 )
则称该多符号离散信源为二维离散平稳信源。 同理，如果除概率分布相同外，直到N维的各 维联合概率分布也都相同，也都与时间起点 无关，即
P( X k ) P( X l )

P( X k X k 1 ) P( X l X l 1 ) P( X k X k 1 X k N 1 ) P( X l X l 1 X l N 1 )
将多符号离散信源发出的符号序列记为
X1X 2 X 3
并设序列中任一符号都取值于同一集合
Xk {x1 , x 2 ,, xn }, k 1,2,
一般情况下，信源在不同时刻发出符号 的概率分布是不同的，即 P( Xk ) P( Xl ), k 1,2,, l 1,2, 这种情况分析起来比较困难，不作讨论。
log e p(xi1 xi2 )ln

§4.2 离散无记忆信道 对称DMC容量的计算

P的所有列都是第一列的一种置换，信 道是关于输出对称的
0 .8 0 .2 P 0 .5 0 .5 0 .2 0 .8
§4.2 离散无记忆信道
命题2 若DMC关于输出为对称的，则当输入分布等概时，输 出分布等概。 证明 此时{p(y|x)，x=0~ K-1}与{p(0|x)，x=0~ K-1}互为置换。 设q(x)=1/K，x∈{0, 1, …, K-1}。则
q( z ) p( y | z )
都取一个相同的值；对任何满足q(k)=0的k，I(X=k; Y)都 不大于此相同的值。 （2）此时此相同的值恰好就是信道容量C。
§4.2 离散无记忆信道
注解
如果对DMC信道没有任何简化，要计算最佳输 入分布并不容易。但是，通常使用的DMC是很简单 的（比如，以下的准对称信道和对称信道），最佳 输入分布很容易求出。
§4.2 ቤተ መጻሕፍቲ ባይዱ散无记忆信道
定理4.2.2(p91) （1）输入概率分布{x, q(x), x∈{0, 1, …, K-1}}是最佳输入分 布的充分必要条件为：对任何满足q(k)>0的k，
I ( X k ; Y ) p( y | k ) log K 1
y 0 z 0 J 1
p( y | k )
第四章：信道及其容量
§4.1 §4.2 §4.5 §4.6 §4.7 信道分类 离散无记忆信道 信道的组合 时间离散的无记忆连续信道 波形信道
5
§4.1 信道分类

所有信道都有一个输入集A，一个输出集B以及 两者之间的联系，如条件概率P(y│x)，x∈A， y∈B。这些参量可用来规定一条信道。

15
N重复码当N很大时，使错误概率Pe降得很低 的同时，信息传输率R也大大降低—如3重复 码的信息率为原信息率的1/3，即该编码的 编码效率仅为1/3 。 需要找这样的纠错码： 足够小的平均译码错误概率Pe 较高的编码效率。
16
1.基本概念：
纠错方式——主要有检错重发(ARQ)、 前向纠错(FEC)和混合纠错(HEC)等。 纠错码——主要有分组码和卷积码两大 类，此外还有1982年提出的将编码与调制 结合在一起的网格编码调制和1993年提出 的将卷积码与随机交织器相结合的Turbo 码、LDPC码等。
p( y j / x*)p( x*)
p( y j / x*)p( x*) p( y j / x i )p( x i )
i 1,2, j 1,2, x* x i
i 1,2, j 1,2, x* x i
6
当信源等概率时，
p(y j / x*) p( y j / x i )
平均译码错误概率:
2 2 2 j 1 2 j 1
i 1,2, j 1,2, x* x i
最小错误概率准则可转换为最大似然译码准 则。
Pe p( y j )p(e / y j ) p( y j )[1 p( x * / y j )]
2 2 j 1 2 j 1 i 1 j 1
7 L 1
i , j 1,2, ,2 , i j
k
例：c1 1011110
d ( c 1 , c 2 ) c 1L c 2 L 3
20
码重(汉明重量):长度为n的码字中非零码 元的个数；对于二元码，码重可表示为：
w (c i ) c i L
n L 1

三、信息的度量
3.1 自信息量
随机事件 x i
出现概率
P xi
自信息量定义
Ixi logPxi
❖ 随机事件的不确定性
▪ 出现概率小的随机事件所包含的不确定性大， 它的自信息量大。
▪ 出现概率大的随机事件所包含的不确定性小， 它的自信息量小。
▪ 在极限情况下，出现概率为1的确定性事件， 其自信息量为零。
2.4 香农信息论
1948 年 ， 美 国 数 学 家 克 劳特·香农（C.E. Shannon） 发表了一篇著名论文“通信 的数学理论”。
该论文给出了信息传输 问题的一系列重要结果，建 立了比较系统的信息理论— —香农信息论。
信息论奠基人——香农
“通信的基本问题就是在一 点重新准确地或近似地再 现另一点所选择的消息”。 这是香农在他的惊世之著 《通信的数学理论》中的 一句铭言。正是沿着这一 思路,他应用数理统计的方 法来研究通信系统，从而 创立了影响深远的信息论。
❖ 若给定x条件下y的条件自信息量为I(y|x)，则它 在XY集合上的概率加权平均值H(Y|X)定义为：
H Y|X P xyIy|x X Y
❖ H(Y|X)为条件熵，也可直接定义为：
H Y |X P x y lo g P y|x
X Y
共熵
❖ 共熵（又称联合熵）是联合空间XY上的每个元素 对xy的自信息量的概率加权平均值，定义为：
计分方式
期终考试占60％ 专题报告占20％；个人报告占20％ 小论文占20%
二、信息概念、信息论
2.1 信息 信息、消息、信号 信息是抽象、复杂的概念，它包含在消息之中，
是通信系统中传递的对象。
2.2 信息定义 信息就是事物运动的状态和方式，就是关于事

[信息论与编码]知识点总结2021/12/02 from Xwhite这个是预习完之后，感觉应该掌握的⼀些知识的总结。

总共分成四个⼤部分吧信息量与信源熵 公式背住，然后套公式，冗余度的概念信道和信道容量 概念，互信息的计算，简单信道容量的计算信源编码 概念，定长编码，变长编码，哈夫曼编码（应该是必考），⾹农编码信道编码 挺难的，编码定理得看，纠错编译码的概念看看就⾏，线性分组码必会，循环码，汉明码。

卷积码应该不考知识点总结第⼀章的⼀些基本概念看书就完了，⽐如信息、消息、通信模型等。

信息量与信源熵背熟！背熟！背熟！因为是知识点总结，所以基本只给出公式，想加深了解可以看课本，当然也可以看看本博客的⽂章先验概率：⽐如，考完试你估算⾃⼰及格的概率是50%，这就是先验概率，你及格的概率。

后验概率：⽐如，你估算完之后，你找个最差的同学⼀问，他说他能及格，也就是在你已知他可能及格的条件下你及格的概率，就是后验概率。

总结如果做题过程中，题⽬问的是单个符号的⾃信息量，那么我们就⽤以下公式。

如果题⽬问的是离散信源的信息量，或者熵，就⽤以下公式。

各概念之间的关系补充⼀些概念我们从信息量的传输⾓度来看通信模型信源：发出信息量H(X)——>信道：信道中损失的信息量H(X|Y)——>信宿：接收端获得的信息量I(X;Y) H(X|Y)：疑义度，也可以叫损失熵，表⽰由于信道上存在⼲扰和噪声⽽损失掉的平均信息量。

H(Y|X)：噪声熵全损信道：⼲扰很⼤，难以从Y中提取X的有效信息，信源发出的所有信息都损失在信道中I(X;Y)=0 ⽐如：加密编码⽆损信道：没有⼲扰，接收端能完全收到信源发出的信息。

I(X;Y)=H(X)冗余度概念看看书。

想要对这⾥的深⼊理解可以看⼀下课本或者看⼀下博客中离散信道的⽂章。

信道和信道容量信道的概念请⾃⾏看书记忆。

总结信源编码定长码：若⼀组码中所有码字的码长相同，则称为定长码变长码：若⼀组码中所有码字的码长各不相同，则称为变长码奇异码：若⼀组码中存在相同的码字，则称为奇异码。

一、填空题1. 设信源X 包含4个不同离散消息，当且仅当X 中各个消息出现的概率为___1/4___时，信源熵达到最大值，为__2__，此时各个消息的自信息量为__2 __。

2.如某线性分组码的最小汉明距dmin=4，则该码最多能检测出___3____个随机错，最多能纠正__1____个随机错。

3.克劳夫特不等式是唯一可译码___存在___的充要条件。

4.平均互信息量I(X;Y)与信源熵和条件熵之间的关系是___(X;Y)=H(X)-H(X/Y )___。

5._信源___提高通信的有效性，_信道____目的是提高通信的可靠性，_加密__编码的目的是保证通信的安全性。

6.信源编码的目的是提高通信的 有效性 ，信道编码的目的是提高通信的 可靠性 ，加密编码的目的是保证通信的 安全性 。

7.设信源X 包含8个不同离散消息，当且仅当X 中各个消息出现的概率为__1/8__时，信源熵达到最大值，为___3____。

8.自信息量表征信源中各个符号的不确定度，信源符号的概率越大，其自信息量越_小___。

9.信源的冗余度来自两个方面，一是信源符号之间的__相关性__，二是信源符号分布的__不均匀性__。

10.最大后验概率译码指的是 译码器要在已知r 的条件下找出可能性最大的发码 作为译码估值 ，即令 =maxP( |r)_ __。

11.常用的检纠错方法有__前向纠错___、反馈重发和混合纠错三种。

二、单项选择题1.下面表达式中正确的是（A ）。

A.∑=j i j x y p 1)/( B.∑=i i j x y p 1)/( C.∑=j j j iy y x p )(),(ω D.∑=ii j i x q y x p )(),( 2.彩色电视显像管的屏幕上有5×105 个像元，设每个像元有64种彩色度，每种彩度又有16种不同的亮度层次，如果所有的彩色品种和亮度层次的组合均以等概率出现，并且各个组合之间相互独立。

[信息论与编码]知识点总结2021/12/02 from Xwhite这个是预习完之后，感觉应该掌握的⼀些知识的总结。

总共分成四个⼤部分吧信息量与信源熵 公式背住，然后套公式，冗余度的概念信道和信道容量 概念，互信息的计算，简单信道容量的计算信源编码 概念，定长编码，变长编码，哈夫曼编码（应该是必考），⾹农编码信道编码 挺难的，编码定理得看，纠错编译码的概念看看就⾏，线性分组码必会，循环码，汉明码。

卷积码应该不考知识点总结第⼀章的⼀些基本概念看书就完了，⽐如信息、消息、通信模型等。

信息量与信源熵背熟！背熟！背熟！因为是知识点总结，所以基本只给出公式，想加深了解可以看课本，当然也可以看看本博客的⽂章先验概率：⽐如，考完试你估算⾃⼰及格的概率是50%，这就是先验概率，你及格的概率。

后验概率：⽐如，你估算完之后，你找个最差的同学⼀问，他说他能及格，也就是在你已知他可能及格的条件下你及格的概率，就是后验概率。

总结如果做题过程中，题⽬问的是单个符号的⾃信息量，那么我们就⽤以下公式。

如果题⽬问的是离散信源的信息量，或者熵，就⽤以下公式。

各概念之间的关系补充⼀些概念我们从信息量的传输⾓度来看通信模型信源：发出信息量H(X)——>信道：信道中损失的信息量H(X|Y)——>信宿：接收端获得的信息量I(X;Y) H(X|Y)：疑义度，也可以叫损失熵，表⽰由于信道上存在⼲扰和噪声⽽损失掉的平均信息量。

H(Y|X)：噪声熵全损信道：⼲扰很⼤，难以从Y中提取X的有效信息，信源发出的所有信息都损失在信道中I(X;Y)=0 ⽐如：加密编码⽆损信道：没有⼲扰，接收端能完全收到信源发出的信息。

I(X;Y)=H(X)冗余度概念看看书。

想要对这⾥的深⼊理解可以看⼀下课本或者看⼀下博客中离散信道的⽂章。

信道和信道容量信道的概念请⾃⾏看书记忆。

总结信源编码定长码：若⼀组码中所有码字的码长相同，则称为定长码变长码：若⼀组码中所有码字的码长各不相同，则称为变长码奇异码：若⼀组码中存在相同的码字，则称为奇异码。

信道传递概率可以用信道矩阵来表示：
x1 x2 P xr
y1 p( y1 | x1 ) p( y | x ) 1 2 p( y1 | xr )
y2 p( y2 | x1 )
p( y2 | x2 ) p( y2 | xr )
ys p( ys | x1 ) 1 p( ys | x2 ) p( ys | xr )
i
第四章：信道及信道容量
二、离散单符号信道及其信道容量
1.离散单符号信道的数学模型（续14）
例3：求二元删除信道的 H ( X )、H (Y )、H ( X | Y )和I ( X ;Y ) 。
已知
1 3 PX 4 4
1 1 2 2 0 P 1 2 0 3 3
3. 后验概率（后向概率）: 贝叶斯公式
p ( xi | y j ) p ( xi y j ) p( y j ) p ( xi ) p ( y j | xi )
p( x ) p( y
i 1 i
r
j
| xi )
（i =1，2，…，r;j =1，2，…，s）
且
p ( xi | y j ) 1
Y y2
ys
i 1, 2,..., r ; j 1, 2,..., s
满足： （1）0≤ p(yj|xi) ≤ 1 (i=1,2,…,r；j=1,2,…,s) （2）
p( y j | xi ) 1
j 1
s
(i=1,2,…,r)
第四章：信道及信道容量
二、离散单符号信道及其信道容量
1.离散单符号信道的数学模型（续2）
r s
第四章：信道及信道容量

《信息论与编码》课程教学大纲一、课程基本信息课程代码：16052603课程名称：信息论与编码英文名称：Information Theory and Coding课程类别：专业课学时：48学分：3适用对象:信息与计算科学考核方式：考试先修课程：数学分析、高等代数、概率论二、课程简介《信息论与编码》是信息科学类专业本科生必修的专业理论课程。

通过本课程的学习，学生将了解和掌握信息度量和信道容量的基本概念、信源和信道特性、编码理论等，为以后深入学习信息与通信类课程、为将来从事信息处理方面的实际工作打下基础。

本课程的主要内容包括：信息的度量、信源和信源熵、信道及信道容量、无失真信源编码、有噪信道编码等。

Information Theory and Coding is a compulsory professional theory course for undergraduates in information science. Through this course, students will understand and master the basic concepts of information measurement and channel capacity, source and channel characteristics, coding theory, etc., lay the foundation for the future in-depth study of information and communication courses, for the future to engage in information processing in the actual work.The main contents of this course include: information measurement, source and source entropy, channel and channel capacity, distortion-free source coding, noisy channel coding, etc。

信息论与编码学习辅导及习题详解Information Theory and Coding Learning Coaching and Exercise ExplanationInformation Theory and Coding are two closely related scientific disciplines for signal processing, data communication, and computer networks. These two studies are often used together in applications, making the learning of the concepts of Information Theory and Coding important. This essay will guide through the basic knowledge of these two fields, provide coaching on learning Information Theory and Coding, and go through exercise explanations.I. Information TheoryA. DefinitionInformation Theory is a branch of applied mathematics and electrical engineering dealing with the quantification, storage, and communication of information. It was developed in 1948 by Claude Shannon. The fundamental problem of communication is to convey a message from a sender to a receiver without any errors. Information Theory is the study of how information is transmitted over a communication medium, and how the communication medium affects the transmission process.B. Basic ConceptsSome basic concepts of Information Theory are entropy, noise, channel capacity, coding, and error control. Entropy is a measure of uncertainty, and is used to help determine the amount of information contained in a signal.Noise is any disturbances that have an impact on the transmission of information. Channel capacity is the maximum amount of data that can be transmitted through a communication channel. Coding is the process of translating the message from the source into a form that can be understood by the destination. Error control is the process of detecting, identifying, and correcting any errors that occur during transmission.II. CodingA. DefinitionCoding is a branch of mathematics and computer science dealing with the efficient representation of data. It was developed in the late 1950s and early 1960s. Coding is used in a variety of applications, including data storage, image processing, digital signal processing, and communications. Coding techniques can greatly reduce the amount of data that needs to be stored and transmitted.B. Basic ConceptsThe main concepts of Coding are coding, signaling, modulation, coding rate, coding efficiency, and entropy. Coding is the process of transforming the message from the source into a form that can be understood by the destination. Signaling is the process of conveying information through a medium over a communication link. Modulation is the process of varying some aspect of a signal in order to transmit information. The coding rate is the number of bits required to encode one message. The coding efficiency is the ratio between the actual number of bits used to encode the message, and the total number of bits used. Entropy is a measure of the amount of information contained in a signal.III. Learning CoachingA. FundamentalsThe best way to learn the fundamentals of Information Theory and Coding is to start by familiarizing oneself with the core concepts such as entropy, noise, channel capacity, coding, and error control. Taking a college course in Information Theory and Coding is also beneficial. Alternatively, reading textbooks and studying reference material is a viable option.B. PracticePracticing the concepts of Information Theory and Coding is essential to mastering them. It is important to try to understand the material rather than memorize it. Doing practice problems is the best way to learn and build an understanding of the material.IV. Exercise ExplanationA. Information TheoryFor the Information Theory part of this exercise, the main goal is to determine the maximum rate at which data can be transmitted through a given communication channel. To do this, one needs to first calculate the entropy of the signal to determine the amount of information contained in it. Then, the channel capacity needs to be calculated by taking the s ignal’s entropy, the noise of the channel, and the coding rate into consideration.B. CodingFor the Coding part of this exercise, the main goal is to encode a message into a format that can be understood by the destination. To do this, one needsto first select an appropriate coding technique. Then, the information needs to be encoded using this technique. Finally, the encoded message needs to be transmitted through a communication link.In conclusion, Information Theory and Coding are two important scientific fields for signal processing, data communication, and computer networks. This essay has guided through the basics of these two fields, provided coaching on learning Information Theory and Coding, and gone through exercise explanations. Therefore, it is essential for one to understand the fundamentals of Information Theory and Coding and practice the concepts in order to gain mastery in these fields.。

p(xi)(i=1,2,…,n)或概率密度函数p(x)的上凸函数。
根据上凸函数定义，如果I(X;Y)在定义域内对
p(xi)或p(x)的极值存在，则该极值一定是极大
值。信道容量就是在固定信道情况下，求平均
C max I ( X ; Y )
互信息极大值的问题，即
p ( xi )

•I(X;Y)又是信道转移概率分布
11/100，可知相应的信息传输速率为：
89
R P (ai ) log
i 1
1
1
P (a90 ) log
P (ai )
P (a90 )
1
11
100
log100
log
100
100
11
log100 0.11log11
89
6.264 (bit / s )
比较 R’与无失真传输条件下的信息率R ,

例：设信源具有一百个以等概率出现的符号a1， a2，…，
a99，a100，并以每秒发出一个符号的速率从信源输出。试
求在允许失真度D＝0.1条件下，传输这些消息所需要的最
小信息率。
信源
a1, a2,..., a99,
a100
a1～a100
a1～a90
试验信道
{p(yj|xi)}
失真信
(a) 源
无扰离散
率P(yj|xi)为零时，所对应的dij为无限大）
该失真信源的组合方案的平均失真函数为：
d
P( x )P( y
i
j
| x i )d ij
XY

P( x )P( y
i
X 1Y1
j

pe x k p y x k y
mk
p p
y y
xm xk
式中0 , 1，因为 , 都是任意数，可取 1
，则有
1
pe x k
p y x k
1 1
p y x m
1 1
（5-8）
Υ
mk
3． 随机编码错误概率上界
Gallager限仅给出发送码矢xk时的错误概率上界，还要对全 部码矢求平均，下面对上述的随机编码集合求平均。
出错概率为p，故序列差错概率为p，误比特率 （3）总差错概率（误比特率）：
p2
1 3
p
。
pe
p1
p2
1 4
1 3
p
【例5.4】 奇偶校验码 在信息序列后面加上一位校验位，使 之模2和等于1，这样的编码称为奇校验码；若使模2和等于0， 这样的编码就称为偶校验码，即每个码矢中1的个数固定为奇 数或偶数。
x3
0.4 ，信道转移概
0.5 0.3 0.2
率矩阵 P 0.1
0.3
0.7 0.3
0.2 0.4
,信道输出符号Y
=
{y1,
y2,
y3}，按最
大后验概率准则译码。
(1)根据p (xy) = p (y︱x) q(x) 算出全概率，用矩阵表示
0.25 0.15 0.10
p(xy) 0.01 0.07 0.02
1
1
记 ln q(x) p( y x)1 E0 (, q) , 0 1
y x
则式(5-16)可写成
pe < exp {-n [-R + E0 (, q ) ]}
(5-17)
对式(5-17)右边求极小值，即对指数-R + E0 (, q )求极大

第五章无失真信源编码定理与编码5．1．1 信源编码和码的类型1．信源编码2．码的类型若码符号集中符号数r=2称为二元码，r=3称为三元码，……，r元码。

若分组码中所有码字的码长都相同则称为等长码，否则称为变长码。

若分组码中所有码字都不相同则称为非奇异码，否则称为奇异码。

若每个码符号x i∈X的传输时间都相同则称为同价码，否则称为非同价码。

若分组码的任意一串有限长的码符号只能被唯一地译成所对应的信源符号序列则称为唯一可译码，否则称为非唯一可译码。

若分组码中,没有任何完整的码字是其他码字的前缀，则称为即时码（又称非延长码或前缀条件码），否则称为延长码。

本章主要研究的是同价唯一可译码.5．1．2 即时码及其树图构造法即时码（非延长码或前缀条件码)是唯一可译码的一类子码。

即时码可用树图法来构造。

构造的要点是:（1）最上端为树根A，从根出发向下伸出树枝，树枝总数等于r，树枝的尽头为节点。

（2）从每个节点再伸出r枝树枝，当某节点被安排为码字后,就不再伸枝，这节点为终端节点。

一直继续进行，直至都不能伸枝为止。

(3）每个节点所伸出的树枝标上码符号，从根出发到终端节点所走路径对应的码符号序列则为终端节点的码字。

即时码可用树图法来进行编码和译码。

从树图可知，即时码可以即时进行译码。

当码字长度给定，即时码不是唯一的。

可以认为等长唯一可译码是即时码的一类子码。

5．1．3 唯一可译码存在的充要条件（1)对含有q个信源符号的信源用含r个符号的码符号集进行编码,各码字的码长为l1，l2,…,l q的唯一可译码存在的充要条件是,满足Kraft不等式5．1．4 唯一可译码的判断法唯一可译码的判断步骤:首先，观察是否是非奇异码.若是奇异码则一定不是唯一可译码。

其次，计算是否满足Kraft不等式。

若不满足一定不是唯一可译码。

再次，将码画成一棵树图，观察是否满足即时码的树图的构造,若满足则是唯一可译码。

或用Sardinas和Patterson设计的判断方法：计算出分组码中所有可能的尾随后缀集合F，观察F中有没有包含任一码字，若无则为唯一可译码;若有则一定不是唯一可译码.上述判断步骤中Sardinas和Patterson设计的判断方法是能确切地判断出是否是唯一可译码的方法,所以可以跳过前三个步骤直接采用该判断法。

第5章离散信道及信道容量信道是传输信息的媒质，信道能通过的信息量不仅与信道的物理特性有关，而且与携带信息的信号形式和信源符号的统计特性有关。

信息论中所讨论的是物理特性一定的前提下的信道，通常可将信道分为离散信道和连续信道(continuous channel)，本章主要讨论的问题：①从整体的角度，如何度量在离散信道中流通的信息量？②在离散信道中流通的信息量能达到的最大值是多少？1、单符号离散信道的数学模型一、单符号离散信道的信道容量1)x (p n ,,2,1i ,1)x (p 0n1i i i ==≤≤∑=且L ⎭⎬⎫⎩⎨⎧=⎥⎦⎤⎢⎣⎡)x (p )x (p )x (p x x x )X (P X n 21n 21L L 单符号离散信源：⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=)x /y (p )x /y (p )x /y (p )x /y (p )x /y (p )x /y (p )x /y (p )x /y (p )x /y (p )X /Y (P n m n 2n 12m 22211m 1211LL LL L LLn,,2,1i 1)x /y (P 1)x /y (P 0m1j i j i j L ==≤≤∑=且单符号离散信道的数学模型可表示为：x i 对y j 的互信息量I(y j ;x i )所反映的是信源输出x i 而信宿接收到y j ，信宿消息y j 所含信源消息x i 的信息量互信息量在联合概率空间的统计平均值，它反映的是单个符号在信道流通所携带的平均信息量。

∑∑∑===+−=n i mj j i j i n i i i )y /x (p log )y x (p )x (p log )x (p 111)Y /X (H )X (H −=其中，条件熵H(X/Y)也是信道所给出的平均“信息”量，通常称为损失熵，也称为信道疑义度。

该式是站在信宿角度，利用信源发出的信息熵和信道的损失熵来度量信道中传输的平均信息量。