## Geometric Huffman Codinglast update 2013-02-06 — Georg Böcherer ()
Dyadic PMFs can be generated by parsing a stream of independent equiprobable data bits by a full prefix-free code. Formally, is dyadic if and . Such a PMF is generated by a prefix-free code with codeword lengths . To match dyadic PMFs to communication channels, the Kullback-Leibler distance between the dyadic PMF and the capacity achieving PMF of the considered channel has to be minimized. See Matching Dyadic Distributions to Channels for details. On this web site I provide implementations of algorithms that find the optimal dyadic PMF. ## References- Writing on the Facade of RWTH ICT Cubes: Cost Constrained Geometric Huffman Coding
G. Böcherer, Fabian Altenbach, Martina Malsbender, and Rudolf Mathar, **best paper award**at ISWCS 2011, Aachen. — pdf
- Matching Dyadic Distributions to Channels
G. Böcherer and R. Mathar, presented at DCC 2011, Snowbird. — pdf
## Downloadsmatching.tar — all implementations from this web site. They are tested in Matlab R2010b and Octave 3.4.0. ## Geometric Huffman Coding (GHC)Given is a vector with non-negative entries. If additionally the entries sum up to one, than is a PMF. The objective is to minimize subject to is a dyadic PMF. Geometric Huffman Coding (GHC) finds the dyadic PMF that minimizes . GHC constructs a Huffman tree using the following updating rule. Denote by and the two smallest entries of . Then For comparison, conventional Huffman coding finds the dyadic PMF that minimizes (minimization is here over the second argument) by using the updating rule
## Normalized Geometric Huffman Coding (nGHC)Given is a target vector with non-negative entries and a weight vector with strictly positive entries. The objective is to minimize the Kullback-Leibler distance normalized by the average weight , i.e., to minimize the fraction subject to is a dyadic PMF. Normalized Geometric Huffman Coding (nGHC) iteratively finds the solution. nGHC supersedes the LEC Algorithm stated in Matching Dyadic Distributions to Channels.
## Cost Constrained Geometric Huffman Coding (ccGHC)Given is a target vector with non-negative entries and a weight vector with strictly positive entries. The objective is to minimize the Kullback-Leibler distance subject to an average cost constraint over all dyadic PMFs p. Cost Constrained Geometric Huffman Coding (ccGHC) iteratively finds the solution.
## Miscellaneous m-files
## Examples## Example 1
octave:11> addpath /home/georg/matching octave:12> q = [0.328 0.32 0.22 0.11 0.022]'; octave:13> pghc = ghc(q) pghc = 0.50000 0.25000 0.12500 0.12500 0.00000 octave:14> phc = hc(q) phc = 0.25000 0.25000 0.25000 0.12500 0.12500 octave:15> kldiv(pghc,q) ans = 0.13619 octave:16> kldiv(phc,q) ans = 0.19548 octave:17> phc_ = [hc(q(1:4));0] phc_ = 0.25000 0.25000 0.25000 0.25000 0.00000 octave:18> kldiv(phc_,q) ans = 0.15523 octave:19> ## Example 2
example2.m
w = (11:20)'; C = fsolve(@(s) sum(exp(-w*s))-1,1); t = exp(-w*C); d_nghc = nghc(t,w); d_hc = hc(t); R_nghc = -d_nghc'*log(d_nghc)/(w'*d_nghc); R_hc = -d_hc'*log(d_hc)/(w'*d_hc); disp(['codeword lengths of nghc: ' num2str(-log2(d_nghc'))]); disp(['codeword lengths of hc : ' num2str(-log2(d_hc'))]); disp(['rate achieved by nghc:' num2str(R_nghc)]); disp(['rate achieved by hc: ' num2str(R_hc)]); octave:7> addpath /home/georg/matching octave:7> example2 codeword lengths of nghc: 3 3 3 3 3 3 4 4 4 4 codeword lengths of hc : 2 3 3 3 3 4 4 4 5 5 rate achieved by nghc:0.15273 rate achieved by hc: 0.15265 octave:8> |