信息论与编码理论-全

信息论与编码理论

山东大学

信息科学与工程学院

第一章绪论通信系统模型信源编码器信道译码器信宿干扰源通信系统模型进一步细分信源信源编码器信道编码器调制器信道干扰源解调器信道译码器信源译码器信宿等效离散信道等效离散信源等效信宿信道编码器信道译码器各部件功能信源产生消息的源，消息可以是文字，语言，图像。可以离散，可以连续。随机发生。研究的主要问题是消息的统计特性和产生信息的速率编码器信源编码器：对信源输出进行变换，求得有效性信道编码器：对信源编码输出变换，提高抗干扰性调制器：将信道编码输出变成适合信道传输的方式各部件功能信道信号从发端传到手段的介质干扰源系统各部分引入的干扰，包括衰落，多径，码间干扰，非线性失真，加性噪声，主要是统计特性信道的中心问题是研究信道的统计特性和传信能力，即信道容量各部件功能译码器编码器的逆变换中心问题是研究各种可实现的解调和译码方法信宿信息的接收者信息、消息和信号信息一个抽象的概念，可以定量的描述。信息、物质和能量是构成一切系统的三大要素消息是信息的载体，相对具体的概念，如语言，文字，数字，图像信号表示消息的物理量，电信号的幅度，频率，相位等等1.2信息论研究的中心问题和发展Shannon信息论的基本任务1948年shannon发表了“通信的数学理论”奠定了信息论理论基础基本任务是设计有效而可靠的通信系统可靠是要使信源发出的消息经过传输后，尽可能准确地、不失真地再现在接收端有效是用尽可能短的时间和尽可能少的设备来传输一定量的消息信息论的研究内容狭义信息论（经典信息论）研究信息测度，信道容量以及信源和信道编码理论一般信息论研究信息传输和处理问题，除经典信息论外还包括噪声理论，信号滤波和预测，统计检测和估值理论，调制理论，信息处理理论和保密理论广义信息论除上述内容外，还包括自然和社会领域有关信息的内容，如模式识别，计算机翻译，心理学，遗传学，神经生理学狭义信息论体系结构Shannon信息论压缩理论有失真编码无失真编码等长编码定理Shannon1948McMillan1953变长编码定理Shannon1948McMillan1956Huffman码(1952)、Fano码算术码(1976,1982)LZ码(1977,1978)率失真理论ShannonGallagerBerger压缩编码JPEGMPEG传输理论信道编码定理网络信息理论纠错码编码调制理论网络最佳码信息论发展简史电磁理论和电子学理论对通信理论技术发展起重要的促进作用1820－1830年，法拉第发现电磁感应莫尔斯1832－1835建立电报系统。1876年Bell发明电话1864麦克斯韦预言电磁波存在，1888年赫兹验证该理论1895年马可尼发明了无线电通信微波电子管导致微波通信系统，微波雷达系统激光技术使通信进入光通信时代量子力学使通信进入量子通信领域信息论发展简史1832年莫尔斯电码对shannon编码理论的启发1885年凯尔文研究了一条电缆的极限传信速率1922年卡逊对调幅信号的频谱结构进行研究1924年奈奎斯特证明了信号传输速率和带宽成正比1928年Hartley提出信息量定义为可能消息量的对数1939年Dudley发明声码器1940维纳将随机过程和数理统计引入通信与控制系统信息论发展简史1948年shannon信息论奠基1952年Fano证明了Fano不等式，给出了shannon信道编码逆定理的证明1957，Wolfowitz，1961Fano，1968Gallager给出信道编码定理的简介证明并描述了码率，码长和错误概率的关系，1972年Arimoto和Blahut发明了信道容量的迭代算法1956McMillan证明了Kraft不等式。1952年Fano码，Huffman码。1976Rissanen算术编码，1977，78Ziv和Lempel的LZ算法信息论发展简史1950年汉明码，1960年卷积码的概率译码，Viterbi译码，1982年Ungerboeck编码调制技术，1993年Turbo编译码技术，1999年LDPC编码技术。1959年，Shannon提出率失真函数和率失真信源编码定理1961年，Shannon的“双路通信信道”开拓了网络信息论的研究，目前是非常活跃的研究领域。信息的概念第一个重要概念：信道上传送的是随机变量的值。注意：（1）这就是说，我们在收到消息之前，并不知道消息的内容。否则消息是没有必要发送的。（2）消息随机变量有一个概率分布。（3）消息随机变量的一个可能取值就称为一个事件。信息的概念第二个重要概念：事件发生的概率越小，此事件含有的信息量就越大。（不太可能发生的事件竟然发生了，令人震惊）例事件“中国足球队3：0力克韩国足球队”含有的信息量大。（小概率事件发生了，事件信息量大）例事件“中国足球队0：1负于韩国足球队”含有的信息量小。（大概率事件发生了，事件信息量小）信息的概念

