信息论基础第24次课-总复习

信息论基础

——总复习第2章信源熵自信息量：

I(ai)=-logp(ai)信源熵：信源的平均信息量条件熵：损失熵噪声熵联合熵：平均互信息：第2章信源熵最大离散熵定理：若信源中包含n个不同离散消息，则当信源等概率时信源熵H(X)取得最大值log2n平均互信息I(X;Y)是输入信源概率分布的上凸函数是信道转移概率分布

的下凸函数。第2章信源熵多符号离散平稳无记忆信源亦称为单符号离散平稳无记忆信源的扩展信源。N维离散平稳信源平均符号熵：第2章信源熵马尔可夫信源：m阶马尔可夫信源：第2章信源熵各态历经定理由状态转移图可求状态极限概率定长编码定理定长编码定理：一个熵为H(X)的离散无记忆信源X1X2…Xl…XL

，若对信源长为L的符号序列进行定长编码，设码字是从m个字母的码符号集合中，选取K个码元组成Y1Y2…Yk…YK

。对于任意ε>0，δ>0只要满足则当L足够大时，必可使译码差错小于δ，即译码错误概率能为任意小。反之，若则译码差错一定是有限值，而当L足够大时，译码几乎肯定出错（译码错误概率近似等于1）。

对离散无记忆信源，符号熵为H(X)，对信源进行m元变长编码，一定存在无失真的信源编码方法，满足：其码字平均长度K(2.4.5)(2.4.6)变长编码定理其码字平均信息率R满足：本章考点1.各种熵的计算。如：P69.2.11;2.一阶马尔可夫信源的状态极限概率及极限熵。如：P69.2.16,2.173.各种熵的性质：信源熵：非负性、最大离散熵定理、上凸性、确定性。平均互信息：非负性、极值性、凸函数性、数据处理定理、各种熵之间的关系（和差关系、大小关系）连续信源熵：可为负、平均互信息非负。4.P68.2.8、2.14.5.离散无失真信源编码定理。第3章信道容量当信道特性p(bj/ai)固定后，I(X;Y)随信源概率分布p(ai)的变化而变化。调整p(ai)，在接收端就能获得不同的信息量。由平均互信息的性质已知，I(X;Y)是p(ai)的上凸函数，因此总能找到一种概率分布p(ai)（即某一种信源），使信道所能传送的信息率为最大。信道容量C：在信道中最大的信息传输速率，单位是比特/信道符号。具有扩展功能的有噪无损信道具有归并性能的有损无噪信道第3章信道容量如果一个信道矩阵具有可排列性，则它所表示的信道称为对称信道若信道矩阵P的行是可排列的，但列不可排列，如果把列分成若干个不相交的子集，且由n行和各子集的诸列构成的各个子矩阵都是可排列的，则称相应的信道为准对称信道。第3章信道容量例：信道输入符号集X={x1,x2}，输出符号集Y={y1,y2,y3,y4}，给定信道转移概率矩阵，

求该信道的信道容量C。解：这是一个准对称信道，当X等概分布，即p(x1)=p(x2)=1/2时，达到信道容量而此时，信宿端概率为连续信道的信道容量C：信源X等于某一概率密度函数p0(x)时，信道平均互信息的最大值，即对于高斯加性信道第3章信道容量信噪功率比香农公式设信道的频带限于(0,W)；根据采样定理，如果每秒传送2W个采样点，在接收端可无失真地恢复出原始信号；香农公式：把信道的一次传输看成是一次采样，由于信道每秒传输2W个样点，所以单位时间的信道容量为(bit/s)信道编码定理信道编码定理：若一离散平稳无记忆信道，其容量为C，输入序列长度为L，只要待传送的信息率R<C，总能找到一种编码。当L足够长时，译码差错概率为任意正数，反之，当R>C,任何编码的必大于0，当本章考点1.几种特殊信道的信道容量。2.准对称离散信道的信道容量。P99.3.7(4)3.高斯加性信道的信道容量，香农公式。4.信道编码定理。第4章信息率失真函数信道的传递概率矩阵失真矩阵第4章信息率失真函数汉明失真：平均失真度（2）信息率失真函数R(D)

在信源给定以后，总希望在允许一定失真的情况下，传送信源所必须的信息率越小越好。从接收端来看，就是在满足保真度准则的条件下，寻找再现信源消息必须的最低平均信息量，即平均互信息的最小值。当p(ai)一定时，互信息I是关于p(bj/ai)的下凸函数，存在极小值。因而在上述允许信道PD中，可以寻找一种信道，使给定的信源经过此信道传输后，互信息I(X；Y)达到最小。该最小的互信息就称为信息率失真函数R(D)，即

率失真函数的定义域信源最小平均失真度Dmin：对于每一个ai，找出一个bj与之对应，使d(ai,bj)最小，这相当于在失真矩阵的每一行找出一个最小的d(ai,bj)

