lzw编译码平均码长和信息熵

㈠ 数据压缩技术的数据压缩技术简史

电脑里的数据压缩其实类似于美眉们的瘦身运动，不外有两大功用。第一，可以节省空间。拿瘦身美眉来说，要是八个美眉可以挤进一辆出租车里，那该有多省钱啊！第二，可以减少对带宽的占用。例如，我们都想在不到 100Kbps 的 GPRS 网上观看 DVD 大片，这就好比瘦身美眉们总希望用一尺布裁出七件吊带衫，前者有待于数据压缩技术的突破性进展，后者则取决于美眉们的恒心和毅力。
简单地说，如果没有数据压缩技术，我们就没法用 WinRAR 为 Email 中的附件瘦身；如果没有数据压缩技术，市场上的数码录音笔就只能记录不到 20 分钟的语音；如果没有数据压缩技术，从 Internet 上下载一部电影也许要花半年的时间……可是这一切究竟是如何实现的呢？数据压缩技术又是怎样从无到有发展起来的呢？ 一千多年前的中国学者就知道用“班马”这样的缩略语来指代班固和司马迁，这种崇尚简约的风俗一直延续到了今天的 Internet 时代：当我们在 BBS 上用“ 7456 ”代表“气死我了”，或是用“ B4 ”代表“ Before ”的时候，我们至少应该知道，这其实就是一种最简单的数据压缩呀。
严格意义上的数据压缩起源于人们对概率的认识。当我们对文字信息进行编码时，如果为出现概率较高的字母赋予较短的编码，为出现概率较低的字母赋予较长的编码，总的编码长度就能缩短不少。远在计算机出现之前，着名的 Morse 电码就已经成功地实践了这一准则。在 Morse 码表中，每个字母都对应于一个唯一的点划组合，出现概率最高的字母 e 被编码为一个点“ . ”，而出现概率较低的字母 z 则被编码为“ --.. ”。显然，这可以有效缩短最终的电码长度。
信息论之父 C. E. Shannon 第一次用数学语言阐明了概率与信息冗余度的关系。在 1948 年发表的论文“通信的数学理论（ A Mathematical Theory of Communication ）”中， Shannon 指出，任何信息都存在冗余，冗余大小与信息中每个符号（数字、字母或单词）的出现概率或者说不确定性有关。 Shannon 借鉴了热力学的概念，把信息中排除了冗余后的平均信息量称为“信息熵”，并给出了计算信息熵的数学表达式。这篇伟大的论文后来被誉为信息论的开山之作，信息熵也奠定了所有数据压缩算法的理论基础。从本质上讲，数据压缩的目的就是要消除信息中的冗余，而信息熵及相关的定理恰恰用数学手段精确地描述了信息冗余的程度。利用信息熵公式，人们可以计算出信息编码的极限，即在一定的概率模型下，无损压缩的编码长度不可能小于信息熵公式给出的结果。
有了完备的理论，接下来的事就是要想办法实现具体的算法，并尽量使算法的输出接近信息熵的极限了。当然，大多数工程技术人员都知道，要将一种理论从数学公式发展成实用技术，就像仅凭一个 E=mc 2 的公式就要去制造核武器一样，并不是一件很容易的事。 设计具体的压缩算法的过程通常更像是一场数学游戏。开发者首先要寻找一种能尽量精确地统计或估计信息中符号出现概率的方法，然后还要设计一套用最短的代码描述每个符号的编码规则。统计学知识对于前一项工作相当有效，迄今为止，人们已经陆续实现了静态模型、半静态模型、自适应模型、 Markov 模型、部分匹配预测模型等概率统计模型。相对而言，编码方法的发展历程更为曲折一些。
1948 年， Shannon 在提出信息熵理论的同时，也给出了一种简单的编码方法—— Shannon 编码。 1952 年， R. M. Fano 又进一步提出了 Fano 编码。这些早期的编码方法揭示了变长编码的基本规律，也确实可以取得一定的压缩效果，但离真正实用的压缩算法还相去甚远。
第一个实用的编码方法是由 D. A. Huffman 在 1952 年的论文“最小冗余度代码的构造方法（ A Method for the Construction of Minimum Rendancy Codes ）”中提出的。直到今天，许多《数据结构》教材在讨论二叉树时仍要提及这种被后人称为 Huffman 编码的方法。 Huffman 编码在计算机界是如此着名，以至于连编码的发明过程本身也成了人们津津乐道的话题。据说， 1952 年时，年轻的 Huffman 还是麻省理工学院的一名学生，他为了向老师证明自己可以不参加某门功课的期末考试，才设计了这个看似简单，但却影响深远的编码方法。
Huffman 编码效率高，运算速度快，实现方式灵活，从 20 世纪 60 年代至今，在数据压缩领域得到了广泛的应用。例如，早期 UNIX 系统上一个不太为现代人熟知的压缩程序 COMPACT 实际就是 Huffman 0 阶自适应编码的具体实现。 20 世纪 80 年代初， Huffman 编码又出现在 CP/M 和 DOS 系统中，其代表程序叫 SQ 。今天，在许多知名的压缩工具和压缩算法（如 WinRAR 、 gzip 和 JPEG ）里，都有 Huffman 编码的身影。不过， Huffman 编码所得的编码长度只是对信息熵计算结果的一种近似，还无法真正逼近信息熵的极限。正因为如此，现代压缩技术通常只将 Huffman 视作最终的编码手段，而非数据压缩算法的全部。
科学家们一直没有放弃向信息熵极限挑战的理想。 1968 年前后， P. Elias 发展了 Shannon 和 Fano 的编码方法，构造出从数学角度看来更为完美的 Shannon-Fano-Elias 编码。沿着这一编码方法的思路， 1976 年， J. Rissanen 提出了一种可以成功地逼近信息熵极限的编码方法——算术编码。 1982 年， Rissanen 和 G. G. Langdon 一起改进了算术编码。之后，人们又将算术编码与 J. G. Cleary 和 I. H. Witten 于 1984 年提出的部分匹配预测模型（ PPM ）相结合，开发出了压缩效果近乎完美的算法。今天，那些名为 PPMC 、 PPMD 或 PPMZ 并号称压缩效果天下第一的通用压缩算法，实际上全都是这一思路的具体实现。
对于无损压缩而言， PPM 模型与算术编码相结合，已经可以最大程度地逼近信息熵的极限。看起来，压缩技术的发展可以到此为止了。不幸的是，事情往往不像想象中的那样简单：算术编码虽然可以获得最短的编码长度，但其本身的复杂性也使得算术编码的任何具体实现在运行时都慢如蜗牛。即使在摩尔定律大行其道， CPU 速度日新月异的今天，算术编码程序的运行速度也很难满足日常应用的需求。没办法，如果不是后文将要提到的那两个犹太人，我们还不知要到什么时候才能用上 WinZIP 这样方便实用的压缩工具呢。 逆向思维永远是科学和技术领域里出奇制胜的法宝。就在大多数人绞尽脑汁想改进 Huffman 或算术编码，以获得一种兼顾了运行速度和压缩效果的“完美”编码的时候，两个聪明的犹太人 J. Ziv 和 A. Lempel 独辟蹊径，完全脱离 Huffman 及算术编码的设计思路，创造出了一系列比 Huffman 编码更有效，比算术编码更快捷的压缩算法。我们通常用这两个犹太人姓氏的缩写，将这些算法统称为 LZ 系列算法。
按照时间顺序， LZ 系列算法的发展历程大致是： Ziv 和 Lempel 于 1977 年发表题为“顺序数据压缩的一个通用算法（ A Universal Algorithm for Sequential Data Compression ）”的论文，论文中描述的算法被后人称为 LZ77 算法。 1978 年，二人又发表了该论文的续篇“通过可变比率编码的独立序列的压缩（ Compression of Indivial Sequences via Variable Rate Coding ）”，描述了后来被命名为 LZ78 的压缩算法。 1984 年， T. A. Welch 发表了名为“高性能数据压缩技术（ A Technique for High Performance Data Compression ）”的论文，描述了他在 Sperry 研究中心（该研究中心后来并入了 Unisys 公司）的研究成果，这是 LZ78 算法的一个变种，也就是后来非常有名的 LZW 算法。 1990 年后， T. C. Bell 等人又陆续提出了许多 LZ 系列算法的变体或改进版本。
说实话， LZ 系列算法的思路并不新鲜，其中既没有高深的理论背景，也没有复杂的数学公式，它们只是简单地延续了千百年来人们对字典的追崇和喜好，并用一种极为巧妙的方式将字典技术应用于通用数据压缩领域。通俗地说，当你用字典中的页码和行号代替文章中每个单词的时候，你实际上已经掌握了 LZ 系列算法的真谛。这种基于字典模型的思路在表面上虽然和 Shannon 、 Huffman 等人开创的统计学方法大相径庭，但在效果上一样可以逼近信息熵的极限。而且，可以从理论上证明， LZ 系列算法在本质上仍然符合信息熵的基本规律。
LZ 系列算法的优越性很快就在数据压缩领域里体现 了 出来，使用 LZ 系列算法的工具软件数量呈爆炸式增长。 UNIX 系统上最先出现了使用 LZW 算法的 compress 程序，该程序很快成为了 UNIX 世界的压缩标准。紧随其后的是 MS-DOS 环境下的 ARC 程序，以及 PKWare 、 PKARC 等仿制品。 20 世纪 80 年代，着名的压缩工具 LHarc 和 ARJ 则是 LZ77 算法的杰出代表。
今天， LZ77 、 LZ78 、 LZW 算法以及它们的各种变体几乎垄断了整个通用数据压缩领域，我们熟悉的 PKZIP 、 WinZIP 、 WinRAR 、 gzip 等压缩工具以及 ZIP 、 GIF 、 PNG 等文件格式都是 LZ 系列算法的受益者，甚至连 PGP 这样的加密文件格式也选择了 LZ 系列算法作为其数据压缩的标准。
没有谁能否认两位犹太人对数据压缩技术的贡献。我想强调的只是，在工程技术领域，片面追求理论上的完美往往只会事倍功半，如果大家能像 Ziv 和 Lempel 那样，经常换个角度来思考问题，没准儿你我就能发明一种新的算法，就能在技术方展史上扬名立万呢。 LZ 系列算法基本解决了通用数据压缩中兼顾速度与压缩效果的难题。但是，数据压缩领域里还有另一片更为广阔的天地等待着我们去探索。 Shannon 的信息论告诉我们，对信息的先验知识越多，我们就可以把信息压缩得越小。换句话说，如果压缩算法的设计目标不是任意的数据源，而是基本属性已知的特种数据，压缩的效果就会进一步提高。这提醒我们，在发展通用压缩算法之余，还必须认真研究针对各种特殊数据的专用压缩算法。比方说，在今天的数码生活中，遍布于数码相机、数码录音笔、数码随身听、数码摄像机等各种数字设备中的图像、音频、视频信息，就必须经过有效的压缩才能在硬盘上存储或是通过 USB 电缆传输。实际上，多媒体信息的压缩一直是数据压缩领域里的重要课题，其中的每一个分支都有可能主导未来的某个技术潮流，并为数码产品、通信设备和应用软件开发商带来无限的商机。
让我们先从图像数据的压缩讲起。通常所说的图像可以被分为二值图像、灰度图像、彩色图像等不同的类型。每一类图像的压缩方法也不尽相同。
传真技术的发明和广泛使用促进了二值图像压缩算法的飞速发展。 CCITT （国际电报电话咨询委员会，是国际电信联盟 ITU 下属的一个机构）针对传真类应用建立了一系列图像压缩标准，专用于压缩和传递二值图像。这些标准大致包括 20 世纪 70 年代后期的 CCITT Group 1 和 Group 2 ， 1980 年的 CCITT Group 3 ，以及 1984 年的 CCITT Group 4 。为了适应不同类型的传真图像，这些标准所用的编码方法包括了一维的 MH 编码和二维的 MR 编码，其中使用了行程编码（ RLE ）和 Huffman 编码等技术。今天，我们在办公室或家里收发传真时，使用的大多是 CCITT Group 3 压缩标准，一些基于数字网络的传真设备和存放二值图像的 TIFF 文件则使用了 CCITT Group 4 压缩标准。 1993 年， CCITT 和 ISO （国际标准化组织）共同成立的二值图像联合专家组（ Joint Bi-level Image Experts Group ， JBIG ）又将二值图像的压缩进一步发展为更加通用的 JBIG 标准。
实际上，对于二值图像和非连续的灰度、彩色图像而言，包括 LZ 系列算法在内的许多通用压缩算法都能获得很好的压缩效果。例如，诞生于 1987 年的 GIF 图像文件格式使用的是 LZW 压缩算法， 1995 年出现的 PNG 格式比 GIF 格式更加完善，它选择了 LZ77 算法的变体 zlib 来压缩图像数据。此外，利用前面提到过的 Huffman 编码、算术编码以及 PPM 模型，人们事实上已经构造出了许多行之有效的图像压缩算法。
但是，对于生活中更加常见的，像素值在空间上连续变化的灰度或彩色图像（比如数码照片），通用压缩算法的优势就不那么明显了。幸运的是，科学家们发现，如果在压缩这一类图像数据时允许改变一些不太重要的像素值，或者说允许损失一些精度（在压缩通用数据时，我们绝不会容忍任何精度上的损失，但在压缩和显示一幅数码照片时，如果一片树林里某些树叶的颜色稍微变深了一些，看照片的人通常是察觉不到的），我们就有可能在压缩效果上获得突破性的进展。这一思想在数据压缩领域具有革命性的地位：通过在用户的忍耐范围内损失一些精度，我们可以把图像（也包括音频和视频）压缩到原大小的十分之一、百分之一甚至千分之一，这远远超出了通用压缩算法的能力极限。也许，这和生活中常说的“退一步海阔天空”的道理有异曲同工之妙吧。
这种允许精度损失的压缩也被称为有损压缩。在图像压缩领域，着名的 JPEG 标准是有损压缩算法中的经典。 JPEG 标准由静态图像联合专家组（ Joint Photographic Experts Group ， JPEG ）于 1986 年开始制定， 1994 年后成为国际标准。 JPEG 以离散余弦变换（ DCT ）为核心算法，通过调整质量系数控制图像的精度和大小。对于照片等连续变化的灰度或彩色图像， JPEG 在保证图像质量的前提下，一般可以将图像压缩到原大小的十分之一到二十分之一。如果不考虑图像质量， JPEG 甚至可以将图像压缩到“无限小”。
JPEG 标准的最新进展是 1996 年开始制定， 2001 年正式成为国际标准的 JPEG 2000 。与 JPEG 相比， JPEG 2000 作了大幅改进，其中最重要的是用离散小波变换（ DWT ）替代了 JPEG 标准中的离散余弦变换。在文件大小相同的情况下， JPEG 2000 压缩的图像比 JPEG 质量更高，精度损失更小。作为一个新标准， JPEG 2000 暂时还没有得到广泛的应用，不过包括数码相机制造商在内的许多企业都对其应用前景表示乐观， JPEG 2000 在图像压缩领域里大显身手的那一天应该不会特别遥远。
JPEG 标准中通过损失精度来换取压缩效果的设计思想直接影响了视频数据的压缩技术。 CCITT 于 1988 年制定了电视电话和会议电视的 H.261 建议草案。 H.261 的基本思路是使用类似 JPEG 标准的算法压缩视频流中的每一帧图像，同时采用运动补偿的帧间预测来消除视频流在时间维度上的冗余信息。在此基础上， 1993 年， ISO 通过了动态图像专家组（ Moving Picture Experts Group ， MPEG ）提出的 MPEG-1 标准。 MPEG-1 可以对普通质量的视频数据进行有效编码。我们现在看到的大多数 VCD 影碟，就是使用 MPEG-1 标准来压缩视频数据的。
为了支持更清晰的视频图像，特别是支持数字电视等高端应用， ISO 于 1994 年提出了新的 MPEG-2 标准（相当于 CCITT 的 H.262 标准）。 MPEG-2 对图像质量作了分级处理，可以适应普通电视节目、会议电视、高清晰数字电视等不同质量的视频应用。在我们的生活中，可以提供高清晰画面的 DVD 影碟所采用的正是 MPEG-2 标准。
Internet 的发展对视频压缩提出了更高的要求。在内容交互、对象编辑、随机存取等新需求的刺激下， ISO 于 1999 年通过了 MPEG-4 标准（相当于 CCITT 的 H.263 和 H.263+ 标准）。 MPEG-4 标准拥有更高的压缩比率，支持并发数据流的编码、基于内容的交互操作、增强的时间域随机存取、容错、基于内容的尺度可变性等先进特性。 Internet 上新兴的 DivX 和 XviD 文件格式就是采用 MPEG-4 标准来压缩视频数据的，它们可以用更小的存储空间或通信带宽提供与 DVD 不相上下的高清晰视频，这使我们在 Internet 上发布或下载数字电影的梦想成为了现实。
就像视频压缩和电视产业的发展密不可分一样，音频数据的压缩技术最早也是由无线电广播、语音通信等领域里的技术人员发展起来的。这其中又以语音编码和压缩技术的研究最为活跃。自从 1939 年 H. Dudley 发明声码器以来，人们陆续发明了脉冲编码调制（ PCM ）、线性预测（ LPC ）、矢量量化（ VQ ）、自适应变换编码（ ATC ）、子带编码（ SBC ）等语音分析与处理技术。这些语音技术在采集语音特征，获取数字信号的同时，通常也可以起到降低信息冗余度的作用。像图像压缩领域里的 JPEG 一样，为获得更高的编码效率，大多数语音编码技术都允许一定程度的精度损失。而且，为了更好地用二进制数据存储或传送语音信号，这些语音编码技术在将语音信号转换为数字信息之后又总会用 Huffman 编码、算术编码等通用压缩算法进一步减少数据流中的冗余信息。
对于电脑和数字电器（如数码录音笔、数码随身听）中存储的普通音频信息，我们最常使用的压缩方法主要是 MPEG 系列中的音频压缩标准。例如， MPEG-1 标准提供了 Layer I 、 Layer II 和 Layer III 共三种可选的音频压缩标准， MPEG-2 又进一步引入了 AAC （ Advanced Audio Coding ）音频压缩标准， MPEG-4 标准中的音频部分则同时支持合成声音编码和自然声音编码等不同类型的应用。在这许多音频压缩标准中，声名最为显赫的恐怕要数 MPEG-1 Layer III ，也就是我们常说的 MP3 音频压缩标准了。从 MP3 播放器到 MP3 手机，从硬盘上堆积如山的 MP3 文件到 Internet 上版权纠纷不断的 MP3 下载， MP3 早已超出了数据压缩技术的范畴，而成了一种时尚文化的象征了。
很显然，在多媒体信息日益成为主流信息形态的数字化时代里，数据压缩技术特别是专用于图像、音频、视频的数据压缩技术还有相当大的发展空间——毕竟，人们对信息数量和信息质量的追求是永无止境的。 从信息熵到算术编码，从犹太人到 WinRAR ，从 JPEG 到 MP3 ，数据压缩技术的发展史就像是一个写满了“创新”、“挑战”、“突破”和“变革”的羊皮卷轴。也许，我们在这里不厌其烦地罗列年代、人物、标准和文献，其目的只是要告诉大家，前人的成果只不过是后人有望超越的目标而已，谁知道在未来的几年里，还会出现几个 Shannon ，几个 Huffman 呢？
谈到未来，我们还可以补充一些与数据压缩技术的发展趋势有关的话题。
1994年， M. Burrows 和 D. J. Wheeler 共同提出了一种全新的通用数据压缩算法。这种算法的核心思想是对字符串轮转后得到的字符矩阵进行排序和变换，类似的变换算法被称为 Burrows-Wheeler 变换，简称 BWT 。与 Ziv 和 Lempel 另辟蹊径的做法如出一辙， Burrows 和 Wheeler 设计的 BWT 算法与以往所有通用压缩算法的设计思路都迥然不同。如今， BWT 算法在开放源码的压缩工具 bzip 中获得了巨大的成功， bzip 对于文本文件的压缩效果要远好于使用 LZ 系列算法的工具软件。这至少可以表明，即便在日趋成熟的通用数据压缩领域，只要能在思路和技术上不断创新，我们仍然可以找到新的突破口。
分形压缩技术是图像压缩领域近几年来的一个热点。这一技术起源于 B. Mandelbrot 于 1977 年创建的分形几何学。 M. Barnsley 在 20 世纪 80 年代后期为分形压缩奠定了理论基础。从 20 世纪 90 年代开始， A. Jacquin 等人陆续提出了许多实验性的分形压缩算法。今天，很多人相信，分形压缩是图像压缩领域里最有潜力的一种技术体系，但也有很多人对此不屑一顾。无论其前景如何，分形压缩技术的研究与发展都提示我们，在经过了几十年的高速发展之后，也许，我们需要一种新的理论，或是几种更有效的数学模型，以支撑和推动数据压缩技术继续向前跃进。
人工智能是另一个可能对数据压缩的未来产生重大影响的关键词。既然 Shannon 认为，信息能否被压缩以及能在多大程度上被压缩与信息的不确定性有直接关系，假设人工智能技术在某一天成熟起来，假设计算机可以像人一样根据已知的少量上下文猜测后续的信息，那么，将信息压缩到原大小的万分之一乃至十万分之一，恐怕就不再是天方夜谭了。
回顾历史之后，人们总喜欢畅想一下未来。但未来终究是未来，如果仅凭你我几句话就可以理清未来的技术发展趋势，那技术创新的工作岂不就索然无味了吗？依我说，未来并不重要，重要的是，赶快到 Internet 上下载几部大片，然后躺在沙发里，好好享受一下数据压缩为我们带来的无限快乐吧。

