Skip to content

komm.ShannonCode

Binary Shannon code. It is a fixed-to-variable length code in which the length of the codeword $\Enc(u)$ for a source symbol $u \in \mathcal{S}^k$ is given by $$ \ell_u = \left\lceil \log_2 \frac{1}{p_u} \right\rceil, $$ where $p_u$ is the probability of the source symbol $u$. This function implements the lexicographic order assignment as described in Wikipedia: Shannon–Fano coding.

Notes

Shannon 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.ShannonCode(pmf, 1)
>>> code.enc_mapping
{(0,): (0,),
 (1,): (1, 0, 0),
 (2,): (1, 0, 1)}
>>> code.rate(pmf)
np.float64(1.6)

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