第三个重要概念：消息随机变量的随机性越大，此消息随机变量含有的信息量就越大。例消息随机变量X=“中国足球队与韩国足球队比赛的结果”，则消息随机变量X含有的信息量小。（随机性小，可预见性大，因此该消息随机变量含有的信息量小。）例消息随机变量X=“意大利足球队与德国足球队比赛的结果”，则消息随机变量X含有的信息量大。（随机性大，可预见性小，因此该消息随机变量含有的信息量大。）信息的概念第四个重要概念：两个消息随机变量的相互依赖性越大，它们的互信息量就越大（这里指的是绝对值大）。例X=西安明日平均气温,Y=咸阳明日平均气温，Z=北京明日平均气温，W=纽约明日平均气温。则X与Y互信息量大，X与Z互信息量小得多，X与W互信息量几乎为0。第二章信息量和熵信息量和熵2.1离散变量的非平均信息量2.2离散集的平均自信息量－熵2.3离散集的平均互信息量2.4连续随机变量的互信息和熵2.5凸函数和互信息的凸性2.1离散变量的非平均信息量输入，输出空间定义输入空间X={xk,k=1,2,…,K},概率记为q(xk)输出空间Y={yj,j=1,2,…,J},概率记为ω(yj)联合空间XY={xkyj;k=1,2,…,K;j=1,2,…,J},概率为p(xkyj)

p(xkyj)=p(xk|yj)ω(yj)=p(yj|xk)q(xk)非平均互信息量例2.1.1输入消息码字p(xk)收到0收到01收到011X1X2X3X4X5X6X7x80000010100111001011101111/81/81/81/81/81/81/81/81/41/41/41/40000001/21/2000000010000非平均互信息量输入消息码字p(xk)收到0收到01收到011X1X2X3X4X5X6X7x80000010100111001011101111/81/41/81/41/161/161/161/161/61/31/61/30000001/32/3000000010000非平均互信息量例2.1.2输入消息码字p(xk)收到0收到01收到011X1X20001111/21/21-pp1/21/21-pp1-p1-p0011pp非平均互信息量条件互信息和联合事件互信息三个事件集的条件互信息定义为可以推广到任意有限多个空间情况互信息的可加性系统u1u2u3系统u1u2u3离散变量的非平均自信息量非平均自信息的性质非负体现先验不确定性大小条件自信息和联合自信息自信息、条件自信息和互信息I(xk)I(yj)I(xk;yj)2.2离散集的平均自信息量－熵熵集X中事件出现的平均不确定性例2.2.1H(p)例2.2.2条件熵和联合熵XY独立时有H(X|Y)=H(X)熵的性质对称性非负性确定性扩展性可加性极值性是H(P)上凸函数熵的性质－可加性H(p1q11,p1q12,…,p4q44)=H(p1…,p4)+p1H(q11,…,q14)+…+p4H(q41,…,q44)p1p2p3p4q11q12q13q14熵的极值性引理1:lnx≤x-1熵的极值性引理2：H(X|Y)≤H(X)H(U1…UN)≤H(U1)+…+H(UN)熵的凸性H(P)是P的上凸函数2.3离散集的平均互信息量平均互信息量非负性对称性

