Código de Hamming

O código de Hamming é um código de bloco linear, foi desenvolvido por Richard Hamming, é utilizado no processamento de sinal e nas telecomunicações. A sua utilização permite a transferência e armazenamento de dados de forma segura e eficiente.

Nas telecomunicações os códigos de Hamming utilizados são generalizações do Hamming (7,4). Estes podem detectar erros até dois bits e corrigir até um bit. Em contraste, o código de paridade não pode corrigir erros, e pode detectar apenas um número impar de erros. Devido à sua simplicidade os códigos Hamming são amplamente utilizados na memória dos computadores (ECC). Neste contexto é frequente utilizar um código de Hamming estendido com um bit de paridade extra.

Em termos matemáticos, códigos de Hamming são uma classe de códigos lineares binários. Para cada inteiro $r\geq 2$ existe um código de comprimento de bloco $n=2^{r}-1$ e com comprimento de mensagem $k=2^{r}-r-1$ . Por isso, a taxa de códigos de Hamming é $R=k/n=1-r/(2^{r}-1)$ que é a mais alta possível para códigos com distância $3$ e de comprimento de bloco $2^{r}-1$ . A matriz de paridade de um código de Hamming é construída listando todas as colunas de comprimento $r$ que são linearmente independentes. Os códigos de Hamming são especiais porque são códigos perfeitos, isto é, alcançam a taxa mais alta para os códigos com o seu comprimento de bloco e uma distância mínima de $3$ . ^[1]

História editar

Richard Hamming trabalhou em 1940 na Bell Labs para implementar o computador Bell Model V – dispositivo electromecânico baseado em relays. O modo de Input de dados era efectuado por cartões perfurados, os quais geravam constantemente erros de leitura. Tendo em conta este facto frustrante, Hamming decidiu, durante os anos seguintes, investigar o problema de correção de erros e em 1950 publicou um algoritmo chamado “Hamming Code” o qual ainda é usado correntemente em inúmeras áreas da Computação.

Códigos anteriores a Hamming editar

Os códigos de correção de erros existiam muito antes dos códigos de Hamming, mas nenhum era tão eficaz como o código de Hamming para a mesma quantidade de informação.

Paridade editar

A paridade adiciona um bit que indica se o número de bits com o valor 1 nos dados é par ou ímpar. Se um número ímpar de bits for alterado durante a transmissão, a paridade será alterada e o erro pode ser detectado (Note-se que o bit que foi alterado pode ter sido o bit de paridade em si!). A convenção mais comum é que o valor de paridade 1 indica que existe um número ímpar de 1 nos dados e um valor de paridade 0 indica que há um número par de 1. Se o número de bits alterados for par, o bit de verificação será válido e o erro não será detectado. Além disso, a paridade não indica que bit contém o erro mesmo quando pode detectá-lo. Os dados devem ser descartados e retransmitidos novamente.

Código dois-de-cinco editar

O código dois-de-cinco é um esquema de codificação que utiliza cinco dígitos, três 0 e dois 1. Isto proporciona 10 combinações possíveis, o suficiente para representar os dígitos 0-9. Este método pode detectar todos os erros de um bit e todos os erros de um número de bits ímpar. No entanto, não permite corrigir esses erros.

Repetição editar

