信息论与编码总复习.doc

“信息论与编码”总复习*简要*第二章 信源与信息熵1每次只发出一个符号代表一个消息的信源叫做发出单个符号的无记忆信源。2由一系列符号组成，这种用每次发出1组含2个以上符号序列来代表一个信息的信源叫做发出符号序列的信源。3信源发出的序列的统计性质与时间的推移无关，是平稳的随机序列。4当信源的记忆长度为m+1时，该时刻发出的符号与前m个符号有关联性，而与更前面的符号无关，这种有记忆信源叫做m阶马尔可夫信源。若上述条件概率与时间起点无关，则信源输出的符号序列可看成齐次马尔可夫链，这样的信源叫做齐次马尔可夫信源。5例题：稳态分布概率|稳定后的符号概率分布：符号条件概率矩阵：状态转移概率矩阵令各稳态分布概率为W1,W2,W3,W4： 得稳态分布的概率：W1=3/35 W2=6/35 W3=6/35 W4=4/7稳定后的符号概率分布：6定义具有概率为的符号的自信息量为：7自信息量具有下列特性：（1）（2）（3）非负性（4）单调递减性（5）可加性8信源熵是在平均意义上来表征信源的总体特征，它是信源X的 函数，一般写成H（X）。9平均自信息量、平均不确定度、信源熵：10条件熵：11联合熵：12联合熵H(X,Y)与熵H(X)及条件熵H(Y|X)的关系：13.互信息:14.熵的性质：非负性，对称性，确定性，极值性。（1）非负性：（2）对称性：（3）确定性：（只要信源符号表中有一个符号出现概率为1，信源熵就等于零）（4）香农辅助定理：对于任意n维概率矢量 和，下列不等式成立：（5）最大熵定理：离散无记忆信源输出M个不同的信息符号，当且仅当各个符号出现概率相等时，熵最大。（6）条件熵小于无条件熵：条件熵小于信息熵，当且仅当 y和x相互独立时，取等号。15数据处理过程中会丢失一些信息，绝不会创造新信息，即所谓信息不增性。16无记忆平稳信源序列熵：17平均符号（信息）熵：第三章1.信道的分类根据用户数可以分为，单用户和多用户；根据输入端和输出端可以分为无反馈和反馈信道；根据信道参数与时间可以分为固定参数和时变参数；根据信道受噪声种类分为随机差错信道和突发差错信道根据输入输出信号的特点分为离散信道，连续信道，半离散半连续，波形信道2信道容量C=含义，表征信道能传输的最大信息量，或者信道的最大传输能力。3，DMC信道容量Clogm-H（Y|）=logm+log第四章1一般失真函数：，失真矩阵：2均方失真：=，绝对失真：=|，相对失真：=|/|，误码失真：=3.对于连续随机变量的平均失真；L长序列编码的为4，信息率失真函数：R（D）=minI（X，Y）；对于无记忆信源R（D）= 5.互信息的关系：I（X；Y）=H（Y）-H（Y|X）=H（X）-H（X|Y）6.R（D）的计算(1)当=，p（x）=，R（D）=log（2）当=|，P（x）=，R（D）=log（3）当=，p（x=0）=p，p（x=1）=1-p，R（D）=H（p）-H（D）第五章 信源编码1分组码:将信源消息分成若干组，即符号序列，序列中的每个符号取自符号集A，。而每个符号序列依照固定的码表映射一个码字，这样的码称为分组码，也叫快码。2码可以分为固定长度码和变长码； 分组码又分为奇异码和非奇异码；若信源符号和码字是一一对应的，该码为非奇异码，反之为奇异码。非奇异码又分为非唯一可译码和唯一可译码；任意有限长的码元序列，只能被唯一分割成一个个码字，称唯一可译码；注：奇异码不是唯一可译码，而非奇异码中有唯一可译码和非唯一可译码。唯一可译码又分为非即时码和即时码；接收端收到一个完整的码字后，不能立即译码，还需等下一个码字开始接受后才能判断是否可以译码，称为非即时码，即时码又称非延时码，任意一个码字都不是其他码字的前缀部分，叫异前缀码。3唯一可译码的充要条件：4定长编码定理：由L个符号组成的、每个符号的熵为的无记忆平稳信源符号序列（）,可用个符号(每个符号有m种可能值)进行定长编码。对任意,则当L足够大时，必可使译码差错小于；当时，译码差错一定是有限值。当L足够大时，译码几乎必定出错。5编码效率：,其中为平均符号熵。 最佳编码效率：6单个符号变长编码定理：若离散无记忆信源的符号熵为,每个信源符号用m进制码元进行变长编码，一定存在一种无失真编码方法，其码字平均长度满足下列不等式.7离散平稳无记忆序列变长编码定理：对于平均符号熵为的离散平稳无记忆信源，必存在一种无失真编码方法，使平均信息率满足不等式,式中为任意小正数。8平均输出信息率为。 9。码字平均长度：9码的剩余度为 10码字平均长度： 信源符号的平均码长：11费诺编码：平均码长，为码长； 信息传输速率：13.m进制的哈夫曼编码：m21)m进制的全树的终结点数=m+k(m-1),k=0,1,2)当nm+k(m-1),则必为非全树，令S= m+k(m-1)-n. 3)第一次取m-s个最小的概率进行合并得。4)以后的每次都取m个进行合并。哈夫曼码的方差：14在二元序列中，只有两种符号，即“0”和“1”这些符号可连续出现，连“0”的这段即为0的游程，如：000101110010001，可变换游程序列3113213。连着出现符号的游程，其长度就是“r”的游程长度。但是这种变换必须再加一些符号，才能成为一一对应或可逆的。15算术编码：为非分组码编码的基本思想：从全序列出发，将个信源序列的各概率映射到0,1区间上，使每个序列对应区间内的一点，即一个二进制小数。例：有4个符号a,b,c,d构成简单序列S=(a,b,d,a),各符号及其对应概率如表，算术编码过程如下；符号符号概率符号累计概率a0.100(1/2)0.000b0.010(1/4)0.100c0.001(1/8)0.110d0.001(1/8)0.111设起始状态为空序列，则A()=1，C()=0。递推得：因此C(a,b,d,a)即为编码后的码字010111。17.三进制哈夫曼编码例：解：六个字母的概率分别为0.32,0.22,0.18,0.16,0.08,0.04，则m=3，n=6，S=3+2（3-1）-6=1，得m-S=3-1=2第六章 信道编码1突发差错模型为双状态一阶马尔可夫链模型，或吉尔伯特模型或Gi模型。2纠错码分类：1）从功能角度，分为检错码和纠错码；2）从对信息序列的处理方法，分为分组码和卷积码；3）从码元与原始信息的关系，分为线性码和非线性码3差错控制系统分类：前向纠错，反馈重发，混合纠错。前向纠错优点：无需反向通道，时延小，实时性好，适用点对点和广播是通信。反馈重发：发送端发送检错码，如循环冗余校验码（CRC）,接收端通过检测接收码是否符合编码规律来判断该码是否存在差错。4.噪声均化的三种方法：增加码长N，卷积，交错51）基底不是唯一的，生成矩阵也就不是唯一的。 2）非系统码的生产矩阵可以通过运算转变为系统形式，此过程叫系统化。3）与任何一个（n,k）分组线性码的码空间C相对应，一定存在一个对偶空间D.4）空间的n-k个基底排列起来可构成一个（n-k）n矩阵，将这个矩阵称为码空间C的校验矩阵H.5）,k）线性码的任意码字c一定正交于其对偶码的任意一个码字，也必定正交于校验矩阵H的任意一个行矢量，即,0为零矩阵，若，则c为码字，反之，则不是码字。6）校验矩阵*详细*7随机事件的不确定度和它的自信息量之间的关系及区别？单符号离散信源的数学模型，自信息量、条件自信息量、联合自信息量的含义？信源符号不确定度：具有某种概率的信源符号在发出之前，存在不确定度，不确定度表征该符号的特性。符号的不确定度在数量上等于它的自信息量，两者的单位相同，但含义不同：不确定度是信源符号固有的，不管符号是否发出；自信息量是信源符号发出后给予收信者的；为了消除该符号的不确定度，接受者需要获得信息量。自信息量条件自信息量：联合自信息量：8信息量的性质？含义？分别从输入端、输出端和系统总体来理解互信息量的含义。自信息量指的是该符号出现后，提供给收信者的信息量。9. 各种熵（信源熵，条件熵，联合熵（共熵），等）的含义及其关系。信源熵：条件熵：疑义度： 噪声熵：联合熵：10. 信源熵的基本性质与定理及其理解？熵的性质对称性非负性确定性香农辅助定理最大熵定理条件熵小于无条件熵信源熵和平均自信息量两者在数值上是相等的，但含义并不同。信源熵表征信源的平均不确定度，平均自信息量是消除信源不确定度所需要的信息的量度。信源熵是在平均意义上来表征信源的总体特性，它是信源X的函数，而X是指随机变量的整体（包括概率空间）。信源给定，概率空间就给定，信源熵就是一个确定值。小结：信源熵H(X)的三种物理含义：表示信源输出后，每个离散消息所提供的平均信息量。表示信源输出前，信源的平均不确定度。反映了变量X的随机性。11. 平均互信息量的定义及物理意义？疑义度及噪声熵？12. 平均互信息量的性质及理解？13. 平均互信息量关于信源概率和信道转移概率的凸性定理。14. 最大离散熵定理及理解。 16. 数据处理定理及其含义。17. 信源的种类（详细分类）？各举出几个例子。按时间和幅度分类： 离散信源 单符号离散信源文字，数字，数据等 离散序列信源连续信源 连续幅度信源话音，图像，图形等 随机波形信源按符号之间的关系： 无记忆信源 发出单个符号的无记忆信源 发出符号序列的无记忆信源有记忆信源 发出符号序列的有记忆信源 发出符号序列的马尔可夫信源18. 离散平稳信源的定义，平均符号熵，极限熵的定义，含义与理解。信源所发符号序列的概率分布与时间的起点无关，这种信源我们称之为多符号离散平稳信源。19. 马尔可夫信源的定义，含义及其极限熵？当信源的记忆长度为m+1时，该时该发出的符号与前m个符号有关联性，而与更前面的符号无关。马尔可夫链极限熵： 为了使马尔可夫链最后达到稳定，成功之路遍历的马尔可夫链，还必须满足两个条件：平稳信源的概率分布特性具有时间推移不变性，而齐次马氏链只要求转移概率具有推移不变性，因此一般情况下平稳包含齐次，但齐次不包含平稳。20. 信源的冗余度的定义和含义？为什么有些信源有冗余度？冗余度的计算。冗余度，表示给定信源在实际发出消息时所包含的多余信息。它来自两个方面，一是信源符号间的相关性；二是信源符号分布的不均匀性.21. 连续信源的熵的定义？连续信源的不确定度应为无穷大，是相对熵，或叫差熵。在取两熵之间的差时才具有信息的所有特性。22. 几种特殊连续信源的熵。幅度连续的单个符号信源熵波形信源熵24. 信源输出值受限的最大连续熵定理。限峰功率最大熵定理：对于定义域为有限的随机变量X，当它是均匀分布时，具有最大熵。25. 信源输出的平均功率受限的最大连续熵定理。限平均功率最大熵定理：对于相关矩阵一定随机变量X，当它是正态分布时具有最大熵。Hc(X) = 1/2 ln()28. Shannon第一定理离散无失真信源编码定理（定长和变长）及含义？ 克劳夫特不等式只是用来说明唯一可译码是否存在，并不能作为唯一可译码的判据。29. 信道的数学模型和分类？30. 信息传输速率R的定义？信道转移概率、信道矩阵和信道容量C的定义？几种离散无噪信道的C？31. 强对称，对称，准对称信道的含义及其C？式中，m为信道输出符号集中符号的数目。强对称信道：或：32. 离散信道容量的一般计算方法及其步骤？33. 连续信道，连续信道的C的定义。连续单符号加性信道： 多维无记忆加性连续信道： 34. 香农公式的含义？ 由香农公式得到的值是其信道的下限值。35 Shannon第二定理（信道编码定理）及其含义？ 35. 对信源编码器有些什么基本要求？编码效率的定义？如何提高编码效率？ 36. 什么是最佳编码？说出Shannon、 Fano和Huffman编码的基本方法和主要特点。 37. 理解Huffman编码是最佳编码？ 38. 游程编码相关定义与步骤？ 39. 算术编码（非分组码）相关定义与步骤？ 40.简要说明下面几种译码准则：（1）最优译码准则；（2）最大似然译码准则 BSC信道的最大似然译码可以简化为信道的最大似然译码可以简化为最最小汉明距离译码小汉明距离译码。41.信源与信道达到匹配的含义以及如何实现？信道剩余度的概念及计算？42.失真函数、平均失真度的定义及其含义？失真