信息论与编码 第二章信源及其熵

2.1 信源的数学模型和分类

离散信源

用[X,P]来表示信源,根据 X 的不同,信源分类: | 信息(信号)取值的集合 | 信息(信号)取值时刻的集合 | 信源种类 | | ---------------------- | -------------------------- | ----------------- | | 离散 | 离散 | 离散信源/数字信源 | | 连续 | 连续 | 波形信源/模拟信源 | | 连续 | 离散 | 连续信源 | | 离散 | 连续 | |

(1)单个符号的无记忆信源

​ 特点:输出是单个符号(代码)的消息,符号集的取值 A:{a1,a2,…,aq} 是有限的或可数的,可用一维离散型随机变量 X 来描述。

​ 数学模型: \(\left[ \begin{matrix} X \\ p(x) \end{matrix} \right] = \left[ \begin{matrix} a_1,a_2,…,a_q \\ p(a_1),p(a_2),…,p(a_q) \end{matrix} \right]\) ,并满足 \(\sum_{i=1}^qp(a_i)=1​\)

​ 概率空间能表征离散信源的统计特性,因此也称概率空间为信源空间。

​ 例:投硬币、书信、电报符号等等。

(2)符号序列的离散无记忆信源

​ 特点:信源输出的消息由一系列符号序列所组成,可用 N 维随机矢量 X=(X1,X2,…,XN) 描述。

​ 若随机矢量 X 的各维概率分布都与时间起点无关,即在任意两个不同时刻的各维概率分布相同,则称为离散平稳信源

​ 离散平稳信源发出的符号都相互统计独立,即各随机变量 Xi (i=1,2,…,N)之间统计独立。

​ 独立->P (X)= P (X1, X2, …,XN)= P1(X1) · P2(X2)· · · PN(XN)

​ 平稳-> P1 (Xi) = P2 (Xi)=· · ·= PN (Xi) -> P(X) = P(X1X2…XN) = \(\Pi_{i=1}^NP(X_{i})\)

​ 设随机变量 Xi 取值同样的符号集 A:{a1,a2,…,aq},则

\[P(x=a_i) = P(a_{i1},a_{i2},…,a_{iN}) = \Pi_{k=1}^NP(a_{ik}),i_k = (1,2,…,q)\]

​ 若信源 X 的各输出空间 Xi 间统计独立、且取值同一符合集 A,则 X 为离散无记忆信源,称该信源输出的 N 维随机矢量 X 为离散无记忆信源 X 的 N 次扩展信源。其数学模型是 X 信源空间的 N 重空间,它是由离散无记忆信源输出 N 长的随机序列构成的信源。

​ 例:中文信源、电报等等。

(3)符号序列的离散有记忆信源

​ 信源在不同时刻发出的符号之间是相互依赖的,即信源输出的平稳随机序列 X 中,各随机变量 Xi 之间相互依赖。在 N 维随机矢量的联合概率分布中,引入条件概率分布来说明它们之间的关联:P(xi|…xi+2xi+1xi-1xi-2…xi-m…x1) 。

​ 例:自然语言序列(中、英文)等等。

(4)符号序列的马尔可夫信源

​ 实际中信源发出的符号往往只与靠近的前若干个符号的依赖关系较强,而与更前面的符号序列依赖关系较弱。因此,在分析时可以限制随机序列的记忆长度。当记忆长度为 m+1 时,即信源每次发出的符号只与前面 m 个符号有关,与更前面的符号无关,则称这种有记忆信源为 m 阶马尔可夫信源。此时信源符号之间依赖关系的条件概率为:

​ P(xi|…xi-1xi-2…xi-m…x1) = P(xi|…xi-1xi-2…xi-m)(i=1,…,N)

​ 若上述条件概率又与时间起点 i 无关,那么信源输出的符号序列可看作时齐马尔可夫链,信源为时齐马尔可夫信源。

