Skip to content

komm.ConvolutionalCode

Binary convolutional code. It is characterized by a matrix of feedforward polynomials $\mathbf{P}(D)$, of shape $k \times n$, and (optionally) by a vector of feedback polynomials $\mathbf{q}(D)$, of length $k$. The element in row $i$ and column $j$ of $\mathbf{P}(D)$ is denoted by $p_{i,j}(D)$, and the element in position $i$ of $\mathbf{q}(D)$ is denoted by $q_i(D)$; they are binary polynomials in $D$. The parameters $k$ and $n$ are the number of input and output bits per block, respectively. For more details, see JZ15 and LC04, Chs. 11, 12.

Parameters:

  • feedforward_polynomials (ArrayLike) –

    The matrix of feedforward polynomials $\mathbf{P}(D)$, which is a $k \times n$ matrix whose entries are either binary polynomials or integers to be converted to the former.

  • feedback_polynomials (ArrayLike | None) –

    The vector of feedback polynomials $\mathbf{q}(D)$, which is a $k$-vector whose entries are either binary polynomials or integers to be converted to the former. The default value corresponds to no feedback, that is, $q_i(D) = 1$ for all $i \in [0 : k)$.

Examples:

  1. Consider the encoder with parameters $(n, k, \sigma) = (2, 1, 6)$ depicted below.

    Convolutional encoder for (2, 1, 6) code.

    Its matrix of feedforward polynomials is given by $$ \mathbf{P}(D) = \begin{bmatrix} D^6 + D^3 + D^2 + D + 1 && D^6 + D^5 + D^3 + D^2 + 1 \end{bmatrix}. $$

    >>> code = komm.ConvolutionalCode(
...     feedforward_polynomials=[[0b1001111, 0b1101101]],
... )

  2. Consider the encoder with parameters $(n, k, \sigma) = (3, 2, 7)$ depicted below.

    Convolutional encoder for (3, 2, 7) code.

    Its matrix of feedforward polynomials is given by $$ \mathbf{P}(D) = \begin{bmatrix} D^4 + D^3 + 1 & D^4 + D^2 + D + 1 & 0 \\ 0 & D^3 + D & D^3 + D^2 + 1 \end{bmatrix}. $$

    >>> code = komm.ConvolutionalCode(
...     feedforward_polynomials=[
...         [0b11001, 0b10111,      0],
...         [      0,  0b1010, 0b1101],
...     ],
... )

  3. Consider the feedback encoder with parameters $(n, k, \sigma) = (2, 1, 4)$ depicted below.

    Convolutional encoder for (2, 1, 4) feedback code.

    Its matrix of feedforward polynomials is given by $$ \mathbf{P}(D) = \begin{bmatrix} D^4 + D^2 + D + 1 && D^4 + D^3 + 1 \end{bmatrix}, $$ and its vector of feedback polynomials is given by $$ \mathbf{q}(D) = \begin{bmatrix} D^4 + D^2 + D + 1 \end{bmatrix}. $$

    >>> code = komm.ConvolutionalCode(
...     feedforward_polynomials=[[0b10111, 0b11001]],
...     feedback_polynomials=[0b10111],
... )

Tables of optimal convolutional codes

The tables below LC04, Sec. 12.3 lists optimal convolutional codes with no feedback, for parameters $(n,k) = (2,1)$ and $(n,k) = (3,1)$, and small values of the overall constraint length $\sigma$.

Parameters $(n, k, \sigma)$ Transfer function matrix $\mathbf{G}(D)$
$(2, 1, 1)$ [[0o1, 0o3]]
$(2, 1, 2)$ [[0o5, 0o7]]
$(2, 1, 3)$ [[0o13, 0o17]]
$(2, 1, 4)$ [[0o27, 0o31]]
$(2, 1, 5)$ [[0o53, 0o75]]
$(2, 1, 6)$ [[0o117, 0o155]]
$(2, 1, 7)$ [[0o247, 0o371]]
$(2, 1, 8)$ [[0o561, 0o753]]
Parameters $(n, k, \sigma)$ Transfer function matrix $\mathbf{G}(D)$
$(3, 1, 1)$ [[0o1, 0o3, 0o3]]
$(3, 1, 2)$ [[0o5, 0o7, 0o7]]
$(3, 1, 3)$ [[0o13, 0o15, 0o17]]
$(3, 1, 4)$ [[0o25, 0o33, 0o37]]
$(3, 1, 5)$ [[0o47, 0o53, 0o75]]
$(3, 1, 6)$ [[0o117, 0o127, 0o155]]
$(3, 1, 7)$ [[0o255, 0o331, 0o367]]
$(3, 1, 8)$ [[0o575, 0o623, 0o727]]

num_input_bits int cached property

The number of input bits per block, $k$.

Examples:

>>> code = komm.ConvolutionalCode(
...     feedforward_polynomials=[[0o31, 0o27, 0o00], [0o00, 0o12, 0o15]],
... )
>>> code.num_input_bits
2

num_output_bits int cached property

The number of output bits per block, $n$.

Examples:

>>> code = komm.ConvolutionalCode(
...     feedforward_polynomials=[[0o31, 0o27, 0o00], [0o00, 0o12, 0o15]],
... )
>>> code.num_output_bits
3

transfer_function_matrix NDArray[object_] cached property

The transfer function matrix (also known as transform-domain generator matrix) $\mathbf{G}(D)$ of the code. This is a $k \times n$ array of binary polynomial fractions with element in row $i$ and column $j$ given by $$ g_{i,j}(D) = \frac{p_{i,j}(D)}{q_{i}(D)}, $$ for $i \in [0 : k)$ and $j \in [0 : n)$.

Examples:

>>> code = komm.ConvolutionalCode(
...     feedforward_polynomials=[[0o31, 0o27, 0o00], [0o00, 0o12, 0o15]],
... )
>>> for row in code.transfer_function_matrix:
...     print("[" + ", ".join(str(x).ljust(12) for x in row) + "]")
[0b11001/0b1 , 0b10111/0b1 , 0b0/0b1     ]
[0b0/0b1     , 0b1010/0b1  , 0b1101/0b1  ]

>>> code = komm.ConvolutionalCode(
...     feedforward_polynomials=[[0o27, 0o31]],
...     feedback_polynomials=[0o27],
... )
>>> for row in code.transfer_function_matrix:
...     print("[" + ", ".join(str(x) for x in row) + "]")
[0b1/0b1, 0b11001/0b10111]

constraint_lengths NDArray[integer] cached property

The constraint lengths $\nu_i$ of the code, defined by $$ \nu_i = \max \{ \deg p_{i,0}(D), \deg p_{i,1}(D), \ldots, \deg p_{i,n-1}(D), \deg q_i(D) \}, $$ for $i \in [0 : k)$. This is a $k$-array of integers.

Examples:

>>> code = komm.ConvolutionalCode(
...     feedforward_polynomials=[[0o31, 0o27, 0o00], [0o00, 0o12, 0o15]],
... )
>>> code.constraint_lengths
array([4, 3])

overall_constraint_length int cached property

The overall constraint length $\sigma$ of the code, defined by $$ \sigma = \sum_{i \in [0:k)} \nu_i. $$

Examples:

>>> code = komm.ConvolutionalCode(
...     feedforward_polynomials=[[0o31, 0o27, 0o00], [0o00, 0o12, 0o15]],
... )
>>> code.overall_constraint_length
7

memory_order int cached property

The memory order $\mu$ of the code, defined by $$ \mu = \max_{i \in [0:k)} \nu_i. $$

Examples:

>>> code = komm.ConvolutionalCode(
...     feedforward_polynomials=[[0o31, 0o27, 0o00], [0o00, 0o12, 0o15]],
... )
>>> code.memory_order
4

free_distance() cached

Returns the free distance $d_\mathrm{free}$ of the code. This is equal to the minimum Hamming weight among all non-zero encoded bit sequences

Examples:

>>> code = komm.ConvolutionalCode([[0b111, 0b101]])
>>> code.free_distance()
5

state_space_representation() cached

Returns the state-space representation of the code, in controller canonical form. Let $$ \begin{aligned} \mathbf{u}_t & = (u_t^{(0)}, u_t^{(1)}, \ldots, u_t^{(k-1)}), \\ \mathbf{v}_t & = (v_t^{(0)}, v_t^{(1)}, \ldots, v_t^{(n-1)}), \\ \mathbf{s}_t & = (s_t^{(0)}, s_t^{(1)}, \ldots, s_t^{(\sigma-1)}), \end{aligned} $$ be the input block, output block, and state, respectively, all defined at time instant $t$. Then, $$ \begin{aligned} \mathbf{s}_{t+1} & = \mathbf{s}_t \mathbf{A} + \mathbf{u}_t \mathbf{B}, \\ \mathbf{v}_{t} & = \mathbf{s}_t \mathbf{C} + \mathbf{u}_t \mathbf{D}, \end{aligned} $$ where $\mathbf{A}$ is the $\sigma \times \sigma$ state matrix, $\mathbf{B}$ is the $k \times \sigma$ control matrix, $\mathbf{C}$ is the $\sigma \times n$ observation matrix, and $\mathbf{D}$ is the $k \times n$ transition matrix. They are all binary matrices. For more details, see WBR01.

Returns:

  • state_matrix (NDArray[integer]) –

    The state matrix $\mathbf{A}$ of the code.

  • control_matrix (NDArray[integer]) –

    The control matrix $\mathbf{B}$ of the code.

  • observation_matrix (NDArray[integer]) –

    The observation matrix $\mathbf{C}$ of the code.

  • transition_matrix (NDArray[integer]) –

    The transition matrix $\mathbf{D}$ of the code.

Examples:

>>> code = komm.ConvolutionalCode([[0b111, 0b101]])
>>> state_matrix, control_matrix, observation_matrix, transition_matrix = (
...     code.state_space_representation()
... )
>>> state_matrix
array([[0, 1],
       [0, 0]])
>>> control_matrix
array([[1, 0]])
>>> observation_matrix
array([[1, 0],
       [1, 1]])
>>> transition_matrix
array([[1, 1]])

finite_state_machine() cached

Returns the finite-state (Mealy) machine of the code, in controller canonical form.

Examples:

>>> code = komm.ConvolutionalCode([[0b111, 0b101]])
>>> code.finite_state_machine()
MealyMachine(transitions=[[0, 1], [2, 3], [0, 1], [2, 3]],
             outputs=[[0, 3], [1, 2], [3, 0], [2, 1]])

encode()

Encodes a given bit sequence, starting from the all-zero state.

Parameters:

  • input (ArrayLike) –

    The bit sequence to be encoded. Must be a 1D-array of bits, with length multiple of $k$.

Returns:

  • output (NDArray[integer]) –

    The encoded bit sequence. It is a 1D-array of bits, with length multiple of $n$.

Examples:

>>> code = komm.ConvolutionalCode([[0b111, 0b101]])
>>> code.encode([1, 1, 1, 1])
array([1, 1, 0, 1, 1, 0, 1, 0])

encode_with_state()

Encodes a given bit sequence, starting from a given state.

Parameters:

  • input (ArrayLike) –

    The bit sequence to be encoded. Must be a 1D-array of bits, with length multiple of $k$.

  • initial_state (ArrayLike) –

    The initial state. Must be a 1D-array of length $\sigma$.

Returns:

  • output (NDArray[integer]) –

    The encoded bit sequence. It is a 1D-array of bits, with length multiple of $n$.

  • final_state (NDArray[integer]) –

    The final state. It is a 1D-array of length $\sigma$.

Examples:

>>> code = komm.ConvolutionalCode([[0b111, 0b101]])
>>> code.encode_with_state([1, 1, 1, 1], [0, 0])
(array([1, 1, 0, 1, 1, 0, 1, 0]), array([1, 1]))
>>> code.encode_with_state([1, 1, 1, 1], [1, 1])
(array([1, 0, 1, 0, 1, 0, 1, 0]), array([1, 1]))