Ayaskt Workspace

Appearance

5 Markov Source and Redundancy ​

字数 9,278｜阅读时间 19 分钟｜Ayaskt
2026/07/07 15:35:34 CST
ゴースト警告を唄う - Empty old City 封面图
Always I’m humming. humming. humming.
我一直低吟，低吟，低吟着，
Can you hear me calling. calling. calling?
你能听见我的呼唤，呼唤，呼唤吗？

「ゴースト警告を唄う」

Empty old City

章节目录 ​

5-1 Markov 信源定义 Definition of Markov Source ​

5-1-1 有限齐次 Markov 链 Finite Homogeneous Markov Chain ​

Markov 性质 Markov Property

若下一状态的概率只由当前状态决定，而与更早的历史状态无关，则称该随机过程满足 Markov 性质 Markov Property。

设状态序列为：

信源输出的符号序列为：

若状态集合有限，记为 ，则从状态 转移到状态 的概率为：

Markov 性质写作：

若转移概率 不随时间 改变，则状态序列构成有限齐次 Markov 链 Finite Homogeneous Markov Chain。

5-1-2 N 维近似与有限记忆 N-D Approximation and Limited Memory ​

维离散平稳有记忆信源可以近似描述实际离散平稳信源。实际信源中，符号之间的统计相关性可能跨越很长的序列，有限维模型只能保留一部分相关性。

设离散信源从符号集合

中随机产生序列：

若采用二维近似，只考虑相邻两个符号构成的消息；若采用三维近似，只考虑相邻三个符号构成的消息。维数越高，保留下来的符号相关性越多。

有限记忆 Limited Memory

若某一时刻发送的符号只与之前有限个符号相关，而与更早发送的符号无关，则该信源具有有限记忆。

当当前符号只与之前 个符号相关时，称该信源的记忆长度 Memory Length 为 。具有记忆长度 的离散平稳信源称为 阶 Markov 信源。

5-1-3 Markov 信源的状态 State of Markov Source ​

设 Markov 信源的字母表为：

若记忆长度为 ，则当前符号只与之前 个符号有关。把这 个历史符号作为信源的状态 State：

其中：

  • ；
  • 状态总数为 。

在下一时刻，信源发送新符号 ，历史窗口向前移动一位：

于是下一状态为：

状态从 转移到 。

5-1-4 状态转移 State Transition ​

Markov 信源的状态空间可写成：

从状态 转移到状态 的概率为：

状态转移由当前状态下发送的新符号决定。若

则：

5-1-5 状态转移图例题 State Transition Graph Examples ​

PROBLEM IT5-E1

给定一阶二元 Markov 信源，其符号发送概率为：

写出状态转移关系。

SOLUTION

alt text

该信源为一阶 Markov 信源，状态就是前一个符号：

因此状态转移关系为：

PROBLEM IT5-E2

给定二阶二元 Markov 信源，其符号发送概率为：

写出状态转移关系。

SOLUTION

alt text

二阶二元 Markov 信源的状态由两个历史符号组成：

发送新符号后，只保留最近两个符号。因此：

5-2 Markov 信源模型 Model of Markov Source ​

5-2-1 状态转移矩阵 State Transition Matrix ​

设状态集合为：

若采用列随机矩阵 Column-stochastic Matrix，状态转移矩阵定义为：

第 列表示从状态 出发，转移到各个状态的概率，因此每一列概率和为 ：

实际计算例题时也常用行随机矩阵 Row-stochastic Matrix：

第 行表示从状态 出发，转移到各个状态的概率。

5-2-2 平稳分布 Stationary Distribution ​

若 Markov 信源齐次且达到平稳状态，则状态分布满足：

记平稳分布为列向量：

若使用列随机矩阵 ，则：

概率还需要满足：

若使用行随机矩阵 ，则把平稳分布写成行向量：

两种写法只差矩阵方向，计算时不要混用。

5-2-3 二阶 Markov 信源矩阵例题 Matrix Example ​