㈡ 关于哈夫曼编码试题的计算

太复杂了，楼主一会记得多给我点分！谢谢啦！
先设权w=(31,22,18,14,10,4,1),n=7,则m=13,按照哈夫曼算法可以构造一棵哈夫曼树如下：
100
40 60
22 18 31 29
14 15
10 5
4 1
末端结点为22，18，31，14，10，4，1，你自己把上面的加上线连成一棵二叉树就行，记得左分支标0，右分支标1（为了得出后面的哈夫曼编码HC）
然后需要列出HT初态表和HT终态表，如下：
HT初态表 HT终态表
weight parent lchild rchild weight parent lchild rchild
1 31 0 0 0 31 12 0 0
2 22 0 0 0 22 11 0 0
3 18 0 0 0 18 11 0 0
4 14 0 0 0 14 10 0 0
5 10 0 0 0 10 9 0 0
6 4 0 0 0 4 8 0 0
7 1 0 0 0 1 8 0 0
8 - 0 0 0 5 9 6 7
9 - 0 0 0 15 10 5 8
10 - 0 0 0 29 12 4 9
11 - 0 0 0 40 13 2 3
12 - 0 0 0 60 13 1 10
13 - 0 0 0 100 0 11 12
最后得出哈夫曼编码HC：
1——>10
2——>00
3——>01
4——>110
5——>1110
6——>11110
7——>11111
平均码字长度为（0.31＋0.22＋0.18）×2＋0.14×3＋0.1×4
＋（0.04＋0.01）×5＝2.47
编码效率为[（1－0.01）×3＋0.01×2]/2.47=1.21
解答完毕！
补充：对于其中的编码效率问题本人有点淡忘，我选择的是用
普通平均编码长度除上了哈夫曼平均编码长度得出，不知对否。
辛苦半天，望楼主能赐我分数，不胜感激！
注：提交后发现格式不太规整，对于哈夫曼树谁是谁的左孩子、右孩子比较容易分出（左右孩子结点相加可知父亲结点），对于HT初态表和HT终态表1列1列的看就行！其中数字第一列为序号，从第2列到第9列分别对应HT初态表的weight parent lchild rchild 和HT终态表的weight parent lchild rchild 。

