Optimization of an decoding algorithm for RM-codes based on concatenation

Astract:

Reed-Muller codes are a family of error correcting codes, which are used in the context of embedded systems. The advantage of these codes is, that they are easy to construct, what makes them compact and efficient. The decoding algorithm, which is best for decoding Reed-Muller codes, considering its speed and ability to correct errors, is the GMC-algorithm. But because of its recursive structure, the algorithm is hard to implement into hardware.The goal of this thesis is to transform the GMC-algorithm in a way, that it doesn’t need recursion anymore. For that I start with some basics and notations, that we need for the following chapters. Afterwards I give a brief overview on constructing big codes with the method of generalized concatenate codes. The GMC-algorithm only works for Reed-Muller codes, because of the possibility to construct them as generalized concatenate codes. Furthermore I will explain different ways on how to construct Reed-Muller codes, followed by a chapter about how to decode them. I will not only show how the GMC- algorithm works, but I will also give a short introduction on two other decoding methods.To find a concept for a hardware implementation of the GMC-algorithm, I start of by transforming the recursive structure into a structure based on for-loops. Based on this new iterative procedure, I found a way to write the GMC-algorithm as a finite state machine. The transition of the states is managed by different counters. A Reed-Muller code is defined by the parameters r and m. The iterative procedure as well as the finite state machine are working for arbitrary values for m, but only for r = 2. At the end of the chapter I will give two hypotheses on how to generalize the concept, so that it works for arbitrary values for r.This thesis provides a working concept on how to implement the GMC-algorithm for Reed-Muller codes with r = 2 without using recursion. Furthermore there are proof of concept implementations for different parts of the thesis in the appendix, written in python code. You can use them to see and test for yourself, that the different concepts are actually working.