平均互信息量4.I(X;Y)≤H(X),I(X;Y)≤H(Y)H(X)H(Y)I(X;Y)H(Y|X)H(X|Y)条件互信息信息处理定理Z出现情况下，X和Y独立,构成一个马氏链系统1系统2XYZ信息处理定理2.4连续随机变量的互信息和相对熵连续随机变量的互信息例:求互信息例:求互信息

随机变量的相对熵(微分熵)均匀分布的相对熵高斯分布的相对熵熵功率相对熵的极大化1.峰值功率受限均匀分布相对熵最大2.平均功率受限高斯分布相对熵最大3.平均功率大于等于熵功率2.5凸函数与互信息的凸性凸函数凸集R：a，b属于R，qa+(1-q)b也属于R，其中0≤q≤1概率矢量矢量a的所有分量和为1上凸函数凸函数的性质f(a)是上凸的，－f(a)是下凸的f1(a),…,fL(a)是R上的上凸函数，c1,…,cL是正数，c1f1(a)+…+cLfL(a)也是上凸函数f(a)是上凸函数，E[f(a)]≤f[E(a)],E为求数学期望K-T条件f(a)是定义域R上的上凸函数，a是概率矢量。偏导数存在且连续，f(a)在R上为极大的充分必要条件互信息的凸性p(y|x)给定，I(X;Y)是q(x)的上凸函数Q(x)给定，I(X;Y)是p(y|x)的下凸函数互信息的凸性q1和q2是X上的任意两个概率矢量，相应的互信息为I1和I2，令θ满足0<θ<1。q=θq1＋(1－θ)q2是合成概率矢量，此时输入X和输出Y之间的互信息为I。需要证明第三章信源编码（一）离散信源无失真编码3.1信源及其分类3.2离散无记忆信源的等长编码3.3离散无记忆信源的不等长编码3.4最佳不等长编码无失真编码限失真编码3.1信源及其分类信源及其分类离散信源连续信源无记忆信源有记忆信源简单信源－独立同分布平稳信源，各态历经源M阶记忆源时间离散连续源随机波形源3.2离散无记忆源的等长编码离散无记忆源字母表A={a1,…,aK},概率p1,…,pK,长为L的源输出序列uL={u1,…,uL}，共有KL种序列码符号字母表B={b1,…,bD},以码符号表示源输出序列，D元码等长D元码，不等长D元码单义可译码，每个消息都至少有一个码字与之对应。单义可译码存在充要条件DN≥KLN≥LlogK/logDDMS的等长编码NlogD≥LH(U)H(U)是统计平均值，L达到无限时，一个具体的源输出序列的平均每符号的信息量才等于H(U)选L足够长，使NlogD≥L[H(U)+eL]弱、强e典型序列集信源划分定理编码速率和等长编码定理R=(1/L)logM=(N/L)logD,M为码字总数对于给定信源和编码速率R以及任意e>0，若有L0,以及编译码方法，使得L>L0,错误概率小于e，R是可达的等长编码定理R>H(U),R是可达的，R<H(U)是不可达的编码效率h=H(U)/R