㈢ 怎样用c++实现香农-范诺编码

#include"iostream.h"
#include<iomanip.h>
#include"vector"
#include"algorithm"
#include"math.h"
using namespace std;
struct bitree
{//定义结构用于存储编码结果的二叉树结构,在译码时用到
char ch; //用于存储码符号
char mz; //用于存储码字
bitree * lchild;
bitree * rchild;

};
struct data
{//用于存储相关的信源符号以及其概率
double p;
char ch;
vector<char> code;
int ml;
};
bool sortspecial(data dt1,data dt2)
{//用于排序时用
return dt1.p>dt2.p;
}
void print2(vector<char>vd)
{//用于打印译码结果
for(int i=0;i<vd.size();i++)
cout<<vd[i]<<" ";
cout<<endl;
}
void read(vector <data> &vd)
{//用于读入相关的信源符号以及概率
int n;
while(true)
{
cout<<"请输入信源符号数:";
cin>>n;
cout<<"请输入相应的信源符号及其概率:"<<endl;
data dt;
int i=0;
while(i<n)
{
cin>>dt.ch;
cin>>dt.p;
dt.ml=0;
vd.push_back(dt);
i++;

}
double sum=0;
vector<data>::iterator pit;
/* for(pit=vd.begin();pit!=vd.end();pit++)
{
sum+=pit->p;
}
if(sum!=1)
{
cout<<"你输入的概率不符合要求,请重新输入."<<endl;
sum=0;
continue;
}*/
sort(vd.begin(),vd.end(),sortspecial);
break;
}
}

