komm.SymbolCode

General symbol code. A symbol code with source alphabet $\mathcal{X}$ and target alphabet $\mathcal{Y}$ is defined by an encoding mapping $\Enc: \mathcal{X} \to \mathcal{Y}^+$, where 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. For more details, see MacK03, Ch. 5.

A symbol code is equivalent to a fixed-to-variable length code with source block size $k = 1$, in which each source symbol $x$ corresponds to the $1$-tuple $(x)$.

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 symbol code from the encoding mapping $\Enc$.

Parameters:

enc_mapping (dict[int, Word]) –

The encoding mapping $\Enc$. Must be a dictionary whose keys are all the integers in $\mathcal{X}$ and whose values are non-empty tuples of integers in $\mathcal{Y}$.

Notes

The source cardinality $|\mathcal{X}|$ is inferred from the size of the domain of the encoding mapping, and the target cardinality $|\mathcal{Y}|$ from the maximum value in its co-domain.

Examples:

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

`from_codewords()` `classmethod`

Constructs a symbol code from a list of codewords.

Parameters:

codewords (list[Word]) –

The codewords of the code. Must be a list of length $|\mathcal{X}|$ containing non-empty tuples of integers in $\mathcal{Y}$. The tuple in position $x$ must be equal to $\Enc(x)$.

Notes

The source cardinality $|\mathcal{X}|$ is inferred from the number of codewords, and the target cardinality $|\mathcal{Y}|$ from the maximum value in the codewords.

Examples:

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

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

`from_lengths()` `classmethod`

Constructs a symbol code from a list of codeword lengths. The codewords are assigned in lexicographic order, which yields the canonical code with the given lengths. The resulting code is always prefix-free (hence uniquely decodable).

Parameters:

lengths (ArrayLike) –

The codeword lengths of the code. Must be a 1D-array of length $|\mathcal{X}|$ of positive integers satisfying the Kraft inequality. The integer in position $x$ must be equal to $\ell(x)$, the length of the codeword $\Enc(x)$.
target_cardinality (int) –

The target cardinality $|\mathcal{Y}|$. Must be an integer greater than or equal to $2$. The default value is $2$ (binary code).

Notes

The source cardinality $|\mathcal{X}|$ is inferred from the number of lengths.

If the lengths are non-decreasing, the resulting code is moreover alphabetic: the codewords preserve the order of the source symbols. See CT06, Sec. 5.7.

Examples:

>>> code = komm.SymbolCode.from_lengths([1, 2, 2])
>>> code.enc_mapping
{0: (0,),
 1: (1, 0),
 2: (1, 1)}

>>> code = komm.SymbolCode.from_lengths([1, 2, 2, 2], target_cardinality=3)
>>> code.enc_mapping
{0: (0,),
 1: (1, 0),
 2: (1, 1),
 3: (1, 2)}

>>> komm.SymbolCode.from_lengths([1, 1, 1])
Traceback (most recent call last):
...
ValueError: 'lengths' must satisfy Kraft inequality

`source_cardinalityint` `property`

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

Examples:

>>> code = komm.SymbolCode(3, 2, {0: (0,), 1: (1, 0), 2: (1, 1)})
>>> code.source_cardinality
3

`target_cardinalityint` `property`

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

Examples:

>>> code = komm.SymbolCode(3, 2, {0: (0,), 1: (1, 0), 2: (1, 1)})
>>> code.target_cardinality
2

`enc_mappingdict[int, Word]` `property`

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

Examples:

>>> code = komm.SymbolCode(3, 2, {0: (0,), 1: (1, 0), 2: (1, 1)})
>>> code.enc_mapping
{0: (0,),
 1: (1, 0),
 2: (1, 1)}

`codewordslist[Word]` `cached` `property`

The codewords of the code. They correspond to the image of the encoding mapping $\Enc$: the tuple in position $x$ is equal to $\Enc(x)$.

Examples:

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

`lengthslist[int]` `cached` `property`

The codeword lengths of the code. The integer in position $x$ is equal to $\ell(x)$, the length of the codeword $\Enc(x)$.

Examples:

>>> code = komm.SymbolCode(3, 2, {0: (0,), 1: (1, 0), 2: (1, 1)})
>>> code.lengths
[1, 2, 2]