3.3DMS的不等长编码平均码长几个定义唯一可译码逗点码，无逗点码字头或前缀异字头码或异前缀码树码，满树，非满树，全树树码构造异字头码例子信源字母集概率码A码B码C码Da1a2a3a40.50.250.1250.125001100100110101101110010110111Shannon－Fano编码D元码每次信源符号化为概率近似相等的D个子集这样可以保证D个码元近似等概，每个码字承载的信息量近似最大，码就近似最短。理想情况I(ak)=nklogD,p(ak)=D-nkKraft不等式不等长编码定理3.4最佳不等长编码两个定理1.对于给定信源，存在最佳唯一二元可译码，最小概率的两个码字码长相等且最长，他们之间仅最后一位不同2.对辅助集为最佳的码，对原始集也是最佳的Huffman编码例(0.20,0.19,0.18,0.17,0.15,0.10,0.01)D元Huffman编码共有K个符号，概率最小的R个符号码长最长K+B=D+m(D-1)注意B<D-1K-2=m(D-1)+D-2-BB个R个B=D-2-((K-2)mod(D-1))R=2+((K-2)mod(D-1))Shannon-Fano-Elias编码累计分布函数修正累计分布函数Shannon-Fano-Elias编码采用的数值作为ak的码字码长Shannon-Fano-Elias编码Shannon-Fano-Elias编码信源符号P(ak)F(ak)修正值二进制码长码字a10.250.250.1250.0013001a20.50.750.50.10210a30.1250.8750.81250.110141101a40.1251.00.93750.111141111算术码算术码信源序列(u1u2…un)的累计分布算术编码是计算序列的累计分布，用累计分布值表示序列，所以称为算术编码以二元信源输出序列的编码为例01110P(0)P(1)F(0)F(1)01算术码P(00)P(01)F(0)F(01)F(1)P(010)P(011)F(011)P(0110)P(0111)F(0111)P(01110)P(01111)F(01111)算术码信源符号序列u对应区间的宽度等于符号序列的概率算术编码F(u)将[0,1)分割成许多小区间，取小区间内的一个点代表该序列，以该点数值的二进制小数表示该序列，码字长度为算术编码例：P(0)=0.25,P(1)=0.75,u=11111100P(u=11111100)=0.7560.252L=7F(s)=0.110100100111C=1101010编码效率92.7%LZ编码利用字典编码方法信源符号A=(a1…aK)将序列分为不同的段取最短长度的连续符号构成段，保证互不相同。先取一个符号分段，若与前面段相同，就再取一个符号，直至序列结束得到字典表，码字由段号加后一个符号组成。单符号的码字，段号为0LZ编码符号码字a0a1a2a300011011LZ编码000000011000011000011000000100011101234567LZ编码设长为L的信源序列u分为M(u)个码段，每段短语的二元码符号长度为总码长平均+LZ编码设长度为l段有Kl种。若把长为L的信源序列u分为M(u)个码段后，设最长的段长为lmax，而且所有小于等于lmax

的段型全部都有，则LZ编码典型段，ak出现的次数为lmaxp(ak)LZ编码设较短的段型忽略不计第四章信道及其容量信道及其容量4.1信道分类4.2离散无记忆信道4.3信道的组合4.4时间离散的无记忆信道4.5波形信道4.1信道分类4.1信道分类离散信道：输入输出均为离散事件集连续信道：输入输出空间均为连续事件集半连续信道：输入和输出一个是离散的，一个是连续的时间离散的连续信道：信道输入和输出是连续的时间序列波形信道：输入和输出都是时间的实函数x(t),y(t)4.1信道分类两端信道多端信道恒参信道：参数不随时间变化随参信道：参数随时间变化无记忆信道和有记忆信道对称信道和非对称信道4.2离散无记忆信道离散无记忆信道平稳信道例：二元对称信道p=0.11-p1-ppp1100信道容量定理4.2.1定理4.2.2Q={Q0,Q1,…,QK-1}达到信道容量的充要条件