void append(char ch1,char ch2,bitree *&bt)
{//用于再构造码字二叉树时向其中添加结点
bitree * bit=new bitree;
bit->ch=ch1;
bit->mz=ch2;
bit->lchild=NULL;
bit->rchild=NULL;
if(ch1=='0')
bt->rchild=bit;
else bt->lchild=bit;
}
void Creatmz1(vector<data>& vd,int begin1,int end1 ,double pn ,bitree *&bt)
{//进行编码,用递归的方法进行编码
int begin=begin1,end=end1;
if(begin==end) return;
else if(begin+1==end)
{
return;
}
else if(begin+2==end){
vd[begin].code.push_back('0');
vd[begin].ml++;
append('0',vd[begin].ch,bt);
vd[end-1].code.push_back('1');
vd[end-1].ml++;
append('1',vd[end-1].ch,bt);
return;
}
else{
double sum0=0,sum1=0,sum2=0;
do{
sum1+=vd[begin].p;
sum2=sum1+vd[begin+1].p;
begin++;
}while(fabs(sum1/pn-0.5)>fabs(sum2/pn-0.5));//用于找到上下两组码的分点使得其概率和近于相同
for(int i=begin1;i<begin;i++){
vd[i].code.push_back('0');
vd[i].ml++;
}
if(begin1+1 == begin){
append('0',vd[begin1].ch,bt);
}
else append('0','0',bt);
for(int j=begin;j<=end1-1;j++){
vd[j].code.push_back('1');
vd[j].ml++;
}
if(begin+1 == end1){
append('1',vd[begin].ch,bt);
}
else append('1','0',bt);
Creatmz1(vd,begin1 ,begin,sum1,bt->rchild );//对分点前的进行编码
Creatmz1(vd,begin ,end1,pn-sum1,bt->lchild);//对分点后的进行编码*/

}
}
void print1(vector<data> vd)
{//用于打印编码结果
cout<<"xi"<<setw(8)<<"P(xi)"<<setw(8)<<"码长"
<<setw(8)<<"码字"<<setw(8)<<endl;
for(int i=0;i<vd.size();i++){
cout<<vd[i].ch<<setw(8)<<vd[i].p<<setw(8)<<vd[i].ml<<setw(8);
for(int j=0;j<vd[i].code.size();j++)
cout<<vd[i].code[j];
cout<<setw(8)<<endl;
}
}

void clear(bitree * & bt)
{//对二叉树的动态存储空间进行释放
if(bt!=NULL&&bt->lchild!=NULL)
clear(bt->lchild);
if(bt!=NULL&&bt->rchild!=NULL)
clear(bt->rchild);
delete bt;
}

bool des_code(vector <char> & vr,vector <char> vt,bitree *bt)
{//用二叉编码树进行解码
if(bt==NULL)
{
cout<<"码树不存在!!!"<<endl;
return false;
}
int pit=0;
bitree * mbt=bt;
while ((mbt->lchild!=NULL||mbt->rchild!=NULL)||pit<vt.size())
{
if(mbt->lchild==NULL&&mbt->rchild==NULL&&mbt->mz!='0')
{
vr.push_back(mbt->mz);
mbt=bt;
}
if(mbt->lchild!=NULL&& vt[pit]=='1')
{
mbt=mbt->lchild;
pit++;
}
else if(mbt->rchild!=NULL&& vt[pit]=='0')
{
mbt=mbt->rchild;
pit++;
}
else if(mbt->lchild!=NULL&&mbt->rchild!=NULL) break;
}
if(mbt->lchild!=NULL&&mbt->rchild!=NULL)
{
cout<<"你输入的是一个错误的码序列,请较正后再输入."<<endl;
return false;
}
else {
vr.push_back(mbt->mz);
return true;
}
}
void read1(vector<char>& vd)
{//用于读入要解码的序列
cout<<"请输要译码的序列(以'#'结束):"<<endl;
char dt;
int i=0;
cin>>dt;
while(dt!='#')
{
vd.push_back(dt);
cin>>dt;
}
}

void print_H_L_R(vector<data>vd)
{//用于计算并打印信息熵,平均码长,效率
double H=0,L=0,R=0;
for(int i=0;i<vd.size();i++)
{
H+=vd[i].p*(log10(1/vd[i].p)/log10(2));
L+=vd[i].p*(double)vd[i].ml;
}
R=H/L;
cout<<"此码的信息熵(H)是:"<<H<<endl;
cout<<"此码的平均码长(L)为:"<<L<<endl;
cout<<"此码的效率(U)为:"<<R<<endl;
}
int main()
{
bitree * bt=new bitree;
bt->ch = '#';
bt->mz = '*';
bt->lchild=NULL;
bt->rchild=NULL;
vector <data> vd;
vector <char> vr;
vector <char> vt;
cout<<"************下面将对Fano编,译码的过程进行演示*************"<<endl;
cout<<"__________________________________________________________"<<endl;
cout<<endl;
cout<<"************下面显示编码的过程及相关参数和结果************"<<endl;
read(vd);
if(vd.size()==1)
{
vd[0].code.push_back('0');
vd[0].ml++;
append('0',vd[0].ch,bt);
}
cout<<endl;
Creatmz1(vd,0,vd.size(),1,bt);
cout<<"************** 编码结果 **************"<<endl;
print1(vd);
print_H_L_R(vd);
cout<<endl;
cout<<"************ 下面将进行译码过程操作的演示 ************"<<endl;
cout<<endl;
read1(vt);
if(des_code(vr,vt,bt))
print2(vr);
clear(bt);
return 1;
}

一定要提高悬赏分哟。

