- [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 | 2010 |
| Format | Journal |
| Category | Channel coding |
| Jounal Name | IEICE Trans. Fundamentals |
| Jounal Page | vol.E93-A, no.11, pp.912-1917 |
| Published Year | 2010 |
| Published Month | 11 |
| 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 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 branch-and-bound method. As applications of these methods, adaptive LP decoding and branch-and-bound decoding have been proposed by Taghavi et al. and Yang et al., respectively. 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. The branch-and-cut method is widely used to solve ILP, however, it is unobvious that the method works well for the ML decoding problem. In this paper, we show that the branch-and-cut method is certainly effective for the ML decoding problem. Furthermore 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. We see the differences caused by the selection of those technical components and consider which scheme is most effective for the ML decoding problem through numerical simulations. |
| Note （English） |
3 |
| Manuscript | |
| Presentation |
Involved Papers
- A New Latent Class Model for Analysis of Purchasing and Browsing Histories on EC Sites
- Linear Programming Decoding of Binary Linear Codes for Symbol-Pair Read Channels
- A Heuristic Search Method with the Reduced List of Test Error Patterns for Maximum Likelihood Decoding
- Parallel Architecture for Generalized LFSR in LSI Built-In Self Testing
- Parallel Encoder and Decoder Architecture for Cyclic Codes
- A Generalization of B.S.Clarke and A.R.Barron's Asymptotics of Bayes Codes for FSMX Sources
- Almost Sure and Mean Convergence of Extended Stochastic Complexity
- A Source Model with Probability Distribution over Word Set and Recurrence Time Theorem
- Properties of a Word-Valued Source with a Non-prefix-free Word Set
- Asymptotics of Bayesian Inference for a Class of Probabilistic Models under Misspecification
- An Analysis of Slepian-Wolf Coding Problem Based on the Asymptotic Normality
- On the Overflow Probability of Fixed - to - Variable Length Codes with Side Information
- A Study on the Degrees of Freedom in an Experimental Design Model Based on an Orthonormal System
- A Note on Relation between the Fourier Coefficients and the Effects in the Experimental Design
- A Note on Linear Programming Based Communication Receivers
- Asymptotic property of universal lossless coding for independent piecewise identically distributed sources
- A Note on the Inference Algorithm on the Factor Graph based on the Linear Programming (in Japanese)
- A Note on the Linear Programming Decoding of Binary Linear Codes for Multiple-Access Channel
- A Note on Automatic Construction Algorithms for Orthogonal Designs of Experiments Using Error-correcting Codes
- Linear Programming Decoding of Binary Linear Codes for Multiple-Access Channel (in Japanese)
