最优化理论与信息论

最优化课程的具体应用,结合具体的专业。

最优化理论在信息论中的应用

摘 要

最优化理论与算法是一个重要的数学分支，它所研究的问题是讨论在众多的方案中什么样的方案最优以及怎么找出最优方案。这类问题普遍的存在于各类的工程计算和方案设计领域，最优化这一数学分支为这些问题的解决提供了有力的理论基础和可靠的求解方法，在实际中应用中发挥了巨大的作用。信息论以香农的三大定理为学科的支撑和架构，其中涉及到了诸多有关信息量和信道容量等的最优值求解问题。

本文结合所学的信息与通信领域的专业知识，讨论最优化理论与算法在信息论中的应用：使用最优化课程中解决非线性目标函数、线性约束函数极值问题的可行方向法中的Zoutendijk方法，结合Matlab软件中的数值计算工具箱对信息论中的问题进行编程分析和求解。最优化方法的引入，能够从数值计算的角度给出相关定理的解释，有助于加深对信息论中香农定理的理解；同时两门学科的交叉融合也能够将学到的最优化理论加以实践，从而更好的掌握并解决实际问题。

关键词：最优化 信息论 香农定理 可行方向法 Zoutendijk

最优化课程的具体应用,结合具体的专业。

ABSTRACT

Optimization theory and algorithm is

最优化课程的具体应用,结合具体的专业。

最优化理论在信息论中的应用

摘 要

最优化理论与算法是一个重要的数学分支，它所研究的问题是讨论在众多的方案中什么样的方案最优以及怎么找出最优方案。这类问题普遍的存在于各类的工程计算和方案设计领域，最优化这一数学分支为这些问题的解决提供了有力的理论基础和可靠的求解方法，在实际中应用中发挥了巨大的作用。信息论以香农的三大定理为学科的支撑和架构，其中涉及到了诸多有关信息量和信道容量等的最优值求解问题。

本文结合所学的信息与通信领域的专业知识，讨论最优化理论与算法在信息论中的应用：使用最优化课程中解决非线性目标函数、线性约束函数极值问题的可行方向法中的Zoutendijk方法，结合Matlab软件中的数值计算工具箱对信息论中的问题进行编程分析和求解。最优化方法的引入，能够从数值计算的角度给出相关定理的解释，有助于加深对信息论中香农定理的理解；同时两门学科的交叉融合也能够将学到的最优化理论加以实践，从而更好的掌握并解决实际问题。

关键词：最优化 信息论 香农定理 可行方向法 Zoutendijk

最优化课程的具体应用,结合具体的专业。

ABSTRACT

Optimization theory and algorithm is

武汉大学 电子信息学院 信号处理实验室 杨文老师 《信息论与编码理论》课件

信息论与编码理论

杨文通信工程系

武汉大学 电子信息学院 信号处理实验室 杨文老师 《信息论与编码理论》课件

第三章信道容量第三章信道容量

内容提要内容提要信道对于信息率的容纳并不是无限制的信道对于信息率的容纳并不是无限制的，它不仅与物理信道本身的特性有关，还与，它不仅与物理信道本身的特性有关，还与信道输入信号的统计特性有关，它有一个极信道输入信号的统计特性有关，它有一个极限值，即信道容量，信道容量是有关信道的限值，即信道容量，信道容量是有关信道的一个很重要的物理量。这一章研究信道，研一个很重要的物理量。这一章研究信道，研究在信道中传输的每个符号所携带的信息量究在信道中传输的每个符号所携带的信息量，并定义信道容量。,并定义信道容量。2006-10-18 2

武汉大学 电子信息学院 信号处理实验室 杨文老师 《信息论与编码理论》课件

3信道容量第三章信道容量

信道的功能：以信号形式传输和存储信息。信道传输信息的速率：与物理信道本身的特性、载荷信息的信号形式和信源输出信号的统计特性有关。信道容量研究内容：在什么条件下，通过信道的信息量最大。

