Author: Min Xu <[email protected]>
This program implements both a Convolutional Encoder and a Viterbi Decoder in C++.
Compile:
make
Run:
./viterbi_main <constraint> <polynomial>... <bits>
Example use:
./viterbi_main 3 7 5 0011100001100111111000101100111011
-
It supports reading input from stdin or from commandline arguments. When reading from stdin, it ignores blank lines or comment lines (which start with
#
). -
It supports any number of generator polynomials.
-
It can perform convolutional encoding by providing
--encode
commandline flag. -
It supports a different notation of generator polynomials by providing
--reverse_polynomials
commandline flag.
Here are more options to run the program.
Show help message:
./viterbi_main --help
Read input from stdin:
./viterbi_main [--reverse_polynomials] [--encode]
Input format is:
<constraint> <polynomial>... <bits>
Read input from commandline arguments:
./viterbi_main [--reverse_polynomials] [--encode] <constraint> <polynomial>... <bits>
Flags:
--reverse_polynomials
Reverse polynomials. E.g. 6 (=0b110) becomes 3 (=0b011).
--encode
Do encoding instead of decoding.
Example usage:
./viterbi_main 3 7 5 0011100001100111111000101100111011
./viterbi_main 3 6 5 111011011100101011
./viterbi_main 7 91 121 1010110100001101001000011101
./viterbi_main 7 91 117 121 111100101110001011110101111111001011100111
./viterbi_main --reverse_polynomials 3 3 5 111011011100101011
./viterbi_main --encode 3 7 5 010111001010001
./viterbi_main --encode 3 6 5 1001101
./viterbi_main --encode --reverse_polynomials 3 3 5 1001101
All inputs are validated, and proper error messages will be output.
- The
constraint
should be greater than0
. - A generator polynomial should be greater than
0
and less than1 << constraint
. - The received bit sequence should be consisted with only
0
and1
. - The received bit sequence should be of length
N * <num-of-polynomials>
whereN
is an integer. Otherwise some bits must be missing during transmission. We will fill in appropriate number of trailing zeros.
Run unit test:
make test
Or
make viterbi_test && ./viterbi_test
If the test passes, it will output PASSED
and the end of the output;
otherwise, the test program aborts with assertion error.
There are a few sample cases in the unit test, some are with manually injected bit errors.
It also generates random messages of length 8
, 16
and 32
for several different
convolutional codes and test if they can be properly encoded and decoded.
The code is self-contained, meaning it depends on nothing but the C++ standard library. The purpose is to make it easy to be integrated in any project.