komm.TerminatedConvolutionalCode

Terminated convolutional code. It is a linear block code obtained by terminating a $(n_0, k_0)$ convolutional code. A total of $h$ information blocks (each containing $k_0$ information bits) is encoded. The dimension of the resulting block code is thus $k = h k_0$; its length depends on the termination mode employed. There are three possible termination modes:

Direct truncation. The encoder always starts at state $0$, and its output ends immediately after the last information block. The encoder may not necessarily end in state $0$. The resulting block code will have length $n = h n_0$.
Zero termination. The encoder always starts and ends at state $0$. To achieve this, a sequence of $k \mu$ tail bits is appended to the information bits, where $\mu$ is the memory order of the convolutional code. The resulting block code will have length $n = (h + \mu) n_0$.
Tail-biting. The encoder always starts and ends at the same state. To achieve this, the initial state of the encoder is chosen as a function of the information bits. This is possible only if $A^h + I$ is invertible, where $A$ is the state matrix of the convolutional code; this always holds for codes without feedback. The resulting block code will have length $n = h n_0$.

The code may also be punctured: after termination, the codeword bits are kept or deleted according to a puncturing matrix $\mathbf{P} \in \mathbb{B}^{n_0 \times T}$, in which the element at row $i$ and column $t$ tells whether the $i$-th output bit of block $t \bmod T$ is kept (1) or deleted (0), tail blocks included. The lengths given above are then denoted by $n_\mathrm{u}$, the length of the unpunctured code, and the length $n$ of the punctured code is the number of kept positions. The puncturing must not delete any nonzero codeword, so that the dimension $k$ is preserved.

For more details, see LC04, Sec. 12.7 and WBR01.

Parameters:

convolutional_code (ConvolutionalCode) –

The convolutional code to be terminated.
num_blocks (int) –

The number $h$ of information blocks. Must be a positive integer.
mode (TerminationMode) –

The termination mode. It must be one of 'direct-truncation' | 'zero-termination' | 'tail-biting'. The default value is 'zero-termination'.
puncturing_matrix (ArrayLike | None) –

The puncturing matrix $\mathbf{P}$. Must be an $n_0 \times T$ array of bits with at least one 1, where the period $T$ divides the number $n_\mathrm{u} / n_0$ of trellis sections. The default value corresponds to no puncturing.

Examples:

>>> code = komm.TerminatedConvolutionalCode(
...     convolutional_code=komm.ConvolutionalCode([[0b1, 0b11]]),
...     num_blocks=3,
...     mode='direct-truncation',
... )
>>> (code.length, code.dimension, code.redundancy)
(6, 3, 3)
>>> code.generator_matrix
array([[1, 1, 0, 1, 0, 0],
       [0, 0, 1, 1, 0, 1],
       [0, 0, 0, 0, 1, 1]])
>>> code.minimum_distance()
2

>>> code = komm.TerminatedConvolutionalCode(
...     convolutional_code=komm.ConvolutionalCode([[0b1, 0b11]]),
...     num_blocks=3,
...     mode='zero-termination',
... )
>>> (code.length, code.dimension, code.redundancy)
(8, 3, 5)
>>> code.generator_matrix
array([[1, 1, 0, 1, 0, 0, 0, 0],
       [0, 0, 1, 1, 0, 1, 0, 0],
       [0, 0, 0, 0, 1, 1, 0, 1]])
>>> code.minimum_distance()
3

>>> code = komm.TerminatedConvolutionalCode(
...     convolutional_code=komm.ConvolutionalCode([[0b1, 0b11]]),
...     num_blocks=3,
...     mode='tail-biting',
... )
>>> (code.length, code.dimension, code.redundancy)
(6, 3, 3)
>>> code.generator_matrix
array([[1, 1, 0, 1, 0, 0],
       [0, 0, 1, 1, 0, 1],
       [0, 1, 0, 0, 1, 1]])
>>> code.minimum_distance()
3

