ILP techniques for binary subspace codes

健太 笠井, Kenta Kasai, 隆之 野崎 +3 more

Kira Kraft, Norbert Wehn

Integer Linear Programming (ILP) is a general method to solve the Maximum-Likelihood (ML) decoding problem for all kinds of binary linear codes. To this end, state-of-the-art techniques use a Branch-and-Bound (B&B) framework to partition the underlying integer linear problem into several relaxed linear problems. These linear problems then have to be solved in reasonable time by an efficient Linear Programming (LP) solver. Recently, the Alternating Direction Method of Multipliers (ADMM) has been proposed for efficient software and hardware LP decoding of sparse codes, hence, an ADMM-based ML decoder seems to be a promising approach. In this paper, we investigate this approach with respect to its algorithmic and implementation-specific challenges.

Kenny Barrese

Martin Bossert, F. Hergert

Kenta Kasai, T. Nozaki, Kohichi Sakaniwa

We study LDPC codes for the channel with 2m-ary input x ϵ F2mand output y = x + z ϵ F2m. The receiver knows a subspace V ⊂ F2mfrom which z = y - x is uniformly chosen. Or equivalently, the receiver receives an affine subspace y-V where x lies. We consider a joint iterative decoder involving the channel detector and the LDPC decoder. The decoding system considered in this paper can be viewed as a simplified model of the joint iterative decoder over non-binary modulated signal inputs e.g., 2m-QAM. We evaluate the performance of binary spatially-coupled MacKay-Neal codes by density evolution. The iterative decoding threshold is seriously degraded by increasing m. EXIT-like function curve calculations reveal that this degradation is caused by wiggles and can be mitigated by increasing the randomized window size. The resultant iterative decoding threshold values are very close to the Shannon limit.

Hannes Bartz, Men‐Andrin Meier, Vladimir R. Sidorenko