信息论与编码-锦囊.ppt

关于两个事件互相提供信息量的大小 ？ （1）直观看，两个事件在什么样的情况下给对方提供的信息量最 大。 （2）我们已经事先知道D国和美国经常唱反调，C国对美国态度保 持中立，英国和美国关系很好，那么美国和某国E发生战争：I、对 于英国在是否向某国E宣战，是否提供信息量？ II、对于C国是否向 某国E宣战，是否提供信息量？III、对于D国是否向某国E宣战，是 否提供信息量？哪个提供的信息量大？提供的信息量是否有正负 之分？ （3）经常骗人的骗子是否给你提供有效的信息？ （4）已知发送信号错误率太高，比如二进制每bit的错误率超过了 百分之五十，能否提供有效的信息？ （5）以下几类人说 “狼来了”给我们提供的信息量？我们已经事先 知道他是：A）诚实的人。B）经常故意骗人，说反话的人。C）故 意吓唬人，闭着眼睛随便乱说话的人，不管狼来不来都乱说。 信息压缩的极限（与信息度量） （1）假如对n个事件可以进行任意长度的编码，则编码的影响因素有哪 些？当希望编码长度尽量短的时候应该怎么办。 （2）假如要告知对方某种情况，而告知的情况只是n中情况之一，是否 可以采用约定的编号、暗号等进行通信，这个编号最小的取值范围是多 少？ （3）我们希望对消息进行编码，以求编码的平均长度最短，假如n种情 况中，某一情况发生的可能性极大，概率达到99.9999999%，对于各种 情况都采用相同长度的编码表示，是否存在浪费？ （4）一个山头上的人S意欲将信息发布给对方山头上的人R，双方通过 五色旗传递信息，双方可以事先约定什么颜色代表什么信号，进而对应 什么样的消息。双方通过多次举旗来传递信息，假如S只是想告诉R发生 了n中情况之一，怎么样可以让举起旗帜的次数最少，这个次数应该是 多少？这其中有哪些现实问题需要考虑？ （5）对上面问题进行简化，考虑事件可能结果为等概率的情况，最初 发生的概率均为p，则相应的可能结果数为多少？等概率事件是否应该 进行等长度编码？如果是，进而采用等长度的编码，则编码长度如何计 算？ 信息压缩的极限（与信息度量） （6）考虑事件可能结果不是等概率的情况，是否应该 进行等长度编码？如果不是，编码的长度与事件的概 率应该呈什么样的关系？ （7）我们希望编码长度尽量的短，如果要求编码可以 还原为唯一的事件，请问是否无限制缩短编码长度？ （8）如果不能无限缩短编码长度，编码的最短长度应 该受到什么样的制约？ （9）假如我们认为在一定的条件下可以编码的编码空 间为1，以所有的编码都不存在互相包含关系为例，即 不存在某个编码包含另外一个完整的编码，假设n进制 ，长度为L的编码会占用多少的编码空间？ 信息压缩的极限（与信息度量） （10）这种编码的占用编码空间特点是否可以类 推到非异前缀编码？ （11）考虑编码空间为1，则编码的各个码字长 度受到什么样的制约？ （12）考虑香农辅助定理，在以上制约的前提下 ，理论上的平均编码长度最短应该是多少？（香 农辅助定理：离散无记忆信源输出q个不同信息 符号，当且仅当各个符号出现的概率相等的时候 ，信息熵最大。）对于任意n维概率矢量 P=(p1,p2,pn)和Q=(q1,q2,qn)，下列不等式成立 ： 4. 限失真编码问题 （1）如何对失真进行度量？ （2）限失真编码的模型如何建立？以数字四舍 五入为范例，建立数学模型。 （3）是否可以通过转换将欲进行限失真压缩的 信源X转变为Y，然后利用这种对应关系进行编码 ？ （4）考虑对长序列的信源X转变为长序列Y会呈 现什么样的特征？ （5）考虑信源符号间的相关性是冗余度的成因 ，是否可以建立相关的方式（如函数）来表征这 种相关性，从而利于压缩？ 5. 信道编码问题 （1）假设信源概率分布未知，一般会如何权宜地处理？ （2）假设n进制系统错误率超过1/n，比如二进制编码的错误率超过0.5，是否可 以进行一定的纠错和检错？如果可以，如何进行？ （3） 监督码元和信息码元在什么统计关系下，监督码元对信息码元没有如何监 督效果？ （4）一般不能保证错误率完全等于0，但是可以让错误率减少，不能保证完全正 确地纠错的时候，这种情况下从概率统计的角度，纠错编码应该如何权宜地处理 ？ （5）假设错误率小于1/n，则每一个监督码元监督一位消息码元，是否存在浪费 ？ （6）我们分别考虑一个小家庭的自我救济和一个社会大家庭的内部调节的救济 ，问哪种救济更加有效。其中小家庭的救济就是一个家里内部积累一定的救济经 费，平时不用，供各种灾难和风险到来的时候自我救济。而大家庭的救济则是许 多人将同样比例的救济经费集中到一起，只有那些遇到灾难和风险的人才能使用 救济经费以克服当前灾难。大家庭越大（乃至于无穷大），救济的效果会有什么 趋向？大家庭的救济是否可以趋向于一个完全完美的救济，使得每一个人活着， 或者是说达到必要的基本生活水平，任何人发生风险都可以几乎按需领取相应的 救济费用。请问是否存在一种相应的救济极限（考虑家庭可以趋向于无穷大）。 5. 信道编码问题 （7）社会上的人可能犯罪，犯罪的人总是少数，少数警察也可能会被收买，当警察采 用一对一的监督的时候，犯罪的人总是少数，警察的监督能力是否能够得到充分利用？ 监督的代价是否比较大，监督的效果如何；考虑警察采用多对多的监督方式，警察可以 监督多人，一个人受到多个警察的监督，这样的情况下，对于警察被收买，监督无效是 否具有更好的效果？罪犯买通多个警察的可能性是否会降低？当监督者可能犯错误的时 候，采用什么样的方法进行监督才能最大限度纠正问题？ （8）纠错编码和社会救济、警察监督社会治安是否有相似之处？一个具体的收码发生 的错误的比例是随机的，并不一定对于一个码元发生错误的比例，但是一个具体的很长 的序列发生错误的符号的比例（误码率），是否随着序列长度的增加而以高概率趋向于 错误的概率。 （9）假设错误率小于1/n，是否可以认为某些错误比例很高的收码发生的概率是少数， 在进行一定的组合后，比如考虑一个很长的序列，是否使得这些发生超过一定误码率的 收码的概率任意小。 （10）考虑分组码，信源等概率分布的情形，当误码率可以得到很好控制在一定量的时 候，是否可能进行编码以使得即使发生错误（错误控制在一定量），也可以区分到底发 码是哪个？如何区分到底发码是哪一个？码距与信道的错误率存在什么样的关系时，在 序列长度足够大的时候，错误是可以纠正的？ （11）如何选择编码的码字，使得在有干扰信道通信的时候，即使发生错误，也可以最 有效区分发码是什么？ （12）将几个分组合并的时候，码距具有累加的性质，而相关的概率却是乘积的关系， 将相同的分组合并的时候，概率依分组个数而呈现幂的关系，码距则是乘积的关系，而 对数恰好可以将幂降级为乘，将乘降级为加。这对于我们有什么启示？ 6. 如何进行加密编码？ （1）什么是信息？密码学中有时候需要提供信息，有时候不希望 提供，怎么从信息论的角度实现？ （2）如何让监听者不确定，而接受者确定？ （3）将密码系统转换为加密 ，解密 这样的数学模型，从哪些角度 可以增加监听者的不确定性？ （4）监听者可以利用哪些因素来确定明文和密钥？ 根据信息论， 如何避免监听者获取关于明文和密钥的信息？ （5）对于密码系统的各种因素的制约、限制，或者这其中体现的 某些规律性，对于破译是有利还是有弊？ （6）当理论上可以确定时候，是否可以构造在实际、或者是计算 上不可确定明文（密钥）的密码体制，这种计算上不可确定应该 利用什么？ （7）给定一个单向的难题，比如 ，已知a，b求d很容易，而已知d ，a求b很难。你可试图怎么样的方式利用类似的难题来设计公钥 密码算法或其他密码算法。 7. 在编码、密码算法、密码协议中质数（ 或者互质）的身影无处不在，一个看起来 似乎毫无用处的质数，会有什么用途？ （1）质数的定义是不可分解的，请问这样的 数我们是否容易通过正面的证明得出一些定 理或结论？ （2）如果是不能，采用反证法应该利用什么 性质，反证法一般要有意识地推导出什么样 的矛盾？ （3）这种证明方式可能应用于哪些领域？ 8. 在编码中经常会遇到取模，分析其 用途和限制 （1）取模对于编码有什么优点？ （2）取模会给编码译码带来什