komm.FixedToVariableCode

General fixed-to-variable length code. A fixed-to-variable length code with source alphabet $\mathcal{X}$, target alphabet $\mathcal{Y}$, and source block size $k$ is defined by an encoding mapping $\Enc: \mathcal{X}^k \to \mathcal{Y}^+$, where the domain is the set of all $k$-tuples with entries in $\mathcal{X}$, and the co-domain is the set of all finite-length, non-empty tuples with entries in $\mathcal{Y}$. The elements in the image of $\Enc$ are called codewords.

Note

Here, for simplicity, we assume that the source alphabet is $\mathcal{X} = [0 : |\mathcal{X}|)$ and the target alphabet is $\mathcal{Y} = [0 : |\mathcal{Y}|)$, where $|\mathcal{X}| \geq 2$ and $|\mathcal{Y}| \geq 2$ are called the source cardinality and target cardinality, respectively.

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$. Must be a dictionary whose keys are all the $k$-tuples of integers in $\mathcal{X}$ and whose values are non-empty tuples of integers in $\mathcal{Y}$.

Notes

The source block size $k$ is inferred from the domain of the encoding mapping, and the source and target cardinalities $|\mathcal{X}|$ and $|\mathcal{Y}|$ are inferred from the maximum values in the domain and co-domain, respectively.

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.codewords
[(0,), (1, 0), (1, 1)]

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

from_codewords() classmethod

Constructs a fixed-to-variable length code from the source cardinality $|\mathcal{X}|$ and a list of codewords.

Parameters:

• source_cardinality (int) –

  The source cardinality $|\mathcal{X}|$. Must be an integer greater than or equal to $2$.

• codewords (list[Word]) –

  The codewords of the code. Must be a list of length $|\mathcal{X}|^k$ containing tuples of integers in $\mathcal{Y}$. The tuple in position $i$ must be equal to $\Enc(\mathbf{x})$, where $\mathbf{x}$ is the $i$-th element in the lexicographic ordering of $\mathcal{X}^k$.

Notes

The source block size $k$ is inferred from the length of the codewords, and the target cardinality $|\mathcal{Y}|$ is inferred from the maximum value in the codewords.

Examples:

>>> code = komm.FixedToVariableCode.from_codewords(
...     source_cardinality=3,
...     codewords=[(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(
...     source_cardinality=2,
...     codewords=[(0,), (1, 1), (1, 1, 0), (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, 1),
 (1, 0): (1, 1, 0),
 (1, 1): (1, 0, 1)}

source_cardinality int cached property

The source cardinality $|\mathcal{X}|$ of the code. It is the number of symbols in the source alphabet.

Examples:

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

target_cardinality int cached property

The target cardinality $|\mathcal{Y}|$ of the code. It is the number of symbols in the target alphabet.

Examples:

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

source_block_size int cached property

The source block size $k$ of the code. It is the number of symbols in each source word.

Examples:

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

size int cached property

The number of codewords in the code. It is equal to $|\mathcal{X}|^k$.

Examples:

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

enc_mapping dict[Word, Word] cached property

The encoding mapping $\Enc$ of the code. It is a dictionary of length $|\mathcal{X}|^k$ whose keys are all the $k$-tuples of integers in $\mathcal{X}$ and whose values are the corresponding codewords.

Examples:

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

codewords list[Word] cached property

The codewords of the code. They correspond to the image of the encoding mapping $\Enc$.

Examples:

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

is_uniquely_decodable() cached

Returns whether the code is uniquely decodable. A code is uniquely decodable if there is a unique way to parse any concatenation of codewords.

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()  # 010 can be parsed as 0|10 or 01|0
False

is_prefix_free() cached

Returns whether the code is prefix-free. 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

kraft_parameter() cached

Computes the Kraft parameter $K$ of the code. This quantity is given by $$ K = \sum_{\mathbf{x} \in \mathcal{X}^k} |\mathcal{Y}|^{-{\ell(\mathbf{x})}}, $$ where $\ell(\mathbf{x})$ is the length of the codeword $\Enc(\mathbf{x})$ associated with the source word $\mathbf{x} \in \mathcal{X}^k$.

Returns:

• kraft_parameter (float) –

  The Kraft parameter $K$ of the code.

Examples:

>>> code = komm.FixedToVariableCode.from_codewords(
...     source_cardinality=5,
...     codewords=[(0, 0, 0), (0, 0, 1), (0, 1, 0), (1, 0, 1), (1, 1)],
... )
>>> code.kraft_parameter()
np.float64(0.75)

>>> code = komm.FixedToVariableCode.from_codewords(
...     source_cardinality=4,
...     codewords=[(0,), (1, 0), (1, 1, 0), (1, 1, 1)],
... )
>>> code.kraft_parameter()
np.float64(1.0)

>>> code = komm.FixedToVariableCode.from_codewords(
...     source_cardinality=4,
...     codewords=[(0, 0), (1, 1), (0,), (1,)],
... )
>>> code.kraft_parameter()
np.float64(1.5)

rate()

Computes the expected rate $R$ of the code, considering a given (first-order) pmf $p$ over $\mathcal{X}$. This quantity is given by $$ R = \frac{\bar{n}}{k}, $$ where $\bar{n}$ is the expected codeword length, assuming iid source symbols drawn according to $p$. It is measured in $|\mathcal{Y}|$-ary digits per source symbol.

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$.

Returns:

• rate (float) –

  The expected rate $R$ of the code.

Examples:

>>> code = komm.FixedToVariableCode.from_codewords(3, [(0,), (1, 0), (1, 1)])
>>> code.rate([1/2, 1/4, 1/4])
np.float64(1.5)

encode()

Encodes a sequence of source symbols using the code, which must be uniquely decodable.

Parameters:

• input (ArrayLike) –

  The sequence of symbols to be encoded. Must be a 1D-array with elements in $\mathcal{X}$ and have a length that is a multiple of $k$.

Returns:

• output (Array1D[integer]) –

  The sequence of encoded symbols. It is a 1D-array with elements in $\mathcal{Y}$.

Examples:

>>> code = komm.FixedToVariableCode.from_enc_mapping({
...     (0, 0): (0,),
...     (0, 1): (1, 1),
...     (1, 0): (1, 0, 0),
...     (1, 1): (1, 0, 1),
... })

>>> code.encode([0, 1, 0, 0])
array([1, 1, 0])

>>> code.encode([0, 1, 0])  # Not a multiple of the source block size
Traceback (most recent call last):
...
ValueError: length of input must be a multiple of block size 2 (got 3)

>>> code.encode([0, 7, 0, 0])  # 07 is not a valid source word
Traceback (most recent call last):
...
ValueError: input contains invalid word

>>> code = komm.FixedToVariableCode.from_codewords(3, [(0,), (0,1), (1,0)])
>>> code.encode([0, 1, 0])  # Code is not uniquely decodable
Traceback (most recent call last):
...
ValueError: code is not uniquely decodable

decode()

Decodes a sequence of target symbols using the code, which must be uniquely decodable.

Warning

Decoding for non-prefix-free codes is not implemented yet.

Parameters:

• input (ArrayLike) –

  The sequence of symbols to be decoded. Must be a 1D-array with elements in $\mathcal{Y}$. Also, the sequence must be a concatenation of codewords (i.e., the output of the encode method).

Returns:

• output (Array1D[integer]) –

  The sequence of decoded symbols. It is a 1D-array with elements in $\mathcal{X}$ with a length that is a multiple of $k$.

Examples:

>>> code = komm.FixedToVariableCode.from_enc_mapping({
...     (0, 0): (0,),
...     (0, 1): (1, 1),
...     (1, 0): (1, 0, 0),
...     (1, 1): (1, 0, 1),
... })

>>> code.decode([1, 1, 0])
array([0, 1, 0, 0])

>>> code.decode([0, 0, 1])  # Not a concatenation of codewords
Traceback (most recent call last):
...
ValueError: input contains invalid word

>>> code = komm.FixedToVariableCode.from_codewords(3, [(0,), (0,1), (1,0)])
>>> code.decode([0, 1, 0])  # Code is not uniquely decodable
Traceback (most recent call last):
...
ValueError: code is not uniquely decodable