Códigos de detecção e correção de erros
Sabemos que os bits 0 e 1 correspondem a duas faixas diferentes de tensões analógicas. Portanto, durante a transmissão de dados binários de um sistema para outro, o ruído também pode ser adicionado. Devido a isso, podem haver erros nos dados recebidos em outro sistema.
Isso significa que um bit 0 pode mudar para 1 ou um bit 1 pode mudar para 0. Não podemos evitar a interferência de ruído. No entanto, podemos recuperar os dados originais primeiro detectando se há algum erro e depois corrigindo esses erros. Para isso, podemos usar os seguintes códigos.
- Códigos de detecção de erro
- Códigos de correção de erros
Error detection codes- são usados para detectar o (s) erro (s) presente (s) nos dados recebidos (fluxo de bits). Esses códigos contêm alguns bit (s), que são incluídos (anexados) ao fluxo de bits original. Esses códigos detectam o erro, se ele ocorreu durante a transmissão dos dados originais (fluxo de bits).Example - Código de paridade, código de Hamming.
Error correction codes- são usados para corrigir o (s) erro (s) presente (s) nos dados recebidos (fluxo de bits) para que possamos obter os dados originais. Os códigos de correção de erros também usam a estratégia semelhante de códigos de detecção de erros.Example - Código de Hamming.
Portanto, para detectar e corrigir os erros, bit (s) adicional (is) são acrescentados aos bits de dados no momento da transmissão.
Código de Paridade
É fácil incluir (anexar) um bit de paridade à esquerda do MSB ou à direita do LSB do fluxo de bits original. Existem dois tipos de códigos de paridade: código de paridade par e código de paridade ímpar com base no tipo de paridade escolhido.
Código de paridade uniforme
O valor do bit de paridade par deve ser zero, se o número par de uns estiver presente no código binário. Caso contrário, deve ser um. Assim, o número par de uns presentes emeven parity code. O código de paridade uniforme contém os bits de dados e o bit de paridade uniforme.
A tabela a seguir mostra o even parity codescorrespondente a cada código binário de 3 bits. Aqui, o bit de paridade par é incluído à direita do LSB do código binário.
| Código binário | Mesmo bit de paridade | Código de paridade uniforme |
|---|---|---|
| 000 | 0 | 0000 |
| 001 | 1 | 0011 |
| 010 | 1 | 0101 |
| 011 | 0 | 0110 |
| 100 | 1 | 1001 |
| 101 | 0 | 1010 |
| 110 | 0 | 1100 |
| 111 | 1 | 1111 |
Aqui, o número de bits presentes nos códigos de paridade pares é 4. Portanto, o número par possível de uns nesses códigos de paridade pares é 0, 2 e 4.
Se o outro sistema receber um desses códigos de paridade par, não há erro nos dados recebidos. Os bits diferentes do bit de paridade par são iguais aos do código binário.
Se o outro sistema receber códigos diferentes de paridade par, haverá erro (s) nos dados recebidos. Nesse caso, não podemos prever o código binário original porque não sabemos a (s) posição (ões) do bit de erro.
Portanto, o bit de paridade par é útil apenas para detecção de erro no código de paridade recebido. Porém, não é suficiente corrigir o erro.
Código de paridade ímpar
O valor do bit de paridade ímpar deve ser zero, se o número ímpar de uns estiver presente no código binário. Caso contrário, deve ser um. Então, número ímpar de uns presentes emodd parity code. O código de paridade ímpar contém os bits de dados e o bit de paridade ímpar.
A tabela a seguir mostra o odd parity codescorrespondente a cada código binário de 3 bits. Aqui, o bit de paridade ímpar é incluído à direita do LSB do código binário.
| Código binário | Bit de paridade ímpar | Código de paridade ímpar |
|---|---|---|
| 000 | 1 | 0001 |
| 001 | 0 | 0010 |
| 010 | 0 | 0100 |
| 011 | 1 | 0111 |
| 100 | 0 | 1000 |
| 101 | 1 | 1011 |
| 110 | 1 | 1101 |
| 111 | 0 | 1110 |
Aqui, o número de bits presentes nos códigos de paridade ímpar é 4. Portanto, o número ímpar possível de um nesses códigos de paridade ímpar é 1 e 3.
Se o outro sistema receber um desses códigos de paridade ímpar, não haverá erro nos dados recebidos. Os bits diferentes do bit de paridade ímpar são iguais aos do código binário.
Se o outro sistema receber códigos diferentes de paridade ímpar, há erro (s) nos dados recebidos. Nesse caso, não podemos prever o código binário original porque não sabemos a (s) posição (ões) do bit de erro.
Portanto, o bit de paridade ímpar é útil apenas para detecção de erro no código de paridade recebido. Porém, não é suficiente corrigir o erro.
Código de Hamming
O código de Hamming é útil para detecção e correção de erros presentes nos dados recebidos. Este código usa vários bits de paridade e temos que colocar esses bits de paridade nas posições de potências de 2.
o minimum value of 'k' para o qual a seguinte relação está correta (válida) nada mais é do que o número necessário de bits de paridade.
$$ 2 ^ k \ geq n + k + 1 $$
Onde,
'n' é o número de bits no código binário (informação)
'k' é o número de bits de paridade
Portanto, o número de bits no código de Hamming é igual a n + k.
Deixe o Hamming codeé $ b_ {n + k} b_ {n + k-1} ..... b_ {3} b_ {2} b_ {1} $ & bits de paridade $ p_ {k}, p_ {k-1}, .... p_ {1} $. Podemos colocar os bits de paridade 'k' em potências de 2 posições apenas. Nas posições de bits restantes, podemos colocar os 'n' bits do código binário.
Com base no requisito, podemos usar paridade par ou paridade ímpar ao formar um código de Hamming. Porém, a mesma técnica de paridade deve ser usada para descobrir se algum erro está presente nos dados recebidos.
Siga este procedimento para encontrar parity bits.
Encontre o valor de p1, com base no número de unidades presentes nas posições de bit b 3 , b 5 , b 7 e assim por diante. Todas essas posições de bits (sufixos) em seus binários equivalentes têm '1' no valor de lugar de 2 0 .
Encontre o valor de p2, com base no número de unidades presentes nas posições de bit b 3 , b 6 , b 7 e assim por diante. Todas essas posições de bits (sufixos) em seus binários equivalentes têm '1' no valor de lugar de 2 1 .
Encontre o valor de p3, com base no número de unidades presentes nas posições de bit b 5 , b 6 , b 7 e assim por diante. Todas essas posições de bits (sufixos) em seus binários equivalentes têm '1' no valor de lugar de 2 2 .
Da mesma forma, encontre outros valores de bits de paridade.
Siga este procedimento para encontrar check bits.
Encontre o valor de c 1 , com base no número de unidades presentes nas posições dos bits b 1 , b 3 , b 5 , b 7 e assim por diante. Todas essas posições de bits (sufixos) em seus binários equivalentes têm '1' no valor de lugar de 2 0 .
Encontre o valor de c 2 , com base no número de unidades presentes nas posições de bit b 2 , b 3 , b 6 , b 7 e assim por diante. Todas essas posições de bits (sufixos) em seus binários equivalentes têm '1' no valor de lugar de 2 1 .
Encontre o valor de c 3 , com base no número de unidades presentes nas posições dos bits b 4 , b 5 , b 6 , b 7 e assim por diante. Todas essas posições de bits (sufixos) em seus binários equivalentes têm '1' no valor de lugar de 2 2 .
Da mesma forma, encontre outros valores de bits de verificação.
O equivalente decimal dos bits de verificação nos dados recebidos dá o valor da posição do bit, onde o erro está presente. Basta complementar o valor presente na posição do bit. Portanto, obteremos o código binário original após remover os bits de paridade.
Exemplo 1
Vamos encontrar o código de Hamming para o código binário, d 4 d 3 d 2 d 1 = 1000. Considere os bits de paridade pares.
O número de bits no código binário fornecido é n = 4.
Podemos encontrar o número necessário de bits de paridade usando a seguinte relação matemática.
$$ 2 ^ k \ geq n + k + 1 $$
Substitua, n = 4 na relação matemática acima.
$$ \ Rightarrow 2 ^ k \ geq 4 + k + 1 $$
$$ \ Rightarrow 2 ^ k \ geq 5 + k $$
O valor mínimo de k que satisfez a relação acima é 3. Portanto, exigimos 3 bits de paridade p 1 , p 2 e p 3 . Portanto, o número de bits no código de Hamming será 7, uma vez que existem 4 bits no código binário e 3 bits de paridade. Temos que colocar os bits de paridade e bits do código binário no código de Hamming, conforme mostrado abaixo.
o 7-bit Hamming code é $ b_ {7} b_ {6} b_ {5} b_ {4} b_ {3} b_ {2} b_ {1} = d_ {4} d_ {3} d_ {2} p_ {3} d_ {1 } p_ {2} bp_ {1} $
Ao substituir os bits do código binário, o código de Hamming será $ b_ {7} b_ {6} b_ {5} b_ {4} b_ {3} b_ {2} b_ {1} = 100p_ {3} Op_ {2 } p_ {1} $. Agora, vamos encontrar os bits de paridade.
$$ p_ {1} = b_ {7} \ oplus b_ {5} \ oplus b_ {3} = 1 \ oplus 0 \ oplus 0 = 1 $$
$$ p_ {2} = b_ {7} \ oplus b_ {6} \ oplus b_ {3} = 1 \ oplus 0 \ oplus 0 = 1 $$
$$ p_ {3} = b_ {7} \ oplus b_ {6} \ oplus b_ {5} = 1 \ oplus 0 \ oplus 0 = 1 $$
Ao substituir esses bits de paridade, o Hamming code será $ b_ {7} b_ {6} b_ {5} b_ {4} b_ {3} b_ {2} b_ {1} = 1001011 $.
Exemplo 2
No exemplo acima, obtivemos o código de Hamming como $ b_ {7} b_ {6} b_ {5} b_ {4} b_ {3} b_ {2} b_ {1} = 1001011 $. Agora, vamos encontrar a posição do erro quando o código recebido é $ b_ {7} b_ {6} b_ {5} b_ {4} b_ {3} b_ {2} b_ {1} = 1001111 $.
Agora, vamos encontrar os bits de verificação.
$$ c_ {1} = b_ {7} \ oplus b_ {5} \ oplus b_ {3} \ oplus b_ {1} = 1 \ oplus 0 \ oplus 1 \ oplus1 = 1 $$
$$ c_ {2} = b_ {7} \ oplus b_ {6} \ oplus b_ {3} \ oplus b_ {2} = 1 \ oplus 0 \ oplus 1 \ oplus1 = 1 $$
$$ c_ {3} = b_ {7} \ oplus b_ {6} \ oplus b_ {5} \ oplus b_ {4} = 1 \ oplus 0 \ oplus 0 \ oplus1 = 0 $$
O valor decimal dos bits de verificação fornece a posição do erro no código de Hamming recebido.
$$ c_ {3} c_ {2} c_ {1} = \ left (011 \ right) _ {2} = \ left (3 \ right) _ {10} $$
Portanto, o erro está presente no terceiro bit (b 3 ) do código de Hamming. Basta complementar o valor presente naquele bit e remover os bits de paridade para obter o código binário original.