信息论与编码总复习

信息论与编码总复习知识点信息、消息和信号信息是事物运动状态或存在方式的不确定性的描述。信息是用以消除随机不确定性的东西消息是指包含有信息的语言、文字和图像等信号是消息的物理体现。在通信系统中，实际传输的是信号，但本质的内容是信息。信息包含在信号之中，信号是信息的载体。通信的结果是消除或部分消除不确定性，从而获得信息。香农信息的定义

信息论研究的内容狭义信息论：主要研究信息的测度、信道容量以及信源和信道编码理论等问题。一般信息论：主要也是研究信息传输和处理问题，除香农信息论，还包括噪声理论、信号滤波和预测、统计检测和估计、调制理论、信息处理理论以及保密理论等。广义信息论：不仅包括上述两方面内容，而且包括所有与信息有关的自然和社会领域，如模式识别、计算机翻译、心理学、遗传学、神经生理学、语言学、语义学甚至包括社会学中有关信息的问题数字通信系统模型信道信源信源编码加密信道编码干扰源信宿信源解码解密信道解码加密密钥解密密钥概率论基础无条件概率、条件概率、联合概率的性质和关系⑴⑵⑶概率论基础无条件概率、条件概率、联合概率的性质和关系⑷⑸⑹

{信源离散信源:文字、数据、电报—随机序列连续信源:话音、图像—随机过程

信源的分类按照信源发出的消息在时间上和幅度上的分布情况可将信源分成离散信源和连续信源两大类连续信源指发出在时间和幅度上都是连续分布的连续消息（模拟消息）的信源，如语音、图像、图形等都是连续消息。

离散信源{离散无记忆信源离散有记忆信源{{发出单个符号的无记忆信源发出符号序列的无记忆信源发出符号序列的有记忆信源发出符号序列的马尔可夫信源信源的分类离散信源指发出在时间和幅度上都是离散分布的离散消息的信源，如文字、数字、数据等符号都是离散消息。离散无记忆信源所发出的各个符号是相互独立的，发出的符号序列中的各个符号之间没有统计关联性，各个符号的出现概率是它自身的先验概率。发出单个符号的信源指信源每次只发出一个符号代表一个消息；发出符号序列的信源指信源每次发出一组含二个以上符号的符号序列代表一个消息信源的描述设信源输出的随机序列为

X=(X1X2…Xl…XL)序列中的变量Xl∈{x1,x2,…

xn}这种由信源X输出的L长随机序列X所描述的信源称为离散无记忆信源X的L次扩展信源随机序列的概率当信源无记忆时

有记忆信源所发出的各个符号的概率是有关联的。发出符号序列的有记忆信源发出符号序列的马尔可夫信源马尔可夫信源m阶马尔可夫信源：信源输出某一符号的概率仅与以前的m个符号有关，而与更前面的符号无关。一阶马尔可夫信源：14马尔可夫信源一类相对简单的离散平稳有记忆信源该信源在某一时刻发出字母的概率除与该字母有关外,只与此前发出的有限个字母有关m阶马尔可夫信源：信源输出某一符号的概率仅与以前的m个符号有关，而与更前面的符号无关。条件概率马尔科夫链的概念若把有限个字母记作一个状态S，则信源发出某一字母的概率除与该字母有关外，只与该时刻信源所处的状态有关。信源将来的状态及其送出的字母将只与信源现在的状态有关，而与信源过去的状态无关。状态的数目与阶数的关系；描述马尔科夫链的状态转移：——状态转移概率——符号条件概率——状态转移图马尔科夫信源达到稳定状态的条件；极限概率及其含义16马氏链的基本概念令si

=(xi1,

xi2,

…xim)xi1,,xi2,

…xim

∈(a1,

a2,

…an)状态集S={s1,s2,…,sQ}Q=nm信源输出的随机符号序列为：x1,x2,…xi-1,xi…信源所处的随机状态序列为：s1,s2,…si-1,si

…例：二元序列为…01011100…考虑m=2，Q=nm=22=4s1=00s2=01s3=10s4=11变换成对应的状态序列为

…s2s3s2s4s4s3s1…17马尔可夫信源设信源在时刻m处于si状态,它在下一时刻(m+1)状态转移到sj的转移概率为：

pij(m)=p{Sm+1=sj|Sm=si}=p{sj|si}pij(m)：基本转移概率（一步转移概率）若pij(m)与m的取值无关,则称为齐次马尔可夫链

pij=p{Sm+1=sj|Sm=si}=p{S2=sj|S1=si}pij具有下列性质：

pij≥018若信源处于某一状态si,当它发出一个符号后,所处状态就变了,任何时候信源处于什么状态完全由前一时刻的状态和发出符号决定。系统在任一时刻可处于状态空间S={s1,s2,…,sQ}中的任意一个状态,状态转移时,转移概率矩阵符号条件概率矩阵区别19马尔可夫信源状态转移图齐次马尔可夫链可以用其状态转移图(香农线图)表示每个圆圈代表一种状态

状态之间的有向线代表某一状态向另一状态的转移有向线一侧的符号和数字分别代表发出的符号和条件概率sos11/0.60/0.30/0.4s21/0.20/0.81/0.720马尔可夫信源遍历状态：非周期的、常返的状态,如图中的状态s2和s3闭集：状态空间中的某一子集中的任何一状态都不能到达子集以外的任何状态不可约的：闭集中除自身全体外再没有其他闭集特殊结论21马尔可夫信源一个不可约的、非周期的、状态有限的马尔可夫链其k步转移概率pij(k)在k→∞时趋于一个和初始状态无关的极限概率Wj，它是满足方程组的唯一解；Wj

：马尔可夫链的一个平稳分布，

Wj[或p(sj)]就是系统此时处于状态sj的概率。无论随机点从哪一个状态si出发，当转移的步数k足够大时，转移到状态sj的概率pij(k)都近似于一个常数Wj平均互信息互信息、平均互信息的定义方式；平均互信息的含义；平均互信息的数学性质（包括与熵之间的关系及其含义）；数据处理定理（信息不增性原理）。互信息量定义互信息量表示先验的不确定性减去尚存的不确定性，这就是收信者获得的信息量；互信息量可能为正数、负数、零；对于无干扰信道，I(xi;yj)=I(xi)；对于全损信道，I(xi;yj)=0；xiyj信道p(xi):发送端发送

xi的概率（也叫先验概率）；P(xi|yj):

接收端收到

yj后，发送端发送

xi的概率（也叫后验概率）定义:平均互信息量定义：与其他熵的关系：

I(X;Y)=H(X)-H(X|Y)I(X;Y)=H(Y)-H(Y|X)I(X;Y)=H(X)+H(Y)-H(X,Y)表达平均互信息量的熵I(X;Y),是确定通过信道的信息量的多少，因此称它为信道传输率或传信率。平均互信息量另一种定义：离散随机变量X和Y之间的平均互信息量根据概率之间的关系式有：I(X;Y)和I(Y;X)是随机变量X和Y之间相互提供的信息量

——称为互信息是完全确切的平均互信息量平均互信息I(X;Y)和I(Y;X)是对X和Y之间统计依存程度的信息量度：当随机变量X和Y之间有确定的关系时，X可以唯一确定Y，此时，H(Y|X)=0→I(X;Y)=H(Y)Y可以唯一确定X，此时，H(X|Y)=0→I(X;Y)=H(X)在通信系统中，若发端的符号是X，而收端的符号是Y，则互信息I(X;Y)就是在接收端收到Y后所能获得的关于X的信息。若干扰很大，Y基本上与X无关，或者说X与Y相互独立，那时就收不到任何关于X的信息，即I(X;Y)=0；若没有干扰，Y是X的确知一一对应函数，那时就能充分地收到X的信息，即I(X;Y)=H(X)∴互信息的范围是：0≤I(X;Y)≤H(X)平均互信息量的性质平均互信息量的基本性质非负性：即I(X;Y)>=0极值性：即I(X;Y)<=H(X)对称性：即I(X;Y)=I(Y;X)平均互信息量I(X;Y)是输入信源X的概率分布p(xi)和信道转移概率p(yj|xi)的函数，即I[p(xi)，p(yj|xi)]当p(xi)一定时，I是关于p(yj|xi)的∪型下凸函数，存在极小值；当p(yj|xi)一定时，I是关于p(xi)的∩型上凸函数，存在极大值；对于无损信道，有I(X;Y)=H(X)=H(Y)=H(X,Y)对于全损信道，有I(X;Y)=0已知级联处理器在Y条件下，X与Z相互独立，即I(X;Z|Y)=0;而且I(X:Y|Z)和I(Y:Z|X)均为非负量，故可得：I(X;Z)≤I(Y;Z),I(X;Z)≤I(X;Y)结论：当消息通过多级处理器时，随着处理器数目的增多，输入消息与输出消息之间的平均互信息量趋于变小。第一级处理器第二级处理器XYZ§2.2.5数据处理中信息的变化信息处理定理：数据处理过程中只会失掉一些信息，决不会创造出新的信息——信息不增性。信息处理定理说明：任何信息处理过程总会丢掉信息，最多保持原来的信息，一旦丢掉了信息，用任何处理手段也不可能再恢复丢失的信息。对于观测采集到的数据做任何加工和处理，只会造成有用信息的损失，或不确定性的增加。因此，由计算机系统对输入数据进行处理，绝对不会增加信息量，要减少信息处理过程中信息的损失，就需要增加计算处理的工作量，或采用较为复杂的处理设备。§2.2.5数据处理中信息的变化一般通信系统的信息流程：根据信息不增性原理有：

I(U;V)≤I(X;V)，I(X;V)≤I(X;Y)从而有I(U;V)≤I(X;Y)编码信道译码UXYV信源信宿§2.2.5数据处理中信息的变化§2.2.5数据处理中信息的变化数据处理定理得另一个应用——多次测量如果想从测量结果Y中得到越来越多的关于X的信息量，必须付出代价。常用的方法是通过多次测量。

∵H(X|Y1,Y2)≤H(X|Y1)∴I(X|Y1,Y2)≥I(X|Y1)可证明取测量值Y的次数越多，X的条件熵越小，获得的信息量就越大。尤其当各次测量值相互独立时，趋势更明显。取Y无数次后，H(X|Y1,Y2,Y3,…)→0自信息量

概率越大，不确定性越小；反之符号出现的概率越小，不确定性越大。定义方式；I

(xi)含义；消息xi的概率P(xi)对数的负值为该消息的自信息量，用I(xi)表示。自信息的单位的确定；单位由对数的底a决定——当a=2时为比特(bit，binaryunit)*；a=e时为奈特(nat，natureunit)；a=10时为哈特(Hart，Hartley)。以比特(bit)为单位的自信息量可记为目前的通信系统多以二进制为基础，因此信息量的单位以bit最为常用。I(xi)的特性：⑴I(xi)是非负值⑵当p(xi)=1时，I(xi)=0⑶当p(xi)=0时，I(xi)=∞⑷I(xi)是先验概率p(xi)的单调递减函数，即当p(x1)＞p(x2)时，I(x1)＜I(x2)⑸两个独立事件的联合信息量等于它们分别的信息量之和。即统计独立信源的信息量等于它们分别的信息量之和。I(Xi|Yj)=I(Xi)+I(Yj)离散信源熵

信源各消息自信息量的数学期望为该信源的熵，也叫无条件熵，用H(X)表示。定义方式单位单位一般是比特/消息(bit/message)，对单符号信源，是比特/符号(bit/symbol)。H(X)反映信源每发出一条消息所提供的平均信息量，不反映信源发出某条特定消息的信息量H(X)表示信源的平均不确定性一般情况下，H(X)并不等于每接受一条消息所获得的平均信息量。含义及与自信息的区别；条件熵和联合熵的定义方式；联合熵X1、X2可以是具有相同的概率空间的随机变量条件熵X1、X2可以是具有相同的概率空间的随机变量n=2,3,…LH(X1/X2):表示已知一个符号(X1发出)时,信源将要输出下一个符号(X2发出)的平均不确定性.对于L维离散随机序列X1X2…XL,当已知前n-1个符号时,后面将要出现第下n个符号的平均不确定性就是条件熵:信源熵的数学性质1、对称性：H(P)的取值与分量p1,p2

,

···

,pq的顺序无关。2、确定性：H(1,0)=H(1,0,0)=H(1,0,0…,0)=0只要信息源符号中，有一个符号出现的概率为1，信源熵就等于零。3、非负性：H(X)04、严格上凸性5、可加性

统计独立信源X和Y的联合信源的熵等于信源X和Y各自的熵之和。H(XY)=H(X)+H(Y)

6、条件熵小于无条件熵H(Y|X)≤H(Y)两个条件下的条件熵小于一个条件下的条件熵，H(Z|X,Y)≤H(Z|Y)联合熵小于信源熵之和，H(X,Y)≤H(X)+H(Y)7、香农辅助定理

任一概率分布{p(ai)}，它对其它概率分布{p(bi)}的自信息取数学期望时，必大于{p(ai)}本身的熵8、最大熵定理（极值性）在离散信源情况下，信源各符号等概率分布时，熵值达到最大。性质表明等概率分布信源的平均不确定性为最大。这是一个很重要的结论，称为最大离散熵定理。9、扩展性性质说明：信源的取值数增多时，若这些取值对应的概率很小(接近于零)，则信源的熵不变。所以，上式成立因为离散平稳信源如果各维联合概率分布均与时间起点无关，那么，信源是完全平稳的。这种各维联合概率分布均与时间起点无关的完全平稳信源称为离散平稳信源。这时有：P(xi)=P(xj)P(xixi+1)=P(xjxj+1)……P(xixi+1…xi+N)=P(xjxj+1…xi+N)输出序列的信源的序列熵；H(X)=H(X1X2…XL)=H(X1)+H(X2/X1)++H(X3/X1X2)…+H(XL/X1X2….XL-1)记作H（X）=H（XL）=平均符号熵N长的信源符号序列中平均每个信源符号所携带的信息量称为平均符号熵.H（X）=1/LH（XL）若当信源退化为无记忆时,有H(X)=若进一步又满足平稳性时，则有H(X)=LH(X)平均符号熵与条件熵的四条性质及其含义①条件熵是L的单调非递增函数②当L给定时,平均符号熵≥条件熵,即③平均符号熵HL(X)是L的单调非增函数④H∞(X)=HL(X)=H(XL/X1X2…XL-1)称H∞为平稳信源的极限熵或极限信息量。马尔科夫信源熵的计算方法；计算熵Hm+1H∞(X)对状态的全部可能性作统计平均,就可以得到马尔可夫信源的平均符号熵是马尔可夫链的平稳分布表示处于某一状态时发出一个消息符号的平均不确定性,即冗余度与效率的定义及其含义。冗余度（多余度、剩余度）表示给定信源在实际发出消息时所包含的多余信息。冗余度来自两个方面:一是信源符号间的相关性，由于信源输出符号间的依赖关系使得信源熵减小，这就是信源的相关性。相关程度越大(长)，信源的实际熵越小，趋于极限熵H

（X）；反之相关程度减小，信源实际熵就增大。另一个方面是信源符号分布的不均匀性，当等概率分布时信源熵最大。而实际应用中大多是不均匀分布，使得实际熵减小。当信源输出符号间彼此不存在依赖关系且为等概率分布时，信源实际熵趋于最大

H0(X)=Hmax(X)。

信息效率（熵的相对率）

信源的实际信息熵与具有同样符号集的最大熵的比值

表示不肯定的程度冗余度

表示肯定性的程度，因为肯定性不含有信息量，因此是冗余的。信道信道的分类用户数量：单用户、多用户输入端和输出端关系：无反馈、有反馈信道参数与时间的关系：固定参数（光纤、电缆信道）、时变参数（无线信道）噪声种类：随机差错（高斯白噪声）、突发差错（干扰的影响是前后相关的，错误成串出现，衰落信道、码间干扰信道）输入输出特点：离散、连续、半离散半连续、波形信道按输入/输出信号在幅度和时间上的取值:离散信道：输入和输出的信号在时间和幅度上均是离散的连续信道：幅度是连续的时间是离散的半离散(半连续)信道：输入变量、输出变量取值一个连续一个离散波形信道：信道的输入和输出在时间和幅度上均连续按输入/输出之间关系的记忆性来划分：无记忆信道：信道的输出只与信道该时刻的输入有关,而与其他时刻的输入无关有记忆信道：信道的输出不但与信道现时的输入有关而且还与以前时刻的输入有关按输入／输出信号之间的关系是否是确定关系:无干扰信道：输入/输出符号之间有确定的一一对应关系有干扰信道：输入/输出之间关系是一种统计依存的关系输入/输出的统计关系：离散无记忆信道：用条件概率矩阵来描述。离散有记忆信道：可像有记忆信源中那样引入状态的概念。3.1信道分类和表示参数信道参数信道种类信道容量的定义；信息传输率信道在单位时间内平均传输的信息量定义为信息传输速率R=I(X;Y)=H(X)－H(X/Y)比特/符号Rt=I(X;Y)/t比特/秒信道容量比特/符号（bits/symbol或bits/channeluse）

无干扰离散信道的描述与特点：无噪无损信道有噪无损信道无噪有损信道无噪无损信道n=m：转移概率为：

信道矩阵为单位阵：

无噪无损I(X;Y)=H(X)=H(Y)C=maxI(X；Y)=logn无噪有损信道(确定信道)n>m：无噪→噪声熵H(Y|X)=0；有损→

疑义度H(X|Y)≠0

；

I(X;Y)=H(Y)≤H(X)

C=maxI(X；Y)=maxH(Y)有噪无损信道：n<m疑义度H(X|Y)=0噪声熵H(Y|X)≠0H(X)≤H(Y)

；C=maxI(X；Y)=maxH(X)DMC信道对称离散无记忆DMC信道特点及其信道容量信道矩阵中的每一行都是第一行的重排列（输入对称）；信道矩阵中的每一列都是第一列的重排列（输出对称）。准对称DMC信道特点及其信道容量；如果转移概率矩阵P是输入对称而输出不对称，即转移概率矩阵P的每一行都包含同样的元素而各列的元素可以不同，则称该信道是准对称DMC信道二元对称信道BSC的信道容量：0101XYpp1-p1-p设输入符号的概率分布为

p(0)=a,p(1)=1-a,条件概率

p(0|0)=p(1|1)=p,p(1|0)=p(0|1)=1-p,则有§3.2.2对称DMC信道的信道容量从而可以计算出：又因为

但是仅发生在下，故BSC的信道容量为：当p=1/2时，二元对称信道的信道容量C=0，不管输入概率分布如何都能达到信道容量。该信道输入端不能传递任何信息到输出端。这种信道是没有任何实际意义的，但它从理论上说明了信道的最佳输入分布不一定是惟一的。二进制对称信道容量C＝1－H（p）0.51.000.51.0cp§3.2.2对称DMC信道的信道容量3.2离散单个符号信道及其容量串联信道C(1,2)=maxI(X;Z)，C(1,2,3)=maxI(X;W)…3.8串联信道及其信道容量若信道II的传递概率使其输出只与输入Y有关，与前面的输入X无关，即满足

称这两信道的输入和输出X，Y，Z序列构成马尔可夫链。

这两个串联信道可以等价成一个总的离散信道，其输入为X，输出为Z，取值，此信道的转移概率为则总信道的传递矩阵若X，Y，Z满足马尔可夫链，得总信道的传递概率

信道矩阵为

对于串联信道，若其输入输出变量之间组成一个马尔可夫链，则存在下述定理。该定理对于串联的单符号离散信道或是输入、输出都是随机序列的一般信道都成立。两个定理定理3.7当且仅当时等式成立。定理3.8若X、Y、Z组成一个马尔可夫链，则有定理3.8表明通过数据处理后，一般只会增加信息的损失，最多保持原来获得的信息，不可能比原来获得的信息有所增加。也就是说，对接收到的数据Y进行处理后，无论变量Z是Y的确定对应关系还是概率关系，决不会减少关于X的不确定性。故定理3.8称为数据处理定理。3.3离散序列信道及其容量

离散序列信道

信道

p(Y/X)

Y

X

X=(X1X2…XL)Xl

{a1,a2,…,an}Y=(Y1Y2…YL)Yl

{b1,b2,…,bm}3.3离散序列信道及其容量

离散无记忆序列信道

11111进一步信道是平稳的

3.3离散序列信道及其容量

离散无记忆序列信道

11111如果信道无记忆如果输入矢量X中的各个分量相互独立

当信道平稳时CL=LC1，一般情况下，I(X;Y)

LC1

限时限频限功率的加性高斯白噪声信道

高斯白噪声加性信道单位时间的信道容量——香农公式。高斯白噪声加性信道单位时间的信道容量：

Ps是信号的平均功率；N0W为高斯白噪声在带宽W内的平均功率（功率谱密度为N0/2）；信道的信噪比SNR=Ps/

N0W——著名且重要的Shannon香农公式当信道输入信号是平均功率受限的高斯信号时，信道中的信息传输率可达到上式的信道容量。此为在噪声信道中可靠通信，信息传输速率的上限值。由香农公式可以得到一般非高斯波形信道的信道容量的下限值。4.1.1失真函数X={xi}，xi

{a1,…an}

信源编码器

Y={yj}，yj

{b1,…bm}失真函数d(xi，yj)失真矩阵

单个符号的失真度的全体构成的矩阵，称为失真矩阵4.1.2

平均失真

失真函数的数学期望称为平均失真，记为已知p(xi)和d(xi，yj)，平均失真只是符号转移概率p(yj/xi)的函数。p(yj/xi

)在此实质上代表编码方式。信源编码器

对于连续随机变量同样可以定义平均失真对于L长序列编码情况，平均失真为

4.1.3信息率失真函数R(D)

信源编码器的目的是使编码后所需的信息传输率R尽量小，R给定失真的限制值D，使

D，找最小R，

R(D)，定义为信息率失真函数。4.1.3信息率失真函数R(D)信源编码器XY假想信道将信源编码器看作信道，信源编码器输出的信息率R对应到信道，即为接收端Y需要获得的有关X的信息量，也就是互信息I(X;Y)。p(yj/xi)信源符号编码概率信道转移概率D允许试验信道

若p(xi)和d(xi，yj)已定，则可给出满足条件的所有转移概率分布pij，它们构成了一个信道集合PD

称为D允许试验信道。

信息率失真函数R(D)

当p(xi)一定时，互信息I是关于p(yj/xi)的U型凸函数，存在极小值(2.2节）。在上述允许信道PD中，可以寻找一种信道pij，使给定的信源p(xi)经过此信道传输后，互信息I(X；Y)达到最小。D=?p(yj/xi)=pij?R(D)=?I[p(xi)，p(yj/xi)]对于离散无记忆信源，R(D)函数可写成

p(ai)，i＝1，2，…，n

是信源符号概率分布；

p(bj/ai)，i＝1，2，…，n，j＝1，2，…，m

是转移概率分布；

p(bj)，j＝1，2，…，m是接收端收到符号概率分布。

R(D)的物理意义无失真时：R=H(X)有失真时：R=R(D)=H(X)－H(X/Y)H(X)H(X/Y)：由于压缩编码损失的信息对于给定信源，在平均失真不超过失真限度D的条件下，信息率容许压缩的最小值R(D)信源编码器H(X)R4.1.4信息率失真函数的性质

R(D)函数的定义域⑴Dmin和R(Dmin)

Dmin＝0

对于连续信源

何时Dmin=0?只有当失真矩阵中每行至少有一个零元素。何时R(0)=H(X)?只有当失真矩阵中每行至少有一个零，并每一列最多只有一个零。否则R(0)可以小于H(X)，表示这时信源符号集中有些符号可以压缩、合并而不带来任何失真。

(2)Dmax和R(Dmax)

R(Dmax)=0选择所有满足R(D)＝0中D的最小值，定义为R(D)定义域的上限Dmax，即因此可以得到R(D)的定义域为R(D)＝0就是I(X;Y)＝0，这时试验信道输入与输出是互相独立的，所以条件概率p(yj/xi)与xi无关。即需满足条件从上式观察可得：在j=1，…，m中，可找到值最小的j，当该j对应的pj＝1，而其余pj为零时，上式右边达到最小，这时上式可简化成2、R(D)函数的下凸性和连续性

3、R(D)函数的单调递减性容许的失真度越大，所要求的信息率越小。反之亦然。R(D)是非负的实数，即R(D)

0。其定义域为0～Dmax，其值为0～H(X)。当D>Dmax时，R(D)

0。R(D)是关于D的下凸函数，因而也是关于D的连续函数。R(D)是关于D的严格递减函数。容许的D越大，所要求的R越小。反之亦然。信道容量C率失真函数R(D)R(D)与C的比较研究对象信道信源给定条件信道转移概率p(yj/xi)信源分布p(xi)选择参数信源分布p(xi)信源编码器编码方法p(yj/xi)限制条件结论I(X;Y)=H(X)-H(X/Y)噪声干扰消失的信息量H(X/Y)压缩损失的信息量H(X/Y)编码的定义编码器输入端为原始信源X=(X1X2…Xl…XL)，其符号集为A，即Xl∈{a1,a2,…ai,…an}信道所能传输的符号集B={b1,b2,…bj,…bm}编码器的功能是用符号集B中的元素，将原始信源的符号序列Xi变换为相应的符号序列Yj

=(Y1Y2…Yj…YKL)编码器L长序列KL长码字编码的定义二元信道是常用的一种信道，其基本符号集为{0,1}若将信源X通过一个二元信道传输，就必须把信源符号xi变换成由0,1符号组成的码符号序列，即编码。分组码：每个符号序列Xi依照固定的码表映射成一个符号序列Yj码字：变换后的各个符号序列Yj码长：码字Yj的长度（符号数）KL码元：组成码字Yj的各位代码符号bj码：所有码字的集合编码：全部Xi←→Yj的映射关系定长码和变长码定长码：所有码字的长度都相同变长码：可变长度码，码中的码字长短不一奇异码和非奇异码奇异码：一组码中有相同的码字。非奇异码：信源符号和码字一一对应，所有码字都不相同。唯一可译码任意有限长的码元序列，只能被唯一地分割成一个个的码字，便称为唯一可译码。奇异码不是唯一可译码，而非奇异码中有非唯一可译码和唯一可译码。非即时码和即时码非即时码：指接收端收到一个完整的码字后，不能立即译码，还需等下一个码字开始接收后才能判断是否可以译码。即时码：无须考虑后续的码符号，即可从码元序列中译出码字。唯一可译码成为即时码的充分条件是：其中任何一个码字都不是其他码字的前缀。码树码树用来表示各码字的构成。A0100000000000011111111111树根—码字的起点分成r个树枝—码的进制数中间节点—生出树枝终端节点—码字11010120000011111222220021码树中间节点不安排码字，只在终端节点安排码字每个终端节点对应的码字由从根节点出发到终端节点走过的路径上所对应的符号组成当第i阶的节点作为终端节点，且分配码字，则码字的码长为i按树图法构成的码一定满足即时码的定义树码的各个分支都延伸到最后一级端点，则称为满树，否则为非满树

满树码是定长码，非满树码是变长码码树克劳夫特不等式唯一可译码存在的充分和必要条件为：各码字的长度Ki

应满足下式。m是进制数，n是信源符号数注意：克拉夫特不等式只是说明唯一可译码是否存在，并不能作为唯一可译码的判据。综上所述，可将码作所示的分类：有mKL种可能的组合无失真信源编码设信源符号序列的长度为L变换成由KL个符号组成的码序列（码字）有nL种序列组合有nL种信源消息有mKL种可能的码字无失真信源编码变换要求能够无失真或无差错地从Y恢复X，也就是能正确地进行反变换或译码传送Y时所需要的信息率最小信息率Yk有m种可能值，平均每个符号输出的最大信息量为log2m，KL长码字的最大信息量为KLlog2m。用该码字表示L长的信源序列，送出一个信源符号所需要的信息率平均为Y所能编成的码字的个数找到使最小的编码方式定长编码在定长编码中，各码字的码长相等，即K为定值。编码器输入X=(X1X2…Xl…XL),

Xl∈{a1,…an},

输入的消息总共有nL种可能的组合输出的码字Y=(Y1Y2…Yk…YK),

Yk∈{b1,…bm}

输出的码字总共有mK种可能的组合只要码长K足够长，即满足:

则每个信源符号串都可以找到一一对应的码字定长编码的目的：寻找最小K值定长编码定理定长编码定理：由L个符号组成的、每个符号的熵为HL(X)的无记忆平稳信源符号序列X1X2…Xl…XL，可用KL个符号Y1,Y2,…,Yk,…YKL（每个符号有m种可能值）进行定长编码。对任意ε>0，δ>0，只要 则当L足够大时，必可使译码差错小于δ；反之，当 时，译码差错一定是有限值，而当L足够大时，译码几乎必定出错。定长编码定理当编码器容许的输出信息率，即每个信源符号所需要的信息率为 时，只要，这种编码器一定可以做到几乎无失真，也就是收端的译码差错概率接近于零，条件是所取的符号数L足够大。定理的条件可以改写为KL长码字所能携带的最大信息L长信源序列携带的信息量定长编码定理定理表明：只要码字所能携带的信息量大于信源序列输出的信息量，则可以使传输几乎无失真，条件是L足够大。反之，当时，不可能构成无失真的编码，也就是不可能做一种编码器，能使收端译码时差错概率趋于零。时，则为临界状态，可能无失真，也可能有失真。变长编码定理在变长编码中，码长K是变化的。我们可根据信源各个符号的统计特性，概率大的符号用短码，概率小的用较长的码，这样在大量信源符号编成码后平均每个信源符号所需的输出符号数就可以降低，从而提高编码效率。变长编码定理单个符号变长编码定理若一离散无记忆信源的符号熵为H(X)，每个信源符号用m进制码元进行变长编码，一定存在一种无失真编码方法，其码字平均长度满足下列不等式变长编码定理离散平稳无记忆序列变长编码定理对于平均符号熵为HL(X)的离散平稳无记忆信源，必存在一种无失真编码方法，使平均信息率满足不等式其中，ε为任意小正数。平均编码最佳码（紧致码）对于某个给定信源，在所有可能的唯一可译码中平均码长最短的码。最佳码可能不止一个。平均码长为了使平均码长最短，将概率大的信息符号编以短的码字，概率小的符号编以长的码字。编码效率编码效率信源的平均符号熵HL(X)，采用平均符号信息率来编码，所得的效率。最佳编码效率为编码定理从理论上给出了编码效率接近1的理想编码器的存在，即编码效率的下界编码效率总是小于1的，可以用它来衡量各种编码方法的优劣。码的剩余度：衡量各种编码方法与最佳码的差距香农编码方法香农第一定理指出了平均码长与信源之间的关系，同时也指出了可以通过编码使平均码长达到极限值。香农第一定理指出，选择每个码字的长度Ki满足就可以得到这种码。这种编码方法称为香农编码。香农编码步骤将信源消息符号按其概率从大到小排列确定满足下列不等式的整数码长Ki令P1=0，计算第i个消息的累加概率将累加概率Pi变换成二进制数，取小数点后Ki位为该消息的码字费诺编码方法费诺编码属于概率匹配编码，不是最佳的编码方法。编码过程如下：将信源消息符号按其出现的概率依次排列

p(x1)≥p(x2)≥…≥p(xn)按编码进制数将概率分组，使每组概率尽可能接近或相等，并为每一组分配一位码元。如编二进制码就分成两组，编m进制码就分成m组。将每一分组再按同样原则划分，重复步骤2，直至概率不再可分为止。信源符号所对应的码字即为费诺码。费诺码比较适合于每次分组概率都很接近的信源哈夫曼编码方法哈夫曼编码的步骤将信源消息符号按其出现的概率大小依次排列

p(x1)≥p(x2)≥…≥p(xn)取两个概率最小的符号分别配以0和1，并将这两个概率相加作为一个新符号的概率，与未分配码元的符号重新排队。对重排后的两个概率最小符号重复步骤2的过程。继续上述过程，直到最后两个符号配以0和1为止。从最后一级开始，向前返回得到各个信源符号所对应的码元序列，即相应的码字。哈夫曼编码方法哈夫曼的编法并不惟一每次对信源缩减时，给两个概率最小的符号分配“0”和“1”是任意的，所以可得到不同的码字。不同的码元分配，得到的具体码字不同，但码长Ki不变，平均码长也不变，所以没有本质区别。缩减信源时，若合并后的新符号概率与其他符号概率相等，从编码方法上来说，这几个符号的次序可任意排列，由此编出的码都是正确的，而得到的码字却不相同。不同的编码方法得到的码长Ki不尽相同。游程编码游程符号序列中某符号连续重复出现而形成符号串的长度，又称为游程长度或游长。游程编码将这种符号序列映射成游程长度和对应符号序列的位置的标志序列。如果知道了游程长度和对应符号序列的位置的标志序列，就可以完全恢复出原来的符号序列。游程编码二元序列的游程连续出现“0”，称为“0”游程，表示为L(0)。连续出现“1”，称为“1”游程，表示为L(1)。若规定二元序列总是从“0”开始，第一个游程是“0”游程，则第二个游程必为“1”游程，第三个又是“0”游程……对于随机序列，游程长度是随机的其取值可为1,2,3,…，直至无穷。用交替出现的“0”游程和“1”游程长度表示任意二元序列。一种一一对应的变换，是可逆变换。游程编码游程变换减弱了原序列符号间的相关性。游程变换将二元序列变换成了多元序列，这样就适合于用其他方法，如哈夫曼编码，进一步压缩信源，提高通信效率。首先测定“0”游程长度和“1”游程长度的概率分布，即以游程长度为元素，构造一个新的信源。对新的信源(游程序列)进行哈夫曼编码。游程编码多元序列游程多元序列也可以变换成游程序列，如m元序列可有m种游程。但是变换成游程序列时，需要增加标志位才能区分游程序列中的“长度”是m种游程中的哪一个的长度，否则，变换就不可逆。增加的标志位可能会抵消压缩编码得到的好处。所以，对多元序列进行游程变换的意义不大。算术编码算术编码是近十多年来发展迅速的一种无失真信源编码，它与最佳的哈夫曼码相比，理论性能稍加逊色，而实际压缩率和编码效率却往往还优于哈夫曼码，且实现简单，故很受工程上的重视。算术编码不同于哈夫曼码，它属于非分组码。它从全序列出发，考虑符号之间的关系来进行编码。算术编码利用了累积概率的概念。算术码主要的