2元線形符号の最尤復号におけるグレブナー基底を用いた方法 : BCH符号への応用
スポンサーリンク
概要
- 論文の詳細を見る
グレブナー基底を用いた整数計画のアルゴリズムとして、コンティとトラベルソのアルゴリズムが有名である。池上と楫はグレブナー基底を用いた2元線形符号の最尤復号のアルゴリズムを提示したが、それはコンティとトラベルソのアルゴリズムの類似物である。本論文の目的は計算機実験により彼らのアルゴリズムの有効性を検証することである。我々は様々なパラメータをもつ(2元)BCH符号に対して符号に付随するイデアルのグレブナー基底を計算する。ここで用いられるアルゴリズムは二つあり、一つは池上と楫による最初のアルゴリズムであり、もう一つは最近見出された改良アルゴリズムである。実験に用いる数式処理システムはAsir とSingular である。改良アルゴリズムにおいては、変数の消去計算が不要であり、最初のアルゴリズムと比べるとグレブナー基底を効率よく計算することが期待される。しかしながら、計算機実験の結果によれば、二つのアルゴリズムにはほとんど差はなかった。
- 同志社大学の論文
著者
-
渡邊 芳英
Department Of Electronics Doshisha University
-
吉武 純子
The Japan Research Institute Ltd.
-
池上 大介
National Institute of Advanced Industrial Science and Technology
関連論文
- 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への実装
- 当世学生試験事情
- 最大流問題とその双対問題
- ネットワークシンプレックス法における巡回を防ぐ方法
- 最尤復号に対する池上・楫アルゴリズムの計算量を減らすための試み
- 最短路問題と最長路問題