komm.MealyMachine

Finite-state Mealy machine. It is defined by a set of states $\mathcal{S}$, an input alphabet $\mathcal{X}$, an output alphabet $\mathcal{Y}$, a transition function $T : \mathcal{S} \times \mathcal{X} \to \mathcal{S}$, and an output function $G : \mathcal{S} \times \mathcal{X} \to \mathcal{Y}$. Here, for simplicity, the set of states, the input alphabet, and the output alphabet are taken as $\mathcal{S} = [0 : |\mathcal{S}|)$, $\mathcal{X} = [0 : |\mathcal{X}|)$, and $\mathcal{Y} = [0 : |\mathcal{Y}|)$, respectively. more details, see Wikipedia: Mealy machine.

Parameters:

transitions (ArrayLike) –

The matrix of transitions of the machine, of shape $|\mathcal{S}| \times |\mathcal{X}|$. The element in row $s \in \mathcal{S}$ and column $x \in \mathcal{X}$ should be $T(s, x) \in \mathcal{S}$, that is, the next state of the machine given that the current state is $s$ and the input is $x$.
outputs (ArrayLike) –

The matrix of outputs of the machine, of shape $|\mathcal{S}| \times |\mathcal{X}|$. The element in row $s \in \mathcal{S}$ and column $x \in \mathcal{X}$ should be $G(s, x) \in \mathcal{Y}$, that is, the output of the machine given that the current state is $s$ and the input is $x$.

Examples:

Consider the finite-state Mealy machine whose state diagram depicted in the figure below.

It has set of states $\mathcal{S} = \{ 0, 1, 2, 3 \}$, input alphabet $\mathcal{X} = \{ 0, 1 \}$, output alphabet $\mathcal{Y} = \{ 0, 1, 2, 3 \}$. The transition function $T$ and output function $G$ are given by the table below.

State $s$	Input $x$	Transition $T(s, x)$	Output $G(s, x)$
$0$	$0$	$0$	$0$
$0$	$1$	$1$	$3$
$1$	$0$	$2$	$1$
$1$	$1$	$3$	$2$
$2$	$0$	$0$	$3$
$2$	$1$	$1$	$0$
$3$	$0$	$2$	$2$
$3$	$1$	$3$	$1$

>>> machine = komm.MealyMachine(
...     transitions=[[0, 1], [2, 3], [0, 1], [2, 3]],
...     outputs=[[0, 3], [1, 2], [3, 0], [2, 1]],
... )

`num_statesint` `cached` `property`

The number of states of the machine.

Examples:

>>> machine = komm.MealyMachine(
...     transitions=[[0, 1], [2, 3], [0, 1], [2, 3]],
...     outputs=[[0, 3], [1, 2], [3, 0], [2, 1]],
... )
>>> machine.num_states
4

`num_input_symbolsint` `cached` `property`

The size (cardinality) of the input alphabet $\mathcal{X}$.

Examples:

>>> machine = komm.MealyMachine(
...     transitions=[[0, 1], [2, 3], [0, 1], [2, 3]],
...     outputs=[[0, 3], [1, 2], [3, 0], [2, 1]],
... )
>>> machine.num_input_symbols
2

`num_output_symbolsint` `cached` `property`

The size (cardinality) of the output alphabet $\mathcal{Y}$.

Examples:

>>> machine = komm.MealyMachine(
...     transitions=[[0, 1], [2, 3], [0, 1], [2, 3]],
...     outputs=[[0, 3], [1, 2], [3, 0], [2, 1]],
... )
>>> machine.num_output_symbols
4

`input_edgesNDArray[integer]` `cached` `property`

The matrix of input edges of the machine. It has shape $|\mathcal{S}| \times |\mathcal{S}|$. If there is an edge from $s_0 \in \mathcal{S}$ to $s_1 \in \mathcal{S}$, then the element in row $s_0$ and column $s_1$ is the input associated with that edge (an element of $\mathcal{X}$); if there is no such edge, then the element is $-1$.

Examples:

>>> machine = komm.MealyMachine(
...     transitions=[[0, 1], [2, 3], [0, 1], [2, 3]],
...     outputs=[[0, 3], [1, 2], [3, 0], [2, 1]],
... )
>>> machine.input_edges
array([[ 0,  1, -1, -1],
       [-1, -1,  0,  1],
       [ 0,  1, -1, -1],
       [-1, -1,  0,  1]])

`output_edgesNDArray[integer]` `cached` `property`

The matrix of output edges of the machine. It has shape $|\mathcal{S}| \times |\mathcal{S}|$. If there is an edge from $s_0 \in \mathcal{S}$ to $s_1 \in \mathcal{S}$, then the element in row $s_0$ and column $s_1$ is the output associated with that edge (an element of $\mathcal{Y}$); if there is no such edge, then the element is $-1$.

Examples:

>>> machine = komm.MealyMachine(
...     transitions=[[0, 1], [2, 3], [0, 1], [2, 3]],
...     outputs=[[0, 3], [1, 2], [3, 0], [2, 1]],
... )
>>> machine.output_edges
array([[ 0,  3, -1, -1],
       [-1, -1,  1,  2],
       [ 3,  0, -1, -1],
       [-1, -1,  2,  1]])

`process()`

Returns the output sequence corresponding to a given input sequence. It assumes the machine starts at a given initial state $s_\mathrm{i}$. The input sequence and the output sequence are denoted by $\mathbf{x} = (x_0, x_1, \ldots, x_{L-1}) \in \mathcal{X}^L$ and $\mathbf{y} = (y_0, y_1, \ldots, y_{L-1}) \in \mathcal{Y}^L$, respectively.

Parameters:

input (ArrayLike) –

The input sequence $\mathbf{x} \in \mathcal{X}^L$. It should be a 1D-array with elements in $\mathcal{X}$.
initial_state (int) –

The initial state $s_\mathrm{i}$ of the machine. Should be an integer in $\mathcal{S}$.

Returns:

output (NDArray[integer]) –

The output sequence $\mathbf{y} \in \mathcal{Y}^L$ corresponding to input, assuming the machine starts at the state given by initial_state. It is a 1D-array with elements in $\mathcal{Y}$.
final_state (int) –

The final state $s_\mathrm{f}$ of the machine. It is an integer in $\mathcal{S}$.

Examples:

>>> machine = komm.MealyMachine(
...     transitions=[[0, 1], [2, 3], [0, 1], [2, 3]],
...     outputs=[[0, 3], [1, 2], [3, 0], [2, 1]],
... )
>>> input, initial_state = [1, 1, 0, 1, 0], 0
>>> output, final_state = machine.process(input, initial_state)
>>> output
array([3, 2, 2, 0, 1])
>>> final_state
2

`viterbi()`

Applies the Viterbi algorithm on a given observed sequence. The Viterbi algorithm finds the most probable input sequence $\hat{\mathbf{x}}(s) \in \mathcal{X}^L$ ending in state $s$, for all $s \in \mathcal{S}$, given an observed sequence $\mathbf{z} \in \mathcal{Z}^L$. It is assumed uniform input priors. See LC04, Sec. 12.1.

Parameters:

observed (Sequence[Z] | NDArray[Any]) –

The observed sequence $\mathbf{z} \in \mathcal{Z}^L$.
metric_function (MetricFunction[Z]) –

The metric function $\mathcal{Y} \times \mathcal{Z} \to \mathbb{R}$.
initial_metrics (ArrayLike | None) –

The initial metrics for each state. It must be a 1D-array of length $|\mathcal{S}|$. The default value is 0.0 for all states.

Returns:

input_hat (NDArray[integer]) –

The most probable input sequence $\hat{\mathbf{x}}(s) \in \mathcal{X}^L$ ending in state $s$, for all $s \in \mathcal{S}$. It is a 2D-array of shape $L \times |\mathcal{S}|$, in which column $s$ is equal to $\hat{\mathbf{x}}(s)$.
final_metrics (NDArray[floating]) –

The final metrics for each state. It is a 1D-array of length $|\mathcal{S}|$.

`viterbi_streaming()`

Applies the streaming version of the Viterbi algorithm on a given observed sequence. The path memory (or traceback length) is denoted by $\tau$. It chooses the survivor with best metric and selects the information block on this path. See LC04, Sec. 12.3.