`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.SymbolCode.from_codewords([(0,), (1, 0), (1, 1)])
>>> code.is_uniquely_decodable()
True

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

>>> code = komm.SymbolCode.from_codewords([(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.SymbolCode.from_codewords([(0,), (1, 0), (1, 1)])
>>> code.is_prefix_free()
True

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

>>> code = komm.SymbolCode.from_codewords([(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_{x \in \mathcal{X}} |\mathcal{Y}|^{-\ell(x)}, $$ where $\ell(x)$ is the length of the codeword $\Enc(x)$ associated with the source symbol $x \in \mathcal{X}$.

Returns:

kraft_parameter (Fraction) –

The Kraft parameter $K$ of the code.

Examples:

>>> code = komm.SymbolCode.from_codewords([(0,), (1, 0)])
>>> code.kraft_parameter()
Fraction(3, 4)

>>> code = komm.SymbolCode.from_codewords([(0,), (1, 0), (1, 1)])
>>> code.kraft_parameter()
Fraction(1, 1)

>>> code = komm.SymbolCode.from_codewords([(0, 0), (1, 1), (0,), (1,)])
>>> code.kraft_parameter()
Fraction(3, 2)

>>> code = komm.SymbolCode.from_lengths([1, 2, 2, 2], target_cardinality=3)
>>> code.kraft_parameter()
Fraction(2, 3)

`is_complete()` `cached`

Returns whether the code is complete. A code is complete if it is uniquely decodable and its Kraft parameter is equal to $1$. See MacK03, Sec. 5.2.

A prefix-free code is complete if and only if every infinite target sequence has a prefix that is a codeword, as in variable-to-fixed codes.

Examples:

>>> code = komm.SymbolCode.from_codewords([(0,), (1, 0), (1, 1)])
>>> code.is_complete()
True

>>> code = komm.SymbolCode.from_codewords([(0,), (0, 1), (1, 1)])
>>> code.is_complete()
True

>>> code = komm.SymbolCode.from_codewords([(0,), (0, 1), (1, 0)])
>>> code.is_complete()  # Not uniquely decodable
False

>>> code = komm.SymbolCode.from_codewords([(0,), (1, 0)])
>>> code.is_complete()  # Kraft parameter is 3/4
False

`average_length()`

Computes the average codeword length $\bar{n}$ of the code, considering a given pmf $p$ over $\mathcal{X}$. This quantity is given by $$ \bar{n} = \sum_{x \in \mathcal{X}} p(x) \ell(x), $$ where $\ell(x)$ is the length of the codeword $\Enc(x)$. It is measured in $|\mathcal{Y}|$-ary digits per source symbol.

Parameters:

pmf (ArrayLike) –

The pmf $p$ to be considered. Must be a 1D-array of size $|\mathcal{X}|$ of non-negative values that sum to $1$.

Returns:

average_length (float) –

The average codeword length $\bar{n}$ of the code.

Examples:

>>> code = komm.SymbolCode.from_codewords([(0,), (1, 0), (1, 1)])
>>> code.average_length([1/2, 1/4, 1/4])
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}$.

Returns:

output (Array1D[integer]) –

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

Examples:

>>> code = komm.SymbolCode.from_codewords([(0,), (1, 0), (1, 1)])

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

>>> code.encode([0, 3, 0])  # 3 is not a source symbol
Traceback (most recent call last):
...
ValueError: elements of 'input' must be in [0:3)

>>> code = komm.SymbolCode.from_codewords([(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.

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

Examples:

>>> code = komm.SymbolCode.from_codewords([(0,), (1, 0), (1, 1)])

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

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

>>> code = komm.SymbolCode.from_codewords([(0,), (0, 1), (1, 1)])
>>> code.decode([0, 1, 1, 1])  # Code is not prefix-free
array([1, 2])

>>> code = komm.SymbolCode.from_codewords([(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

`encode_single()`

Encodes a single source symbol into its codeword.

Parameters:

symbol (SupportsIndex) –

The source symbol to be encoded. Must be in $\mathcal{X}$.

Returns:

codeword (Word) –

The codeword of the source symbol. It is a tuple with elements in $\mathcal{Y}$.

Examples:

>>> code = komm.SymbolCode.from_codewords([(0,), (1, 0), (1, 1)])

>>> code.encode_single(2)
(1, 1)

>>> code.encode_single(3)  # 3 is not a source symbol
Traceback (most recent call last):
...
ValueError: 'symbol' must be in [0:3) (got 3)

`decode_single()`

Decodes a single codeword from an iterator of target symbols, using the code, which must be prefix-free. This method consumes exactly the symbols of one codeword, leaving the iterator at the boundary with the next one; any remaining symbols are left untouched.

Parameters:

symbols (Iterator[SupportsIndex]) –

An iterator of target symbols starting with a complete codeword. It must be an iterator (as returned by iter), not a general iterable, since advancing it is part of the contract.

Returns:

symbol (int) –

The decoded source symbol.

Notes

A ValueError is raised if the iterator is exhausted mid-codeword or if an invalid word is found.

Examples:

>>> code = komm.SymbolCode.from_codewords([(0,), (1, 0), (1, 1)])

>>> symbols = iter([1, 1, 0, 1, 0])
>>> code.decode_single(symbols)
2
>>> list(symbols)  # Iterator is left at codeword boundary
[0, 1, 0]

>>> code.decode_single(iter([1]))  # Incomplete codeword
Traceback (most recent call last):
...
ValueError: input contains an incomplete codeword

>>> code = komm.SymbolCode.from_codewords([(0,), (0, 1), (1, 1)])
>>> code.decode_single(iter([0, 1]))  # Code is not prefix-free
Traceback (most recent call last):
...
ValueError: code is not prefix-free

komm.SymbolCode

from_enc_mapping() classmethod

from_codewords() classmethod

from_lengths() classmethod

source_cardinality int property

target_cardinality int property

enc_mapping dict[int, Word] property

codewords list[Word] cached property

lengths list[int] cached property

is_uniquely_decodable() cached

is_prefix_free() cached

kraft_parameter() cached

is_complete() cached

average_length()

encode()

decode()

encode_single()

decode_single()

`from_enc_mapping()` `classmethod`

`from_codewords()` `classmethod`

`from_lengths()` `classmethod`

`source_cardinalityint` `property`

`target_cardinalityint` `property`

`enc_mappingdict[int, Word]` `property`

`codewordslist[Word]` `cached` `property`

`lengthslist[int]` `cached` `property`

`is_uniquely_decodable()` `cached`

`is_prefix_free()` `cached`

`kraft_parameter()` `cached`

`is_complete()` `cached`

`average_length()`

`encode()`

`decode()`

`encode_single()`

`decode_single()`