Development and implementation of efficient decoding algorithms for linear block codes

纠错译码方法在通信中起着重要的作用。利用软可靠性信息的最大似然译码可以达到理论上最佳的纠错率。目前，迭代启发式在实践中得到了应用。这些启发式方法一方面非常有效，但另一方面却没有达到最优的纠错潜力。这尤其适用于具有密集奇偶校验矩阵的代码。相比之下，基于数学规划模型的解码方法导致整数优化问题（ip）确保最佳可能的纠错。这种方法还有一个额外的优点，就是普遍适用于任何类型的线性分组码（例如LDPC、RS、turbo码）。现有的IP解码算法存在计算复杂度高的问题。该建议旨在通过利用特定于代码的数学结构来降低这种复杂性。当今的通信系统（例如移动服务）同时要求高数据速率以及高功率效率。使用标准硬件的软实现不能满足这些要求。因此，解码算法通常作为优化的专用硬件实现。这些硬件实现是在ASIC（专用集成电路）或FPGA（现场可编程门阵列）平台上实现的。因此，本提案的科学目标是为底层整数程序开发有效的解决算法，并在专用硬件上实现它们。实现这一目标的核心概念是所谓的线性规划（LP）解码，它反过来又基于线性优化理论。到目前为止，文献中很少研究LP解码的硬件实现。为了缩小这一差距，我们将开发基于数学规划的高效解码方法。在算法开发阶段考虑硬件需求所施加的条件和约束对于本项目至关重要。科学挑战在于通信，硬件设计和实现以及数学规划研究领域的苛刻组合。

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.