A funcionalidade de pesquisa está em construção.
A funcionalidade de pesquisa está em construção.

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 Note on the Branch-and-Cut Approach to Decoding Linear Block Codes Uma nota sobre a abordagem branch-and-cut para decodificação de códigos de blocos lineares

Shunsuke HORII, Toshiyasu MATSUSHIMA, Shigeichi HIRASAWA

  • Exibições de texto completo

    0

  • Cite isto

Resumo:

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.

Publicação
IEICE TRANSACTIONS on Fundamentals Vol.E93-A No.11 pp.1912-1917
Data de publicação
2010/11/01
Publicitada
ISSN online
1745-1337
DOI
10.1587/transfun.E93.A.1912
Tipo de Manuscrito
Special Section PAPER (Special Section on Information Theory and Its Applications)
Categoria
Teoria da Codificação

autores

Palavra-chave