Mathematische Aspekte von linearen Block-Codes

Abstract

In der Nachrichtentechnik werden lineare Block-Codes zur Kanalkodierung eingesetzt, die zur Erkennung und Korrektur von Übertragungsfehlern bei der Übermittlung digitaler Daten über störungsbehaftete Übertragungskanäle dient. In dieser Arbeit wird zunächst der Begriff der Coderate von allgemeinen Block-Codes über endlichen Körpern erläutert. Danach wird für lineare Block-Codes deren Darstellung, Kardinalität und Coderate sowie der Zusammenhang zwischen Generatormatrix und Prüfmatrix betrachtet. Die restliche Arbeit widmet sich zwei speziellen Unterklassen von binären linearen Block-Codes, den Low-Density-Parity-Check (LDPC)-Codes und den Multi-Edge-Type (MET)-LDPC-Codes, die eine Verallgemeinerung der LDPC-Codes sind. Beim Einsatz dieser Codes zur Kanalkodierung spielen symmetrische gedächtnislose Übertragungskanäle mit binärem Eingang (BMS-Kanäle) eine wichtige Rolle. Der Belief-Propagation-Algorithmus, der zur empfängerseitigen Dekodierung von LDPC-Codes und MET-LDPC-Codes nach deren Übertragung über BMS-Kanäle verwendet werden kann, wird erläutert. Für die stochastische Analyse des Verhaltens des Belief-Propagation-Algorithmus werden Log-Likelihood-Ratio (LLR)-Verteilungen und der Density-Evolution-Algorithmus eingesetzt. Die Theorie der LLR-Verteilungen wird im Kontext der Maß- und Wahrscheinlichkeitstheorie und der Lebesgue-Integration aufgebaut, insbesondere werden eine spezielle Symmetrieeigenschaft, zwei Arten von Faltungsoperationen und einige lineare Funktionale betrachtet. Auch einige theoretisch bedeutsame Resultate für BMS-Kanäle werden gezeigt. Danach wird der Density-Evolution-Algorithmus für LDPC-Codes und MET-LDPC-Codes beschrieben. Schließlich wird ein Quantisierungsverfahren zur effizienten näherungsweisen numerischen Implementierung des Density-Evolution-Algorithmus für MET-LDPC-Codes betrachtet und verbessert, und die Resultate eines numerischen Beispiels werden gezeigt.

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.