In this work, iterative decoders for Low-Density Parity-Check (LDPC) codes are analyzed and optimized for low computational complexity. LDPC block codes are now widely used in industry standards such as Wi-Fi or 5G New Radio (NR). Hence, there is a strong need for decoder concepts suitable for hardware designs. In addition, terminated LDPC convolutional codes are promising candidates for next-generation communication systems.

The main theme of this work is to investigate low-overhead strategies for reducing the computational complexity of iterative decoders. Two aspects are considered for fast decoding of the LDPC block codes in 5G NR. Firstly, an efficient but simple-to determine update schedule for the iterative decoding process, i.e., the sequence of updates on different parts of a codeword, is proposed. Secondly, Early Termination (ET), i.e., an option to stop decoding before a maximal number of iterations is exhausted, is improved in two ways: On the one hand, a partial evaluation of the code’s Parity-Check (PC) equations speeds up the detection of valid codewords. On the other hand, a novel criterion detects when the decoding process is unlikely to converge and stops the decoding before a lot of resources are wasted on futile iterations. The combination of all techniques results in a decoder with significant reduction of the computational complexity compared to a decoder without these methods. Still, only few additional residual decoding errors are produced.

This work also contains an analysis of various aspects of a Windowed Decoder (WD), which is a specialized decoder design for LDPC convolutional codes. A WD can be configured in even more ways than a decoder for block codes. The analysis in this work assumes a normalization of the computational complexity to a certain maximal value. With this setup, it is shown that a larger size of the decoding window may be preferable over a smaller size to minimize the computational complexity. Furthermore, various window update strategies (determining in which way the code symbol reliabilities are updated in each window) and variations of ET are compared to identify a well-suited WD configuration. Lastly, strategies with Dynamic Scheduling (DS) are considered to further reduce the computational complexity. A novel fixed approach derived from several DS strategies performs well without actual dynamic knowledge of the decoder state. All in all, the optimized WD configuration halves the computational complexity of a block decoder while maintaining an acceptable loss in the decoding performance measured by the number of residual decoding errors.

A comparison of systems with Hybrid Automatic Repeat reQuest (HARQ) expands the scope of this work into the domain of error control by retransmissions. The analyzed systems make use of the decoder output, e.g., the final code-symbol reliabilities, to assemble dynamic retransmissions that are as short as possible and contain specifically selected code symbols. These systems stand in contrast to contemporary implementations of HARQ that only use imprecise feedback messages. Still, some compatibility with existing systems is achieved by assuming a limited feedback channel, which requires clever compression of the feedback information. A novel HARQ system is proposed, which evaluates the code’s PC equations to avoid the computational overhead of soft-value processing. The throughput with the proposed system is found to be improved compared to a reference system that evaluates code-symbol reliabilities.

Finally, approximations of the accurate message-update rules of the Sum–Product Algorithm (SPA) are analyzed. With fixed-point arithmetic, Look-Up Tables (LUTs) are a promising approach to approximate functions that are costly to compute. It is shown that an optimized LUT with just nine entries can be used in a fixed-point decoder such that the decoding performance is close to that of a floating-point decoder with accurate message updates.

In dieser Arbeit werden iterative Decodierer für dünn besetzte Paritätsprüfungscodes (Low-Density Parity-Check Codes, LDPC-Codes) analysiert und für geringe Decodierkomplexität optimiert. LDPC-Blockcodes sind heutzutage in Industriestandards wie Wi-Fi oder 5G New Radio (NR) weit verbreitet. Daher besteht ein starker Bedarf nach Decodiererkonzepten, die für den Hardwareentwurf geeignet sind. Zusätzlich stellen terminierte LDPC-Faltungscodes einen vielversprechenden Kandidaten für die Kommunikationssysteme der nächsten Generation dar.

