{"created":"2023-07-27T07:47:47.234548+00:00","id":22424,"links":{},"metadata":{"_buckets":{"deposit":"bb91c7c3-6064-454f-a856-39111d7f02b4"},"_deposit":{"created_by":20,"id":"22424","owners":[20],"pid":{"revision_id":0,"type":"depid","value":"22424"},"status":"published"},"_oai":{"id":"oai:doshisha.repo.nii.ac.jp:00022424","sets":["4251:8393:8394:8395:8402","8:3372:3812:3819"]},"author_link":["19362","19363","2484","15621"],"item_1693811493084":{"attribute_name":"出版タイプ","attribute_value_mlt":[{"subitem_version_resource":"http://purl.org/coar/version/c_970fb48d4fbd8a85","subitem_version_type":"VoR"}]},"item_1694490770713":{"attribute_name":"権利者情報","attribute_value_mlt":[{"nameIdentifiers":[{"nameIdentifier":"DA03974933","nameIdentifierScheme":"AID"}],"rightHolderNames":[{"rightHolderLanguage":"ja","rightHolderName":"同志社大学理工学研究所"},{"rightHolderLanguage":"en","rightHolderName":"Science and Engineering Research Institute of Doshisha University"}]}]},"item_1_alternative_title_2":{"attribute_name":"その他（別言語等）のタイトル","attribute_value_mlt":[{"subitem_alternative_title":"最尤復号に対する池上楫アルゴリズムの計算量を減らすための試み","subitem_alternative_title_language":"ja"}]},"item_1_biblio_info_14":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicIssueDates":{"bibliographicIssueDate":"2013-07-31","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"2","bibliographicPageEnd":"177","bibliographicPageStart":"171","bibliographicVolumeNumber":"54","bibliographic_titles":[{"bibliographic_title":"同志社大学理工学研究報告","bibliographic_titleLang":"ja"},{"bibliographic_title":"The Science and Engineering Review of Doshisha University","bibliographic_titleLang":"en"}]}]},"item_1_description_12":{"attribute_name":"抄録","attribute_value_mlt":[{"subitem_description":"最尤復号とは,受信後と同じシンドロームを持つベクトルの中でハミング重みが最小の誤りベクトルを選ぶことによって実行される.したがって,最尤復号は有限体上の整数計画問題として定式化できる.整数計画問題をグレブナー基底を使って解く方法としてConti-Traversoのアルゴリズムが有名である.このアルゴリズムをもとに,池上と楫はグレブナー基底を用いて最尤復号を解くアルゴリズムを提唱した.しかし,池上・楫アルゴリズムにはグレブナー基底の計算量について,重大な問題点がある.本論文では,2元符号に付随するグレブナー基底の計算量を減らすため,2つの試みを行っている.1つはFaugéreらによるグレブナー基底変換を用いる方法で,もう1つはグレブナー基底の中で最尤復号に必要なものだけを取り出す方法である.2元符号に付随するイデアルの辞書式順序に関するグレブナー基底が容易に得られることは知られている.このグレブナー基底をFGLMアルゴリズムを用いて適合順序に関するグレブナー基底に変換する.この方法は我々の目的に有効ではなかった.2つ目の方法については,復号に有効であると思われる特定のグレブナー基底を見出すことができた.","subitem_description_language":"ja","subitem_description_type":"Abstract"},{"subitem_description":"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.","subitem_description_language":"en","subitem_description_type":"Abstract"}]},"item_1_description_25":{"attribute_name":"フォーマット","attribute_value_mlt":[{"subitem_description":"application/pdf","subitem_description_type":"Other"}]},"item_1_identifier_registration":{"attribute_name":"ID登録","attribute_value_mlt":[{"subitem_identifier_reg_text":"10.14988/pa.2017.0000013295","subitem_identifier_reg_type":"JaLC"}]},"item_1_publisher_15":{"attribute_name":"出版者","attribute_value_mlt":[{"subitem_publisher":"同志社大学理工学研究所","subitem_publisher_language":"ja"}]},"item_1_publisher_16":{"attribute_name":"出版者（英）","attribute_value_mlt":[{"subitem_publisher":"Science and Engineering Research Institute of Doshisha University","subitem_publisher_language":"en"}]},"item_1_relation_24":{"attribute_name":"関連サイト","attribute_value_mlt":[{"subitem_relation_name":[{"subitem_relation_name_language":"ja","subitem_relation_name_text":"掲載刊行物所蔵情報へのリンク ／ Link to Contents"}],"subitem_relation_type":"isFormatOf","subitem_relation_type_id":{"subitem_relation_type_id_text":"https://doors.doshisha.ac.jp/opac/opac_link/bibid/SB00960326/?lang=0","subitem_relation_type_select":"URI"}}]},"item_1_source_id_17":{"attribute_name":"ISSN","attribute_value_mlt":[{"subitem_source_identifier":"00368172","subitem_source_identifier_type":"PISSN"}]},"item_1_source_id_19":{"attribute_name":"書誌レコードID","attribute_value_mlt":[{"subitem_source_identifier":"AN00165868","subitem_source_identifier_type":"NCID"}]},"item_1_subject_27":{"attribute_name":"日本十進分類法","attribute_value_mlt":[{"subitem_subject":"411.8","subitem_subject_scheme":"NDC"}]},"item_1_text_8":{"attribute_name":"著者所属","attribute_value_mlt":[{"subitem_text_language":"ja","subitem_text_value":"辻, 雄太 / Graduate School of Science and Engineering, Doshisha University"},{"subitem_text_language":"ja","subitem_text_value":"渡辺, 扇之介 / Graduate School of Science and Engineering, Doshisha University"},{"subitem_text_language":"ja","subitem_text_value":"渡邊, 芳英 / 同志社大学理工学部数理システム学科"}]},"item_access_right":{"attribute_name":"アクセス権","attribute_value_mlt":[{"subitem_access_right":"open access","subitem_access_right_uri":"http://purl.org/coar/access_right/c_abf2"}]},"item_creator":{"attribute_name":"著者","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"辻, 雄太","creatorNameLang":"ja"},{"creatorName":"ツジ, ユウタ","creatorNameLang":"ja-Kana"},{"creatorName":"Tsuji, Yuta","creatorNameLang":"en"}],"nameIdentifiers":[{},{}]},{"creatorNames":[{"creatorName":"吉水, 敏郎","creatorNameLang":"ja"},{"creatorName":"ヨシミズ, トシロウ","creatorNameLang":"ja-Kana"},{"creatorName":"Yoshimizu, Toshirou","creatorNameLang":"en"}],"nameIdentifiers":[{},{}]},{"creatorNames":[{"creatorName":"渡辺, 扇之介","creatorNameLang":"ja"},{"creatorName":"ワタナベ, センノスケ","creatorNameLang":"ja-Kana"},{"creatorName":"Watanabe, Sennosuke","creatorNameLang":"en"}],"nameIdentifiers":[{},{},{}]},{"creatorNames":[{"creatorName":"渡邊, 芳英","creatorNameLang":"ja"},{"creatorName":"ワタナベ, ヨシヒデ","creatorNameLang":"ja-Kana"},{"creatorName":"Watanabe, Yoshihide","creatorNameLang":"en"}],"nameIdentifiers":[{},{},{},{}]}]},"item_files":{"attribute_name":"ファイル情報","attribute_type":"file","attribute_value_mlt":[{"accessrole":"open_date","date":[{"dateType":"Available","dateValue":"2013-11-12"}],"displaytype":"detail","filename":"023054020010.pdf","filesize":[{"value":"692.8 kB"}],"format":"application/pdf","licensetype":"license_note","mimetype":"application/pdf","url":{"label":"023054020010.pdf","url":"https://doshisha.repo.nii.ac.jp/record/22424/files/023054020010.pdf"},"version_id":"485fed59-2d18-4b8e-8286-e972814681be"}]},"item_keyword":{"attribute_name":"キーワード","attribute_value_mlt":[{"subitem_subject":"グレブナー基底","subitem_subject_language":"ja","subitem_subject_scheme":"Other"},{"subitem_subject":"最尤復号","subitem_subject_language":"ja","subitem_subject_scheme":"Other"},{"subitem_subject":"池上・楫アルゴリズム","subitem_subject_language":"ja","subitem_subject_scheme":"Other"},{"subitem_subject":"FGLMアルゴリズム","subitem_subject_language":"ja","subitem_subject_scheme":"Other"},{"subitem_subject":"Gröbner basis","subitem_subject_language":"en","subitem_subject_scheme":"Other"},{"subitem_subject":"maximum likelihood decoding","subitem_subject_language":"en","subitem_subject_scheme":"Other"},{"subitem_subject":"Ikegami-Kaji Algorithm","subitem_subject_language":"en","subitem_subject_scheme":"Other"},{"subitem_subject":"FGLM Algorithm","subitem_subject_language":"en","subitem_subject_scheme":"Other"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"jpn"}]},"item_resource_type":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"resourcetype":"departmental bulletin paper","resourceuri":"http://purl.org/coar/resource_type/c_6501"}]},"item_title":"最尤復号に対する池上・楫アルゴリズムの計算量を減らすための試み","item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"最尤復号に対する池上・楫アルゴリズムの計算量を減らすための試み","subitem_title_language":"ja"},{"subitem_title":"サイユウ フクゴウ ニタイスル イケガミ・カジ アルゴリズム ノ ケイサンリョウ オ ヘラス タメノ ココロミ","subitem_title_language":"ja-Kana"},{"subitem_title":"An attempt to reduce the computational complexity in the Ikegami-Kaji algorithm for maximum likelihood decoding","subitem_title_language":"en"}]},"item_type_id":"1","owner":"20","path":["3819","8402"],"pubdate":{"attribute_name":"PubDate","attribute_value":"2013-10-24"},"publish_date":"2013-10-24","publish_status":"0","recid":"22424","relation_version_is_last":true,"title":["最尤復号に対する池上・楫アルゴリズムの計算量を減らすための試み"],"weko_creator_id":"20","weko_shared_id":-1},"updated":"2023-12-06T00:47:23.177422+00:00"}