信息论中有记忆信源的一种数学模型. 还是比较抽象的说

个人笔记与见解, 若有Error或Warning, Notice, 欢迎提issue.

---

马尔可夫信源是什么:

(下文中”前文/后文”均指”当前时刻前的符号/当前时刻的符号”. 这个”符号”就是信息论里承载信息的符号, 可以是任意表示信息的符号)

信息论只研究信息本身的性质, 对信息不区分. 根据有记忆/无记忆, 将信源分为两类. 无记忆信源指的是前后文概率独立. 而有记忆则表明信源前后文相关. 前文会干涉后文内容

比如”今天是个雨天”后跟随”我在家打游戏”的概率高于”我出去打篮球”

将这三个事件记作  使用高端的数学形式表示就是

第一个表示已经出现”情况3″下的概率, 第二个表示连续的信息之间的概率(可以理解为两句话合成的一个消息符号)

这种后文会被前文影响的信源中的一种称之为”马尔可夫信源”. 而”马尔科夫链”指的是类似的对象经历的”过程”. 比如: 用于预测随机事件.

马尔可夫信源的通俗定义: 假如信息序列是这个样子:  ,其  出现的符号概率取决于之前连续的  个符号, 且时齐(概率分布不随时间变化), 则这是个i阶时齐马尔可夫信源. 其记忆深度为  .

有记忆平稳离散信源的信息熵

根据熵的定义, 我们可以发现, 前后文相关必然提升信息的预测性, 降低信息的不确定性, 所以立刻得到有记忆信源的熵低于其假使无记忆时的情形. 翻译成人话就是: 有记忆信源包含冗余, 具备纠错能力且可以进一步压缩. 香农当时举的例子是”一个100页的英语书理论上包含的信息可以只用29页就塞下, 剩下的信息可以根据语法等恢复且不失真. “

信源的状态

这里有一个哲学公理: 你的未来仅取决于你的当下状态. 马尔可夫这么处理任意阶马氏信源:

不管多少阶, 统一将记忆深度内的符号序列看作当前信源的”状态“. 一般记为Q.

举个例子: 二阶二符号时齐马氏信源, 包含两个符号”0″和”1″, 某次信源吐出的序列长这样

……….010100010101110101010100

最后一次吐出的是”0″, 我们将其前面的两个符号(因为是二阶的, 所以记忆深度是2), 也就是”10″看作那时的信源状态. 所以这个信源应该包含4种状态(00, 01, 10, 11)

所以我们可以尝试画一幅信源状态转移图(这幅图一般来源于测试得到的数据, 题目给出的已知值, 等. 总之可以自己很容易的画出来. 如果题都看不懂就回去翻书搞懂那些奇怪的符号的意思)

我随便举个例子, 假如这个图是从什么地方得到的…….(因为用公式表示太占地方, 故省略)

看图知道, 这个信源包含三个符号(状态图中), 记忆深度为1(每个状态只包含一个符合)

(所以你应该已经会由数据画状态图了)

求熵

我们这里求的一般是极限概率, 记为  .含义是: 信源输出趋于无穷时的平均序列熵. 即每个符号所包含的平均信息量.

设符号概率  , 表示在  状态下出现某符号的概率.  表示出现某种状态的概率. 注意这里的x和q是”符号/状态矩阵“, 包含所有的符号和状态, 相应的P也是概率矩阵. 这样写对人类不友好, 但是非常省纸(版面小)

接上文的那张图, 是已知的(这里从图中看出, 或者题目中得到概率然后自己画图, 或者自己测数据等得到概率然后画图), 这里我们要求的值. 方法是列方程

 表示状态的概率, 比如  就表示图中右上角那种状态, 课本上喜欢用  表示, 但是写括号费时间………个人习惯

这个方程的列法应该一下就看懂了, 每个状态的概率应该就是其他状态(包括自身)转移到自己状态的概率和(表述不严谨, 意会即可). 注意到这里应该满足归一化条件:

要不然概率和大于1可还行.

求解得到各种, 然后这么求熵

可以发现马尔可夫信源的信息熵求起来还是比较计算量密集………..

至于这个式子咋来的, 推导比较复杂, 暂且背过吧…我的直观理解就是: 状态概率加权熵的和. 感觉还行.

(完)