发布时间 : 星期二 文章09级信息论与编码复习材料更新完毕开始阅读
一、填空
1. 信息论基础主要研究信息的测度、 信道容量 、 信源和信道编码理论 等问题。 2. 必然事件的自信息量是0,不可能事件的自信息量是无穷大。 3. 若把掷骰子的结果作为一离散信源,则信源熵为
log26。
4. 当事件xi和yj彼此之间相互独立时,平均互信息量为 0 。
5. 若二维平稳信源的信源熵为3bit/sign,则其平均符号熵为1.5bit/sign 。 6. 信源熵H(X)表示信源输出后每个消息所提供的 平均信息量 。
7. 布袋中有红白球各50只,若从中随意取出一只球,则判断其颜色所需的信息量为 1bit 。 8. 单符号离散信源是用随机变量来描述的,则多符号离散信源用随机矢量来描述。 9. 平均互信息量与信息熵、联合熵的关系是I(X;Y)=H(X)+H(Y)-H(XY) 。 10. 条件熵H(x|y)和无条件熵H(X)的关系是小于等于。 11. 对于理想信道,H(x|y)等于0 ;I(x;y)= H(X)。
12. 若YZ统计独立,则H(YZ)和H(Y)、H(Z)之间的关系是H(YZ)=H(Y)+H(Z) 。 13. 对某含有7个消息的信源,其熵的最大值为log27,对应为等概分布分布。 14. 对某含有8个消息的信源,其熵的最大值为log28,对应为等概分布。 15. 对某含有6个消息的信源,其熵的最大值为log26,对应为等概分布。 16. 对某含有9个消息的信源,其熵的最大值为log29,对应为等概分布。 17. 十六进制脉冲所含的信息量是四进制脉冲的2 倍。 18. 八进制脉冲所含的信息量是二进制脉冲的3倍。 19. 十六进制脉冲所含的信息量是二进制脉冲的 4倍。
20. 离散平稳无记忆信源的N次扩展信源的熵等于离散信源熵的N 倍。 21. 离散信源的熵越小,则该信源消息之间的平均不确定性越弱。 22. 对于r进制树图,n级节点的个数一般为r。
23. 信道中任一时刻输出符号仅统计依赖于对应时刻的输入符号,而与非对应时刻的输入符号及其它任何时刻的输出符号无关,
这种信道称之为 有干扰无记忆信道 。
24. 对于某一信源和某一符号集来说,若有一个唯一可译码,其平均码长小于所有其它唯一可译码的平均码长,则称该码为紧致
码或最佳码 。
25. 分组码是前向纠错码 ,它可以在无需重新发射的情况下检测出有限个错码,并加以纠正。 26. 信源编码的目的是提高通信的有效性。
27. 对于香农编码和哈夫曼编码,编码方法唯一的是香农编码 。
28. 若纠错码的最小距离为dmin,则可以纠错任意小于等于(dmin-1)/2个差错。 29. 线性分组码是同时具有线性特性和分组特性的纠错码。
30. 道的输出仅与当前输入有关,而与过去无关的信道称无记忆信道。 31. 唯一可译码存在的充要条件是?m?ki?1。
i?1nn32. 编码分为信源编码和信道编码两种。
33. 信道无失真传输信息的条件是信息传输速率小于信道容量。
34. 对称信道中,信源的最佳分布为等概分布。
35. 信源编码和信道编码的最大区别在于信源编码需减少信源的冗余度,而信道编码需增加信源的冗余。
36. 信道编码的目的是提高通信的可靠性。
37. 离散信源分为离散无记忆信源 和 离散有记忆信源。
38. R(D)是D的下凸函数。
39. 码字10100001与码字01100000之间的距离是 3 。 40. 码字011111101、100111001之间的最汉明距离为5。 41. 码字101110101、100111001之间的最汉明距离为3。
42. 码字101111101、011111101、100111001之间的最小汉明距离为 2 。 43. 码字101010101、100111001之间的最汉明距离为4。 44. 码字101010101、100101001之间的最汉明距离为5。 45. 码字10100001与码字01100000之间的距离是 3 。 46. 将循环码0010111循环左移位1之后的码字10101110。 47. 将循环码0010111循环左移位2之后的码字1011100。 48. 将循环码0010111循环左移4位之后的码字1110010。
二、解释下列名词
自信息量:一个随机事件发生某一结果后所带来的信息量称为自信息量,简称自信息。I(ai)??log2p(ai)
互信息量:xi的后验概率与先验概率比值的对数,为yj 对xi的互信息量,也称为交互信息量(简称互信息),用I(xi;yj)表
示, 即:I(xi;yj)?logp(xi/yj)p(xi)
(i=1,2,……n;j=1,2,……m)
信道冗余度:设信道的信息传输速率为R=I(X,Y),信道容量为C,信道的剩余度定义为:信道冗余度=C-I(X,Y) 离散信源:发出在时间和幅度上都是离散分布的离散消息的信源。 如:文字、数字、数据、字母等。
离散无记忆序列信源:若信源输出的消息是取值离散的平稳随机序列,并且序列中各随机变量之间彼此统计独立,则此信源称为
离散无记忆序列信源.
无记忆离散信源:发出的各个符号是相互独立的;各符号序列中的各个符号之间是没有统计关联的关系。 各个符号的出现概率
是它自身的先验概率。无记忆离散信源包含发出单符号的无记忆离散信源和发出符号序列的无记忆离散信源。
有记忆离散信源:发出的各个符号是相关联的。表述起来很困难。有记忆离散信源又可分为发出符号序列的有记忆离散信源和发
出符号序列的马尔可夫信源。
冗余度: 它表示给定信源在实际发出消息时所包含的多余信息.(也称为多余度或剩余度).
实际熵; Hm(X)--信源最大熵。
线性分组码:同时具有分组特性和线性特性的纠错码。将输入的信息组编成长为n的码字,码字前k位为信息元,后r=n-k个码元
为校验元。若各校验元与前k个信息元之间是线性关系,则称这样的码为线性分组码。
唯一可译码:若码的任意一串有限长的码符号序列,只能被唯一的译成所对应的信源符号序列,则称为唯一可译码。
编码效率: 表示编码后实际信息量和能载荷最大信息量的比值。 假设码元为m进制,即可取m种可能值,则每个码元所能载荷的
H(x)R???KRmaxlogm 最大信息量为logm比特/码元。
??1?H?/Hm其中:H∞(X)--为信源
准对称信道:如果信道转移矩阵按列可以划分为几个互不相交的子集,每个子矩阵满足下列性质: (1)每行都是第一行的某种置
换; (2)每列都是第一列的某种置换。 称该信道为准对称信道。
信息率失真函数:选定信源和失真函数后,D?E[d(a,b)]可以看成条件概率p(b|a)的函数。设BD={P(b|a):D?D}满足保真度准
则的所有信道集合,这种信道称为失真度D允许信道(或试验信道)。 即时译码:非延长码或非续长码,任意一个码子都不是其它码字的前缀部分.
信道容量:互信息量I(X,Y)是输入符号X 概率分布的凸函数对于一个给定的信道,总是存在某种概率分布p(xi),使得传输每个
符号平均获得的信息量最大,即对于每个固定的信道总是存在一个最大的信息传输速率,这个最大信息传输速率定义为信道容量。
对称信道:若转移概率矩阵P每一行都是第一行的置转, 称矩阵是输入对称.若每一列都是第一列的置转,称矩阵是输出对称.若输
??
入输出都对称,称对称DMC信道。
汉明距离:长度为n的两个符号序列(码字)αi和βj之间的汉明距离为αi和βj对应位置上不同码元的个数, 汉明距离记为d(α
i,βj)
循环码:设c是线性分组码的任一码字,如果c经循环移位c=(c1,c 2,…,cn-1,cn)→c⑴=(c2,c3,…,cn-1cn,c1)后的序列仍然
是码字, 那么称该线性分组码为循环码。
无损压缩:长是利用数据的统计冗余进行压缩,可完全回复原始数据而不引起任何失真。 但压缩率是受到数据统计冗余度的理论
限制,一般为2:1到5:1。
有损压缩:经过压缩、解压的数据与原始数据不同,但是非常接近的压缩方法,又称破坏型压缩,即将次要的信息数据压缩掉,牺
牲一些质量来减少数据量,使压缩比提高。
输出对称信道:如果信道转移概率矩阵中所有列矢量都是第一列的某种置换,则称信道是关于输出对称离散信道。
有噪无损信道:信道输出符号Y集合的数量大于信道符号X集合的数量,即r<s,形成一对多的映射关.由于一对多的映射关系,不
能由输入完全确定信道的输出,H(X︱Y) >0,H(X)<H(Y),I(X;Y)=H(X).
C?max?I(X;Y)??max?H(x)??logr
p(x)p(x)码树:码树有一个树根A,树根有m个树枝,树枝的尽头称为节点,每个节点生出是树枝的数量等于码符号的数量m,从而形成m进
制的码树。
非即时译码:接收端收到一个完整的码字后,不能立即译码,而等下一码字开始接收后才判断是否可以码. 平均码长:编码后的每个信源符号平均所需的码元(码符号)个数。
K??P(xi)Ki
i?1q3.简答
简述信息、消息、信号及其区别。
答:信息是事物运动状态或存在方式的不确定性的描述。信息的基本概念在于它的不确定性,任何确定的事物都不会有信息。用文字、符号、数据、语言、音符、图片、图像等能够被人们感觉器官所感知的形式,把客观物质运动和主观思维活动的状态表达出来就成为消息。消息包含信息,是信息的载体,但不是物理性的。把消息换成适合信道传输的物理量(如电信号、光信号、声信号、生物信号等),这种物理量称为信号。信号是信息的载体,是物理性的。
信息量、联合自信息量和条件自信息量三者之间的关系。
信息是事物运动状态或存在方式的不确定性的描述。信息的基本概念在于它的不确定性,任何确定的事物都不会有信息。用文字、符号、数据、语言、音符、图片、图像等能够被人们感觉器官所感知的形式,把客观物质运动和主观思维活动的状态表达出来就成为消息。消息包含信息,是信息的载体,但不是物理性的。把消息换成适合信道传输的物理量(如电信号、光信号、声信号、生物信号等),这种物理量称为信号。信号是信息的载体,是物理性的。 简述信源熵物理含义。
(1)信息熵H(X)表示了信源输出前,信源的平均不确定性; (2)信息熵H(X)表示了信源输出后,每个消息或符号所提供的平均信息量; (3)信息熵H(X)反映了随机变量X的随机性。 描述最大离散熵定理的内容。
离散无记忆信源输出M个不同的信息符号,当且仅当各个符号出现概率相等时(即pi=1/M),熵最大。H(X)?H(简答描述单符号离散信源的数学模型。
单符号离散信源输出的消息是以一个符号的形式出现.信源每次只发出一个符号代表一个消息,可用离散随机变量来描述。 设X={ a1,a2 · · · an },这n个符号消息的概率分布是:p?{p(a1),p(a2),p(an)}
111,,..,)?logM MMM?X??a1?P???p(a)???1an?p(a2)......p(ai).....P(an)??0≤p(ai)≤1,?p(ai)?1
a2....ai...信源熵、条件熵、联合熵之间的关系。
H(XY)= H(X)+H(Y/X) H(XY)= H(Y)+H(X/Y)
条件熵小于无条件熵,H(Y/X)≤H(Y)。当且仅当y和x相互独立p(y/x)=p(y),H(Y/X)=H(Y)。
两个条件下的条件熵小于一个条件下的条件熵H(Z/X,Y)≤H(Z/Y) 当且仅当p(z/x,y)=p(z/y)时取等号。 简述香农第二定理的内容。
答:对任意一个离散无记忆平稳信道,设信道容量为C,则只要信息传输率R 道编码方案(n足够大),以小于ε的错误概率实现可靠通信。反之,R>C时不可能找到一种编码,使错误概率pe趋于零。 简述信源编码的实质。 是对信源的原始符号按一定的数学规则进行的一种变换,以码字代替原始信源符号,使变换后得到的码符号接近等概率分布,从而提高信息的传输有效性。 简述单个符号变长编码定理。 若一离散无记忆信源的符号熵为H(X),每个信源符号用m进制码元进行变长编码,一定存在一种无失真编码方法,其码字平均长 度 满足下列不等式 简单叙述香农编码的步骤。 编码步骤如下: (1)将信源发出的q个消息符号按其概率的递减次序依次排列:p1?p2?...?pq; (2)按下式计算第i个消息的二进制代码组的码长li,并取整; ?logp(si)?li??logp(si)?1 (3)为了编成唯一可译码,首先计算第i个消息的累加概率Pi?(4)将累加概率Pi(为小数)变换成二进制。 (5)去除小数点,并根据码长li,取小数点后li位数作为第i个信源符号的码字,由下式确定:li??logp(si)?1。 H(X)H(X)?K??1 logmlomg?p(s); kk?1i?1写出费诺编码步骤。 答:1. 将信源消息符号按其出现概率大小依次排列: p(x1)≥p(x2) …. p(xn)。2 .将依次排列的信源符号按概率植分两大组,并对各组赋予一个二进制元码0、1。3.将每一大组的信源符号进一步分组,使划分后的两组概率和近于相同并又赋两组0,1。4.如此重复,至两组只剩下一个信源符号为止。5.信源符号所对应的码字即为费诺码. 写出哈夫曼编码步骤。 (1) 将n个信源消息符号按其出现的概率大小依次排列,p(x1)≥p(x2)≥…≥p(xn) (2) 取两个概率最小的字母分别配以0和1两码元,并将这两个概率相加作为一个新字母的概率,与未分配的二进符号的字母重新排队。(3) 重复步骤(2)的过程,直到最后两个符号配以0和1为止; (4)从最后一级开始,向前返回得到各个信源符号所对应的码元序列。 描述克劳夫特不等式。 用码树的概念可以推导出唯一可译码存在的充要条件,即各码字的长度Ki应符合不等式?m?ki?1 m是进制数,n是信源符号数 i?1n称之为克劳夫特(Kraft)不等式 简单叙述无噪无损信道、无噪有损信道、有噪无损信道的信道容量。 无噪无损信道: ?H(X)??logr比特/符号 C?max?I(X;Y)??max1p(x)p(x)?r无噪有损信道: C?max?I(X;Y)??max?H(Y)??logs比特/符号 p(x)p(x)有噪无损信道: C?max?I(X;Y)??max?H(x)??logr(比特/符号) p(x)p(x) 简单叙述离散信道、连续信道、半连续半离散信道。 离散信道:又称数字信道,该类信道中输入空间、输出空间均为离散时间集合,集合中事件的数量是有限的,或者无限的,随机变量取值都是离散的。连续信道:又称为模拟信道,输入空间、输出空间均为连续事件集合,集合中事件的数量是无限的、不可数的,即随机变量的取