A Low-Complexity Projection Algorithm for ADMM-Based LP Decoding
A Low-Complexity Projection Algorithm for ADMM-Based LP Decoding
复制标题
DOI：
10.1109/istc.2018.8625295
复制
发表时间：
2018-12
期刊：
影响因子：
--
通讯作者：
Florian Gensheimer;Tobias Dietz;Stefan Ruzika;Kira Kraft;N. Wehn
中科院分区：
文献类型：
--
作者：
Florian Gensheimer;Tobias Dietz;Stefan Ruzika;Kira Kraft;N. Wehn
在基于admm的LP译码中，我们提出了一种新的计算奇偶多面体投影的低复杂度算法。该投影是ADMM算法的核心，它通常涉及排序操作，这是投影的主要工作。我们提出的算法依赖于宇称多面体递归结构的新发现，并通过迭代方式固定选定的组件来工作。没有排序操作使得它更适合于高效的硬件和软件实现。此外，我们可以证明，与最先进的投影相比，这种新的投影算法需要的算术运算减少了37%。
In this paper, we present a new low-complexity algorithm for computing the projection onto the parity polytope in the context of ADMM-based LP decoding. This projection is the heart of the ADMM algorithm, that usually involves a sorting operation, which is the main effort of the projection. Our proposed algorithm relies on new findings in the recursive structure of the parity polytope and works by fixing selected components in an iterative manner. The absence of the sorting operation makes it preferable for efficient hard- and software implementations. In addition, we can show that this new projection algorithm requires up to 37% less arithmetic operations compared to state-of-the-art projections.