Outro código em uso na altura consistia em repetir cada bit de dados várias vezes a fim de garantir sua boa transmissão. Por exemplo, se o bit de dados a ser enviado for 1, o código de repetição com n=3 iria enviar "111". Se os três bits recebidos não forem idênticos, ocorreu um erro. Se o canal tiver pouco ruído, na maioria das vezes apenas um bit será alterado em cada trio. Assim, 001, 010, e 100 correspondem a um bit 0, ao passo que 110, 101, e 011 correspondem a um bit 1, como se os bits fossem "votos" que indicam o sentido do bit original. Um código com a capacidade de reconstituir a mensagem original, na presença de erros, é conhecido como um código de correção de erros. Este código de tripla repetição é na realidade o mais curto código de Hamming, com dois bits de paridade e um bits de dados. Esses códigos não consegue reparar corretamente todos os erros. No nosso exemplo, se o canal alterar dois bits e o receptor obtiver 001, o sistema detecta o erro, mas conclui que o bit original era 0, o que está incorreto. Se aumentarmos o número de repetições para quatro, podemos detectar todos os erros de dois bits, mas não pode corrigi-los (os votos "empatam"); com cinco repetições, podemos corrigir todos os erros de dois bits, mas não todos os erros de três bits. Além disso, o código de repetição é extremamente ineficiente, reduzindo o rendimento em três vezes, no nosso caso; e a eficiência cai drasticamente à medida que aumentamos o número de vezes que cada bit é repetido, a fim de detectar e corrigir mais erros.

Códigos de Hamming editar

Se incluirmos na mensagem bits adicionais para correção de erros, e se esses bits forem organizados de forma que bits incorretos produzam erros diferentes, então podemos identificar os bits com erro. Numa mensagem de sete bits, há sete erros de um bit possíveis, assim, com três bits de controle seria eventualmente possível especificar, não apenas que ocorreu um erro, mas também que bit causou o erro.

Hamming estudou os sistemas de codificação existentes, incluindo o dois-de-cinco, e generalizou os seus conceitos. Para começar, desenvolveu uma nomenclatura para descrever o sistema, incluindo o número de bits de dados e de correção de erros num bloco. Por exemplo, a paridade inclui um único bit detecção de erros, assumindo assim palavras ASCII com 7-bits, Hamming descreveu este código como (8,7), com oito bits no total, dos quais 7 dados. Seguindo a mesma lógica o exemplo da repetição seria (3,1). A taxa do código ou taxa de informação, é o segundo número dividido pelo primeiro, para o último exemplo seria 1/3.

Hamming também percebeu os problemas procedentes da alteração de dois ou mais bits, e descreveu como "distância" (denominada distância de Hamming, em sua homenagem). A paridade tem uma distância de 2, pois a alteração de dois bits não é detectável. A repetição (3,1) tem uma distância de 3, pois é necessário alterar três bits para se obter uma outra palavra válida. A repetição (4,1) (cada bit é repetido quatro vezes) tem uma distância de 4, de modo que a alteração dois bits pode ser detectada, mas não corrigido. Quando três bits se alteram no mesmo grupo pode haver situações em que o código corrige para outra palavra de código válida, mas que não seja a original.

Hamming estava interessado em resolver dois problemas ao mesmo tempo, aumentar a distância o mais possível, ao mesmo tempo que aumentava a taxa de informação. Durante os anos de 1940, desenvolveu vários algoritmos de codificação com melhorias substanciais sobre os códigos existentes. O princípio chave para estes sistemas era sobrepor os bits de paridade, de forma que eles conseguissem verificar-se uns aos outros, bem como os bits de dados.

Estrutura editar

Os códigos binários de Hamming são baseados em códigos de paridade sobre um bloco de dados de comprimento fixo. O bloco de dados, também denominado de "palavra" contém n bits, este parâmetro pode assumir apenas valores inteiros específicos, que resultam da especificação do código. As combinações de bits do bloco de dados pode ser seleccionado como desejado, o que significa que todas as combinações de bits arbitrárias são permitidas. O código de paridade do código de Hamming é obtido a partir da palavra de dados, inserindo pontos de controle, denominados bits de paridade. Em cada palavra de dados, de comprimento n, são inseridos um número fixo k, de pontos de controlo, ficando a palavra de código com um comprimento $N=n+k$ . Para a palavra de código, apenas certas combinações de bits são possíveis, uma vez que os pontos de controlo têm informação derivada da palavra de dados. Isto permite a detecção e correcção dos erros.

A relação entre $N$ e $k$ é descrita pela seguinte equação:

$N=2^{k}-1$

