| タイトル | 2元線形符号を用いた多重アクセス通信路に対する線形計画復号について |
|---|---|
| 著者 | 堀井俊佑 、松嶋敏泰 、平澤茂一 |
| 年度 | 2010 |
| 形式 | 国内学会 |
| 分野 | 通信路符号化 |
| 掲載雑誌名 | 電子情報通信学会技術研究報告 |
| 掲載号・ページ | IT2010-39, pp.31-36 |
| 掲載年 | 2010 |
| 掲載月 | 9 |
| アブスト （日本語） |
学会名：電子情報通信学会技術研究報告 日程：不明 場所：不明 vol., no. 不明． 2元線形符号を用いた多元接続通信路における線形計画法に基づいた復号法を提案する． 近年，通信路符号化の最尤復号の問題に対して線形計画復号法が注目を浴びている． 本研究ではまず，2元線形符号を用いた多元接続通信路における最尤復号の問題がどのようにして線形計画問題として定式化されるかを示す． これは，目的関数である対数尤度関数が，一般的には符号語シンボルに対する線形関数ではないため自明ではない． そこで，本研究では，目的関数がその変数の線形関数になるような補助変数を導入する． これにより，最尤復号の問題が線形計画問題として定式化されるが，この問題を解くには非常に多くの計算量を要し，現実的ではない． 本研究では，1対1通信における線形計画復号法と同様に，この問題を緩和した線形計画問題を考える． 提案された復号法は，1対1通信の場合と同様，復号結果が整数ならば最尤復号であることが保証されるという望ましい性質を持つ． 提案された復号法は，通信路のユーザー数に対して指数オーダーの計算量が必要となるが，ガウス型多元接続通信路においてはその計算量を削減することが出来ることを示す． また，コンピュータシミュレーションにより，Sum-Productアルゴリズムに基づいた復号法との性能比較を行う． |
| アブスト （英語） |
In this paper, we develop a linear-programming (LP) decoding for the multiple-access channel with binary linear codes. For the single-user channel, LP decoding has been attracting much attention in recent years as a good approximation to the maximum likelihood decoding. We demonstrate that how the maximum likelihood decoding problem for the multiple-access channel with binary linear codes can be formulated as a linear programming problem. It is not straightforward because the objective function of the problem is a non-linear function of the codeword symbols in general. We introduce the auxiliary variables such that the objective function is a linear function of those variables. Then the ML decoding problem reduces to the LP problem however, it is too complex for practical implementation. As the case for the single-user channel, we formulate the relaxed LP problem. Just as in the case of the single-user channel, the proposed decoder has the desirable property called ML certificate property, that is, if the decoder outputs integer solution, it is guaranteed to be the ML codeword. The computational complexity of the proposed algorithm is the exponential order of the number of users, however, we can reduce the computational complexity of the algorithm for the gaussian multiple-access channel. Furthermore, we compare the performance of the proposed decoder with the decoder based on the sum-product algorithm. |
| 備考 （日本語） |
1 |
| 備考 （英語） |
1 |
| 論文原稿 | |
| 発表資料 |
関連論文
- 統計的決定理論に基づく階層構造を利用したマルチラベル分類法について
- 関数に対する最小ストレージ再生成符号に関する一検討
- 多重アクセス通信に対する双対分解法に基づいた線形計画復号法
- A Note on Linear Programming Based Communication Receivers
- 線形計画法に基づいたファクターグラフ上の推論アルゴリズムに関する一考察
- A Note on the Linear Programming Decoding of Binary Linear Codes for Multiple-Access Channel
- An Efficient Algorithm for the Bayes Codes using an Unlimited Depth Context Tree
- A Note on the Branch-and-Cut Approach to Decoding Linear Block Codes
- 補助情報を伴う情報源符号化定理に関する一考察
