TD 7, Concatenated Codes

Introduction to Information Theory

February 17, 2022

1 Introduction : Decoding simulation of a linear code

When it comes to assess the performances of a linear code, it is in general not necessary to encode it. Most decoding algorithms display the same performances regardless of the codeword that is sent. In such a case, one can assume that the zero codeword was sent. It just remains to draw at random errors according to the channel model and to compute how many times the decoding algorithm will recover the zero codeword. This simplified procedure presents several advantages

it is not necessary to implement the encoder

it is not always necessary to implement the whole decoder, one just has to check whether a given error is decoded to zero.

2 Syndrome decoding of the Golay code

The syndrome decoder consists in choosing for each possible syndrome a word of minimum weight which has this syndrome. You will have to implement this decoder for the Golay code G₂₄ [24,12,8] which has the following generator matrix

    static int [] G = {
        0xa3b001, 0xc76002, 0x8ed004, 0x9da008, 0xbb4010, 0xf68020,
        0xed1040, 0xda3080, 0xb47100, 0xe8e200, 0xd1d400, 0x7ff800
    };

It will be useful to notice that this generator matrix is also a parity-check matrix : each row of G is also in the kernel of G. The main steps you will have to implement are given by

INIT: construction of the lookup table: for each syndrome s store in the table the word e_s of minimum Hamming weight which has this syndrome ;
for an error e that we want to decode, determine its syndrome s ;
return e−e_s.

Note that we always work in the code space F₂²⁴ (three bytes stored into an int), and never in the message space F₂¹². You can use the following java class Golay.java .

3 Concatenated codes

We are going to consider the following concatenated code

Inner code : the Golay code
Outer code : a q-ary Reed-Solomon code with q=2¹², of length n<q, of minimum distance d<n (dimension k=n−d+1). We choose n=255, d=33 (it permits to correct 16 errors).

For the inner Golay code, calling Golay.decoder(y) returns

(true, w) if y is decoded into 0 and is at distance w from the code,
(false, w) if y is decoded into x != 0 and at distance w from the code,

In the case of a concatenated code, we will prefer to declare that decoding the inner code leads to an erasure rather than producing an error which might be more harmful.

A threshold e will be defined: if there are more than e errors we will decide that the symbol gets erased.

A Reed-Solomon code can correct a configuration of t errors and s erasures if and only if 2t+s<d.

4 The program

takes as arguments

the binary crossover probability
the erasure threshold
the number of decoding attemps that that have to be generated

The outer code is a [255,223,33] Reed-Solomon code. The program will be used to answer the following questions :

give an estimation of the error probability of decoding for various crossover probabilities.
What is the best threshold for decoding the inner code ?

This document was translated from L^AT_EX by H^EV^EA.