信息论基础教程
李亦农 李梅 编著
目录
第一章 绪论
第二章 信息的度量
第三章 信源及信息熵
第四章 信道及信道容量
第五章 无失真信源编码
第六章 有噪信道编码
第七章 限失真信源编码
第一章 绪论
信息的概念
信息论研究的对象、目的和内容
信息的概念
信息论是关于信息的本质和传输规律的科学的理论，是研究信息的计量、发送、传递、交换、接收和储存的一门新兴学科。
信息的概念
信息论是通信的数学基础，它是随着通信技术的发展而形成和发展起来的一门新兴的横断学科。信息论创立的标志是1948年Claude Shannon （香农）发表的论文 “A Mathematical Theory
of Communication”。在这篇文章中香农创造
性的采用概率论的方法来研究通信中的问题，
并且对信息给予了科学的定量描述，第一次
提出了信息熵的概念。
1928年，哈特莱(Hartley)首先提出了
用对数度量信息的概念。一个消息所含有的
信息量用它的可能值的个数的对数来表示。
香农
香农信息:信息是事物运动状态或存在方式的不确定性的描述。
可运用研究随机事件的数学工具——概率来测度不确定性的大小。在信息论中，我们把消息用随机事件表示，而发出这些消息的信源则用随机变量来表示。
我们把某个消息 出现的不确定性的大小，定义为自信息，用这个消息出现的概率的对数的负值来表示：
自信息同时表示这个消息所包含的信息量，也就是最大能够给予收信者的信息量。如果消息能够正确传送，收信者就能够获得这么大小的信息量。
信源所含有的信息量定义为信源发出的所有可能消息的平均不确定性，香农把信源所含有的信息量称为信息熵(entropy)。自信息的统计平均定义为信源熵，即
这里的q表示信源消息的个数。信息熵表示信源的平均不确定性的大小，同时表示信源输出的消息所含的平均信息量。因此，虽然信源产生的消息可能会含有不同的信息量。
在收信端，信源的不确定性得到了部分或全部的消除，收信者就得到了信息。信息在数量上等于通信前后“不确定性”的消除量（减少量）。
信息论的研究对象、目的和内容
信息论的研究对象是广义的通信系统，它把所有的信息流通系统都抽象成以下的模型：
图 通信系统模型
这个通信系统主要分成五个部分：
（1）信源。顾名思义，信源是产生消息和消息序列的源。
（2）编码器。编码就是把消息变成适合在信道传输的物理量，这种物理量称为信号。编码器可分为信源编码器、信道编码器。
信源编码的目的为了提高通信系统的有效性和提高信息传输的可靠性。在实际的通信系统中，可靠性和有效性常常相互矛盾 。
（3）信道。信道是指通信系统把载荷消息的信号从发送端送到接收端的媒介或通道，是包括收发设备在内的物理设施。
（4）译码器。译码就是把信道输出的已迭加了干扰的编码信号进行反变换，变成信宿能够接受的消息。译码器也可分成信源译码器和信道译码器。
（5）信宿。信宿是消息传送的对象，即接受消息的人或机器。
信息论研究的是关于这个通信系统的最根本、最本质的问题。例如：
①什么是信息？如何度量信息？
②怎样确定信源中含有多少信息量？
③对于一个信道，它传输信息量的最高极限（信道容量）是多少？
④为了能够无失真的传输信源信息，对信源编码时所需的最少的码符号数是多少？（无失真信源编码即香农第一定理）
⑤在有噪信道中有没有可能以接近信道容量的信息传输率传输信息而错误概率几乎为零？（有噪信道编码即香农第二定理）
⑥如果对信源编码时允许一定量的失真，所需的最少的码符号数又是多少？（限失真信源编码即香农第三定理）
目前，对信息论的研究内容一般有三种理解：
（1）狭义信息论：又称香农信息论。主要通过数学描述与定量分析，研究通信系统从信源到信宿的全过程，包括信息的测度、信道容量以及信源和信道编码理论等问题，强调通过编码和译码使收、发两端联合最优化，并且以定理的形式证明极限的存在。这部分内容是信息论的基础理论。
（2）一般信息论：也称工程信息论。主要也是研究信息传输和处理问题，除香农信息论的内容外，还包括噪声理论、信号滤波和预测、统计检测和估计、调制理论、信息处理理论以及保密理论等。
（3）广义信息论：不仅包括上述两方面内容，而且包括所有与信息有关的自然和社会领域，如模式识别、计算机翻译、心理学、遗传学、神经生理学、语言学、语义学甚至包括社会学中有关信息的问题。
第二章 信息的度量
自信息和互信息
平均自信息
平均互信息
关于信息的度量有几个重要的概念：
（1）自信息：一个事件（消息）本身所包含的信息量，它是由事件的不确定性决定的。比如抛掷一枚硬币的结果是正面这个消息所包含的信息量。
（2）互信息：一个事件所给出关于另一个事件的信息量，比如今天下雨所给出关于明天下雨的信息量。
（3）平均自信息（信息熵）：事件集（用随机变量表示）所包含的平均信息量，它表示信源的平均不确定性。比如抛掷一枚硬币的试验所包含的信息量。
（4）平均互信息：一个事件集所给出关于另一个事件集的平均信息量，比如今天的天气所给出关于明天的天气的信息量。
自信息和互信息
自信息
随机事件的自信息量 是该事件发生概率 的函数，并且应该满足以下公理化条件：
1. 是 的严格递减函数。当 时， ，概率越小，事件发生的不确定性越大，事件发生以后所包含的自信息量越大。
2． 极限情况下当 =0时， ；当 =1时， =0。
3． 另外，从直观概念上讲，由两个相对独立的不同的消息所提供的信息量应等于它们分别提供的信息量之和。
可以证明，满足以上公理化条件的函数形式是对数形式。
如果实函数f(x)(1 ≤ x ≤ ∞)满足以下条件:
f(x) ≥ 0
f(x)是严格单调增函数,即若x<y，则f(x)<f(y)
f(x﹒y)=f(x)+f(y)
则f(x)=clog x
定义 随机事件的自信息量定义为该事件发生概率的对数的负值。设事件 的概率为 ，则它的自信息定义为
从图种可以看到上述信息量的定义正
是满足上述公理性条件的函数形式。
代表两种含义：当事件发生以前，
等于事件发生的不确定性的大小；当事
件发生以后，表示事件所含有或所能提
供的信息量。
图 自信息量
自信息量的单位与所用对数的底有关。
（1）常取对数的底为2，信息量的单位为比特（bit，binary unit）。当 =1/2时， =1比特，即概率等于1/2的事件具有1比特的自信息量。
（2）若取自然对数（对数以e为底），自信息量的单位为奈特（nat，natural unit）。 1奈特= 比特=比特
（3）工程上用以10为底较方便。若以10为对数底，则自信息量的单位为哈特莱（Hartley）。1哈特莱= 比特=比特
（4）如果取以r为底的对数（r>1），则 = 进制单位 1r进制单位= 比特
例
1. 英文字母中”a”出现的概率为，“c”出现的概率为，分别计算它们的自信息量
2. 假定前后字母出现是互相独立的，计算“ac”出现的自信息量
3. 假定当“a”出现后，出现“c”的概率为，计算“a”出现后， “c”出现的自信息量
例 同时扔一对均匀色子，当得知“两色子两朝上点数之和为2”或“两色子面朝上点数为3和4”时，试问，这两种情况分别获得多少信息量。
互信息
定义 一个事件 所给出关于另一个事件 的信息定义为互信息，用 表示。
互信息 是已知事件 后所消除的关于事件 的不确定性，它等于事件 本身的不确定性 减去已知事件 后对 仍然存在的不确定性 。
互信息的引出，使信息得到了定量的表示，是信息论发展的一个重要的里程碑。
例 某地二月份天气出现的概率分别为晴1/2，阴1/4，雨1/8，雪1/8。某天有人告诉你：“今天不是晴天”，把这句话作为收到的消息y1，求收到y1后， y1与各种天气的互信息量。
解：把各种天气记作x1(晴),x2(阴),x3(雨),x4(雪)，收到消息y1后，阴天发生的概率为
例 四个等概率分布的消息M1,M2,M3,M4被送入一个二元无记忆对称信道（它的输入\输出符号取值{0，1}）进行传送，通过编码使M1=00，M2=01，M3=10，M4=11,
试问：（1）输入是M1和输出第一个符号是0的互信息是多少？
X Y
0 0
P
P
1 1
解：根据题意知
P(M1)= P(M2)= P(M3)= P(M4)=1/4
而P(0|M1)=P(0|0)=
所以输入M1和输出第一个符号为0 的联合概率P(M1,0)= P(M1) *P(0|M1)=1/4
根据信道特性，输出第一个符号为0的概率
（2）如果知道第二个符号也是0，这时带来多少附加信息量？（课堂习题）
平均自信息
平均自信息（信息熵）的概念
自信息量是信源发出某一具体消息所含有的信息量，发出的消息不同所含有的信息量不同。因此自信息量不能用来表征整个信源的不确定度。我们定义平均自信息量来表征整个信源的不确定度。平均自信息量又称为信息熵、信源熵，简称熵。
因为信源具有不确定性，所以我们把信源用随机变量来表示，用随机变量的概率分布来描述信源的不确定性。通常把一个随机变量的所有可能的取值和这些取值对应的概率 称为它的概率空间。
定义 随机变量X的每一个可能取值的自信息 的统计平均值定义为随机变量X的平均自信息量:
这里q为的所有X可能取值的个数。
熵的单位也是与所取的对数底有关，根据所取的对数底不同，可以是比特/符号、奈特/符号、哈特莱/符号或者是r进制单位/符号。通常用比特/符号为单位。
一般情况下，信息熵并不等于收信者平均获得的信息量，收信者不能全部消除信源的平均不确定性，获得的信息量将小于信息熵。
熵函数的性质
信息熵 是随机变量X的概率分布的函数，所以又称为熵函数。如果把概率分布 ，记为 ，则熵函数又可以写成概率矢量 的函数的形式，记为 。
熵函数 具有以下性质：
1.对称性：
性说明熵函数仅与信源的总体统计特性有关。
2. 确定性：
在概率矢量中，只要有一个分量为1，其它分量必为0，它们对熵的贡献均为0，因此熵等于0。也就是说确定信源的不确定度为0。
3. 非负性：
对确定信源，等号成立。信源熵是自信息的数学期望，自信息是非负值，所以信源熵必定是非负的。
4. 扩展性：
这个性质的含义是增加一个基本不会出现的小概率事件，信源的熵保持不变。
5. 连续性：
即信源概率空间中概率分量的微小波动，不会引起熵的变化。
6．递增性
这性质表明，假如有一信源的n个元素的概率分布为 ，其中某个元素 又被划分成m个元素，这m个元素的概率之和等于元素 的概率，这样得到的新信源的熵增加，熵增加了一项是由于划分产生的不确定性。
7. 极值性：
式中n是随机变量X的可能取值的个数。
极值性表明离散信源中各消息等概率出现时熵最大，这就是最大离散熵定理。连续信源的最大熵则与约束条件有关。
8. 上凸性: 是严格的上凸函数，设
则对于任意小于1的正数 有以下不等式成立：
凸函数在定义域内的极值必为极大值，可以利用熵函数的这个性质可以证明熵函数的极值性。
以下例子说明信息熵的含义
例 有一布袋内放100个球，其中80个球为红色，20个球为白色。若随意摸取一个球，猜测是什么颜色。
这一随机事件的概率空间为：
a1– 表示摸出红球，a2– 表示摸出白球
则
若每次摸出一个球后又放回，再进行第二次摸取，那么n次中，红球出现的次数约为np(a1)次，白球出现的次数约为np(a2)次，
则摸取n次后共获得的信息量为
平均摸取一次所能获得的信息量约为
信息熵具有以下三种物理含义
信息熵H(x)是信源输出后，每个消息（或符号）所提供的平均信息量
信息熵H(x)是表示信源输出前，信源的平均不确定性
用信息熵H(x)来表征变量X的随机性
注：信息熵是信源的平均不确定性的描述。
一般情况下获得的信息量是两熵之差，并不是信息熵本身。
例扔一对质地均匀色子，确定其面朝上的点数。当得知点数和为8时，获得信息量为：Log36-log5
直观来看，随机变量的不确定程度并不都是一样的。香农指出，存在这样的不确定性的度量，它是随机变量的概率分布的函数，而且必须满足三个公理性条件：
1. 连续性条件： 应是 的连续函数；
2. 等概时为单调函数： 应是 的增函数；
3. 递增性条件：当随机变量的取值不是通过一次试验而是若干次试验才最后得到时，随机变量在各次试验中的不确定性应该可加，且其和始终与通过一次试验取得的不确定程度相同，即：
其中
联合熵与条件熵
一个随机变量的不确定性可以用熵来表示，这一概念可以方便地推广到多个随机变量。
定义 二维随机变量 的概率空间表示为
其中 满足概率空间的非负性和完备性：
二维随机变量 的联合熵定义为联合自信息的数学期望，它是二维随机变量 的不确定性的度量。
定义 给定 时， 的条件熵：
其中， 表示已知 时， 的平均不确定性。
各类熵之间的关系：
1．联合熵与信息熵、条件熵的关系：
这个关系可以方便地推广到N个随机变量的情况：
称为熵函数的链规则。
推论：当二维随机变量X，Y相互独立时，联合熵等于X和Y各自熵之和：
2 ．条件熵与信息熵的关系：
3 ．联合熵和信息熵的关系：
当X、Y相互独立时等号成立。
熵的基本性质
信源空间
1.对称性
当变量 的顺序任意互换时，熵函数的值不变，即
若某些信源的统计特性相同（含有的符号数和概率分布相同），则这些信源的熵相同。
熵的局限性：熵不能描述事件本身的具体含义和主观价值
2.确定性
H(1,0)=H(1,0,0)=…=H(1,0, …,0)=0
3.非负性
对连续信源不存在该性质。
4.扩展性
该性质说明：信源的取值数增多时，若这些值对应的概率很小（接近于零），则信源的熵不变
5.可加性（即统计独立信源X和Y的联合熵等于分别熵之和）
H(X,Y)=H(X)+H(Y)
可加性是熵函数的一个重要特性，正因为具有可加性，所以可以证明熵函数的形式是唯一的，不可能有其他形式存在.
6.强可加性（链法则）
H(X,Y)=H(X)+H(Y|X)=H(Y)+H(X|Y)
证明：
7. 递增性
例运用熵函数的递增性，计算H(1/3,1/3,1/6,1/6)
8.极值性
即
此式表示在离散信源情况下，信源各符号等概率分布时，熵值达到最大。
证明：设概率矢量P=(p1,p2, …pn),并有
另设随机变量
∵log Y在正实数集（Y>0)上是一上凸（凹）函数
定义区间（a,b)上的一个函数f(x) 为凹函数，如果对任意x1,x2∈(a,b)和 ，有
∴根据Jensen不等式（Jensen不等式：如果f是一个凹函数，X是取值X的一个随机变量，E表示数学期望，则E[f(x)] ≤f(E[X])）
平均互信息
平均互信息的概念
为了从整体上表示从一个随机变量Y所给出关于另一个随机变量
的信息量，我们定义互信息 在的 联合概率空间中的统计平均值为随机变量X和Y间的平均互信息：
定义
平均互信息的性质
1.非负性:
平均互信息是非负的，说明给定随机变量Y后，一般来说总能消除一部分关于X的不确定性。
2.互易性（对称性）：
对称性表示Y从X中获得关于的信息量等于X从Y中获得关于的信息量。
3.平均互信息和各类熵的关系:
当 统计独立时，
4. 极值性：
极值性说明从一个事件提取关于另一个事件的信息量，至多只能是另一个事件的平均自信息量那么多，不会超过另一事件本身所含的信息量。
5. 凸函数性:
定理 当条件概率分布 给定时，平均互信息 是输入分布 的上凸函数。
定理 对于固定的输入分布 ，平均互信息量 是条件概率分布 的下凸函数。
数据处理定理
为了证明数据处理定理，我们需要引入三元随机变量 的平均条件互信息和平均联合互信息的概念。
定义 平均条件互信息
它表示随机变量 给定后，从随机变量 所得到得关于随机变量
的信息量。
定义 平均联合互信息
它表示从二维随机变量 所得到得关于随机变量 的信息量。
定理 （数据处理定理）
如果随机变量 构成一个马尔可夫链，则有以下关系成立：
等号成立的条件是对于任意的 ，有
数据处理定理再一次说明，在任何信息传输系统中，最后获得的信息至多是信源所提供的信息，如果一旦在某一过程中丢失一些信息，以后的系统不管如何处理，如不触及丢失信息的输入端，就不能再恢复已丢失的信息，这就是信息不增性原理，它与热熵不减原理正好对应，反映了信息的物理意义。
§相对熵
§ 相对熵也称鉴别信息、方向散度、交叉熵、Kullback熵、K-L数等。相对熵是两个概率分布差异的一种度量。
设离散随机变量X的可能取值为
且X的概率分布与假设H1和H2有关，即在假设H1下，X的概率分布为
在假设H2下，X的概率分布为
另外，假设H1和H2成立的概率分别为p(H1 )和p(H2)
则根据条件概率公式和全概率公式，有
上式右边第一项是已知X取xk时，假设H1和H2的对数似然比，右边第二项是未知X取xk时，假设H1和H2的对数似然比，可以看出 对数似然比刚好等于随机变量X在取xk前后假设H1和H2的对数似然比之差。
定义 我们定义 为随机变量X在取xk时所提供的在鉴别假设H1和H2时倾向于H1的信息
对数似然比 在假设H1下的数学期望就称为鉴别信息或相对熵。记为
相对熵是在为鉴别H1和H2而对随机变量X在H2假设的分布下进行观察所得到的倾向于H1的信息量，也可以理解为：观察者对随机变量X的了解由分布q(x)->p(x)时所获得的信息量
定理 D(p||q) ≥0,且等号成立的充要条件是，p(x)=q(x)对所有x∈X成立
证明：
以下利用相对熵证明熵的性质8（极值性）
第三章 信源及信息熵
信源的分类及其数学模型
离散单符号信源
离散多符号信源
* 连续信源
信源(Information Source)是信息的来源，是产生消息（符号）、时间离散的消息序列（符号序列）以及时间连续的消息的来源。
信源输出的消息都是随机的，因此可用概率来描述其统计特性。在信息论中，用随机变量X、随机矢量X、随机过程 分别表示产生消息、消息序列以及时间连续消息的信源。
信源的主要问题：
1．如何描述信源（信源的数学建模问题）
2．怎样计算信源所含的信息量
3．怎样有效的表示信源输出的消息，也就是信源编码问题
信源的分类及其数学模型
信源的分类由多种方法，我们常根据信源输出的消息在时间和取值上是离散或连续进行分类：
不常见
离散
连续
随机过程
语音、音乐、热噪声、图形、图象
波形信源
（模拟信源）
连续
连续
连续随机变量序列
跳远比赛的结果、语音信号抽样以后
连续信号
连续
离散
离散随机变量序列
文字、数据、
离散化图象
离散信源
（数字信源）
离散
离散
数学描述
举例
信源种类
取值
时间（空间)
表 信源的分类
我们还可以根据各维随机变量的概率分布是否随时间的推移而变化将信源分为平稳信源和非平稳信源，根据随机变量间是否统计独立将信源分为有记忆信源和无记忆信源。
一个实际信源的统计特性往往是相当复杂的，要想找到精确的数学模型很困难。实际应用时常常用一些可以处理的数学模型来近似。随机序列，特别是离散平稳随机序列是我们研究的主要内容。
随机序列
离散单符号信源
输出单个离散取值的符号的信源称为离散单符号信源。它是最简单也是最基本的信源，是组成实际信源的基本单元。它用一个离散随机变量表示。信源所有可能输出的消息和消息对应的概率共同组成的二元序对 称为信源的概率空间：
信源输出的所有消息的自信息的统计平均值定义为信源的平均自信息量（信息熵），它表示离散单符号信源的平均不确定性：
离散多符号信源
定义：对于随机变量序列 ，在任意两个不同时刻 和 ( 和 为大于1的任意整数)信源发出消息的概率分布完全相同，即对于任意的 ， 和
具有相同的概率分布。也就是
即各维联合概率分布均与时间起点无关的信源称为离散平稳信源。
对于离散多符号信源, 我们引入熵率的概念，它表示信源输出的符号序列中，平均每个符号所携带的信息量。
定义 随机变量序列中，对前N个随机变量的联合熵求平均：
称为平均符号熵。如果当 时上式极限存在，则 称为熵率，或称为极限熵，记为
离散平稳无记忆信源
离散平稳无记忆信源输出的符号序列是平稳随机序列，并且符号之间是无关的，即是统计独立的。假定信源每次输出的是N长符号序列，则它的数学模型是N维离散随机变量序列： ，
并且每个随机变量之间统计独立。同时，由于是平稳信源，每个随机变量的统计特性都相同，我们还可以把一个输出N长符号序列的信源记为：
根据统计独立的多维随机变量的联合熵与信息熵之间的关系，可以推出：
离散平稳无记忆信源的熵率：
离散平稳有记忆信源
实际信源往往是有记忆信源。 对于相互间有依赖关系的N维随机变量的联合熵存在以下关系（熵函数的链规则） ：
定理 对于离散平稳信源，有以下几个结论：
（1）条件熵 随N的增加是递减的；
（2）N给定时平均符号熵大于等于条件熵，即
（3）平均符号熵 随N的增加是递减的；
（4）如果 ，则 存在，并且
有一类信源，信源在某时刻发出的符号仅与在此之前发出的有限个符号有关，而与更早些时候发出的符号无关，这称为马尔可夫性，这类信源称为马尔可夫信源。马尔可夫信源可以在N不很大时得到 。如果信源在某时刻发出的符号仅与在此之前发出的 m个符号有关，则称为m阶马尔可夫信源，它的熵率：
（马尔可夫性）
（平稳性）
通常记作
马尔可夫信源
马尔可夫信源是一类相对简单的有记
忆信源，信源在某一时刻发出某一符号
的概率除与该符号有关外，只与此前发
出的有限个符号有关。因此我们把前面
若干个符号看作一个状态，可以认为信
源在某一时刻发出某一符号的概率除了
与该符号有关外，只与该时刻信源所处
的状态有关，而与过去的状态无关。信
源发出一个符号后，信源所处的状态即
发生改变，这些状态的变化组成了马氏
链。
图 马尔可夫信源
对于一般的 阶马尔可夫信源，它的概率空间可以表示成：
令 ，从而得到马尔
可夫信源的状态空间：
状态空间由所有状态及状态间的状态转移概率组成。通过引入状态转移概率，可以将对马尔可夫信源的研究转化为对马尔可夫链的研究。
下面计算遍历的m阶马尔可夫信源的熵率。
当时间足够长后，遍历的马尔可夫信源可以视作平稳信源来处理，又因为m阶马尔可夫信源发出的符号只与最近的m个符号有关，所以极限熵 等于条件熵 。
对于齐次遍历的马尔可夫链，其状态 由 唯一确定，因此有
所以
信源的相关性和剩余度
根据定理可得
由此看出，由于信源输出符号间的依赖关系也就是信源的相关性使信源的实际熵减小。信源输出符号间统计约束关系越长，信源的实际熵越小。当信源输出符号间彼此不存在依赖关系且为等概率分布时，信源的实际熵等于最大熵 。
定义 一个信源的熵率（极限熵）与具有相同符号集的最大熵的比值称为熵的相对率：
信源剩余度为：
信源的剩余度来自两个方面，一是信源符号间的相关性，相关程度越大，符号间的依赖关系越长，信源的实际熵越小，另一方面是信源符号分布的不均匀性使信源的实际熵越小。
为了更经济有效的传送信息，需要尽量压缩信源的剩余度，压缩剩余度的方法就是尽量减小符号间的相关性，并且尽可能的使信源符号等概率分布。
从提高信息传输效率的观点出发，人们总是希望尽量去掉剩余度。但是从提高抗干扰能力角度来看，却希望增加或保留信源的剩余度，因为剩余度大的消息抗干扰能力强。
信源编码是减少或消除信源的剩余度以提高信息的传输效率，而信道编码则通过增加冗余度来提高信息传输的抗干扰能力。
* 连续信源
连续信源的微分熵
连续随机变量的取值是连续的，一般用概率密度函数来描述其统计特征。
单变量连续信源的数学模型为 ，并满足 ，
是实数域，表示 的取值范围。
对于取值范围有限的连续信源还可以表示成： ，并满足 ，（a,b）是 的取值范围。
通过对连续变量的取值进行量化分层，可以将连续随机变量用离散随机变量来逼近。量化间隔越小，离散随机变量与连续随机变量越接近。当量化间隔趋于0时，离散随机变量就变成了连续随机变量。通过这种方式，我们来推导连续随机变量的熵。
定义连续信源的微分熵为：
微分熵又称为差熵。虽然已不能代表连续信源的平均不确定性，也不能代表连续信源输出的信息量，但是它具有和离散熵相同的形式，也满足离散熵的主要特性，比如可加性，但是不具有非负性。
同样，我们可以定义两个连续随机变量的联合熵：
以及条件熵
连续信源的最大熵
离散信源当信源符号为等概分布时有最大熵。连续信源微分熵也有极大值，但是与约束条件有关，当约束条件不同时，信源的最大熵不同。我们一般关心的是下面两种约束下的最大熵。
定理 在输出幅度受限的情况，服从均匀分布的随机变量X具有最大输出熵。
定理 对于平均功率受限的连续随机变量，当服从高斯分布时具有最大熵。
（对于均值为m ，方差为 的连续随机变量，平均功率p=直流功率+交流功率= ）
连续信源的熵功率
均值为零，平均功率限定为p的连续信源当服从高斯分布时达到最大熵：
也就是说高斯信源的熵值与p有确定的对应关系：
现在假定限定的平均功率为p，某连续信源的熵为h(X)，则与它具有相同熵的高斯信源的平均功率 定义为熵功率即
所以， ，当该连续信源为高斯信源时等号成立。
的大小可以表示连续信源剩余的大小。如果熵功率等于信源平均功率，表示信源没有剩余；熵功率和信源的平均功率相差越大，说明信源的剩余越大。所以信源平均功率和熵功率之差 称为连续信源的剩余度。
第四章 信道及其信道容量
信道的分类
离散单符号信道及其信道容量
离散多符号信道及其信道容量
组合信道及其信道容量
* 连续信道及其信道容量
* 波形信道及其信道容量
信道是指信息传输的通道，包括空间传输和时间传输。我们在实际通信中所利用的各种物理通道是空间传输信道的最典型的例子，时间传输是指将信息保存，在以后读取，如磁带、光盘等在时间上将信息进行传输的信道。有时我们把为了某种目的而使信息不得不经过的通道也看作信道，这里最关键的是信道有一个输入以及一个与输入有关的输出。至于信道本身的物理结构可能是千差万别的，信息论研究的信道其输入点和输出点在一个实际物理通道中所处位置的选择完全取决于研究的目的。关于信道的主要问题有：
1.信道的建模（信道的统计特性的描述）
2.信道容量的计算
3. 在有噪信道中能不能实现可靠传输？怎样实现可靠传输？
信道的分类
信息论不研究信号在信道中传输的物理过程，它假定信道的传输特性是已知的，这样信道就可以用图所示的抽象的数学模型来描述。在信息论中，信道通常表示成： ，即信道输入随机变量X、输出随机变量Y以及在输入已知的情况下，输出的条件概率分布 。
根据实际应用的需要，信道有几种
分类方法：
(1)按其输入/输出信号在幅度和时间
上的取值是离散或连续来划分
如表所示：
图 信道模型
表 按其输入/输出信号在幅度和时间上的取值是离散或连续来划分
（2）按其输入/输出信号之间关系的记忆特性分为有记忆信道和
无记忆信道。
（3）按输入/输出信号之间的关系是否确定关系分为有噪声信道
和无噪声信道。
（理论和实用价值均很小）
连续
离散
模拟信道（波形信道）
连续
连续
连续信道
离散
连续
离散信道（数字信道）
离散
离散
信道名称
时间
幅度
（4）另外，根据信道输入和输出的个数可分为
① 两端信道（单用户信道）：只有一个输入端和一个输出端的单
向通信的信道。
② 多端信道（多用户信道）：双向通信或三个或更多个用户之间
相互通信的情况。
本课程主要研究两端信道的情况。
（5）根据信道的统计特性是否随时间变化分为：
①恒参信道（平稳信道）：信道的统计特性不随时间变化。卫星通
信信道在某种意义下可以近似为恒参信道。
②随参信道（非平稳信道）：信道的统计特性随时间变化。如短波
通信中，其信道可看成随参信道。
本课程主要研究恒参信道的情况。
离散单符号信道及其信道容量
离散单符号信道的数学模型
信道的输入、输出都取值于离散符号集，且都用一个随机变量来表示的信道就是离散单符号信道。
设离散单符号信道的输入随机变量为 ，输出随机变量为 ，由于信道中存在干扰，因此输入符号在传输中将会产生错误，这种信道干扰对传输的影响可用传递概率 来描述：
信道传递概率实际上是一个传递概率矩阵，称为信道矩阵，记为：
为了表述简便，常常写成
下面推导一般离散单符号信道的一些概率关系：
（1）输入输出随机变量的联合概率分布为
则有
其中 是信道传递概率，即输入为 ，通过信道传输输出
的概率，通常称为前向概率。它是由于信道噪声引起的，所
以通常用它描述信道噪声的特性。而 是已知信道输出符号
，输入符号为 的概率，称为后向概率。有时把 称为输入
符号的先验概率。而对应的把 称为输入符号的后验概率。
（2）由全概率公式，可从先验概率和信道传递概率求输出符号的
概率：
写成向量的形式：
或记成
（3）根据贝叶斯公式，可由先验概率和信道的传递概率求后向
概率：
信道容量的概念
平均互信息 是接收到输出符号集 后所获得的关于输入符号集 的信息量。信源的不确定性为 ，由于干扰的存在，接收端收到 后对信源仍然存在的不确定性为 ，又称为信道疑义度。信宿所消除的关于信源的不确定性，也就是获得的关于信源的信息为 ，它是平均意义上每传送一个符号流经信道的信息量，从这个意义上来说，平均互信息又称为信道的信息传输率，通常用 表示。即
有时我们所关心的是信道在单位时间内平均传输的信息量。如果平均传输一个符号为t秒，则信道平均每秒钟传输的信息量为
一般称为信息传输速率。
比特/符号
比特/秒
对于固定的信道，总存在一种信源（某种输入概率分布），使信道平均传输一个符号接收端获得的信息量最大，也就是说对于每个固定信道都有一个最大的信息传输率，这个最大的信息传输率即为信道容量，而相应的输入概率分布称为最佳输入分布。
定义 信道容量为平均互信息对于输入概率分布的最大值：
单位依所用的对数底不同可以是比特/符号、奈特/符号等。
若平均传输一个符号需要t秒钟，则信道在单位时间内平均传输的最大信息量
信道容量是信道传送信息的最大能力的度量，信道实际传送的信息量必然不大于信道容量。
图 表示不同的二元对称信
道，其传递概率p不同，信道
容量也不同。
当p=1/2时，是一种最坏的信
道，这时C=0，即该信道不能
传递任何信息，信息全部损失
在信道中了。而当p=0 或p=1
时，C=1，这是最好的情况，
信道能够无失真的传送信源信
息。
图 BSC的信道容量
几种特殊信道的信道容量
1.具有扩展性能的无损信道
无损信道是一个输入对应多个输出。
如图所示，信道矩阵为
无损信道信道矩阵中每一列只有一个非
零元素，接收到信道输出符号后对输入
符号将不存在不确定性。
图 无损信道
2.具有归并性能的无噪信道
无噪信道是一个输出对应多个输入。
如图所示，信道矩阵为
无噪信道每一行只有一个非零元素1，
信道矩阵元素非零即1。已知信道输
入符号，必能确定输出符号。
图 无噪信道
3.具有一一对应关系的无噪无损信道
无噪无损信道输入、输出之间有确定的一一对应关系，即 。
信道传递概率为
如图所示，信道矩阵为
无噪无损信道每一行、每一列只有一个
“1”，已知 X后对Y不存在不确定性，收
到 Y后对X也不存在不确定性。
图 无噪无损信道
离散对称信道的信道容量
离散信道中有一类特殊的信道，其特点是信道矩阵具有行对称性，利用这个对称性我们可以简化信道容量的计算。
定义 若信道矩阵中，每行都是第一行元素的不同排列，则称此类信道为行对称信道。
定义 若信道矩阵中，不仅每行都是第一行元素的不同排列，而且每列都是第一列元素的不同排列，这类信道称为对称信道。
定义 若信道矩阵中，每行都是第一行元素的不同排列，每列并不都是第一列元素的不同排列，但是可以按照信道矩阵的列将信道矩阵划分成若干对称的子矩阵，则称这类信道为准对称信道。
定义 若对称信道中输入符号和输出符号个数相同，且信道中总的错误概率为p，对称地平均分配给r-1个输出符号，r为输入输出符号的个数，即信道矩阵为
则称此信道为强对称信道或均匀信道。
二元对称信道就是r=2的均匀信道。一般信道的信道矩阵中各行之和为1，但各列之和不一定等于1，而均匀信道中各列之和亦等于1。
定理 对于对称信道，当输入分布为等概分布时，输出分布必能达到等概分布。
定理 若一个离散对称信道具有r个输入符号，s个输出符号，则当输入为等概分布时达到信道容量，且
其中 为信道矩阵中的任一行。
推论：均匀信道的信道容量为
当输入为等概分布时，输出为等概分布，信道达到信道容量。当r=2 时的均匀信道常称为二元对称信道，这时C = 1–H(p)。
对于一般的离散行对称信道，信道容量C仍然可以写成：
但是不一定存在一种输入分布能使输出达到等概分布，此时的信道容量 。
而离散对称信道的信道矩阵中每一列都是由同一组元素的不同排列组成，所以保证了当输入符号X为等概分布时，输出符号Y一定也是等概分布，输出随机变量熵可以达到 。
对于离散准对称信道，
但是可以证明当输入为等概分布时，可以达到信道容量
一般离散信道的信道容量
平均互信息 是输入概率分布p(x)的上凸函数，因此极大值必定存在。在信道固定的条件下，平均互信息是r个变量
的多元函数，且满足约束条件 ，故可用拉格朗日乘子法来求这个条件极值。即在
设辅助函数： ，当 时求得的
的值即为信道容量。
通过计算可得平均互信息的极大值 ，即
的条件下求 的极值。
这样得到的信道容量有一个参数 。在某些情况下可以消去 得到信道容量值。
1．当输入概率分布只有一个变量时，例如r=2，可以设输入概率分布为 和 ，因此输入概率分布只有一个变量，这时我们可以直接对 求导求出，从而得出 的极大值C。
2．对于信道矩阵为可逆矩阵的信道，我们可以采用解方程组的方法。
在一般信道的信道容量的推导中我们推出了下式：
移项得
当r=s，且信道矩阵是可逆矩阵时，该方程组有唯一解。这时就可以求出 ，然后根据 求出信道容量：
令
则
所以
由 和C就可以求得输出概率分布
（1）由 列方程组求出 ；
（2）由 求出C；
（3）由 求出 ；
（4）由 列方程组求 。
再根据
列方程组求
将计算步骤总结如下：
信道容量定理
从以上的讨论可知，求信道容量的问题实际上是在约束条件下求多元函数极值的问题，在通常情况下，计算量是非常大的。下面我们介绍一般离散信道的平均互信息 达到信道容量的充要条件，在某些情况下它可以帮助我们较快地找到极值点。
定理 设有一般离散信道，它有r个输入信号，s个输出信号。当且仅当存在常数C使输入分布 满足：
(1) 当
(2) 当
其中，
它表示信道输入 时，所给出关于输出Y的信息量。常数C即为所求的信道容量。
时， 达到最大值。
信道容量定理告诉我们，平均互信息 取到极大值也就是信道容量时，对于任意 ，只要它出现的概率大于0， 都相等。
信道容量定理只给出了达到信道容量时，最佳输入概率分布应满足的条件，并没有给出最佳输入概率分布值，也没有给出信道容量的数值。另外，定理本身也隐含着达到信道容量的最佳分布不一定是唯一的，只要输入概率分布满足充要条件式，就是信道的最佳输入分布。在一些特殊情况下，我们常常利用这一定理寻求输入分布和信道容量值。
离散多符号信道及其信道容量
实际离散信道的输入和输出常常是随机变量序列，用随机矢量来表示，称为离散多符号信道，如图所示。实际离散信道往往是有记忆信道，为了简化起见，我们主要研究离散无记忆信道。
定义 若在任意时刻信道的输出只与此时刻信道的输入有关，而与其他时刻的输入和输出无关，则称之为离散无记忆信道，简称为DMC(discrete memoryless channel)。
输入、输出随机序列的长度为N的离
散无记忆平稳信道通常称为离散无记
忆信道的N次扩展信道。
N次扩展信道的信道矩阵是一个
的矩阵。
图 离散多符号信道
离散无记忆信道的数学模型仍然表示为： ，注意这时输入、输出均为随机矢量。
根据信道无记忆的特性，其转移概率
定理 若信道的输入和输出分别是N长序列X和Y，且信道是无记忆的，则存在
这里Xk、Yk分别是序列X和Y中第k位随机变量。
对于离散无记忆N次扩展信道，当信源是平稳无记忆信源时，其平均互信息 等于单符号信道的平均互信息的N倍。
离散无记忆信道的N次扩展信道的信道容量为
因为现在输入随机序列在同一信道中传输，所以任何时刻通过离散无记忆信道传输的最大信息量都相同，即
所以
当信源也是无记忆信源并且每一时刻的输入分布各自达到最佳输入分布时，才能达到这个信道容量NC。
一般情况下，消息序列在离散无记忆N次扩展信道中传输时，其平均互信息量
4. 4 组合信道及其信道容量
前面我们分析了单符号离散信道和离散无记忆信道的扩展信道。实际应用中常常会遇到两个或更多个信道组合在一起使用的情况。例如，待发送的消息比较多时，可能要用两个或更多个信道并行发送，这种组合信道称为并联信道；有时消息会依次地通过几个信道串联发送，例如无线电中继信道，数据处理系统，这种组合信道称为级联信道。在研究较复杂信道时，为使问题简化，往往可以将它们分解成几个简单的信道的组合。这一节我们将讨论这两种组合信道的信道容量与其组成信道的信道容量之间的关系。
独立并联信道
一般独立并联信道如图所示。
可以把定理的结论推广到N个独
立并联信道中来：
只有当每个输入随机变量的概率分布
均达到各自信道的最佳输入分布时，
独立并联信道的信道容量才等于各信
道容量之和：
当N个独立并联信道的信道容量都相同时，
图 独立并联信道
级联信道
级联信道是信道最基本的组合形式，许多实际信道都可以看成是其组成信道的级联。图是由两个单符号信道组成的最简单的级联信道。
X→Y→Z 组成一个马尔可夫链。根据马尔可夫链的性质，级联信道的总的信道矩阵等于这两个串接信道的信道矩阵的乘积。求得级联信道的总的信道矩阵后，级联信道的信道容量就可以用求离散单符号信道的信道容量的方法计算。
图 级联信道
*4. 5 连续信道及其信道容量
连续随机变量的互信息
连续随机变量和之间的平均互信息定义为
连续随机变量的平均互信息具有和离散随机变量的平均互信息一样的性质：
1．对称性：
2．非负性：
当且仅当随机变量和统计独立时等号成立。
高斯加性信道的信道容量
高斯信道是最差的信道，实际应用中往往把噪声视为高斯噪声。
噪声源为高斯白噪声的加性信道。其信道容量
如果噪声N是均值为0、方差为 的高斯随机变量，即
表示噪声N的平均功率。这种信道称为高斯加性连续信道。
当输入随机变量X的概率密度是均值为0、方差为 的高斯随机变量，加性信道的噪声N是均值为0、方差为 的高斯随机变量时，输出随机变量Y也是一个高斯随机变量，其均值为0、方差为 ，此时输出随机变量的熵 达到最大，
而信道达到信道容量：
其中 称为信道的信噪比。
多维高斯加性信道的信道容量
当信道为多维高斯加性信道时，由于加性噪声信道必然是一个无记忆信道，所以
当且仅当输入随机矢量X中各分量统计独立，并且均为高斯变量时达到信道容量。
如果在每个抽样时刻信源和噪声是均值为0、方差分别为 和
的高斯随机变量，
因此
则
比特/n个样值
* 波形信道及其信道容量
波形信道通常根据抽样定理转化成多维连续信道进行处理。
一般来说，信道的带宽总是有限的。假设某信道的频带限于（0，B），则其输入、输出信号和噪声都是限频的随机过程，频带限于（0，B）。根据抽样定理，可把一个时间连续的信道变换成时间离散的随机序列信道来处理，即用每隔 秒时间的采样值来
表示输入、输出信号和噪声。我们把一次采样看成信道的一次传输，由于每秒传送2B个样值，所以单位时间的信道容量为
当噪声是双边功率谱密度为 的高斯白噪声时，
比特/秒
这就是著名的香农公式，它适用于加性高斯白噪声信道。从前面的讨论可知，只有当输入信号为功率受限的高斯白噪声信号时，才能达到该信道容量。
香农公式说明，当信道容量一定时，增大信道的带宽，可以降低对信噪功率比的要求；反之，当信道频带较窄时，
可以通过提高信噪功率比来补偿。
上式表明当频带很宽时，信道容量正比于信号功率与噪声谱密度之比。上式是加性高斯噪声信道信息传输率的极限值。
当 时，则
第五章 无失真信源编码
信源编码的相关概念
定长码及定长编码定理
变长码及变长编码定理
变长码的编码方法
实用的无失真信源码方法
信源编码的相关概念
编码器
信源输出的符号序列，需要变换成适合信道传输的符号序列，一般称为码序列，对信源输出的原始符号按照一定的数学规则进行的这种变换称为编码，完成编码功能的器件，称为编码器。接收端有一个译码器完成相反的功能。
信源编码器的输入是信源符号集 ，共有q个信源符号。同时存在另一个符号集 ，称为码符号集，共有r个码符号，码符号集中的元素称为码元或码符号，编码器的作用就是将信源符号集 中的符号 变换成由 个码符号组成的一一对应的码符号序列。编码器输出的码符号序列称为码字，并用 来表示，它与信源符号 之间是一一对应的关系，如图所示。
码字的集合C称为码，即 。信源符号 对应的码字 包含 个码符号， 称为码字长度，简称码长。
所以，信源编码就是把信源符号序列变换到码符号序列的一种映射。 若要实现无失真编码，那么这种映射必须是一一对应的、可逆的。 一般来说，人们总是希望把信源所有的信息毫无保留地传递到接收端，即实现无失真传递，所以首先要对信源实现无失真编码。
图 信源编码器
信源编码有以下3种主要方法：
(1) 匹配编码根据信源符号的概率不同，编码的码长不同：概率大的信源符号，所编的代码短；概率小的信源符号所编的代码长，这样使平均码长最短。将要讲述的香农编码、哈夫曼编码、费诺码都是概率匹配编码，都是无失真信源编码。
(2) 变换编码 先对信号进行变换，从一种信号空间变换为另一种信号空间，然后针对变换后的信号进行编码。
(3) 识别编码识别编码主要用于印刷或打字机等有标准形状的文字符号和数据的编码，比如中文文字和语音的识别。
后两种信源编码均为有失真的信源编码。
无失真信源编码主要针对离散信源，连续信源在量化编码的过程中必然会有量化失真，所以对连续信源只能近似地再现信源的消息。
码的分类
1. 分组码和非分组码
定义 将信源符号集中的每个信源符号 固定地映射成一个码字 ，这样的码称为分组码。
用分组码对信源符号进行编码时，为了使接收端能够迅速准确地将码译出，分组码必须具有一些直观属性。与分组码对应的是非分组码，又称为树码、树码编码器输出的码符号通常与编码器的所有信源符号都有关。
2. 奇异码与非奇异码
定义 若一种分组码中的所有码字都不相同，则称此分组码为非奇异码，否则称为奇异码。
3. 唯一可译码与非唯一可译码
定义 任意有限长的码元序列，如果只能唯一地分割成一个个码字，便称为唯一可译码。
唯一可译码的物理含义是指不仅要求不同的码字表示不同的信源符号，而且还要求对由信源符号构成的符号序列进行编码时，在接收端仍能正确译码而不发生混淆。唯一可译码首先是非奇异码，且任意有限长的码字序列不会雷同。
4. 即时码与非即时码
定义 无需考虑后续的码符号就可以从码符号序列中译出码字，这样的唯一可译码称为即时码。
下面讨论唯一可译码成为即时码的条件。
定义 设 为一码字，对于任意的 ，称码符号序列的前j个元素 为码字的前缀。
按照上述的前缀的定义，有下述结论：
定理 一个唯一可译码成为即时码
的充要条件是其中任何一个码字都不是
其他码字的前缀。
即时码可以用树图来构造．图是一个
二元即时码的树图．
图 二元即时码的树图
树是没有回路的图，所以它也是由节点和弧构成的．树中最顶部的节点称为根节点，没有子节点的节点称为叶子节点。
所有根节点的子节点称为一阶节点，所有一阶节点的子节点称为二阶节点，依此类推。 阶节点最多有 个。节点的阶次又称为节点的深度。
综上所述，可将信源编码作如下分类：
码
非分组码（树码）
分组码（块码）
奇异码
非奇异码
非唯一可译码
唯一可译码
即时码
非即时码
定长码及定长编码定理
若对一个有q个信源符号的信源S进行定长编码，那么信源S存在唯一可译定长码的条件是
()
其中，r是码符号集中的码元数，l是定长码的码长。
如果对信源S的N次扩展信源 进行定长编码，若要编得的定长码是唯一可译码，则必须满足
()
其中，q是信源S的符号个数， 是信源S的N次扩展信源 的符号个数，r是码符号集X的码符号数。
定长编码的信息传输效率是很低的。提高信息传输效率的方法有：
方法1 考虑符号之间的依赖关系，对信源S的扩展信源进行编码。方法2对于概率等于0或非常小的符号序列不予编码。
定理 离散无记忆信源的熵为H(S)，若对信源长为N的序列进行定长编码，码符号集X中有r个码符号，码长为l，则对于任意 ，只要满足
则当N足够大时，可实现几乎无失真编码，即译码错误概率δ任小；反之，如果
则不可能实现几乎无失真编码，即当N足够大时，译码错误概率为1。
定理是在离散平稳无记忆信源的条件下证明的，但它同样适合于平稳有记忆信源，只要将式中H(S)改为极限熵 即可，条件是有记忆信源的极限熵 和极限方差 存在。
定长信源编码定理给出了定长编码时每个信源符号最少所需的码符号的理论极限，该极限值由H(S)决定。
定义 设熵为H(S)的离散无记忆信源，若对信源的长为N的符号序列进行定长编码，码符号集中码符号个数为r，设码字长为l，
定义 比特/信源符号为编码速率，它表示平均每个信
源符号编码后能载荷的最大信息量。
这时，定理的条件可表述为R′≥H(S)+ε，即编码速率大于信源的熵才能实现几乎无失真编码。为了衡量编码效果，引进编码效率。
定义 定义 为编码效率。
由定理可得最佳编码效率为 ，所以
在已知方差和信源熵的条件下，信源符号序列长度N与最佳编码效率η和允许错误概率 的关系为：
当允许错误概率越小，编码效率又要高，那么信源符号序列长度N必须越长．在实际情况下，要实现几乎无失真的定长编码，N需要的长度将会大到难以实现。
变长码及变长编码定理
Kraft不等式和McMillan不等式
定理 设信源符号集为 ，码符号集为 ，对信源进行编码，得到的码为 ，码长分别为 。即时码存在的充要条件是
这称为Kraft不等式。
由Kraft不等式可知，给定r和q，只要允许码字长度可以足够长，则码长总可以满足Kraft不等式而得到即时码，Kraft不等式指出了即时码的码长必须满足的条件．
()
对于唯一可译码，该不等式又称为McMillan不等式。
定理 唯一可译码存在的充要条件是
r为码符号个数，为码字长度，q为信源符号个数。
定理指出了唯一可译码中r、q、 之间的关系，如果满足这个不等式的条件，则一定能够构成至少一种唯一可译码，否则，无法构成唯一可译码．它给出了唯一可译变长码的存在性。
另外，从定理和定理可以得到一个重要的结论，即任何一个唯一可译码均可用一个相同码长的即时码来代替，因为即时码很容易用树图法构造，因此要构造唯一可译码，只要构造即时码就可以了。
()
唯一可译码的判别准则
和于1957年提出下述算法用于判断码C的唯一可译性．此算法的原理如下所示：
其中 都是码字。可知，当且仅当某个有限长的码符号序列能译成两种不同的码字序列时，此码不是唯一可译码，此时 一定是 的前缀，而 的尾随后缀一定是另一码字 的前缀；而 的尾随后缀又是其他码字的前缀．最后，码符号序列的尾部一定是一个码字。
设C为码字集合，按以下步骤构造此码的尾随后缀集合F：
(1) 考查C中所有的码字，若 是 的前缀，则将相应的后缀作为一个尾随后缀码放入集合 中；
(2) 考查C和 两个集合，若 是 的前缀或 是 的前缀，则将相应的后缀作为尾随后缀码放入集合 中；
(3) 即为码C的尾随后缀集合；
(4) 若F中出现了C中的元素，则算法终止，返回假(C不是唯一可译码)；否则若F中没有出现新的元素，则返回真。
定理 一个码是唯一可译码的充要条件是的 并集中没有C中的码字。
无失真变长编码定理
定义 设有信源
编码后的码字分别为 ，各码字相应的码长分别为 因为是唯一可译码，信源符号 和码字 一一对应，则定义此码的平均码长为
其中， 表示每个信源符号平均需用的码元数。
当信源给定时，信源熵H(S)就确定了，而编码后每个信源符号平均用 个码元来变换，故平均每个码元载荷的信息量即编码后信源的信息传输率。
码符号/信源符号
()
定义 编码后信源的信息传输率为
如果传输一个码符号平均需要t秒时间，则编码后信源每秒钟提供的信息量为
可以看出， 越小，则 越大，信息传输率就越高，因此我们感兴趣的码是使平均码长 最短的码。
定义 对于给定的信源和码符号集，若有一个唯一可译码，其平均码长 小于所有其他唯一可译码，则称这种码为紧致码或最佳码。
无失真信源编码的核心问题就是寻找紧致码．
比特/码符号
()
()
下面的定理给出了紧致码的平均码长可能达到的理论极限．
定理 若一个离散无记忆信源S，熵为H(S)，用拥有r个码符号的码符号集 对S进行无失真编码，则总可以找到一种唯一可译码，其平均码长满足
若熵以r进制为单位，则式()可写成
另外还可以看到平均码长的极限值与无失真定长信源编码定理中的极限值是一致的。
()
()
香农第一编码定理
定理 设离散无记忆信源S的信源熵H(S)，它的N次扩展信源 ，其熵 。并用码符号 对信源 进行编码，总可以找到一种唯一可译码，使信源S中每个信源符号所需的平均码长满足
或者写成
定理可以看作定理在N=1时的特殊情况。
定理是香农信息论的主要定理之一。
()
()
定义 编码后信道的信息传输率为
这里， ，所以
无失真信源编码的实质就是对离散信源进行适当的变换，使变换后新的码符号信源(信道的输入)尽可能为等概率分布，使新信源的每个码符号平均所含的信息量达到最大，从而使信道的信息传输率R达到信道容量，实现信源与信道理想的统计匹配。这就是香农第一定理的物理意义。
比特/码符号
()
比特/信源符号
码符号/信源符号
为了衡量各种编码是否已达到极限情况，我们定义变长码的编码效率。
定义 设对信源S进行无失真编码所得到的平均码长为 ，则 ，定义
为编码效率，
对同一信源来说，码的平均码长 越短，越接近极限 ，信道的信息传输率越高，越接近无噪无损信道的信道容量，这时η也越接近于1，所以用码的效率η来衡量各种编码的优劣。
()
另外，为了衡量各种编码与最佳码的差距，引入码的剩余度的概念。
定义 定义
为码的剩余度。
在二元无噪无损信道中r=2， ，所以在二元无噪无损信道中信息传输率
注意它们数值相同，单位不同．η是个无单位的比值，而R的单位是比特/码符号。
()
变长码的编码方法
本章介绍的变长码的常见编码方法，如香农编码、香农-费诺-埃利斯编码、霍夫曼编码、费诺编码均为匹配编码，也称统计编码，都是通过使用较短的码字来给出现概率较高的信源符号编码。而出现概率较小的信源符号用较长的码字来编码，从而使平均码长最短，达到最佳编码的目的。下面介绍这几种方法：
香农编码
香农码的方法是选择每个码字长度 满足
按照香农编码方法构造的码，其平均码长 不超过上界，即
其具体方法如下：
(1) 将信源发出的q个消息符号按其概率的递减次序排列
(2) 计算出各个信源符号的累加概率
(3) 按下式计算第i个消息的二元代码组的码长
(4) 将累加概率 (十进制小数)变换成二进制小数。根据码长 取小数点后 个二进制符号作为第i个消息的码字。
香农-费诺-埃利斯编码
将香农编码中的累加概率换成修正累加概率即可得到相应的香农-费诺-埃利斯编码：
(1) 计算出各个信源符号的修正累加概率
(2) 按下式计算第i个消息的二元代码组的码长
(3) 将累加概率 (十进制小数)变换成二进制小数．根据码长 取小数点后 个二进制符号作为第i个消息的码字．
霍夫曼编码
这是霍夫曼于1952年提出的一种构造紧致码的方法．具体方法如下：
(1) q将个信源符号按概率大小递减排列
(2) 用“0，1”码符号分别代表概率最小的两个信源符号，并将这两个概率最小的信源符号合并成一个，从而得到只包含q-1个符号的新信源 ，称为缩减信源 ；
(3) 把缩减信源 的符号仍按概率大小递减次序排列，再将其最后两个概率最小的信源符号分别用“0”和“1”码符号表示，并且合并成一个符号，这样又形成了q-2个信源符号的缩减信源 ；
(4) 依次继续下去，直至信源最后只剩下两个信源符号为止，将这最后两个信源符号分别用二元码符号“0”和“1”表示；
(5) 然后从最后一级缩减信源开始，进行回溯，就得到各信源符号所对应的码符号序列，即相应的码字。
霍夫曼编码方法得到的码并非是唯一的。造成非唯一的原因有两个：
(1) 每次对信源缩减时，赋予最后两个概率最小的信源符号的码符号“0”和“1”是可以互换的，所以可得到不同的霍夫曼码；
(2) 对信源进行缩减时，如果两个概率最小的信源符号合并后的概率与其他信源符号的概率相同，则在进行概率排序时的次序可以是任意的，因此会得到不同的霍夫曼码。
霍夫曼码是用概率匹配的方法进行信源编码．它有两个明显特点：
(1) 霍夫曼码的编码方法保证了概率大的信源符号对应的码长小，概率小的信源符号对应的码长大，充分利用了短码；
(2) 每次缩减信源的最长两个码字有相同的码长，并且仅仅只有最后一位码符号不同。
定理 霍夫曼码是紧致码。
r元霍夫曼编码
二进制霍夫曼码的编码方法很容易推广到r进制的情况，只是编码过程中构成缩减信源时，每次都是将r个概率最小的信源符号合并，并分别用码符号0,1,…,(r-1)表示。
为了充分利用短码，使霍夫曼码的平均码长最短，必须使最后一个缩减信源恰好有r个信源符号．因此对于r元霍夫曼编码，信源S符号个数q必须满足q=(r-1)θ+r。θ表示信源缩减次数．如果不满足上式，则可以在最后增补一些概率为0的信源符号，因此上式又可以写成q+i=(r-1)θ+r。i为增加的信源符号数，并且是满足上式的最小正整数或0。当r=2时的二元码．信源S的符号个数q满足q=θ+2。
由于霍夫曼码是紧致码，所以编码后单个信源符号平均码长随N的增加很快接近于极限值——信源熵。
费诺编码
费诺码编码过程如下：
(1) 将信源符号 以概率递减次序排列，即
(2) 将依次排列的信源符号以概率分为两组，使两个组的概率和基本相等，并对各组赋予二元码符号“0”和“1”；
(3) 将每一大组的信源符号进一步再分成两组，使划分后的两个组的概率和近于相等，又分别赋予各组二元码符号“0”和“1”；
(4) 如此重复，直至每组只剩下一个信源符号为止；
(5) 信源符号所对应的码符号序列即为费诺码．
以上讨论了霍夫曼码和其他一些编码方法，并且证明了霍夫曼码是最佳码，当N不很大时，它能使无失真编码的效率接近于1，但是在实际使用时设备较复杂。
首先，每个信源符号所对应的码
长不同，一般情况下，信源符号
以匀速输出，信道也是匀速传输
的。
其次，差错扩散的问题．变长码
的一个码元的差错可能造成译码
错误，并且还会造成同步错误，
结果后面一系列码字也会译错。
最后，霍夫曼码的编译码需要用
查表的方法来进行。
香农码
霍夫曼
费诺码
信息传输率R
平均码长
编码
表 三种编码方法的比较
实用的无失真信源编码方法
游程编码
游程编码主要用于黑白二值文件、传真的数据压缩。 由于传真文件中连“0”和连“1”较多．这些连“0”或连“1”的字符串称为游程．对游程长度进行霍夫曼编码或其他的编码处理就可以达到压缩数据的目的。
图是一幅10×50黑白二值图像。
图 二值图像
MH编码是一种实用的游程编码算法，应用于黑、白传真数据的压缩编码，根据不同的黑、白游程长度有两张结尾码表和两张组合码表．其基本的编码规范为
(1) 游程长度在0～63时，直接查表用相应的结尾码作为码字；
(2) 游程长度在64～1728范围内时，用组合码加上结尾码作为相应的码字；
(3) 每行的第一个游程规定为白游程(长度可以为零)，每行用一个结束码(EOL) 终止；
(4) 在传输时，每页数据之前加一个结束码，每页尾部连续实用6个结束码。
算术编码
算术式编码是一种非分组码，无需计算出所有N长信源序列的概率分布及码表，可以直接对输入的信源符号序列编码输出。这种方法是由香农-费诺-埃利斯编码直接扩展得到的。
算术式编码算法的中心思想是高效地计算n长信源符号序列x的分布概率p(x)和累积概率F(x)，然后用区间[F(x)-p(x), F(x)]中的一个值来作为x的码字。
假定信源是二进制的，并且分组的长度n已知。
定义 两个n长信源符号序列x和y，定义x大于y，当第一个使得 的i有 。
LZW码
LZW码也称基于字典的编码方法，它是定长码。
(1) 基于字典编码的基本原理
计算机文件是以字节为单位组成的。LZW码是一种自适应变码，它的字典是直接由被压缩文件在编码过程中生成的。
(2) 字典的构成
字典的容量为4096(0～4095),序号用12bit表示．最后一个单词(第4095个单词)为空。
(3) 算法
①字典初始化
②动态数据初始化：初始化新单词存放位置指针P，将它指向字典的第一个空位置。
③如果文件再没有字符了，输出当前单词W的序号。编码结束。如果文件中还有字符，把当前单词W作为前缀，再从被压缩文件中读入一个字符CH，把CH作为尾字符，得到一个单词 。
④如果字典中已有 ，则将 看作当前单词W，返回③。如果字典中没有 (发现一个新单词)，先将原单词W的序号输出，再加新单词 ，增加到字典中，然后把刚刚读入的字符CH作为当前单词W，返回③。
(4) 适用文件类型
不适合小文件的压缩(因为压缩编码初期，由于字典中的单词很少，字典对压缩效果的贡献也很少，主要是进行字典的扩充)，也不适合太大的文件(因字典容量有限，文件太大时字典满了，效率将受到制约)．适合内容有明显单词结构的文件(如文本文件、程序文件)。
(5) 译码
①字典初始化
②动态数据初始化
③如果压缩中已经没有码字，解码结束。否则继续读入一个码字。
④如果读入的码字是无效码字FFF，则解码结束，否则下一步。
⑤如果在字典中已经有该码字对应的单词，则采用递归算法，输出该单词的内容。并将单词的第一个有效字符作为尾字符，将已经记忆的前一个码字作为前缀，组成一个新单词，写入字典中，然后将当前码字记忆下来，返回③；否则，首先在字典中生成新的单词，然后再输出这个单词，将新单词的码字记忆下来，返回③。这时的新单词一定是首尾相同的单词。
(6) LZW编码算法的优化
第六章 有噪信道编码
信道编码的相关概念
有噪信道编码定理
纠错编码
* 几种重要的纠错码
信道编码的相关概念
信道编码又称为数据传输码或差错控制码，虽然和信源编码一样都是一种编码，但信源编码的作用是压缩冗余度以得到信息的有效表示，提高传输时的信息传输率。而信道编码的作用是提高信息传输时的抗干扰能力以增加信息传输的可靠性。在研究信道编码时，信源编码器和信源译码器分别归于信源和信宿。等效通信系统模型如图所示。下面研究编码信道中的信道编码和译码。
图 等效通信系统模型
信源符号 一般是已经经过信源编码的M种信源码字．信道编码的编码对象就是这M种信源码字。这M种信源码字通常是由二元符号“0,1”构成的码字序列，也叫信息序列，而且符号“0”和“1”是独立等概的。所谓信道编码，就是按一定的规则给信息序列增加一些多余的码元，使不具有规律性的信息序列变为具有某种规律性的信道码字序列X，也就是说码字序列X的码元之间是相关的。在接收端，信道译码器利用这种相关性(也就是已知的编码规则)来译码，检验接收到的码字序列Y中是否有错，并且纠正其中的差错。根据相关性来检测和纠正传输过程中产生的差错就是信道编码的基本思想。
在有噪信道中，传输信息发生错误的错误概率与信道的统计特性、编码方法和译码规则都有关系。下面分别讨论这些因素，看看能不能对这些因素加以控制以提高通信的可靠性。
错误概率和译码规则
我们已经知道，错误概率与信道的统计特性有关。信道的统计特性可由信道的传递矩阵来表示，由信道矩阵可以求出错误概率。例如在图的二元对称信道中，单个符号的错误传递概率是p，单个符号的正确传递概率为 ，
因此错误概率与信道的统计特征
有关。但是通信的过程并不是信
息传输到信道输出端就结束了，
还要经过译码过程才能到达信宿，
译码过程和译码规则对系统的错
误概率影响很大。
图 二元对称信道
定义 设信道的输入符号集 ，输出符号集 ，若对每一个输出符号 ，都有一个确定的函数 ，使 对应于唯一的一个输入符号 ，则称这样的函数为译码规则，记为
对于有r个输入，s个输出的信道而言，输出 可以对应r个输入中的任何一个，所以译码规则共有 种。
1.错误概率
在确定译码规则 后，若信道输出端接收到符号 ，则一定译成 。如果发送端发送的确实就是 ，就是正确译码；反之，若发送端发送的不是 就认为是错误译码。
()
于是收到符号 条件下，译码的条件正确概率为：
而条件错误概率：
译码后的平均错误概率是条件错误概率 对Y空间取平均值，即
它表示经过译码后平均接收到一个符号所产生的错误大小。
2.译码规则
定义 选择译码函数 ，使之满足条件
则称为最大后验概率译码规则，又称为最小错误概率准则、最优译码、 最佳译码、 理想观测者规则。
它对于每一个输出符号 均译成具有最大后验概率的那个输入符号 ，则信道译码平均错误概率最小。
定义 选择译码函数 ，使之满足条件
称为极大似然译码规则。
当输入符号等概时，这两个译码规是等价的，根据极大似然译码准则可以直接从信道矩阵的传递概率中去选定译码函数。
3.平均错误概率
共(r-1)s项求和。上式表示对联合概率矩阵 中除
以外的所有元素求和，而平均正确概率为
如果输入为等概分布，即 ，则
所以在输入为等概分布时，极大似然译码规则可使信道平均错误概率最小。
()
译码时发生错误是由信道中的噪声引起的，而信道噪声的影响使在接收端收到输出符号Y后对发送端发送的符号仍然存在不确定性，因此平均错误概率与信道疑义度存在着一定的关系，这个关系用费诺不等式表示。
定理 平均错误概率 与信道疑义度 满足以下关系：
费诺不等式表明，接收到Y后关于X的平均不确定性可以分为两部分：第一部分 是指接收到Y后是否产生错误的不确定性；第二部分 是当错误 发生后，判断是哪个输入符号造成错误的最大不确定性，是(r-1)个符号不确定性的最大值与的乘积。
若以 为纵坐标， 为横坐标，函数
随 变化的曲线如图所示。
图 费诺不等式曲线图
错误概率与编码方法
选择最佳译码规则只能使错误概率 有限地减小，无法使 任意地小，要想进一步减小错误概率 ，还必须选择恰当的编码方法。
1. 消息符号个数
因此看到这样一个现象：在一个二元信道的n次无记忆扩展信道中，输入端有 个符号序列可以作为消息。如果选出其中的M个作为消息传递，则：M大一些， 也大些，R也大；M取小一些， 就降低，而R也要降低。
2. (5,2)线性码
信道输入端所选的消息数不变，任取M=4，增加码字的长度，取n=5。这时信道为二元对称信道的五次扩展信道，这个信道输入端有 个不同的二元序列。我们选取其中4个作为发送消息。这时信息传输率为
设输入序列 ，若 中各分量满足
由上述编码方法得到一种(5,2)线性码。选用此码，接收端译码能纠正码字中所有发生一位码元的错误，也能纠正其中两个两位码元的错误。
3. 汉明距离
定义 长度为n的两个符号序列(码字) 与 之间的距离是指序列 和 对应位置上码元不同的位置的个数，通常又称为汉明距离。
汉明距离满足以下性质：
(1) 非负性： ，当且仅当 时等号成立；
(2) 对称性： ；
(3) 三角不等式：
定义 码C中，任意两个码字的汉明距离的最小值称为该码C的最小距离。
显然， 越大， 越小。码的最小距离 越大，受干扰后，越不容易把一个码字错成另一个码字，因而错误概率小； 越小，受干扰后很容易把一个码字变成另一个码字，因而错误概率大。这就说明：在编码选择码字时，要使码字之间的距离尽可能地大。
极大似然译码准则为：
选择译码函数 使
设码字 ，在传输过程中输入码字 中有 个位置发生错误，接收端接收序列为 ，即 ，没有发生错误的位置有 个。
有噪信道编码定理
有噪信道编码定理
定理 设有一个离散无记忆平稳信道，其信道容量为C。当信息传输率R＜C，只要码长n足够长，则总存在一种编码，可以使平均译码错误概率任意小。
这个定理称为有噪信道编码定理，又称为香农第二定理。
通过一个有噪信道可以实现几乎无失真传输，这与人们的直观想象似乎是大相径庭的，而定理的证明也是非常巧妙的。香农巧妙地先，他不去构造理想的好码，而是用随机编码的方法得到所有可能生成的码的集合，然后在码集合中随机选择一个码作为输入码序列，最后计算这样随机选择的一个码在码集合上的平均性能。在译码时，利用了联合典型序列的概念，即将接收序列译成与其联合典型的码字．这种译码方法不是最优译码，但便于理论分析。
定义 设 是长为n的随机序列对，且
则在这些随机序列对中同时满足以下条件的序列对称为联合ε典型序列。
即 是X的ε典型序列；
(1)
(2)
即 是X的ε典型序列；
(3)
ε是任意小的正数。
联合ε典型序列的全体构成的集合称为联合ε典型序列集，记作
按照以上定义可以得到联合渐进等分割性。
对于任意小的正数ε≥0,δ≥0,当n足够大时，有
(1) 典型列集和联合典型列集的概率满足：
(2) 典型列和联合典型列出现的概率满足：
(3) 典型列集和联合典型列集中元素的个数满足：
典型序列 是输入端高概率出现的序列，典型序列 是输出端高概率出现的序列，而联合典型序列对 则是信道输入和输出之间关联密切且经常出现的序列对。也就是说，当某一输入典型序列 发送时，必定高概率地以和它构成联合ε典型序列对的接收序列 接收。
有噪信道编码逆定理
定理 设有一个离散无记忆平稳信道，其信道容量为C。对于任意q＞0，若选用码字总数 ，则无论n取多大，也找不到一种编码，使译码错误概率 任意小。
以上定理只是在离散无记忆信道的情况下证明的，但是对连续信道和有记忆信道同样成立。
错误概率的上界
离散无记忆信道中 趋于零的速度与n成指数关系，即当R<C时，平均错误概率 ，式中， 称为随机编码指数，又称为可靠性函数或加拉格(Gallaqer)函数。一般可靠性函数与信息传输率R的关系曲线如图所示，
图 曲线图
香农第二定理也只是一个存在定理，它说明错误概率趋于零的好码是存在的，但是没有说明如何构造这个好码。尽管如此，香农第二定理仍然具有重要的理论意义和实践指导作用，它可以指导各种通信系统的设计，有助于评价各种通信系统及编码效率。
从香农第一定理和香农第二定理可以看出，要做到有效和可靠地传输信息，可以将编码分成信源编码和信道编码两部分。这种分两部分编码的方法在实际通信系统中有着重要的意义。在实际数字通信系统中，信道常常是共用的数字信道(二元信道)，输入端只是二元序列，所以信道编码只需针对信道特性进行，纠正信道中带来的错误，这样，可以大大降低通信系统设计的复杂度。可以证明，这种分两步编码处理的方法与一步编码处理方法是一样有的。
纠错编码
信道编码的目的是提高信号传输的可靠性，广义的信道编码还包括为特定信道设计的传输信号，如NRZ(不归零)码、HDB3码、伪随机序列码都属于信道编码。纠错编码是提高传输可靠性的最主要措施之一。
纠错码分类
由于信道中干扰和噪声的存在，使得经信道传输后的接收码字与原来的发送码字存在着差异，也就是差错。一般信道中噪声干扰越大，码字产生错误的概率也越大。
信道中的干扰和噪声一般分为两种形式：一是随机噪声，它主要来源于设备的热噪声和散弹噪声以及传播媒介的热噪声，是通信系统中的主要噪声；二是脉冲干扰和信道衰落，它的特点是突发出现，主要来源于雷电、通电开关、负荷突变或设备故障等。
根据信道中干扰和噪声的形式，可将信道分为3类：随机信道、突发信道和混合信道。
随机噪声产生的错误是独立随机出现的，称为随机错误。它的特点是各码元是否发生错误是随机的，且相互独立，因而不会出现成片的错误．只产生随机错误的信道称为随机信道。
脉冲干扰和信道衰落产生的错误是成串出现的，错误间具有相关性，这类错误称为突发错误。产生突发错误的信道称为突发信道。
有些实际信道既有随机错误又有突发错误，称为混合信道。
根据不同的信道类型设计的信道编码分为纠随机错误码、纠突发错误码和纠混合错误码。在通信系统中，纠检错的工作方式有反馈重传纠错、前向纠错和混合纠错等。
1. 反馈重传纠错
图即反馈重传纠错图示
发送端发出的是能够发现错误的检错码，接收端对接收到的码字进行译码，发现有错时，通过反馈系统向发送端请求重传已发送的全部或部分码字，直到接收端认为没有错误为止，我国的电报系统就是一种反馈重传纠错系统。
图 反馈重传纠错
2. 前向纠错
图即前向纠错图示．
前向纠错也称为自动纠错。发送端发出的是具有纠错能力的纠错码，接收端根据编码规则进行解码。当误码个数在码的纠错能力范围之内时，译码器可以自动纠正错误。
图 前向纠错
3. 混合纠错
对发送端进行适当的编码，当错误不严重时，在码的纠错能力之内，采用自动纠错，当产生的差错超出码的纠错能力时，则通过反馈系统向发送端要求重发，这种同时具有反馈重传纠错和自动纠错工作方式的纠错称为混合纠错。
检错码和纠错码在不加区别时统称为纠错码。
纠错码的分类如下：
(1)根据信息码元与校验码元之间是否存在线性关系可分为线性码和非线性码。
(2) 根据不同的分组及映射方式，纠错码可以分成分组码和树码。
纠错码按结构分类如下：
纠错码
分组码
树码
线性分组码
非线性分组码
循环码
非循环码
线性—卷积码
非线性码
目前的通信系统大多采用二进制的数字系统，所以以下提到的纠错码都是指二元码。
纠错码的基本概念
对信道编码的一般要求是：
(1) 纠错检错能力强，可发现和纠正多个错误；
(2) 信息传输率高，信息传输率也称为码率： ，M为信息序列数，所以码长n应尽可能短；
(3) 编码规律简单，实现设备简单且费用合理；
(4) 与信道的差错统计特性相匹配。
定义将信源编码器的输出序列进行分组，分组长度为k，则可以有 个不同的分组信息序列．每个分组信息序列用一个n长的码字来表示(n>k)， ，这样的 个码字的集合称为二元分组码。
定义每个码字 中k位称为信息位，其余n-k位为校验位或监督位。信息序列的个数为 ，而长为n的二元码一共有 个，选出其中的M个作为码字，称为许用序列，而其他序列为禁用序列。
用η=k/n表示码字中信息位所占的比重，称编码效率，它表明了信道的利用率。η越大，编码效率越高，它是衡量码性能的一个重要参数。
如果n长码字的每一位与原始信息序列 的k个信息位之间的函数关系 是线性关系，则称该分组码为线性分组码，否则称为非线性分组码。
定义 若(n,k)分组码字中k个信息位与原始信息序列的k个信息位相同，且位于n长码字的前（或后）k位，而校验位位于其后（或前）n-k位，则该分组码为系统码，否则为非系统码。
码的最小汉明距离是衡量码的纠检错能力的重要参数，码的最小距离越大，其纠检错能力越强。
定义 对于某一码字，其非零元素的个数称为该码字的汉明重量。
对于二元码，其码字的重量是码字中1的个数。
若码字为 ，则其重量可以表示为
* 几种重要的纠错码
线性分组码
线性分组码是最有实用价值的一类码。比如汉明码、Golay码、RS码、BCH码等都属于线性分组码。
线性分组码的编码方式是将信源输出序列分组，每组是长为k的信息序列，然后按照一定的编码规则插入n-k位的校验位，校验位是信息位的线性组合，组成n长的码元序列。
1. 校验矩阵与生成矩阵
定义对于k位信息位n长码元序列的线性方程组，可有下面关系式存在： ()
其中，C为n维行向量，m为k维行向量，G为k×n矩阵，称为线性分组码C的生成矩阵。
式()表明，码字C为信息序列m和生成矩阵G的行向量的线性组合，和为“模2加”。
一般地，构造一个(n,k)线性分组码，只需找出一个秩为n-k的n-k行、n列矩阵H，则可由齐次线性方程组 的解空间的全部向量作为许用码字，得到一个(n,k)线性分组码。
生成矩阵和校验矩阵有如下关系：
即线性分组码的生成矩阵和校验矩阵的行矢量彼此正交．以上结果表明，线性分组码既可以由生成矩阵确定，也可以由校验矩阵确定。
标准形式的校验矩阵和生成矩阵可以很方便地实现转换。
或
线性分组码的性质是：
(1) 码中任意两个码字之和仍为一码字；
(2) 任意码字是G的行向量 的线性组合；
(3) 零向量0=(0,0,…,0)是一个码字，称为零码字；
(4) 线性分组码的最小距离等于非零码字的最小重量。
线性分组码最重要的性质是其线性特性以及在此基础上的对称性。所谓线性特性是指线性码中任意两个码字的和或差仍为一码字，对称性是指在一个码的所有码字上减去一个特定的码字，结果仍是同一码的全部码字。这样在求码字间的距离分布只需求出任一码字与其他所有码字的距离分布就可以了，因为所有码字的距离分布都相同，又因为任两个码字的差仍为一码字，所以边距分布相同。
2. 线性分组码的纠检错能力
由生成矩阵产生的码字在信道传输过程中，由于干扰的存在，使得一些码元发生错误。接收端通过编码规则进行译码，如能发现错误，则称为检错，如果再能纠正错误，称为纠错。码能纠检错误码元的个数称为该码的纠检错能力。发现错误和纠正错误的个数越多，则说明该码的纠检错能力越强。只要接收码字R没有错到变成其他发送码字，就可以发现错误。因此设计的码字之间应有较大的区别，即它们的汉明距离要大。
定理 对于一个二进制对称信道，当输入为 个等可能的n长码字时，最大后验概率准则等效于最小汉明距离译码准则。
定理线性分组码的最小距离等于非零码字的最小重量。
推论对于(n,k)线性分组码，设 为最小汉明距离，则
(1) 这组码能纠正u个错误的充要条件是 ；
(2) 具有检测l个错误的充要条件是 ；
(3) 具有纠正t个错误，同时可以发现l(l>t)个错误的充分必要条件为
推论码的纠错能力u与码字的长度n和消息数m也满足一定的关系：
若n长码字中信息位为k，则 ，所以有
3. 校验矩阵与最小距离的关系
校验矩阵H除了用来校验码字外，还与码的最小距离进而与码的纠错能力发生一定的关系。
定理对于(n,k)线性分组码：校验矩阵H中的任意t列线性无关而t+1列线性相关，则码字的最小距离或码字的最小重量为t+1。反之，若码字的最小重量或最小距离为t+1则H的任意t列线性无关而t+1列线性相关。
如果设计的(n,k)线性分组码达到了 ，则称为极大最小距离码。
由于码的最小汉明距离与纠错能力又有以下关系：
即如果线性分组码能纠正u个错误，则H中必有2u个列向量线性无关，而2u+1个列向量线性相关。
*4. 线性分组码的伴随式及伴随式译码
由于 ，校验矩阵可以用来验证接收码字是否为许用码字．设发送码字为C，接收码字为R，令 。当R为许用码字C时满足校验方程 ，因此S=0。若S≠0，则说明R不是发送码字，码字在传输过程中产生了错误。所以S是码字在传输过程中是否出现错误的标志，称为伴随式（或称监督子、校验子等）。
设接收码字R是发送码字C在传输过程中产生差错得到的，可以将R写成R=C+E， 称为差错图样。当码字的第i位发生错误时 ，否则 。
可以通过伴随式得到错误图样信息，然后对接收码字进行修正，以得到正确的译码。
定理 若(n,k)线性分组码能够纠正u个错误，则其校验位的数目必须满足
式()等号成立时的线性分组码称为完备码。
完备码具有下述特性：
（1）每一个接收码字都落在这些球中之一，因此接收码字与发送码字的距离至多为u；
（2）所有差错数小于等于u的接收码字都能得到纠正；
（3）差错数大于等于u+1的接收码字，因为落在另一个球内被纠正为其他的发送码字。
完备码并不多见，我们知道的有u=1的汉明码、u=3的高莱码，以及(n,1)中n为奇数的重复码等。
()
汉明码
汉明码是指能够纠正一个错误的线性分组码．它是香农的信道编码定理提出后最早发现的码，有二进制的，也有非二进制的．这里讨论二进制的汉明码．
汉明码是能够纠正一个错误的线性分组码，因此码长n和信息位数k服从以下规律：
其中，m=n-k为校验位数。
只要把(n-k)个码元组成的列矢量按二进制数大小顺序从左到右排列．就可以得到它的H。这样得到的H是非系统码。当发生单个错误时，伴随式是H中与错误位置对应的列，并且伴随式的二进制数的值就是错误位置的序号，因此它的编译码规则很简单。如果想得到系统形式的H ，可以通过列置换把非系统形式的H变成系统形式的H 。
()
循环码
循环码是线性分组码的一个子集，它具有完整的代数结构，编码和译码可以用具有反馈联级的移位寄存器来实现。它满足循环移位特性：码C中任何一个码字的循环移位仍是码C中的一个码字。
定义对于一个(n,k)线性分组码，
若某一码字为
若 均为码字，则称这个(n,k)线性分组码为循环码。循环移位也可以定义为向右移位。
该码字向左循环一位后为
向左循环移动i位后为
构造循环码的步骤：
(1) 对 作因式分解，找出(n-k)次因式；
(2) 以该(n-k)次因式作为生成多项式，与不高于(k-1)次的信息多项式相乘得码多项式C(x)=m(x)g(x)，C(x)的次数不高于(k-1)+(n-k)=(n-1)次。
循环码是线性分组码中非常重要的一个子类，要设计一个码率R=k/n的循环码，只要将 解出一个(n-k)次因式g(x)就可以生成(n,k)循环码。目前有实用价值的纠错码大部分都属于循环码的范围，比如在无线信道上应用最广泛的BCH、RS等。
BCH码是一类重要的循环码。它把生成多项式与码的最小距离和纠错能力联系起来，根据所需要的纠错能力，选取适当的g(x)，可以方便地得到非常有效地纠正多个独立错误的码。
卷积码
我们考虑在码长n有限的情况下，将有限个分组的相关性消息添加到码字里，从而等效地增加码长。译码时利用前后码字的相关性将前面的译码信息反馈到后面作译码参考。这就是编码器在某个时间段产生的n个码元，不但取决于该时间段进入编码器的信息组的k个信息位，还与前面的N-1个时间段内的信息组有关，这就是树码或称链码。
卷积码是树码中最重要的一类，它的码字与N个时间段的信息组的映射关系是时不变的线性关系，卷积码与分组码相似，具有纠正随机错误、突发错误或同时纠正这两类错误的能力。通常，它更适用于前向纠错法，因为其纠错性能对于许多实际情况常优于分组码，而且设备较简单，可用移位寄存起来完成编解码。
第七章 限失真信源编码
失真测度
信息率失真函数
信息率失真函数的计算
限失真信源编码定理和逆定理
熵压缩编码具体方法
在允许一定失真程度的条件下，怎样用尽可能少的信道符号来表达信源的信息，也就是信源熵所能压缩的极限或者说编码后信源输出的信息率压缩的极限值，这就是本章要讨论的问题——限失真信源编码问题。限失真信源编码也称保真度准则下的信源编码、熵压缩编码或者称信息率失真理论，它是量化、数模转换、频带压缩和数据压缩的理论基础。
如果无失真的冗余度压缩编码主要是针对离散信源的，那么，有失真的熵压缩编码主要是针对连续信源。本章讨论的是离散无记忆信源的限失真信源编码理论，这样便于理解率失真理论的基本概念。
失真测度
失真函数
对于每一对 ，指定一个非负的函数
称 为单个符号的失真度或失真函数，用它来表示信源发出一个符号 ，而在接收端再现为 所引起的误差或失真的大小。
设离散无记忆信源
经过信道传输后接收端的离散变量Y的概率空间
通常较小的d值代表较小的失真，而 表示没有失真。由于信源X有r个符号，信道输出Y有s个符号，所以 有r×s个，这r×s个非负的函数可以排列成矩阵形式，即
D称为失真矩阵，它是一个r×s阶矩阵。
失真函数是根据人们的实际需要和失真引起的损失、风险大小等人为规定的。常用的失真函数有
(1) 汉明失真
在离散对称信道(r=s)中，定义单个符号失真度为汉明失真。
汉明失真矩阵D通常为方阵，且对角线上的元素为0。即
D是r×r阶方阵。
(2) 平方误差失真函数
如果信源符号代表信源输出信号的幅度值，则上式意味着较大的幅度差值要比较小的幅度差值引起的失真更为严重，严重程度用平方表示。
定义 设发送序列为 ，接收序列为
定义序列的失真度为
写成矩阵形式时，是 阶矩阵。
平均失真
由于X,Y都是随机变量，故单个符号失真度 也是随机变量。显然，规定了单个符号失真度 之后，传输一个符号引起的平均失真，即信源的平均失真度为
它是在X,Y的联合概率空间求平均。
平均失真度已对信源和信道进行了统计平均，所以此值描述了某一信源在某一信道下的失真大小。
离散无记忆平稳信源通过离散无记忆平稳信道，其信源序列的平均失真度等于单个符号平均失真度的N倍。
信息率失真函数
D失真许可信道
如果要求信源符号的平均失真度小于我们所允许的失真D，即 ，称为保真度准则。N维信源序列的保真准则是
凡满足保真度准则的信道称为D失真许可的试验信道，所有D失真许可的试验信道的集合用 表示，即
对于离散无记忆信源的N次扩展信源和离散无记忆信道的N次扩展信道，相应的D失真许可的试验信道为
信息率失真函数的定义
我们总希望在满足保真度准则以后，压缩后的信息传输率 尽可能地小。把信源的压缩编码的过程看成一个信道，从这个信道的接收端来说， 可以用平均互信息I(X;Y)来表示，压缩过程中引入的失真可以用H (X|Y)表示。
我们的任务就是在满足保真度准则的所有D失真许可的试验信道集合 中寻找某一个信道 ，使I(X;Y)达到最小，即
这个最小值R(D)就是信息率失真函数，也称率失真函数，它的单位是比特/信源符号、哈特莱/信源符号或奈特/信源符号。
对于N维信源符号序列，同样可以得其信息率失真函数：
当信源和信道均为无记忆时，I(X;Y)=NI(X;Y)，所以有
信息率失真函数是在信源固定，满足保真度准则的条件下的信息传输率的最小值，它反映了满足一定失真度的条件下信源可以压缩的程度，也就是满足失真要求而再现信源消息所必须获得的最少平均信息量。R(D)是信源特性的参量，R(D)一旦求出就与求极值过程中选择的试验信道无关，不同的信源R(D)不同。
信息率失真函数R(D)的性质
1. R(D)的定义域
R(D)的定义域，也就是D的取值范围，必须根据信源的概率分布和选定的失真函数 来确定，在不同的试验信道下，求得的可能取值范围。
这样可以得到R(D)函数定义域的
2. R(D)是关于D的下凸函数
R(D)是关于D的下凸函数，即对于任意
有
上限值
下限值
3. R(D)在定义域内是严格递减函数
由于R(D)具有凸状性，这意味着它在定义域内是连续的．并且R(D)在定义域内是递减的，即在 范围内，若 ，则
因此在 中I(X;Y)为最小的试验信道 必在 的边界上，即
所以我们通常选择在 的条件下来计算信息率失真函数。
根据以上性质，可以画出率失真函数R(D)的曲线图：
图 信息率失真函数
信息率失真函数的计算
应用参量表示式计算R(D)
下面采用拉格朗日乘数法求解R(D)函数，采用S作为参量来表示信息率失真函数R(D)和失真函数D(S)。即在
的约束条件下求
通常推导可得出
这表明参量s是信息率失真函数R(D)的斜率．由R(D)在 之间是严格的单调递减函数可知，s必是负值．并且由于R(D)是下凸函数，所以s将随D的增加而增加．在D=0处， ，当
时， R(D) =0斜率为0，所以s =0 ；而在 处，s一般是从一个非常小的负数跳变到0。
对于不同p值可以得出一组R(D)的曲线，如图所示，可以看出，对于给定的平均失真度D，信源分布越均匀（ p值接近1/2）， R(D)越大，可压缩性越小；反之，信源分布越不均匀，R(D)越小，可压缩性越大。
图 不同p值对应的信息率失真函数
对于不同的r值可以得到一组R(D)曲线．对于给定的平均失真度D， r越大， R(D)越大，信源可压缩性越小；反之， r越小， R(D)越小，信源可压缩性越大，如图所示。
因此信息率失真函数可以用于比较编码方法的压缩效果。
信息率失真理论给出了在给定的失真度D条件下，信源输出的信息率所能压缩的极限R(D) ，没有给出具体的压缩方法．但是它可以作为一种尺度，衡量一种压缩编码的方法的压缩效果。
图 不同r值对应的信息率失真函数
二元信源和离散等概信源的R(D)函数
对于汉明失真的离散信源，除了参量表示式以外还可以运用一些技巧来求解R(D)。
由于采用了汉明失真度，平均失真度就等于平均错误概率，使得求解R(D)的过程简化，结果与参量表示式中求得的结果是一样的。但汉明失真度不是一种最合理的失真函数。实际应用中，设计一种符合信源主观要求的，合理的失真函数是很重要的。
限失真信源编码定理和逆定理
限失真信源编码定理
对于无失真信源编码来说，在允许一定失真的情况下，信源输出信息率最少可减少到信息率失真函数R(D) ，有可能是多个信源符号（符号序列）对应一个码字（码字序列）。失真信源编码定理就是关于信息率和失真关系的一个极限定理，也称香农第三定理，保真度准则下的离散信源编码定理。
定理 设R(D)是离散无记忆信源的信息率失真函数并且失真函数为有限值．对于任意的允许失真度D≥0和任意小的正数ε>0，当信源序列长度N足够长时，一定存在一种编码 ，其码字个数 ，而编码后的平均失真度
限失真信源编码逆定理
定理 不存在平均失真度D而信息传输率R′＜ R(D)的任何信源编码．即对任意码长为N的信源码C，若码字个数
逆定理说明，如果编码后平均每个信源符号的信息传输率R′＜ R(D) ，就不能在保真度准则下再现信源的信息。
限失真信源编码定理也是一个极限存在定理，不能像无失真信源编码定理那样从证明过程中引出概率匹配的编码方法。一般只能从优化的思路去求最佳编码，至今尚无合适的可实现的编码方法来接近R(D)这个极限。常用的限失真信源编码有量化编码、预测编码、变换编码。
则
熵压缩编码具体方法
标量量化
对连续无记忆信源进行熵压缩编码的常用方法是标量量化。设标量量化器的输出符号共有M个： ，量化的过程为将取值为任意实数的信源输出符号x映射成M个可能的离散值中的一个。该映射是通过M-1个门限 实现的。
标量量化器的输入符号序列为
其输出序列共有 种，记为
每个符号 出现的概率为
由于此映射为多对一映射，所以通过该量化器传输的信息率为
而量化带来的平均失真为
一般来讲，标量量化器输出符号的概率分布不一定是均匀分布。量化器输出的最大可能比特速率为
矢量量化
在标量量化中，我们总是对每个信源符号单独处理，这样的处理方法忽略了信源符号之间的相关性，因此信源的冗余度没有得到有效的压缩。通过将多个符号构成的序列作为一个整体进行量化的方法可以避免标量量化的固有缺点，这种方法称为矢量量化。
先将待编码的信源符号序列划分为一个个等长的分组，每个分组含有若干个符号，形成一个矢量。每个矢量与预先生成的矢量码书中的每个码字进行比较，求出相应的失真，然后用失真最小的码字的编号作为量化器的输出就实现了矢量量化。
由于在译码端有一个同样的码书，所以译码工作只是通过接收的码字序号在码书中搜索相应的码字，算法简单，容易实现。
矢量量化的关键在于矢量码书的构造，目前最流行的算法是由
Y. Linde、A. Buzo、R. M. Gray共同提出的LBG算法：
(1) 采集用于构造码书的训练数据，为了得到性能较好的矢量码书，一般要求训练样本的数量N和码字的个数L满足：N ≥ 20L；
(2) 构造初始码书，常用的构造方法有随机码书法、白噪声码书法等；
(3) 按照初始码书对所有的训练样本进行矢量量化，得到分属不同码 字的L个样本集合和相应的量化误差；
(4) 对每个样本集合进行聚类，根据聚类的结果修正初始码字，得到 新的码书；
(5) 判断量化误差是否小于门限值、迭代次数是否超出规定值，若是， 则训练结束，否则转第3步继续。
矢量量化中第二个重要的问题是量化误差的度量问题，即如何选择一个能准确反映量化前后失真大小的度量函数。这个问题与被编码的对象的具体特性有关，没有一个统一的答案。
矢量量化的第三个问题是搜索运算量问题。在量化的过程中，需要计算待量化矢量与所有码字的失真，然后选取失真最小的码字。当码书的规模较大时需要很大的计算量。可以通过为码书安排某种特定的结构(如二叉树)来有效地降低运算量。
矢量量化具有如下特点
(1) 矢量维数N越大，量化失真越小；
(2) 码字个数L越大，量化失真越小，相应的存储空间开销和搜索时间开销也越大。
变换编码
为了去除信源符号之间的相关性，通常将信源符号序列划分为较长的分组，然后对每个分组进行统一的编码。这仅仅是去除相关性的最简单的一种方法。还可以通过某种数学变换来去除信源符号之间的相关性。
将信源符号经过数学变换后再进行编码就称为变换编码。常用的数学变换有傅里叶(Fourier)变换、小波(Wavelet)变换、沃尔什- 哈达玛(Walsh-Hadamard)变换、K-L(Karhunen-Loeve)变换、余弦变换、正弦变换等等．其中，K-L变换去相关性最好，但算法复杂、实现困难；而离散余弦变换(DCT)的性能接近K-L变换，也容易实现，被选为众多图像压缩编码技术标准的基本算法。
* 预测编码
预测编码的概念最早是由Peter Elias在1955年提出的，它是目前得到广泛应用的一种实用的熵压缩树码。
在预测编码的编码器和译码器中都存储有过去的符号值，并以此来预测或估计未来符号的值；编码器的输出不是信源符号本身，而是实际信源符号与预测值之间的差值；在译码端，译码器将接收到的这一差值与译码器的预测值相加，从而恢复信源符号。预测编码的编译码过程如图和所示。
图 预测编码器
图 预测译码器
根据预测器中预测值与信源符号过去时刻的值之间的函数关系，可将预测器分为线性预测器和非线性预测器，相应的预测编码称为线性预测编码和非线性预测编码。
设信源输出的符号序列为 ，预测器根据所存储的过去的符号值对时刻n的符号进行预测，得到的预测值 与实际 之间的差值称为预测误差：
预测编码设计中的核心问题使如何选取预测函数以使预测误差满足某种最佳条件。常见的几种条件是最小均方误差、最小平均决定误差和最大零误差概率。
不同准则下的最佳预测给出不同的预测值和不同的预测误差值，但是预测误差的分布与信源符号的一维分布具有相同的形状，其差别只是因为减去预测值所导致的分布的平移。
甲布袋放入n个不同阻值的电阻
乙布袋放入n个不同功率的电阻
丙布袋中放入n*m个不同阻值,不同功率的电阻
则从甲乙布袋各拿出一个电阻所获得的信息量之和与从丙取出相同阻值与功率的电阻的信息量相等
