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$ |
Parameters:
-
next_states(ArrayLike) –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(ArrayLike) –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: int cached property
The number of states of the machine.
num_input_symbols: int cached property
The size (cardinality) of the input alphabet $\mathcal{X}$.
num_output_symbols: int cached property
The size (cardinality) of the output alphabet $\mathcal{Y}$.
input_edges: npt.NDArray[np.integer] 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: npt.NDArray[np.integer] 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(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_sequence(NDArray[integer]) –The output sequence $\mathbf{y} \in \mathcal{Y}^L$ corresponding to
input_sequence, assuming the machine starts at the state given byinitial_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
np.int64(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(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.0for all states.
Returns:
-
input_sequences_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(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_sequence_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(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})$.