Cota de Hamming

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

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 ${𝒜}_q^n\text{,}$ em que o alfabeto ${𝒜}_q$ tem $q$ elementos)

Então:

$A_q(n,d)\le \frac{q^n}{\sum _{k=0}^t(\genfrac{}{}{0ex}{}{n}{k})(q-1{)}^k}$

onde

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

Códigos perfeitos

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.

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.

Ver também

• Cota de Griesmer
• Cota de Singleton
• Cota de Gilbert-Varshamov
• Cota de Plotkin
• Cota de Johnson

Referências

• Predefinição:Citar livro
• Predefinição:Citar livro
• Predefinição:Citar livro
• Predefinição:Citar livro
• Predefinição:Citar livro
• Predefinição:Citar periódico

Ligações externas

• Predefinição:Link