komm.FanoCode

Binary Fano code. For a given pmf $p$ over $\mathcal{X}$, it is a symbol code in which the source symbols 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 symbol is assigned a unique codeword. For more details, see Wikipedia: Shannon–Fano coding.

Notes

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

Parameters:

• pmf (ArrayLike) –

  The pmf $p$ to be considered. Must be a 1D-array of size $|\mathcal{X}|$ of non-negative values that sum to $1$.

• assignment (Literal['tree', 'canonical']) –

  The strategy used to assign the codewords, once the partition tree is built. Must be either 'tree' (read the codewords off the paths of the tree, bit $\mathtt{0}$ being assigned to the group of more probable source symbols) or 'canonical' (the canonical code with the resulting lengths). The default value is 'tree'. It affects neither the codeword lengths nor the average length.

Examples:

>>> pmf = [0.1, 0.2, 0.3, 0.4]

>>> code = komm.FanoCode(pmf)
>>> code.codewords
[(1, 1, 1), (1, 1, 0), (1, 0), (0,)]
>>> code.average_length(pmf)
1.9

>>> code = komm.FanoCode(pmf, assignment="canonical")
>>> code.codewords
[(1, 1, 0), (1, 1, 1), (1, 0), (0,)]
>>> code.average_length(pmf)
1.9