viterbi

This is a small convolutional encoder and Viterbi decoder written just for fun and for learning purposes.

Usage

Include the header file viterbi.h in your C or C++ program:

#include "viterbi.h"

The header file already provides a good documentation of the functions and data structures. So here is a brief introduction.

General

Bit sequences

Bit sequences are represented as strings, e.g. "010011"

Encoders

The essence of convolutional codes is a shift register into which bits of a bit sequence are being pushed sequentially and one at a time.
An Encoder selects certain bits defined by the user from the shift register and performs a logical operation on them. The bits from the encoder are then being concatenated into a new string which is the current convolutional code.
Therefore, an encoder is defined by

• A logical operation
• A series of bit indexes

Trellis

A Trellis is a diagram that shows to which state a certain state transitions if a 0 or a 1 is being push into the shift register and which resulting convolutional code it outputs during a transition.
Therefore, a trellis is defined by

• The number of bits in a state
• A series of encoders (The number of encoders determines the length of the convolutional code being outputted)
• A push function (This determines whether the bits are being pushed into the shift array from the left-hand side (most significant bit) or from the right-hand side (least significant bit)

Getting started

In order to perform convolutional encoding and Viterbi decoding, you first have to do the following things in order:

1. Create a series of encoders
2. Create and initialize a trellis

These steps are also described and illustrated in the file example.c.

Encoder

First, create an array of encoders:

encoder encs [<number of encoders>];

Then initialize them using the function create_encoder.

Return type	void
Parameters	encoder* enc: Array of encoders int operation: Logical operation (defined in enum operations) int num_bits: Number of bit indexes ...: As many bit indexes as int as you have defined in num_bits

Trellis

Then we can create a trellis:

trellis t;

Now we can use the function create_trellis to initialize the trellis.

Return type	void
Parameters	trellis* tr: Pointer to the trellis int num_bits: Number of bits in the shift register encoder* enc: Pointer to the array of encoders int num_encoders: Array length of enc int (*push_bit_func)(char*, unsigned int): Pointer to the push bit function

Convolutional encoding

You can encode a bit sequence using the function convolutional_encode.

Return type	char*: Encoded bit sequence
Parameters	char* seq: Raw bit sequence to encode encoder* enc: Array of encoders int num_encoders: Number of encoders in the array enc int state_length: Number of bits in the shift register int(*push_bit_func)(char*, unsigned int): Pointer to the push bit function

Viterbi decoding

You can decode a bit sequence using the function viterbi_decode.

Return type	viterbi_result*: Decoded bit sequence
Parameters	char* code: Convolutional code trellis* tr: Pointer to the trellis

The function viterbi_decode does not only return the decoded bit sequence, but also the weight of the last node in the Viterbi decoder grid. This indicates if the convolutional code contains errors and if the decoded sequence is correct:

Weight	Meaning
= 0	The convolutional code does not contain errors and the decoded bit sequence is correct with a certainty of 100 %
> 0	The convolutional code contains errors and the certainty of the decoded bit sequence being correct decreases with the weight increasing