3.1信道的数学模型和分类 3.2单符号离散信道

第二章 信息量和熵

2.2 八元编码系统，码长为3，第一个符号用于同步，每秒1000个码字，求它的

信息速率。

解：同步信息均相同，不含信息，因此 每个码字的信息量为 2?log8=2?3=6 bit

因此，信息速率为 6?1000=6000 bit/s

2.3 掷一对无偏骰子，告诉你得到的总的点数为：(a) 7; (b) 12。问各得到多少信

息量。

解：(1) 可能的组合为 {1，6},{2，5},{3，4},{4，3},{5，2},{6，1}

61p(a)==

366得到的信息量 =log1=log6=2.585 bit p(a) (2) 可能的唯一，为 {6，6}

1 p(b)=

36 得到的信息量=log1=log36=5.17 bit p(b)

2.4 经过充分洗牌后的一副扑克（52张），问：

(a) 任何一种特定的排列所给出的信息量是多少？

(b) 若从中抽取13张牌，所给出的点数都不相同时得到多少信息量？

1解：(a) p(a)=

52! 信息量=log1=log52!=225.58 bit p(a)?13!??13种点数任意排列

第二章 信息量和熵

2.2 八元编码系统，码长为3，第一个符号用于同步，每秒1000个码字，求它的

信息速率。

解：同步信息均相同，不含信息，因此 每个码字的信息量为 2?log8=2?3=6 bit

因此，信息速率为 6?1000=6000 bit/s

2.3 掷一对无偏骰子，告诉你得到的总的点数为：(a) 7; (b) 12。问各得到多少信

息量。

解：(1) 可能的组合为 {1，6},{2，5},{3，4},{4，3},{5，2},{6，1}

61p(a)==

366得到的信息量 =log1=log6=2.585 bit p(a) (2) 可能的唯一，为 {6，6}

1 p(b)=

36 得到的信息量=log1=log36=5.17 bit p(b)

2.4 经过充分洗牌后的一副扑克（52张），问：

(a) 任何一种特定的排列所给出的信息量是多少？

(b) 若从中抽取13张牌，所给出的点数都不相同时得到多少信息量？

1解：(a) p(a)=

52! 信息量=log1=log52!=225.58 bit p(a)?13!??13种点数任意排列

8¹