㈣ 什么是信源在允许一定失真的条件下，信源熵所能压缩的极限

1．统计编码原理──信息量和信息熵

根据香农信息论的原理，最佳的数据压缩方法的理论极限是信息熵。如果要求在编码过程中不丢失信息量，即要求保存信息熵，这种信息保持的编码又叫熵保存编码，或叫熵编码。熵编码是无失真压缩。当然在考虑人眼失真不易察觉的生理特性时，有些图像编码不严格要求熵保存，信息允许通过部分损失来换取高的数据压缩比。这种编码属于有失真数据压缩。
信息是用不确定性的量度定义的，也就是说信息被假设为由一系列的随机变量所代表，它们往往用随机出现的符号来表示。我们称输出这些符号的源为“信源”。也就是要进行研究与压缩的对象。 信息量

信息量指从N个相等可能事件中选出一个事件所需要的信息度量或含量，也可以说是辨别N个事件中特定事件过程中所需提问“是”或“否”的最小次数。
例如：从64个数（1～64的整数）中选定某一个数（采用折半查找算法），提问：“是否大于32？”，则不论回答是与否，都消去半数的可能事件，如此下去，只要问6次这类问题，就可以从64个数中选定一个数，则所需的信息量是 =6（bit）。 我们现在可以换一种方式定义信息量，也就是信息论中信息量的定义。
设从N中选定任一个数X的概率为P(x)，假定任选一个数的概率都相等，即P(x)=1/N，则信息量I (x)可定义为：

上式可随对数所用“底”的不同而取不同的值，因而其单位也就不同。设底取大于1的整数α，考虑一般物理器件的二态性，通常α取2，相应的信息量单位为比特（bit）；当α=e，相应的信息量单位为奈特（Nat）；当α=10，相应的信息量单位为哈特（Hart）。显然，当随机事件x发生的先验概率P(x)大时，算出的I(x)小，那么这个事件发生的可能性大，不确定性小，事件一旦发生后提供的信息量也少。必然事件的P(x)等于1， I(x)等于0，所以必然事件的消息报导，不含任何信息量；但是一件人们都没有估计到的事件（P(x)极小），一旦发生后，I(x)大，包含的信息量很大。所以随机事件的先验概率，与事件发生后所产生的信息量，有密切关系。I(x)称x发生后的自信息量，它也是一个随机变量。
P(x)大时，算出的I(x)小 必然事件的P(x)等于1， I(x)等于0。
P(x)小时，算出的I(x)大 必然事件的P(x)等于0， I(x)等于1。
I(x)称x发生后的自信息量，它也是一个随机变量。
信息熵

现在可以给“熵”下个定义了。信息量计算的是一个信源的某一个事件（X）的自信息量，而一个信源若由n个随机事件组成，n个随机事件的平均信息量就定义为熵(Entropy)。
熵的准确定义是：信源X发出的xj(j=1,2,……n), 共n个随机事件的自信息统计平均（求数学期望），即

H(X)在信息论中称为信源X的“熵 （Entropy）” ，它的含义是信源X发出任意一个随机变量的平均信息量。

更详细的说，一般在解释和理解信息熵有4种样式
（1） 当处于事件发生之前，H(X)是不确定性的度量；
（2） 当处于事件发生之时，是一种惊奇性的度量；
（3） 当处于事件发生之后，是获得信息的度量；
（4） 还可以理解为是事件随机性的度量． 下面为了掌握信息熵的概念，我们来做一道计算题。
例如：以信源X中有8个随机事件，即n=8。每一个随机事件的概率都相等，即P(x1)=P(x2)=P(x3)……P(x8)=1/8 ，计算信源X的熵。
应用“熵”的定义可得其平均信息量为3比特

再例： 信源X中有17个随机事件，即n=17。每一个随机事件的概率分别为：

计算信源X的熵。
信息熵的计算公式：

信源X的熵：

定长码与变长码
定长码（fixed-length code）即采用相同的位数（bit）对数据进行编码。大多数存储数字信息的编码系统都采用定长码。如我们常用的ASCII码就是定长码，其码长为1字节（Byte）。汉字国标码也是定长码，其码长为2字节（Byte）。变长码（variable-length code）即采用不相同的位数（bit）对数据进行编码，以节省存储空间。例如，不同的字符或汉字出现的概率是不同的，有的字符出现的概率非常高，有的则非常低。根据统计，英文字母中“E”的使用概率约为13％，而字母“Z”的使用概率则为0.08％。又如大多数图像常含有单色的大面积图块，而且某些颜色比其他颜色出现更频繁。为了节省空间，在对数据进行编码时，就有可能对那些经常出现的数据指定较少的位数表示，而那些不常出现的数据指定较多的位数表示。这样从总的效果看还是节省了存储空间。用这种方法得到的代码，其码的位数，也即码长就是不固定的，故称为变长码。香农-范诺编码，以及霍夫曼编码，都是变长码。
2．赫夫曼（Huffman）编码基本原理：按信源符号出现的概率大小进行排序，出现概率大的分配短码，出现概率小的则分配长码。（定长码采用相同的码长对数据进行编码，如ASCII码是定长码，其码长为1字节。）
定理：在变长码中，对于出现概率在的信息符号编以短字长的码，对于出现概率小的信息符号以长字长的码，如果码字长度严格按照符号概率的大小的相反顺序排列，则平均码字长度一定小于按任何其他符号顺序排列方式得到的码字长度。
定理证明

设最佳排列方式的码字平均长度为 ，则有：

式中 为信源符号 出现的概率， 是符号 的编码长度。规定 ， 。如果将 的码字与 的码字互换，其余码字不变，经过这样的互换以后，平均码字长度变成 ，即

因为 ，所以 ，也就是说 最短。证毕。
Huffman编码的编码步骤

① 概率统计（如对一幅图像，或m幅同种类型图像作灰度信号统计），得到n个不同概率的信息符号。
② 将n个信源信息符号的n个概率，按概率大小排序。
③ 将n个概率中，最后两个小概率相加，这时概率个数减为n-1个。
④ 将n-1个概率，按大小重新排序。
⑤ 重复③，将新排序后的最后两个小概率再相加，相加和与其余概率再排序。
⑥ 如此反复重复n-2次，得到只剩两个概率序列。
⑦ 以二进制码元(0.1)赋值，构成霍夫曼码字。编码结束。

利用Huffman编码方式对信源进行编码

已知信源：
编码结果：平均码长： ＝（0.35＋0.20）×2＋（0.15＋0.10＋0.10）×3＋（0.06＋0.04）×4＝2.55（bit）（对于等长码则需要3比特）。

Huffman编码的特点

（1）平均码长 （熵）；
（2）平均码长 bits（等长码需要的比特数）；
（3）保证解码的唯一性，短码字不构成长码字的前缀；
（4）在接收端需保存一个与发送端相同的赫夫曼码表。 Huffman不足方面：（1）构造出的码不唯一，其原因是：一是在给两个分支赋值时，可以是左支（或上支）为0，也可以是右支（或下支）为0，造成编码的不唯一；二是当两个消息的概率相等时，谁前谁后也是随机的，构造出来的码字也不唯一。
（2）编码码字字长参差不齐，因此硬件实现起来不大方便。
（3）编码对不同信编码效率是不同的。在概率颁很不均匀时，Huffman编码才会有显着的效果，在信源颁均匀的情况下，一般不使用Huffman编码。
3．算术编码（Arithmetic Coding）算术编码方法也是利用信源概率分布特性、能够趋近熵极限的编码的方法。算术编码不按符号编码，即不是用一个特定的码字与输入符号之间建立一一对应的关系，而是从整个符号序列出发，采用递推形式进行连续编码，用一个单独的浮点数来表示一串输入符号。算术编码是将被编码的信息表示成实数0和1之间的一个间隔。信息越长编码表示它的间隙就越小，表示这一间隙所须二进位就越多，大概率符号出现的概率越大对应于区间愈宽，可用长度较短的码字表示；小概率符号出现概率越小层间愈窄，需要较长码字表示。它的编码方法比Huffman编码方式要复杂，但它不需要传送像Huffman编码中的Huffman码表，同时算术编码还有自适应的优点，所以算术编码是实现高效压缩数据中很有前途的编码方法。特点：方法比较复杂，具有自适应能力（随着编码符号流中01出现的概率的变化将自适应的改变）。在信源符号概率接近时，算术编码比Huffman编码效率要高。 算术编码与解码举例