​ 从任何一个状态出发,可以通过有限步到达其他状态,该马尔可夫链是遍历的。

​ 马尔可夫链的遍历定理:

\(P(s_j)=\sum_{i=1}^{n^m}P(s_i)P(s_j/s_i)\) ,j =1,2,…,nm,0≤P(sj)≤1,且\(\sum_{i=1}^{n^m}P(s_i)\)=1。

​ 遍历的马尔可夫链,最后可以达到稳定,即所有变量 Xk 的概率分布不变。设稳态分布为 Wi,WP=W。(Wi):系统此时处于状态 si 的概率。

连续信源

输出在时间和幅度上都是连续分布的连续消息(模拟消息)的信源。

特点:输出是单个符号(代码)的消息,输出消息的符号集 A 的取值是连续的,可用一维的连续型随机变量 X 来描述。

数学模型:

例:语音信号、热噪声信号、遥控系统中有关电压、温度、压力等测得的连续数据等等。

实际信源输出的消息常常是时间和取值都是连续的。这类信源称为随机波形信源。随机波形信源在某一固定时间 t0 的可能取值是连续和随机的。对于这种信源输出的消息,可用随机过程来描述。

2.2 离散信源的信息熵及其性质

信息的度量(信息量)和不确定性消除的程度有关,消除的不确定性=获得的信息量;不确定性就是随机性,可以用概率论和随机过程来测度,概率小->不确定性大;信息量应该具有可加性。

2.2.1 自信息

离散信源 X 的概率空间: \(\left[ \begin{matrix} X \\ p(x) \end{matrix} \right] = \left[ \begin{matrix} a_1,a_2,…,a_q \\ p(a_1),p(a_2),…,p(a_q) \end{matrix} \right]\)\(\sum_{i=1}^qp(a_i)=1\)

称事件 ai 发生所含有的信息量为 ai 的自信息量,定义为 $I(a_i) = log_r 1{P(a_i)} = -log_rP(a_i) $

I(ai) 代表两种含义:事件 ai 发生以前,表示事件 ai 发生的不确定性;事件 ai 发生以后,表示事件 ai 所提供的信息量。

不确定度:随机事件的不确定度在数量上等于它的自信息量。

2.2.2 联合自信息量

定义:两个消息 xi ,yj 同时出现的联合自信息量 \(I(x_iy_j) = -logP(x_iy_j) ​\)

注意:当 xi,yj 相互独立时,有 P(xiyj) = P(xi)P(yj),即 I(xiyj) = I(xi)+I(yj)

2.2.3 条件自信息量

定义:在事件 yj 出现的条件下,随机事件 xi 发生的概率为 p(xi/yj),它的条件自信息量定义为:\(I(x_i|y_j) = -logP(x_i|y_j) ​\)

注意:在给定 yj 条件下,随机事件 xi 所包含的确定度在数值上与条件自信息量相同,但两者含义不同。

2.2.4 信息熵(平均自信息量)

对一个信源发出不同的消息所含有的信息量也不同。所以自信息 I(ai) 是一个随机变量,不能用它来作为整个信源的信息测度。定义自信息的数学期望为平均自信息量 Hr(X),称为信息熵:

  • 熵是从整个信源集合的统计特性来考虑的,它从平均意义上来表征信源的总体特征。
  • 在信源输出后,信息熵 H(X) 表示每个信息提供的平均信息量。
  • 在信源输出前,信息熵 H(X) 表示信源的平均不确定性。
  • 信息熵 H(X) 表征了变量 X 的随机性。

2.2.5 信息熵的基本性质

已知信源: \(\left[ \begin{matrix} X \\ p(x) \end{matrix} \right] = \left[ \begin{matrix} a_1,a_2,…,a_q \\ p(a_1),p(a_2),…,p(a_q) \end{matrix} \right]​\)\(\sum_{i=1}^qp(a_i)=1​\)