3Ã å`z3.1 `5^ .....................................3.2 { Ú½9Âñ5.............................3.3 eü{.....................................3.4Úî{.......................................3.5[Úî{......................................3.6

ÝFÝ{.....................................

11412152227

8¹·ii·

1nÙÃ å`z

â1 Ü© {nØÐÚ §3¦) 55y¯K L§¥§· I (½|¢ Ú

实验4 Huffman编码对英文文本的压缩和解压缩

一、实验内容

根据信源压缩编码——Huffman编码的原理，制作对英文文本进行压缩和解压缩的软件。要求软件有简单的用户界面，软件能够对运行的状态生成报告，分别是：字符频率统计报告、编码报告、压缩程度信息报告、码表存储空间报告。 二、实验环境

1. 计算机

2. Windows 2000 或以上 3. Microsoft Office 2000 或以上 4. VC++ 6.0 三、实验目的

1. 掌握Huffman编码的原理

2. 掌握VC开发环境的使用（尤其是程序调试技巧） 3. 掌握C语言编程（尤其是位运算和文件的操作） 4. 掌握数据结构的内容：链表、顺序表、堆栈、最优二叉树 5. 掌握结构化程序分析和开发的软件工程原理 四、实验要求

1. 提前预习实验，认真阅读实验原理。

2. 认真高效的完成实验，实验过程中服从实验室管理人员以及实验指导老

师的管理。

3. 认真填写实验报告。 五、实验原理

压缩/解压缩流程

压缩流程：

读取扫描文本文件——〉统计字符频率——〉生成码字——〉保存压缩文件 解压缩流程：

读取扫描压缩文件——〉提取字符频率——〉生成码树——〉保存文本文件 六、参考书

1.

实验二 离散信道及其容量

一、实验目的

1、 2、 3、

理解离散信道容量的内涵；

掌握求二元对称信道（BSC）互信息量和容量的设计方法； 掌握二元扩展信道的设计方法并会求其平均互信息量。

二、实验原理

若某信道输入的是N维序列x，其概率分布为q(x),输出是N维

序列y,则平均互信息量记为I(X;Y)，该信道的信道容量C定义为

C?maxI(X;Y)。

q(x)三、实验内容

1、给定BSC信道，信源概率空间为

X

P

=

０ １ 0.6 0.4

?0.990.01?信道矩阵 P??? 0.010.99??求该信道的I(X;Y)和容量，画出I(X;Y)和?、C和p的关系曲线。 2 、编写一M脚本文件t03.m，实现如下功能：

在任意输入一信道矩阵P后，能够判断是否离散对称信道，若是，求出信道容量C。 3、已知X=(0,1,2);Y=(0,1,2,3),信源概率空间和信道矩阵分别为

X

Px

=

０ １ ２ 0.3 0.5 0.2

P=

0.1 0.3 0 0.6 0.3 0.5 0.2 0 0.1 0.7 0.1 0.

实验4 Huffman编码对英文文本的压缩和解压缩

一、实验内容

根据信源压缩编码——Huffman编码的原理，制作对英文文本进行压缩和解压缩的软件。要求软件有简单的用户界面，软件能够对运行的状态生成报告，分别是：字符频率统计报告、编码报告、压缩程度信息报告、码表存储空间报告。 二、实验环境

1. 计算机

2. Windows 2000 或以上 3. Microsoft Office 2000 或以上 4. VC++ 6.0 三、实验目的

1. 掌握Huffman编码的原理

2. 掌握VC开发环境的使用（尤其是程序调试技巧） 3. 掌握C语言编程（尤其是位运算和文件的操作） 4. 掌握数据结构的内容：链表、顺序表、堆栈、最优二叉树 5. 掌握结构化程序分析和开发的软件工程原理 四、实验要求

1. 提前预习实验，认真阅读实验原理。

2. 认真高效的完成实验，实验过程中服从实验室管理人员以及实验指导老

师的管理。

3. 认真填写实验报告。 五、实验原理

压缩/解压缩流程

压缩流程：

读取扫描文本文件——〉统计字符频率——〉生成码字——〉保存压缩文件 解压缩流程：

读取扫描压缩文件——〉提取字符频率——〉生成码树——〉保存文本文件 六、参考书

1.

2.1一个马尔可夫信源有3个符号?u1,u2,u3?，转移概率为：p?u1|u1??1/2，

p?u2|u1??1/2，p?u3|u1??0，p?u1|u2??1/3，p?u2|u2??0，p?u3|u2??2/3，

p?u1|u3??1/3，p?u2|u3??2/3，p?u3|u3??0，画出状态图并求出各符号稳态概率。解：状态图如下

状态转移矩阵为：

1/2u11/31/21/32/32/3u2u3

0??1/21/2??p??1/302/3?

?1/32/30???设状态u1，u2，u3稳定后的概率分别为W1，W2、W3

11?1W1?W2?W3?W110??2W1?33??2512???WP?W9?W1?W3?W2?由?得?2计算可得?W2? 325?W1?W2?W3?1?2?6?W2?W3?W3?3??25??W1?W2?W3?1?

2.2 由符号集{0，1}组成的二阶马尔可夫链，其转移概率为：p(0|00)=0.8，p(0|11)=0.2，

p(1|00)=0.2，p(1|11)=0.8，p(0|01)=0.5，p(0|10)=0.5，p(1|01)=0.5，p(1|10)=0.5。

画出状态图，并计算各状态的稳态概率。

?p解：p(