信息论讲义教材

安德雷·马尔可夫(AndreiMarkov1856－1922），俄国数学家。1874年马尔可夫入圣彼得堡大学，师从切比雪夫，1886年当选为圣彼得堡科学院院士。开创了随机过程这个新的领域，以他的名字命名的马尔可夫链在现代工程、自然科学和社会科学各个领域都有很广泛的应用。马尔可夫性：一个过程的“将来”仅依赖“现在”而不依赖“过去”

马尔可夫链的应用排队理论和统计学中的建模，还可作为信号模型用于熵编码技术，如算术编码著名的LZMA数据压缩算法就使用了马尔可夫链与类似于算术编码的区间编码。生物学应用，人口过程，可以帮助模拟生物人口过程的建模。隐蔽马尔可夫模型还被用于生物信息学，用以编码区域或基因预测。马尔可夫链最近的应用是在地理统计学（geostatistics）中,被称为是“马尔可夫链地理统计学”。仍在发展过程中。“基于马尔可夫链的我国城乡居民收入演进分析”

信源剩余度与自然语言的熵离散平稳信源m阶Markov信源一阶Markov信源实际信源离散无记忆信源等概的离散无记忆信源实际信源可能是非平稳的有记忆随机序列信源，其极限熵H∞不存在。解决的方法是假设其为离散平稳随机序列信源，极限熵存在，但求解困难；1、关于离散信源熵的总结

进一步假设其为m阶Markov信源，用其m阶条件熵Hm+1来近似，近似程度的高低取决于记忆长度m的大小；最简单的是记忆长度m=1的马尔可夫信源，其熵Hm+1=H2=H(X2|X1)

再进一步简化，可设信源为无记忆信源，信源符号有一定的概率分布。这时可用信源的平均自信息量H1=H(X)来近似。

最后可假定是等概分布的离散无记忆信源，用最大熵H0

来近似。HNHm+1H2H1H0H∞①实际信源近似为平稳信源

实际信源可能是非平稳的，极限熵H∞不一定存在。 假设它是平稳的，测得N足够大时的条件概率P(XN/X1X2…XN-1)，再计算出平均符号熵HN(X)，近似极限熵H∞

。②离散平稳信源近似为马尔可夫信源计算N足够大时的HN(X)往往也十分困难，可进一步假设离散平稳信源是m阶马尔可夫信源。信源熵用m阶马尔可夫信源的熵Hm+1来近似，需要测定的条件概率要少的多。近似程度的高低取决于记忆长度m。越接近实际信源，m值越大；反之对信源简化的越多，m值越小。最简单的马尔可夫信源记忆长度m=1，信源熵H2=

H1+1=H(X2/X1)。当m=0时，信源变为离散无记忆信源，其熵可用H1(X)表示。继续简化，假定信源是等概率分布的无记忆离散信源，这种信源的熵就是最大熵值H0(X)=log2n。信源符号的相关性与提供的平均信息量

把多符号离散信源都用马尔可夫信源来逼近，则记忆长度不同，熵值就不同，意味着平均每发一个符号就有不同的信息量。log2n=H0≥H1≥H2≥…≥Hm≥H∞

由此可见，由于信源符号间的依赖关系使信源的熵减小。如果它们的前后依赖关系越长，则信源的熵越小。并且仅当信源符号间彼此无依赖、等概率分布时，信源的熵才最大，即信源符号的相关性越强，提供的平均信息量越小。为此，引进信源的冗余度来衡量信源的相关性程度(有时也称为多余度或剩余度)。冗余度与结构信息1、冗余度冗余压缩信息论的创始人Shannon提出把数据看作是信息和冗余度（redundancy）的组合。如在一份计算机文件中，某些符号会重复出现、某些符号比其他符号出现得更频繁、某些字符总是在各数据块中可预见的位置上出现等，这些冗余部分便可在数据编码中除去或减少。相邻的数据之间存在着相关性。如图片中常常有色彩均匀的背影，电视信号的相邻两帧之间可能只有少量的变化影物是不同的，声音信号有时具有一定的规律性和周期性等等。人们由于耳、目对信号的时间变化和幅度变化的感受能力都有一定的极限信源编码可利用一些编码的方法删去它们，从而达到减少冗余压缩数据的目的。图像压缩编码(1)无损压缩编码(2)有损压缩编码(3)混合编码，如H261，JPEG，MPEG等技术标准简单地说，如果没有数据压缩技术，我们就没法用WinRAR为Email中的附件瘦身；如果没有数据压缩技术，市场上的数码录音笔就只能记录不到20分钟的语音；如果没有数据压缩技术，从Internet上下载一部电影也许要花半年的时间衡量一个压缩编码方法优劣的重要指标(1)压缩比要高；(2)算法简单，硬件实现容易；(3)解压缩的图像质量要好。冗余纠错信道编码信道前向纠错编码（FEC）技术通过在传输码列中加入冗余纠错码，在一定条件下，通过解码可以自动纠正传输误码，降低接收信号的误码率（BER）。衡量FEC纠错能力的指标称为“FEC编码增益”，该增益越强表示纠错性能越强。汉明码、奇偶校验码、RS码、Turbo码、LDPC等纠错性能、码率、实现复杂度中华人民共和国中国*华人民*和国*国2、熵的相对率

——信源实际的信息熵与具有同样符号集的最大熵的比值

（q为符号数）3、信源剩余度第七节信源剩余度与自然语言的熵H0：相同符号数的最大值定义信源的m阶极限熵Hm+1与N-1阶极限熵H∞的相对差为该信源的冗余度，也叫剩余度。表示信源的冗余度表示信源可以被压缩的程度*信源剩余度第七节信源剩余度与自然语言的熵

可见，信源冗余度的大小能很好地反映离散信源输出的符号序列中符号之间依赖关系的强弱。冗余度越大，表示信源的实际熵H∞越小。这表明信源符号之间的依赖关系越强，即符号之间的记忆长度越长。反之，冗余度越小，这表明信源符号之间依赖关系越弱，即符号之间的记忆长度越短。当冗余度等于零时，信源的信息熵就等于极大值H0

，这表明信源符号之间不但统计独立无记忆，而且各符号还是等概率分布。所以冗余度可用来衡量信源输出的符号序列中各符号之间的依赖程度。①把英语看成是离散无记忆信源英语字母26个，加上一个空格，共27个符号。英语信源的最大熵(等概率)H0=log227=4.76(比特/符号)英语字母并非等概率出现，字母之间有严格的依赖关系。对英文书写中27个符号出现的概率统计结果如下表。4、自然语言的熵如果不考虑符号间的依赖关系，近似认为信源是离散无记忆的，则信源熵为按上表的概率分布，随机选择英语字母排列起来，得到一个输出序列：AI_NGAE_ITE_NNR_ASAEV_OTE_BAINTHA_HYROO_PORE_SETRYGAIETRWCO_EHDUARU_EUEU_C_FT_NSREM_DIY_EESE_F_O_SRIS_R_UNNASHOR…这个序列看起来有点像英语，但不是。实际英语的某个字母出现后，后面的字母并非完全随机出现，而是满足一定关系的条件概率分布。例如T后面出现H,R的可能性较大，出现J,K,M,N的可能性极小，而根本不会出现Q,F,X。即英语字母之间有强烈的依赖性。上述序列仅考虑了字母出现的概率，忽略了依赖关系。无记忆信源的熵：②把英语看成马尔可夫信源为了进一步逼近实际情况，可把英语信源近似看做1阶，2阶，…∞阶马尔可夫信源，它们的熵为H2=3.32(比特/符号)H3=3.1(比特/符号)若把英语信源近似成2阶马尔可夫信源，可得到某个输出序列：IANKS_CAN_OU_ANG_RLER_THTTED_OF_TO_SHOR_OF_TO_HAVEMEM_A_I_MAND_AND_BUT_WHISS_ITABLY_THERVEREER…这个序列中被空格分开的两字母或三字母，组成的大都是有意义的英语单词，而四个以上字母组成的“单词”，很难从英语词典中查到。因为该序列仅考虑了3个以下字母之间的依赖关系。实际英语字母之间的关系延伸到更多的符号，单词之间也有依赖关系。有依赖关系的字母数越多，即马尔可夫信源的阶数越高，输出的序列就越接近于实际情况。当依赖关系延伸到无穷远时，信源输出的就是真正的英语，此时可求出马尔可夫的极限熵

H∞=1.4(比特/符号)。（2）对于中文写英语文章时，71%是由语言结构定好的，只有29%是写文字的人可以自由选择的。100页的书，大约只传输29页就可以了，其余71页可以压缩掉。信息的剩余度表示信源可压缩的程度。从提高传输效率的观点出发，总是希望减少或去掉剩余度。剩余度大的消息抗干扰能力强。能通过前后字之间的关联纠正错误。（1）对于英文字母信源剩余度4、自然语言的熵

第七节信源剩余度与自然语言的熵

从提高传输信息效率的观点出发，总是希望减少或去掉冗余度。例如把“中华人民共和国”压缩成“中国”；“母亲病愈，身体健康”压缩为“母病愈”。这样原意并没变，而电文变得简洁，冗余度大大减少。

4、自然语言的熵

第七节信源剩余度与自然语言的熵

但是冗余度大的消息具有强的抗干扰能力。当干扰使消息在传输过程中出现错误时，我们能从它的上下关联中纠正错误。 例如，当收到电文为“中×人民×和国”、“母亲病×，身体健康”时，我们很容易把它纠正。 但若发的是压缩后的电文”中国”和“母病愈”，那么当接收电文为”×国”和“母病×”时，就很难肯定所发的电文。由此将会造成很大的错误。所以，从提高抗干扰能力角度看，总希望增加或保留信源的冗余度。5、通信效率与可靠性的关系信源编码就是通过减少或消除剩余度来提高通信效率。信道编码是通过增加剩余度来提高通信的抗干扰能力，即提高通信的可靠性。通信的效率问题和可靠性问题往往是一对矛盾。补充：InformationHidingTechniques

文本隐写文本是一种使用非常广泛的数据形式，比图片等数据形式的使用更为频繁，使用的领域也更为宽广。文本隐写工具：Ffencode、WbStego、ByteShelter、Snow、加密奇兵、InfriHide、Crypto123、Stego、Texto、SamsBigPlayMaker、Nicetext、TextHide。隐写术(Steganography)，也称为信息隐藏技术。该技术是将秘密信息隐藏在其他载体信息中，通过载体的存储与传输来实现秘密信息的保存与传递。隐写术使秘密信息能很好地避免第三方的注意，从而比单纯使用传统加密技术能更有效地保障秘密信息存储与传递的安全。基于网络聊天的文本隐写算法隐写术(steganography)

随着计算机的普及应用和互联网的飞速发展，在网络环境下如何安全隐密的通信成为重要的研究方向．隐写术(steganography)是实现隐密通信的重要手段，它将秘密信息隐藏在载体数据中进行传递，除了约定的通信接收方，秘密信息不易被他人察觉。补充：文本隐写技术法轮功的信息传递：使用文本隐写工具软件Snow。该软件使用公开对称加密算法ICE对秘密信息进行加密，再使用基于行末不可见字符的文本隐写方法把秘密信息隐藏在文本中。这种使用隐写技术传递隐秘信息的方法使得政府许多常规侦察方法失去效果，从而使得相关职能部门对这些不法分子进行的不法活动更加难以采取预防措施，给国家安全、社会稳定和经济的发展带来了严峻的挑战。补充：文本隐写技术隐写术按载体分类，可分为图像信息隐藏、视频信息隐藏、音频信息隐藏、文本信息隐藏等。文本中的冗余信息非常有限，所以文本隐写所用的方法与其他几类载体中使用的隐写方法往往截然不同。补充：文本隐写技术文本隐写算法分类：1)图像文本中的隐写技术该类方法针对以图像格式保存的文本或印刷文本进行信息隐藏，主要是利用图像文本的特点，使用图像处理技术来进行信息隐藏。补充：文本隐写技术2)基于不可见字符的文本隐写技术这类方法通过对文本中的不可见字符进行添加、删除、替换等操作来进行信息隐藏，这些不可见字符主要包括文本中显示为空白的字符或某些情况下不显示的字符，如空格可以被加载在句末或行末等位置而不会显著改变文本的外观。最早用于非格式化文本的隐写方法就是该类方法中的行末空格编码方法。补充：文本隐写技术3)基于字体格式的文本隐写技术该类方法利用人类视觉系统对字体格式的微量变化不敏感的特性进行信息隐藏。即在格式文本中，微量的改变字、行等文本元素的格式信息不会显著改变文本的外观，可以通过这种微量修改进行隐藏信息编码。如基于行移的文本隐写方法、基于字移的文本隐写方法、基于字体颜色的文本隐写方法等。该类方法的视觉隐蔽性好、信息隐藏容量大、不会破坏载体的语义，但是比较脆弱。经过重新排版就能抹除嵌入的信息补充：文本隐写技术4)基于文件格式的文本隐写技术该类方法利用文件格式中通常允许存在一定冗余的特性，在文件格式中加入一些隐藏的信息。比如附加编码法，是在文件中附加经过编码后的隐藏信息；PDF注释法，是在PDF文件格式的注释部分加入编码后的隐藏信息等。补充：文本隐写技术5）文本剩余度的计算

将每一个被检测的文本都当作一个独立的m阶时齐遍历马尔可夫信源，以该文本中的单词作为信源符号；即检测方法只考虑每一篇文本内部单词间的关系，而不将该文本与其所属的语种的总体特征进行对比。