对称DMC容量的计算若信道转移概率矩阵所有行矢量都是第一行的置换，称为关于输入对称。对称DMC容量的计算P的所有列都是第一列的一种置换，关于输出是对称的当输入事件等概，Qk=1/K对称DMC的容量计算输出集Y可划为若干和子集,每个子集对应的信道转移概率矩阵P中列所组成的子阵具有下列性质每一行都是第一行的置换每一列都是第一列的置换该信道称为准对称信道关于输入对称Y的划分只有一个时，关于输入和输出均对称，称为对称信道（例）对称DMC容量的计算定理4.2.3实现准对称DMC信道容量的输入分布为等概分布YS：子阵中每一列都是第一列置换对每个j相同对每个k相同对称DMC容量计算K元对称信道二元对称信道C=1-H(p)准对称信道离散无记忆模K加性噪声信道Z=X=Y={0,1,…,K-1}y=x+zmodK一般DMC的容量计算信道转移矩阵时非奇异方阵，假定所有Qk>0一般DMC的容量计算4.3信道的组合积信道C1＝maxI(X1,Y1)C2＝maxI(X2,Y2)信道1和信道2同时传递消息，输入集X=X1×X2,输出集Y=Y1×Y2,转移概率p(jj’|kk’)=p(j|k)p(j’|k’)C=C1+C2信道1P(j|k)X1Y1信道2P(j‘|k’)X2Y2证明和信道单位时间内可随机选用信道1和信道2中的一个，选用信道1的概率为p1，选用信道2的概率为p2，p1＋p2＝1输入空间X=X1+X2，Y=Y1+Y2，级联信道信道1的输出作为信道2的输入4.4时间离散的无记忆连续信道可加噪声信道P(y|x)=p(y-x)=p(z)可加噪声信道高斯噪声信道平均功率受限的可加噪声信道平均功率受限的时间离散、恒参、可加高斯噪声信道容量最佳分布是均值为0，方差为S的高斯型分布平均功率受限时间离散恒参可加噪声信道容量给定信号功率，高斯信道是最差的信道平行可加高斯噪声信道X=(x1,…,xN),y=(y1,…,yN)4.5波形信道可加波形信道Y(t)=x(t)+z(t)可加波形信道可加波形信道可加波形信道Shannon公式N=2WTW趋于无穷大，单位时间的信道容量Shannon极限-1.59dB第五章信道编码定理1.离散信道编码问题2.信道译码3.Fano不等式和信道编码逆定理1.离散信道编码问题纠错编码器送给纠错编码器的消息是经过最佳信源编码后，信息速率为比特/秒的离散二元或q元数字序列。分组码

每K个信息数字为一组，计算出N个编码数字，称这些数字为一个码字。通常N为整数。卷积码输出的n0长码段不仅依赖于当前的k0位信息数字，还依赖于前m个信息段的信息数字，即总共与（m＋1）k0个信息数字有关。纠错编码器R＝K/N，码率误组率误比特率2.信道译码问题译码错误概率译码准则最小错误概率译码：使pe(y)最小最大后验概率译码：最大似然译码所有Q(m)相同最大对数似然译码最小汉明距离译码汉明距离

d(x,y),x,y中分量不同的数目码字先验等概K元对称信道最小汉明距离译码判决区域Ym:lnp(y|xm)>lnp(y|xm’)给定m,错误概率高斯信道Fano不等式和信道编码逆定理Fano不等式信道编码逆定理离散平稳源有M个字母熵为HL(U),信道容量为C,当HL(U)>(N/L)C时,误码率为非零值信道编码定理R<C时，R是可达的，即对信息速率R,任意给定的e>0，存在编译码方法，当N足够大，p<e第七章信道编码线性分组码信息位，信息空间码字，码空间分组码：n维线性空间中的k维子空间参数（n,k,d），n是码长，k是信息位长度，d是最小汉明距离汉明重量：向量x中非零分量的数目最小距离：所有码字中最小非零重量GF（2）上的向量GF(2)包含0,1定义了两个运算加法：0＋0＝0，0＋1＝1＋0＝1，1＋1＝0乘法：0×0＝0，0×1＝0，1×0＝0，1×1＝1d(x,y)=w(x+y)生成矩阵K维子空间的基底C=u0g0+u1g1+…+uk-1gk-1(7,4)汉明码消息序列码字消息序列码字00000001001000110100010101100111000000010100011110010010001101101001100101100011000101111000100110101011110011011110111111010000111001001101010010110101100000110101011101111111系统码校验位信息位生成矩阵校验矩阵C的对偶空间Vcv=0V的生成矩阵H是G的校验矩阵V的维数是N-K校验矩阵生成矩阵和校验矩阵的关系错误图样错误图样伴随式伴随式和错误的关系s≠0,有错误出现S=0e＝0，没有错误e=ci,不可检错误不可检错误概率重量分布矢量Ai码中重量为i的码字数目陪集将2N个可能的向量分为2N-k个集合集合中每个向量的伴随式相同这样的集合称为陪集选择陪集中重量最轻的向量作为陪集代表，称为陪集首。标准阵伴随式陪集首陪集正确译码概率第l个陪集首的重量重量为i的陪集首的数量(6,3)码的标准阵陪集首伴随式译码步骤