Servicenavigation

Project Details

Back

Projekt Print View

Development and implementation of efficient decoding algorithms for linear block codes

Subject Area Electronic Semiconductors, Components and Circuits, Integrated Systems, Sensor Technology, Theoretical Electrical Engineering
Term from 2012 to 2019
Project identifier Deutsche Forschungsgemeinschaft (DFG) - Project number 221415220
 
Final Report Year 2019

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

 
 

Additional Information

© 2025 DFG Disclaimer / Copyright / Privacy Policy

Textvergrößerung und Kontrastanpassung