Viterbi Decoder Model

Python model of a Viterbi decoder.

Original author: David Banas <capn.freako@gmail.com>

Original date: June 12, 2025

Copyright (c) 2025 David Banas; all rights reserved World wide.

To use this module to construct your own Viterbi decoder, import the ViterbiDecoder class as follows:

from pybert.models.viterbi import ViterbiDecoder

and follow the example given by the ViterbiDecoder_ISI class definition, below.

class pybert.models.viterbi.ViterbiDecoder[source]

Bases: ABC, Generic[S, X]

Abstract definition of a Viterbi decoder.

decode(samps: list[X], dbg_dict: dict[str, Any] | None = None) → list[int][source]

Use trellis to decode a list of observations.

Parameters:

samps – List of observations.

Keyword Arguments:

dbg_dict – Dictionary for stashing debugging info. Default: None

Returns:

Maximum likelihood sequence estimation (MLSE) of state indices.

abstractmethod expectation(s: int) → Any[source]

Expected observation for state at index s.

log(msg: str)[source]

Debugging logger.

abstractmethod prob(s: int, x: X) → float[source]

Probability of state at index s given observation x.

Notes

  1. This is sometimes referred to as the “emission probability” in the literature.

step_trellis(x: X, priming: bool = False) → int[source]

Shift the trellis one column left, using the given observation sample.

Parameters:

x – The new observation sample.

Keyword Arguments:

priming – Don’t perform backtrace when True. Default: False

Returns:

The decided state index of the exiting (i.e. - leftmost) column.

log_msg: str = ''
property path: list[int]

Maximum likelihood forward path through the trellis.

Notes

1. First element in returned list corresponds to the time just before the first trellis column. 2. The decided state of the final trellis column is not included.

abstract property states: list[S]

List of all possible states.

abstract property trans: numpy.typing.NDArray.~Real

State transition probability matrix.

Notes

  1. Row/column ordinates match those of states.

abstract property trellis: list[list[tuple[float, int]]]

Current trellis matrix.

Notes

  1. Length of returned list gives trellis depth.

  2. Length of all inner lists should equal len(states).

  3. Each location in the trellis matrix contains the probability and previous state index for the corresponding state.

class pybert.models.viterbi.ViterbiDecoder_ISI(L: int, N: int, sigma: float, pulse_resp_samps: numpy.typing.NDArray.~Real)[source]

Bases: ViterbiDecoder[tuple[list[int], float], float]

Viterbi decoder using ISI to define observation probabilities.

Parameters:

  • L – Number of symbol voltage levels.

  • N – Number of symbols per state.

  • sigma – Standard deviation of Gaussian voltage noise (V).

  • pulse_resp_samps – Upstream channel pulse response samples, one per UI, beginning with cursor (V). (Must have length >= N!)

Notes

1. The symbol voltages are assumed uniformly distributed. (This will require modification for photonics!)

expectation(s: int) → float[source]

Expected observation in state s.