信息论课程设计报告.pdf

信息论课程设计报告 指导老师： 雷 菁 学院： 电子科学与工程学院 队别： 四院五队 姓名： 张 博 学号： 国防科学技术大学电子科学与工程学院 统计信源熵 一． 设计要求 1.统计文件“课程设计大作业 2_处理的对象.txt”的一阶信源熵、二至五阶的联合信 源熵、一至五阶的条件熵。 2.把上述文件中的内容当作一个字符串，编程实现 BWT 和MTF 算法。 3.编程实现BWT 的解码（从 BWT 之后的最后一列和矩阵行数,解码得到原始字符串），并 和原始字符串进行比较,检查解码是否成功。 4.对经过 BWT 之后的最后一列字符串、经过 MTF 处理之后的字符串，再进行上述第 1 项的工作。 5.分析各信源熵的大小及其变化。 二． 思路阐述 （1）各种熵的计算 信息熵 q 1 H X E I a P a ( ) [ ( i )] ∑ ( i )log P a i 1 ( i ) 联合熵 1 q q 1 H X X P x x P a a ( 1 2 ) ∑∑ ( 1 2 )log ∑∑ ( i j )log P x x P a a X 1 X 2 ( 1 2 ) i 1 j 1 ( i j ) 条件熵 强可加性：H(X 1…XN)=H(X 1)+H(X 2|X 1)+…+ H(XN |X 1…XN -1) 因此，由联合熵即可求得条件熵。如：H(X 2|X 1)= H(X 1X 2)-H(X 1)， H(X3 |X 1X2 )= H(X 1…X 3)- H(X 1X 2)…… （2 ）bwt 算法阐述 步骤如下： 信源分块，固定长度字符串； 循环移位，形成置换矩阵； 矩阵各行排序，形成新矩阵； 编两个量：最后一列 + 原字符串的行号。 例如：To be coded: ACUSAB 正方形 矩阵； 行之间：循环移位关系； 列之间：循环移位关系； 新矩阵具有新特性： 最后一列中，相同字符所在的行，它们在矩阵中的先后次序，和第一列中，该字符所在 的行，的先后次序，是一致的。 最后一列中，相同字符所在的行，它们在矩阵中的先后次序， 和第一列中，该字符所在的行，的先后次序，是一致的。 假设把最后一列 移位 到第一列，并重新调节 各新形成的行 的先后次序，则，那些相 同字符所在的行，其先后次序，是不变的。 解码步骤如下： 1 解两个量：最后一列 + 原字符串的行号。 2 由最后一列，排序，得第一列； 3 由第一列和最后一列的字母位置关系，推导出任一行； 4 由原始字符串行号，得之； ******某个字符的下一个字符，是最后一列中，该字符所在行的第一列中的字符； （3 ）MTF 算法