Development and implementation of efficient decoding algorithms for linear block codes

• Applicants: Professor Dr. Stefan Ruzika; Professor Dr.-Ing. Norbert Wehn
• 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

Error-correcting decoding methods play an important role in communications. The theoretically best error correction rate is achieved by maximum-likelihood (ML) decoding using soft reliability information. Nowadays, iterative heuristics are used in practice. These heuristics are very efficient on the one hand, but on the other they do not reach the optimal error correction potential. This holds especially for codes with dense parity check matrices. In contrast, decoding methods based on mathematical programming models resulting in integer optimization problems (IPs) assure best-possible error correction. This approach has the additional advantage of being universally applicable to any kind of linear block code (e.g. LDPC, RS, turbo codes). Existing algorithms for IP based decoding suffer from high computational complexity. This proposal aims at reduction of this complexity by exploiting code-specific mathematical structures. Today's communcations systems (e.g. mobile service) simultaneously demand high data rates as well as a high degree of power efficiency. Soft implementations using standard hardware do not satisfy these demands. Hence, decoding algorithms are typically implemented as optimized, dedicated hardware. Such hardware implementations are realized on ASIC (application-specific integrated circuit) or FPGA (field-programmable gate array) platforms. The scientific goal of this proposal is thus the development of efficient solution algorithms for the underlying integer programs and their implementation on dedicated hardware. The central concept for achieving this goal is the so-called linear programming (LP) decoding which in turn is based on the theory of linear optimization. So far, hardware realizations of LP decoding have hardly been investigated in literature. In order to close this gap, we will develop efficient decoding methods based on mathematical programming. Considering the conditions and constraints imposed by hardware requirements during the phase of algorithm development is of crucial importance for this project. The scientific challenge lies in the demanding combination of the research areas of communications, hardware design and implementation and mathematical programming.

• DFG Programme: Research Grants