Skip to content

komm.FanoCode

Binary Fano code. 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 probability mass function of the source.

  • source_block_size (int) –

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

Examples:

>>> pmf = [0.7, 0.15, 0.15]

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

>>> 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(1.1975)