Cota de Hamming

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

Em matemática e ciência da computação, na área de teoria de códigos, a Cota de Hamming é uma limitação sobre os parâmetros de um código de blocos arbitrário: ela também é conhecida pelo nome de cota do empacotamento de esferas ou a cota do volume em uma interpretação em termos do empacotamento de esferas a métrica de Hamming no espaço de todas as palavras possíveis. Ela fornece uma limitação importante na eficiência com a qual um código corretor de erros pode utilizar o espaço do qual suas palavras fazem parte. Um código que atinge a cota de Hamming é dito um código perfeito.

Descrição da cota[editar | editar código-fonte]

Denote por o maior tamanho possível para um código de blocos -ário de comprimento e distância mínima de Hamming (um código de blocos -ário de comprimento é um subconjunto das strings de em que o alfabeto tem elementos)

Então:[1]

onde

Códigos perfeitos[editar | editar código-fonte]

Código que atingem a cota de Hamming são chamados de códigos perfeitos. Exemplos incluem os códigos de repetição binários de comprimento impar, códigos que tem apenas uma palavra, e código que consistem do conjunto inteiro. Estes são chamados geralmente de códigos perfeitos triviais.

Em 1973 foi demonstrado que qualquer código perfeito não trivial sobre um alfabeto cujo número de elementos é potência de algum primo tem os parâmetros de um código de Hamming ou de um Código de Golay.[2]

Um código perfeito pode ser interpretado como sendo um em que as bolas de raio t (na métrica de Hamming) centradas nas palavras do código preenche exatamente o espaço. Um código quase perfeito é aquele em que as bolas de raio t (na métrica de Hamming) centradas nas palavras do código são disjuntas e as bolas de raio t+1 cobrem o espaço, possivelmente com algumas sobreposições.[3]

Ver também[editar | editar código-fonte]

Notas e referências

  1. HEFEZ & VILLELA (2002), p. 181, Teorema 2.
  2. Hill (1988) p.102
  3. McWilliams e Sloane, p.19

Referências[editar | editar código-fonte]

Ligações externas[editar | editar código-fonte]