Skip to content

komm.FixedToVariableCode

Fixed-to-variable length code. A fixed-to-variable length code with source alphabet $\mathcal{S}$, target alphabet $\mathcal{T}$, and source block size $k$ is defined by an injective encoding mapping $\Enc : \mathcal{S}^k \to \mathcal{T}^+$, where the domain is the set of all $k$-tuples with entries in $\mathcal{S}$, and the co-domain is the set of all finite-length, non-empty tuples with entries in $\mathcal{T}$. Here we assume that $\mathcal{S} = [0:S)$ and $\mathcal{T} = [0:T)$, for integers $S \geq 2$ and $T \geq 2$. The elements in the image of $\Enc$ are called codewords.

Attributes:

  • source_cardinality (int) –

    The source cardinality $S$.

  • target_cardinality (int) –

    The target cardinality $T$.

  • source_block_size (int) –

    The source block size $k$.

  • enc_mapping (dict[Word, Word]) –

    The encoding mapping $\Enc$ of the code. Must be a dictionary of length $S^k$ whose keys are $k$-tuples of integers in $[0:S)$ and whose values are distinct non-empty tuples of integers in $[0:T)$.

from_enc_mapping classmethod

Constructs a fixed-to-variable length code from the encoding mapping $\Enc$.

Parameters:

  • enc_mapping (dict[Word, Word]) –

    The encoding mapping $\Enc$. See the corresponding attribute for more details.

Examples:

>>> code = komm.FixedToVariableCode.from_enc_mapping({(0,): (0,), (1,): (1,0), (2,): (1,1)})
>>> code.source_cardinality, code.target_cardinality, code.source_block_size
(3, 2, 1)
>>> code.enc_mapping
{(0,): (0,),
 (1,): (1, 0),
 (2,): (1, 1)}

>>> code = komm.FixedToVariableCode.from_enc_mapping({(0,0): (0,), (0,1): (1,0,0), (1,0): (1,1), (1,1): (1,0,1)})
>>> code.source_cardinality, code.target_cardinality, code.source_block_size
(2, 2, 2)
>>> code.enc_mapping
{(0, 0): (0,),
 (0, 1): (1, 0, 0),
 (1, 0): (1, 1),
 (1, 1): (1, 0, 1)}

from_codewords classmethod

Constructs a fixed-to-variable length code from the source cardinality $S$ and a list of codewords.

Parameters:

  • source_cardinality (int) –

    The source cardinality $S$. Must be an integer greater than or equal to $2$.

  • codewords (list[Word]) –

    The codewords of the code. See the corresponding property for more details.

Examples:

>>> code = komm.FixedToVariableCode.from_codewords(3, [(0,), (1,0), (1,1)])
>>> code.source_cardinality, code.target_cardinality, code.source_block_size
(3, 2, 1)
>>> code.enc_mapping
{(0,): (0,),
 (1,): (1, 0),
 (2,): (1, 1)}

>>> code = komm.FixedToVariableCode.from_codewords(2, [(0,), (1,0,0), (1,1), (1,0,1)])
>>> (code.source_cardinality, code.target_cardinality, code.source_block_size)
(2, 2, 2)
>>> code.enc_mapping
{(0, 0): (0,),
 (0, 1): (1, 0, 0),
 (1, 0): (1, 1),
 (1, 1): (1, 0, 1)}

codewords: list[Word] property

The codewords of the code. It is a list of length $S^k$ containing tuples of integers in $[0:T)$. The tuple in position $i$ of codewords is equal to $\Enc(u)$, where $u$ is the $i$-th element in the lexicographic ordering of $[0:S)^k$.

Examples:

>>> code = komm.FixedToVariableCode.from_enc_mapping({(0,): (0,), (1,): (1,0), (2,): (1,1)})
>>> code.codewords
[(0,), (1, 0), (1, 1)]

inv_enc_mapping: dict[Word, Word] property

The inverse encoding mapping $\Enc^{-1}$ of the code. It is a dictionary of length $S^k$ whose keys are all the codewords of the code and whose values are the corresponding source words.