信息熵:\(H(X) = -\sum_i^qP(a_i)log_rP(a_i)​\)

用概率矢量 \(\vec{P}=(p(a_1),…,p(a_q))=(p_1,…,p_q)​\) 来表示信源的概率分布,则信息熵是 \(\vec{P}​\) 的函数,无特殊说明,对数的底可以略去不写。则把 H(X) 写成: \(H(X) = -\sum_i^qP(a_i)logP(a_i) = -\sum_i^qp_ilogp_i = H(p_1,…,p_q)= H(\vec{P})​\)

  1. 对称性

    \(\vec{P}​\) 的值与分量 p1,…,pq 的顺序无关:\(H(p_1,p_2,…,p_q)=H(p_2,p_1,…,p_q)​\)

    从数学角度,\(H(\vec{P})= -\sum_i^qp_ilogp_i\) 的和式满足交换律;

    从随机变量的角度,熵只与随机变量的总体统计特性有关。

  2. 确定性

    \(H(1,0)=H(1,0,0)=H(1,0,0,…,0)=0\)

    从总体来看,信源虽然有不同的输出符号,但它只有一个符号几乎必然出现,而其它符号则是几乎不可能出现,那么,这个信源是一个确知信源,其熵等于零。

  3. 非负性

    \(H(P)≥0\)

    这种非负性合适于离散信源的熵,对连续信源来说这一性质并不存在。非负性体现信息是非负的。

  4. 扩展性

    \(\lim_{\varepsilon\to0}H(p_1,p_2,…,p_q-\varepsilon,\varepsilon)=H(p_1,p_2,…,p_q)​\)

    信源的取值数增多时,若这些取值对应的概率很小(接近于零),则信源的熵不变。

    当某一消息出现概率很小时,虽然它的自信息量很大,但是对信源的平均信息量贡献非常小,体现了熵的总体平均性。

  5. 可加性

    统计独立信源 X 和 Y 的联合信源的熵等于信源 X 和 Y 各自的熵之和。

    H(XY) = H(X) + H(Y)

    因为可加性,使得熵的形式唯一。

  6. 强可加性

    两个互相关联的信源 X 和 Y 的联合信源的熵等于信源 X 的熵加上在 X 已知条件下信源 Y 的条件熵。

    H(XY) = H(X) + H(Y|X)

    H(Y|X) 表示信源 X 输出一符号的条件下,信源 Y 再输出一符号所能提供的平均信息量,称为条件熵。

    \(H(Y|X)=-\sum_{j=1}^m\sum_{i=1}^nP(x_iy_j)logP(y_j|x_i)\)

  7. 递增性

    \(H_{n+m-1}(p_1,p_2,…,p_{n-1},q_1,q_2,…,q_m)=H_n(p_1,p_2,…,p_{n-1},p_n) + p_nH_m(\frac{q_1}{p_n},\frac{q_2}{p_n},…,\frac{q_m}{p_n})\)

    \(\sum_{i=1}^np_i=1,\sum_{j=1}^mq_j=p_n​\)

    例:\[H(\frac{1}{3},\frac{1}{3},\frac{1}{6},\frac{1}{6})\\=H(\frac{1}{3},\frac{1}{3},\frac{1}{3})+\frac{1}{3}H(\frac{1}{2},\frac{1}{2})\\=H(\frac{1}{3},\frac{2}{3})+\frac{2}{3}H(\frac{1}{2},\frac{1}{2})+\frac{1}{3}H(\frac{1}{2},\frac{1}{2})\\=H(\frac{1}{3},\frac{2}{3})+H(\frac{1}{2},\frac{1}{2})​\]

  8. 极值性

最大离散熵定理:在离散信源情况下,信源各符号等概率分布时,熵值达到最大。

\(H(p_1,p_2,…,p_q) ≤H(\frac{1}{q},\frac{1}{q},…,\frac{1}{q})=logq\) ,\(\sum_{i=1}^qp_i=1\)

