komm.TruncatedBinaryCode
Truncated binary code. It is a binary symbol code with source alphabet $\mathcal{X} = [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 a source symbol $x \in \mathcal{X}$ is the $k$-bit binary representation of $x$, if $x < u$, or the $(k + 1)$-bit binary representation of $x + u$, otherwise. For more details, see Wikipedia: Truncated binary encoding.
The table below shows the codewords for small values of $M$.
| $x$ | $M = 4$ | $M = 5$ | $M = 6$ | $M = 7$ | $M = 8$ |
|---|---|---|---|---|---|
| $0$ | 00 |
00 |
00 |
00 |
000 |
| $1$ | 01 |
01 |
01 |
010 |
001 |
| $2$ | 10 |
10 |
100 |
011 |
010 |
| $3$ | 11 |
110 |
101 |
100 |
011 |
| $4$ | 111 |
110 |
101 |
100 |
|
| $5$ | 111 |
110 |
101 |
||
| $6$ | 111 |
110 |
|||
| $7$ | 111 |
Notes
- For $M$ a power of $2$ it reduces to the fixed-length binary code.
- It coincides with the Huffman code for the uniform pmf, with canonical assignment.
Parameters:
-
cardinality(SupportsIndex) –The cardinality $M$ of the code. Must satisfy $M \geq 2$.
Examples:
>>> code = komm.TruncatedBinaryCode(5)
>>> code.encode([4, 1, 3])
array([1, 1, 1, 0, 1, 1, 1, 0])
>>> code.decode([1, 1, 1, 0, 1, 1, 1, 0])
array([4, 1, 3])