Examples:

>>> code = komm.FixedToVariableCode.from_codewords(3, [(0,), (1,0), (1,1)])
>>> code.inv_enc_mapping
{(0,): (0,),
 (1, 0): (1,),
 (1, 1): (2,)}

is_uniquely_decodable

Returns whether the code is uniquely decodable or not. A code is uniquely decodable if $$ s_1 \cdots s_n \neq s'_1 \cdots s'_m \implies \Enc(s_1) \cdots \Enc(s_n) \neq \Enc(s'_1) \cdots \Enc(s'_m). $$

Examples:

>>> code = komm.FixedToVariableCode.from_codewords(3, [(0,), (1,0), (1,1)])
>>> code.is_uniquely_decodable()
True

>>> code = komm.FixedToVariableCode.from_codewords(3, [(0,), (0,1), (1,1)])
>>> code.is_uniquely_decodable()
True

>>> code = komm.FixedToVariableCode.from_codewords(3, [(0,), (0,1), (1,0)])
>>> code.is_uniquely_decodable()
False

is_prefix_free

Returns whether the code is prefix-free or not. A code is prefix-free if no codeword is a prefix of any other codeword.

Examples:

>>> code = komm.FixedToVariableCode.from_codewords(3, [(0,), (1,0), (1,1)])
>>> code.is_prefix_free()
True

>>> code = komm.FixedToVariableCode.from_codewords(3, [(0,), (0,1), (1,1)])
>>> code.is_prefix_free()
False

>>> code = komm.FixedToVariableCode.from_codewords(3, [(0,), (0,1), (1,0)])
>>> code.is_prefix_free()
False

rate

Computes the expected rate $R$ of the code, considering a given pmf. This quantity is given by $$ R = \frac{\bar{n}}{k}, $$ where $\bar{n}$ is the expected codeword length, assuming iid source symbols drawn from $p_X$, and $k$ is the source block size. It is measured in $T$-ary digits per source symbol.

Parameters:

  • pmf (ArrayLike) –

    The (first-order) probability mass function $p_X$ to be considered.

Returns:

  • rate (float) –

    The expected rate $R$ of the code.

Examples:

>>> code = komm.FixedToVariableCode.from_codewords(3, [(0,), (1,0), (1,1)])
>>> code.rate([0.5, 0.25, 0.25])
np.float64(1.5)

encode

Encodes a sequence of source symbols using the code.

Parameters:

  • source_symbols (ArrayLike) –

    The sequence of symbols to be encoded. Must be a 1D-array with elements in $[0:S)$, where $S$ is the source cardinality of the code.

Returns:

  • NDArray[integer] –

    The sequence of encoded symbols. It is a 1D-array with elements in $[0:T)$, where $T$ is the target cardinality of the code.

Examples:

>>> code = komm.FixedToVariableCode.from_codewords(3, [(0,), (1,0), (1,1)])
>>> code.encode([1, 0, 1, 0, 2, 0])
array([1, 0, 0, 1, 0, 0, 1, 1, 0])

decode

Decodes a sequence of target symbols using the code. Only implemented for prefix-free codes.

Parameters:

  • target_symbols (ArrayLike) –

    The sequence of symbols to be decoded. Must be a 1D-array with elements in $[0:T)$, where $T$ is the target cardinality of the code.

Returns:

  • output (NDArray[integer]) –

    The sequence of decoded symbols. It is a 1D-array with elements in $[0:S)$, where $S$ is the source cardinality of the code.

Examples:

>>> code = komm.FixedToVariableCode.from_codewords(3, [(0,), (1,0), (1,1)])
>>> code.decode([1, 0, 0, 1, 0, 0, 1, 1, 0])
array([1, 0, 1, 0, 2, 0])

>>> code = komm.FixedToVariableCode.from_codewords(2, [(0,), (1,0), (1,1), (1,1,0)])
>>> code.decode([1, 0, 0, 1, 0, 0, 1, 1, 0])
Traceback (most recent call last):
...
NotImplementedError: decoding is not implemented for non-prefix-free codes