等概率分布信源的平均不确定性为最大,记作 H0

2.3 离散无记忆信源的扩展信源

当离散平稳无记忆信源信源发出固定长度的消息序列时,则得到原信源的扩展信源 。

离散无记忆信源的 N 次扩展信源就是把简单的单符号信源经 N 次扩展后得到的新信源。

单符号离散信源 X 的数学模型: \(\left[ \begin{matrix} X \\ p(x) \end{matrix} \right] = \left[ \begin{matrix} a_1,a_2,…,a_q \\ p(a_1),p(a_2),…,p(a_q) \end{matrix} \right]​\)\(\sum_{i=1}^qp(a_i)=1​\)

其 N 次扩展信源用 XN 表示,其数学模型:

\(\left[ \begin{matrix} X^N \\ p(\vec{a_i}) \end{matrix} \right] = \left[ \begin{matrix} \vec{a_1},\vec{a_2},…,\vec{a_{q^N}} \\ P(\vec{a_1}),P(\vec{a_2}),…,P(\vec{a_{q^N})} \end{matrix} \right]\)\(\vec{a_i} = (\vec{a_{i_1}},\vec{a_{i_2}},…,\vec{a_{i_N}})\)\(\sum_{i=1}^{q^N}p(\vec{a_i}=1)\)

2.4 离散平稳信源

2.4.1 平稳信源的概念

若信源 X 满足 \(p(x_i)=p(x_j),i≠j​\),该信源的一维概率分布与观察的时间无关,则称该信源 X 为一维平稳信源。

若该信源 X 同时满足二位联合概率分布与时间起点无关,即 \(p(x_ix_{i+1})=p(x_jx_{j+1}),i≠j​\),则称信源 X 为二维平稳信源。

以此类推,若信源的各位概率分布都与时间起点无关,那么就称为离散平稳信源。

对于平稳信源来说,其条件概率均与时间起点无关,只与关联长度 N 有关。即平稳信源发出的平稳随机序列前后的依赖关系与时间起点无关。对平稳信源如果某时刻发出什么符号只与前面发出的N个符号有关,那么任何时刻它们的依赖关系都是一样的。即:

2.4.2 二维平稳信源

已知一个离散二维平稳信源,其概率空间为:

\(\left[ \begin{matrix} X \\ p(x) \end{matrix} \right] = \left[ \begin{matrix} a_1,a_2,…,a_q \\ P(a_1),P(a_2),…,P(a_q) \end{matrix} \right]\)\(\sum_{i=1}^qP(a_i)=1\)

把这个信源输出的随机序列分成每二个符号一组(因为相邻的两个符号才有关联),每组构成新信源的一个符号,并假设组与组之间统计无关(实际上,组尾的符号与下一组组头的符号是有关的)。 这时,等效成一个新的信源 X1X2,它们的联合概率空间为:

下标 2 表示是通过二维平稳信源的符号序列的联合熵求取信源信息熵,所以又称 H2(X) 为二维平稳信源的平均符号熵。H(X) 称为简单符号熵,H(X2|X1) 称为信源 X 的条件熵

2.4.3 一般离散平稳信源

对离散平稳信源若 \(H_1(X)<\infty​\) ,则有以下性质:

  • 条件熵 H(XN/X1X2…XN-1) 随 N 的增加是递减的;
  • HN(X) ≥ H(XN/X1X2…XN-1);
  • 平均符号熵 HN(X) 也是随 N 增加而递减的;
  • 极限熵 \(H_\infty​\) 存在,并且: \(H_\infty=\lim_{N\to\infty}H_N(X)=\lim_{N\to\infty}H(X_N|X_1X_2…X_{N-1})​\),当依赖关系趋于无穷时,平均符号熵和条件熵都递减地一致趋于平稳信源的极限熵。当 N 不是很大时,\(H_{\infty}\approx H_N(X)\approx H( X_N|X_1X_2…X_{N-1})​\)

