タイトル | A Note on the Linear Programming Decoding of Binary Linear Codes for Multiple-Access Channel |
---|---|
著者 | 堀井俊佑 、松嶋敏泰 、平澤茂一 |
年度 | 2011 |
形式 | 論文誌 |
分野 | 通信路符号化 |
掲載雑誌名 | IEICE Trans. Fundamentals |
掲載号・ページ | E94-A, no.6, pp.1230-1237 |
掲載年 | 2011 |
掲載月 | 6 |
アブスト (日本語) |
査読:有 DOI: 10.1587/transfun.E94.A.1230 <a href="http://search.ieice.org/bin/summary.php?id=e94-a_6_1230&category=A&lang=&year=2011&abst="> IEICE page </a> |
アブスト (英語) |
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. |
備考 (日本語) |
3 |
備考 (英語) |
3 |
論文原稿 | |
発表資料 |
関連論文
- A New Latent Class Model for Analysis of Purchasing and Browsing Histories on EC Sites
- Linear Programming Decoding of Binary Linear Codes for Symbol-Pair Read Channels
- A Heuristic Search Method with the Reduced List of Test Error Patterns for Maximum Likelihood Decoding
- Parallel Architecture for Generalized LFSR in LSI Built-In Self Testing
- Parallel Encoder and Decoder Architecture for Cyclic Codes
- A Generalization of B.S.Clarke and A.R.Barron's Asymptotics of Bayes Codes for FSMX Sources
- Almost Sure and Mean Convergence of Extended Stochastic Complexity
- A Source Model with Probability Distribution over Word Set and Recurrence Time Theorem
- Properties of a Word-Valued Source with a Non-prefix-free Word Set
- Asymptotics of Bayesian Inference for a Class of Probabilistic Models under Misspecification
- An Analysis of Slepian-Wolf Coding Problem Based on the Asymptotic Normality
- On the Overflow Probability of Fixed - to - Variable Length Codes with Side Information
- A Study on the Degrees of Freedom in an Experimental Design Model Based on an Orthonormal System
- A Note on Relation between the Fourier Coefficients and the Effects in the Experimental Design
- 多重アクセス通信に対する双対分解法に基づいた線形計画復号法
- Asymptotic property of universal lossless coding for independent piecewise identically distributed sources
- A Note on Automatic Construction Algorithms for Orthogonal Designs of Experiments Using Error-correcting Codes
- A Note on the Branch-and-Cut Approach to Decoding Linear Block Codes
- 2元線形符号を用いた多重アクセス通信路に対する線形計画復号について
- Estimation of the Effects in the Experimental Design using Fourier Transforms