Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IEICE Technical Report; IEICE Tech. Rep.

Linear Programming Decoding for Multiple Access Channel based on Decomposition Methods

俊佑 堀井, 敏泰 松嶋

Published Sep 20, 2012• 0 citations
OpenAlex

Related papers

Linear Programming Decoding of Binary Linear Codes for Multiple-Access Channel

Shunsuke Horii, Matsushima Toshiyasu, Hirasawa Shigeichi

IEICE Technical Report; IEICE Tech. Rep.•Sep 14, 2010•0 citations

Linear Programming Decoding of Binary Linear Codes over Symbol-Pair Read Channels

Shunsuke Horii, Matsushima Toshiyasu, Hirasawa Shigeichi

IEICE Technical Report; IEICE Tech. Rep.•Aug 28, 2015•0 citations

On Linear Programming Decoding on a Quantized Additive White Gaussian Noise Channel

Eirik Rosnes

Lecture notes in computer science•Jan 1, 2009•0 citations

A Note on the Linear Programming Decoding of Binary Linear Codes for Multiple-Access Channel

Shunsuke Horii, Toshiyasu Matsushima, Shigeichi Hirasawa

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.

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•Jan 1, 2011•0 citations

A decoding algorithm for linear codes

Martin Bossert, F. Hergert

Lecture notes in computer science•Jan 1, 1986•2 citations

Improved Check Node Decomposition for Linear Programming Decoding

Xiaopeng Jiao, Jianjun Mu

For the linear programming decoding (LPD) proposed by Feldman et al., the number of constraints increases exponentially with check degrees. By decomposing a high-degree check node into a number of degree-3 check nodes, the number of constraints grows linearly with check degrees. In this letter, we show that the size of the LPD can be reduced by decomposing a high-degree check node into a number of degree-4 check nodes. The LPD using the degree-4 decomposition leads to almost the same number of constraints as using the degree-3 decomposition, while the number of auxiliary variable nodes is less than half of the one using the degree-3 decomposition. Moreover, when decomposing a high degree check node into a number of check nodes with degree d, d>4, the number of constraints increases rapidly and the size of the LPD becomes larger than the degree-4 decomposition. It is demonstrated on an LDPC code and a BCH code that the decoding time of the degree-4 decomposition is the smallest among the different decomposition methods.

IEEE Communications Letters•Jan 2, 2013•4 citations
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.
For the linear programming decoding (LPD) proposed by Feldman et al., the number of constraints increases exponentially with check degrees. By decomposing a high-degree check node into a number of degree-3 check nodes, the number of constraints grows linearly with check degrees. In this letter, we show that the size of the LPD can be reduced by decomposing a high-degree check node into a number of degree-4 check nodes. The LPD using the degree-4 decomposition leads to almost the same number of constraints as using the degree-3 decomposition, while the number of auxiliary variable nodes is less than half of the one using the degree-3 decomposition. Moreover, when decomposing a high degree check node into a number of check nodes with degree d, d>4, the number of constraints increases rapidly and the size of the LPD becomes larger than the degree-4 decomposition. It is demonstrated on an LDPC code and a BCH code that the decoding time of the degree-4 decomposition is the smallest among the different decomposition methods.