線形ブロック符号復号化のための分枝切除法における注釈

HORII Shunsuke; MATSUSHIMA Toshiyasu; HIRASAWA Shigeichi; HIRASAWA Shigeichi

文献

J-GLOBAL ID：201002284422773020 整理番号：10A1153777

線形ブロック符号復号化のための分枝切除法における注釈

A Note on the Branch-and-Cut Approach to Decoding Linear Block Codes

出版者サイト複写サービスで全文入手 {{ this.onShowCLink("http://jdream3.com/copy/?sid=JGLOBAL&noSystem=1&documentNoArray=10A1153777&COPY=1") }}
高度な検索・分析はJDreamⅢで {{ this.onShowJLink("http://jdream3.com/lp/jglobal/index.html?docNo=10A1153777&from=J-GLOBAL&jstjournalNo=F0699C") }}

著者 (4件)： , , ,
資料名：
巻： E93-A 号： 11 ページ： 1912-1917 発行年： 2010年11月01日
JST資料番号： F0699C ISSN： 0916-8508 資料種別：逐次刊行物 (A)
記事区分：原著論文発行国：日本 (JPN) 言語：英語 (EN)

ILP(整数線形計画法)として線形ブロック符号のML(最大尤度)復号化を検討した。一般的にこれはNPハード問題であるため,問題を近似的に解くためのアルゴリズム研究が盛んに行われている。最もポピュラーなアルゴリズムの一つはFeldmanにより提案されたLP(線形計画法)復号化である。LP復号化はLP緩和に基づいており,これはML復号化問題に対応したILPを近似的に解くための手法である。ILPを(近似的あるいは正確に)解くための先進型アルゴリズムは切除平面法および分枝限定法を含んでいる。これら手法の応用として,TaghaviらおよびYangらにより適応LP復号化および分枝限定復号化がそれぞれ提案された。ILPを解くためのもう一つの手法は分枝切除法であり,これは切除平面法および分枝限定法のハイブリッド型である。分枝切除法はILPを解くため広く用いられているが,本手法がML復号化問題のために良好に動作するかどうかは明白になっていない。本論文では,分枝切除法がML復号化問題にとってある程度有効であることを示した。さらに,分枝切除法をいくつかの技術的コンポーネントで構成し,そのアルゴリズムの性能をこれらコンポーネントの選択に依存させた。分枝切除法において技術的コンポーネントを選択できるかどうかを検討することは重要である。これら技術的コンポーネントの選択を起因とする相違を確認し,数値シミュレーションによりML復号化問題のためにどの手法が最も有効であるかを検討した。(翻訳著者抄録)

, , , , , , , , ,
, ,

符号理論

引用文献 (12件)：

GNU linear programming Kit. http://www.gnu.org/software/glpk
MARTIN, A. General mixed integer programming : Computational issues for branch-and-cut algorithms. Computational Combinatorial Optimization. 2001, 1-25
FELDMAN, J. Using linear programming to decoding binary linear codes. IEEE Trans. Inf. Theory. 2005, 51, 3, 954-972
DRAPER, S. C. ML decoding via mixed-integer adaptive linear programming. Proc. Int. Symp. Inf. Theory, Nice, France, June 2007. 2007, 1656-1660
YANG, K. Nonlinear programming approaches to decoding low-density parity-check codes. IEEE J. Sel. Areas Commun. 2006, 24, 8, 1603-1613

, , , ,

前のページに戻る