Optimization of an decoding algorithm for RMcodes based on concatenation
ReedMuller 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 ReedMuller codes, considering its speed and ability to correct errors, is the GMCalgorithm. But because of its recursive structure, the algorithm is hard to implement into hardware.The goal of this thesis is to transform the GMCalgorithm 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 GMCalgorithm only works for ReedMuller codes, because of the possibility to construct them as generalized concatenate codes. Furthermore I will explain different ways on how to construct ReedMuller 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 GMCalgorithm, I start of by transforming the recursive structure into a structure based on forloops. Based on this new iterative procedure, I found a way to write the GMCalgorithm as a finite state machine. The transition of the states is managed by different counters. A ReedMuller 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 GMCalgorithm for ReedMuller 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.
Optimization of an decoding algorithm for RMcodes based on concatenation
Supervisor(s): 
Ludwig Kürzinger 
Status: 
finished 
Topic: 
Monitoring (VMI etc.) 
Author: 
Lukas Sandmeir 
Submission: 
20170117 
Type of Thesis: 
Bachelorthesis

Proof of Concept 
No 
Thesis topic in cooperation with the Fraunhofer Institute for Applied and Integrated Security AISEC, Garching

Astract:ReedMuller 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 ReedMuller codes, considering its speed and ability to correct errors, is the GMCalgorithm. But because of its recursive structure, the algorithm is hard to implement into hardware.The goal of this thesis is to transform the GMCalgorithm 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 GMCalgorithm only works for ReedMuller codes, because of the possibility to construct them as generalized concatenate codes. Furthermore I will explain different ways on how to construct ReedMuller 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 GMCalgorithm, I start of by transforming the recursive structure into a structure based on forloops. Based on this new iterative procedure, I found a way to write the GMCalgorithm as a finite state machine. The transition of the states is managed by different counters. A ReedMuller 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 GMCalgorithm for ReedMuller 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. 