Development and implementation of efficient decoding algorithms for linear block codes
Final Report Abstract
Die Fehlerkorrektur in heutigen Kommunikationssystemen ist dominiert von heuristischen iterativen Decodierverfahren. Diese sind zwar sehr effizient implementierbar, erreichen jedoch keine optimale Fehlerkorrektur. Die exakte, bestmögliche Lösung des Decodierproblems bietet die Maximum-Likelihood (ML)-Decodierung, welche ein NP-schweres Problem darstellt. Auch wenn ein ML-Decoder daher kaum für Echtzeitanwendungen in Betracht kommt, bietet das Wissen über die optimale nachrichtentechnische Performanz eines Codes eine Reihe von Vorteilen. So kann damit etwa das Optimierungspotenzial neuer Decoder abgeschätzt werden oder es können verschiedene Codes ohne den Einfluss von heuristischen Decodieralgorithmen miteinander verglichen werden. Ziel dieses Projekts war daher die Implementierung eines ML-Decoders als dedizierter Hardwarebeschleuniger. Um dieses Ziel für mittlere bis lange Codes erreichen zu können, darf das Problem nicht nur von theoretischer oder praktischer Seite angegangen werden. Vielmehr müssen Theorie und Anwendung zusammenrücken und Randbedingungen einer effizienten Implementierung müssen schon früh in den Prozess der Algorithmenentwicklung mit einbezogen werden. Die in diesem Projekt entstandene Hardwarearchitektur beruht daher auf einer sorgfältigen mathematischen Analyse des ML-Decodierproblems, welcher eine Vielzahl an Algorithmen zur Lösung des Problems entsprungen sind, wie etwa ein schneller Branch-and-Cut-Algorithmus oder ein neuer Projektionsalgorithmus für den ADMM-Decoder. Diese Algorithmen wurden anschließend unter Hardwarerandbedingungen untersucht, um Aussagen über ihre Effizienz zu treffen. Auf diesem Weg kann das so erlangte Wissen über auftretende (Hardware-)Probleme, wie z. B. Instabilitäten gegenüber Quantisierungseffekten, schon früh in die Algorithmenentwicklung zurückfließen. Im nächsten Schritt wurden aus den zuvor entwickelten und unter Hardwarerandbedingungen evaluierten Algorithmen Hardwarearchitekturen entworfen. Einerseits wurde dabei ein RS-Soft-Decoder implementiert, der entweder einen deutlichen Vorteil bezüglich benötigter Ressourcen und Durchsatz oder einen großen Gewinn in nachrichtentechnischer Performanz bringt. Andererseits wurden effiziente LP-Decoder entwickelt, die entweder auf dem Simplex-Algorithmus oder dem ADMM-Verfahren beruhen. In einem letzten Schritt wurden die bisherigen Teilarchitekturen in einer Branch-and-Bound-Struktur zusammengeführt, wodurch nach unserem besten Wissen die erste vollständige Hardwareimplementierung eines ML-Decoders entstanden ist.
Publications
- Towards combinatorial LP turbo decoding. In Proceedings of IEEE International Symposium on Information Theory, pages 1491–1495, Istanbul, Turkey, July 2013
M. Helmling and S. Ruzika
(See online at https://doi.org/10.1109/ISIT.2013.6620475) - Advanced hardware architecture for soft decoding Reed-Solomon codes. In 2014 8th International Symposium on Turbo Codes and Iterative Information Processing (ISTC), pages 22–26, August 2014
S. Scholl and N. Wehn
(See online at https://doi.org/10.1109/ISTC.2014.6955078) - Efficient maximum-likelihood decoding of linear block codes on binary memoryless channels. In Proceedings of IEEE International Symposium on Information Theory, pages 2589–2593, Honolulu, HI, USA, June/July 2014
M. Helmling, E. Rosnes, S. Ruzika, and S. Scholl
(See online at https://doi.org/10.1109/ISIT.2014.6875302) - Hardware implementation of a Reed-Solomon soft decoder based on information set decoding. In 2014 Design, Automation Test in Europe Conference Exhibition (DATE), pages 1–6, March 2014
S. Scholl and N. Wehn
(See online at https://doi.org/10.7873/DATE.2014.222) - Minimum pseudoweight analysis of 3- dimensional turbo codes. IEEE Transactions on Communications, 62(7):2170–2182, July 2014
E. Rosnes, M. Helmling, and A. Graell i Amat
(See online at https://doi.org/10.1109/TCOMM.2014.2329690) - Method and device for an error correction of transmitted data. Patent WO2015140253A1
S. Scholl and N. Wehn
- ADMM versus Simplex algorithm for LP decoding. In 2016 9th International Symposium on Turbo Codes and Iterative Information Processing (ISTC), pages 211–215, September 2016
F. Gensheimer, S. Ruzika, S. Scholl, and N. Wehn
(See online at https://doi.org/10.1109/ISTC.2016.7593107) - A low-complexity projection algorithm for ADMM-based LP decoding. In International Symposium on Turbo Codes & Iterative Information Processing (ISTC), December 2018
F. Gensheimer, T. Dietz, S. Ruzika, K. Kraft, and N. Wehn
(See online at https://doi.org/10.1109/ISTC.2018.8625295) - A reduced-complexity projection algorithm for ADMM-based LP decoding, 2019
F. Gensheimer, T. Dietz, K. Kraft, S. Ruzika, and N. Wehn
(See online at https://doi.org/10.1109/TIT.2020.2984247)
