IEICE TRANSACTIONS on Fundamentals
A Note on the Linear Programming Decoding of Binary Linear Codes for Multiple-Access Channel
Summary :
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.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E94-A No.6 pp.1230-1237
- Publication Date
- 2011/06/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.E94.A.1230
- Type of Manuscript
- Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
- Category
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Shunsuke HORII, Toshiyasu MATSUSHIMA, Shigeichi HIRASAWA, "A Note on the Linear Programming Decoding of Binary Linear Codes for Multiple-Access Channel" in IEICE TRANSACTIONS on Fundamentals,
vol. E94-A, no. 6, pp. 1230-1237, June 2011, doi: 10.1587/transfun.E94.A.1230.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E94.A.1230/_p
Copy
@ARTICLE{e94-a_6_1230,
author={Shunsuke HORII, Toshiyasu MATSUSHIMA, Shigeichi HIRASAWA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A Note on the Linear Programming Decoding of Binary Linear Codes for Multiple-Access Channel},
year={2011},
volume={E94-A},
number={6},
pages={1230-1237},
abstract={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.},
keywords={},
doi={10.1587/transfun.E94.A.1230},
ISSN={1745-1337},
month={June},}
Copy
TY - JOUR
TI - A Note on the Linear Programming Decoding of Binary Linear Codes for Multiple-Access Channel
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1230
EP - 1237
AU - Shunsuke HORII
AU - Toshiyasu MATSUSHIMA
AU - Shigeichi HIRASAWA
PY - 2011
DO - 10.1587/transfun.E94.A.1230
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E94-A
IS - 6
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - June 2011
AB - 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.
ER -
English
