信息论理论基础(第二章)

2020 4 6 1 第二章 基本信息论 2 1信息度量 2 2离散信源的熵 2 3二元联合信源的共熵与条件熵 2 4信源冗余度 2 5连续信源的熵 2 6熵速率和信道容量 2 7离散有噪信道的熵速率和信道容量 2 8连续有噪信道的熵速率和信道容量 2 9使信源与信道匹配的编码 2020 4 6 2 2 1信息度量 基本信息论又称狭义信息论 是以信息的度量为基础 有了对信息的确切定义与测度 信息科学才得以建立和发展 案例一 甲乙同去听某一学者讲课 由于两个人的业务基础不同 他们听到的虽然是同一内容 但听后得到的新知识是不一样的 怎么衡量呢 就可以用信息度量的方法 案例二 信源发出的消息 经过信道传送给信宿 信道能够传送或存储的最大信息量为多少呢 可以用信道容量来分析 2020 4 6 3 2 1 1信源的不肯定性信源是发送消息的一方 信源发出的消息常常是随机的 这样信源要发出的消息的状态应该存在某种程度的不肯定性 比如大学生在上课时 老师给大学生讲1 1 2的知识 那么这些大学生肯定得不到任何的信息 因为1 1 2的知识他们在上小学时就已经学过了 它的不肯定性为零 获得以前不知道的内容 可以获得信息 因为它存在不肯定性 信源中某一消息发生的不肯定性越大 一旦发出 收信者获得的信息量就越大 相反 信源中某一消息发生的不肯定性越小 通过通信收信者得到的信息量就越少 因此 获得信息量的多少与信源的不肯定性有关 即与不肯定程度有关 下面介绍不肯定程度 不肯定程度上面讲了信源的不肯定性有大小之分 也就是说不肯定性有程度上的差分 那么 什么是不肯定程度呢 为了便于说明问题 举个例子说明 2020 4 6 4 例题 有三个布袋 每个布袋中分别放100个球 这三个布袋中球的存在方式如下 布袋a 放99个白球 1个黑球 布袋b 放50个白球 50个黑球 布袋c 放4种颜色的球 红 蓝 白 黑各25个 从这三个布袋中分别抓1个球 猜测在三个布袋中抓到的是哪种颜色的球 解 布袋a 可以肯定这样的一个信源发出的消息具有不肯定性 因为拿出一个球可能是红球 也可能是白球 但很容易猜测出它大概是红球 因为红球多 所以猜测的难度不大 当然不肯定程度也不大 布袋b 这时猜测从布袋中随意拿出一个球的颜色的难度就比第一种情况大 因为这时红球 白球一样多 不容易猜测 所以这种情况下信源发出的消息的不肯定程度较大 布袋c 这时猜测从布袋中随意拿出一个球的颜色的难度更大 因为这时更难猜测 所以这种情况下的不肯定程度更大 由此可知 事件发生的不肯定性与事件发生的概率有关 一般情况下 一个信源可以用一个概率空间来描述 而信源的不肯定程度可以用这个概率空间的可能状态数目及其概率来描述 2020 4 6 5 2020 4 6 6 2020 4 6 7 单位 bit nat hartleyLog2 e 10 2020 4 6 8 2 1 2信息量根据以上对信源不肯定程度度量方法的分析 我们可以很容易地得出信息量的度量方法 定义收信者收到消息实质上就是从不肯定到比较肯定或完全肯定的过程 要实现这个过程 必须通过通信获得信息 在这个过程就会有不肯定程度的减小 因此 很容易直观地将信息量定义为 信息量 不肯定程度的减小量也就是说 收信者收到一个消息后 所获得的信息量等于收到消息前不肯定程度的减小量 之所以不直接定义信宿收到的信息量就等于信源发出的信息量 是因为在一般情况下 由于信道中噪声的干扰 信源发出的信息量可能会损失一些 而定义信宿对于信源不肯定程度的减小量才是信宿从信源收到的净信息量 2020 4 6 9 2020 4 6 10 2020 4 6 11 2020 4 6 12 2020 4 6 13 2020 4 6 14 作业 2 1 2 3 2 5 2020 4 6 15 2 2离散信源的熵 2020 4 6 16 2020 4 6 17 2020 4 6 18 2020 4 6 19 2020 4 6 20 2020 4 6 21 2020 4 6 22 2 3二元联合信源的共熵和条件熵 2020 4 6 23 2020 4 6 24 2020 4 6 25 2020 4 6 26 2020 4 6 27 2020 4 6 28 2020 4 6 29 2020 4 6 30 2020 4 6 31 2020 4 6 32 2 4信源冗余度 2020 4 6 33 2020 4 6 34 2020 4 6 35 2020 4 6 36 2 5连续信源的熵 2020 4 6 37 2020 4 6 38 2020 4 6 39 2020 4 6 40 2020 4 6 41 2020 4 6 42 2020 4 6 43 2020 4 6 44 2020 4 6 45 2020 4 6 46 2020 4 6 47 2 6熵速率和信道容量 2020 4 6 48 2020 4 6 49 2 6 2信道容量在一般广义的通信系统中 信道是很重要的一部分 信道是所传信息的载体 消息 的具体形式 信号 所要通过的通道 或媒介 信息是抽象的 但是信道是具体的 比如二人对话 二人之间的空气就是信道 打电话时 电话线就是信道 看电视 听收音机时 发送和接收天线之间的空气就是信道等等 信道的分类根据实际的应用 信道有几种分类方法 1 按其输入 输出信号在幅度和时间上的取值来分类 离散信道 也称为数字信道 输入 输出信号在幅度和时间上都是离散的信道 连续信道 输入 输出信号在幅度上连续 在时间上离散的信道 模拟信道 输入 输出信号在幅度和时间上都是连续的信道 2020 4 6 50 2 按其输入 输出信号之间关系的记忆特性来分类可以分为记忆信道和无记忆信道 如果信道的输出只与信道该时刻的输入有关而与其它时刻的输入无关 称此信道为无记忆信道 反之称为记忆信道 实际信道一般都是有记忆的 如电缆信道中的电感电容 无线信道中的电波传播的衰落现象等 有记忆信道的分析比较复杂 有用的研究成果很少 3 按其输入 输出信号之间的关系是否确定来分类可以分为有噪声信道和无噪声信道 一般来说 因为信道中总是存在某种程度的噪声 所以信道输入 输出之间的关系是一种统计依赖的关系 但是当噪声与信号相比很小时 可以近似为无噪声信道 而有噪声信道是信息论研究的主要对象 4 根据信道输入和输出的个数来分类 单用户信道 只有一个输入端和一个输出端的单向通信的模型 多用户信道 双向通信或三个或更多个用户之间相互通信的情况 在本章中主要讨论的是离散信道和连续信道的内容 信道的任务就是传输信息和存储信息 研究信道就是研究信道中传送或存储的最大信息量 即信道容量的问题 2020 4 6 51 2020 4 6 52 2020 4 6 53 2020 4 6 54 2 7离散有噪信道中的熵速率和信道容量 2020 4 6 55 2020 4 6 56 2020 4 6 57 2020 4 6 58 2020 4 6 59 2020 4 6 60 2020 4 6 61 2020 4 6 62 2020 4 6 63 作业 2 13 2 16 2 20 2020 4 6 64 2 8连续有噪信道中的熵速率和信道容量 2020 4 6 65 2020 4 6 66 2020 4 6 67 2020 4 6 68 2 9使信源与信道匹配的编码 一 编码定理小结1 编码定理所要研究的问题为了不失真地恢复信源的信息 对理想信道所需的最小信息率是多少 这就是信源编码定理所要研究的问题 为了不失真地恢复信源的信息 对给定信道容量 能够传输的最大信息率是多少 这就是信道编码定理所要研究的问题 例如 X x1 x2 xi xL xi a1 a2 an X Y y1 y2 yi yk k Lxiyi b1 b2 bm 2020 4 6 69 若为二元系统 yi 0 1 Y是由k个 0 1 组成的序列 变换要求 A 能无失真或无差错地从Y恢复到X B 传送Y所需的信息率最小 即码长最短 K个码源携带的最大信息量 klogm每条消息的最大信息量 klogm L信息率最小意味着klogm L最小 在不失真译码时 这个最小值应是多少 2 信源编码定理的分类无失真离散信源编码定理A 定长编码定理B 变长编码定理 两种方法 限失真信源编码定理A 离散无记忆信源限失真编码定理B 连续信源适用的编码定理 2020 4 6 70 3 编码定理内容简介1 定长编码定理内容 由L个符号组成的 每个符号的熵为H X 的无记忆平稳信源 符号序列x1 x2 xL可用k个符号y1 y2 yk 每个yi有m种取值 进行定长编码 对任意 0 0 只要klogm L H X 则当L足够大时 必可使译码差错 Pe 小于 反之 当klogm L H X 2 时 译码差错一定是有限值 且当L足够大时 译码几乎必定出错 例 设信源X有8个变量 x0 x7 即L 8 码元为二元码 0 1 即m 2 每个xi需用三个二元码表示 则Y序列长 3 8 24 即 k 24 根据定理 只要klogm L H X 便可无失真译码 因为Hmax X log28 3bit 等概分布 实际的X不可能等概分布 H X 3bit 所以能够满足定理要求 2020 4 6 71 定理含义 klogm LH X klogm 长为k的符号序列能载有的最大信息量 LH X 长为L的信源序列平均携带的信息量 当L充分长时 传输效率接近1 2 按符号变长编码定理内容 若一个离散无记忆信源的熵为H X 每个信源符号用m进制符号进行变长编码 一定存在一种无失真的编码方法 其码字平均长度K满足下列不等式 H X logm K 1 H X logm其中 K kipiki的数学期望 物理含义 Klogm H X K H X logm码长的下界K 1 H X logm码长的上界 大于此上界仍可无失真地编码 1 H X logm H X logm 2020 4 6 72 3 变长无失真信源编码定理 香农第一定理 内容 若一个离散无记忆信源的熵为H X 对该信源的N次扩展信源XN用m进制符号进行变长编码 一定存在一种无失真的编码方法 其码字平均长度K满足下列不等式 NH X logm KC时 任何编码的Pe必大于零 当L Pe 1 2020 4 6 73 二 编码定理的证明略 三 信源最佳化 R C H X C H X maxR H X maxH X 无噪 使 1的过程即是信源最佳化过程 即通过信源最佳化可使信源输出的 含金量 得到提高 从而节省时间 提高通信效率 为使信源最佳化 应采取以下两个步骤 1 符号独立化过程弱记忆信源 只有几个符号相关 将基本信源空间 多重空间重数 相关性 实现复杂程度 应视具体情况而定 强记忆信源 相关性很强 以至于根据其中一个即可推测出其余的 能被推知的可不传送 节省了时间即提高了H X q qu 2020 4 6 74 2 概率均匀化 最佳编码 信源的有效性编码 编码的基本术语 二元代码 A中只有 0 1 相当D 2 X x1 x1 xn A a1 a1 aD 同价代码 二元代码的两个码元长度相同 占用时间相同 反之 非同价代码 如莫尔斯电码的点与划 等长代码 任意码字Wi均由同样多个码元组成 如5单位起止式电传打字机 译码时不需同步 2020 4 6 75 单义代码 如果任意一个有限长的码字序列 即有限长的一串Wi 只能唯一地分割成一个个码字 则称单义代码 例如 W W1 W2 W3 0 10 11 是单义代码 100111000 W2W1W3W2W1W1 10 0 11 10 0 0不需加同步 效率高 非续长代码 如任意一个码字都不是另一个码子的续长 前缀 例如 W 0 10 100 111 不是非续长代码 因为100是10的续长 非续长码一定是单义码 但单义码却不一定是非续长码 例如 W 0 01 不是非续长代码 但却是单义代码 2020 4 6 76 单义代码存在定理 克劳夫特不等式 D ki 1D 码元集的元素个数 n 码字个数 ki Wi的码元个数 例 贾书P82非续长代码的构成方法贾书P83最佳编码方法 不等长非续长代码 p大 短码p小 长码香农 范诺编码法 Shannon Fanno 例1 贾书P85 A B C D E F G H 0 1 0 18 0 4 0 05 0 06 0 1 0 07 0 04 X P x 2020 4 6 77 H X p xi logp xi 2 55bit 消息令n 1 s 则 H X 即无噪信道的接收熵速率R H X R nH X 2 55bit sC 无噪 H max X nHmax X nlog8 3bit s未编码的传输效率 H X C 2 55 3 85 用普通方法编码 等长编码 8个消息 3个二元码 每个码元的码元熵 2 55 3 0 85bit 码元二元码元的最大熵 1bit 码元 R H max X n 0 8