Parameters:

observed (Sequence[Z] | NDArray[Any]) –

The observed sequence $\mathbf{z} \in \mathcal{Z}^L$.
metric_function (MetricFunction[Z]) –

The metric function $\mathcal{Y} \times \mathcal{Z} \to \mathbb{R}$.
memory (MetricMemory) –

The metrics for each state. It must be a dictionary containing two keys: 'paths', a 2D-array of integers of shape $|\mathcal{S}| \times (\tau + 1)$; and 'metrics', a 2D-array of floats of shape $|\mathcal{S}| \times (\tau + 1)$. This dictionary is updated in-place by this method.

Returns:

input_hat (NDArray[integer]) –

The most probable input sequence $\hat{\mathbf{x}} \in \mathcal{X}^L$

`forward_backward()`

Applies the forward-backward algorithm on a given observed sequence. The forward-backward algorithm computes the posterior pmf of each input $x_0, x_1, \ldots, x_{L-1} \in \mathcal{X}$ given an observed sequence $\mathbf{z} = (z_0, z_1, \ldots, z_{L-1}) \in \mathcal{Z}^L$. The prior pmf of each input may also be provided. See LC04, 12.6.

Parameters:

observed (Sequence[Z] | NDArray[Any]) –

The observed sequence $\mathbf{z} \in \mathcal{Z}^L$.
metric_function (MetricFunction[Z]) –

The metric function $\mathcal{Y} \times \mathcal{Z} \to \mathbb{R}$.
input_priors (ArrayLike | None) –

The prior pmf of each input, of shape $L \times |\mathcal{X}|$. The element in row $t \in [0 : L)$ and column $x \in \mathcal{X}$ should be $p(x_t = x)$. The default value yields uniform priors.
initial_state_distribution (ArrayLike | None) –

The pmf of the initial state of the machine. It must be a 1D-array of length $|\mathcal{S}|$. The default value is uniform over all states.
final_state_distribution (ArrayLike | None) –

The pmf of the final state of the machine. It must be a 1D-array of length $|\mathcal{S}|$. The default value is uniform over all states.

Returns:

input_posteriors (NDArray[floating]) –

The posterior pmf of each input, given the observed sequence, of shape $L \times |\mathcal{X}|$. The element in row $t \in [0 : L)$ and column $x \in \mathcal{X}$ is $p(x_t = x \mid \mathbf{z})$.

State $s$	Input $x$	Transition $T(s, x)$	Output $G(s, x)$
$0$	$0$	$0$	$0$
$0$	$1$	$1$	$3$
$1$	$0$	$2$	$1$
$1$	$1$	$3$	$2$
$2$	$0$	$0$	$3$
$2$	$1$	$1$	$0$
$3$	$0$	$2$	$2$
$3$	$1$	$3$	$1$

State $s$	Input $x$	Transition $T(s, x)$	Output $G(s, x)$
$0$	$0$	$0$	$0$
$0$	$1$	$1$	$3$
$1$	$0$	$2$	$1$
$1$	$1$	$3$	$2$
$2$	$0$	$0$	$3$
$2$	$1$	$1$	$0$
$3$	$0$	$2$	$2$
$3$	$1$	$3$	$1$

komm.MealyMachine

num_states int cached property

num_input_symbols int cached property

num_output_symbols int cached property

input_edges NDArray[integer] cached property

output_edges NDArray[integer] cached property

process()

viterbi()

viterbi_streaming()

forward_backward()

`num_statesint` `cached` `property`

`num_input_symbolsint` `cached` `property`

`num_output_symbolsint` `cached` `property`

`input_edgesNDArray[integer]` `cached` `property`

`output_edgesNDArray[integer]` `cached` `property`

`process()`

`viterbi()`

`viterbi_streaming()`

`forward_backward()`

State $s$	Input $x$	Transition $T(s, x)$	Output $G(s, x)$
$0$	$0$	$0$	$0$
$0$	$1$	$1$	$3$
$1$	$0$	$2$	$1$
$1$	$1$	$3$	$2$
$2$	$0$	$0$	$3$
$2$	$1$	$1$	$0$
$3$	$0$	$2$	$2$
$3$	$1$	$3$	$1$