PROBLEM IT5-E3

给定二阶二元 Markov 信源，状态集合为：

符号发送概率为：

写出行随机状态转移矩阵。

SOLUTION

alt text

状态顺序取：

发送 或 后，窗口向前移动一位：

例如状态 下发送 后进入 ，发送 后进入 ，因此第二行为：

5-3 熵率计算 Calculation of Entropy Rate ​

5-3-1 Markov 信源的熵率 Entropy Rate of Markov Source ​

对一般 维有记忆信源，符号相关性由联合概率描述。对 Markov 信源，相关性由状态转移概率描述。

若 Markov 信源的阶数为 ，则第 个符号只与前 个符号相关。其极限熵可写成：

因此， 阶 Markov 信源的熵率等于同阶条件熵：

利用状态表示，可进一步写成：

其中 为 阶 Markov 信源的平稳分布。

5-3-2 一阶 Markov 信源熵率例题 First-Order Example ​

PROBLEM IT5-E4

给定一阶二元 Markov 信源：

alt text

计算该 Markov 信源的熵率。

SOLUTION

取状态集合：

行随机转移矩阵为：

设平稳分布为：

由 与 ：

解得：

状态 下发送新符号的条件熵为：

状态 下：

因此：

5-3-3 二阶 Markov 信源熵率例题 Second-Order Example ​

PROBLEM IT5-E5

给定二阶二元 Markov 信源。令：

alt text

其符号发送概率矩阵为：

其中列顺序为：

计算该信源的熵率。

SOLUTION

由符号发送概率得到行随机状态转移矩阵：

设平稳分布为：

由 ：

解得：

各状态下的条件熵为：

因此：

若按课件中的四舍五入值 计算，则：

5-3-4 熵率计算流程 Calculation Steps ​

Markov 信源熵率计算按以下顺序做：

  1. 由合法符号空间和记忆长度决定状态集合；
  2. 由条件发送概率写出状态转移概率；
  3. 由状态转移矩阵求平稳分布；
  4. 由平稳分布和状态条件熵计算熵率。

公式上就是：

其中：

5-4 信息源冗余 Redundancy of Information Source ​

5-4-1 实际信源建模 Modelling a Practical Source ​

非平稳信源的熵率不一定存在。实际处理中，常把信源近似成 维多符号平稳信源，估计足够大 下的联合概率：

再用平均每符号熵近似熵率：

也可以把实际信源近似成 阶 Markov 信源，此时熵率就是 阶条件熵：

当 增大时，近似会保留更长的历史相关性。各阶熵满足：

其中 对应等概率无记忆信源， 对应单符号概率分布， 对应 阶 Markov 条件熵。

5-4-2 英文信源熵率 English Language Entropy ​

对英文字符序列，可以用不同阶数的 Markov 信源逐步逼近。常见近似值为：

只考虑字符种类数， 加入单字符概率分布， 开始引入相邻字符相关性。英文中存在拼写、词法和语法约束，因此 明显小于 。

5-4-3 冗余度 Redundancy ​

实际信源真正需要传输的信息量由 决定。由于准确的 通常无法直接得到，只能用有限阶 Markov 模型近似。

定义熵效率 Entropy Efficiency：

定义信源冗余度 Source Redundancy：

对英文信源，代入：

因此：

5-4-4 冗余度意义 Meaning of Redundancy ​

信源冗余度反映序列中符号之间依赖关系的强弱。

冗余度越大，实际熵越小，说明符号之间依赖更强，记忆长度更长。冗余度越小，符号之间依赖更弱，记忆长度更短。

较高冗余度会降低传输效率，但也能提高可靠性。传输不理想时，冗余结构可以抵消一部分错误影响。

除特别注明外，本站原创内容采用 CC BY-NC-SA 4.0 协议授权；引用的歌词、课程材料、图片等第三方内容版权归原权利人所有。
Built with VitePress.

Copyright © 2025-present Ayaskt