A correction is made in the statement and proof of a lemma used to prove codeword symmetry. In addition, an important typo is noted and corrected.

In this paper, we introduce a new way of constructing and decoding multipermutation codes. Multipermutations are the permutations of a multiset that generally consist of duplicate entries. We first introduce a class of binary matrices called multipermutation matrices, each of which corresponds to a unique and distinct multipermutation. By enforcing a set of linear constraints on these matrices, we define a new class of codes that we term linear program (LP)-decodable multipermutation codes. In order to decode these codes using an LP, thereby enabling soft decoding, we characterize the convex hull of multipermutation matrices. This characterization allows us to relax the coding constraints to a polytope and to derive two LP decoding problems. These two problems are, respectively, formulated by relaxing the maximum likelihood decoding problem and the minimum Chebyshev distance decoding problem. Because these codes are non-linear, we also study efficient encoding and decoding algorithms. We first describe an algorithm that maps consecutive integers, one by one, to an ordered list of multipermutations. Based on this algorithm, we develop an encoding algorithm for a code proposed by Shieh and Tsai, a code that falls into our class of LP-decodable multipermutation codes. Regarding decoding algorithms, we propose an efficient distributed decoding algorithm based on the alternating direction method of multipliers. Finally, we observe from the simulation results that the soft decoding techniques we introduce can significantly outperform hard decoding techniques that are based on quantized channel outputs.

Linear programming (LP) decoding for low-density parity-check codes was introduced by Feldman et al. and has been shown to have theoretical guarantees in several regimes. Furthermore, it has been reported in the literature-via simulation and via instanton analysis-that LP decoding displays better error rate performance at high signal-to-noise ratios (SNR) than does belief propagation (BP) decoding. However, at low SNRs, LP decoding is observed to have worse performance than BP. In this paper, we seek to improve LP decoding at low SNRs while maintaining LP decoding's high SNR performance. Our main contribution is a new class of decoders obtained by applying the alternating direction method of multipliers (ADMM) algorithm to a set of non-convex optimization problems. These non-convex problems are constructed by adding a penalty term to the objective of LP decoding. The goal of the penalty is to make pseudocodewords, which are non-integer vertices of the LP relaxation, more costly. We name this class of decoders-ADMM penalized decoders. For low and moderate SNRs, we simulate ADMM penalized decoding with ℓ1and ℓ2penalties. We find that these decoders can outperform both BP and LP decoding. For high SNRs, where it is difficult to obtain data via simulation, we use an instanton analysis and find that, asymptotically, ADMM penalized decoding performs better than BP but not as well as LP. Unfortunately, since ADMM penalized decoding is not a convex program, we have not been successful in developing theoretical guarantees. However, the non-convex program can be approximated using a sequence of linear programs; an approach that yields a reweighted LP decoder. We show that a two-round reweighted LP decoder has an improved theoretical recovery threshold when compared with LP decoding. In addition, we find via simulation that reweighted LP decoding significantly attains lower error rates than LP decoding at low SNRs.

In this paper, we develop efficient decoders for non-binary low-density parity-check codes using the alternating direction method of multipliers (ADMM). We apply ADMM to two decoding problems. The first problem is linear programming (LP) decoding. In order to develop an efficient algorithm, we focus on non-binary codes in fields of characteristic two. This allows us to transform each constraint in F2m to a set of constraints in F2that has a factor graph representation. Applying ADMM to the LP decoding problem results in two types of non-trivial sub-routines. The first type requires us to solve an unconstrained quadratic program. We solve this problem efficiently by leveraging new results obtained from studying the above factor graphs. The second type requires Euclidean projections onto polytopes that are studied in the literature. Such projections can be solved efficiently using off-the-shelf techniques, which scale linearly in the dimension of the vector to project. ADMM LP decoding scales linearly with block length, linearly with check degree, and quadratically with field size. The second problem we consider is a penalized LP decoding problem. This problem is obtained by incorporating a penalty term into the LP decoding objective. The purpose of the penalty term is to make non-integer solutions (pseudocodewords) more expensive and hence to improve decoding performance. The ADMM algorithm for the penalized LP problem requires Euclidean projection onto a polytope formed by embedding the constraints specified by the non-binary single parity-check code, which can be solved by applying the ADMM technique to the resulting quadratic program. Empirically, this decoder achieves a much reduced error rate than LP decoding at low signal-to-noise ratios.

Alternating direction method of multipliers (ADMM) decoding is a new decoding framework for low-density parity-check (LDPC) codes. It can be used to implement linear programming (LP) decoding or penalized LP decoding. Similar to belief propagation (BP) decoding, ADMM decoding consists of local “check” and “variable updates”. However, ADMM decoding performs better than BP at high signal-to-noise ratios (SNRs). To understand why these two locally operating algorithms result in different error floor behaviors, we study the dynamics of ADMM decoding in this paper. In particular, we focus on trapping sets, which are observed to cause error floors in ADMM decoding. Our results show that the dynamics of ADMM decoding on trapping sets can be characterized as a jump linear system. Furthermore, these results indicate that the Lagrange multipliers involved in ADMM play an important role in correcting trapping set errors. Finally, we present simulation results that support this understanding.

