The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
A decodificação de máxima verossimilhança (ML) de códigos de bloco lineares pode ser considerada como uma programação linear inteira (ILP). Por se tratar de um problema NP-difícil em geral, existem muitas pesquisas sobre algoritmos para resolver aproximadamente o problema. Um dos algoritmos mais populares é a decodificação de programação linear (LP) proposta por Feldman et al. A decodificação LP é baseada na relaxação LP, que é um método para resolver aproximadamente o ILP correspondente ao problema de decodificação ML. Algoritmos avançados para resolver ILP (aproximadamente ou exatamente) incluem o método do plano de corte e o método branch-and-bound. Como aplicações desses métodos, a decodificação LP adaptativa e a decodificação branch-and-bound foram propostas por Taghavi et al. e Yang et al., respectivamente. Outro método para resolver ILP é o método branch-and-cut, que é um híbrido dos métodos de plano de corte e branch-and-bound. O método branch-and-cut é amplamente utilizado para resolver ILP, no entanto, não é óbvio que o método funcione bem para o problema de decodificação de ML. Neste artigo, mostramos que o método branch-and-cut é certamente eficaz para o problema de decodificação de ML. Além disso, o método branch-and-cut consiste em alguns componentes técnicos e o desempenho do algoritmo depende da seleção desses componentes. É importante considerar como selecionar os componentes técnicos no método branch-and-cut. Vemos as diferenças causadas pela seleção desses componentes técnicos e consideramos qual esquema é mais eficaz para o problema de decodificação de ML através de simulações numéricas.
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copiar
Shunsuke HORII, Toshiyasu MATSUSHIMA, Shigeichi HIRASAWA, "A Note on the Branch-and-Cut Approach to Decoding Linear Block Codes" in IEICE TRANSACTIONS on Fundamentals,
vol. E93-A, no. 11, pp. 1912-1917, November 2010, doi: 10.1587/transfun.E93.A.1912.
Abstract: 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. 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 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E93.A.1912/_p
Copiar
@ARTICLE{e93-a_11_1912,
author={Shunsuke HORII, Toshiyasu MATSUSHIMA, Shigeichi HIRASAWA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A Note on the Branch-and-Cut Approach to Decoding Linear Block Codes},
year={2010},
volume={E93-A},
number={11},
pages={1912-1917},
abstract={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. 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 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.},
keywords={},
doi={10.1587/transfun.E93.A.1912},
ISSN={1745-1337},
month={November},}
Copiar
TY - JOUR
TI - A Note on the Branch-and-Cut Approach to Decoding Linear Block Codes
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1912
EP - 1917
AU - Shunsuke HORII
AU - Toshiyasu MATSUSHIMA
AU - Shigeichi HIRASAWA
PY - 2010
DO - 10.1587/transfun.E93.A.1912
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E93-A
IS - 11
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - November 2010
AB - 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. 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 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.
ER -