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.
Imagem: Zach Weinersmith · BY-SA · Openverse
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.
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
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
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
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.
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.
Estrutura
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 {\displaystyle 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.
Algoritmo
O seguinte algoritmo geral produz um código de correcção de um erro para codificar qualquer número de bits. 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: 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.
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 {\displaystyle p_{1}} e p 2 {\displaystyle p_{2}} para o bit de dados d 1 {\displaystyle 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.
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
A matriz G := ( I k | − A T ) {\displaystyle \mathbf {G} :={\begin{pmatrix}I_{k}|-A^{T}\\\end{pmatrix}}} é denominada matriz geradora de um código linear (n, k), e H := ( A | I n − k ) {\displaystyle \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 H G T = 0 {\displaystyle \mathbf {H} \,\mathbf {G} ^{T}=\mathbf {0} } deve resultar a matriz nula. Uma vez que (7,4,3)=(n,k,d)=[2m − 1, 2m−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.
Codificação
A partir da matriz acima, temos 2k=24=16 palavras-código. As palavras código x → {\displaystyle {\overrightarrow {x}}} deste código binário podem ser obtidas a partir de x → = a → G {\displaystyle {\overrightarrow {x}}={\overrightarrow {a}}G} . Com a → = a 1 a 2 a 3 a 4 {\displaystyle {\overrightarrow {a}}=a_{1}a_{2}a_{3}a_{4}} e a i {\displaystyle a_{i}} , sendo F 2 {\displaystyle 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).
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.
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: 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).