LP-decodable multipermutation codes are a class of multipermutation codes that can be decoded using linear programming (LP). These codes are defined using linearly constrained multipermutation matrices, which are binary matrices that satisfy particular row sum and column sum constraints. Although generic LP solvers are capable of solving the LP decoding problem, they are not efficient in general because they do not leverage structures of the problem. This motivates us to study efficient decoding algorithms. In this paper, we focus on encoding and decoding algorithms for LP-decodable multipermutation codes. We first describe an algorithm that “ranks” multipermutations. In other words, it maps consecutive integers, one by one, to an ordered list of multipermutations. By leveraging this algorithm, we develop an encoding algorithm for a code proposed by Shieh and Tsai. Regarding decoding algorithms we propose an iterative decoding algorithm based on the alternating direction method of multipliers (ADMM), each iteration of which can be solved efficiently using off-the-shelf techniques. Finally, we study decoding performances of different decoders via simulation.

Many code constraints can be represented using factor graphs. By relaxing these factorable coding constraints to linear constraints, it is straightforward to form a decoding optimization problem. Furthermore, by pairing these factor graphs with the alternating directions method of multipliers (ADMM) technique of large-scale optimization, one can develop distributed algorithms to solve the decoding optimization problems. However, the non-trivial part has always been developing an efficient algorithm for the subroutines of ADMM, which directly relates to the geometries of the relaxed coding constraints. In this paper, we focus on summarizing existing results and distilling insights to these problems. First, we review the ADMM formulation and geometries involved in the subroutines. Next, we present a linear time algorithm for projecting onto an ℓ1ball with box constraints.

Linear programming (LP) decoding using the alternating direction method of multipliers (ADMM) has been shown to be an efficient algorithm. A non-convex variation based on the ADMM LP decoder called the ADMM penalized decoder was introduced by Liu et al. (IEEE ITW, Sep. 2012) to close the signal-to-noise ratio (SNR) gap between LP decoding and classic belief propagation (BP) decoding. This algorithm was shown to achieve or outperform BP decoding at all SNRs, including high SNRs where BP decoding suffers from the error floor effect. In this paper, we study the behaviors of the ADMM penalized decoder at high SNRs where simulation is infeasible. We use a generic tool called instanton analysis and propose an instanton search algorithm for the ADMM penalized decoder. We then apply the algorithm to the [155, 64] Tanner code and a [1057, 813] LDPC code. We show that the instanton information we obtained provides good predictions for word-error-rate curve at high SNRs. In addition, our results suggest that the ADMM penalized decoder can suffer from trapping sets.

In this paper, we develop an efficient algorithm for linear programming (LP) decoding of non-binary low-density parity-check (LDPC) codes. We build our algorithm on the decomposition method based on the alternating direction method of multipliers (ADMM). Although expressing the LP decoding problem using ADMM is not hard, a sub-routine of ADMM - projection onto a polytope formed from embeddings of the non-binary single parity-check code - is not straightforward. In this work, we focus on non-binary codes in fields of characteristic two. This allows us to use operations in F2to relax the polytope under consideration into a form that is computational friendly. We introduce a rotation step that normalizes the geometry under consideration. We then apply ADMM a second time to solve the projection problem, which is a quadratic program (QP). Our decoding algorithm scales linearly with block length, linearly with check degree, and quadratically with field size.

When binary linear error-correcting codes are used over symmetric channels, a relaxed version of the maximum likelihood decoding problem can be stated as a linear program (LP). This LP decoder can be used to decode error-correcting codes at bit-error-rates comparable to state-of-the-art belief propagation (BP) decoders, but with significantly stronger theoretical guarantees. However, LP decoding when implemented with standard LP solvers does not easily scale to the block lengths of modern error correcting codes. In this paper, we draw on decomposition methods from optimization theory, specifically the alternating direction method of multipliers (ADMM), to develop efficient distributed algorithms for LP decoding. The key enabling technical result is a “two-slice” characterization of the parity polytope, the polytope formed by taking the convex hull of all codewords of the single parity check code. This new characterization simplifies the representation of points in the polytope. Using this simplification, we develop an efficient algorithm for Euclidean norm projection onto the parity polytope. This projection is required by the ADMM decoder and its solution allows us to use LP decoding, with all its theoretical guarantees, to decode large-scale error correcting codes efficiently. We present numerical results for LDPC codes of lengths more than 1000. The waterfall region of LP decoding is seen to initiate at a slightly higher SNR than for sum-product BP, however an error floor is not observed for LP decoding, which is not the case for BP. Our implementation of LP decoding using the ADMM executes as fast as our baseline sum-product BP decoder, is fully parallelizable, and can be seen to implement a type of message-passing with a particularly simple schedule.

In this paper, we present a new class of decoders for low density parity check (LDPC) codes. We are motivated by the observation that the linear programming (LP) decoder has worse error performance than belief propagation (BP) decoders at low SNRs. We base our new decoders on the alternating direction method of multipliers (ADMM) decomposition technique for LP decoding. The ADMM not only efficiently solves the LP decoding problem, but also makes it possible to explore other decoding algorithms. In particular, we add various penalty terms to the linear objective of LP decoding with the goal of suppressing pseudocodewords. Simulation results show that the new decoders achieve much better error performance compared to LP decoder at low SNRs. What is more, similar to the LP decoder, no error floor is observed at high SNRs.