komm.TruncatedBinaryCode

Truncated binary code. It is an integer code with domain $[0 : M)$, where $M \geq 2$ is a given cardinality. Let $k = \lfloor \log_2 M \rfloor$ and $u = 2^{k+1} - M$. The codeword for an integer $n \in [0 : M)$ is the $k$-bit binary representation of $n$, if $n < u$, or the $(k + 1)$-bit binary representation of $n + u$, otherwise. If $M$ is a power of $2$, the code reduces to the fixed-length binary code. For more details, see Wikipedia: Truncated binary encoding.

Parameters:

• cardinality (int) –

  The cardinality $M$ of the code. Must satisfy $M \geq 2$.

encode_single()

Encodes a single integer into its codeword.

Parameters:

• integer (int) –

  The integer to be encoded. Must be in the domain of the code.

Returns:

• bits (list[int]) –

  The codeword of the integer, as a list of bits.

Examples:

>>> code = komm.TruncatedBinaryCode(5)
>>> code.encode_single(2)
[1, 0]
>>> code.encode_single(3)
[1, 1, 0]

decode_single()

Decodes a single codeword from a bit iterator. This method consumes exactly the bits of one codeword, leaving the iterator at the boundary with the next one; any remaining bits are left untouched.

Parameters:

• bits (Iterator[int]) –

  An iterator of bits 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:

• integer (int) –

  The decoded integer.

Notes

A ValueError is raised if the iterator is exhausted mid-codeword or if an invalid bit is found. In contrast, next(self.decode(bits)) behaves identically except on an exhausted iterator, where it raises StopIteration (end of data) instead of ValueError (malformed data).

Examples:

>>> code = komm.TruncatedBinaryCode(5)
>>> bits = iter([1, 1, 0, 1, 0])
>>> code.decode_single(bits)
3
>>> list(bits)  # Iterator is left at codeword boundary
[1, 0]

length()

Returns the codeword length $\ell(n)$ for a given integer $n$ in the domain of the code.

Examples:

>>> code = komm.TruncatedBinaryCode(5)
>>> code.length(2), code.length(3)
(2, 3)

encode()

Lazily encodes an iterable of integers.

Parameters:

• input (Iterable[int]) –

  The integers to be encoded. Must all be in the domain of the code.

Returns:

• output (Iterator[int]) –

  An iterator over the bits of the concatenated codewords.

Examples:

>>> code = komm.TruncatedBinaryCode(5)
>>> list(code.encode([4, 1, 3]))
[1, 1, 1, 0, 1, 1, 1, 0]

decode()

Lazily decodes an iterable of bits.

Note

Decoding is lazy: invalid or truncated input only raises ValueError when the offending codeword is consumed.

Parameters:

• input (Iterable[int]) –

  The bits to be decoded. Must be a concatenation of codewords, possibly partial.

Returns:

• output (Iterator[int]) –

  An iterator over the decoded integers.

Examples:

>>> code = komm.TruncatedBinaryCode(5)
>>> list(code.decode([1, 1, 1, 0, 1, 1, 1, 0]))
[4, 1, 3]