komm.FiniteStateMachine

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

For example, consider the finite-state 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 \}$, and transition function $T$ given by the table below.

State	Input	Next state	Output
$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$

__init__()

Constructor for the class.

Parameters:

• next_states (Array2D[int]) –

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

• outputs (Array2D[int]) –

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

Examples:

>>> fsm = komm.FiniteStateMachine(next_states=[[0,1], [2,3], [0,1], [2,3]], outputs=[[0,3], [1,2], [3,0], [2,1]])

num_states property

The number of states of the machine.

num_input_symbols property

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

num_output_symbols property

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

next_states property

The matrix of next states of the machine. It has shape $|\mathcal{S}| \times |\mathcal{X}|$. The element in row $s$ and column $x$ is the next state of the machine (an element in $\mathcal{S}$), given that the current state is $s \in \mathcal{S}$ and the input is $x \in \mathcal{X}$.

outputs property

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

input_edges 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:

>>> fsm = komm.FiniteStateMachine(next_states=[[0,1], [2,3], [0,1], [2,3]], outputs=[[0,3], [1,2], [3,0], [2,1]])
>>> fsm.input_edges
array([[ 0,  1, -1, -1],
       [-1, -1,  0,  1],
       [ 0,  1, -1, -1],
       [-1, -1,  0,  1]])

output_edges 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:

>>> fsm = komm.FiniteStateMachine(next_states=[[0,1], [2,3], [0,1], [2,3]], outputs=[[0,3], [1,2], [3,0], [2,1]])
>>> fsm.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_sequence (Array1D[int]) –

  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_sequence (Array1D[int]) –

  The output sequence $\mathbf{y} \in \mathcal{Y}^L$ corresponding to input_sequence, 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:

>>> fsm = komm.FiniteStateMachine(next_states=[[0,1], [2,3], [0,1], [2,3]], outputs=[[0,3], [1,2], [3,0], [2,1]])
>>> input_sequence, initial_state = [1, 1, 0, 1, 0], 0
>>> output_sequence, final_state = fsm.process(input_sequence, initial_state)
>>> output_sequence
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 (Array1D) –

  The observed sequence $\mathbf{z} \in \mathcal{Z}^L$.

• metric_function (function) –

  The metric function $\mathcal{Y} \times \mathcal{Z} \to \mathbb{R}$.

• initial_metrics (Optional[Array1D[float]]) –

  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_sequences_hat (Array2D[int]) –

  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 (Array1D[float]) –

  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 (Array1D) –

  The observed sequence $\mathbf{z} \in \mathcal{Z}^L$.

• metric_function (function) –

  The metric function $\mathcal{Y} \times \mathcal{Z} \to \mathbb{R}$.

• memory (dict) –

  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_sequence_hat (Array1D[int]) –

  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 (Array1D) –

  The observed sequence $\mathbf{z} \in \mathcal{Z}^L$.

• metric_function (function) –

  The metric function $\mathcal{Y} \times \mathcal{Z} \to \mathbb{R}$.

• input_priors (Optional[Array2D[float]]) –

  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 (Optional[Array1D[float]]) –

  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 (Optional[Array1D[float]]) –

  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 (Array2D[float]) –

  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})$.