This page contains pointers to several programs in C for simulating encoding and decoding procedures of binary convolutional codes as well as Matlab scripts for simulation and analysis via union bounds. Binary convolutional codes, both nonsystematic codes and systematic (recursive) codes, and their decoding with the Viterbi algorithm, are discussed in Chapter 5 of the book.
In simulating of a given convolutional codes, there are two steps: (1)
Setting up a file with the trellis structure and (2) Viterbi
decoding using this structure.
1. Trellis structure
The two C programs below generate the trellis structure of a binary convolutional encoder. The input to the programs is a file with information of the encoder: The number of output bits per branch, n, the memory of the encoder, m, and the n generator polynomials in octal form. For example, to specify a memory-2 rate-1/2 nonsystematic convolutional code (NSC) with generator polynomials 5,7 (in hexadecimal), the input file contains the lines:
2 2
5
7
The trellis structure is written to an output file that contains the following information, where k=1 in the current versions:
n m
2^m n 2^k
g1
g2
... gn
INIT DATA FINAL OUT[0] OUT[1] ... OUT[n-1]
INIT DATA FINAL OUT[0] OUT[1] ... OUT[n-1]
...
INIT DATA FINAL OUT[0] OUT[1] ... OUT[n-1]
where INIT and FINAL denote the initial and final states, DATA is the
bit associated with the transision and {OUT[0] OUT[1] ... OUT[n-1]} denotes
the output symbols (branch labels).
As an example, the output file for the memory-2 rate-1/2 NSC contains the lines:
2 2
4 2 2
5
7
0 0 0 1 1
0 1 1 -1 -1
1 0 2 1 -1
1 1 3 -1 1
2 0 0 -1 -1
2 1 1 1 1
3 0 2 -1 1
3 1 3 1 -1
The same comments hold for nonrecursive systematic encoders.
Generate trellis data of a memory-m rate-1/n convolutional encoder:
Nonsystematic case
generate_trellis_nsc.c
Generate trellis data of a memory-m rate-1/n convolutional encoder:
Recursive systematic case
generate_trellis_rsc.c
2. Viterbi decoding and puncturing rules
The programs below implement the VD algorithm operating on the trellis
structure of a binary convolutional encoder. Puncturing can be specified
by a rule, which is input to the program via a file containing the lines
PERIOD
bit(1,1) bit(1,2) ... bit(1,PERIOD)
...
bit(n,1) bit(n,2) ... bit(n,PERIOD)
where PERIOD is the puncturing period and n the number of output
symbols per branch. For rate-2/3 punctued code obtained from a rate-1/2
mother code, the file with the puncturing rule
contains the lines:
2
1 0
1 1
Viterbi decoder, hard-decision decoding, BSC with Hamming metric:
NSC
viterbi_binary_hard.c
Viterbi decoder, AWGN channel with correlation metric: NSC
viterbi_binary_nsc.c
Viterbi decoder, AWGN channel with correlation metric: RSC
viterbi_binary_rsc.c
Viterbi decoder, AWGN channel with correlation metric: NSC with puncturing
viterbi_binary_punct.c