霍夫曼编码论文开题报告

问题: 哈夫曼编码,英文名称 Huffman Coding，有时也翻译为霍夫曼编码，在1952年提出的，是最好的编码方式。哈夫曼编码在电子通讯方面有着重要的应用，同时也广泛应用于数据压缩，其压缩率通常在20% 90%之间 赫夫曼码是可变字长编码(VLC)的一种。哈夫曼树是最优二叉树， 带权路径长度最小的二叉树。

原理:

假设有几个数字40,10,20,16,14。

首先将这五个数字按照从小到大的顺序排列：10, 14，16，20, 40。

构建哈夫曼树：

1.首先选取10,14

2.重新排序：16,20,24,40

3.重新排序24,36,40,60

4.按照二叉树左0右1，构建哈夫曼树

所以最终得到数字10的编码为100，数字14的编码为101，数字16的编码为110，数字20的编码为111，数字40的编码为0。

代码：

运行结果:

赫夫曼码的码字（各符号的代码）是异前置码字，即任一码字不会是另一码字的前面部分，这使各码字可以连在一起传送，中间不需另加隔离符号，只要传送时不出错，收端仍可分离各个码字，不致混淆。

哈夫曼编码，又称霍夫曼编码，是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫做Huffman编码。

扩展资料

赫夫曼编码的具体方法：先按出现的概率大小排队，把两个最小的概率相加，作为新的概率 和剩余的概率重新排队，再把最小的两个概率相加，再重新排队，直到最后变成1。

每次相 加时都将“0”和“1”赋与相加的两个概率，读出时由该符号开始一直走到最后的“1”， 将路线上所遇到的“0”和“1”按最低位到最高位的顺序排好，就是该符号的赫夫曼编码。

例如a7从左至右，由U至U″″，其码字为1000；

a6按路线将所遇到的“0”和“1”按最低位到最高位的顺序排好，其码字为1001…

用赫夫曼编码所得的平均比特率为：Σ码长×出现概率

上例为：0.2×2+0.19×2+0.18×3+0.17×3+0.15×3+0.1×4+0.01×4=2.72 bit

可以算出本例的信源熵为2.61bit，二者已经是很接近了。

参考资料来源：百度百科-哈夫曼编码

