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 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
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
- Cota de Griesmer
- Cota de Singleton
- Cota de Gilbert-Varshamov
- Cota de Plotkin
- Cota de Johnson
Notas e referências
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
Ligações externas
- «Uma wiki dedicada à teoria de códigos» (em inglês)