Raio de empacotamento de códigos poset / The packing radius of poset codes
AUTOR(ES)
Rafael Gregorio Lucas D Oliveira
FONTE
IBICT - Instituto Brasileiro de Informação em Ciência e Tecnologia
DATA DE PUBLICAÇÃO
08/08/2012
RESUMO
Até o trabalho presente, só era conhecido o raio de empacotamento de um código poset nos casos do poset ser uma cadeia, hierárquico, a união disjunta de cadeias do mesmo tamanho, e para algumas famílias de códigos. Nosso objetivo é abordar o caso geral de um poset qualquer. Para isso, iremos dividir o problema em dois. A primeira parte consiste em encontrar o raio de empacotamento de um único vetor. Veremos que este problema é equivalente à uma generalização de um problema NP-difícil famoso conhecido como o problema da partição". Veremos então os principais resultados conhecidos sobre este problema dando atenção especial aos algoritmos para resolvê-lo. A receita principal destes algoritmos é o método da diferenciação, e sendo assim, iremos estendê-la para o caso geral. A segunda parte consiste em encontrar o vetor que determina o raio de empacotamento do código. Para isso, mostraremos como é as vezes possível comparar o raio de empacotamento de dois vetores sem calculá-los explicitamente.
ASSUNTO(S)
códigos corretores de erros (teoria da informação) metricas sobre ordens parciais ordered sets error-correcting codes (information theory) poset metric conjuntos ordenados
