Skip to content

komm.TunstallCode

Binary Tunstall code. It is an optimal (minimal expected rate) variable-to-fixed length code for a given pmf $p$ over $\mathcal{X}$. For more details, see Say06, Sec. 3.7.

Notes

Tunstall codes are always prefix-free (hence uniquely encodable) and fully covering.

Parameters:

  • pmf (ArrayLike) –

    The pmf $p$ to be considered. It must be a one-dimensional array of floats of size $|\mathcal{X}|$. The elements must be non-negative and sum to $1$.

  • target_block_size (int | None) –

    The target block size $n$. Must satisfy $2^n \geq |\mathcal{X}|$. The default value is $n = \lceil \log_2 |\mathcal{X}| \rceil$.

Examples:

>>> pmf = [0.8, 0.1, 0.1]

>>> code = komm.TunstallCode(pmf)
>>> code.dec_mapping
{(0, 0): (0,),
 (0, 1): (1,),
 (1, 0): (2,)}
>>> code.rate(pmf)
np.float64(2.0)

>>> code = komm.TunstallCode(pmf, 3)
>>> code.dec_mapping
{(0, 0, 0): (0, 0, 0),
 (0, 0, 1): (0, 0, 1),
 (0, 1, 0): (0, 0, 2),
 (0, 1, 1): (0, 1),
 (1, 0, 0): (0, 2),
 (1, 0, 1): (1,),
 (1, 1, 0): (2,)}
>>> code.rate(pmf)
np.float64(1.2295081967213108)