Se por exemplo, tivermos três bits de controlo (os bits de paridade) então o comprimento da mensagem N será necessariamente 7. O comprimento da palavra de dados é obtido de $n=7-3=4$ n = 7-3 = 4 bits ou de uma forma mais geral:

$n=2^{k}-k-1$

A tabela seguinte lista todos os códigos Hamming possíveis de vários comprimentos de mensagem até um máximo de 255 bits:

Combinações de parâmetros do códigos de Hamming
n	k	N = n + k
Bits de dados	Bits de paridade	Total da mensagem
1	2	3
4	3	7
11	4	15
26	5	31
57	6	63
120	7	127
247	8	255

Para a classificação dos diferentes códigos de Hamming, geralmente usa-se a seguinte notação: Hamming (N, n). O primeiro número indica o número de bits da mensagem (N), o segundo indica o número de bits de dados (n) por mensagem. Em exemplos de demonstração, por questões de simplicidade, muitas vezes é usado o código Hamming (7,4). Para o trabalho real este código tem uma taxa de informação pequena, ou seja, a proporção de bits de controlo de bits de dados é muito desfavorável, tendo em atenção que podemos usar o código de Hamming (63,57).

Por vezes a classificação do código tem a distância em terceiro lugar: Hamming (63,57,3). Mas como a distância é, normalmente, fixa o código é apenas descrito como: Hamming (63,57).

Algoritmo editar

O seguinte algoritmo geral produz um código de correcção de um erro para codificar qualquer número de bits.

Numerar os bits a partir de 1: bit 1, 2, 3, 4, 5, etc.
Escrever o número do bit em binário. 1, 10, 11, 100, 101, etc.
Todas as posições que são potências de dois (têm apenas um 1 e está no bit mais significativo) são bits de paridade.
Todas as outras posições são os bits de dados.
Cada bit de dados é incluído num único conjunto de 2 ou mais bits de paridade, conforme determinado pela sua posição.
1. O bit de paridade 1 abrange todas as posições que têm o bit menos significativo activo: bit 1 (o bit de paridade em si), 3, 5, 7, 9, etc.
2. O bit de paridade 2 abrange todas as posições que têm o segundo bit menos significativo activo: bit 2 (o bit de paridade em si), 3, 6, 7, 10, 11, etc.
3. O bit de paridade 4 abrange todas as posições de bits que possuem o terceiro bit menos significativo: bits 4 a 7, 12 a 15, 20 a 23, etc.
4. O bit de paridade 8 abrange todas as posições de bits que têm o quarto bit menos significativo activo: bits 8 a 15, 24 a 31, 40 a 47, etc.
5. Regra geral cada bit de paridade abrange todos os bits onde o E lógico da posição de paridade e a posição do bit, é diferente de zero.

A forma da paridade é irrelevante. A paridade par é mais simples do ponto de vista matemático, mas na prática não há diferença.

Esta regra pode ser mostrada visualmente:

bits codificados		p1	p2	d1	p4	d2	d3	d4	p8	d5	d6	d7	d8	d9	d10	d11	p16	d12	d13	d14	d15
Posição do bit		1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	...
bits de paridade	p1	X		X		X		X		X		X		X		X		X		X
	p2		X	X			X	X			X	X			X	X			X	X
	p4				X	X	X	X					X	X	X	X					X
	p8								X	X	X	X	X	X	X	X
	p16																X	X	X	X	X

Neste quadro são mostrados apenas 20 bits (5 paridade, 15 de dados), mas o padrão continua indefinidamente. A primeira coisa que podemos ver a partir de uma análise do quadro é que qualquer bit de dados está incluído em um único conjunto de bits de paridade.

Para verificar se houve erros devemos validar todos os bits de paridade. O padrão de erros, designado síndroma (conjunto de sintomas) do erro, identifica o bit com erro. Se todos os bits de paridade estiverem correctos, não temos erros. Portanto, a soma das posições dos bits de paridade com erro identifica o bit com problemas. Por exemplo, se os bits de paridade nas posições 1, 2 e 8 indicam um erro, então o bit 1+2+8 = 11 está errado. Se apenas um bit de paridade indicar erro, o erro está no bit de paridade.

