huffman编码译码的matlab仿真
1.问题描述:
哈夫曼树介绍
哈夫曼树又称最优二叉树,是一种带权路径长度最短的二叉树。所谓树的带权路径长度,就是树中所有的叶结点的权值乘上其到根结点的路径长度(若根结点为0层,叶结点到根结点的路径长度为叶结点的层数)。树的带权路径长度记为WPL=(W1*L1+W2*L2+W3*L3+...+ Wn*Ln),N个权值Wi(i=1,2,...n)构成一棵有N个叶结点的二叉树,相应的叶结点的路径长度为Li(i=1,2,...n)。可以证明哈夫曼树的WPL是最小的。 利用哈夫曼编码进行通信可以大大提高信道利用率,缩短信息传输时间,降低传输成本。
路径和路径长度
在一棵树中,从一个结点往下可以达到的孩子或子孙结点之间的通路,称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1,则从根结点到第L层结点的路径长度为L-1。
结点的权及带权路径长度
若将树中结点赋给一个有着某种含义的数值,则这个数值称为该结点的权。结点的带权路径长度为:从根结点到该结点之间的路径长度与该结点的权的乘积。
树的带权路径长度
树的带权路径长度规定为所有叶子结点的带权路径长度之和,记为WPL。
哈夫曼树的建立
由哈夫曼最早给出的建立最优二叉树的带有一般规律的算法,俗称哈夫曼算法。描述如下:
- 初始化:根据给定的n个权值(W1,W2,…,Wn),构造n棵二叉树的森林集合F={T1,T2,…,Tn},其中每棵二叉树Ti只有一个权值为Wi的根节点,左右子树均为空。
- 找最小树并构造新树:在森林集合F中选取两棵根的权值最小的树做为左右子树构造一棵新的二叉树,新的二叉树的根结点为新增加的结点,其权值为左右子树的权值之和。
- 删除与插入:在森林集合F中删除已选取的两棵根的权值最小的树,同时将新构造的二叉树加入到森林集合F中。
- 重复2)和3)步骤,直至森林集合F中只含一棵树为止,这颗树便是哈夫曼树,即最优二叉树。由于2)和3)步骤每重复一次,删除掉两棵树,增加一棵树,所以2)和3)步骤重复n-1次即可获得哈夫曼树
设终端节点数为n0,度为二的节点数为n2,度为一的节点数为n1,总结结点个数为n,分支数目为B
1.n=n0+n1+n2
2.n=B+1
3.B=n1+2*n2;
4.n0=n2+1;
哈夫曼编码
在数据通信中,需要将传送的文字转换成二进制的字符串,用0,1码的不同排列来表示字符。例如,需传送的报文为“AFTER DATA EAR ARE ART AREA”,这里用到的字符集为“A,E,R,T,F,D”,各字母出现的次数为{8,4,5,3,1,1}。现要求为这些字母设计编码。要区别6个字母,最简单的二进制编码方式是等长编码,固定采用3位二进制,可分别用000、001、010、011、100、101对“A,E,R,T,F,D”进行编码发送,当对方接收报文时再按照三位一分进行译码。显然编码的长度取决报文中不同字符的个数。若报文中可能出现26个不同字符,则固定编码长度为5。然而,传送报文时总是希望总长度尽可能短。在实际应用中,各个字符的出现频度或使用次数是不相同的,如A、B、C的使用频率远远高于X、Y、Z,自然会想到设计编码时,让使用频率高的用短码,使用频率低的用长码,以优化整个报文编码。
哈夫曼译码
在通信中,若将字符用哈夫曼编码形式发送出去,对方接收到编码后,将编码还原成字符的过程,称为哈夫曼译码。
2.部分程序:
% data
data = ['Practical purposes often demand a separation of intermediate and leaf nodes'...
' during that process. If you do that store the leaf nodes in an array of size'...
' alphabetsize-1 and fill it from left to right. Since intermediate nodes are'...
' constructed in the sequence they are used you just need two pointers;'...
' one pointing to the next unfilled place and one pointing to the next unused'...
' intermediate node. You don''t have to do the heap sink down that often this way;'...
' you just compare the top of the heap containing the symbols with the unused'...
' intermediate node. If you like you could also sort the symbols by probability'...
' first and then use them in the sequence of increasing probability.'...
' The result is the same; if you sort first you might use quicksort,'...
' if you keep the heap idea you (implicitly) use heapsort to sort the symbols.'];
data = uint8(data);
% compress data
fprintf('Compresing data ... ')
[zipped,info] = norm2huff(data);
fprintf('Done!\n')
% decompress data
fprintf('Decompressing data ... ')
unzipped = huff2norm(zipped,info);
fprintf('Done!\n')
% test it
isOK = isequal(data(:),unzipped(:))
whos data zipped unzipped
3.仿真结论:
D-39
相关文章
- Matlab:成功解决Index must be a positive integer or logical
- Matlab:成功解决In an assignment A(I)=B,the number of elements in B and I must be the same
- Matlab:序列分析法MATLAB代码
- 多微网优化调度(风机、光伏、蓄电池、燃料电池、柴油机、电网交互)(Matlab代码实现)
- 选择编码节点的最佳数量和位置研究(Matlab代码实现)
- 基于能量的凸集高光谱端元提取算法(Matlab代码实现)
- 基于多目标优化算法的电力系统分析(Matlab代码实现)
- 基于MATLAB中雷达和视觉合成数据的目标级传感器融合(Matlab代码实现)
- 【MATLAB】图像压缩编码(DCT、RLE)
- 【MATLAB】matlab实现最大熵法图像分割程序
- 【MATLAB】求解微分方程
- m基于EAN13字符编码规则的一维条形码条码宽度计算和数字译码matlab仿真
- 五通信算法:五种编码增益比较matlab模拟
- 【语音编码】基于matlab ADPCM编解码(Matlab代码实现)
- 【语音处理】基于自适应差分脉冲编码调制(ADPCM)的实现研究(Matlab代码实现)
- 【语音编码】基于matlab ADPCM编解码【G.723.1】(Matlab代码实现)
- m基于matlab的里德-穆勒码Reed Muller(RM)编码译码误码率仿真分析
- matlab实现实时编辑器创建交互编译功能(.mlx):实时脚本库
- Matlab使用笔记(三):matlab设置代码自动补全功能
- Matlab使用笔记(九):matlab实现交通流仿真/车感知/城市交通交叉路口