[Back]

P. Grabenweger:
"Mathematical aspects of linear block codes";
Supervisor: J. Melenk; Institut für Analysis und Scientific Computing, 2021; final examination: 2021-09-09.

Linear block codes are used in communications engineering for the purpose of channel coding, which allows detection and correction of transmission errors of digital data communicated over interference-afflicted transmission channels. In this work, the meaning of the term of code rate is explained first for general block codes over finite fields. Afterwards, considering linear block codes, their representation, cardinality and code rate as well as the relationship between generator matrix and (non-binary) parity check matrix are examined. The remaining part of this work is dedicated to two particular subclasses of binary linear block codes, the low-density parity-check (LDPC) codes and the multi-edge type (MET) LDPC codes, which are a generalisation of LDPC codes. In applications of these codes for channel coding, binary-input memoryless symmetric channels (BMS channels) play an important role. The belief propagation algorithm, which can be used for receiver side decoding of LDPC codes and MET-LDPC codes after their transmission over BMS channels, is illustrated. For the stochastic analysis of the behaviour of the belief propagation algorithm, log-likelihood ratio (LLR) distributions and the density evolution algorithm are used. The theory of LLR distributions is build up in the context of measurement and probability theory and of Lebesgue integration, where in particular a specific symmetry property, two kinds of convolution operations and some linear functionals are considered. Also some theoretically significant results for BMS channels are shown. Subsequently, the density evolution algorithm for LDPC codes and MET-LDPC codes is described. Finally, a quantisation method for the efficient approximate numerical implementation of the density evolution algorithm for MET-LDPC codes is considered and improved, and the results of a numerical example are presented.

linear block codes; error correction; density evolution algorithm