komm.VariableToFixedCode

Variable-to-fixed length code. A variable-to-fixed length code with target alphabet $\mathcal{T}$, source alphabet $\mathcal{S}$, and target block size $n$ is defined by a (possibly partial) injective decoding mapping $\mathrm{Dec} : \mathcal{T}^n \to \mathcal{S}^+$, where the domain is the set of all $n$-tuples with entries in $\mathcal{T}$, and the co-domain is the set of all finite-length, non-empty tuples with entries in $\mathcal{S}$. Here, we assume that $\mathcal{T} = [0:T)$ and $\mathcal{S} = [0:S)$, for integers $T \geq 2$ and $S \geq 2$. The elements in the image of $\mathrm{Dec}$ are called sourcewords.

Attributes:

• target_cardinality (int) –

  The target cardinality $T$.

• source_cardinality (int) –

  The source cardinality $S$.

• target_block_size (int) –

  The target block size $n$.

• dec_mapping (dict[Word, Word]) –

  The decoding mapping $\mathrm{Dec}$ of the code. Must be a dictionary of length at most $S^n$ whose keys are $n$-tuples of integers in $[0:T)$ and whose values are distinct non-empty tuples of integers in $[0:S)$.

from_dec_mapping classmethod

Constructs a variable-to-fixed code from the decoding map $\Dec$.

Parameters:

• dec_mapping (dict[Word, Word]) –

  The decoding map $\Dec$. See the corresponding attribute for more details.

Examples:

>>> code = komm.VariableToFixedCode.from_dec_mapping({(0,0): (0,0,0), (0,1): (0,0,1), (1,0): (0,1), (1,1): (1,)})
>>> (code.target_cardinality, code.source_cardinality, code.target_block_size)
(2, 2, 2)
>>> code.dec_mapping
{(0, 0): (0, 0, 0),
 (0, 1): (0, 0, 1),
 (1, 0): (0, 1),
 (1, 1): (1,)}

>>> code = komm.VariableToFixedCode.from_dec_mapping({(0,0,0): (1,), (0,0,1): (2,), (0,1,0): (0,1), (0,1,1): (0,2), (1,0,0): (0,0,0), (1,0,1): (0,0,1), (1,1,0): (0,0,2)})
>>> code.target_cardinality, code.source_cardinality, code.target_block_size
(2, 3, 3)
>>> code.dec_mapping
{(0, 0, 0): (1,),
 (0, 0, 1): (2,),
 (0, 1, 0): (0, 1),
 (0, 1, 1): (0, 2),
 (1, 0, 0): (0, 0, 0),
 (1, 0, 1): (0, 0, 1),
 (1, 1, 0): (0, 0, 2)}

from_sourcewords classmethod

Constructs a variable-to-fixed code from the target cardinality $T$ and a list of sourcewords.

Parameters:

• target_cardinality (int) –

  The target cardinality $T$. Must be an integer greater than or equal to $2$.

• sourcewords (list[Word]) –

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

Examples:

>>> code = komm.VariableToFixedCode.from_sourcewords(2, [(0,0,0), (0,0,1), (0,1), (1,)])
>>> (code.target_cardinality, code.source_cardinality, code.target_block_size)
(2, 2, 2)
>>> code.dec_mapping
{(0, 0): (0, 0, 0),
 (0, 1): (0, 0, 1),
 (1, 0): (0, 1),
 (1, 1): (1,)}

sourcewords: list[Word] property

The sourcewords of the code. It is a list of length at most $T^n$ containing tuples of integers in $[0:S)$. The tuple in position $i$ of sourcewords is equal to $\mathrm{Dec}(v)$, where $v$ is the $i$-th element in the lexicographic ordering of $[0:T)^n$.

Examples:

>>> code = komm.VariableToFixedCode.from_dec_mapping({(0,0): (0,0,0), (0,1): (0,0,1), (1,0): (0,1), (1,1): (1,)})
>>> code.sourcewords
[(0, 0, 0), (0, 0, 1), (0, 1), (1,)]

inv_dec_mapping: dict[Word, Word] property

The inverse decoding mapping $\mathrm{Dec}^{-1}$ of the code. It is a dictionary of length at most $T^n$ whose keys are all the sourcewords of the code, and whose values are the corresponding target words.

Examples:

>>> code = komm.VariableToFixedCode.from_sourcewords(2, [(0,0,0), (0,0,1), (0,1), (1,)])
>>> code.inv_dec_mapping
{(0, 0, 0): (0, 0),
 (0, 0, 1): (0, 1),
 (0, 1): (1, 0),
 (1,): (1, 1)}

is_unique_encodable

Returns whether the code is unique encodable or not. [Not implemented yet].

is_prefix_free

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

Examples:

>>> code = komm.VariableToFixedCode.from_sourcewords(2, [(0,0,0), (0,0,1), (0,1), (1,)])
>>> code.is_prefix_free()
True

>>> code = komm.VariableToFixedCode.from_sourcewords(2, [(0,0,0), (0,1,0), (0,1), (1,)])
>>> 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{n}{\bar{k}}, $$ where $n$ is the target block size, and $\bar{k}$ is the expected sourceword length, assuming iid source symbols drawn from $p_X$. It is measured in $T$-ary digits per source symbol.

Parameters:

• pmf (Array1D[float]) –

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

Returns:

• rate (float) –

  The expected rate $R$ of the code.

Examples:

>>> code = komm.VariableToFixedCode.from_sourcewords(2, [(0,0,0), (0,0,1), (0,1), (1,)])
>>> code.rate([2/3, 1/3])
np.float64(0.9473684210526315)

encode

Encodes a sequence of source symbols using the code. Only implemented for prefix-free codes.

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.VariableToFixedCode.from_sourcewords(2, [(0,0,0), (0,0,1), (0,1), (1,)])
>>> code.encode([0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0])
array([0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0])

>>> code = komm.VariableToFixedCode.from_sourcewords(2, [(0,0,0), (0,0,1), (0,1), (0,)])
>>> code.encode([0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0])
Traceback (most recent call last):
...
NotImplementedError: encoding is not implemented for non-prefix-free codes

decode

Decodes a sequence of target symbols using the code.

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:

• 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.VariableToFixedCode.from_sourcewords(2, [(0,0,0), (0,0,1), (0,1), (1,)])
>>> code.decode([0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0])
array([0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0])