The Karl H. Ditze Foundation was founded in 1979 to support universities in Hamburg as well as community projects. The Karl H. Ditze award for excellent bachelor theses, master theses and dissertations has been granted annually since the year 2000.
About the thesis
Digital Communication systems are omnipresent in today's world and appear in all kinds of shapes and applications. However, in all practical systems, the data transmission is disturbed for example by noise or interference in wireless communication systems. In order to protect the sent data from these perturbations channel codes are used.
Low-Density Parity-Check (LDPC) codes have become the state-of-the-art in modern systems such as 5G and WiFi. LDPC codes are defined by a parity-check matrix, or equivalently by a so-called Tanner graph. In practical receivers, LDPC codes are decoded by performing an algorithm called message passing over this Tanner graph. While decoding LDPC codes via message passing can achieve close to optimal performance in some cases, it is well-known that short cycles in the Tanner graph degrade the performance significantly.
The parity check matrix is not unique for a given LDPC code, meaning it is possible to construct different Tanner graphs and therefore decoding algorithms for the same code. In his master thesis, Jannik Jacobsen investigated how to find Tanner graphs with good properties, in particular few short cycles, to improve the performance of practical codes. For this, he used optimization approaches based on simulated annealing.
The thesis is built on a strong mathematical foundation in graph theory, randomized algorithms and optimization of NP-hard problems. Moreover, different ways of exploiting the newly constructed graphs in the decoder are discussed and evaluated by bit error rate simulations. The results show that it can be beneficial to use multiple different equivalent Tanner graphs within a single decoder which are exchanged after a few iterations. Further, decoding a received codeword multiple times using different Tanner graphs can also improve the bit error rate.
Since the optimization of Tanner graphs is a challenging and computationally demanding problem, the work focused on LDPC codes with a relatively short block length. Future work could include applying the optimization approaches to state-of-the-art codes, which typically have much longer block lengths.
