@article{oai:doshisha.repo.nii.ac.jp:00022424, author = {辻, 雄太 and Tsuji, Yuta and 吉水, 敏郎 and Yoshimizu, Toshirou and 渡辺, 扇之介 and Watanabe, Sennosuke and 渡邊, 芳英 and Watanabe, Yoshihide}, issue = {2}, journal = {同志社大学理工学研究報告, The Science and Engineering Review of Doshisha University}, month = {Jul}, note = {最尤復号とは,受信後と同じシンドロームを持つベクトルの中でハミング重みが最小の誤りベクトルを選ぶことによって実行される.したがって,最尤復号は有限体上の整数計画問題として定式化できる.整数計画問題をグレブナー基底を使って解く方法としてConti-Traversoのアルゴリズムが有名である.このアルゴリズムをもとに,池上と楫はグレブナー基底を用いて最尤復号を解くアルゴリズムを提唱した.しかし,池上・楫アルゴリズムにはグレブナー基底の計算量について,重大な問題点がある.本論文では,2元符号に付随するグレブナー基底の計算量を減らすため,2つの試みを行っている.1つはFaugéreらによるグレブナー基底変換を用いる方法で,もう1つはグレブナー基底の中で最尤復号に必要なものだけを取り出す方法である.2元符号に付随するイデアルの辞書式順序に関するグレブナー基底が容易に得られることは知られている.このグレブナー基底をFGLMアルゴリズムを用いて適合順序に関するグレブナー基底に変換する.この方法は我々の目的に有効ではなかった.2つ目の方法については,復号に有効であると思われる特定のグレブナー基底を見出すことができた., 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., application/pdf}, pages = {171--177}, title = {最尤復号に対する池上・楫アルゴリズムの計算量を減らすための試み}, volume = {54}, year = {2013}, yomi = {ツジ, ユウタ and ヨシミズ, トシロウ and ワタナベ, センノスケ and ワタナベ, ヨシヒデ} }