In this paper, we develop linear-programming (LP) decoding for multiple-access channels with binary linear codes. For single-user channels, LP decoding has attracted much attention in recent years as a good approximation to maximum-likelihood (ML) decoding. We demonstrate how the ML decoding problem for multiple-access channels with binary linear codes can be formulated as an LP problem. This is not straightforward, because the objective function of the problem is generally a non-linear function of the codeword symbols. We introduce auxiliary variables such that the objective function is a linear function of these variables. The ML decoding problem then reduces to the LP problem. As in the case for single-user channels, we formulate the relaxed LP problem to reduce the complexity for practical implementation, and as a result propose a decoder that has the desirable property known as the ML certificate property (i.e., if the decoder outputs an integer solution, the solution is guaranteed to be the ML codeword). Although the computational complexity of the proposed algorithm is exponential in the number of users, we can reduce this complexity for Gaussian multiple-access channels. Furthermore, we compare the performance of the proposed decoder with a decoder based on the sum-product algorithm.

In this study, we develop a new algorithm for decoding binary linear codes for symbol-pair read channels. The symbol-pair read channel was recently introduced by Cassuto and Blaum to model channels with higher write resolutions than read resolutions. The proposed decoding algorithm is based on linear programming (LP). For LDPC codes, the proposed algorithm runs in time polynomial in the codeword length. It is proved that the proposed LP decoder has the maximum-likelihood (ML) certificate property, i.e., the output of the decoder is guaranteed to be the ML codeword when it is integral. We also introduce the fractional pair distance dfp of the code, which is a lower bound on the minimum pair distance. It is proved that the proposed LP decoder corrects up to ⌈dfp/2⌉-1 errors.

Maximum likelihood (ML) decoding of linear block codes can be considered as an integer linear programming (ILP). Since it is an NP-hard problem in general, there are many researches about the algorithms to approximately solve the problem. One of the most popular algorithms is linear programming (LP) decoding proposed by Feldman et al. LP decoding is based on the LP relaxation, which is a method to approximately solve the ILP corresponding to the ML decoding problem. Advanced algorithms for solving ILP (approximately or exactly) include cutting-plane method and branch-and-bound method. As applications of these methods, adaptive LP decoding and branch-and-bound decoding have been proposed by Taghavi et al. and Yang et al., respectively. Another method for solving ILP is the branch-and-cut method, which is a hybrid of cutting-plane and branch-and-bound methods. The branch-and-cut method is widely used to solve ILP, however, it is unobvious that the method works well for the ML decoding problem. In this paper, we show that the branch-and-cut method is certainly effective for the ML decoding problem. Furthermore the branch-and-cut method consists of some technical components and the performance of the algorithm depends on the selection of these components. It is important to consider how to select the technical components in the branch-and-cut method. We see the differences caused by the selection of those technical components and consider which scheme is most effective for the ML decoding problem through numerical simulations.