Skip to content

komm.FanoCode

Binary Fano code. For a given pmf $p$ over $\mathcal{X}$, it is a fixed-to-variable length code in which the source words are first sorted in descending order of probability and then are recursively partitioned into two groups of approximately equal total probability, assigning bit $\mathtt{0}$ to one group and bit $\mathtt{1}$ to the other, until each source word is assigned a unique codeword. For more details, see Wikipedia: Shannon–Fano coding.

Notes

Fano codes are always prefix-free (hence uniquely decodable).

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$.

  • source_block_size (int) –

    The source block size $k$. The default value is $k = 1$.

Examples:

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

>>> code = komm.FanoCode(pmf)
>>> code.enc_mapping
{(0,): (0,),
 (1,): (1, 0),
 (2,): (1, 1)}
>>> code.rate(pmf)
np.float64(1.2)

>>> code = komm.FanoCode(pmf, 2)
>>> code.enc_mapping
{(0, 0): (0,),
 (0, 1): (1, 0, 0),
 (0, 2): (1, 0, 1),
 (1, 0): (1, 1, 0),
 (1, 1): (1, 1, 1, 1, 0, 0),
 (1, 2): (1, 1, 1, 1, 0, 1),
 (2, 0): (1, 1, 1, 0),
 (2, 1): (1, 1, 1, 1, 1, 0),
 (2, 2): (1, 1, 1, 1, 1, 1)}
>>> code.rate(pmf)
np.float64(0.96)