Development and implementation of efficient decoding algorithms for linear block codes

线性分组码高效解码算法的开发和实现

• 批准号: 221415220
• 负责人: Professor Dr. Stefan Ruzika
• 金额: --
• 依托单位: Lehrstuhl Entwurf Mikroelektronischer Systeme
• 依托单位国家: 德国
• 项目类别: Research Grants
• 财政年份: 2012
• 资助国家: 德国
• 起止时间: 2011-12-31 至 2018-12-31
• 项目状态: 已结题
• 来源: https://gepris.dfg.de/gepris/projekt/221415220?language=en
• 关键词: Development; implementation; efficient; decoding; algorithms

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.

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

项目成果

Towards combinatorial LP turbo decoding

走向组合 LP Turbo 解码

• DOI: 10.1109/isit.2013.6620475
• 发表时间: 2013
• 期刊: 2013 IEEE International Symposium on Information Theory
• 作者: M. Helmling;S. Ruzika
• 通讯作者: S. Ruzika

A Reduced-Complexity Projection Algorithm for ADMM-Based LP Decoding

一种用于基于 ADMM 的 LP 解码的复杂度降低的投影算法

• DOI: 10.1109/tit.2020.2984247
• 发表时间: 2019
• 期刊: IEEE Transactions on Information Theory
• 影响因子: 2.5
• 作者: F. Gensheimer;T. Dietz;K. Kraft;S. Ruzika;N. Wehn
• 通讯作者: N. Wehn

Advanced hardware architecture for soft decoding Reed-Solomon codes

• DOI: 10.1109/istc.2014.6955078
• 发表时间: 2014-11
• 期刊: 2014 8th International Symposium on Turbo Codes and Iterative Information Processing (ISTC)
• 作者: S. Scholl;N. Wehn

Hardware implementation of a Reed-Solomon soft decoder based on information set decoding

基于信息集解码的Reed-Solomon软解码器的硬件实现

• DOI: 10.7873/date.2014.222
• 发表时间: 2014
• 期刊: 2014 Design, Automation & Test in Europe Conference & Exhibition (DATE)
• 作者: S. Scholl;N. Wehn
• 通讯作者: N. Wehn

A Low-Complexity Projection Algorithm for ADMM-Based LP Decoding

• DOI: 10.1109/istc.2018.8625295
• 发表时间: 2018-12
• 期刊: 2018 IEEE 10th International Symposium on Turbo Codes & Iterative Information Processing (ISTC)
• 作者: Florian Gensheimer;Tobias Dietz;Stefan Ruzika;Kira Kraft;N. Wehn