komm.EliasDeltaCode

Elias delta code. It is an integer code. The codeword for a positive integer $n$ consists of the Elias gamma codeword for the number of bits of $n$ followed by the binary representation of $n$ without its leading one. For more details, see Wikipedia: Elias delta coding or MacK03, Ch. 7 (therein called code $C_\beta$).

encode_single()

Encodes a single integer into its codeword.

Parameters:

• integer (int) –

  The integer to be encoded. Must be positive.

Returns:

• bits (list[int]) –

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

Examples:

>>> code = komm.EliasDeltaCode()
>>> code.encode_single(4)
[0, 1, 1, 0, 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.EliasDeltaCode()
>>> bits = iter([0, 1, 1, 0, 0, 1, 1])
>>> code.decode_single(bits)
4
>>> list(bits)  # Iterator is left at codeword boundary
[1, 1]

length()

Returns the codeword length $\ell(n)$ for a given positive integer $n$.

Examples:

>>> code = komm.EliasDeltaCode()
>>> code.length(4)
5

encode()

Lazily encodes an iterable of positive integers.

Parameters:

• input (Iterable[int]) –

  The integers to be encoded. Must all be positive.

Returns:

• output (Iterator[int]) –

  An iterator over the bits of the concatenated codewords.

Examples:

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

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 positive integers.

Examples:

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