Die Hauptthematik dieser Arbeit ist die Untersuchung von Strategien zur Reduzierung der Decodierkomplexität von iterativen Decodierern mit geringen Zusatzkosten. Zwei Aspekte werden betrachtet für schnelles Decodieren der LDPC-Blockcodes in 5G NR. Als erstes wird ein effizienter, aber einfach zu bestimmender Aktualisierungsablauf für den iterativen Decodierprozess vorgeschlagen, also die Sequenz aus Aktualisierungen von verschiedenen Teilen eines Codeworts. Als zweites wird ein frühes Terminieren (Early Termination, ET), also eine Option, mit dem Decodieren aufzuhören, bevor eine maximale Anzahl von Iterationen aufgebraucht ist, auf zwei Arten verbessert: Einerseits beschleunigt eine partielle Auswertung der Paritätsgleichungen des Codes die Erkennung von gültigen Codeworten. Andererseits erkennt ein neues Kriterium, wenn der Decodierprozess wahrscheinlich nicht konvergiert und hält das Decodieren an, bevor eine Menge an Ressourcen mit aussichtslosen Iterationen verschwendet wird. Die Kombination all dieser Verfahren ergibt einen Decodierer mit signifikant reduzierter Decodierkomplexität im Vergleich zu einem Decodierer ohne diese Verfahren. Dennoch werden nur wenige zusätzliche verbleibende Decodierfehler produziert.

Diese Arbeit enthält auch eine Analyse von verschiedenen Aspekten eines Fenster-Decodierers (Windowed Decoder, WD), welcher ein auf LDPC-Faltungscodes spezialisierter Decodierer ist. Ein WD kann auf noch mehr verschiedenen Arten konfiguriert werden, als ein Decodierer für Blockcodes. Die Analyse in dieser Arbeit geht von einer Normalisierung der Decodierkomplexität auf einen bestimmten Maximalwert aus. Mit diesem Versuchsaufbau wird gezeigt, dass ein größeres Decodierfenster vorteilhaft gegenüber einem kleineren Decodierfenster sein kann, um die Decodierkomplexität zu minimieren. Darüber hinaus werden verschiedene Fensteraktualisierungsstrategien (die bestimmen, in welcher Weise die Zuverlässigkeiten der Codesymbole in jedem Fenster aktualisiert werden) und Varianten von ET verglichen, um eine geeignete WD-Konfiguration zu bestimmen. Zuletzt werden dynamische Aktualisierungsablaufstrategien (Dynamic Scheduling, DS) herangezogen, um die Decodierkomplexität weiter zu verringern. Ein neuartiger fixer Ansatz, der aus mehreren DS-Strategien abgeleitet wurde, funktioniert gut, auch ohne tatsächliche dynamische Kenntnis des Zustands des Decodierers. Alles in allem halbiert die optimierte WD-Konfiguration die Decodierkomplexität eines Block-Decodierers bei gleichzeitig akzeptabler Reduktion der Decodierleistung, gemessen an der Anzahl verbleibender Decodierfehler.

Ein Vergleich von System mit hybrider automatischer Wiederholungsanfrage (Hybrid Automatic Repeat reQuest, HARQ) erweitert den Rahmen dieser Arbeit im Hinblick auf Fehlerkontrolle durch Übertragungswiederholungen. Die untersuchten Systeme nutzen die Decodiererausgabe, also zum Beispiel die endgültigen Zuverlässigkeiten der Codesymbole, um dynamische Übertragungswiederholungen zusammenzustellen, die so kurz wie möglich sind und spezifisch ausgewählte Codesymbole enthalten. Diese Systeme sind gegensätzlich zu derzeit üblichen HARQ-Implementierungen, die nur unpräzise Rückmeldung geben. Dennoch wird ein gewisses Maß an Kompatibilität mit existierenden Systemen erreicht, indem ein begrenzter Rückkanal angenommen wird, was eine kluge Kompression der Rückmeldung erfordert. Ein neuartiges HARQ-System wird vorgeschlagen, welches die Paritätsgleichungen des Codes auswertet, um so den zusätzlichen Berechnungsaufwand für die Verarbeitung von Zuverlässigkeiten zu vermeiden. Der Durchsatz mit dem vorgeschlagenen System stellt sich als überlegen gegenüber einem System, das Zuverlässigkeiten der Codesymbole auswertet, heraus.

Zum Abschluss werden Annäherungen der genauen Berechnungsvorschriften für Nachrichten im sogenannten Sum–Product Algorithm (SPA) analysiert. Mit Festkomma-Arithmetik sind Umsetzungstabellen (Look-Up Tables, LUTs) ein vielversprechender Ansatz zur Annäherung von aufwendig zu berechnenden Funktionen. Es wird gezeigt, dass eine optimierte Umsetzungstabelle mit nur neun Einträgen so in einem Festkomma-Decodierer verwendet werden kann, dass dessen Decodierleistung einem Gleitkomma-Decodierer mit genauen Berechnungen nahekommt.