>>> code = komm.TerminatedConvolutionalCode(
...     convolutional_code=komm.ConvolutionalCode([[0b1, 0b11]]),
...     num_blocks=3,
...     mode='zero-termination',
...     puncturing_matrix=[[1, 1], [1, 0]],
... )
>>> (code.length, code.dimension, code.redundancy)
(6, 3, 3)
>>> code.generator_matrix
array([[1, 1, 0, 0, 0, 0],
       [0, 0, 1, 0, 1, 0],
       [0, 0, 0, 1, 1, 0]])
>>> code.minimum_distance()
2

`lengthint` `cached` `property`

The length $n$ of the code.

Examples:

>>> code = komm.TerminatedConvolutionalCode(
...     convolutional_code=komm.ConvolutionalCode([[0b1, 0b11]]),
...     num_blocks=3,
...     mode='tail-biting',
... )
>>> code.length
6

`dimensionint` `cached` `property`

The dimension $k$ of the code.

Examples:

>>> code = komm.TerminatedConvolutionalCode(
...     convolutional_code=komm.ConvolutionalCode([[0b1, 0b11]]),
...     num_blocks=3,
...     mode='tail-biting',
... )
>>> code.dimension
3

`redundancyint` `cached` `property`

The redundancy $m$ of the code.

Examples:

>>> code = komm.TerminatedConvolutionalCode(
...     convolutional_code=komm.ConvolutionalCode([[0b1, 0b11]]),
...     num_blocks=3,
...     mode='tail-biting',
... )
>>> code.redundancy
3

`ratefloat` `cached` `property`

The rate $R = k/n$ of the code.

Examples:

>>> code = komm.TerminatedConvolutionalCode(
...     convolutional_code=komm.ConvolutionalCode([[0b1, 0b11]]),
...     num_blocks=3,
...     mode='tail-biting',
... )
>>> code.rate
0.5

`generator_matrixArray2D[integer]` `cached` `property`

The generator matrix $G \in \mathbb{B}^{k \times n}$ of the code.

Examples:

>>> code = komm.TerminatedConvolutionalCode(
...     convolutional_code=komm.ConvolutionalCode([[0b1, 0b11]]),
...     num_blocks=3,
...     mode='tail-biting',
... )
>>> code.generator_matrix
array([[1, 1, 0, 1, 0, 0],
       [0, 0, 1, 1, 0, 1],
       [0, 1, 0, 0, 1, 1]])

`check_matrixArray2D[integer]` `cached` `property`

The check matrix $H \in \mathbb{B}^{m \times n}$ of the code.

Examples:

>>> code = komm.TerminatedConvolutionalCode(
...     convolutional_code=komm.ConvolutionalCode([[0b1, 0b11]]),
...     num_blocks=3,
...     mode='tail-biting',
... )
>>> code.check_matrix
array([[1, 0, 1, 1, 0, 0],
       [1, 1, 0, 0, 1, 0],
       [1, 1, 1, 0, 0, 1]])

`encode()`

Applies the encoding mapping $\Enc : \mathbb{B}^k \to \mathbb{B}^n$ of the code. This method takes one or more sequences of messages and returns their corresponding codeword sequences.

Parameters:

input (ArrayLike) –

The input sequence(s). Can be either a single sequence whose length is a multiple of $k$, or a multidimensional array where the last dimension is a multiple of $k$.

Returns:

output (NDArray[integer]) –

The output sequence(s). Has the same shape as the input, with the last dimension expanded from $bk$ to $bn$, where $b$ is a positive integer.

Examples:

See BlockCode.encode for examples.

`inverse_encode()`

Applies the inverse encoding partial mapping $\Enc^{-1} : \mathbb{B}^n \rightharpoonup \mathbb{B}^k$ of the code. This method takes one or more sequences of codewords and returns their corresponding message sequences.

Parameters:

input (ArrayLike) –

The input sequence(s). Can be either a single sequence whose length is a multiple of $n$, or a multidimensional array where the last dimension is a multiple of $n$.

Returns:

output (NDArray[integer]) –

