In this page pointers are presented to programs in C/C++ for simulating
iterative decoding algorithms. These include programs to compute constellation-constrainted
capacity. The design of interleavers is an important issue, particularly
with short frame lengths. Computer programs to construct several types
of interleavers are given. These and other issues are discussed in Chapter
8 of the book!
TURBO CODES
In the design and implementation of a turbo code in software, there
are two main issues:
1. Construction of an interleaver
2. Simulation of iterative decoding
RANDOM interleaver
The programs output the interleaver array as one integer per row (i.e.,
separated by CR characters). Other types of interleavers exist, but the
above classes should always yield competitive alternatives. The programs
are well documented.
2. Iterative decoding
MAP decoding of a parallel concatenated (turbo) convolutional code:
Rate 1/3
turbo.cpp random.cpp
random.h
Simulation of a binary rate-1/3 turbo code with two identical rate-1/2 component recursive convolutional encoders. The memory of the encoders can be selected betwen 2, 3 and 4, corresponding to 4, 8 and 16 state trellises respectively. Files turbo_MAP.cpp and random.cpp must be compiled together, with the "gcc" command in a unix-like environment (or equivalent in other OS) as
gcc -O2 turbo_MAP.cpp random.cpp -lm
NOTE: This version of the program does not consider tail bits
to terminate the trellis. As a result, performance will be worse than turbo
codes with tail bits, specially with short interleaver lengths. The original
program was written by Mathys Walma in 1998. Please refere to the original
README
file. Many changes to the program were necessary to make it more compatible
with the style of the programs in this site.
MAP decoding of a parallel concatenated (turbo) convolutional code:
Puncturing and rate 1/2
turbo_punc.cpp random.cpp
random.h
These programs are used for simulation of a rate-1/2 punctured turbo code. A puncturing rule is applied in the branch metric (gamma) computation stage, very much in the same way as in the convolutional code case. In this version, the puncturing rule is hard-coded in the program, but it should be easy to specified it in a file, just as in the case of binary punctured convolutional codes.
All other comments made for the rate-1/3 turbo code above are pertinent
to the punctured rate-1/2 turbo code.
LDPC CODES
Below are iterative soft-decision (belief propagation) decoding and hard-decision decoding algorithms for the important family of low-density parity-check codes. Since these algorithms can be applied to any linear code (with a low-density parity check matrix), a simplification is made in that the all-zero codeword is always transmitted. This simplifies programming enormously.
The iterative decoding algorithms need the parity-check matrix as an
input. The format of the files specifying the structure of these matrices
(or the Tanner graphs) is the same as that used by David MacKay, that is,
the "alist" (adjacency list) format. Please refer to his
web site for more information, some C source code, and to pick up some
matrices for your simulations. Below are two examples of parity-check matrix
file definition, for Gallager's (20,5) code and a finite (projective) geometry
cyclic (273,191,17) code, respectively:
gallager.20.4.3
DSC.273.17.17
NOTE: The three numbers in suffix of a file name above are
N.J.K, where N=length, J=maximum degree of bit nodes and K=maximum degree
of check nodes.
Belief-propagation decoding algorithm: Probabilistic decoding
pearl.c
The algorithm works directly with probabilities. In terms of
numerical precision, it is the most stable BP decoder, although it is very
intensive in terms of exp() computations.
Belief-propagation decoding algorithm: Logarithm domain
log_pearl.c
This version of BP algorithm is obtained from the probabilistic one
by straight log-domain translation. No approximation (table) used.
This results in log(exp(a)+/-exp(b)) computations that are even more intensive
than in pearl.c...
Belief-propagation decoding algorithm: Log-likelihood domain
llr_pearl.c
This version utilizes log-likelihood ratios. This results in
much improvement in terms of speed compared to log_pearl.c with practically
the same numerical precision as pearl.c. It can be further improved by
the use of a look-up table to avoid exp() computations, as mentioned in
the book.
Bit-flipping hard-decision decoding algorithm
bitf.c
Gallager's iterative bit-flipping decoding of linear block codes. The
user can specify a threshold on the number of unsatisfied parity checks
needed in order to flip (or complement the value of) a bit.
The Tanner graph of a binary cyclic code: tannercyclic.m
The Tanner graph of a binary LDPC code: tanner_LDPC.m with alist2sparse.m (Igor Kozintsev, 1999)
Capacity
Both turbo codes and LDPC codes are so-called capacity achieving. Therefore,
there is an interest in knowing the theoretical limits of transmission when
using a particular modulation scheme. This is called constellation-constrainted
capacity. Below are some programs that are useful in computing this capacity
compared to the ultimate Shannon capacity of an AWGN channel.