Códigos De Hamming
Artigo: Códigos De Hamming. Pesquise 862.000+ trabalhos acadêmicosPor: manitiba • 25/2/2015 • Artigo • 353 Palavras (2 Páginas) • 243 Visualizações
Códigos de Hamming
Um código de Hamming adiciona um bloco de paridade a um bloco de dados, de forma a que, caso ocorram erros de transmissão, seja possível detectar ou corrigir erros do bloco transmitido.
É formado da seguinte maneira, constrói-se uma matriz H cujas colunas são formadas por todos os vetores não nulos de dimensão p = c – d. O código de Hamming consiste no espaço nulo da matriz H, i.e., as palavras de código verificam Hc=0.
Exemplo:
Código (3,1) -> 1 bit dados + 2 bits redundância
H=[0 1 1
1 0 1]
O espaço nulo de H é composto pelos vetores [0 0 0] e [1 1 1].
Detecção de erros
Como as palavras de código pertencem ao espaço nulo de H, é muito simples verificar se houve erro de transmissão: Basta verificar se a palavra recebida
pertence ao espaço nulo:
Se Hr = 0, então r pertence ao espaço nulo --> OK!
Se Hr ≠ 0, então r não pertence a null(H) --> ERRO!
Exemplo:
Se c=000 e r=000, Hr = [0 0]' --> sem erros
Se c=000 e r=001, Hr = [1 1]' --> erros detectados
Se c=000 e r=101, Hr = [1 0]' --> erros detectados
Se c=000 e r=111, Hr = [0 0]' --> sem erros
Note que se existirem 3 erros é recebida uma palavra válida e não são detectados erros.
Escolhendo o número de bits de paridade:
O número de colunas de H é igual a 2p-1, que deve ser compatível com a dimensão do vetor r. Então d+p = 2p-1
Regra de Hamming: d - p -1 ≤2p
Se a igualdade se verificar, diz-se que é um código perfeito. Os códigos de Hamming designam-se pelo par (c,d)
Exemplos:
p d c código
3 4 7 (7,4)
4 11 15 (15,11)
5 26 31 (31,26)
...