熵的意义(对通信系统) H(X):表示信源中每个符号的平均信息量(信源熵)。 H(Y):表示信宿中每个符号的平均信息量(信宿熵)。 H(X|Y):表示在输出端接收到 Y 的全部符号后,发送端X尚存的平均不确定性。这个对X尚存的不确定性是由于干扰引起的。信道疑义度(损失熵,含糊度) H(Y|X):表示在已知 X 的全部符号后,对于输出 Y 尚存的平均不确定性。信道散布度(噪声熵) H(XY):表示整个信息传输系统的平均不确定性(联合熵)。

2.4.4 马尔可夫信源

若一个信源满足下面两个条件,则称为马尔可夫信源: (1)某一时刻信源输出的符号的概率只与当前所处的状态有关,而与以前的状态无关; (2)信源的下一个状态由当前状态和下一刻的输出唯一确定。

马尔可夫信源的熵:\(H_\infty =H(X_{m+1}|X_1X_2…X_m)\) 表明 m 阶马尔可夫信源的极限熵等于 m 阶条件熵。根据条件熵公式得:\(H_\infty =H_{m+1}=-\sum_{i=1}^{q^m}\sum_{j=1}^{q^m}p(e_i)p(e_j|e_i)logp(e_j|e_i)\)

2.5 连续信源的信息熵

2.5.1 单符号连续信源的熵

连续信源的熵具有相对性,有时又称为相对熵、或差熵。连续信源的差熵 h(X) 的含义如下:

  • 与离散信源的熵在形式熵保持统一。
  • 在讨论熵之差值时,可将实际熵中的无限大常数项互相抵消掉。
  • 在任何包含有差熵的问题中,上式定义的连续信源的熵具有信息的特性。

连续信源的熵具有以下性质:

即 N 维区域体积内均匀分布连续平稳信源的差熵就是 N 维区域体积的对数。它也等于各变量 Xi 在各自取值区间 [ai,bj] 内均匀分布时的差熵 h(Xi) 之和。因此,无记忆连续平稳信源和无记忆离散平稳信源一样,其差熵也满足:\(h(\vec{X}=h(X_1,X_2,…,X_N)=\sum_{i=1}^Nh(X~i~))​\)

2.5.2 波形信源的熵

令平稳随机矢量为 \(\vec{X}=h(X_1,X_2,…,X_n)​\)\(\vec{Y}=h(Y_1,Y_2,…,Y_n)​\),其联合概率密度为 \(p(\vec{x}\vec{y})​\),则它们的差熵和条件差熵分别为:

对平稳随机过程 {x(t)} 和 {y(t)},其差熵可由平稳随机矢量 \(\vec{X}\)\(\vec{Y}\) 的差熵和条件差熵表达式中令序列长度趋向无穷(n->∞)来得到,即

2.5.3 最大熵定理

  1. 峰值功率受限条件下信源的最大熵

    即信源输出信号的瞬时幅度受限,等价于信源输出信号的幅度被限定在 [a,b] 区域内。此时,当信源输出信号的概率密度分布式均匀分布时,具有最大熵,\(H(X)=log(b-a)\)

  2. 平均功率受限条件下信源的最大熵

    若一个连续信源输出信号的平均功率被限定为 P,则信源输出信号的概率密度分布为高斯分布时,信源具有最大值,为 \(h(X)=\frac12log(2\pi eP)\)

2.6 信源的冗余度

2.6.1 信源效率

信源的熵表示了信源每输出一个符号所携带的信息量,熵值越大,表示信源符号携带信息的效率越高。对于一个具体的信源,它所具有的总信息量是一定的。

有记忆信源中输出符号间的相关长度越长,则信源熵越小。对无记忆信源,信源符号等概率分布时熵最大,其平均自信息量记为: \(H_0=log(q)\):