Como se pode ver, se tivermos $m$ bits de paridade, podemos cobrir do bit 1 até $2^{m}-1$ . Se subtrairmos os bits de paridade, ficamos com $2^{m}-m-1$ bits que podemos usar para os dados. Se variarmos $m$ obtemos todos os códigos de Hamming possíveis:

Bits de paridade	Bits totais	Bits de dados	Nome	Taxa
2	3	1	Hamming(3,1) (Tripla repetição)	1/3 ≈ 0.333
3	7	4	Hamming(7,4)	4/7 ≈ 0.571
4	15	11	Hamming(15,11)	11/15 ≈ 0.733
5	31	26	Hamming(31,26)	26/31 ≈ 0.839
...
$m$	$2^{m}-1$	$2^{m}-m-1$	Hamming $(2^{m}-1,2^{m}-m-1)$	$1-m/(2^{m}-1)$

O menor código de Hamming editar

O código de Hamming mais curto é o Hamming(3,1). Neste caso, a um bit de dados é atribuído uma palavra código de três bits, ou seja, existem dois bits de paridade, $p_{1}$ e $p_{2}$ para o bit de dados $d_{1}$ . Neste caso só pode haver duas palavras código válidas, 000 e 111. As palavras de código inválidas 001, 010 e 100, por maioria de razão, são corrigidas para a palavra de código 000. 110, 101 e 011 para a palavra de código 111. Assim, o código de Hamming (3,1) e um caso especial, é igual a um código de repetição com comprimento 3.

Hamming (7,4) editar

Descrição gráfica de 4 bits de dados (d1,d2,d3 e d4) e 3 bits de paritdade (p1,p2 e p3)

Este tipo de código de controle de erros, transforma cada bloco de 4 bits de dados, num bloco de 7 bits, acrescentando 3 bits de paridade Pode detectar e corrigir um erro num único bit, e apenas detecta erros quando ocorrem erros em 2 bits.

Construção de G e H editar

A matriz $\mathbf {G} :={\begin{pmatrix}I_{k}|-A^{T}\\\end{pmatrix}}$ é denominada matriz geradora de um código linear (n, k), e

$\mathbf {H} :={\begin{pmatrix}A|I_{n-k}\\\end{pmatrix}}$ é chamada de matriz de paridade.

Esta é a construção standard de G e H na forma sistemática. Independentemente da forma, G e H, para os códigos de blocos lineares, têm que satisfazer, ou seja, da operação $\mathbf {H} \,\mathbf {G} ^{T}=\mathbf {0}$ deve resultar a matriz nula.^[2]

Uma vez que (7,4,3)=(n,k,d)=[2^m − 1, 2^m−1-m, m]. A matriz de paridade H, de um código de Hamming, é construída listando todas as colunas de comprimento, que são linearmente independentes. Assim H,é uma matriz cujo lado esquerdo são os tuplos não nulos. O lado direito é a matriz identidade.

Assim G pode ser obtido a partir de H , juntando a transposta do lado esquerdo de H , com a matriz identidade de k no lado esquerdo de G.

A matriz geradora $\mathbf {G}$ e matriz de paridade $\mathbf {H}$ são:

\mathbf {G} :={\begin{pmatrix}1&1&0&1\\1&0&1&1\\1&0&0&0\\0&1&1&1\\0&1&0&0\\0&0&1&0\\0&0&0&1\\\end{pmatrix}}

e

\mathbf {H} :={\begin{pmatrix}1&0&1&0&1&0&1\\0&1&1&0&0&1&1\\0&0&0&1&1&1&1\\\end{pmatrix}}

