## Viterbi algorithm

The Viterbi algorithm is the algorithm for finding the most likely sequence of hidden states, creating the so called path between states. It uses mathematical models of Hidden Markow Model, creating the trellis of possible states. It’s useful especially in decoding convolutional codes, providing the correction of data affected by the noisy communication channel.

The operations made in Viterbi algorithm are the implementation of shift register built with D-type flip-flop. They encode the next bits, based on the state of set of bits. The fact of bits being dependent of other, creates possibility to find the most probable sequence of states, even if there were some bit distortions.

Viterbi decoder implemented in *sdrdab* is uses pure Viterbi algorithm. It has been highly optimized to achieve the shortest execution time available, although it still takes the major of CPU time required by the application.

The `DeViterbi`

method is defined in `DataDecoder`

class. It is used for decoding FIC as well as MSC. On running the application, the `DataDecoder`

constructor executes `DeViterbiInit`

method, which creates the basic vectors (including trellis), each of them not changed through the runtime. They are used as globals by `DeViterbi`

function on every call.

The function’s input data has fixed length depending on decoding FIC or MSC. It is `4*3096`

or `4*10776`

float-values array. However the code itself is also capable of decoding any data which length is a multiple of the trellis length.

The input vector is firstly divided into 4 equal length arrays, each decoded separately. The length of array is always multiple of 8 (symbolising the char) with the 6-bit so-called ‘tail’ added at the end. Each 3096- or 10776-value array is processed by the function separately. The *sdrdab* Viterbi decoder decodes the data, reducing the additional bits to 774b vector of values equal to `0`

or `1`

. The vector is then shortened by tail length and packed into 8-bit char values in descending (from the oldest bit) order. The size of the output vector returned by `DeViterbi`

function is .

### Performance

`DeViterbi`

method consumes the most of the CPU time (64% while not using full power, 44% when does - on stress test) in the *sdrdab*. Although it works in real time on PCs, there is possibility that there won’t be enough computation power in smaller units.

- Implementation of other algorithm, eg. Lazy-Viterbi or BCJR.
- Sppeding-up the Viterbi algorithm, resulting in lowering the accuracy.
- Implementation of depuncturer in
`DeViterbi`

function.

### Bibliography

- Tomasz P. Zieliński, Przemysław Korohoda, Roman Rumian, Cyfrowe przetwarzanie sygnałów w telekomunikacji: podstawy – multimedia – transmisja (Digital Signal Processing in Communications. Fundamentals. Multimedia. Transmission), PWN, 1st ed., Warsaw 2014, pp. 825-830