huffman编译码

1.算法描述

        利用哈夫曼编码进行信息通信可以较大提高信道利用率,缩短信息传输时间,降低传输成本。但是,这要求在发送端通过一个编码系统对待传数据预先编码;在接收端将传来的数据进行译码(复原)。对于双工信道（即可以双向传输信息的信道),每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼码的编译码系统。

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

       设某信源产生有五种符号u1、u2、u3、u4和u5，对应概率P1=0.4，P2=0.1，P3=P4=0.2，P5=0.1。首先，将符号按照概率由大到小排队，如图1所示。编码时，从最小概率的两个符号开始，可选其中一个支路为0，另一支路为1。这里，我们选上支路为0，下支路为1。再将已编码的两支路的概率合并，并重新排队。多次重复使用上述方法直至合并概率归一时为止。从图1中（a）和（b）可以看出，两者虽平均码长相等，但同一符号可以有不同的码长，即编码方法并不唯一，其原因是两支路概率合并后重新排队时，可能出现几个支路概率相等，造成排队方法不唯一。一般，若将新合并后的支路排到等概率的最上支路，将有利于缩短码长方差，且编出的码更接近于等长码。这里图1中（a）的编码比（b）好。

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

       实际应用中，除采用定时清洗以消除误差扩散和采用缓冲存储以解决速率匹配以外，主要问题是解决小符号集合的统计匹配，例如黑（1）、白（0）传真信源的统计匹配，采用0和1不同长度游程组成扩大的符号集合信源。游程，指相同码元的长度（如二进码中连续的一串0或一串1的长度或个数）。按照CCITT标准，需要统计2×1728种游程（长度），这样，实现时的存储量太大。事实上长游程的概率很小，故CCITT还规定：若l表示游程长度，则l=64q+r。其中q称主码，r为基码。编码时，不小于64的游程长度由主码和基码组成。而当l为64的整数倍时，只用主码的代码，已不存在基码的代码。

       长游程的主码和基码均用赫夫曼规则进行编码，这称为修正赫夫曼码，其结果有表可查。该方法已广泛应用于文件传真机中。

2.仿真效果预览

matlab2022a仿真结果如下：

3.MATLAB部分代码预览

function [zipped,info] = norm2huff(vector)
 
 
 
% ensure to handle uint8 input vector
if ~isa(vector,'uint8'),
	error('input argument must be a uint8 vector')
end
 
% vector as a row
vector = vector(:)';
 
% frequency
f = frequency(vector);
 
% simbols presents in the vector are
simbols = find(f~=0); % first value is 1 not 0!!!
f = f(simbols);
 
% sort using the frequency
[f,sortindex] = sort(f);
simbols = simbols(sortindex);
 
% generate the codewords as the 52 bits of a double
len = length(simbols);
simbols_index = num2cell(1:len);
codeword_tmp = cell(len,1);
while length(f)>1,
	index1 = simbols_index{1};
	index2 = simbols_index{2};
	codeword_tmp(index1) = addnode(codeword_tmp(index1),uint8(0));
	codeword_tmp(index2) = addnode(codeword_tmp(index2),uint8(1));
	f = [sum(f(1:2)) f(3:end)];
	simbols_index = [{[index1 index2]} simbols_index(3:end)];
	% resort data in order to have the two nodes with lower frequency as first two
	[f,sortindex] = sort(f);
	simbols_index = simbols_index(sortindex);
end
 
% arrange cell array to have correspondance simbol <-> codeword
codeword = cell(256,1);
codeword(simbols) = codeword_tmp;
 
% calculate full string length
len = 0;
for index=1:length(vector),
	len = len+length(codeword{double(vector(index))+1});
end
	
% create the full 01 sequence
string = repmat(uint8(0),1,len);
pointer = 1;
for index=1:length(vector),
	code = codeword{double(vector(index))+1};
	len = length(code);
	string(pointer+(0:len-1)) = code;
	pointer = pointer+len;
end
 
% calculate if it is necessary to add padding zeros
len = length(string);
pad = 8-mod(len,8);
if pad>0,
	string = [string uint8(zeros(1,pad))];
end
 
% now save only usefull codewords
codeword = codeword(simbols);
codelen = zeros(size(codeword));
weights = 2.^(0:51);
maxcodelen = 0;
for index = 1:length(codeword),
	len = length(codeword{index});
	if len>maxcodelen,
		maxcodelen = len;
	end
	if len>0,
		code = sum(weights(codeword{index}==1));
		code = bitset(code,len+1);
		codeword{index} = code;
		codelen(index) = len;
	end
end
codeword = [codeword{:}];
 
% calculate zipped vector
cols = length(string)/8;
string = reshape(string,8,cols);
weights = 2.^(0:7);
zipped = uint8(weights*double(string));
 
% store data into a sparse matrix
huffcodes = sparse(1,1); % init sparse matrix
for index = 1:numel(codeword),
	huffcodes(codeword(index),1) = simbols(index);
end
 
% create info structure
info.pad = pad;
info.huffcodes = huffcodes;
info.ratio = cols./length(vector);
info.length = length(vector);
info.maxcodelen = maxcodelen;
 
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function codeword_new = addnode(codeword_old,item)
codeword_new = cell(size(codeword_old));
for index = 1:length(codeword_old),
	codeword_new{index} = [item codeword_old{index}];
end
A_039