Por exemplo, 1 0 1 1 é codificado em 0 1 1 0 0 1 1 , onde dígitos azuis correspondem aos dados a enviar (bloco de dados), e os de cor vermelha representam os bits de paridade. A notar também que, a Distância de Hamming ( nº de bits que diferem uns dos outros na matriz de paridade ) é 4.

Codificação editar

A partir da matriz acima, temos 2^k=2⁴=16 palavras-código. As palavras código ${\overrightarrow {x}}$ deste código binário podem ser obtidas a partir de ${\overrightarrow {x}}={\overrightarrow {a}}G$ . Com ${\overrightarrow {a}}=a_{1}a_{2}a_{3}a_{4}$ e $a_{i}$ , sendo $F_{2}$ um corpo finito com dois elementos, 0 e 1.

Assim, a mensagem (1,0,1,1) fica codificada como (0,1,1,0,0,1,1).

Código de Hamming estendido editar

Os códigos de Hamming têm uma distância mínima de 3, o que significa que o descodificador pode detectar e corrigir um erro simples, mas não pode distinguir um erro de dois bits de algumas palavras de código de um erro de um bit de uma outra palavra de código. Assim, é possível detectar erros em dois bits apenas se a correcção não for tentada.

Para corrigir esta deficiência, os códigos de Hamming pode ser estendidos num bit de paridade. Desta forma, é possível aumentar a distância mínima do código de Hamming para 4, o que permite ao descodificador distinguir entre erros de um bit e de dois bits. Assim, o descodificador pode detectar e corrigir um erro simples e ao mesmo tempo detectar (mas não corrigir) um erro duplo. Se o descodificador não tentar corrigir o erro, ele pode detectar até 3 erros.

Este código Hamming estendido é bastante popular nos sistemas de memória de computador, onde é conhecido como SECDED ("single error correction, double error detection"). O código (72,64) é particularmente popular, sendo um Hamming (127,120) truncado, mais um bit de paridade adicional.

Código Hamming (7,4) com um bit de paridade adicional editar

O código Hamming (7,4) pode ser facilmente estendido para um código de (8,4) por adição de um bit extra de paridade sobre a palavra de código (7,4). Este pode ser resumido com as matrizes seguintes:

\mathbf {G} :={\begin{pmatrix}1&1&1&0&0&0&0&1\\1&0&0&1&1&0&0&1\\0&1&0&1&0&1&0&1\\1&1&0&1&0&0&1&0\end{pmatrix}}_{4,8}

e

\mathbf {H} :={\begin{pmatrix}1&0&1&0&1&0&1&0\\0&1&1&0&0&1&1&0\\0&0&0&1&1&1&1&0\\1&1&1&1&1&1&1&1\end{pmatrix}}_{4,8}

A introdução da quarta linha permite acomodar a soma de todos os bits de palavra de código (dados e paridade) como o quarto bit de paridade. Por exemplo, 1011 é codificada como 01100110, onde são dados os dígitos azuis; os dígitos vermelhos são a paridade do código, e o dígito verde é bit de paridade estendido. O dígito verde faz a paridade do código (7,4). Podemos assim mostrar que a distância mínima aumentou de 3 para 4, passando o código (7,4), a código (8,4). Assim, o código passa a definido como Hamming (8,4,4).

Ver também editar

Notas editar

Referências

↑ http://www.cs.cmu.edu/~venkatg/teaching/codingtheory/notes/notes1.pdf
↑ Moon T. Error correction coding: Mathematical Methods and Algorithms. John Wiley and Sons, 2005.(Cap. 3) ISBN 978-0-471-64800-0

Ligações externas editar

Commons

O Commons possui imagens e outros ficheiros sobre Código de Hamming

[1] ttp://www.cs.cmu.edu/~venkatg/teaching/codingtheory/notes/notes1.pdf

[Moon-2] Moon T. Error correction coding: Mathematical Methods and Algorithms. John Wiley and Sons, 2005.(Cap. 3) ISBN 978-0-471-64800-0

[1]

[2]