The output sequence(s). Has the same shape as the input, with the last dimension contracted from $bn$ to $bk$, where $b$ is a positive integer.

Examples:

See BlockCode.inverse_encode for examples.

`check()`

Applies the check mapping $\mathrm{Chk} : \mathbb{B}^n \to \mathbb{B}^m$ of the code. This method takes one or more sequences of received words and returns their corresponding syndrome sequences.

Parameters:

input (ArrayLike) –

The input sequence(s). Can be either a single sequence whose length is a multiple of $n$, or a multidimensional array where the last dimension is a multiple of $n$.

Returns:

output (NDArray[integer]) –

The output sequence(s). Has the same shape as the input, with the last dimension contracted from $bn$ to $bm$, where $b$ is a positive integer.

Examples:

See BlockCode.check for examples.

`depuncture()`

Undoes the puncturing, by inserting a given value at the deleted positions. This method takes one or more sequences of received words and returns their corresponding sequences in the coordinates of the unpunctured code.

Parameters:

input (ArrayLike) –

The input sequence(s). Can be either a single sequence whose length is a multiple of $n$, or a multidimensional array where the last dimension is a multiple of $n$.
fill_value (float) –

The value to insert at the deleted positions, such as 0.0 for L-values or 2 for erasures.

Returns:

output (NDArray[integer | floating]) –

The output sequence(s). Has the same shape as the input, but with the last dimension expanded by a factor of $n_\mathrm{u} / n$.

Examples:

>>> code = komm.TerminatedConvolutionalCode(
...     convolutional_code=komm.ConvolutionalCode([[0b1, 0b11]]),
...     num_blocks=3,
...     mode='zero-termination',
...     puncturing_matrix=[[1, 1], [1, 0]],
... )
>>> code.depuncture([1, 1, 1, 0, 0, 0], 2)
array([1, 1, 1, 2, 0, 0, 0, 2])
>>> code.depuncture([-0.8, -0.1, -1.0, +0.5, +1.8, -1.1], 0.0)
array([-0.8, -0.1, -1. ,  0. ,  0.5,  1.8, -1.1,  0. ])

`codewords()` `cached`

Returns the codewords of the code. This is a $2^k \times n$ matrix whose rows are all the codewords. The codeword in row $i$ corresponds to the message obtained by expressing $i$ in binary with $k$ bits (LSB-first).

Examples:

>>> code = komm.TerminatedConvolutionalCode(
...     convolutional_code=komm.ConvolutionalCode([[0b1, 0b11]]),
...     num_blocks=3,
...     mode='tail-biting',
... )
>>> code.codewords()
array([[0, 0, 0, 0, 0, 0],
       [1, 1, 0, 1, 0, 0],
       [0, 0, 1, 1, 0, 1],
       [1, 1, 1, 0, 0, 1],
       [0, 1, 0, 0, 1, 1],
       [1, 0, 0, 1, 1, 1],
       [0, 1, 1, 1, 1, 0],
       [1, 0, 1, 0, 1, 0]])

`codeword_weight_distribution()` `cached`

Returns the codeword weight distribution of the code. This is the list $A_0, A_1, \ldots, A_n$, in which $A_w$ is the number of codewords of Hamming weight $w$.

If $m < k$, this method enumerates the $2^m$ codewords of the dual code, spanned by the rows of the check matrix $H$, and applies the MacWilliams identity $$ \sum_{w=0}^n A_w z^w = \frac{1}{2^m} \sum_{w=0}^n B_w (1 - z)^w (1 + z)^{n - w}, $$ where $B_w$ is the number of codewords of Hamming weight $w$ in the dual code. Otherwise, it enumerates the $2^k$ codewords of the code. For more details, see LC04, Sec. 3.6.

Examples:

>>> code = komm.TerminatedConvolutionalCode(
...     convolutional_code=komm.ConvolutionalCode([[0b1, 0b11]]),
...     num_blocks=3,
...     mode='tail-biting',
... )
>>> code.codeword_weight_distribution()
[1, 0, 0, 4, 3, 0, 0]

`minimum_distance()` `cached`

Returns the minimum distance $d$ of the code. This is equal to the minimum Hamming weight of the non-zero codewords.

Examples:

>>> code = komm.TerminatedConvolutionalCode(
...     convolutional_code=komm.ConvolutionalCode([[0b1, 0b11]]),
...     num_blocks=3,
...     mode='tail-biting',
... )
>>> code.minimum_distance()
3

`coset_leaders()` `cached`

Returns the coset leaders of the code. This is a $2^m \times n$ matrix whose rows are all the coset leaders. The coset leader in row $i$ corresponds to the syndrome obtained by expressing $i$ in binary with $m$ bits (LSB-first), and whose Hamming weight is minimal. This may be used as a LUT for syndrome-based decoding.

Of all minimal-weight words in each coset, this method returns the one whose support comes first in lexicographic order.

Examples:

>>> code = komm.TerminatedConvolutionalCode(
...     convolutional_code=komm.ConvolutionalCode([[0b1, 0b11]]),
...     num_blocks=3,
...     mode='tail-biting',
... )
>>> code.coset_leaders()
array([[0, 0, 0, 0, 0, 0],
       [0, 0, 0, 1, 0, 0],
       [0, 0, 0, 0, 1, 0],
       [1, 0, 0, 0, 0, 1],
       [0, 0, 0, 0, 0, 1],
       [0, 0, 1, 0, 0, 0],
       [0, 1, 0, 0, 0, 0],
       [1, 0, 0, 0, 0, 0]])

`coset_leader_weight_distribution()` `cached`

Returns the coset leader weight distribution of the code. This is the list $\alpha_0, \alpha_1, \ldots, \alpha_n$, in which $\alpha_w$ is the number of coset leaders of Hamming weight $w$.

Examples:

>>> code = komm.TerminatedConvolutionalCode(
...     convolutional_code=komm.ConvolutionalCode([[0b1, 0b11]]),
...     num_blocks=3,
...     mode='tail-biting',
... )
>>> code.coset_leader_weight_distribution()
[1, 6, 1, 0, 0, 0, 0]

`packing_radius()` `cached`

Returns the packing radius of the code. This is also called the error-correcting capability of the code, and is equal to $\lfloor (d - 1) / 2 \rfloor$.

Examples:

>>> code = komm.TerminatedConvolutionalCode(
...     convolutional_code=komm.ConvolutionalCode([[0b1, 0b11]]),
...     num_blocks=3,
...     mode='tail-biting',
... )
>>> code.packing_radius()
1

`covering_radius()` `cached`

Returns the covering radius of the code. This is equal to the maximum Hamming weight of the coset leaders.

Examples:

>>> code = komm.TerminatedConvolutionalCode(
...     convolutional_code=komm.ConvolutionalCode([[0b1, 0b11]]),
...     num_blocks=3,
...     mode='tail-biting',
... )
>>> code.covering_radius()
2

komm.TerminatedConvolutionalCode

length int cached property

dimension int cached property

redundancy int cached property

rate float cached property

generator_matrix Array2D[integer] cached property

check_matrix Array2D[integer] cached property

encode()

inverse_encode()

check()

depuncture()

codewords() cached

codeword_weight_distribution() cached

minimum_distance() cached

coset_leaders() cached

coset_leader_weight_distribution() cached

packing_radius() cached

covering_radius() cached

`lengthint` `cached` `property`

`dimensionint` `cached` `property`

`redundancyint` `cached` `property`

`ratefloat` `cached` `property`

`generator_matrixArray2D[integer]` `cached` `property`

`check_matrixArray2D[integer]` `cached` `property`

`encode()`

`inverse_encode()`

`check()`

`depuncture()`

`codewords()` `cached`

`codeword_weight_distribution()` `cached`

`minimum_distance()` `cached`

`coset_leaders()` `cached`

`coset_leader_weight_distribution()` `cached`

`packing_radius()` `cached`

`covering_radius()` `cached`