假设信源符号为{00, 01, 10, 11}，这些符号的概率分别为{ 0.1, 0.4, 0.2, 0.3 }，根据这些概率可把间隔[0,1)分成4个子间隔：[0, 0.1), [0.1, 0.5), [0.5, 0.7), [0.7, 1)，其中[x,y)表示半开放间隔，即包含x不包含y。上面的信息可综合在下表中。 表 信源符号，概率和初始编码间隔 符号00011011概率0.10.40.20.3初始编码间隔[0,0.1)[0.1,0.5)[0.5,0.7)[0.7,1)
如果二进制消息序列的输入为：10 00 11 00 10 11 01。编码时首先输入的符号是10，找到它的编码范围是[0.5, 0.7)。由于消息中第二个符号00的编码范围是[0, 0.1)，因此它的间隔就取[0.5, 0.7)的第一个十分之一作为新间隔[0.5, 0.52)。依此类推，编码第3个符号11时取新间隔为[0.514, 0.52)，编码第4个符号00时，取新间隔为[0.514, 0.5146)，… 。消息的编码输出可以是最后一个间隔中的任意数。整个编码过程如下图示：
表: 编码过程步骤 输入符号编码间隔 编码判决110[0.5, 0.7)符号的间隔范围[0.5, 0.7) 200[0.5, 0.52)[0.5, 0.7)间隔的第一个1/10311[0.514, 0.52)[0.5, 0.52)间隔的最后三个1/10400[0.514, 0.5146)[0.514, 0.52)间隔的第一个1/10510[0.5143, 0.51442)[0.514, 0.5146)间隔的第六个1/10开始的两个1/10611[0.514384, 0.51442)[0.5143, 0.51442)间隔的最后三个1/10701[0.5143836, 0.514402)[0.514384, 0.51442)间隔的从第二个1/10开始的四个1/108从[0.5143876, 0.514402中选择一个数作为输出：0.51439
表：译码过程步骤间隔译码符号 译码判决 1[0.5, 0.7)100.51439在间隔 [0, 1) 第六个1/102[0.5, 0.52)000.51439在间隔 [0.5, 0.7)的第一个1/103[0.514, 0.52)110.51439在间隔[0.5, 0.52)的第八个1/104[0.514, 0.5146)000.51439在间隔[0.514, 0.52)的第一个1/105[0.5143, 0.51442)100.51439在间隔[0.514, 0.5146)的第七个1/106[0.514384, 0.51442)110.51439在间隔[0.5143, 0.51442)的第八个1/107[0.5143876, 0.514402)010.51439在间隔[0.5143876, 0.514402)的第二个1/108译码的消息：10 00 11 00 10 11 01译码器的译码过程应无限制地运行下去。在译码器中需要添加一个专门的终止符，当译码器看到终止符时就停止译码。在算术编码中需要注意的几个问题：
①由于实际的计算机的精度不可能无限长，运算中出现溢出是一个明显的问题，但多数机器都有16位、32位或者64位的精度，因此这个问题可使用比例缩放方法解决。
②算术编码器对整个消息只产生一个码字，这个码字是在间隔[0, 1)中的一个实数，因此译码器在接受到表示这个实数的所有位之前不能进行译码。
③算术编码也是一种对错误很敏感的编码方法，如果有一位发生错误就会导致整个消息译错。

算术编码可以是静态的或者自适应的。在静态算术编码中，信源符号的概率是固定的。在自适应算术编码中，信源符号的概率根据编码时符号出现的频繁程度动态地进行修改，在编码期间估算信源符号概率的过程叫做建模。需要开发自适应算术编码的原因是因为事先知道精确的信源概率是很难的，而且是不切实际的。当压缩消息时，不能期待一个算术编码器获得最大的效率，所能做的最有效的方法是在编码过程中估算概率。因此动态建模就成为确定编码器压缩效率的关键。
算术编码的实现相应地比Huffman编码复杂，但当与信号源符号的出现概率接近时，算术编码的效率高于Huffman编码。在图像测试中表明，算术编码效率比Huffman效率高5%左右。

㈤ 数据无损压缩算法

所谓无损压缩格式，顾名思义，就是毫无损失地将声音信号进行压缩的音频格式。常见的像MP3、WMA等格式都是有损压缩格式，相比于作为源的WAV文件，它们都有相当大程度的信号丢失，这也是它们能达到10%的压缩率的根本原因。而无损压缩格式，就好比用Zip或RAR这样的压缩软件去压缩音频信号，得到的压缩格式还原成WAV文件，和作为源的WAV文件是一模一样的！但是如果用Zip或RAR来压缩WAV文件的话，必须将压缩包解压后才能播放。而无损压缩格式则能直接通过播放软件实现实时播放，使用起来和MP3等有损格式一模一样。总而言之，无损压缩格式就是能在不牺牲任何音频信号的前提下，减少WAV文件体积的格式。

经常使用的无损压缩算法有 Shannon-Fano 编码，Huffman 编码，行程（Run-length）编码，LZW（Lempel-Ziv-Welch）编码和算术编码等。

Huffman 编码
该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫做Huffman编码。它是统计独立信源能达到最小平均码长的编码方法。编码效率高 。

基本原理：

依据信源字符出现的概率大小来构造代码，对出现概率较大的信源字符，给予较短码长，而对于出现概率较小的信源字符，给予较长的码长，最后使得编码的平均码字最短。

编码步骤：

（1）初始化，根据符号概率的大小按由大到小顺序对符号进行排序。

（2）把概率最小的两个符号组成一个节点。

（3）重复步骤2。

（4）从根节点开始到相应于每个符号的“树叶”，从上到下标上“0”（上枝）或者“1”（下枝）至于哪个为“1”哪个为“0”则无关紧要，最后的结果仅仅是分配的代码不同，而代码的平均长度是相同的。

（5）从根节点开始顺着树枝到每个叶子分别写出每个符号的代码。

无损压缩算法有哪些

Huffman编码的注意点：

Huffman编码没有错误保护功能，如果码中有错误，则可能引起接下来的一连串译码错误。

Huffman编码是可变长编码，因此很难随意查找或调用中的文件内容。

Huffman依赖于信源的统计特性。 Huffman编码的每个码字都是整数：因此实际上平均码长很难达到信息熵的大小。

Huffman编码解码必须要有码表，如果消息数目很多，那么

㈥ 信息论基础的作品目录

第1章绪论1
1.1信息的基本概念1
1.1.1信息论的产生1
1.1.2信息的基本概念2
1.2香农信息论研究的内容3
1.2.1通信系统模型4
1.2.2香农信息论的主要内容6
1.3香农信息论研究的进展与应用8
1.3.1香农信息论创立的背景8
1.3.2香农的主要贡献9
1.3.3香农信息论的研究进展9
1.3.4香农信息论的应用12
思考题12
第2章离散信息的度量14
2.1自信息和互信息14
2.1.1自信息14
2.1.2互信息17
2.2信息熵18
2.2.1信息熵的定义与计算18
2.2.2条件熵与联合熵21
2.2.3熵的基本性质22
2.3平均互信息27
2.3.1平均互信息的定义27
2.3.2平均互信息的性质28
2.3.3平均条件互信息30
本章小结33
思考题34
习题34
第3章离散信源37
3.1离散信源的分类与数学模型37
3.1.1离散信源的分类37
3.1.2离散无记忆信源的数学模型38
3.1.3离散有记忆信源的数学模型39
3.2离散无记忆信源的熵39
3.2.1单符号离散无记忆信源的熵39
3.2.2离散无记忆信源N次扩展源的熵40
3.3离散平稳信源的熵40
3.3.1离散平稳信源40
3.3.2离散平稳有记忆信源的熵41
3.4有限状态马尔可夫链42
3.4.1马氏链基本概念43
3.4.2齐次马氏链43
3.4.3马氏链状态分类46
3.4.4马氏链的平稳分布47
3.5马尔可夫信源48
3.5.1马氏源的基本概念48
3.5.2马氏源的产生模型50
3.5.3马氏链N次扩展源的熵的计算51
3.5.4马氏源符号熵的计算53
3.6信源的相关性与剩余度55
3.6.1信源的相关性55
3.6.2信源剩余度(冗余度)55
3.6.3自然语言的相关性和剩余度56
本章小结59
思考题59
习题60
第4章连续信息与连续信源64
4.1连续随机变量集合的熵64
4.1.1连续随机变量的离散化65
4.1.2连续随机变量集的熵65
4.1.3连续随机变量集的条件熵65
4.1.4连续随机变量集的联合熵66
4.1.5连续随机变量集合差熵的性质66
4.1.6连续随机变量集合的信息散度68
4.2离散时间高斯信源的熵69
4.2.1一维高斯随机变量集的熵69
4.2.2多维独立高斯随机变量集的熵69
4.2.3多维相关高斯随机变量集的熵69
4.3连续最大熵定理70
4.3.1限峰值最大熵定理71
4.3.2限功率最大熵定理71
4.3.3熵功率和剩余度72
4.4连续随机变量集的平均互信息72
4.4.1连续随机变量集的平均互信息72
4.4.2连续随机变量集平均互信息的性质73
4.5离散集与连续集之间的互信息75
4.5.1离散事件与连续事件之间的互信息76
4.5.2离散集合与连续集合的平均互信息76
本章小结77
思考题77
习题77
第5章无失真信源编码80
5.1概述80
5.1.1信源编码器80
5.1.2信源编码的分类81
5.1.3分组码82
5.2定长码83
5.2.1无失真编码条件83
5.2.2信源序列分组定理84
5.2.3定长码信源编码定理86
5.3变长码88
5.3.1异前置码的性质88
5.3.2变长码信源编码定理90
5.4哈夫曼编码93
5.4.1二元哈夫曼编码93
5.4.2多元哈夫曼编码96
5.4.3马氏源的编码97
*5.5几种实用的编码方法99
5.5.1算术编码99
5.5.2游程编码100
5.5.3L-Z编码101
本章小结101
思考题102
习题102
第6章离散信道及其容量105
6.1概述105
6.1.1信道的分类105
6.1.2离散信道的数学模型106
6.1.3信道容量的定义109
6.2单符号离散信道及其容量109
6.2.1离散无噪信道的容量109
6.2.2离散对称信道的容量110
6.2.3一般离散信道的容量112
6.3级联信道及其容量116
6.4多维矢量信道及其容量118
6.4.1多维矢量信道输入与输出的性质118
6.4.2离散无记忆扩展信道及其容量120
6.4.3并联信道及其容量122
6.4.4和信道及其容量122
6.5信道容量的迭代计算123
本章小结125
思考题126
习题126
第7章有噪信道编码129
7.1概述129
7.1.1信道编码的基本概念129
7.1.2判决与译码规则130
7.1.3译码错误概率131
7.2最佳判决与译码准则132
7.2.1最大后验概率准则132
7.2.2最大似然准则133
7.3信道编码与最佳译码134
7.3.1线性分组码134
7.3.2序列最大似然译码 135
7.3.3几种简单的分组码136
7.4费诺(Fano)不等式137
7.4.1信道疑义度137
7.4.2费诺(Fano)不等式138
7.5有噪信道编码定理139
7.5.1联合典型序列140
7.5.2有噪信道编码定理141
7.5.3无失真信源信道编码定理143
7.6纠错编码技术简介144
7.6.1线性分组码的编译码144
7.6.2几种重要的分组码148
7.6.3卷积码简介149
*7.7信道编码性能界限150
7.7.1汉明球包界150
7.7.2VarsharmovGilbert界151
7.7.3Plotkin界152
本章小结153
思考题153
习题154
第8章波形信道159
8.1离散时间连续信道159
8.1.1时间离散连续信道模型159
8.1.2平稳无记忆连续信道160
8.1.3多维矢量连续信道的性质160
8.1.4离散时间连续信道的容量160
8.2加性噪声信道与容量161
8.2.1加性噪声信道的容量161
8.2.2加性高斯噪声信道的容量162
8.2.3一般加性噪声信道容量界163
8.2.4并联加性高斯噪声信道的容量164
8.3AWGN信道的容量166
8.3.1加性高斯噪声波形信道166
8.3.2波形信道的互信息与容量167
8.3.3AWGN信道的容量168
8.3.4高斯噪声信道编码定理170
8.3.5功率利用率和频谱利用率的关系171
8.4有色高斯噪声信道173
8.4.1有色高斯噪声信道容量173
8.4.2AWGN信道容量的进一步讨论175
*8.5数字调制系统的信道容量176
本章小结179
思考题180
习题180
第9章信息率失真函数183
9.1概述183
9.1.1系统模型184
9.1.2失真测度184
9.2离散信源信息率失真函数185
9.2.1信息率失真函数185
9.2.2R(D)函数的性质185
9.3限失真信源编码定理188
9.3.1码率的压缩188
9.3.2限失真信源编码定理189
9.3.3限失真信源信道编码定理190
9.4离散信源信息率失真函数的计算190
9.4.1R(D)参量表示法求解191
9.4.2R(D)求解过程归纳192
9.4.3参量s的意义193
9.5连续信源信息率失真函数195
9.5.1信息率失真函数与性质195
9.5.2R(D)函数的计算195
9.5.3差值失真测度196
9.6高斯信源的R(D)函数197
9.6.1离散时间无记忆高斯信源197
9.6.2独立并联高斯信源199
9.7一般连续信源R(D)函数201
*9.8有损数据压缩技术简介201
9.8.1量化202
9.8.2预测编码202
9.8.3子带编码203
9.8.4变换编码203
本章小结204
思考题205
习题205
第10章有约束信道及其编码208
10.1标号图的性质208
10.1.1标号图的基本概念208
10.1.2标号图的变换210
10.2有约束信道容量211
10.2.1有约束信道容量的定义211
10.2.2等时长符号有约束信道的容量212
10.2.3不等时长符号无约束信道的容量213
10.2.4不等时长符号有约束信道的容量214
10.3有约束序列的性质215
10.3.1信道对传输序列的约束215
10.3.2游程长度受限序列(RLL)215
10.3.3部分响应最大似然(PRML)序列217
10.3.4直流平衡序列218
10.3.5其他频域受限序列220
10.4有约束信道编码定理220
10.4.1编码器的描述220
10.4.2有约束信道编码定理221
10.4.3有限状态编码定理221
10.4.4编码器性能指标222
*10.5有约束序列编码与应用222
10.5.1块编码器222
10.5.2实用直流平衡序列223
10.5.3常用有约束序列编码及应用225
本章小结227
思考题227
习题227
第11章网络信息论初步230
11.1概述230
11.2多址接入信道231
11.2.1二址接入信道的容量232
11.2.2不同多址方式下的接入信道容量分析236
11.2.3多址接入信道的容量238
11.3广播信道238
11.3.1退化广播信道239
11.3.2退化广播信道的容量区域240
11.4相关信源编码242
11.4.1典型的相关信源编码模型243
11.4.2Slepian-Wolf相关信源编码定理244
本章小结247
思考题248
习题249
*第12章信息理论方法及其应用250
12.1信源熵的估计250
12.1.1离散信源序列熵的估计251
12.1.2连续信源熵的估计254
12.2最大熵原理255
12.2.1最大熵原理的描述255
12.2.2熵集中定理258
12.2.3几种重要的最大熵分布259
12.3最小交叉熵原理261
12.3.1最小交叉熵原理261
12.3.2交叉熵的性质263
12.3.3最小交叉熵推断的性质264
12.3.4交叉熵法265
12.4信息理论方法的应用265
12.4.1DNA序列的熵估计和压缩265
12.4.2最大熵谱估计和最小交叉熵谱估计267
12.4.3最大熵建模及其在自然语言处理中的应用269
12.4.4最大熵原理在经济学中的应用271
12.4.5信息理论方法应用展望273
本章小结273
思考题274
习题274
参考文献276

㈦ 典型的有损压缩编码方法错误的是

错误的是：啥夫曼编码将出现概率大的信源符号用长码表示，出现概率小的信源符号用短码表示。
对于多媒体数据，按照压缩的原理可分为熵编码、源编码和混合编码。其中，源编码包含预测编码去、变换编码法和矢量量化编码法，属于有损压缩编码，如表210所示。啥夫曼编码是最着名的熵编码，它将出现概率大的信源符号用短码表示，而出现概率小的信源符号用长码表示，于是平均码长接近信息熵的理论值。因此这个是错误的。

㈧ 用费诺编码实现信源编译码

我回答你的问题啊！呵呵，你怎么不给分啊？？？？实验命令：clc;clear all;
N=input('N=');%输入信源符号的个数
s=0;l=0;H=0;
for i=1:N
fprintf('第%d个',i);
p(i)=input('p=');%输入信源符号概率分布矢量,p(i)<1
if p(i)<=0
error('不符合概率分布')
end
s=s+p(i)
H=H+(- p(i)*log2(p(i)));%计算信源信息熵
end
if (s<=0.999999||s>=1.000001)
error('不符合概率分布')
end
tic;
for i=1:N-1 %按概率分布大小对信源排序
for j=i+1:N
if p(i)<p(j)
m=p(j);p(j)=p(i);p(i)=m;
end
end
end
x=f1(1,N,p,1);
for i=1:N %计算平均码长
L(i)=length(find(x(i,:)));
l=l+p(i)*L(i);
end
n=H/l; %计算编码效率
fprintf('按概率降序排列的码字:\n');
disp(x) %显示按概率降序排列的码字
fprintf('平均码长:\n');
disp(l)% 显示平均码长
fprintf('信源信息熵:\n');
disp(H)%显示信源信息熵
fprintf('编码效率:\n');
disp(n) %显示编码效率
fprintf('计算耗时time= %f\n',toc);
再建立两个M文件：%函数f1存放于f1.m
function x=f1(i,j,p,r)
global x;
x=char(x);
if(j<=i)
return;
else
q=0;
for t=i:j %对于区间[i,j]自上而下求累加概率值
q=p(t)+q;y(t)=q;
end
for t=i:j%把所有自上而下的累加概率值与该区间总概率值减该累加概率值之差取绝对值存在一数组
v(t)=abs(y(t)-(q-y(t)));
end
for t=i:j
if(v(t)==min(v)) %求该数组中最小的一个值来确定分界点位置
for k=i:t %赋值码字
x(k,r)='0';
end
for k=(t+1):j
x(k,r)='1';
end
d=t;
f1(i,d,p,r+1); %递归调用及相互调用
f2(d+1,j,p,r+1);
f1(d+1,j,p,r+1);
f2(i,d,p,r+1);
else
end
end
end
return;第二个：%函数f2存放于f2.m
function x=f2(i,j,p,r)
global x;
x=char(x);
if(j<=i)
return;
else
q=0;
for t=i:j %对于区间[i,j]自上而下求累加概率值
q=p(t)+q;y(t-i+1)=q;
end
for t=1:j-(i-1)%把所有自上而下的累加概率值与该区间总概率值减该累加概率值之差取绝对值存在一数组
v(t)=abs(y(t)-(q-y(t)));
end
for t=1:j-(i-1)
if(v(t)==min(v)) %求该数组中最小的一个值来确定分界点位置
d=t+i-1;
for k=i:d %赋值码字
x(k,r)='0';
end
for k=(d+1):j
x(k,r)='1';
end
f2(d+1,j,p,r+1);%递归调用及相互调用
f1(i,d,p,r+1);
f2(i,d,p,r+1);
f1(d+1,j,p,r+1);
else
end
end
end
return;

㈨ 如何计算密码所携带的信息熵

可加性与强可加性（涉及到了两个变量！）H（XY）为两个随机变量的联合熵。可加性：H（XY）等于 X的无条件熵，加上已知 X 时 Y的条件概率的熵的平均值，即条件熵。对于 X 与 Y 独立的情况有：（强可加性）信息论基础2011年3月教材和参考书傅祖芸编着《信息论－基础理论与应用》，电子工业出版社，2006第二版. 孟庆生《信息论》，西安交通大学，1986。（数学家写的研究生教材，含编码和密码）朱雪龙《应用信息论基础》，清华大学出版社,2000。（研究生教材，面向电子类，含编码方法。王育民、梁传甲《信息与编码理论》，西电教材。 （内容深入，推导过程少）沈连丰、叶芝惠编着《信息论与编码》东南大学硕士教材，科学出版社，2004，（面向通信专业）。周荫清主编《信息理论基础》北航出版社，2006（简洁，面向电子类）T. M. Cover & J. A. Thomas , Elements of Information Theory ，Addison-Wesley Pub, 1990, 清华影印。R. J. McEliece《The Theory of Information and Coding》第二版，电子工业出版社，2003。（内容简练，编码方面较全） * J.H.Van Lint 《Introction to coding theory》 GTM 86, Springer-Verlag, 1998. * Roman 《Coding and information theory》, GTM 134，新的教材：在广义信息论、网络信息论方面的内容有所增加。第一讲 1-1 信息论的主要内容 1-2 信息的度量－信息熵 1-3 信息熵的性质 信息熵 1－1. 信息论的主要内容 香农信息论最初是为了解决通信问题而提出的。通信的重要意义是勿庸置疑的。类传递思想、表达情感，就需要相互交流。人类的劳动、生产、政治、文化、日常生活等都离不开通信。人类利用眼、耳、鼻、舌、身等五种感觉器官来感受外界的信息，形成一个信息流通的体系。通信方式的不断提高，代表了人类文明和科技水平的不断提高。通信的根本任务：将一地点的消息可靠地、有效地传送到另一地点。信源干扰源信道信宿通信系统的基本模型：为了使消息可靠地、有效地传送到信宿，就需要对信源的消息进行处理；信源编码：实现有效性；信道编码：实现可靠性；密码：实现保密性及认证性；有没有可靠的、有效的处理方法？如何进行编码？香农信息论奠定了通信的理论基础。信息是消息的不确定性度量。某消息出现的概率大，它的信息量就小，相反某消息出现的概率小，则它的信息量就大。通信的关键是信息的传输问题。 信源，信源，编码信宿，信道，信道编码，信道译码，信源译码加密钥，加密解密钥，解密 干扰源提出的背景：在香农信息论出现以前，没有系统的通信理论。是香农，开创了信息论的研究，奠定了一般性通信 理论的基础。对数字通信技术的形成有很大贡献。（不论什么样的干扰信道，抓住了本质问题Shannon, 1916－2001)“A Mathematical Theory of Communication ”“ Communication Theory of Secrecy System ” About Claude Elwood Shannon: 1916年生于 Gaylord, MI 的一个小镇。母亲是一个语言教师和中学校长，父亲是一个商人。 16岁高中毕业，进入密西根大学。1936年获得电子工程和数学双学士学位。随后进入 MIT，作为研究生和研究人员。