最尤復号に対する池上・楫アルゴリズムの計算量を減らすための試み

スポンサーリンク

概要

• 論文の詳細を見る

• Maximum likelihood decoding (MLD) is performed by choosing the error vector with the minimal Hamming weight among the set of vectors having the same syndromes as the received word. Thus, it is formulated as an integer programming (IP) problem on finite fields. There is a famous algorithm by Conti and Traverso for solving IP problems using the Grobner basis in the polynomial ideal theory. Ikegami and Kaji have presented the algorithm for solving MLD using Grobner basis; which is an analogue of the Conti and Traverso's algorithm. Once we have the Grobner basis with respect to the adapted ordering of the ideal associated with the binary code, we efficiently perform MLD by computing the normal form of the monomials corresponding to the received word. However the algorithm has a serious problem on the computational complexity of the Grobner basis. The present paper is an attempt to reduce the computational complexity of the Grobner basis of the ideals associated with binary codes. We take two approaches: One is to apply the Grobner basis conversion algorithm by Faugere et al. and the other is to determine the subset of binomials in the Grobner basis that are indispensable for MLD. It is known that the Grobner basis of the ideals associated with binary code with respect to the lexicographic ordering can be obtained easily. We convert this Grobner basis to the Grobner basis with respect to the adapted ordering by using FGLM algorithm. We have shown that this approach is not effective for our purpose. As for the second approach we have found the specified subset of the Grobner basis that seems to be effective for the decoding.

• 2013-07-00

著者

• 渡邊 芳英

  Department Of Electronics Doshisha University

• 渡邊 芳英

  Department Of Mathematical Sciences Doshisha University

• 渡辺 扇之介

  Graduate School Of Science And Engineering Doshisha University

• 辻 雄太

  Graduate School of Science and Engineering, Doshisha University

• 渡邊 芳英

  Department of Mathematical Science,Doshisha University

関連論文

• Semi-Discrete発展方程式のbiーHamilton構造
• 整数計画法に基づくRNA間相互作用予測
• 整数計画法に基づくRNA間相互作用予測
• 2元線形符号の最尤復号におけるグレブナー基底を用いた方法 : BCH符号への応用
• トーリックイデアルのグレプナ基底計算アルゴリズム : 数式処理システムAsirへの実装
• AsirによるToric idealのグレブナー基底計算
• Asirによる有限群の不変式環の生成元の計算 (Computer Algebra : Algorithms, Implementations and Applications)
• Asirによる有限群の不変式環の生成元の計算
• 形式的線形化可能な発展方程式の数え挙げ
• 保存則による発展方程式の分類(数式処理の利用)I:形式的線形化可能系(非線型可積分系の研究の現状と展望)
• Recursion opertor[operator], Hereditary operator 及び Schouten bracket の計算について(数式処理と数学研究への応用)
• 最短路問題を用いたネットワークシンプレックス法のMATLABへの実装
• 当世学生試験事情
• 最大流問題とその双対問題
• ネットワークシンプレックス法における巡回を防ぐ方法
• 最尤復号に対する池上・楫アルゴリズムの計算量を減らすための試み
• 最短路問題と最長路問題

もっと見る 閉じる

スポンサーリンク