WEKO3
アイテム
最尤復号に対する池上・楫アルゴリズムの計算量を減らすための試み
https://doi.org/10.14988/pa.2017.0000013295
https://doi.org/10.14988/pa.2017.0000013295ee2c12cb-da1b-46b8-89d7-47e401a0db53
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
023054020010.pdf (692.8 kB)
|
|
| Item type | 紀要論文 / Departmental Bulletin Paper(1) | |||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2013-10-24 | |||||||||||||||||
| タイトル | ||||||||||||||||||
| タイトル | 最尤復号に対する池上・楫アルゴリズムの計算量を減らすための試み | |||||||||||||||||
| 言語 | ja | |||||||||||||||||
| タイトル | ||||||||||||||||||
| タイトル | サイユウ フクゴウ ニタイスル イケガミ・カジ アルゴリズム ノ ケイサンリョウ オ ヘラス タメノ ココロミ | |||||||||||||||||
| 言語 | ja-Kana | |||||||||||||||||
| タイトル | ||||||||||||||||||
| タイトル | An attempt to reduce the computational complexity in the Ikegami-Kaji algorithm for maximum likelihood decoding | |||||||||||||||||
| 言語 | en | |||||||||||||||||
| 言語 | ||||||||||||||||||
| 言語 | jpn | |||||||||||||||||
| キーワード | ||||||||||||||||||
| 主題 | グレブナー基底, 最尤復号, 池上・楫アルゴリズム, FGLMアルゴリズム Gröbner basis, maximum likelihood decoding, Ikegami-Kaji Algorithm, FGLM Algorithm |
|||||||||||||||||
| 資源タイプ | ||||||||||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||||||||||||
| 資源タイプ | departmental bulletin paper | |||||||||||||||||
| ID登録 | ||||||||||||||||||
| ID登録 | 10.14988/pa.2017.0000013295 | |||||||||||||||||
| ID登録タイプ | JaLC | |||||||||||||||||
| アクセス権 | ||||||||||||||||||
| アクセス権 | open access | |||||||||||||||||
| アクセス権URI | http://purl.org/coar/access_right/c_abf2 | |||||||||||||||||
| その他（別言語等）のタイトル | ||||||||||||||||||
| その他のタイトル | 最尤復号に対する池上楫アルゴリズムの計算量を減らすための試み | |||||||||||||||||
| 言語 | ja | |||||||||||||||||
| 著者 |
辻, 雄太
× 辻, 雄太× 吉水, 敏郎× 渡辺, 扇之介
WEKO
2484
× 渡邊, 芳英
WEKO
15621
|
|||||||||||||||||
| 著者所属 | ||||||||||||||||||
| 言語 | ja | |||||||||||||||||
| 値 | 辻, 雄太 / Graduate School of Science and Engineering, Doshisha University | |||||||||||||||||
| 著者所属 | ||||||||||||||||||
| 言語 | ja | |||||||||||||||||
| 値 | 渡辺, 扇之介 / Graduate School of Science and Engineering, Doshisha University | |||||||||||||||||
| 著者所属 | ||||||||||||||||||
| 言語 | ja | |||||||||||||||||
| 値 | 渡邊, 芳英 / 同志社大学理工学部数理システム学科 | |||||||||||||||||
| 抄録 | ||||||||||||||||||
| 内容記述タイプ | Abstract | |||||||||||||||||
| 内容記述 | 最尤復号とは,受信後と同じシンドロームを持つベクトルの中でハミング重みが最小の誤りベクトルを選ぶことによって実行される.したがって,最尤復号は有限体上の整数計画問題として定式化できる.整数計画問題をグレブナー基底を使って解く方法としてConti-Traversoのアルゴリズムが有名である.このアルゴリズムをもとに,池上と楫はグレブナー基底を用いて最尤復号を解くアルゴリズムを提唱した.しかし,池上・楫アルゴリズムにはグレブナー基底の計算量について,重大な問題点がある.本論文では,2元符号に付随するグレブナー基底の計算量を減らすため,2つの試みを行っている.1つはFaugéreらによるグレブナー基底変換を用いる方法で,もう1つはグレブナー基底の中で最尤復号に必要なものだけを取り出す方法である.2元符号に付随するイデアルの辞書式順序に関するグレブナー基底が容易に得られることは知られている.このグレブナー基底をFGLMアルゴリズムを用いて適合順序に関するグレブナー基底に変換する.この方法は我々の目的に有効ではなかった.2つ目の方法については,復号に有効であると思われる特定のグレブナー基底を見出すことができた. | |||||||||||||||||
| 言語 | ja | |||||||||||||||||
| 抄録 | ||||||||||||||||||
| 内容記述タイプ | Abstract | |||||||||||||||||
| 内容記述 | 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 Gröbner basis in the polynomial ideal theory. Ikegami and Kaji have presented the algorithm for solving MLD using Gröbner basis; which is an analogue of the Conti and Traverso's algorithm. Once we have the Gröbner 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 Gröbner basis. The present paper is an attempt to reduce the computational complexity of the Gröbner basis of the ideals associated with binary codes. We take two approaches: One is to apply the Gröbner basis conversion algorithm by Faugére et al. and the other is to determine the subset of binomials in the Gröbner basis that are indispensable for MLD. It is known that the Gröbner basis of the ideals associated with binary code with respect to the lexicographic ordering can be obtained easily. We convert this Gröbner basis to the Gröbner 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 Gröbner basis that seems to be effective for the decoding. | |||||||||||||||||
| 言語 | en | |||||||||||||||||
| 書誌情報 |
ja : 同志社大学理工学研究報告 en : The Science and Engineering Review of Doshisha University 巻 54, 号 2, p. 171-177, 発行日 2013-07-31 |
|||||||||||||||||
| 出版者 | ||||||||||||||||||
| 出版者 | 同志社大学理工学研究所 | |||||||||||||||||
| 言語 | ja | |||||||||||||||||
| 出版者（英） | ||||||||||||||||||
| 出版者 | Science and Engineering Research Institute of Doshisha University | |||||||||||||||||
| 言語 | en | |||||||||||||||||
| ISSN | ||||||||||||||||||
| 収録物識別子タイプ | PISSN | |||||||||||||||||
| 収録物識別子 | 00368172 | |||||||||||||||||
| 書誌レコードID | ||||||||||||||||||
| 収録物識別子タイプ | NCID | |||||||||||||||||
| 収録物識別子 | AN00165868 | |||||||||||||||||
| 権利者情報 | ||||||||||||||||||
| 権利者識別子Scheme | AID | |||||||||||||||||
| 権利者識別子URI | https://ci.nii.ac.jp/author/DA03974933 | |||||||||||||||||
| 権利者識別子 | DA03974933 | |||||||||||||||||
| 権利者名 | 同志社大学理工学研究所 | |||||||||||||||||
| 言語 | ja | |||||||||||||||||
| 権利者名 | Science and Engineering Research Institute of Doshisha University | |||||||||||||||||
| 言語 | en | |||||||||||||||||
| 関連サイト | ||||||||||||||||||
| 関連タイプ | isFormatOf | |||||||||||||||||
| 識別子タイプ | URI | |||||||||||||||||
| 関連識別子 | https://doors.doshisha.ac.jp/opac/opac_link/bibid/SB00960326/?lang=0 | |||||||||||||||||
| 言語 | ja | |||||||||||||||||
| 関連名称 | 掲載刊行物所蔵情報へのリンク ／ Link to Contents | |||||||||||||||||
| 出版タイプ | ||||||||||||||||||
| 出版タイプ | VoR | |||||||||||||||||
| 出版タイプResource | http://purl.org/coar/version/c_970fb48d4fbd8a85 | |||||||||||||||||
| 日本十進分類法 | ||||||||||||||||||
| 主題Scheme | NDC | |||||||||||||||||
| 主題 | 411.8 | |||||||||||||||||
