A respeito dos sistemas de computadores, responda:
Construa um código capaz de corrigir um único erro de bit onde as palavras de memória possuem m=8 bits. Prove que ele funciona apresentando um exemplo de erro em um dos bits de uma palavra de código.

Passo 1

Beleza, vamos ter um enunciado que diz: “Precisamos montar um código que corrija um único erro de bit para palavras de memória com bits”. Isso é assunto de códigos de detecção/correção de erro, mais especificamente o código de Hamming.
O que vamos precisar:
  • Descobrir quantos bits de paridade (chamados de ) são necessários para proteger 8 bits de dados.
  • Escolher as posições desses bits de paridade na palavra de código.
  • Definir quais bits cada paridade deve “olhar” (a lógica de cobertura).
  • Mostrar na prática que, se um bit é invertido por engano, a gente consegue achar qual foi e corrigir.

Passo 2

Primeiro, quantos bits de paridade precisamos? A condição do Hamming é
2^r ;>=; m + r + 1
Aqui . Testando:
  • Se , e . Falha.
  • Se , e . OK!
    Logo, são 4 bits de paridade.

Passo 3

Como colocar esses 4 bits junto dos 8 de dados?
A gente vai ter uma palavra de código de bits. As posições que são potências de 2 (1, 2, 4 e 8) ficam reservadas para os bits de paridade . Nas outras vai cada dado .
Indices:
1:p1
2:p2
3:d1
4:p3
5:d2
6:d3
7:d4
8:p4
9:d5
10:d6
11:d7
12:d8

Passo 4

Agora a regra de cobertura:
  • (posição 1) checa todos os bits cuja posição em binário tenha o bit 0 (LSB) = 1 → cobre posições 1,3,5,7,9,11.
  • (pos 2) checa os que têm bit 1 = 1 → cobre 2,3,6,7,10,11.
  • (pos 4) checa os que têm bit 2 = 1 → cobre 4,5,6,7,12.
  • (pos 8) checa os que têm bit 3 = 1 → cobre 8,9,10,11,12.
Cada paridade é calculada pra que a soma total (desses bits + ele próprio) fique par (ou seja, soma módulo 2 = 0).

Passo 5

Vamos pegar um exemplo de dado de 8 bits, digamos
d1ldots d8 = 1;0;1;1;0;0;1;0
Preenchemos nas posições certas e calculamos cada underbrace1p1,;underbrace0p2,;1,;underbrace0p3,;0,;1,;1,;underbrace1p4,;0,0,1,0 :
  1. p1 cobre bits em (3,5,7,9,11) = (1,0,1,0,1), soma = 3 ≡1 mod2, então p1 = 1 (pra sum+ p1 = 0 mod2).
  2. p2 cobre (3,6,7,10,11) = (1,1,1,0,1), soma = 4 ≡0 mod2, então p2 = 0.
  3. p3 cobre (5,6,7,12) = (0,1,1,0), soma = 2 ≡0 mod2, então p3 = 0.
  4. p4 cobre (9,10,11,12) = (0,0,1,0), soma = 1 ≡1 mod2, então p4 = 1.
A palavra de código (posições 1 a 12) fica:

Passo 6

Agora insere um erro simples: digamos que o bit na posição 6 vire de 1 → 0. Aí a gente recalcula cada paridade (sindrome):
  • = soma mod2 de (1,3,5,7,9,11) no recebido = 0 → sem erro nessa cobertura, .
  • = soma mod2 de (2,3,6,7,10,11) = 1 → .
  • = soma mod2 de (4,5,6,7,12) = 1 → .
  • = soma mod2 de (8,9,10,11,12) = 0 → .
Juntando os bits de síndrome em binário, isso é 6 em decimal. Ou seja, “o erro está no bit 6”. Bingo! A gente inverte de volta e corrigiu o único erro.

Resposta

O código que corrige 1 erro para é o código de Hamming com 4 bits de paridade em posições 1,2,4 e 8, usando cobertura pelos bits de índice em binário conforme mostrado. A prova de funcionamento veio do exemplo: erro no bit 6 → síndrome indica “6” → corrige.

Exercícios relacionados