赫夫曼编码译码毕业论文
#include 八成是数据结构的大作业吧.... 我把网上的程序修改了一下，并整合了，你看看#include<>#include<>#include<>#define M 50#define MAX 100000;typedef struct{ int weight;//结点权值 int parent,lchild,rchild;}HTNODE,*HUFFMANTREE;typedef char** HUFFMANCODE;//动态分配数组存储哈夫曼编码表typedef struct{ int key; /*关键字*/}RecordNode; /*排序节点的类型*/typedef struct{ RecordNode *record; int n; /*排序对象的大小*/}SortObject; //待排序序列 HUFFMANTREE huffmantree(int n,int weight[])//构建哈夫曼树{ int m1,m2,k; int i,j,x1,x2; HUFFMANTREE ht; ht=(HUFFMANTREE)malloc((2*n)*sizeof(HTNODE)); for(i=1;i<(2*n);i++)//初始化哈夫曼树中各结点的数据，没初始值的赋值为0 { ht[i].parent=ht[i].lchild=ht[i].rchild=0; if(i<=n) ht[i].weight=weight[i]; else ht[i].weight=0; } for(i=1;i class HaffmanNode //哈夫曼树的结点类{ int weight; //权值 int parent,left,right; //父母结点和左右孩子下标 public HaffmanNode(int weight) { = weight; ; ; ; } public HaffmanNode() { this(0); } public String toString() { return ", "+", "+", "+; } return code; } public static void main(String[] args) { int[] weight={5,29,7,8,14,23,3,11}; //指定权值集合 HaffmanTree htree = new HaffmanTree(weight); ("哈夫曼树的结点数组:\n"+()); String[] code = (); ("哈夫曼编码:"); for (int i=0; i<; i++) (code[i]); }}希望能解决您的问题。 霍夫曼编码计算过程：无损数据压缩的熵编码。 在计算机数据处理中，霍夫曼编码使用变长编码表对源符号（如文件中的一个字母）进行编码，其中变长编码表是通过一种评估来源符号出现机率的方法得到的，出现机率高的字母使用较短的编码，反之出现机率低的则使用较长的编码，这便使编码之后的字符串的平均长度、期望值降低，从而达到无损压缩数据的目的。 例如，在英文中，e的出现机率最高，而z的出现概率则最低。当利用霍夫曼编码对一篇英文进行压缩时，e极有可能用一个比特来表示，而z则可能花去25个比特（不是26）。用普通的表示方法时，每个英文字母均占用一个字节，即8个比特。 二者相比，e使用了一般编码的1/8的长度，z则使用了3倍多。倘若我们能实现对于英文中各个字母出现概率的较准确的估算，就可以大幅度提高无损压缩的比例。 霍夫曼编码历史： 1951年，霍夫曼在麻省理工学院（MIT）攻读博士学位，他和修读信息论课程的同学得选择是完成学期报告还是期末考试。导师罗伯特·法诺（Robert Fano）出的学期报告题目是：查找最有效的二进制编码。 由于无法证明哪个已有编码是最有效的，霍夫曼放弃对已有编码的研究，转向新的探索，最终发现了基于有序频率二叉树编码的想法，并很快证明了这个方法是最有效的。霍夫曼使用自底向上的方法构建二叉树，避免了次优算法香农-范诺编码（Shannon–Fano coding）的最大弊端──自顶向下构建树。 1952年，于论文《一种构建极小多余编码的方法》（A Method for the Construction of Minimum-Redundancy Codes）中发表了这个编码方法。 多媒体图像压缩技术姓名:Vencent Lee摘要：多媒体数据压缩技术是现代网络发展的关键性技术之一。由于图像和声音信号中存在各种各样的冗余，为数据压缩提供了可能。数据压缩技术有无损压和有损压缩两大类，这些压缩技术又各有不同的标准。一、多媒体数据压缩技术仙农(C．E．Shannon)在创立信息论时，提出把数据看作是信息和冗余度的组合。早期的数据压缩之所以成为信息论的一部分是因为它涉及冗余度问题。而数据之所以能够被压缩是因为其中存在各种各样的冗余；其中有时间冗余性、空间冗余性、信息熵冗余、先验知识冗余、其它冗余等。时间冗余是语音和序列图像中常见的冗余，运动图像中前后两帧间就存在很强的相关性，利用帧间运动补兴就可以将图像数据的速率大大压缩。语音也是这样。尤其是浊音段，在相当长的时间内(几到几十毫秒)语音信号都表现出很强的周期性，可以利用线性预测的方法得到较高的压缩比。空间冗余是用来表示图像数据中存在的某种空间上的规则性，如大面积的均匀背景中就有很大的空间冗余性。信息熵冗余是指在信源的符号表示过程中由于未遵循信息论意义下最优编码而造成的冗余性，这种冗余性可以通过熵编码来进行压缩，经常使用的如Huff-man编码。先验知识冗余是指数据的理解与先验知识有相当大的关系，如当收信方知道一个单词的前几个字母为administrato时，立刻就可以猜到最后一个字母为r，那么在这种情况下，最后一个字母就不带任何信息量了，这就是一种先验知识冗余。其它冗余是指那些主观无法感受到的信息等带来的冗余。通常数据压缩技术可分为无损压缩(又叫冗余压缩)和有损压缩(又叫熵压缩)两大类。无损压缩就是把数据中的冗余去掉或减少，但这些冗余量是可以重新插入到数据中的，因而不会产生失真。该方法一般用于文本数据的压缩，它可以保证完全地恢复原始数据；其缺点是压缩比小(其压缩比一般为2：1至5：1)。有损压缩是对熵进行压缩，因而存在一定程度的失真；它主要用于对声音、图像、动态视频等数据进行压缩，压缩比较高(其压缩比一般高达20：1以上。最新被称为“E—igen—ID”的压缩技术可将基因数据压缩1．5亿倍)。对于多媒体图像采用的有损压缩的标准有静态图像压缩标准(JPEG标准，即‘JointPhotographicExpertGroup’标准)和动态图像压缩标准(MPEG标准，即‘MovingPictureExpertGroup’标准)。JPEG利用了人眼的心理和生理特征及其局限性来对彩色的、单色的和多灰度连续色调的、静态图像的、数字图像的压缩，因此它非常适合不太复杂的以及一般来源于真实景物的图像。它定义了两种基本的压缩算法：一种是基于有失真的压缩算法，另一种是基于空间线性预测技术(DPCM)无失真的压缩算法。为了满足各种需要，它制定了四种工作模式：无失真压缩、基于DCT的顺序工作方式、累进工作方式和分层工作方式。MPEG用于活动影像的压缩。MPEG标准具体包三部分内容：(1)MPEG视频、(2)MPEG音频、(3)MP系统(视频和音频的同步)。MPEG视频是标准的核心分，它采用了帧内和帧间相结合的压缩方法，以离散余变换(DCT)和运动补偿两项技术为基础，在图像质量基不变的情况下，MPEG可把图像压缩至1／100或更MPEG音频压缩算法则是根据人耳屏蔽滤波功能。利用音响心理学的基本原理，即“某些频率的音响在重放其频率的音频时听不到”这样一个特性，将那些人耳完全不到或基本上听到的多余音频信号压缩掉，最后使音频号的压缩比达到8：1或更高，音质逼真，与CD唱片可媲美。按照MPEG标准，MPEG数据流包含系统层和压层数据。系统层含有定时信号，图像和声音的同步、多分配等信息。压缩层包含经压缩后的实际的图像和声数据，该数据流将视频、音频信号复合及同步后，其数据输率为1．5MB／s。其中压缩图像数据传输率为1．2M压缩声音传输率为0．2MB／s。MPEG标准的发展经历了MPEG—I,MPEG一2、MPEG一4、MPEG-7、MPEG一21等不同层次。在MPEG的不同标准中，每—个标准都是建立在前面的标准之上的，并与前面的标准向后的兼容。目前在图像压缩中，应用得较多的是MPEG一4标准，MPEG-是在MPEG-2基础上作了很大的扩充，主要目标是多媒体应用。在MPEG一2标准中，我们的观念是单幅图像，而且包含了一幅图像的全部元素。在MPEG一4标准下，我们的观念变为多图像元素，其中的每—个多图像元素都是独立编码处理的。该标准包含了为接收器所用的指令，告诉接收器如何构成最终的图像。上图既表示了MPEG一4解码器的概念，又比较清楚地描绘了每个部件的用途。这里不是使用单一的视频或音频解码器，而是使用若干个解码器，其中的每一个解码器只接收某个特定的图像(或声音)元素，并完成解码操作。每个解码缓冲器只接收属于它自己的灵敏据流，并转送给解码器。复合存储器完成图像元素的存储，并将它们送到显示器的恰当位置。音频的情况也是这样，但显然不同点是要求同时提供所有的元素。数据上的时间标记保证这些元素在时间上能正确同步。MPEG一4标准对自然元素(实物图像)和合成元素进行区分和规定，计算机生成的动画是合成元素的一个例子。比如，一幅完整的图像可以包含一幅实际的背景图，并在前面有一幅动画或者有另外一幅自然图像。这样的每一幅图像都可以作最佳压缩，并互相独立地传送到接收器，接收器知道如何把这些元素组合在一起。在MPEG一2标准中，图像被看作一个整体来压缩；而在MPEG一4标准下，对图像中的每一个元素进行优化压缩。静止的背景不必压缩到以后的I帧之中去，否则会使带宽的使用变得很紧张。而如果这个背景图像静止10秒钟，就只要传送一次(假设我们不必担心有人在该时间内切人此频道)，需要不断传送的仅是前台的比较小的图像元素。对有些节目类型，这样做会节省大量的带宽。MPEG一4标准对音频的处理也是相同的。例如，有一位独唱演员，伴随有电子合成器，在MPEG一2标准下，我们必须先把独唱和合成器作混合，然后再对合成的音频信号进行压缩与传送。在MPEG一4标准下，我们可以对独唱作单独压缩，然后再传送乐器数字接口的声轨信号，就可以使接收器重建伴音。当然，接收器必须能支持MIDI放音。与传送合成的信号相比，分别传送独唱信号和MIDI数据要节省大量的带宽。其它的节目类型同样可以作类似的规定。MPEG一7标准又叫多媒体内容描述接口标准。图像可以用色彩、纹理、形状、运动等参数来描述，MPEG一7标准是依靠众多的参数对图像与声音实现分类，并对它们的数据库实现查询。二、多媒体数据压缩技术的实现方法目前多媒体压缩技术的实现方法已有近百种，其中基于信源理论编码的压缩方法、离散余弦变换(DCT)和小波分解技术压缩算法的研究更具有代表性。小波技术突破了传统压缩方法的局限性，引入了局部和全局相关去冗余的新思想，具有较大的潜力，因此近几年来吸引了众多的研究者。在小波压缩技术中，一幅图像可以被分解为若干个叫做“小片”的区域；在每个小片中，图像经滤波后被分解成若干个低频与高频分量。低频分量可以用不同的分辨率进行量化，即图像的低频部分需要许多的二进制位，以改善图像重构时的信噪比。低频元素采用精细量化，高频分量可以量化得比较粗糙，因为你不太容易看到变化区域的噪声与误差。此外，碎片技术已经作为一种压缩方法被提出，这种技术依靠实际图形的重复特性。用碎片技术压缩图像时需要占用大量的计算机资源，但可以获得很好的结果。借助于从DNA序列研究中发展出来的模式识别技术，能减少通过WAN链路的流量，最多时的压缩比率能达到90％，从而为网络传送图像和声音提供更大的压缩比，减轻风络负荷，更好地实现网络信息传播。三、压缩原理由于图像数据之间存在着一定的冗余，所以使得数据的压缩成为可能。信息论的创始人Shannon提出把数据看作是信息和冗余度（redundancy）的组合。所谓冗余度，是由于一副图像的各像素之间存在着很大的相关性，可利用一些编码的方法删去它们，从而达到减少冗余压缩数据的目的。为了去掉数据中的冗余，常常要考虑信号源的统计特性，或建立信号源的统计模型。图像的冗余包括以下几种：(1) 空间冗余：像素点之间的相关性。(2) 时间冗余：活动图像的两个连续帧之间的冗余。(3) 信息熵冗余：单位信息量大于其熵。(4) 结构冗余：图像的区域上存在非常强的纹理结构。(5) 知识冗余：有固定的结构，如人的头像。(6) 视觉冗余：某些图像的失真是人眼不易觉察的。对数字图像进行压缩通常利用两个基本原理：(1) 数字图像的相关性。在图像的同一行相邻像素之间、活动图像的相邻帧的对应像素之间往往存在很强的相关性，去除或减少这些相关性，也就去除或减少图像信息中的冗余度，即实现了对数字图像的压缩。(2) 人的视觉心理特征。人的视觉对于边缘急剧变化不敏感(视觉掩盖效应)，对颜色分辨力弱，利用这些特征可以在相应部分适当降低编码精度，而使人从视觉上并不感觉到图像质量的下降，从而达到对数字图像压缩的目的。编码压缩方法有许多种，从不同的角度出发有不同的分类方法，比如从信息论角度出发可分 为两大类：(1)冗余度压缩方法，也称无损压缩，信息保持编码或熵编码。具体讲就是解码图像和压缩 编码前的图像严格相同，没有失真，从数学上讲是一种可逆运算。(2)信息量压缩方法，也称有损压缩，失真度编码或熵压缩编码。也就是讲解码图像和原始图像是有差别的，允许有一定的失真。应用在多媒体中的图像压缩编码方法，从压缩编码算法原理上可以分类为：(1)无损压缩编码种类 •哈夫曼编码 •算术编码 •行程编码 •Lempel zev编码(2)有损压缩编码种类 •预测编码：DPCM，运动补偿 •频率域方法：正文变换编码(如DCT)，子带编码 •空间域方法：统计分块编码 •模型方法：分形编码，模型基编码 •基于重要性：滤波，子采样，比特分配，矢量量化(3)混合编码 •JBIG，H261，JPEG，MPEG等技术标准衡量一个压缩编码方法优劣的重要指标(1)压缩比要高，有几倍、几十倍，也有几百乃至几千倍；(2)压缩与解压缩要快，算法要简单，硬件实现容易；(3)解压缩的图像质量要好。四、JPEG图像压缩算法1．.JPEG压缩过程JPEG压缩分四个步骤实现：1.颜色模式转换及采样；变换；3.量化；4.编码。2．1．颜色模式转换及采样RGB色彩系统是我们最常用的表示颜色的方式。JPEG采用的是YCbCr色彩系统。想要用JPEG基本压缩法处理全彩色图像，得先把RGB颜色模式图像数据，转换为YCbCr颜色模式的数据。Y代表亮度，Cb和Cr则代表色度、饱和度。通过下列计算公式可完成数据转换。Y=＋128人类的眼晴对低频的数据比对高频的数据具有更高的敏感度，事实上，人类的眼睛对亮度的改变也比对色彩的改变要敏感得多，也就是说Y成份的数据是比较重要的。既然Cb成份和Cr成份的数据比较相对不重要，就可以只取部分数据来处理。以增加压缩的比例。JPEG通常有两种采样方式：YUV411和YUV422，它们所代表的意义是Y、Cb和Cr三个成份的资料取样比例。2．变换DCT变换的全称是离散余弦变换(Discrete Cosine Transform)，是指将一组光强数据转换成频率数据，以便得知强度变化的情形。若对高频的数据做些修饰，再转回原来形式的数据时，显然与原始数据有些差异，但是人类的眼睛却是不容易辨认出来。压缩时，将原始图像数据分成8*8数据单元矩阵，例如亮度值的第一个矩阵内容如下：JPEG将整个亮度矩阵与色度Cb矩阵，饱和度Cr矩阵，视为一个基本单元称作MCU。每个MCU所包含的矩阵数量不得超过10个。例如，行和列采样的比例皆为4:2:2，则每个MCU将包含四个亮度矩阵，一个色度矩阵及一个饱和度矩阵。当图像数据分成一个8*8矩阵后，还必须将每个数值减去128，然后一一代入DCT变换公式中，即可达到DCT变换的目的。图像数据值必须减去128，是因为DCT转换公式所接受的数字范围是在-128到+127之间。DCT变换公式：x,y代表图像数据矩阵内某个数值的坐标位置f(x,y)代表图像数据矩阵内的数个数值u,v代表DCT变换后矩阵内某个数值的坐标位置F(u,v)代表DCT变换后矩阵内的某个数值u=0 且 v=0 c(u)c(v)=1/>0 或 v>0 c(u)c(v)=1经过DCT变换后的矩阵数据自然数为频率系数，这些系数以F（0，0）的值最大，称为DC，其余的63个频率系数则多半是一些接近于0的正负浮点数，一概称之为AC。3．3、量化图像数据转换为频率系数后，还得接受一项量化程序，才能进入编码阶段。量化阶段需要两个8*8矩阵数据，一个是专门处理亮度的频率系数，另一个则是针对色度的频率系数，将频率系数除以量化矩阵的值，取得与商数最近的整数，即完成量化。当频率系数经过量化后，将频率系数由浮点数转变为整数，这才便于执行最后的编码。不过，经过量化阶段后，所有数据只保留整数近似值，也就再度损失了一些数据内容，JPEG提供的量化表如下：2．4、编码Huffman编码无专利权问题，成为JPEG最常用的编码方式，Huffman编码通常是以完整的MCU来进行的。编码时，每个矩阵数据的DC值与63个AC值，将分别使用不同的Huffman编码表，而亮度与色度也需要不同的Huffman编码表，所以一共需要四个编码表，才能顺利地完成JPEG编码工作。DC编码DC是彩采用差值脉冲编码调制的差值编码法，也就是在同一个图像分量中取得每个DC值与前一个DC值的差值来编码。DC采用差值脉冲编码的主要原因是由于在连续色调的图像中，其差值多半比原值小，对差值进行编码所需的位数，会比对原值进行编码所需的位数少许多。例如差值为5，它的二进制表示值为101，如果差值为-5，则先改为正整数5，再将其二进制转换成1的补码即可。所谓1的补码，就是将每个Bit若值为0，便改成1；Bit为1，则变成0。差值5应保留的位数为3，下表即列出差值所应保留的Bit数与差值内容的对照。在差值前端另外加入一些差值的霍夫曼码值，例如亮度差值为5（101）的位数为3，则霍夫曼码值应该是100，两者连接在一起即为100101。下列两份表格分别是亮度和色度DC差值的编码表。根据这两份表格内容，即可为DC差值加上霍夫曼码值，完成DC的编码工作。AC编码AC编码方式与DC略有不同，在AC编码之前，首先得将63个AC值按Zig-zag排序，即按照下图箭头所指示的顺序串联起来。63个AC值排列好的，将AC系数转换成中间符号，中间符号表示为RRRR/SSSS，RRRR是指第非零的AC之前，其值为0的AC个数，SSSS是指AC值所需的位数，AC系数的范围与SSSS的对应关系与DC差值Bits数与差值内容对照表相似。如果连续为0的AC个数大于15，则用15/0来表示连续的16个0，15/0称为ZRL（Zero Rum Length），而（0/0）称为EOB（Enel of Block）用来表示其后所剩余的AC系数皆等于0，以中间符号值作为索引值，从相应的AC编码表中找出适当的霍夫曼码值，再与AC值相连即可。例如某一组亮度的中间符为5/3，AC值为4，首先以5/3为索引值，从亮度AC的Huffman编码表中找到1111111110011110霍夫曼码值，于是加上原来100（4）即是用来取[5，4]的Huffman编码1111111110011110100，[5，4]表示AC值为4的前面有5个零。由于亮度AC，色度AC霍夫曼编码表比较长，在此省略去，有兴趣者可参阅相关书籍。实现上述四个步骤，即完成一幅图像的JPEG压缩。 Content as follows: no distortion source coding is a kind of when source symbols, can convert code without distortion from code returned to the original source of the source coding symbols. This paper firstly introduces the without distortion encoding technology development and application; Then discussed emphatically shannon coding, feanor coding, hoffmann coding and the arithmetic coding of four kinds of coding method, the principle and encoding steps are compared with the corresponding sample the average yards long and information transmission speed; Finally, using the Matlab software realize the coding hoffmann the simulation process, also gives part of the source program, and illustrates the application of output, analysed and corresponding conclusions. 哈夫曼编码(Huffman Coding)是一种编码方式，以哈夫曼树—即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。 在计算机信息处理中，“哈夫曼编码”是一种一致性编码法（又称"熵编码法"），用于数据的无损耗压缩。这一术语是指使用一张特殊的编码表将源字符（例如某文件中的一个符号）进行编码。这张编码表的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起来的（出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的）。这种方法是由发展起来的。 例如，在英文中，e的出现概率很高，而z的出现概率则最低。当利用哈夫曼编码对一篇英文进行压缩时，e极有可能用一个位(bit)来表示，而z则可能花去25个位（不是26）。用普通的表示方法时，每个英文字母均占用一个字节（byte），即8个位。二者相比，e使用了一般编码的1/8的长度，z则使用了3倍多。倘若我们能实现对于英文中各个字母出现概率的较准确的估算，就可以大幅度提高无损压缩的比例。 本文描述在网上能够找到的最简单，最快速的哈夫曼编码。本方法不使用任何扩展动态库，比如STL或者组件。只使用简单的C函数，比如：memset，memmove，qsort，malloc，realloc和memcpy。 因此，大家都会发现，理解甚至修改这个编码都是很容易的。 背景 哈夫曼压缩是个无损的压缩算法，一般用来压缩文本和程序文件。哈夫曼压缩属于可变代码长度算法一族。意思是个体符号（例如，文本文件中的字符）用一个特定长度的位序列替代。因此，在文件中出现频率高的符号，使用短的位序列，而那些很少出现的符号，则用较长的位序列。 编码使用 我用简单的C函数写这个编码是为了让它在任何地方使用都会比较方便。你可以将他们放到类中，或者直接使用这个函数。并且我使用了简单的格式，仅仅输入输出缓冲区，而不象其它文章中那样，输入输出文件。 bool CompressHuffman(BYTE *pSrc, int nSrcLen, BYTE *&pDes, int &nDesLen); bool DecompressHuffman(BYTE *pSrc, int nSrcLen, BYTE *&pDes, int &nDesLen); 要点说明 速度 为了让它()快速运行，我花了很长时间。同时，我没有使用任何动态库，比如STL或者MFC。它压缩1M数据少于100ms（P3处理器，主频1G）。 压缩 压缩代码非常简单，首先用ASCII值初始化511个哈夫曼节点： CHuffmanNode nodes[511]; for(int nCount = 0; nCount < 256; nCount++) nodes[nCount].byAscii = nCount; 然后，计算在输入缓冲区数据中，每个ASCII码出现的频率： for(nCount = 0; nCount < nSrcLen; nCount++) nodes[pSrc[nCount]].nFrequency++; 然后，根据频率进行排序： qsort(nodes, 256, sizeof(CHuffmanNode), frequencyCompare); 现在，构造哈夫曼树，获取每个ASCII码对应的位序列： int nNodeCount = GetHuffmanTree(nodes); 构造哈夫曼树非常简单，将所有的节点放到一个队列中，用一个节点替换两个频率最低的节点，新节点的频率就是这两个节点的频率之和。这样，新节点就是两个被替换节点的父节点了。如此循环，直到队列中只剩一个节点（树根）。 // parent node pNode = &nodes[nParentNode++]; // pop first child pNode->pLeft = PopNode(pNodes, nBackNode--, false); // pop second child pNode->pRight = PopNode(pNodes, nBackNode--, true); // adjust parent of the two poped nodes pNode->pLeft->pParent = pNode->pRight->pParent = pNode; // adjust parent frequency pNode->nFrequency = pNode->pLeft->nFrequency + pNode->pRight->nFrequency; 这里我用了一个好的诀窍来避免使用任何队列组件。我先前就直到ASCII码只有256个，但我分配了511个(CHuffmanNode nodes[511])，前255个记录ASCII码，而用后255个记录哈夫曼树中的父节点。并且在构造树的时候只使用一个指针数组(ChuffmanNode *pNodes[256])来指向这些节点。同样使用两个变量来操作队列索引(int nParentNode = nNodeCount;nBackNode = nNodeCount –1)。 接着，压缩的最后一步是将每个ASCII编码写入输出缓冲区中： int nDesIndex = 0; // loop to write codes for(nCount = 0; nCount < nSrcLen; nCount++) { *(DWORD*)(pDesPtr+(nDesIndex>>3)) |= nodes[pSrc[nCount]].dwCode << (nDesIndex&7); nDesIndex += nodes[pSrc[nCount]].nCodeLength; } (nDesIndex>>3): >>3 以8位为界限右移后到达右边字节的前面 (nDesIndex&7): &7 得到最高位. 注意：在压缩缓冲区中，我们必须保存哈夫曼树的节点以及位序列，这样我们才能在解压缩时重新构造哈夫曼树（只需保存ASCII值和对应的位序列）。 解压缩 解压缩比构造哈夫曼树要简单的多，将输入缓冲区中的每个编码用对应的ASCII码逐个替换就可以了。只要记住，这里的输入缓冲区是一个包含每个ASCII值的编码的位流。因此，为了用ASCII值替换编码，我们必须用位流搜索哈夫曼树，直到发现一个叶节点，然后将它的ASCII值添加到输出缓冲区中： int nDesIndex = 0; DWORD nCode; while(nDesIndex < nDesLen) { nCode = (*(DWORD*)(pSrc+(nSrcIndex>>3)))>>(nSrcIndex&7); pNode = pRoot; while(pNode->pLeft) { pNode = (nCode&1) ? pNode->pRight : pNode->pLeft; nCode >>= 1; nSrcIndex++; } pDes[nDesIndex++] = pNode->byAscii; } 多媒体图像压缩技术姓名:Vencent Lee摘要：多媒体数据压缩技术是现代网络发展的关键性技术之一。由于图像和声音信号中存在各种各样的冗余，为数据压缩提供了可能。数据压缩技术有无损压和有损压缩两大类，这些压缩技术又各有不同的标准。一、多媒体数据压缩技术仙农(C．E．Shannon)在创立信息论时，提出把数据看作是信息和冗余度的组合。早期的数据压缩之所以成为信息论的一部分是因为它涉及冗余度问题。而数据之所以能够被压缩是因为其中存在各种各样的冗余；其中有时间冗余性、空间冗余性、信息熵冗余、先验知识冗余、其它冗余等。时间冗余是语音和序列图像中常见的冗余，运动图像中前后两帧间就存在很强的相关性，利用帧间运动补兴就可以将图像数据的速率大大压缩。语音也是这样。尤其是浊音段，在相当长的时间内(几到几十毫秒)语音信号都表现出很强的周期性，可以利用线性预测的方法得到较高的压缩比。空间冗余是用来表示图像数据中存在的某种空间上的规则性，如大面积的均匀背景中就有很大的空间冗余性。信息熵冗余是指在信源的符号表示过程中由于未遵循信息论意义下最优编码而造成的冗余性，这种冗余性可以通过熵编码来进行压缩，经常使用的如Huff-man编码。先验知识冗余是指数据的理解与先验知识有相当大的关系，如当收信方知道一个单词的前几个字母为administrato时，立刻就可以猜到最后一个字母为r，那么在这种情况下，最后一个字母就不带任何信息量了，这就是一种先验知识冗余。其它冗余是指那些主观无法感受到的信息等带来的冗余。通常数据压缩技术可分为无损压缩(又叫冗余压缩)和有损压缩(又叫熵压缩)两大类。无损压缩就是把数据中的冗余去掉或减少，但这些冗余量是可以重新插入到数据中的，因而不会产生失真。该方法一般用于文本数据的压缩，它可以保证完全地恢复原始数据；其缺点是压缩比小(其压缩比一般为2：1至5：1)。有损压缩是对熵进行压缩，因而存在一定程度的失真；它主要用于对声音、图像、动态视频等数据进行压缩，压缩比较高(其压缩比一般高达20：1以上。最新被称为“E—igen—ID”的压缩技术可将基因数据压缩1．5亿倍)。对于多媒体图像采用的有损压缩的标准有静态图像压缩标准(JPEG标准，即‘JointPhotographicExpertGroup’标准)和动态图像压缩标准(MPEG标准，即‘MovingPictureExpertGroup’标准)。JPEG利用了人眼的心理和生理特征及其局限性来对彩色的、单色的和多灰度连续色调的、静态图像的、数字图像的压缩，因此它非常适合不太复杂的以及一般来源于真实景物的图像。它定义了两种基本的压缩算法：一种是基于有失真的压缩算法，另一种是基于空间线性预测技术(DPCM)无失真的压缩算法。为了满足各种需要，它制定了四种工作模式：无失真压缩、基于DCT的顺序工作方式、累进工作方式和分层工作方式。MPEG用于活动影像的压缩。MPEG标准具体包三部分内容：(1)MPEG视频、(2)MPEG音频、(3)MP系统(视频和音频的同步)。MPEG视频是标准的核心分，它采用了帧内和帧间相结合的压缩方法，以离散余变换(DCT)和运动补偿两项技术为基础，在图像质量基不变的情况下，MPEG可把图像压缩至1／100或更MPEG音频压缩算法则是根据人耳屏蔽滤波功能。利用音响心理学的基本原理，即“某些频率的音响在重放其频率的音频时听不到”这样一个特性，将那些人耳完全不到或基本上听到的多余音频信号压缩掉，最后使音频号的压缩比达到8：1或更高，音质逼真，与CD唱片可媲美。按照MPEG标准，MPEG数据流包含系统层和压层数据。系统层含有定时信号，图像和声音的同步、多分配等信息。压缩层包含经压缩后的实际的图像和声数据，该数据流将视频、音频信号复合及同步后，其数据输率为1．5MB／s。其中压缩图像数据传输率为1．2M压缩声音传输率为0．2MB／s。MPEG标准的发展经历了MPEG—I,MPEG一2、MPEG一4、MPEG-7、MPEG一21等不同层次。在MPEG的不同标准中，每—个标准都是建立在前面的标准之上的，并与前面的标准向后的兼容。目前在图像压缩中，应用得较多的是MPEG一4标准，MPEG-是在MPEG-2基础上作了很大的扩充，主要目标是多媒体应用。在MPEG一2标准中，我们的观念是单幅图像，而且包含了一幅图像的全部元素。在MPEG一4标准下，我们的观念变为多图像元素，其中的每—个多图像元素都是独立编码处理的。该标准包含了为接收器所用的指令，告诉接收器如何构成最终的图像。上图既表示了MPEG一4解码器的概念，又比较清楚地描绘了每个部件的用途。这里不是使用单一的视频或音频解码器，而是使用若干个解码器，其中的每一个解码器只接收某个特定的图像(或声音)元素，并完成解码操作。每个解码缓冲器只接收属于它自己的灵敏据流，并转送给解码器。复合存储器完成图像元素的存储，并将它们送到显示器的恰当位置。音频的情况也是这样，但显然不同点是要求同时提供所有的元素。数据上的时间标记保证这些元素在时间上能正确同步。MPEG一4标准对自然元素(实物图像)和合成元素进行区分和规定，计算机生成的动画是合成元素的一个例子。比如，一幅完整的图像可以包含一幅实际的背景图，并在前面有一幅动画或者有另外一幅自然图像。这样的每一幅图像都可以作最佳压缩，并互相独立地传送到接收器，接收器知道如何把这些元素组合在一起。在MPEG一2标准中，图像被看作一个整体来压缩；而在MPEG一4标准下，对图像中的每一个元素进行优化压缩。静止的背景不必压缩到以后的I帧之中去，否则会使带宽的使用变得很紧张。而如果这个背景图像静止10秒钟，就只要传送一次(假设我们不必担心有人在该时间内切人此频道)，需要不断传送的仅是前台的比较小的图像元素。对有些节目类型，这样做会节省大量的带宽。MPEG一4标准对音频的处理也是相同的。例如，有一位独唱演员，伴随有电子合成器，在MPEG一2标准下，我们必须先把独唱和合成器作混合，然后再对合成的音频信号进行压缩与传送。在MPEG一4标准下，我们可以对独唱作单独压缩，然后再传送乐器数字接口的声轨信号，就可以使接收器重建伴音。当然，接收器必须能支持MIDI放音。与传送合成的信号相比，分别传送独唱信号和MIDI数据要节省大量的带宽。其它的节目类型同样可以作类似的规定。MPEG一7标准又叫多媒体内容描述接口标准。图像可以用色彩、纹理、形状、运动等参数来描述，MPEG一7标准是依靠众多的参数对图像与声音实现分类，并对它们的数据库实现查询。二、多媒体数据压缩技术的实现方法目前多媒体压缩技术的实现方法已有近百种，其中基于信源理论编码的压缩方法、离散余弦变换(DCT)和小波分解技术压缩算法的研究更具有代表性。小波技术突破了传统压缩方法的局限性，引入了局部和全局相关去冗余的新思想，具有较大的潜力，因此近几年来吸引了众多的研究者。在小波压缩技术中，一幅图像可以被分解为若干个叫做“小片”的区域；在每个小片中，图像经滤波后被分解成若干个低频与高频分量。低频分量可以用不同的分辨率进行量化，即图像的低频部分需要许多的二进制位，以改善图像重构时的信噪比。低频元素采用精细量化，高频分量可以量化得比较粗糙，因为你不太容易看到变化区域的噪声与误差。此外，碎片技术已经作为一种压缩方法被提出，这种技术依靠实际图形的重复特性。用碎片技术压缩图像时需要占用大量的计算机资源，但可以获得很好的结果。借助于从DNA序列研究中发展出来的模式识别技术，能减少通过WAN链路的流量，最多时的压缩比率能达到90％，从而为网络传送图像和声音提供更大的压缩比，减轻风络负荷，更好地实现网络信息传播。三、压缩原理由于图像数据之间存在着一定的冗余，所以使得数据的压缩成为可能。信息论的创始人Shannon提出把数据看作是信息和冗余度（redundancy）的组合。所谓冗余度，是由于一副图像的各像素之间存在着很大的相关性，可利用一些编码的方法删去它们，从而达到减少冗余压缩数据的目的。为了去掉数据中的冗余，常常要考虑信号源的统计特性，或建立信号源的统计模型。图像的冗余包括以下几种：(1) 空间冗余：像素点之间的相关性。(2) 时间冗余：活动图像的两个连续帧之间的冗余。(3) 信息熵冗余：单位信息量大于其熵。(4) 结构冗余：图像的区域上存在非常强的纹理结构。(5) 知识冗余：有固定的结构，如人的头像。(6) 视觉冗余：某些图像的失真是人眼不易觉察的。对数字图像进行压缩通常利用两个基本原理：(1) 数字图像的相关性。在图像的同一行相邻像素之间、活动图像的相邻帧的对应像素之间往往存在很强的相关性，去除或减少这些相关性，也就去除或减少图像信息中的冗余度，即实现了对数字图像的压缩。(2) 人的视觉心理特征。人的视觉对于边缘急剧变化不敏感(视觉掩盖效应)，对颜色分辨力弱，利用这些特征可以在相应部分适当降低编码精度，而使人从视觉上并不感觉到图像质量的下降，从而达到对数字图像压缩的目的。编码压缩方法有许多种，从不同的角度出发有不同的分类方法，比如从信息论角度出发可分 为两大类：(1)冗余度压缩方法，也称无损压缩，信息保持编码或熵编码。具体讲就是解码图像和压缩 编码前的图像严格相同，没有失真，从数学上讲是一种可逆运算。(2)信息量压缩方法，也称有损压缩，失真度编码或熵压缩编码。也就是讲解码图像和原始图像是有差别的，允许有一定的失真。应用在多媒体中的图像压缩编码方法，从压缩编码算法原理上可以分类为：(1)无损压缩编码种类 •哈夫曼编码 •算术编码 •行程编码 •Lempel zev编码(2)有损压缩编码种类 •预测编码：DPCM，运动补偿 •频率域方法：正文变换编码(如DCT)，子带编码 •空间域方法：统计分块编码 •模型方法：分形编码，模型基编码 •基于重要性：滤波，子采样，比特分配，矢量量化(3)混合编码 •JBIG，H261，JPEG，MPEG等技术标准衡量一个压缩编码方法优劣的重要指标(1)压缩比要高，有几倍、几十倍，也有几百乃至几千倍；(2)压缩与解压缩要快，算法要简单，硬件实现容易；(3)解压缩的图像质量要好。四、JPEG图像压缩算法1．.JPEG压缩过程JPEG压缩分四个步骤实现：1.颜色模式转换及采样；变换；3.量化；4.编码。2．1．颜色模式转换及采样RGB色彩系统是我们最常用的表示颜色的方式。JPEG采用的是YCbCr色彩系统。想要用JPEG基本压缩法处理全彩色图像，得先把RGB颜色模式图像数据，转换为YCbCr颜色模式的数据。Y代表亮度，Cb和Cr则代表色度、饱和度。通过下列计算公式可完成数据转换。Y=＋128人类的眼晴对低频的数据比对高频的数据具有更高的敏感度，事实上，人类的眼睛对亮度的改变也比对色彩的改变要敏感得多，也就是说Y成份的数据是比较重要的。既然Cb成份和Cr成份的数据比较相对不重要，就可以只取部分数据来处理。以增加压缩的比例。JPEG通常有两种采样方式：YUV411和YUV422，它们所代表的意义是Y、Cb和Cr三个成份的资料取样比例。2．变换DCT变换的全称是离散余弦变换(Discrete Cosine Transform)，是指将一组光强数据转换成频率数据，以便得知强度变化的情形。若对高频的数据做些修饰，再转回原来形式的数据时，显然与原始数据有些差异，但是人类的眼睛却是不容易辨认出来。压缩时，将原始图像数据分成8*8数据单元矩阵，例如亮度值的第一个矩阵内容如下：JPEG将整个亮度矩阵与色度Cb矩阵，饱和度Cr矩阵，视为一个基本单元称作MCU。每个MCU所包含的矩阵数量不得超过10个。例如，行和列采样的比例皆为4:2:2，则每个MCU将包含四个亮度矩阵，一个色度矩阵及一个饱和度矩阵。当图像数据分成一个8*8矩阵后，还必须将每个数值减去128，然后一一代入DCT变换公式中，即可达到DCT变换的目的。图像数据值必须减去128，是因为DCT转换公式所接受的数字范围是在-128到+127之间。DCT变换公式：x,y代表图像数据矩阵内某个数值的坐标位置f(x,y)代表图像数据矩阵内的数个数值u,v代表DCT变换后矩阵内某个数值的坐标位置F(u,v)代表DCT变换后矩阵内的某个数值u=0 且 v=0 c(u)c(v)=1/>0 或 v>0 c(u)c(v)=1经过DCT变换后的矩阵数据自然数为频率系数，这些系数以F（0，0）的值最大，称为DC，其余的63个频率系数则多半是一些接近于0的正负浮点数，一概称之为AC。3．3、量化图像数据转换为频率系数后，还得接受一项量化程序，才能进入编码阶段。量化阶段需要两个8*8矩阵数据，一个是专门处理亮度的频率系数，另一个则是针对色度的频率系数，将频率系数除以量化矩阵的值，取得与商数最近的整数，即完成量化。当频率系数经过量化后，将频率系数由浮点数转变为整数，这才便于执行最后的编码。不过，经过量化阶段后，所有数据只保留整数近似值，也就再度损失了一些数据内容，JPEG提供的量化表如下：2．4、编码Huffman编码无专利权问题，成为JPEG最常用的编码方式，Huffman编码通常是以完整的MCU来进行的。编码时，每个矩阵数据的DC值与63个AC值，将分别使用不同的Huffman编码表，而亮度与色度也需要不同的Huffman编码表，所以一共需要四个编码表，才能顺利地完成JPEG编码工作。DC编码DC是彩采用差值脉冲编码调制的差值编码法，也就是在同一个图像分量中取得每个DC值与前一个DC值的差值来编码。DC采用差值脉冲编码的主要原因是由于在连续色调的图像中，其差值多半比原值小，对差值进行编码所需的位数，会比对原值进行编码所需的位数少许多。例如差值为5，它的二进制表示值为101，如果差值为-5，则先改为正整数5，再将其二进制转换成1的补码即可。所谓1的补码，就是将每个Bit若值为0，便改成1；Bit为1，则变成0。差值5应保留的位数为3，下表即列出差值所应保留的Bit数与差值内容的对照。在差值前端另外加入一些差值的霍夫曼码值，例如亮度差值为5（101）的位数为3，则霍夫曼码值应该是100，两者连接在一起即为100101。下列两份表格分别是亮度和色度DC差值的编码表。根据这两份表格内容，即可为DC差值加上霍夫曼码值，完成DC的编码工作。AC编码AC编码方式与DC略有不同，在AC编码之前，首先得将63个AC值按Zig-zag排序，即按照下图箭头所指示的顺序串联起来。63个AC值排列好的，将AC系数转换成中间符号，中间符号表示为RRRR/SSSS，RRRR是指第非零的AC之前，其值为0的AC个数，SSSS是指AC值所需的位数，AC系数的范围与SSSS的对应关系与DC差值Bits数与差值内容对照表相似。如果连续为0的AC个数大于15，则用15/0来表示连续的16个0，15/0称为ZRL（Zero Rum Length），而（0/0）称为EOB（Enel of Block）用来表示其后所剩余的AC系数皆等于0，以中间符号值作为索引值，从相应的AC编码表中找出适当的霍夫曼码值，再与AC值相连即可。例如某一组亮度的中间符为5/3，AC值为4，首先以5/3为索引值，从亮度AC的Huffman编码表中找到1111111110011110霍夫曼码值，于是加上原来100（4）即是用来取[5，4]的Huffman编码1111111110011110100，[5，4]表示AC值为4的前面有5个零。由于亮度AC，色度AC霍夫曼编码表比较长，在此省略去，有兴趣者可参阅相关书籍。实现上述四个步骤，即完成一幅图像的JPEG压缩。 Content as follows: no distortion source coding is a kind of when source symbols, can convert code without distortion from code returned to the original source of the source coding symbols. This paper firstly introduces the without distortion encoding technology development and application; Then discussed emphatically shannon coding, feanor coding, hoffmann coding and the arithmetic coding of four kinds of coding method, the principle and encoding steps are compared with the corresponding sample the average yards long and information transmission speed; Finally, using the Matlab software realize the coding hoffmann the simulation process, also gives part of the source program, and illustrates the application of output, analysed and corresponding conclusions. 数字图像压缩技术的研究及进展摘要：数字图像压缩技术对于数字图像信息在网络上实现快速传输和实时处理具有重要的意义。本文介绍了当前几种最为重要的图像压缩算法：JPEG、JPEG2000、分形图像压缩和小波变换图像压缩，总结了它们的优缺点及发展前景。然后简介了任意形状可视对象编码算法的研究现状，并指出此算法是一种产生高压缩比的图像压缩算法。关键词：JPEG；JPEG2000；分形图像压缩；小波变换；任意形状可视对象编码一 引 言 随着多媒体技术和通讯技术的不断发展，多媒体娱乐、信息高速公路等不断对信息数据的存储和传输提出了更高的要求，也给现有的有限带宽以严峻的考验，特别是具有庞大数据量的数字图像通信，更难以传输和存储，极大地制约了图像通信的发展，因此图像压缩技术受到了越来越多的关注。图像压缩的目的就是把原来较大的图像用尽量少的字节表示和传输，并且要求复原图像有较好的质量。利用图像压缩，可以减轻图像存储和传输的负担，使图像在网络上实现快速传输和实时处理。 图像压缩编码技术可以追溯到1948年提出的电视信号数字化，到今天已经有50多年的历史了[1]。在此期间出现了很多种图像压缩编码方法，特别是到了80年代后期以后，由于小波变换理论，分形理论，人工神经网络理论，视觉仿真理论的建立，图像压缩技术得到了前所未有的发展，其中分形图像压缩和小波图像压缩是当前研究的热点。本文对当前最为广泛使用的图像压缩算法进行综述，讨论了它们的优缺点以及发展前景。二 JPEG压缩 负责开发静止图像压缩标准的“联合图片专家组”（Joint Photographic Expert Group,简称JPEG），于1989年1月形成了基于自适应DCT的JPEG技术规范的第一个草案，其后多次修改，至1991年形成ISO10918国际标准草案，并在一年后成为国际标准，简称JPEG标准。1．JPEG压缩原理及特点 JPEG算法中首先对图像进行分块处理，一般分成互不重叠的 大小的块，再对每一块进行二维离散余弦变换（DCT）。变换后的系数基本不相关，且系数矩阵的能量集中在低频区，根据量化表进行量化，量化的结果保留了低频部分的系数，去掉了高频部分的系数。量化后的系数按zigzag扫描重新组织，然后进行哈夫曼编码。JPEG的特点优点：（1）形成了国际标准；（2）具有中端和高端比特率上的良好图像质量。缺点：（1）由于对图像进行分块，在高压缩比时产生严重的方块效应；（2）系数进行量化，是有损压缩；（3）压缩比不高，小于50。 JPEG压缩图像出现方块效应的原因是：一般情况下图像信号是高度非平稳的，很难用Gauss过程来刻画，并且图像中的一些突变结构例如边缘信息远比图像平稳性重要，用余弦基作图像信号的非线性逼近其结果不是最优的。2． JPEG压缩的研究状况及其前景 针对JPEG在高压缩比情况下，产生方块效应，解压图像较差，近年来提出了不少改进方法，最有效的是下面的两种方法：（1）DCT零树编码 DCT零树编码把 DCT块中的系数组成log2N个子带，然后用零树编码方案进行编码。在相同压缩比的情况下，其PSNR的值比 EZW高。但在高压缩比的情况下，方块效应仍是DCT零树编码的致命弱点。（2）层式DCT零树编码 此算法对图像作 的DCT变换，将低频 块集中起来，做 反DCT变换；对新得到的图像做相同变换，如此下去，直到满足要求为止。然后对层式DCT变换及零树排列过的系数进行零树编码。 JPEG压缩的一个最大问题就是在高压缩比时产生严重的方块效应，因此在今后的研究中，应重点解决 DCT变换产生的方块效应，同时考虑与人眼视觉特性相结合进行压缩。三 JEPG2000压缩 JPEG2000是由ISO/IEC JTCISC29标准化小组负责制定的全新静止图像压缩标准。一个最大改进是它采用小波变换代替了余弦变换。2000年3月的东京会议，确定了彩色静态图像的新一代编码方式—JPEG2000图像压缩标准的编码算法。1．JPEG2000压缩原理及特点 JPEG2000编解码系统的编码器和解码器的框图如图1所示。编码过程主要分为以下几个过程：预处理、核心处理和位流组织。预处理部分包括对图像分片、直流电平（DC）位移和分量变换。核心处理部分由离散小波变换、量化和熵编码组成。位流组织部分则包括区域划分、码块、层和包的组织。 JPEG2000格式的图像压缩比，可在现在的JPEG基础上再提高10%~30%，而且压缩后的图像显得更加细腻平滑。对于目前的JPEG标准，在同一个压缩码流中不能同时提供有损和无损压缩，而在JPEG2000系统中，通过选择参数，能够对图像进行有损和无损压缩。现在网络上的JPEG图像下载时是按“块”传输的，而JPEG2000格式的图像支持渐进传输，这使用户不必接收整个图像的压缩码流。由于JPEG2000采用小波技术，可随机获取某些感兴趣的图像区域（ROI）的压缩码流，对压缩的图像数据进行传输、滤波等操作。2．JPEG2000压缩的前景 JPEG2000标准适用于各种图像的压缩编码。其应用领域将包括Internet、传真、打印、遥感、移动通信、医疗、数字图书馆和电子商务等。JPEG2000图像压缩标准将成为21世纪的主流静态图像压缩标准。四 小波变换图像压缩1．小波变换图像压缩原理小波变换用于图像编码的基本思想就是把图像根据Mallat塔式快速小波变换算法进行多分辨率分解。其具体过程为：首先对图像进行多级小波分解，然后对每层的小波系数进行量化，再对量化后的系数进行编码。小波图像压缩是当前图像压缩的热点之一，已经形成了基于小波变换的国际压缩标准，如MPEG-4标准，及如上所述的JPEG2000标准 。2．小波变换图像压缩的发展现状及前景 目前3个最高等级的小波图像编码分别是嵌入式小波零树图像编码（EZW），分层树中分配样本图像编码（SPIHT）和可扩展图像压缩编码（EBCOT）。（1）EZW编码器 1993年，Shapiro引入了小波“零树”的概念，通过定义POS、NEG、IZ和ZTR四种符号进行空间小波树递归编码，有效地剔除了对高频系数的编码，极大地提高了小波系数的编码效率。此算法采用渐进式量化和嵌入式编码模式，算法复杂度低。EZW算法打破了信息处理领域长期笃信的准则：高效的压缩编码器必须通过高复杂度的算法才能获得，因此EZW编码器在数据压缩史上具有里程碑意义。（2）SPIHT编码器 由Said和Pearlman提出的分层小波树集合分割算法（SPIHT）则利用空间树分层分割方法，有效地减小了比特面上编码符号集的规模。同EZW相比，SPIHT算法构造了两种不同类型的空间零树，更好地利用了小波系数的幅值衰减规律。同EZW编码器一样，SPIHT编码器的算法复杂度低，产生的也是嵌入式比特流，但编码器的性能较EZW有很大的提高。（3）EBCOT编码器优化截断点的嵌入块编码方法（EBCOT）首先将小波分解的每个子带分成一个个相对独立的码块，然后使用优化的分层截断算法对这些码块进行编码，产生压缩码流，结果图像的压缩码流不仅具有SNR可扩展而且具有分辨率可扩展，还可以支持图像的随机存储。比较而言，EBCOT算法的复杂度较EZW和SPIHT有所提高，其压缩性能比SPIHT略有提高。小波图像压缩被认为是当前最有发展前途的图像压缩算法之一。小波图像压缩的研究集中在对小波系数的编码问题上。在以后的工作中，应充分考虑人眼视觉特性，进一步提高压缩比，改善图像质量。并且考虑将小波变换与其他压缩方法相结合。例如与分形图像压缩相结合是当前的一个研究热点。五 分形图像压缩 1988年，Barnsley通过实验证明分形图像压缩可以得到比经典图像编码技术高几个数量级的压缩比。1990年，Barnsley的学生提出局部迭代函数系统理论后，使分形用于图像压缩在计算机上自动实现成为可能。1． 分形图像压缩的原理 分形压缩主要利用自相似的特点，通过迭代函数系统（Iterated Function System, IFS）实现。其理论基础是迭代函数系统定理和拼贴定理。 分形图像压缩把原始图像分割成若干个子图像，然后每一个子图像对应一个迭代函数，子图像以迭代函数存储，迭代函数越简单，压缩比也就越大。同样解码时只要调出每一个子图像对应的迭代函数反复迭代，就可以恢复出原来的子图像，从而得到原始图像。2．几种主要分形图像编码技术 随着分形图像压缩技术的发展，越来越多的算法被提出，基于分形的不同特征，可以分成以下几种主要的分形图像编码方法。（1）尺码编码方法 尺码编码方法是基于分形几何中利用小尺度度量不规则曲线长度的方法，类似于传统的亚取样和内插方法，其主要不同之处在于尺度编码方法中引入了分形的思想，尺度 随着图像各个组成部分复杂性的不同而改变。（2）迭代函数系统方法 迭代函数系统方法是目前研究最多、应用最广泛的一种分形压缩技术，它是一种人机交互的拼贴技术，它基于自然界图像中普遍存在的整体和局部自相关的特点，寻找这种自相关映射关系的表达式，即仿射变换，并通过存储比原图像数据量小的仿射系数，来达到压缩的目的。如果寻得的仿射变换简单而有效，那么迭代函数系统就可以达到极高的压缩比。（3）A-E-Jacquin的分形方案 A-E-Jacquin的分形方案是一种全自动的基于块的分形图像压缩方案，它也是一个寻找映射关系的过程，但寻找的对象域是将图像分割成块之后的局部与局部的关系。在此方案中还有一部分冗余度可以去除，而且其解码图像中存在着明显的方块效应。3．分形图像压缩的前景 虽然分形图像压缩在图像压缩领域还不占主导地位，但是分形图像压缩既考虑局部与局部，又考虑局部与整体的相关性，适合于自相似或自仿射的图像压缩，而自然界中存在大量的自相似或自仿射的几何形状，因此它的适用范围很广。六 其它压缩算法 除了以上几种常用的图像压缩方法以外，还有：NNT（数论变换）压缩、基于神经网络的压缩方法、Hibert扫描图像压缩方法、自适应多相子带压缩方法等，在此不作赘述。下面简单介绍近年来任意形状纹理编码的几种算法[10]~ [13]。（1）形状自适应DCT（SA-DCT）算法 SA-DCT把一个任意形状可视对象分成 的图像块，对每块进行DCT变换，它实现了一个类似于形状自适应Gilge DCT[10][11]变换的有效变换，但它比Gilge DCT变换的复杂度要低。可是，SA-DCT也有缺点，它把像素推到与矩形边框的一个侧边相平齐，因此一些空域相关性可能丢失，这样再进行列DCT变换，就有较大的失真了[11][14][15]。（2）Egger方法 Egger等人[16][17]提出了一个应用于任意形状对象的小波变换方案。在此方案中，首先将可视对象的行像素推到与边界框的右边界相平齐的位置，然后对每行的有用像素进行小波变换，接下来再进行另一方向的小波变换。此方案，充分利用了小波变换的局域特性。然而这一方案也有它的问题，例如可能引起重要的高频部分同边界部分合并，不能保证分布系数彼此之间有正确的相同相位，以及可能引起第二个方向小波分解的不连续等。（3）形状自适应离散小波变换（SA-DWT） Li等人提出了一种新颖的任意形状对象编码，SA-DWT编码[18]~[22]。这项技术包括SA-DWT和零树熵编码的扩展（ZTE），以及嵌入式小波编码（EZW）。SA-DWT的特点是：经过SA-DWT之后的系数个数，同原任意形状可视对象的像素个数相同；小波变换的空域相关性、区域属性以及子带之间的自相似性，在SA-DWT中都能很好表现出来；对于矩形区域，SA-DWT与传统的小波变换一样。SA-DWT编码技术的实现已经被新的多媒体编码标准MPEG-4的对于任意形状静态纹理的编码所采用。 在今后的工作中，可以充分地利用人类视觉系统对图像边缘部分较敏感的特性，尝试将图像中感兴趣的对象分割出来，对其边缘部分、内部纹理部分和对象之外的背景部分按不同的压缩比进行压缩，这样可以使压缩图像达到更大的压缩比，更加便于传输。七 总结 图像压缩技术研究了几十年，取得了很大的成绩，但还有许多不足，值得我们进一步研究。小波图像压缩和分形图像压缩是当前研究的热点，但二者也有各自的缺点，在今后工作中，应与人眼视觉特性相结合。总之，图像压缩是一个非常有发展前途的研究领域，这一领域的突破对于我们的信息生活和通信事业的发展具有深远的影响。参考文献：[1] 田青. 图像压缩技术[J]. 警察技术, 2002, (1)：30-31.[2] 张海燕, 王东木等. 图像压缩技术[J]. 系统仿真学报, 2002, 14(7)：831-835.[3] 张宗平, 刘贵忠. 基于小波的视频图像压缩研究进展[J]. 电子学报, 2002, 30(6)：883-889.[4] 周宁, 汤晓军, 徐维朴. JPEG2000图像压缩标准及其关键算法[J]. 现代电子技术, 2002, (12)：1-5.[5] 吴永辉, 俞建新. JPEG2000图像压缩算法概述及网络应用前景[J]. 计算机工程, 2003, 29(3)：7-10.[6] J M Shaprio. Embedded image coding using zerotree of wavelet coefficients[J]. IEEE Trans. on Signal Processing, 1993, 41(12): 3445-3462.[7] A Said, W A Pearlman. A new fast and efficient image codec based on set partitioning in hierarchical trees[J]. IEEE Trans. on Circuits and Systems for Video Tech. 1996, 6(3): 243-250.[8] D Taubman. High performance scalable image compression with EBCOT[J]. IEEE Transactions on Image Processing, 2000, 9(7): 1158–1170.[9] 徐林静, 孟利民, 朱建军. 小波与分行在图像压缩中的比较及应用. 中国有线电视, 2003, 03/04：26-29.[10] M Gilge, T Engelhardt, R Mehlan. Coding of arbitrarily shaped image segments based on a generalized orthogonal transform[J]. Signal Processing: Image Commun., 1989, 1(10): 153–180.[11] T Sikora, B Makai. Shape-adaptive DCT for generic coding of video[J]. IEEE Trans. Circuits Syst. Video Technol., 1995, 5(1): 59–62.[12] T Sikora, S Bauer, B Makai. Efficiency of shape-adaptive 2-D transforms for coding of arbitrarily shaped image segments[J]. IEEE Trans. Circuits Syst. Video Technol., 1995, 5(3): 254–258.[13]邓家先 康耀红 编著 《信息论与编码》 多媒体的应用很广泛，请链接 基于FPGA的HDB3码编译码器设计电子机械论文目 录摘 要 IAbstract II第1章 绪论 HDB3码简述 FPGA和其设计方法 FPGA/CPLD简介 FPGA设计方法 VHDL设计技术 VHDL简介 利用VHDL语言设计硬件电路的方法 本文所做的工作内容安排 6第2章 HDB3码编译原理 HDB3码的编码原理 HDB3码的译码原理 8第3章 HDB3数字信源 数字信源单元 HDB3编码单元 用CD22103A芯片实现 用VHDL建模实现 16第4章 HDB3译码器实现方法分析 25第5章 HDB3译码器的FPGA实现 HDB3译码器的FPGA设计流程 HDB3译码器设计的总体框图 双单极性变换模块 译码功能模块的设计 译码模块的VHDL设计 译码模块的原理图设计 误码检测模块设计 位同步提取模块设计 鉴相器模块的设计 滤波器的设计 数控振荡器的设计 简易显示模块 38第6章 Max-plusⅡ与HDB3译码器的仿真 MAX-PLUSⅡ简述 功能简介 设计流程 设计步骤 系统仿真与调试 编码部分仿真结果 译码模块仿真结果 误码检测模块仿真结果 位同步提取模块仿真结果 42结束语 44参考文献 45致 谢 46附录A 译码器总图 47附录B 锁相环总图 48附录C 滤波器电路图 49基于FPGA的HDB3码编译码器的设计摘 要：HDB3 码是基带传输系统中常用的码型。本设计是基于 EMP7128设计的一个完整的 HDB3 码的编译码器。给出了硬件设计电路图、软件设计流程和HDB3编译码器的仿真波形。本设计中编码器部分用了专用集成芯片CD22103和VHDL建模两种方法来实现。译码器中除了包含有译码的电路外，还包含有单双极性转换，误码检测和位同步提取等功能。双单极性变换的作用是使得双极性的 HDB3 码能够进入 CPLD，同时易于做数字逻辑分析。其中的位同步提取功能是利用超前滞后型数字锁相环从编码序列中提取出位同步信号，并把该信号作为译码部分的时钟。位同步模块中最为关键的一步是在 CPLD 实现若干个上升沿触发数字单稳。总体来说，该编译码器具有外围电路简单，工作稳定，抗干扰能力强等特点。此实现方法具有硬件设计简单、运行速度快、成本低等优点。同时由于CPLD可重复编程的特点，可以对它进行在线修改，便于设备的调试和运行。此编译码器已经过实际测试，运行稳定可靠，可用于实际电路中。关键词：HDB3码；FPGA；编译码器；位同步HDB3 Encoder Decoder Based on FPGAAbstract: HDB3 code is the commonly used code in the transmission system . It is an intact HDB3 encoder and decoder designed on the basis of EMP7128 to originally design. This paper presents the circuit diagram of hardware design, the flow of software design and the simulated waveform of HDB3 encoder and decoder. The encoder is designed on the basis CD22103A and VHDL language. Also include single polarity to bipolar conversion besides including the circuit of the decode in this design, code measured by mistake , and location synchronized signals picked out. The function that vary bipolar to one polarity makes ambipolar HDB3 code can introduce to CPLD and make digital logic analysis easy. Location among them draw function to utilize digital phase locking ring produce the synchronous signal in the location to draw from code array in step, and regard this signal as the clock of the part of the decoder. To location synchronous module the most crucial one is to realize several rise along touch off digital form steady in CPLD. On the whole, this encoder and decoder has simple outside circuit, works steadily and better anti-interference ability. The method has the advantages of simple hardware design, high speed and low cost. In addition, since CPLD can be reprogrammed, it can be repaired online, thus making it convenient to debug and run the equipment. Testing shows that this encoder and decoder has stable performance and therefore can be applied to : HDB3 code; FPGA; Encoder and Decoder; Location sychronized第1章 绪论 HDB3码简述现代通信借助于电和光来传输信息，数字终端产生的数字信息是以“1”和“0”两种代码（状态）位代表的随机序列，他可以用不同形式的电信号表示，从而构造不同形式的数字信号。在一般的数字通信系统中首先将消息变为数字基带信号，称为信源编码，经过调制后进行传输，在接收端先进行解调恢复为基带信号，再进行解码转换为消息。在实际的基带传输系统中，并不是所有电波均能在信道中传输，因此有基带信号的选择问题，因此对码型的设计和选择需要符合一定的原则。当数字信号进行长距离传输时，高频分量的衰减随距离的增大而增大，电缆中线对之间的电磁辐射也随着频率的增高而加剧，从而限制信号的传输距离和传输质量，同时信道中往往还存在隔直流电容和耦合变压器，他们不能传输直流分量及对低频分量有较大的衰减，因此对于一般信道高频和低频部分均是受限的。对于这样的信道，应使线路传输码型的频谱不含直流分量，并且只有很少的低频分量和高频分量。其次，传输码型中应含有定时时钟信息，以利于收端定时时钟的提取，在基带传输系统中，定时信息是在接收端再生原始信息所必需的。一般传输系统中，为了节省频带是不传输定时信息的，必须在接受端从相应的基带信号中加以提取。再次，实际传输系统常希望在不中断通信的前提下，能监视误码，如果传输码型有一定的规律性，那么就可以根据这一规律性来检测传输质量，以便做到自动监测，因此，传输码型应具有一定的误码检测能力。当然，对传输码型的选择还需要编码和解码设备尽量简单等要求，但以上的几点是最主要的考虑因素。HDB3码又叫三阶高密度双极性码，是基带电信设备之间进行基带传输的主要码型之一。该码具有以下特点：(1) 无直流分量，且低频分量也很少：其功率谱密度也与AMI码类似，其方波中丰富的高频分量同样被消除了。(2) 由于引入取代节，因而解决了AMI码在连‘0’过长时提取位定信号的困难。(3) 具有内在检错能力。由此可见，HDB3码是一种优良码，目前广泛应用于基带传输的接口码。 兄弟你这个论文有点难度了。不是随便拉拉就行了。得找专业书籍慢慢找和高人指导了。我查到点不指导有没有用。Turbo卷积码(TCC)是3G无线系统中所采用的前向错误校正（FEC）机制的整体部分。然而，Turbo译码器所带来的计算负担非常重，并不太适合采用传统DSP或RISC处理器实现。由于现场可编程逻辑阵列（FPGA）内在的并行结构，FPGA为解决3G基站收发器中所需要的符号速率FEC和其它计算密集的任务提供了一个高性能信号处理平台基础。Turbo 编码级联码方案（Concatenated coding schemes）是为了通过结合两个或更多相对简单的分量或构造模块码来获得较高的编码增益。Turbo码认为是对级联码结构的一种改进，其中采用迭代算法对相关的码序列进行译码。Turbo码是通过将两个或更多分量码应用到同一数据序列的不同交织版本上构成的。对于任何传统单分量编码，译码器的最后一级生成的都是硬判决译码数据位。为了使象Turbo码这样的级联码方案工作得更好，译码算法不应被限制为只能在译码器间传递硬判决。为最好地利用每个译码器获得的信息，译码算法必须可以实现软判决交换，而不是采用硬判决。对于采用两个分量码的系统，译码的概念是指将来自一个译码器的软判决输入到另一个译码器的输入，并将此过程重复几次以获得更好的判决，如图1所示 。3GPP Turbo 编码器图2为3GPP编码器。输入数据流输入到RSC1，它为每个输入比特生成一个对等比特（Parity Bit）。输入数据还经过交织后由RSC2处理生成第二个对等比特流。3GPP标准定义，输入块的长度在40至5114 位之间。编码器生成一个速率为1/3的包括原始输入位和两个对等位的系统码。通过打孔方法可以获得1/2编码速度的编码。递归系统编码器的实现比较直接，然而交织器则不那么简单，要比标准的卷积或块交织器复杂。一旦将输入数据块长度K 提供给编码器以后，编码器将计算交织矩阵行数R和列数 C，并创建相应的交织数据结构。R 和 C 是数据块长度K的函数。在输入符号被加载到交织矩阵以后，那么将根据一定的顺序进行行间交换和列间交换。交换模式是根据块长度K选择的（即依赖于K）。行和列交换完成后，通过逐列读出交织矩阵数据就可以得到最终的交织序列。在数据读出时需要进行删减操作，以保证在输出中只有正确的输入符号，请注意，交织阵列包含的数据位通常比K个原始输入符号要多 ，因为R C>K。然后，新的序列经过RSC2编码生成第二个对等位流。实现交织器的一种方法是在存储器中存储完整的交换序列。即，一旦K 给定，即调用一个初始化例程（运行在处理器上的软件例程或利用FPGA中的功能单元）生成相应的交换序列，然后将这一信息存储在存储器中。然而，这一方法需要大量的存储器。利用Virtex -E FPGA 技术提供的 4096位每块的片上存储器，将需要[5114 13/4096]=17个存储器块。在我们的方法中，采用一个预处理引擎生成一个序列值（存储），这一序列值被存储起来，交织器地址发生器将使用这些序列值。这一硬件单元采用几个小型数据结构（素数表）来计算所需要的序列。这一准备过程需要的时钟周期数与信息块的长度成比例。例如，对于K=40的块需要280时钟周期，而对于最大块长度K=5114，则需要 5290个时钟周期。该过程只需要在块长度变化时进行。地址发生器利用这些更为紧凑的数据结构来实时生成交织地址。 3GPP Turbo 译码器译码器包括两个MAP（最大后验概率）译码器和几个交织器。Turbo算法的优良的性能源于可以在两个MAP译码器间共享可靠性信息（extrinsic data，外数据，或称先验数据）。在我们的设计中，MAP译码器采用的是Bahl， Cocke， Jelinek 和 Rajiv (BCJR) 算法。BCJR算法计算每个符号的最大后验对数似然率，并且是一种真正的软判决算法。考虑到数据是以块的形式传输的，因此可以在时间维中前向或反向搜索一个符号序列。对于任一序列，其出现概率都是单独符号出现概率的乘积。由于问题是线性的，因此序列概述可以利用概率的对数和来代替。为了与一般文献中的习惯一致，我们将译码迭代的前向和反向状态概率分别利用 和 来表示。通常，BCJR算法要求在接收到整个信息后才开始解码。对于实时应用，这一限制可能太严格了。例如，3GPP Turbo译码器将需要大量存储器存储一个5114符号信息块的完全状态结构（state trellis）。对于单片FPGA设计来说，这需要的存储资源太多了。与维特比（Vitebi）算法类似，我们可以先从全零向量 O和数据{yk}（k 从 n 到 n-L） 开始反向迭代。L次反向迭代可获得非常好的 n-L近似值。只要L选择合适，最终的状态标志（state metric）就是正确的。可以利用这一性质在信息结束前就开始进行有效的位译码。L 被称为收敛长度。其典型值大约是译码器约束长度的数倍（通常为5至10倍），并随着信噪比的降低而增加。通常，Turbo译码算法将计算所有的 （对整块信息），将这些数值存储起来，然后在反向迭代中与反向状态概率一起用来计算新的外信息（extrinsic information，或称先验信息）。我们的设计中采用了窗口化方法。译码过程以一个前向迭代开始，计算包含L 个接收符号的块i的 值。同时，对未来（i+1）块进行一个反向迭代（标号 ）。对块i+1的反向迭代结束时，就获得了开始对块i 进行反向迭代所需要的正确的 初始向量。 与此同时对数似然函数（Lall）也在进行。 每一 和 处理过程都需要8个max* 操作 - 每个针对状态结构（tellis）中的8个结点之一。最终的对数似然计算需要14个并行max* 运算符。为了提供可接受的译码速率，在设计中采用了38个max* 功能单元。从 C描述到FPGA设计FPGA Turbo 编码译码器设计是利用基于C的设计和验证方法进行的，如图3所示。 算法开发阶段采用具有定点C类型的Art Library 来对定点计算的位真（bit-true）效应进行准确建模。在这一阶段考察了几种可能算法的定点性能。一旦选定正确的量化算法，就可利用A|rtDesignerPro创建一个专用DSP架构。A|rtDesignerPro的一个最强大的功能之一是可以插入和利用专用的数据通道核心（称为专用单元，ASU）。利用这些ASU加速器核心可以使我们处理Turbo译码器算法内在的计算复杂性。A|rtDesignerPro可自动完成寄存器分配、调度和控制器生成。在Turbo编码译码器设计中， A|rtDesignerr的自动循环合并可获得最佳的；任务调度，MAP译码步骤的内部循环都只有一个周期长。A|rtDesignerPro生成的最终结果是可综合的寄存器级（RT-level） VHDL或Verilog 描述。基于C的工具流支持FPGA专用功能。例如，可利用BlockRAM自动构造RAM，而寄存器文件也可利用分布式存储器而不是触发器来实现 。 最后，逻辑综合和Xilinx实施工具套件将RTL HDL 转换为 FPGA 配置位流。FPGA Turbo 编码译码器实现A|rtDesigner创建的Turbo编码器和译码器核心硬件结构包含许多专用ASU加速器。其中最重要的一个加速器完成max* 操作。max* 运算符根据下式计算两个幂值a 和 b：max* (a,b)=ln(expc(a)+expc(b))。如 图4所示， max* 运算是通过选择（a,b）最大值，并应用一个存储在查找表（LUT）中的校正因子近似进行的。这一近似算法非常适合利用Xilinx FPGA 实现，其中LUT是其最终基本构造单元。结果Turbo译码算法硬件字长的选择极大地影响总体性能。利用C-to-FPGA设计流程，这一定点分析是完全在C环境中完成的。结果示于图 5。上图显示出了我们的浮点Turbo译码器算法和对应的定点算法之间的性能差别。仿真是在5114块长度、5次译码迭代和AWGN信道模型情况下进行的。结果清晰明显出性能的损失是非常小的。我们的Turbo译码器的定点性能做为译码器迭代次数的函数 ，对于 dB SNR，位错率为10-6。译码器功能的实现非常具有挑战性，我们同时针对Virtex-E和 Virtex-II 器件进行了适配。Virtex-II 器件实施是采用运行在 speedfile数据库上的Xilinx 实施工具集完成的。利用XC2V1000BG575-5 FPGA实现的最终设计，达到了66 MHz 的时钟性能，消耗了3,060个逻辑片 和 16个块RAM。对于从40至 5114符号长度的块，采用5次译码迭代循环的情况下，译码器达到了2 至 百万符号每秒（Msym/s）的吞吐量。编码器占用了903个逻辑片、3个块RAM并支持83 MHz时钟频率。对于从40至5114位的块长度，速率可达到9 至20 Msym/s。能用上就好了，用不上别怪我。对不起哈~祝福你~赫夫曼编码毕业论文
哈夫曼编码毕业论文
哈夫曼编码的相关毕业论文
turbo码编解码分析毕业论文