定义信源效率(熵的相对率)为:\(\eta=\frac{H_\infty}{H_0}\)

它表示一个信源实际的信息熵与具有同样符号集的最大熵的比值。

这一比值反映了实际信源符号之间的相关程度,相关程度越大,则 η 的值越小,即信源效率越低。

2.6.2 信源冗余度

信源符号间的相关性越强,信源中冗余信息越多,信源冗余度越大,信源效率越低,定义信源冗余度为:\(\gamma=1-\eta=1-\frac{H_\infty}{H_0}\)

  1. 冗余度 γ 越大,实际熵 H 越小。说明信源符号之间的依赖关系越强,即符号之间的记忆长度越长。
  2. 冗余度 γ 越小,表明信源符号之间依赖关系越弱,即符号之间的记忆长度越短。
  3. 当冗余度等于零时,信源的信息熵就等于最大值 H0 ,这表明信源符号之间不但统计独立无记忆,而且各符号还是等概率分布。

从提高信息传输效率的角度出发,总是希望减少剩余度(压缩),这是信源编码的作用;从提高信息抗干扰能力来看,总是希望增加或保留剩余度,这是信道编码要达到的目的。

在通信系统中,除了在传输或恢复信息时所必须的最少消息外,其他的符号或系统都是剩余的。

2.7 离散无失真信源编码定理

2.7.1 信源编码的基本概念

离散信源的无失真编码是要将信源输出的离散消息符号变换成适合于信道传输的信道基本符号。

信源压缩编码实质:对信源输出的原始符号按一定规则进行变换,以新的编码符号代替原始信源符号,从而降低原始信源的冗余度。

编码:从信源符号到码符号组成的码字之间的一种映射。

无失真编码:这种映射是一一对应的,要求码是唯一可译码。

唯一可译码:码的任意一串有限长的符号序列只能被唯一地译成所对应的信源符号。

若各码字的码长相同,则称为等长编码;不同,则称为变长编码

对 N 次扩展信源 SN 中的符号 \(\vec{a_i}​\) 进行编码的码长为 \(l_i​\) ,则对 SN 中所有符号 \(\vec{a_i}​\) 进行编码的平均码长为: \(\vec{L_N}=\sum_{i=1}^{q^N}P(\vec{a_i})l_i​\) (r 元码符号 / N 个信源符号)

等价地对原始信源 S 中的各符号编码的平均码长为: \(\frac{\vec{L_N}}{N}​\)

所以,对 SN 进行无失真编码后得到一个由码符号组成的新信源 X,\(η = H(X)=\frac{H(S)}{\vec{L_N}/N}​\) (bit /码符号),同时称 η 为改码的编码效率。

2.7.2 香农第一定理

香农第一定理(无失真变长信源编码定理):

离散无记忆信源 S 的 N 次扩展信源 \(S^N = \{a_1, a_2 ,…, a_{q^N} \}​\) ,其熵为 H(SN),并有码符号 X ={x1, x2, …, xr}。对信源 SN 进行编码,总可以找到一种编码方法,构成惟一可译码,使信源 S 中每个信源符号所需的平均码长满足:\(\frac{H(S)}{logr}+\frac{1}{N}>\frac{\overline{L_N}}{N}≥\frac{H(S)}{logr}​\)

\(\overline{L_N}\) S是对 SN 中扩展信源符号的平均码长,\(\frac{\overline{L_N}}{N}\) 为对 SN 进行编码后,信源符号的平均码长。

香农第一定理说明:

  • 要做到无失真的信源编码,每个信源符号平均所需最少的 r 元码元数为信源的熵 Hr(S) ,即Hr(S) 是无失真信源压缩的极限值。

  • 若编码的平均码长小于信源的熵值 Hr(S) ,则惟一可译码不存在,在译码或反变换时必然要带来失真或差错。

  • 通过对扩展信源进行变长编码,当 N->∞ 时,平均码长 ->Hr(S) 。

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×