# Generic finite state machine / Viterbi algorithm implementat

Hi everybody,

I finally found some time and ported in gnuradio-2.7
my old ANSI-C implementation of a generic framework
for finite state machines (FSM) and corresponding
sequence detection using the Viterbi algorithm (VA).
The code is more generic (and I guess slower; 117 Kbps
for an 1/2 CC with 128 states on a Pentium 4 @ 2GHz running FC3)
than the one by Phil Karn in that it allows the user to define an
arbitrary FSM through a next-state (NS) function and an output-symbol
(OS) function.

The code decomposes the FSM design from the modulation design,
and from the details of the channel. Similarly, it decomposes the metric
evaluation details from the VA.
Thus, the same code can be used, for instance to simulate/decode
CC, TCM, GMSK, line codes, or even equalize ISI channels.

The basic ingredients of the code are the following:

FSM: is a sync_block,
defined by the 5-tuple (I,S,O,NS,OS)=(input alphabet cardinality, number
of states,
output alphabet cardinality, next-state table, output-symbol table)
that takes one input (short) and produces one
output (short). Eg, for an 1/2 CC with 8 states, the FSM
is defined by (2,8,4,NS,OS) (with the corresponding NS,OS functions).
The input is a short taking values in {0,1} and the
output is a short taking values in {0,1,2,3}.
A variety of FSM definitions are also provided in the form of text files
that are parsed by the python code.

MODULATOR/LOOKUP TABLE: this is essentially a memoryless devise that
translates the FSM output symbols (shorts) into modulated symbols.
Eg, if we want to transmit/simulate 4-PAM modulation (for the FSM
example
mentioned before), then we have a lookup table of
the form [-3 -1 1 3]. If we want to transmit/simulate
biorthogional modulation, the lookup table is
[1 0
0 1
-1 0
0 -1].
This way any modulation (regardless of its dimensionality, and
regardless
of the underlying FSM) is supported. In general, for a D-dimensional
modulation
and a packet of K FSM symbols, this block will generate K x D floats.
This block can be skipped altogether if one wants to simulate directly a
channel acting
directly on the output FSM symbols (eg, O-ary symmetric channel).

Rx PRE-PROCESSING:
a memoryless device that receives the channel outputs and generates a
stream of metrics
for use with the VA. Again, this step hides the channel
details from the VA implementation. For instance, for
an output stream of length K of FSM symbols that belong
to an O-ary alphabet, that are modulated by a D-dimensional modulation,
this block receives K x D floats and generates K x O metrics
(one for each output symbol and for each hypothesized output).
Hard decisions, soft decisions, and any other metric (as long as it is
to be minimized) can be implemented here, without affecting the VA
operation.

VITERBI ALGORITH:
The VA receives K x O metrics and outputs K shorts, representing
the estimate of the input sequence (ie, they belong to the alphabet
{0,1,…,I}).
Starting and ending states can be set as well.
Implementation details: this is a full-record implementation of the VA,
ie,
it receives the entire packet and processes it once in the forward and
once in the backward direction.
(I don’t know if there is interest in coding up also a forward-only
version where a finite traceback buffer is maintained. Maybe this will
be
a good idea for very long packets, as the required memory is on
the order of K x S floats for the full-record VA).

At this point all my files are in my howto_ directory, so I do not
know how to proceed distributing them in the list.
They are available in the following website:
Files:
*.h *.i *.cc (FSM/VA implementation)
*.fsm (various FSM definitions)
*.py (a couple of examples on how the whole thing works)

I am willing to work further on the code and provide additional
improvements if there is enough interest.

Best,
Achilleas

PS: when I find the time, I’ll also port a soft-output version of the
detector,
that outputs reliability information for the input symbols (instead of a
signle sequence
estimate). This can be used to implement decoding of turbo-like codes.