。只有当失真矩阵的每一行至少有一个0元素时，信源的平均失真度才能达到下限值0。计算Dmax的值令试验信道特性p(bj/ai)=p(bj)(i=1,2,…,n)这时X和Y相互独立，等效于通信中断，因此I(X;Y)=0，即R(D)=0。满足上式的试验信道有许多，相应地可求出许多平均失真值，这类平均失真值的下界，就是Dmax。这里令当R(D)等于0时，对应的平均失真最大，也就是函数R(D)定义域的上界值Dmax。当D>Dmax时，从数学意义上讲，因为R(D)是非负函数，所以它仍只能等于0。率失真函数的性质连续性下凸性非负性单调递减本章考点1.信息率失真函数的含义。2.信息率失真函数的定义域。对应到最大失真度和最小失真度的信道矩阵。P129.4.1、4.2、4.103.信息率失真函数的性质：下凸性、连续性、非负性、单调递减。4.保真度准则下的信源编码定理。第5章信源编码异前置码的充要条件：Craft不等式在Huffman编码过程中，对缩减信源符号按概率由大到小的顺序重新排列时，应使合并后的新符号尽可能排在靠前的位置，这样可使合并后的新符号重复编码次数减少，使码方差最小。输入数据流：编码过程：114A1225B2336B2447A4568A7693(最后字符C)BBABABACLZW算法举例A律特性式中：x为归一化信号值，当x≥0时函数取正，否则取负，一般取A=87.6。为实现方便，大多采用13折线来逼近A律特性。非均匀量化1f(x)7/86/85/84/83/82/81/8011/21/41/8xx划分为8个不均匀的段落：其中第8段占量化范围的1/2，除第1段外，其余各段的宽度均按1/2倍率减小，即第7段占1/4，第6段占1/8，…，第2段占1/128；第1段也占1/128。0~1量化范围的13折线A律特性：这样，0~1量化范围内共划分出了8*16个不均匀的量化间隔；如果将最小的量化间隔记为Δ，则Δ=1/(128*16)，相应最大的量化间隔为64Δ=1/32。13折线A律非均匀量化编码也采用定长折叠二进制码，并将码长确定为8位；其8位码元安排如下：最高位C7为极性码，用以表示信号极性，其准则与均匀量化相同；以下三位C6C5C4为段落码，用以表示|x|落在正方向的第几个段落；最后四位C3C2C1

C0为段内码，用以表示|x|在段内落在第几个量化间隔。

每段再均匀地分为16份，每一份作为一个量化间隔。

采用13折线A律非均匀量化编码，设最小量化间隔为Δ，已知某采样时刻的信号值为x=635Δ，试求其非均匀量化编码c，并求量化噪声e

。解：①635Δ>0，故极性码为1。②因为512Δ≤635Δ≤1024，所以635Δ在第7个段落，段落码为110；③由于(1024-512)/16=32，所以该段落内每个量化间隔为32Δ，635Δ-512Δ=123Δ最接近32Δ的4倍，所以段内码为0100。故13折线A律非均匀量化编码为c=11100100。

量化噪声为e=|123Δ-128Δ|=5Δ一、增量调制

增量调制是预测编码中最简单的一种，增量调制原理如下，其中(a)为发送端，(b)为接收端。1比特量化+-

编码++

译码(a)(b)【例5.3.1】已知某归一化信号序列，设初始量化dq0=0

，量化增量Δ=0.125，求其增量调制编码和量化值。

的编码；

的量化值。差分脉冲编码调制原理如下，+预测+

译码(a)(b)量化+++-

编码预测二、差分脉冲编码调制

其中(a)为发送端，(b)为接收端。【例5.3.2】已知某归一化信号序列x1,x2,x3,x4=0.05,0.15,0.23,0.2，设初始值dq0=0，，采用码长为4的均匀量化，量化间隔Δ=0.03125，求其差分脉冲编码调制的编码和量化信号值。DPCM的编码

DPCM的量化信号值无损编码香农编码、Huffman编码、费诺编码、算术编码、字典编码、L-D编码、行程编码……有损编码均匀量化、非均匀量化、矢量量化、增量调制、差分脉冲编码调制、变换编码……本章考点1.异前置码存在的充要条件：克拉夫特不等式。2.LZW编码。见课件3.13折线A律特性非均匀编码。P168.5.124.增量调制、差分脉冲编码调制。见课件5.哪些是无损编码、有损编码。第6章信道编码检纠错能力和最小码距的关系若要能检测l个随机错误，则要求dmin≥l+1若要纠正t个随机错误，则要求dmin≥2t+1若要纠正t个，同时检测l(l>t)个随机错误，则要求dmin≥l+t+1。此处“同时”是指能检测t+l个错误，其中t个错误可以纠正。(n,k)线性分组码：c=mG线性分组码有如下性质：（1）零向量θ=(0,0,…,0)一定是一个码字；（2）任意两码字的和仍是一个码字；（3）任意码字c是生成矩阵

G的行向量g0,g1,…,gk-1的线性组合；（4）线性分组码的最小距离等于最小非零码字重量。定理

线性分组码的最小码距为d，当且仅当其一致校验矩阵H中任意d-1列线性无关，某d列线性相关。线性分组码系统码：生成矩阵G具有如下形式G=Gs=[Ik

Qk×r]即消息比特在码字中的位置和取值不变在码字集合不变的情况下，任何一个线性分组码都可以一对一的去对应一个系统码。对于系统码，易求相应的一致校验矩阵注意，G与Hs仍然满足线性分组码的译码设一致校验矩阵为H，对正确的码字c，应有cHT=0，若接收到的码字有错，即r=c+e，则伴随式s=rHT=(c+e)HT=eHT。事先对最有可能出现的差错图案e，求s=eHT，建立e和s的对应关系表，译码时对接收到的码字r，求s=rHT，按es关系表查出对应的错误，纠错计算得c=r+e。如：es关系表对某接收序列r=(1100100)

计算对应的e为（0001000）

纠错译码输出为循环码：一个线性分组码的任意一个码字c(n元组)都是另外一个码字c’的循环移位.定理1：

(n,k)循环码C(x