Skip to content

komm.ShannonCode

Binary Shannon code. For a given pmf $p$ over $\mathcal{X}$, it is a symbol code in which the length of the codeword $\Enc(x)$ associated with a source symbol $x \in \mathcal{X}$ is given by $$ \ell(x) = \left\lceil \log_2 \frac{1}{p(x)} \right\rceil. $$ For more details, see Wikipedia: Shannon–Fano coding.

Notes

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

Parameters:

  • pmf (ArrayLike) –

    The pmf $p$ to be considered. Must be a 1D-array of size $|\mathcal{X}|$ of positive values that sum to $1$. Zero probabilities are not allowed, since $\ell(x)$ is undefined for $p(x) = 0$.

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

    The strategy used to assign the codewords, once the lengths are computed. Must be either 'cumulative' (the codeword of $x$ is formed by the first $\ell(x)$ bits of the binary expansion of the total probability of the source symbols that precede $x$ in descending order of probability, as in Shannon's original construction) or 'canonical' (the canonical code with the same lengths). The default value is 'cumulative'. It affects neither the codeword lengths nor the average length.

Examples:

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

>>> code = komm.ShannonCode(pmf)
>>> code.codewords
[(0, 1, 1), (0, 0), (1, 0, 0), (1, 1, 0, 0), (1, 1, 1, 0)]
>>> code.average_length(pmf)
2.8

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