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.

Denote por ${\displaystyle \ A_{q}(n,d)}$ o maior tamanho possível para um código de blocos ${\displaystyle q}$-ário ${\displaystyle \ C}$ de comprimento ${\displaystyle n}$ e distância mínima de Hamming ${\displaystyle d}$ (um código de blocos ${\displaystyle q}$-ário de comprimento ${\displaystyle n}$ é um subconjunto das strings de ${\displaystyle {\mathcal {A}}_{q}^{n}{\text{,}}}$ em que o alfabeto ${\displaystyle {\mathcal {A}}_{q}}$ tem ${\displaystyle q}$ elementos)

Então:^[1]

${\displaystyle \ A_{q}(n,d)\leq {\frac {q^{n}}{\sum _{k=0}^{t}{\binom {n}{k}}(q-1)^{k}}}}$

onde

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

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 ${\displaystyle (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]

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

Notas e referências

• Raymond Hill (1988). A First Course In Coding Theory. [S.l.]: Oxford University Press. ISBN 0-19-853803-0 
• F.J. MacWilliams; N.J.A. Sloane (1977). The Theory of Error-Correcting Codes. [S.l.]: North-Holland. ISBN 0-444-85193-3  A referência emprega parâmetros obsoletos |coautor= (ajuda)
• HEFEZ, Abramo; VILLELA, Maria Lúcia T. (2002). Códigos Corretores de Erros. Rio de Janeiro: IMPA. ISBN 85-244-0169-9  !CS1 manut: Nomes múltiplos: lista de autores (link)
• Vera Pless (1982). Introduction to the Theory of Error-Correcting Codes. [S.l.]: John Wiley & Sons. ISBN 0-471-08684-3 
• J.H. van Lint (1992). Introduction to Coding Theory. Col: GTM. 86 2nd ed. [S.l.]: Springer-Verlag. ISBN 3-540-54894-7 
• J.H. van Lint (1975). «A survey of perfect codes». Rocky Mountain Math. J. 5: 199–224. doi:10.1216/RMJ-1975-5-2-199 

• «Uma wiki dedicada à teoria de códigos» (em inglês)