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 \ A_q(n,d) o maior tamanho possível para um código de blocos q-ário \ C de comprimento n e distância mínima de Hamming d (um código de blocos q-ário de comprimento n é um subconjunto das strings de \mathcal{A}_q^n\text{,} em que o alfabeto \mathcal{A}_q tem q elementos)

Então:[1]


\ A_q(n,d) \leq \frac{q^n}{\sum_{k=0}^t \binom{n}{k}(q-1)^k}

onde

t=\left\lfloor\frac{d-1}{2}\right\rfloor.

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 (F_{q})^{n} 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]