タイトル | A Note on the Branch-and-Cut Approach to Decoding Linear Block Codes |
---|---|
著者 | 堀井俊佑 、松嶋敏泰 、平澤茂一 |
年度 | 2009 |
形式 | 国際学会 |
分野 | 通信路符号化 |
掲載雑誌名 | Proc. of 2010 International Workshop on Nonlinear Circuits, Communication and Signal Processing (NCSP'10) |
掲載号・ページ | 321-324, Hawaii, USA |
掲載年 | 2010 |
掲載月 | 3 |
アブスト (日本語) |
学会名:2010 RISP International Workshop on Nonlinear Circuits, Communications and Signal Processing 日程:March 3-5, 2010 場所:Waikiki Beach Marriott Resort & Spa, Honolulu, Hawaii, USA |
アブスト (英語) |
Maximum likelihood (ML) decoding of linear block codes can be considered as an integer linear programming (ILP). Since it is an NP-hard problem in general, there are many researches about the algorithms to approximately solve the problem. One of the most popular algorithms is linear programming (LP) decoding proposed by Feldman et al.. LP decoding is based on the LP relaxation, which is a method to approximately solve the ILP corresponding to the ML decoding problem. Advanced algorithms for solving ILP (approximately or exactly) include cutting-plane method and branchand- bound method. Another method for solving ILP is the branch-and-cut method, which is a hybrid of cutting-plane and branch-andbound methods. In this paper, we describe the branch-and-cut based ML decoding algorithm. The branch-and-cut method is widely used to solve ILP. The branch-and-cut method consists of some technical components and the performance of the algorithm depends on the selection of these components. It is important to consider how to select the technical components in the branch-and-cut method. We construct a generalized framework for the branch-and-cut based ML decoding and compare some algorithms with numerical simulations. |
備考 (日本語) |
1 |
備考 (英語) |
1 |
論文原稿 | |
発表資料 |