信息论基础最新版本

.,信息论基础,张松松080803129南京林业大学理学院,.,目录,前言第一章随机变量的信息度量第二章随机过程信息度量和渐进等分性第三章数据压缩和信源编码第四章数据可靠传输和信道编码,.,绪论,信息论简史信息论简介,.,信息论简史,信息论是在20世纪40年代后期在通讯工程实践中，由通讯技术与概率论随机过程和数理统计相结合而发展起来的一门科学，是专门研究信息的有效处理和可靠传输的一般规律的科学。克劳德香农（ClaudeShannon）于1948年发表的具有里程碑性质的论文“通讯的数学理论”是世界上首次将通讯过程建立了数学模型的论文，这篇论文和1949年发表的另一篇论文一起奠定了现代信息论的基础。,.,信息论简介,作为通讯系统的数学理论，香农在1948年的奠基性文章中提出了通信系统的一般模型（如下图所示）,图1.1通信系统模型,.,1.1自信息1.2熵、联合熵、条件熵1.3相对熵和互信息,第一章随机变量的信息度量,.,1.1自信息,定理1.1.1若自信息满足一下5个条件：非复性：如则如则严格单调性：如果则如果则则,其中为常数。,定义1.1.1设有概率，则的自信息定义为,。,.,1.2熵、联合熵、条件熵,定义1.2.1离散随机变量的熵定义为,我们也用表示这个熵，有时也称它为概率分布的熵，其中对数函数以2为底时，熵的单位为比特（bit），若对数以为底时，则熵的单位为奈特（nat）若对数以10为底时，则熵的单位为哈特（hartley）。注意熵只是概率分布的函数，与的取值无关。用表示数学期望，表示关于分布的数学期望，即,则熵可以表示为随机变量的数学期望，即,可见熵是自信息的概率加权平均值,.,引理1.2.1,，且等号成立的充要条件是有退化分布。,例题1.2.1设,依概率,依概率,则,。,.,定义1.2.2设一对随机变量的联合分布为,则定义的联合熵为,或写成数学期望形式：,.,定理1.2.2（链法则）,证明：,.,习题一选做,1设随机变量由以下给出,计算：（a）（b）如果为两个边际分布的乘积分布，计算和。,.,解：,.,.,.,6设随机变量有联合分布，证明一下不等式，并说明等号成立的条件：,.,解：,.,.,13令为掷一枚均匀硬币直至其正面向上所需的次数，求的概率分布和。,.,.,第二章随机过程的信息度量和渐进等分性,概念一如果一个信源序列是阶马尔可夫过程，称信源为阶马尔可夫信源（简称阶马氏信源），时称马尔科夫信源（简称马氏信源）。二若存在上的一个概率分布，满足，则称为马氏过程的平稳分布。,.,习题二选做,3设为二值平稳马氏信源，其进一步转移概率如下：,（a）求该信源的平稳分布。（b）求该信源的熵率。,.,.,.,第三章数据压缩和信源编码,定义一称唯一可以编码为即时编码（瞬时编码），如果出现的码字集中，没有一个码字的前缀。定义二设码树上最长得路长为，如果进码树上的路的终结点都被用作码字时共有个码字，这时每个码字长都是，即是定长码，这种树称满树。定理（克莱夫特不等式）码字字母取值于进字母集的即时码，其码字长分别为时必须满足。反之，对给定的满足上述不等式的一组，必存在以他们为码字长的一个即时码。注1定理的结论对构成即时码的任何可列无穷码长集也成立。注2克莱夫特不等式对唯一可译码也成立。定义三一个进唯一可译码的冗余度定义为其平均长度与信源熵的差，即冗余度或。,.,习题三选做,5一个信源有以下概率分布,(a)对该信源构造一个二进即时码；(b)计算信源熵和平均码字长。,.,.,.,6已知信源有以下概率分布,(a)构造一个二进即时码；(b)计算信源熵和平均码字长。,.,.,.,8已知信源有以下概率分布,(a)对分别编一个二进和三进哈弗曼码；(b)计算信源的二进熵和三进熵；(c)以上二种编码哪种更好些？说明理由。,.,.,.,第四章数据可靠传输和信道编码,概念信道编码的目的是要使译码错误概率在一定限制下（例如小于）使码率达到最大，这个码率的上限就称为信道容量。,例题1二进对称信道。这时,其中,所以,达到的输出分布,对应的输入分布也是均匀分布。,.,例题2二进对称删除信道，这时易计算得,其中,，由于，猜测,，是否存在这样的输入分布使对应的输入分布,是达到最大熵的均匀分布呢？,.,于是,进而,其中，当时达到最大,，这时对应的输出分布为,，只有当时，才是均匀分布。此时信道的容量为,.,习题四选做,1、计算以下有关信道之容量：,解：这是两二进对称信道的串联信道，每个二进对称信道容量，考虑为一马氏链。,.,先计算转移概率:,.,类似可以计算得,和,因此上述串联信道相当于一下的二