《实验二Huffman编码》由会员分享，可在线阅读，更多相关《实验二Huffman编码（5页珍藏版）》请在金锄头文库上搜索。
1、1安排周一下午：第一批周一晚上：第二批周四下午：第三批实验二Huffman编码上次课程预测编码码长:算术码字：预测值算术编码12() 0. , 0,1LiPcccc = nullnull1log()Lp = null变换编码1kririisas= =差值预测编码rrress= rrrs es= +解码我们首先介绍变换编码的基本原理然后介绍变换编码中常用的几种变换(1)变换编码的基本原理设信源连续发出的两个信源符号之间存在相关性，如果均为3比特量化，即它们各有八种可能的取值，那么之间的相关特性可用图表示。12,ss12,ss图中的椭圆区域表示s1与s2相关程度较高的区域，此相关区关于s1轴和s2
2、轴对称。显然如果s1与s2的相关性越强，则椭圆形状越扁长，而且变量s1与s2幅度取值相等的可能性也越大，二者方差近似相等，即。如果我们将s1与s2的坐标轴逆时针旋转45，变成平面，则椭圆区域的长轴落在轴上，此时当取值变动较大时，所受影响很小，说明与之间的相关性大大减弱。同时由图可以看出：随机变量与的能量分布也发生了很大的变化，在相关区域内的大部分点上的方差均大于的方差，即. 221212yOy1y1y1y1y1y2y2y2y2y2212yynull另外，由于坐标变换不会使总能量发生变化，所以有：由此可见，通过上述坐标变换，使变换后得到的新变量、呈现两个重要的特点：变量间相关性大大减弱；能量更集
3、中，即，且小到几乎可忽略.这两个特点正是变换编码可以实现数据压缩的重要依据。2212 +2212yy +1y2y2212yy null22y2上述坐标旋转对应的变换方程为：因为因此，坐标旋转变换矩阵是一个正交矩阵，由正交矩阵决定的变换称为正交变换。1122cos sinsin cosy sy s = cos sin cos sin 1 0sin cos sin cos 0 1T =icos sinsin cosT=高性能的变换编码方法不仅能使输出的压缩信源矢量中各分量之间的相关性大大减弱，而且使能量集中到少数几个分量上，在其他分量上数值很小，甚至为“0”。因此在对变换后的分量(系数)进行量化再
4、编码时，因为在量化后等于“0”的系数可以不传送，因此在一定保真度准则下可达到压缩数据率的目的，量化参数的选取主要根据保真度要求或恢复信号的主观评价效果来确定。在变换编码方法中最关键的是正交变换的选择，最佳的正交变换是KL变换，由于KL变换使变换后随机矢量的各分量之间完全独立，因而它常作为衡量正交变换性能的标准，在评价其它变换的性能时，常与KL变换的结果进行比较。KL变换的最大缺点是计算复杂，而且其变换矩阵与信源有关，实用性不强。为此人们又找出了各种实用化程度较高的变换，如离散傅里叶变换（DFT）、离散余弦变换（DCT）、沃尔什变换（WHT）等等，其中性能较接近KL变换的是离散余弦变换（DCT）
5、，在某些情况下，DCT能获得与KL变换相同的性能，因此DCT也被称为准最佳变换。(2)离散余弦变换DCT是根据DFT的不足，按实际需要而构造的一种实数域的变换，由于DCT源于DFT，这里我们先考察DFT。DFT是一种常见的正交变换，在数字信号处理中得到广泛应用.设长度为N的离散序列为，DFT定义为：正变换反变换其中:将正变换写成矩阵形式:其中T为离散傅里叶变换的变换矩阵。101( ) ( ) (u 0,1,2,.,N-1)NuxxFu fxWN=101( ) ( ) 0,1,2,.,N-1Nuxufx FuW xN=2/ej NW=() ()F uTfx=nullnull00 0 001 2
6、1012(1) (1)(1)1NNN NNWW W WWW W WTNWW W W =nullnullnullnull nullnull nullnull12, , , Nff fnull虽然DFT为频谱分析提供了有力的工具，但是通常DFT是复数域的运算，尽管有快速傅里叶变换（FFT），在实际应用中仍有许多不便。如果将一个实函数对称延拓成一个实偶函数，由于实偶函数的傅里叶变换也是实偶函数，只含有余弦项，以此构造一种实数域的变换，即离散余弦变换。3DCT定义为：11 1.22 23(1)2 cos cos . cos22 2:.:(1) 3(1) (21)(1)cos cos . cos22 2
7、CNTNNNNN NN = 12, , , Nff fnull设长度为的离散序列为10(2 1)() () ()cos 0, , 12NxxuFu au fx u NN=+=null正变换10(2 1)() () ()cos 0,1, , 12Nuxufx auFu x NN=+null反变换=1,.,2,1u /20u /1)(NNNua其中:() ()CF uTf x=nullnull将正变换写成矩阵形式:经DCT变换后信号的能量将向左上角集中，因而有利于数据的压缩。例:求二维信号的DCT0000011001100000f = 1.33 0.26 0.89 0.180.26 0.05 0.
8、18 0.04(,)0.89 0.18 0.59 0.120.18 0.04 0.12 0.02cFuv = Fc= GTf G0.5 0.5 0.5 0.50.653 0.271 0.271 0.6530.5 0.5 0.5 0.50.271 0.653 0.653 0.271G=例给定两幅图像信源如图所示，对它们进行DCT，则其DCT系数图所示，图中亮度越大表示对应的DCT系数的值也越大。二维DCT的恢复与误差二维DCT的恢复与误差二维DCT的恢复与误差4二维DCT的恢复与误差二维DCT的恢复与误差(3)沃尔什-哈达玛变换离散沃尔什-哈达玛变换(WHT)，其变换矩阵是由“+1”和“-1”组
9、成的，因此在变换过程中只有加法和减法，计算速度快而且易于用硬件实现。设长度为N的离散序列为，当时，WHT变换对定义为：12, , , Nff fnull2nN=101 () ()0() ()(1)NiN bxbuiiufx Hu=101 () ()01() ()(1)NiN bxbuiiuHu fxN=0, , 1uNnull=0, , 1xNnull=正变换反变换其中指数上的求和是以“2”为模的，是D的二进制表达式中的第i位的取值。例如当n=3时，对有比较可知,WHT正变换和反变换只差一个常数项，所以用于正变换的算法也可用于反变换，这使得WHT的使用非常方便。()ibD26 (110)D =
10、012() 0,()1, ()1bD bD bD= =101 () ()0() ()(1)NiN bxbuiiufx Hu=101 () ()01() ()(1)NiN bxbuiiuHu fxN= WHT变换矩阵是一个对称的正交矩阵，例如当N=8时的WHT变换矩阵为：111111111111111111 1111 1111111 11111111 111181 11 1 11 1111 1111111111 111 1HT = 对WHT变换矩阵而言，其构成规律具有简单的迭代性质，可以方便地产生各阶变换矩阵。最小阶(N=2)的TH为：如果用代表N阶WHT变换矩阵，则上面所述的迭代关系如下：21
11、111HT=NHT2NNNNNHHHHHTTTTT = WHT变换矩阵的生成：5例求二维均匀分布信号的二维沃尔什变换。解：由于信号是4* 4矩阵，沃尔什变换核为因此二维沃尔什变换如下：本例表明，二维沃尔什变换具有能量集中的性质，原始数据越是均匀分布，沃尔什变换后的数据越集中于矩阵的左上角，因此，应用二维沃尔什变换可以压缩(图像)信息。411 1 1111 1111 1 141111HT= 2111111111111 10001 1 1 111111 1 1 1 0 0 0 011 1 1 111111 1 1 1 0 0 0 04111111111111 0000H = 11111111111
12、11111f=例给定如图(a)所示的图像信源，对其进行WHT，则WHT系数图(b)所示，同样在图中亮度越大表示对应的WHT系数的取数值也越大。从本例可以看到，经沃尔什-哈达玛变换后图像信号的能量向左上角集中，因而有利于数据的压缩。但WHT的能量集中能力不如DCT。许多信号变换方法都可用于变换编码。需要注意的是数据的压缩并不是在变换步骤取得的，而是在量化变换系数时取得的，因为在实际编码时，对应于方差很小的分量，往往可以不传送，从而使数据得到压缩。对某一个给定的编码应用，如何选择变换取决于可容许的重建误差和计算要求。变换具有将信号能量集中于某些系数的能力，不同的变换信号能量集中的能力不同。对常用的
13、变换而言，DCT比DFT和WHT有更强的信息集中能力。从理论上说，KL变换是所有变换中信息集中能力最优的变换，但KLT的变换矩阵与输入数据有关，所以不太实用。实际中用的变换其变换矩阵都与输入数据无关，在这些变换中，非正弦类变换（如WHT)实现起来相对简单，但正弦类变换(如DFT和DCT)更接近KLT的信息集中能力。近年来，由于DCT的信息集中能力和计算复杂性综合得比较好，而得到了较多的应用，DCT已被设计在单个集成块上。另外，近年来得到广泛研究和应用的一些编码方法（例如子带编码、小波变换编码、分形编码等）也直接或间接地与变换编码相关，在实际应用中，需要根据信源特性来选择变换方法以达到解除相关性
14、、压缩码率的目的。此外还可以根据一些参数来比较各种变换方法间的性能优劣，如反映编码效率的编码增益、反映编码质量的块效应系数等。当信源的统计特性很难确知时，可用各种变换分别对信源进行变换编码，然后用实验或计算机仿真来计算这些参数，从而选择合适的编码。本章讨论了对信源的编码，若为无失真编码，其本章讨论了对信源的编码，若为无失真编码，其平均码长平均码长达到最短的极限值是信源的信息熵达到最短的极限值是信源的信息熵。同时还给出了一些实用。同时还给出了一些实用的编码方法。的编码方法。通过最佳的信源编码虽然可以消除信源的剩余度、提高信通过最佳的信源编码虽然可以消除信源的剩余度、提高信息传输率，但结果却息传输率，但结果却使码变得十分使码变得十分“脆弱脆弱”，经不起信道中噪，经不起信道中噪声的干扰，容易造成译码错误。声的干扰，容易造成译码错误。如上表中的霍夫曼码。若信源发出的符号为如上表中的霍夫曼码。若信源发出的符号为s2，通过信源编码，变换为通过信源编码，变换为码字码字01。假设它在二元信道中发生传输错误，接收端接收到的符号变成假设它在二元信道中发生传输错误，接收端接收到的符号变成11，收信者就会判断信源发出的符号为收信者就会判断信源发出的符号为s1s1，造成严重的接收错误。造成严重的接收错误。另外，也可能在一串码字序列中，由于传输过程中某个符号错了，而使另外，也可能在一
