Skip to content

komm.ShannonCode

Binary Shannon code. For a given pmf $p$ over $\mathcal{X}$, it is a fixed-to-variable length code in which the length of the codeword $\Enc(\mathbf{x})$ associated with a source word $\mathbf{x} \in \mathcal{X}^k$ is given by $$ \ell(\mathbf{x}) = \left\lceil \log_2 \frac{1}{p(\mathbf{x})} \right\rceil. $$ 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 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.ShannonCode(pmf)
>>> code.enc_mapping
{(0,): (0,),
 (1,): (1, 0, 0, 0),
 (2,): (1, 0, 0, 1)}
>>> code.rate(pmf)
np.float64(1.6)

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