- [Home]
- [Research achievement]
- [Research achievement detail]
Title | A Note on the Branch-and-Cut Approach to Decoding Linear Block Codes (in Japanese) |
---|---|
Authors | Shunsuke Horii 、Toshiyasu Matsushima 、Shigeichi Hirasawa |
Released Year | 2009 |
Format | Conference |
Category | Channel coding |
Jounal Name | Proceedings of the 32th Symposium on Information Theory and its Applications |
Jounal Page | pp.569-573 |
Published Year | 2009 |
Published Month | 12 |
Abstract (English) |
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. Advanced algorithms for solving ILP (approximately or exactly) include cutting-plane method and branch-and-bound method. As applications of these methods, adaptive LP decoding and branch-and-bound decoding have been proposed. Another method for solving ILP is the branch-and-cut method, which is a hybrid of cutting-plane and branch-and-bound methods. In this paper, we describe the branch-and-cut based ML decoding algorithm. We construct a generalized framework for the branch-and-cut based ML decoding and compare some algorithms with numerical simulations. |
Note (English) |
1 |
Manuscript | Download |
Presentation |