Convolutional Codes and the Viterbi Algorithm

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

Bounds on the performance of two binary rate-1/2 convolyutional codes over a BSC:
bound_BSC_R12_K3_K4_hard.m

VO and JZ bounds on performance of a memory-1 rate-1/2 convolutional code over an AWGN channel:
bound_AWGN_R12_K2_EbNo.m

Simulation of a memory-1 rate-1/2 convolutional code over an AWGN channel:
AWGN_conv_R12_K2.m

VO and JZ bounds on performance of a memory-2 rate-1/3 convolutional code over an AWGN channel:
bound_AWGN_R13_K3_EbNo.m

Simulation of a memory-2 rate-1/3 convolutional code over an AWGN channel:
AWGN_conv_R13_K3.m

Viterbi decoding of a memory-2 rate-1/2 convolutional code over an AWGN channel - Hard decisions:
AWGN_conv_R12_K3_hard.m

Viterbi decoding of a memory-2 rate-1/2 convolutional code over an AWGN channel - Soft decisions:
AWGN_conv_R12_K3.m

Bound on the performance of a memory-2 rate-1/2 convolutional code over an AWGN channel with soft-decision decoding:
bound_AWGN_R12_K3.m

Bound on the performance of a memory-2 rate-1/2 convolutional code over an AWGN channel with hard-decision decoding:
bound_AWGN_R12_K3_hard.m