《信息论基础》第三章：离散信源及信源熵

本章是《信息论基础》的核心基础章节完整建立离散信源的数学模型体系。本章以概率空间、随机过程作为理论起点依次对各类离散信源给出严格定义系统推导自信息量、信源熵、条件熵、联合熵、平均符号熵与极限熵研究扩展信源、平稳有记忆信源的基本性质最终建立一套用于定量刻画信息不确定性的完整理论框架。信息论的根本目标就是对信息进行量化只有将“信息”转化为可以计算的量才能够进一步完成信源编码、信道传输与数据压缩。在香农创立信息论之前信息仅仅是定性概念无法度量大小香农借助概率论把信息等价于事件的不确定性实现了信息的定量化。3.1 随机过程基本知识信源是信息产生的源头。信息本身是抽象的想要定量刻画信息必须依靠概率论与随机过程作为数学工具。普通随机变量仅描述单次随机试验的结果而信源通常会源源不断地输出一串符号序列每一个时刻输出的符号都是随机变量并随时间不断演化这恰好就是随机过程的研究对象。从数学定义上说随机过程可以记作 {X_t, t∈T}指标集 T 代表时间。若指标集为离散取值则称为离散时间随机过程如果每一个随机变量的取值集合为离散集合则该过程的值域离散。离散信源输出的符号序列本质上就是一类离散时间、离散取值的随机过程。平稳随机过程是其中最重要的一类。如果随机过程的任意有限维分布都不随时间起点的平移而改变则称该随机过程是严平稳的。严平稳意味着统计性质在全部时间上保持恒定不会随着时间推移发生变化。弱化条件之后可以得到宽平稳只要求均值与自协方差不随时间平移而改变。在信息论当中绝大多数有记忆信源都直接假设为平稳信源这一假设极大简化了熵的推导。例 3-1抛硬币序列反复独立抛掷一枚均匀硬币记正面为符号 0反面为符号 1。每一次抛硬币对应一个随机变量无限次抛掷得到符号串就是一个随机过程。由于每次抛掷独立分布恒定这个序列构成严平稳随机过程。需要区分独立与记忆两个概念。如果前后时刻的随机变量互不关联则信源无记忆反之若后一个符号发生的概率依赖前面已经输出的符号信源就带有记忆也就是有记忆信源。现实世界当中大量信源都是有记忆的例如自然语言文本一个字出现的概率强烈依赖于前面相邻的文字。3.2 离散信源的数学模型离散信源的标准数学表达是概率空间\left[\begin{array}{c} X \\ P(x) \end{array}\right] \left[\begin{array}{cccc} x_1 x_2 \dots x_q \\ p(x_1) p(x_2) \dots p(x_q) \end{array}\right]满足归一条件\sum_{i1}^q p(x_i)1,\quad 0\le p(x_i)\le 1集合 X{x_1, x_2, …, x_q}代表信源所有可以输出的符号称为符号集p(x_i) 代表符号 x_i 的发生概率。只要给出符号集合和对应的概率分布就完全确定一个简单离散信源。离散无记忆信源DMS是最基础的模型。所谓无记忆是指信源先后输出的全部符号之间相互独立任意一个符号的输出概率都不受之前输出符号的影响。无记忆假设虽然是理想近似但它计算简便是学习更复杂信源模型的基础。例 3-2二元信源设二元信源符号集 X{0, 1}p(0)pp(1)1−p概率空间写为\begin{bmatrix} X\\P \end{bmatrix} \begin{bmatrix} 0 1 \\ p 1-p \end{bmatrix}当 p0.5两个符号等概不确定性达到最大当 p 趋近于 0 或者 1信源几乎固定输出单一符号不确定性趋近消失。仅仅依靠简单单符号信源不足以描述连续输出的长序列于是引入扩展信源。3.3 自信息量与信源熵对于一个随机事件 x_i自信息量表征这个事件本身含有的信息大小定义I(x_i)-\log_2 p(x_i)单位比特bit。自信息量有明确含义一件发生概率越小的事件如果一旦发生带来的信息就越多必然事件概率等于 1自信息量等于零不携带任何信息不可能事件概率趋近于零自信息量趋于无穷。自信息量是针对单个样本点定义的本身也是随机量取值随事件结果变化。自信息量的统计平均值就是信源熵香农熵H(X)E[I(x)]-\sum_{i1}^q p(x_i)\log_2 p(x_i)约定p→0 时p log p0。信源熵不再是某一次输出的信息而是整个信源全部符号的平均不确定度代表在接收之前我们对信源下一个输出符号平均不确定的大小。熵越大信源越难预测。例 3-3计算二元信源熵二元信源p(0)0.5p(1)0.5H(X)-(0.5\log_2 0.50.5\log_2 0.5)1\ \text{bit}如果取 p(0)0.1p(1)0.9H(X)-(0.1\log_2 0.1 0.9\log_2 0.9)\approx 0.469\ \text{bit}可以直观验证分布越不均匀熵值越小。信源熵具备一组重要性质非负性、极值性、对称性、确定性、扩展性。极值定理指出在固定符号总数的前提下均匀分布取得最大熵。3.4 联合熵与条件熵当我们同时考察两个随机变量 X、Y对应的联合概率分布 p(x,y)定义联合自信息量I(x,y)-\log_2 p(x,y)对全部取值求期望得到联合熵H(X,Y)-\sum_{x}\sum_{y} p(x,y)\log_2 p(x,y)联合熵代表二维随机对 (X,Y) 的整体平均不确定性。条件自信息量定义为已知事件 y 已经发生在此前提下事件 x 的信息量I(x|y)-\log_2 p(x|y)取数学期望得到条件熵H(X|Y)-\sum_{x}\sum_{y} p(x,y)\log_2 p(x|y)条件熵的物理含义观测到 Y 之后尚且残留的关于 X 的平均不确定度。如果 X 和 Y 完全独立则观测 Y 完全不能降低 X 的不确定性此时 H(X|Y)H(X)如果 Y 可以完全确定 X条件熵直接等于零。熵的链式关系是本章的核心恒等式H(X,Y)H(X)H(Y|X)H(Y)H(X|Y)它清晰地说明两个随机变量总的不确定度可以拆分为先观测一个变量的熵加上已知第一个变量之后剩下的条件熵。例 3-4联合熵简单演算设 X、Y 均为二元联合分布p(0,0)0.25p(0,1)0.25p(1,0)0.25p(1,1)0.25二者独立直接算出H(X,Y)H(X)H(Y)2\ \text{bit}在链式法则的基础之上可以进一步推演出互信息用来刻画两个随机变量之间相互提供的信息量。3.5 N 次扩展离散无记忆信源设原始离散无记忆信源 X把连续输出的 N 个符号当成一个新的大符号构成 N 次扩展信源记作 X^N。扩展信源的符号是长度为 N 的序列\boldsymbol{\alpha}(x_1,x_2,\dots,x_N)因为原始信源无记忆序列联合概率等于各个符号概率直接相乘p(\boldsymbol{\alpha})\prod_{k1}^N p(x_k)对于无记忆信源扩展信源熵满足H(X^N)N\cdot H(X)也就是说长度为 N 的无记忆序列总的平均不确定度等于单符号熵直接乘以序列长度。单位符号的平均熵依旧等于原来的信源熵。这个性质只对无记忆信源严格成立一旦引入记忆该等式不再成立。扩展信源模型的价值在于把单符号理论推广到长序列为信源编码奠定理论基础。信源编码本质上就是对扩展之后的长符号块进行编码利用统计特性压缩冗余。3.6 平稳有记忆信源、极限熵无记忆仅仅是理想假设。对于平稳有记忆信源符号之间互相依赖前面输出的符号会影响后续符号的概率分布。取一段长度为 N 的序列定义长度为 N 的序列熵 H(X_1,X_2,\dots,X_N)进一步定义平均符号熵H_N\frac{1}{N}H(X_1,X_2,\dots,X_N)H_N 的含义把长度为 N 的序列总熵平均分摊到每一个符号上得到单个符号的平均不确定度。随着序列长度不断增大平稳信源的平均符号熵单调非递增并且存在下界。当 N→∞取极限得到极限熵也叫熵率H_\infty\lim_{N\rightarrow\infty} H_N极限熵代表有记忆平稳信源当序列足够长的时候单个符号真正含有的信息也就是信源固有的最小不确定度。由于符号之间存在相关性一部分信息是冗余的平均符号熵随着序列拉长不断下降最终收敛至极限熵。只要信源存在记忆就一定满足H_\infty \le H_N \le H(X)极限熵是一个理论极值。在工程当中不可能直接取无穷长序列但是只要取足够大的 N平均符号熵就可以无限逼近极限熵。信源编码的目标就是去除信源当中由符号相关性带来的冗余让编码之后的输出序列尽可能逼近信源的极限熵用最少的码元承载全部有效信息。本章小结本章全部定理、结论都可以建立严格的数学证明。文中配套二元信源、抛硬币试验等典型例题将抽象公式与其对应的物理含义相互印证把信息度量转化为可直接运算的数学形式是整个信息论的重要理论基石。本章完整建立起一套度量信息不确定性的体系从概率空间定义信源由自信息量过渡到信源熵再推广到联合熵、条件熵利用熵的链式法则建立变量之间的关系通过扩展信源完成从单符号到长序列的过渡最终针对更加贴近现实的平稳有记忆信源引出平均符号熵与极限熵。整套理论是香农三大定理、信源压缩、信道编码的前置基础。