Dyadic probability mass functions (PMFs) can be generated by parsing a stream of independent equiprobable data bits by a full prefix-free code. Formally, $p$ is dyadic if $p_i=2^{-\ell_i}$, $\ell_i \in\mathbb{N}$ and $\sum_i 2^{-\ell_i}=1$. Such a PMF $p$ is generated by a prefix-free code with codeword lengths $\ell_i$. 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.

# Geometric Huffman Coding (GHC)

Given is a vector $x$ with non-negative entries. If additionally the entries sum up to one, than $x$ is a PMF. The objective is to minimize

subject to $p$ is a dyadic PMF. Geometric Huffman Coding (GHC) finds the dyadic PMF $p$ that minimizes $\mathrm{D}(p\Vert x)$. GHC constructs a Huffman tree using the following updating rule. Denote by $x_{m}$ and $x_{m-1}\geq x_m$ the two smallest entries of $x$. Then

$% $.

For comparison, conventional Huffman coding finds the dyadic PMF $p$ that minimizes $\mathrm{D}(x\Vert p)$ (minimization is here over the second argument) by using the updating rule $x' = x_{m-1}+x_m$.

ghc.m in matching.tar is a Matlab implementation of GHC.

# Normalized Geometric Huffman Coding (nGHC)

Given is a target vector $x$ with non-negative entries and a weight vector $w$ with strictly positive entries. The objective is to minimize the Kullback-Leibler distance $\mathrm{D}(p\Vert x)$ normalized by the average weight $w^Tp=\sum_i p_iw_i$, i.e., to minimize the fraction

subject to $p$ 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.

nghc.m in matching.tar is a Matlab implementation of nGHC.

# Cost Constrained Geometric Huffman Coding (ccGHC)

Given is a target vector $x$ with non-negative entries and a weight vector $w$ with strictly positive entries. The objective is to minimize the Kullback-Leibler distance $\mathrm{D}(p\Vert x)$ subject to an average cost constraint $w^Tp\leq E$ over all dyadic PMFs $p$. Cost Constrained Geometric Huffman Coding (ccGHC) iteratively finds the solution.

ccghc.m in matching.tar is a Matlab implementation of ccGHC.

# Example 2

example2.m:

Output: