komm.ConvolutionalCode
Binary convolutional encoder. It is characterized by a matrix of feedforward polynomials $P(D)$, of shape $k \times n$, and (optionally) by a vector of feedback polynomials $q(D)$, of length $k$. The parameters $k$ and $n$ are the number of input and output bits per block, respectively. In this class, the encoder is realized in controllable canonical form. For more details, see McE98, JZ15, and LC04, Chs. 11, 12.
Parameters:
-
feedforward_polynomials
(ArrayLike
) –The matrix of feedforward polynomials $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 $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:
-
Consider the encoder with parameters $(n, k, \sigma) = (3, 2, 7)$ depicted below.
Its matrix of feedforward polynomials is given by $$ 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], ... ], ... ) >>> code = komm.ConvolutionalCode( ... feedforward_polynomials=[[0o31, 0o27, 0o0], [0o0, 0o12, 0o15]], ... )
-
Consider the feedback encoder with parameters $(n, k, \sigma) = (2, 1, 4)$ depicted below.
Its matrix of feedforward polynomials is given by $$ 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 $$ q(D) = \begin{bmatrix} D^4 + D^2 + D + 1 \end{bmatrix}. $$
>>> code = komm.ConvolutionalCode( ... feedforward_polynomials=[[0b10111, 0b11001]], ... feedback_polynomials=[0b10111], ... ) >>> code = komm.ConvolutionalCode( ... feedforward_polynomials=[[0o27, 0o31]], ... feedback_polynomials=[0o27], ... )
num_input_bits
int
cached
property
The number of input bits per block, $k$.
Examples:
>>> code = komm.ConvolutionalCode(
... feedforward_polynomials=[[0o31, 0o27, 0o0], [0o0, 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, 0o0], [0o0, 0o12, 0o15]],
... )
>>> code.num_output_bits
3
degree
int
cached
property
The degree $\sigma$ of the encoder. This corresponds to the number of delay elements in the encoder realization.
It is given by $$ \sigma = \sum_{i \in [0:k)} \nu_i, $$ where $\nu_i$ are the constraint lengths of the encoder.
Examples:
>>> code = komm.ConvolutionalCode(
... feedforward_polynomials=[[0o31, 0o27, 0o0], [0o0, 0o12, 0o15]],
... )
>>> code.degree
7
memory_order
int
cached
property
The memory order $\mu$ of the encoder. It is given by $$ \mu = \max_{i \in [0:k)} \nu_i, $$ where $\nu_i$ are the constraint lengths of the encoder.
Examples:
>>> code = komm.ConvolutionalCode(
... feedforward_polynomials=[[0o31, 0o27, 0o0], [0o0, 0o12, 0o15]],
... )
>>> code.memory_order
4
constraint_lengths
NDArray[integer]
cached
property
The constraint lengths $\nu_i$ of the encoder, 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, 0o0], [0o0, 0o12, 0o15]],
... )
>>> code.constraint_lengths
array([4, 3])
state_space_representation()
cached
Returns the matrices $(\mathbf{A}, \mathbf{B}, \mathbf{C}, \mathbf{D})$ corresponding to the state-space representation of the encoder realization. The state-space representation of the encoder is given by $$ \begin{aligned} s_{t+1} & = s_t \mathbf{A} + u_t \mathbf{B}, \\ v_t & = s_t \mathbf{C} + u_t \mathbf{D}, \end{aligned} $$ where
- $u_t \in \mathbb{B}^k$ is the input block,
- $v_t \in \mathbb{B}^n$ is the output block,
- $s_t \in \mathbb{B}^\sigma$ is the state,
- $\mathbf{A} \in \mathbb{B}^{\sigma \times \sigma}$ is the state matrix,
- $\mathbf{B} \in \mathbb{B}^{k \times \sigma}$ is the control matrix,
- $\mathbf{C} \in \mathbb{B}^{\sigma \times n}$ is the observation matrix,
- $\mathbf{D} \in \mathbb{B}^{k \times n}$ is the transition matrix.
Returns:
-
state_matrix
(NDArray[integer]
) –The state matrix $\mathbf{A}$ of the encoder.
-
control_matrix
(NDArray[integer]
) –The control matrix $\mathbf{B}$ of the encoder.
-
observation_matrix
(NDArray[integer]
) –The observation matrix $\mathbf{C}$ of the encoder.
-
transition_matrix
(NDArray[integer]
) –The transition matrix $\mathbf{D}$ of the encoder.
Examples:
>>> code = komm.ConvolutionalCode(
... feedforward_polynomials=[[0o31, 0o27, 0o0], [0o0, 0o12, 0o15]],
... )
>>> A_mat, B_mat, C_mat, D_mat = code.state_space_representation()
>>> A_mat
array([[0, 1, 0, 0, 0, 0, 0],
[0, 0, 1, 0, 0, 0, 0],
[0, 0, 0, 1, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 1, 0],
[0, 0, 0, 0, 0, 0, 1],
[0, 0, 0, 0, 0, 0, 0]])
>>> B_mat
array([[1, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 0, 0]])
>>> C_mat
array([[0, 1, 0],
[0, 1, 0],
[1, 0, 0],
[1, 1, 0],
[0, 1, 0],
[0, 0, 1],
[0, 1, 1]])
>>> D_mat
array([[1, 1, 0],
[0, 0, 1]])
>>> code = komm.ConvolutionalCode(
... feedforward_polynomials=[[0o27, 0o31]],
... feedback_polynomials=[0o27],
... )
>>> A_mat, B_mat, C_mat, D_mat = code.state_space_representation()
>>> A_mat
array([[1, 1, 0, 0],
[1, 0, 1, 0],
[0, 0, 0, 1],
[1, 0, 0, 0]])
>>> B_mat
array([[1, 0, 0, 0]])
>>> C_mat
array([[0, 1],
[0, 1],
[0, 1],
[0, 0]])
>>> D_mat
array([[1, 1]])
generator_matrix()
cached
Returns the (transform-domain) generator matrix (also known as transfer function matrix) $G(D)$ of the encoder. This is a $k \times n$ array of binary polynomial fractions.
For a convolutional code with matrix of feedforward polynomials $$ P(D) = \begin{bmatrix} p_{0,0}(D) & p_{0,1}(D) & \cdots & p_{0,n-1}(D) \\ p_{1,0}(D) & p_{1,1}(D) & \cdots & p_{1,n-1}(D) \\ \vdots & \vdots & \ddots & \vdots \\ p_{k-1,0}(D) & p_{k-1,1}(D) & \cdots & p_{k-1,n-1}(D) \end{bmatrix}, $$ and vector of feedback polynomials $$ q(D) = \begin{bmatrix} q_0(D) \\ q_1(D) \\ \vdots \\ q_{k-1}(D) \end{bmatrix}, $$ the generator matrix is given by $$ G(D) = \begin{bmatrix} p_{0,0}(D)/q_0(D) & p_{0,1}(D)/q_0(D) & \cdots & p_{0,n-1}(D)/q_0(D) \\ p_{1,0}(D)/q_1(D) & p_{1,1}(D)/q_1(D) & \cdots & p_{1,n-1}(D)/q_1(D) \\ \vdots & \vdots & \ddots & \vdots \\ p_{k-1,0}(D)/q_{k-1}(D) & p_{k-1,1}(D)/q_{k-1}(D) & \cdots & p_{k-1,n-1}(D)/q_{k-1}(D) \end{bmatrix}. $$
Examples:
If matrix of feedforward polynomials is $$ P(D) = \begin{bmatrix} D^4 + D^2 + D + 1 && D^4 + D^3 + 1 \end{bmatrix} $$ and vector of feedback polynomials is $$ q(D) = \begin{bmatrix} D^4 + D^2 + D + 1 \end{bmatrix}, $$ then the generator matrix is given by $$ G(D) = \begin{bmatrix} 1 & \frac{D^4 + D^3 + 1}{D^4 + D^2 + D + 1} \end{bmatrix}. $$
>>> code = komm.ConvolutionalCode(
... feedforward_polynomials=[[0o27, 0o31]],
... feedback_polynomials=[0o27],
... )
>>> for row in code.generator_matrix():
... print("[" + ", ".join(str(x) for x in row) + "]")
[0b1/0b1, 0b11001/0b10111]
finite_state_machine()
cached
Returns the finite-state (Mealy) machine of the encoder.
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]])
is_catastrophic()
cached
Returns whether the encoder is catastrophic. A convolutional encoder is catastrophic if there exists an infinite-weight input sequence that generates a finite-weight output sequence.
Examples:
>>> code = komm.ConvolutionalCode([[0b111, 0b101]])
>>> code.is_catastrophic()
False
>>> code = komm.ConvolutionalCode([[0b11, 0b101]])
>>> code.is_catastrophic()
True
free_distance()
cached
Returns the free distance $d_\mathrm{free}$ of the code. This is equal to the minimum Hamming weight among all possible non-zero output sequences.
Examples:
>>> code = komm.ConvolutionalCode(
... feedforward_polynomials=[[0o31, 0o27, 0o0], [0o0, 0o12, 0o15]],
... )
>>> code.free_distance()
5
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]))