摘要: 多媒体通信技术是当今世界科技领域中最有活力、发展最快的高新信息技术，它时时刻刻都在影响着世界经济的发展和科学技术进步的速度，并不断改变着人类的生活方式和生活质量。多媒体通信综合了多种媒体信息间的通信，它是通过现有的各种通讯网来传输、转储和接收多媒体信息的通信方式，几乎覆盖了信息技术领域的所有范畴，包括数据、音频和视频的综合处理和应用技术，其关键技术是多媒体信息的高效传输和交互处理。关键词：多媒体 图象 音频 功能The application of multimedia technologyAbstract: Multimedia communications technology is the world's science and technology in the field of the most dynamic and fastest growing high-tech information technology, it always have influence in the world economic development and the pace of scientific and technological progress and changing the human way of life and quality of life . A variety of integrated multimedia communications between the communications media information, it is through the various existing communications network to transmit and receive multimedia information and dump the means of communication, cover nearly the area of information technology in all areas, including data, audio and video The integrated treatment and application technology, its technology is the key to the efficient transmission of multimedia information and interactive processingKey words: Multimedia audio features images引 言随着技术的迅速发展，图像、视频等多媒体数据已逐渐成为信息处理领域中主要的信息媒体形式。多媒体通信是信息高速公路建设中的一项关键技术，是多媒体、通信、计算机和网络等相互渗透和发展的产物，它将极大地提高人们的工作效率，改变人们的教育、娱乐等生活方式，是21世纪人们通信的基本方式。第一章 多媒体通信技术基础简介多媒体通信的基本概念和特征1.1 基本概念媒体是信息表示和传输的载体，是一个重要的概念。ITU-T I .374建议将媒体划分为感觉媒体、表示媒体、显示媒体、存储媒体和传输媒体5类。多媒体数据是指多种式样信息的载体，如文本、图形、图像、声音等数据。其特点主要有以下几点：（1）多媒体数据种类繁多（大多是非结构化数据），不同来源的媒体，具有完全不同的形式和格式；（2）多媒体数据量庞大；（3）多媒体数据具有时间特性和版本概念，如在视频点播系统中必须考虑到媒体间以及媒体内部在时间上的同步关系。由此可知多媒体数据与传统的数值和字符不同，因而其存储结构和存取方式也具有特殊性，描述它的数据结构和数据模型也是有差别的。在这种情况下就产生了一种全新的数据库系统--多媒体数据库系统。多媒体数据库是能够有效实现多媒体数据的存储、读取、检索等功能的数据库系统。它的主要特点是：（1）继承了传统数据库的一些优点，例如数据独立性、利用数据库查询语言进行高层次查询、开发控制、容错技术等；（2）能对具有时空关系的数据进行同步和管理。但是目前对于多媒体数据库的功能以及实现方法还没有达成共识，因而出现了多种形式的媒体数据库，并且实现方法也各不相同。从其总体发展上看，多媒体数据库的数据模型可分为关系数据模型、面向对象的数据模型和超媒体数据模型3类。基于不同数据模型的多媒体数据库管理系统（DBMS）的功能也有很大差别，通常基于关系数据模型的多媒体DBMS可以实现多媒体数据的存取，对多媒体数据对象之间的语义关系、时态关系、空间关系不加处理，所以这部分工作就留给应用程序去完成了。面向对象的数据模型和超媒体数据类型可以支持多媒体数据对象之间的语义关系、时态关系、空间关系的处理，其抽象程度更高，但DBMS的实现也相对复杂。在多媒体通信系统中另一个常出现的词汇是"超媒体"。在出版物中经常会出现表示注解意思的"注"字，由"注"你可以找到与之相关的一段文字或一篇文章。这种由"注"而链接到一段文字或一篇文章的链即称为超链拨，同理，超级链也可以将若干不同媒体链接起来，其集合便称为"超媒体"。1.2多媒体通信的特征多媒体通信技术的发展打破了传统通信的单一媒体、单一电信业务的通信系统格局，反映了通信向高层次发展的一种趋势，是人们对未来社会工作和生活方式的向往。多媒体通信技术是一种综合技术，涉及多媒体技术、计算机技术、通信技术等多个领域。多媒体通信系统必须同时兼有集成性、交互性、同步性3个主要特征。1.2.1 集成性多媒体通信系统的集成性指的是能对内容数据信息、多媒体和超媒体信息、脚本信息和特定的应用信息等4类信息进行存储、传输、处则和显现的能力。（1） 内容数据信息（2） 信息是以某一种结构的形式存在的，典型的结构有两种：一种是对象构，其中可处理的最小单元为对象(Object)；另一种是文件结构，其中处理的最小单元为文件（File）。多媒体和超媒体信息多媒体和超媒体信息与单媒体信息不一样，它们是结构化的信息，由结构框架和内容数据2部分组成。多媒体和超媒体信息的最小表达形式由两类，一类称为对象，另一类称为文件。（3） 脚本信息脚本信息是一组特定的用语意关系联系起来的、结构化的多媒体和超媒体信息，需要提供表示这一组多媒体信息的运作过程和与外部处理模块间的关系。（4） 特定的应用信息上述3类信息都是低层信息，可以由标准来定义和表示。特定的应用信息是高层信息，是与应用密切相关的，将随应用场合的不同有很大的不同，它的表示方法是基于上述3类的基础之上的。1.2.2 交互性交互性指的是在通信系统中人与系统之间的相互控制能力。在多媒体通信系统中，交互性有两个方面的内容。一是人机接口，也就是人在使用系统的终端时用户终端向用户提供的操作界面；二是用户终端与系统之间的应用层通信协议。多媒体通信终端的用户对通信的全过程有完备的交互控制能力，这是多媒体通信系统的一个主要特征，也是区别多媒体通信系统与非多媒体通信系统的一个主要准则。1.2.3 同步性同步性指的是在多媒体通信终端上显现的图像、声音和文字均以同步方式工作。如用户要检索一个重要的历史事件的片断，该事件的活动图像或静止图像存放在图像数据库中，其文字叙述和语言说明则是放在其他数据库中。多媒体通信终端通过不同传输途径将所需要的信息从不同的数据库中提取出来，并将这些图像、声音、文字同步起来，构成一个整体的信息呈现在用户面前。多媒体通信系统中的同步性是多媒体通信系统最主要的特征之一，信息的同步与否决定了系统是多媒体系统还是非多种媒体系统。同步可在链路层级、表示层级和应用层级3个层面上实现第二章 多媒体音频技术音频技术发展较早，几年前一些技术已经成熟并产品化，甚至进入了家庭，如数字音响。音频技术主要包括四个方面:音频数字化、语音处理、语音合成及语音识别。音频数字化目前是较为成熟的技术，多媒体声卡就是采用此技术而设计的，数字音响也是采用了此技术取代传统的模拟方式而达到了理想的音响效果。音频采样包括两个重要的参数即采样频率和采样数据位数。采样频率即对声音每秒钟采样的次数，人耳听觉上限在20KHz左右，目前常用的采样频率为11KHz，22KHz和44KHz几种。采样频率越高音质越好，存贮数据量越大。CD唱片采样频率为44.1KHz，达到了目前最好的听觉效果。采样数据位数即每个采样点的数据表示范围，目前常用的有8位、12位和16位三种。不同的采样数据位数决定了不同的音质，采样位数越高，存贮数据量越大，音质也越好。CD唱片采用了双声道16位采样，采样频率为44.1KHz，因而达到了专业级水平。音频处理包括范围较广，但主要方面集中在音频压缩上，目前最新的MPEG语音压缩算法可将声音压缩六倍。语音合成是指将正文合成为语言播放，目前国外几种主要语音的合成水平均已到实用阶段，汉语合成几年来也有突飞猛进的发展，实验系统正在运行。在音频技术中难度最大最吸引人的技术当属语音识别，虽然目前只是处于实验研究阶段，但是广阔的应用前景使之一直成为研究关注的热点之一。第三章 多媒体图像视频技术3．1视频技术虽然视频技术发展的时间较短，但是产品应用范围已经很大，与MPEG压缩技术结合的产品已开始进入家庭。视频技术包括视频数字化和视频编码技术两个方面。视频数字化是将模拟视频信号经模数转换和彩色空间变换转为计算机可处理的数字信号，使得计算机可以显示和处理视频信号。目前采样格式有两种:Y:U:V4:1:1和Y:U:V4:2:2，前者是早期产品采用的主要格式，Y:U:V4:2:2格式使得色度信号采样增加了一倍，视频数字化后的色彩、清晰度及稳定性有了明显的改善，是下一代产品的发展方向。视频编码技术是将数字化的视频信号经过编码成为电视信号，从而可以录制到录像带中或在电视上播放。对于不同的应用环境有不同的技术可以采用。从低档的游戏机到电视台广播级的编码技术都已成熟。3.2图像压缩技术图像压缩一直是技术热点之一，它的潜在价值相当大，是计算机处理图像和视频以及网络传输的重要基础，目前ISO制订了两个压缩标准即JPEG和MPEG。JPEG是静态图像的压缩标准,适用于连续色调彩色或灰度图像。它包括两部分:一是基于DPCM(空间线性预测)技术的无失真编码，一是基于DCT(离散余弦变换)和哈夫曼编码的有失真算法。前者图像压缩无失真，但是压缩比很小，目前主要应用的是后一种算法，图像有损失但压缩比很大，压缩20倍左右时基本看不出失真。MJPEG是指MotionJPEG，即按照25帧/秒速度使用JPEG算法压缩视频信号，完成动态视频的压缩。MPEG算法是适用于动态视频的压缩算法，它除了对单幅图像进行编码以外还利用图像序列中的相关原则，将帧间的冗余去掉，这样大大提高了图像的压缩比例。通常保持较高的图像质量而压缩比高达100倍。MPEG算法的缺点是压缩算法复杂，实现很困难。第四章 多媒体通信系统1、 体系结构多媒体通信(multimedia communcations)是在位于不同地理位置的参与者之间召开的一种会议或者进行的交流，通过局域网(LAN)、广域网(WAN)、内联网(intranet)、因特网(Internet)或者电话网来传输压缩的数字图像和声音信号。像电视那样的多目标广播、录象机那样的流式播放、电话会议、电视会议、IP电话、可视电话和IP传真等等都是多媒体通信技术的一些具体的和各有特色的应用。多年来，国际电信联盟(ITU)为公共和私营电信组织制定了许多多媒体计算和通信系统的推荐标准，以促进各国之间的电信合作。ITU的26个(Series A～Z)系列推荐标准中，与多媒体通信关系最密切的7个系列标准如表4-1所示，三种类型的多媒体通信系统的核心技术标准集如表4-1所示。表4-1 ITU系列推荐标准系列名 主要内容Series G 传输系统、媒体数字系统和网络Series H 视听和多媒体系统Series I 综合业务数字网(ISDN)Series J 电视、声音节目和其他多媒体信号的传输Series Q 电话交换和控制信号传输法Series T 远程信息处理业务的终端设备2、网关的功能和结构网关是一台功能强大的计算机或者工作站，它担负线路交换网络(如电话网络)和信息包交换网络(如因特网)之间进行实时的双向通信，提供异种网络之间的连通性，它是传统线路交换网络和现代IP网络之的桥梁。IP电话(见"7.4 IP电话")的出现允许电话呼叫在信息包交换网络上进行，从而引发一场电信工业的革命。但IP电话在成为主流电话服务的道路上遇到了许多障碍。其中最大的一个问题是在IP电话网络和公众交换电话网络之间缺乏连通性。一个重要的原因是早期的网关存在对IP电话进入主流电话服务的限制。例如，通过网关建立呼叫比较困难，而且需要使用非常规的电话号码；不同的网关之间的兼容性妨碍呼叫的建立；声音的质量比较差、有回音以及延迟时间比较长等。这就促进了开发允许IP和PSTN客户能够相互通信的网关，其中的一个措施就是提高网关的处理能力。低档的网关有1～6个端口，典型地使用高档奔腾处理器的PC机方案，提供媒体处理、呼叫控制和信息包的处理等网关功能。高档网关把网关功能分散到几个处理器来实现，这叫做计算机基电话集成(computer-telephony integration，CTI)平台，可提供100多个端口。网关的基本功能可归纳为三种：(1) 转换协议(translating protocols)：网关作为一个解释器，使不同的网络能够建立联系，例如，允许PSTN和H.323网络相互对话以建立和清除呼叫。(2) 转换信息格式(converting information formats)：不同的网络使用不同的编码方法，网关将对信息进行转换，使异种网络之间能够自由地交换信息，例如声音和电视。(3) 传输信息(transferring information)：负责在不同网络之间传输信息。网关的主要部件包括：(1) 线路交换网络(switched-circuit network，SCN)接口卡，这是一种典型的T1/E1或者叫做PRI ISDN线路接口卡，它们与线路交换网络进行通信。主速率接口(primary rate interface，PRI)由23个B通道和一个64 kb/s的D通道组成，叫做23B＋D，相当于T1线的带宽。(2) 数字信号处理器(digital signal processors，DSP)卡，它执行的任务包括声音信号的压缩和回音的取消等。(3) 网络接口(network interfaces)卡，它用来与H.323网络进行通信，典型的网络卡包括10/100BaseT网络接口卡(network interface cards，NIC)，或者把它们的功能集成到主机板上。(4) 控制处理器(control processor)，它协调其他网关部件的所有活动，这个部件通常是在系统的主机板上。网关的主要软件包括：(1) 执行所有网关基本功能和选择功能的网关软件。例如，H.323网关平台(Gateway Platform)执行转换协议、转换消息格式和传输信息等基本功能，支持声音压缩、协议转换、实时的传真解调/再调制以及执行H.323系列协议。(2) 特定网关的应用软件，它执行自定义的功能以及管理和控制功能。3、会务器的功能和结构会务器(gatekeepers)是用于连接IP网络上的H.323电视会议客户，是电视会议的关键部件之一，许多人把它当作电视会议的"大脑"。它提供授权和验证、保存和维护呼叫记录、执行地址转换而不需要你去记忆IP地址、监视网络、管理带宽以限制同时呼叫的数目从而保证电视会议的质量、以及提供与现存系统的接口。会务器的功能一般都是用软件来实现。会务器的功能分成两个部分：基本功能和选择功能。会务器必须要提供的基本功能包括："地址转换(Address Translation)：使用一种可由注册消息(Registration messages)更新的转换表，把别名地址转换成传输地址(Transport Address)。这个功能在线路交换网络上的电话企图呼叫IP网络上的PC时显得尤其重要，在确定网关地址时也很重要。准入控制(Admissions Control)：使用准入请求/准入确认/准入拒绝ARQ/ARC/ARJ(Admission Request, Confirm and Reject)消息，对访问局域网进行授权。H323标准规定必须要有用来对网络服务进行授权的RAS消息(RAS messages)，RAS是一个注册/准入/状态(Registration/Admission/Status)协议，但它不定义授权存取网络资源的规则或者政策，因此服务提供者需要会务器来干预现存的授权方法。此外，企业管理人员和服务提供者也许想使用他自己的标准来授权，例如，根据订金、信用卡等。带宽控制(Bandwidth Control)：支持RAS带宽消息(RAS bandwidth messages)，即带宽请求/带宽确认/带宽拒绝BRQ/BCF/BRJ(Request, Confirm and Reject)消息，以强制执行带宽控制。至于如何管理则要根据服务提供者或者企业管理人员的政策来确定。在许多情况下，如果在网络或者特定的网关不拥挤的况下，对任何带宽的请求都应该给予满足。区域管理(Zone Management)：用于管理所有已经注册的H.323端点(endpoint)，为它们提供上面介绍的功能。至于确定哪个终端可以注册以及地理或者逻辑区域的组成(单个会务器管理的终端、网关和多点控制单元MCU)则由网络设计人员决定。会务器提供的选择功能包括:呼叫控制信号传输方法(Call Control Signalling)：在H.323中有两种呼叫控制信号传输模型：会务器安排呼叫信号传输模型(Gatekeeper Routed Call Signaling Model)和直接端点呼叫信号传输模型(Direct Endpoint Call Signaling Model)。会务器可根据访问提供者的要求进行选择。呼叫授权(Call Authorization)：会务器可根据服务提供者指定的条件对一个给定的呼叫进行授权或者拒绝。其条件可包括会议时间、预定的服务类型、对受限网关的访问权限或者可用的带宽等。带宽管理(Bandwidth Management)：根据服务提供者指定的带宽分配确定是否有足够的带宽用于呼叫。呼叫管理(Call Management)：提供智能呼叫管理。会务器维护一种H.323呼叫表以指示被呼叫终端是否处于忙状态，并为带宽管理(Bandwidth Management)功能提供信息。会务器的结构会务器通常设计成内外两层，如图4-8所示。会务器的内层叫做核心层，它由执行H.323协议堆的软件和实现多点控制单元MCU(multipoint control unit)功能的软件组成，有的软件开发公司把它叫做H.323会务器核心功能部件。MCU的主要功能是连接多条线路并自动或者在会议主持人的指导下手动交换电视号。会务器的外层由许多应用程序的接口组成，用于连接网络上现有的许多服务。外层软件