下载文档原格式
信息论与编码答案傅祖芸【篇一：信息论与编码课程设计报告】t>设计题目：统计信源熵与香农编码专业班级学号学生姓名指导教师教师评分2014年3月24日目录一、设计任务与要求................................................. 2 二、设计思路....................................................... 2 三、设计流程图..................................................... 3 四、程序运行及结果................................................. 5 五、心得体会....................................................... 6 参考文献 .......................................................... 6 附录：源程序.. (7)一、设计任务与要求1、统计信源熵要求：统计任意文本文件中各字符（不区分大小写）数量，计算字符概率，并计算信源熵。
2、香农编码要求：任意输入消息概率，利用香农编码方法进行编码，并计算信源熵和编码效率。
二、设计思路1、统计信源熵：统计信源熵就是对一篇英文文章（英文字母数为n），通过对其中的a,b,c,d/a,b,c,d.....(不区分大小写)统计每个字母的个数n，有这个公式p=n/n可得每个字母的概率，最后又信源熵计算公式h（x）=??p(xi)logp(xi)i?1n，可计算出信源熵h,所以整体步骤就是先统计出英文段落的总字符数，在统计每个字符的个数，即每遇到同一个字符就++1，直到算出每个字符的个数，进而算出每个字符的概率，再由信源熵计算公式计算出信源熵。
2、香农编码：香农编码主要通过一系列步骤支出平均码长与信源之间的关系，同时使平均码长达到极限值，即选择的每个码字的长度ki满足下式：i(xi)?ki?i(xi)?1,?i具体步骤如下：a、将信源消息符号按其出现的概率大小依次排列为：p1?p2?......?pn b、确定满足下列不等式的整数码长ki为：?lb(pi)?ki??lb(pi)?1 c、为了编成唯一可译码，计算第i个消息的累加概率：pi??p(ak)k?1i?1d、将累加概率pi变换成二进制数。
信息论与编码理论课后答案【篇一：《信息论与编码》课后习题答案】式、含义和效用三个方面的因素。
2、 1948年，美国数学家香农发表了题为“通信的数学理论”的长篇论文，从而创立了信息论。
3、按照信息的性质，可以把信息分成语法信息、语义信息和语用信息。
4、按照信息的地位，可以把信息分成客观信息和主观信息。
5、人们研究信息论的目的是为了高效、可靠、安全地交换和利用各种各样的信息。
6、信息的是建立信息论的基础。
7、8、是香农信息论最基本最重要的概念。
9、事物的不确定度是用时间统计发生概率的对数来描述的。
10、单符号离散信源一般用随机变量描述，而多符号离散信源一般用随机矢量描述。
11、一个随机事件发生某一结果后所带来的信息量称为自信息量，定义为其发生概率对数的负值。
12、自信息量的单位一般有比特、奈特和哈特。
13、必然事件的自信息是。
14、不可能事件的自信息量是15、两个相互独立的随机变量的联合自信息量等于两个自信息量之和。
16、数据处理定理：当消息经过多级处理后，随着处理器数目的增多，输入消息与输出消息之间的平均互信息量趋于变小。
17、离散平稳无记忆信源x的n次扩展信源的熵等于离散信源x的熵的。
limh(xn/x1x2?xn?1)h?n???18、离散平稳有记忆信源的极限熵，。
19、对于n元m阶马尔可夫信源，其状态空间共有m个不同的状态。
20、一维连续随即变量x在[a，b] 。
1log22?ep21、平均功率为p的高斯分布的连续信源，其信源熵，hc（x）=2。
22、对于限峰值功率的n维连续信源，当概率密度均匀分布时连续信源熵具有最大值。
23、对于限平均功率的一维连续信源，当概率密度24、对于均值为0，平均功率受限的连续信源，信源的冗余度决定于平均功率的限定值p和信源的熵功率p25、若一离散无记忆信源的信源熵h（x）等于2.5，对信源进行等长的无失真二进制编码，则编码长度至少为。
2728、同时掷两个正常的骰子，各面呈现的概率都为1/6，则“3和5同时出现”这件事的自信息量是 ?mn?ki?11?mp(x)?em29、若一维随即变量x的取值区间是[0，∞]，其概率密度函数为，其中：x?0，m是x的数学2期望，则x的信源熵c。
第1章 绪论1.1 信源、编码器、信道、干扰、译码器、信宿 1.2 香农1.3 通信系统模型1.4信号是消息的表现形式，是物理的，比如电信号、光信号等。
消息是信息的载荷者，是信号的具体容，不是物理的，但是又比较具体，例如语言、文字、符号、图片等。
信息包含在消息中，是通信系统中被传送的对象，消息被人的大脑所理解就形成了信息。
1.5 略第2章 信息的统计度量2.1 少2.2 y 的出现有助于肯定x 的出现、y 的出现有助于否定x 的出现、x 和y 相互独立 2.3 FTTTF 2.4 2.12比特2.5依题意，题中的过程可分为两步，一是取出一枚硬币恰好是重量不同的那一枚，设其发生的概率为1p ，由于每枚硬币被取出的概率是相同的，所以1181p =所需要的信息量()()1log 6.34I A p bit =-=二是确定它比其他硬币是重还是轻，设其发生的概率为2p ，则212p =总的概率12111812162p p p ==⨯=所需要的信息量()log log1627.34I p bit =-==2.6 设A 表示“大学生”这一事件，B 表示“身高1.60m 以上”这一事件，则()()()0.250.5|0.75p A p B p B A ===故()()()()()()|0.750.25|0.3750.5p AB p A p B A p A B p B p B ⨯====()()()11|loglog 1.42|0.375I A B bit p A B ===2.7 四进制波形所含的信息量为()log 42bit =，八进制波形所含信息量为()log 83bit =，故四进制波形所含信息量为二进制的2倍，八进制波形所含信息量为二进制的3倍。
2.8()()()()()()2322log 3log 32log 3 1.585I p bit I p bit I I =-=-==故以3为底的信息单位是比特的1.585倍。
信息论与编码第5章第五章信源编码（第⼗讲）（2课时）主要内容：（1）编码的定义（2）⽆失真信源编码重点：定长编码定理、变长编码定理、最佳变长编码。
难点：定长编码定理、哈夫曼编码⽅法。
作业：5。
2，5。
4，5。
6；说明：本堂课推导内容较多，枯燥平淡，不易激发学⽣兴趣，要注意多讨论⽤途。
另外，注意，解题⽅法。
多加⼀些内容丰富知识和理解。
通信的实质是信息的传输。
⽽⾼速度、⾼质量地传送信息是信息传输的基本问题。
将信源信息通过信道传送给信宿，怎样才能做到尽可能不失真⽽⼜快速呢？这就需要解决两个问题：第⼀，在不失真或允许⼀定失真的条件下，如何⽤尽可能少的符号来传送信源信息；第⼆，在信道受⼲扰的情况下，如何增加信号的抗⼲扰能⼒，同时⼜使得信息传输率最⼤。
为了解决这两个问题，就要引⼊信源编码和信道编码。
⼀般来说，提⾼抗⼲扰能⼒（降低失真或错误概率）往往是以降低信息传输率为代价的；反之，要提⾼信息传输率常常⼜会使抗⼲扰能⼒减弱。
⼆者是有⽭盾的。
然⽽在信息论的编码定理中，已从理论上证明，⾄少存在某种最佳的编码或信息处理⽅法，能够解决上述⽭盾，做到既可靠⼜有效地传输信息。
这些结论对各种通信系统的设计和估价具有重⼤的理论指导意义。
§3.1 编码的定义编码实质上是对信源的原始符号按⼀定的数学规则进⾏的⼀种变换。
讨论⽆失真信源编码，可以不考虑⼲扰问题，所以它的数学描述⽐较简单。
图 3.1是⼀个信源编码器，它的输⼊是信源符号},,, {21q s s s S =，同时存在另⼀符号},,,{21r x x x X =，⼀般来说，元素xj 是适合信道传输的，称为码符号（或者码元）。
编码器的功能就是将信源符号集中的符号s i （或者长为N 的信源符号序列）变换成由x j (j=1,2,3,…r)组成的长度为l i 的⼀⼀对应的序列。
输出的码符号序列称为码字，长度l i 称为码字长度或简称码长。
可见，编码就是从信源符号到码符号的⼀种映射。
信息论与编码理论课后答案【篇一：《信息论与编码》课后习题答案】式、含义和效用三个方面的因素。
2、 1948年，美国数学家香农发表了题为“通信的数学理论”的长篇论文，从而创立了信息论。
3、按照信息的性质，可以把信息分成语法信息、语义信息和语用信息。
4、按照信息的地位，可以把信息分成客观信息和主观信息。
5、人们研究信息论的目的是为了高效、可靠、安全地交换和利用各种各样的信息。
6、信息的是建立信息论的基础。
7、8、是香农信息论最基本最重要的概念。
9、事物的不确定度是用时间统计发生概率的对数来描述的。
10、单符号离散信源一般用随机变量描述，而多符号离散信源一般用随机矢量描述。
11、一个随机事件发生某一结果后所带来的信息量称为自信息量，定义为其发生概率对数的负值。
12、自信息量的单位一般有比特、奈特和哈特。
13、必然事件的自信息是。
14、不可能事件的自信息量是15、两个相互独立的随机变量的联合自信息量等于两个自信息量之和。
16、数据处理定理：当消息经过多级处理后，随着处理器数目的增多，输入消息与输出消息之间的平均互信息量趋于变小。
17、离散平稳无记忆信源x的n次扩展信源的熵等于离散信源x的熵的。
limh(xn/x1x2?xn?1)h?n???18、离散平稳有记忆信源的极限熵，。
19、对于n元m阶马尔可夫信源，其状态空间共有m个不同的状态。
20、一维连续随即变量x在[a，b] 。
1log22?ep21、平均功率为p的高斯分布的连续信源，其信源熵，hc（x）=2。
22、对于限峰值功率的n维连续信源，当概率密度均匀分布时连续信源熵具有最大值。
23、对于限平均功率的一维连续信源，当概率密度24、对于均值为0，平均功率受限的连续信源，信源的冗余度决定于平均功率的限定值p和信源的熵功率p25、若一离散无记忆信源的信源熵h（x）等于2.5，对信源进行等长的无失真二进制编码，则编码长度至少为。
2728、同时掷两个正常的骰子，各面呈现的概率都为1/6，则“3和5同时出现”这件事的自信息量是 ?mn?ki?11?mp(x)?em29、若一维随即变量x的取值区间是[0，∞]，其概率密度函数为，其中：x?0，m是x的数学2期望，则x的信源熵c。
第1章 绪论1.1 信源、编码器、信道、干扰、译码器、信宿 1.2 香农1.3 通信系统模型1.4信号是消息的表现形式，是物理的，比如电信号、光信号等。
消息是信息的载荷者，是信号的具体容，不是物理的，但是又比较具体，例如语言、文字、符号、图片等。
信息包含在消息中，是通信系统中被传送的对象，消息被人的大脑所理解就形成了信息。
1.5 略第2章 信息的统计度量2.1 少2.2 y 的出现有助于肯定x 的出现、y 的出现有助于否定x 的出现、x 和y 相互独立 2.3 FTTTF 2.4 2.12比特2.5依题意，题中的过程可分为两步，一是取出一枚硬币恰好是重量不同的那一枚，设其发生的概率为1p ，由于每枚硬币被取出的概率是相同的，所以1181p =所需要的信息量()()1log 6.34I A p bit =-=二是确定它比其他硬币是重还是轻，设其发生的概率为2p ，则212p =总的概率12111812162p p p ==⨯=所需要的信息量()log log1627.34I p bit =-==2.6 设A 表示“大学生”这一事件，B 表示“身高1.60m 以上”这一事件，则()()()0.250.5|0.75p A p B p B A ===故()()()()()()|0.750.25|0.3750.5p AB p A p B A p A B p B p B ⨯====()()()11|loglog 1.42|0.375I A B bit p A B ===2.7 四进制波形所含的信息量为()log 42bit =，八进制波形所含信息量为()log 83bit =，故四进制波形所含信息量为二进制的2倍，八进制波形所含信息量为二进制的3倍。
2.8()()()()()()2322log 3log 32log 3 1.585I p bit I p bit I I =-=-==故以3为底的信息单位是比特的1.585倍。
第5章 有噪信道编码5.1 基本要求通过本章学习，了解信道编码的目的，了解译码规则对错误概率的影响，掌握两种典型的译码规则：最佳译码规则和极大似然译码规则。
掌握信息率与平均差错率的关系，掌握最小汉明距离译码规则，掌握有噪信道编码定理（香农第二定理）的基本思想，了解典型序列的概念，了解定理的证明方法，掌握线性分组码的生成和校验。
5.2 学习要点5.2.1 信道译码函数与平均差错率5.2.1.1 信道译码模型从数学角度讲，信道译码是一个变换或函数，称为译码函数，记为F 。
信道译码模型如图5.1所示。
5.2.1.2 信道译码函数信道译码函数F 是从输出符号集合B 到输入符号集合A 的映射：*()j j F b a A =∈，1,2,...j s =其含义是：将接收符号j b B ∈译为某个输入符号*j a A ∈。
译码函数又称译码规则。
5.2.1.3 平均差错率在信道输出端接收到符号j b 时，按译码规则*()j j F b a A =∈将j b 译为*j a ，若此时信道输入刚好是*j a ，则称为译码正确，否则称为译码错误。
j b 的译码正确概率是后验概率：*(|)()|j j j j P X a Y b P F b b ⎡⎤===⎣⎦ （5.1）j b 的译码错误概率：(|)()|1()|j j j j j P e b P X F b Y b P F b b ⎡⎤⎡⎤=≠==-⎣⎦⎣⎦ （5.2）平均差错率是译码错误概率的统计平均，记为e P ：{}1111()(|)()1()|1(),1()|()s se j j j j j j j ssj j j j j j j P P b P e b P b P F b b P F b b P F b P b F b ====⎡⎤==-⎣⎦⎡⎤⎡⎤⎡⎤=-=-⎣⎦⎣⎦⎣⎦∑∑∑∑ （5.3）5.2.2 两种典型的译码规则两种典型的译码规则是最佳译码规则和极大似然译码规则。
5.2.2.1 最佳译码规则图5.1 信道译码模型,,}a }r a使e P 达到最小的译码规则称为最佳译码规则。
这种规则是按后验概率最大原则定出的，所以又称最大后验概率译码规则。
**(),:(|)(|),j j j j j i j i F b a A b BF P a b P a b a A⎧=∈∈⎪⎨∈⎪⎩≥ （5.4） 上式中最大后验概率条件可等价成最大联合概率条件。
将*(|)(|)j j i j P a b P a b ≥两边乘以()j P b ，变换为*(,(,)j j i j P a b P a b )≥。
因此，最佳译码规则又可表示成：**(),:(,)(,),j j j j j i j i F b a A b BF P a b P a b a A⎧=∈∈⎪⎨∈⎪⎩≥ （5.5） 因为使用最大联合概率条件，所以又称为最大联合概率译码规则。
5.2.2.2 极大似然译码规则按最大转移概率条件来确定的译码规则，称为极大似然译码规则：**(),:(|)(|),j j j j j j i i F b a A b B F P b a P b a a A⎧=∈∈⎪⎨∈⎪⎩≥ （5.6） 虽然极大似然译码规则的平均差错率不是最小，不是最佳的，但最易找出。
可以证明，当信道输入等概时，极大似然译码规则与最大联合概率译码规则等价，此时极大似然译码规则也是最佳的。
5.2.3 信道编码对平均差错率和信息率的影响信道编码（或称纠错编码）是靠增加冗余码元来克服或减轻噪声影响的。
冗余是相对于信息的表示而言，但是对提高传送可靠性来说，冗余码元却提供了极宝贵的可靠性信息。
以下以两种简单信道编码方法来说明信道编码对平均差错率和信息率的影响。
5.2.3.1 “简单重复”编码日常中人们可以通过重复某句话使别人听得更清楚。
数字通信中，将符号重复传几次，也会提高传送可靠性。
例如，“重复2次”编码，如图5.2所示。
编码规则为图5.2 “重复2次”编码112345672800000010100111001011101111ffu u αααααααα=−−→========−−→=12345678000001010011100101110111ββββββββ========12000111αα==P 8,,}β8,,}α0000:1111f →⎧⎨→⎩ 扩展信道的转移矩阵为331234567832222223132222223|8[]Y X p p p p p pp p p pp pp p P ppp pp p ppp p pp pp ββββββββαα⎡⎤=⎢⎥⎢⎥⎣⎦按极大似然译码规则得译码函数：1121314851687888()()()()()()()()F F F F F F F F βαβαβαβαβαβαβαβα========即4162183758011000101001000111010110100111FFββββααββββ==⎫⎫⎪⎪==⎪⎪−−→=−−→=⎬⎬==⎪⎪⎪⎪==⎭⎭信道编码之后的信息率为()H U R N=b i t /码元 （5.7） 若信源等概率分布，则log MR N=b i t /码元 （5.8） 其中M 代表信源消息（符号）个数。
无编码 log 2111N R === b i t /码元 210e P -= “重复2次”编码 log 21333N R === b i t /码元 4310e P -=⨯155N R == bit /码元 510e P -=177N R == bit /码元 7410e P -=⨯随着“重复”次数的增加，e P 下降，但R 也跟着下降。
即信息传输的有效性和可靠性是矛盾的。
5.2.3.2 对符号串编码对信源的符号串进行编码，即增多消息个数M ，同时增大码长N ，有可能使平均差错率e P 降低到要求的范围以内，而又能使信息率R 降低得不多。
例如，取4M =（2次扩展信源）、5N =。
4个消息记为123400,01,10,11s s s s ==== 编码函数为1212345:1,2,3,4i i i i i i i i i f s m m a a a a a i α=→==112231241112i i i i i i i i i i i i a m a m a m m a m a m m ⎧=⎪=⎪⎪=⊕⎨⎪=⎪⎪=⊕⎩ 译码采用极大似然规则。
编译码示意图见图5.3所示。
编码后的信息率R 和平均差错率e P 分别为log 4255R == bit /码元 5432411(4208)7.86104e P p p p p p -=-++≈⨯与“重复2次”编码相比，R 略有增加，e P 处在同一数量级。
因此，增大码长N 和适当增多消息个数M ，对兼顾e P （可靠性）和R （有效性）的要求是有效的。
5.2.4 最小汉明距离译码规则5.2.4.1汉明距离两个等长符号序列x 和y 之间的汉明距离，记为(,)D x y ，是x 与y 之间对应位置上不同符号的个数，用来定量描述符号序列之间的“相似”程度。
5.2.4.2汉明距离与信道编码性能的关系码是码字的集合，码字则是由码元组成的符号序列。
假如12{,,,}q C c c c =是等长码，则C 中任意两个不同码字之间的汉明距离或码间距离为(,),,,i j i j i j D c c c c c c C ≠∈码C 的最小码间距离定义为min min (,),i j i j i j d D c c c c c c C ⎡⎤=≠∈⎣⎦最小码间距离min d 是衡量码的性能的重要参数，码的min d 小，说明其中有些码字受干扰后容易变为另一码字，译码时就会出错。
因此，信道编码在选择码字时，应尽量使码的最小码间距离min d 大一些为好。
图5.3 4M = 、5n = 的编译码示意图0000000010110110101111111010ff f f −−→−−→−−→−−→0000000001000100010001000100001000100011011010110001111010010010111101111000111010111101101010110011111110011100110101001101011011110001111010010010100101111001000000110110111110105次扩展信道对于二元对称信道，设信源有M 个消息12{,,,}M s s s ，输入和输出符号集分别为{0,1}A =和{0,1}B =，其N 次扩展信道的入口符号集N A 和出口符号集N B 中都含有2N 个N 长二元符号串，即122122{,,,}{,,,}N N N NA B αααβββ==从NA 中选择M 个符号串当作码字组成码C ：12{,,,}M C c c c =按极大似然译码规则进行译码时，可以推导出等价于以下规则，称为最小（汉明）距离译码规则：**(),:(,)min (,),Nj j j Nj j i j i F c C B F D c D c c C A ββββ⎧=∈∈⎪⎨⎡⎤=∈⊂⎪⎣⎦⎩ （5.9） 其含意是：将接收序列j β译为与之最相似的输入序列（码字）*j c 。
5.2.5有噪信道编码定理（香农第二定理）5.2.5.1有噪信道编码定理若信道是离散、无记忆、平稳的，且信道容量为C ，只要待传送的信息率R C <，就一定能找到一种信道编码方法，使得码长N 足够大时，平均差错率e P 任意接近于零。
有噪信道编码定理实际上是一个存在性定理，它指出：在R C <时，肯定存在一种好的信道编码方法，用这种好码来传送消息可使e P 逼近零。
但香农并没有给出具体编码方法。
对有噪信道编码定理的证明要用到联合典型序列。
所谓典型序列，是指那些平均自信息量逼近熵的序列。
联合ε典型序列，是指那些平均联合自信息量逼近联合熵的序列。
离散无记忆信源X 发出N 长序列12N i i i i x x x x =，若()()i I x H X Nε-< （5.10） 则称i x 为X 的ε典型序列，否则称为X 的非ε典型序列。
若i x 和j y 分别是X 和Y 的N 长ε典型序列，且(,)()i j I x y H XY Nε-< （5.11）则称序列对(,)i j x y 为X 与Y 的联合ε典型序列，否则称为非联合ε典型序列。
5.2.5.2有噪信道编码逆定理若信道是离散、无记忆、平稳的，且信道容量为C ，如果信息率R C >，则肯定找不到一种信道编码方法，使得码长N 足够大时，平均差错率e P 任意接近于零。
