Códigos+de+Detecção+e+Correção+de+Erros

Sistemas 
Embarcados II
Aula 2 – Códigos de Detecção 
e Correção de Erros
Prof. Fernando Luiz Trazzi Junior
Conteúdo da aula
 UNIDADE 2: Segurança da veracidade dos dados: 
Códigos de correção e códigos de validação 
2.1 Introdução a segurança e veracidade dos dados em 
sistemas embarcados
2.2 Código de correção de erros
2.3 Checksum
2.4 CRC - Cyclic Redundancy Check 
2.5 Código de Hamming
Introdução
Falha, Erro e Defeito
Confiabilidade dos sistemas
 Os sistemas embarcados devem oferecer 
confiabilidade no seu funcionamento, evitando o 
prejuízo das pessoas que os utilizam e do próprio 
equipamento físico
 Um sistema de computação funciona através da 
transferência de informação desde o nível de 
circuito integrados até aos níveis mais altos, como 
por exemplo gravação no disco ou comunicação 
entre computadores.
 Está sujeito a diversos erros, como os causados 
por interferências electromagnéticas, 
envelhecimento de componentes, curto-circuitos, ...
Erros
 São inevitáveis em qualquer sistema de 
comunicação real;
 A distribuição dos erros não é homogênea: bits 
isolados ou em “rajadas” (bursts) de erros, com 8 
ou mais bits sucessivos errados;
 Deve-se levar em conta o meio físico de 
transmissão de dados, para incluir maior ou menor 
redundância na transmissão, a fim de garantir que a 
informação recebida seja confiável.
Erros
 Possíveis abordagens no tratamento de erros:
– Ignorar o erro;
– Eco (transmissão à origem de reflexos dos dados 
recebidos);
– Sinalizar o erro;
– Detectar e solicitar a retransmissão em caso de erro;
– Detectar e corrigir os erros na recepção de forma 
automática.
Código de Detecção de Erros
 Detectar um erro é uma tarefa mais simples do que 
detectar e corrigir; 
 Nem sempre é possível solicitar uma 
retransmissão;
 Todos os métodos utilizam a inserção de bits 
extras;
– Esses bits podem ser obtidos a partir da informação 
original e o receptor recalcula os bits extras
Código de Detecção de Erros
 Um método ineficiente mas muito utilizado para 
detectar erros é a Paridade;
 Outro método é o checksum
 Um método mais eficiente é o uso de um código 
polinomial ou CRC (Cyclic Redundancy Check);
Código de Detecção 
e Correção de Erros
 Códigos de correção podem recuperar o dado 
original a partir do código com erros;
 Consistem na criação de códigos extras que 
detectam situações inválidas mas que mantém a 
identidade do dado original;
 O conceito mais básico e mais importante desses 
códigos é a distância de Hamming, utilizada para a 
criação de códigos de correção.
Redundância de um código
Quantidade total de bits transmitidos
n = m+r
Overhead: r/m
Palavras válidas
 Seja um código binário com m bits, então existem 2m 
mensagens válidas
 São agregados r bits para a verificação de erros, 
resultando uma mensagem com: n = m + r bits
– 2m+r palavras possíveis
– 2m palavras são válidas
– 2m(2r-1) palavras são inválidas
 O sistema só gera palavras válidas.
 Logo, se surgir alguma palavra inválida, trata-se de 
um erro!
Detecção de Erros - Paridade
 Paridade
– Consiste basicamente no ato do transmissor 
adicionar um bit de redundância após um 
determinado número de bits
 Número par de 1’s → paridade par
 Número ímpar de 1’s → paridade impar
Ex.: 000, 011, 101, 110 são mensagens transmitidas sem 
erro, tendo em conta que o último bit é o de paridade
Detecção de Erros - Paridade
Exemplo:
 Deseja-se transmitir a seguinte sequência de bits:
1000001
Deve-se inserir o bit P de paridade:
1000001P → número par de 1’s → P = 0
Portanto, a sequência de bits transmitida é:
10000010
 O receptor calcula a paridade da mensagem e 
compara-a com o bit P recebido: 
P = paridade → transmissão correta
Detecção de Erros - Paridade
 Este processo pode ser vulnerável se houver mais 
do que um erro, permitindo assim que este passe 
até ao destino sem ser identificado.
 No exemplo, se o receptor recebesse a sequência:
11010010 
 O bit de paridade seria 0, mas o erro existe
Detecção de Erros - Paridade
 Tem capacidade de detectar número ímpar de erros
 Não corrige erro, somente detecta
Detecção de Erros – Paridade
Exercício
Calcular o bit de paridade das seguintes 
sequências de bits:
a) 10010010
b) 11001001
c) 01010001
d) 11101110
Detecção de Erros – Paridade
Exercício
Calcular o bit de paridade das seguintes 
sequências de bits:
a) 100100101
b) 110010010
c) 010100011
d) 111011100
Detecção de Erros - 
Paridade Bidimensional
 Generalização bidimensional do esquema de 
paridade de bit único.
 O receptor não somente pode detectar que ocorreu 
um erro de um bit único, como identificar o bit e 
corrigi-lo.
 A paridade 2-dim detecta todos os erros de 1, 2 e 3
bits, e a maioria dos erros de 4 bits.
– 2 erros na mesma coluna e 2 erros na mesma linha 
não são detectados
Detecção de Erros - 
Paridade Bidimensional
Detecção de Erros - 
Paridade Bidimensional
 Erro de 4 bits não detectável:
Detecção de Erros – Paridade 
Bidimensinal – Exercício
Deseja-se transmitir 4 bytes de dados. Calcular os 
bits de paridade bidimensional
10010010
11001001
01010001
11101110
Detecção de Erros – Paridade 
Bidimensinal – Exercício
Deseja-se transmitir 4 bytes de dados. Calcular os 
bits de paridade bidimensional
100100101
110010010
010100011
111011100
111001000
Detecção de Erros – Paridade 
Bidimensinal – Exercício
Caso o receptor receba a seguinte sequência de 
bits com erro, como seria feita a correção?
100100101
110110010
010100011
111011100
111001000
Detecção de Erros - Checksum
 A ideia é somar todas as palavras que são 
transmitidas e depois transmitir o resultado daquela 
soma (checksum) junto com as palavras. Se 
quaisquer dos dados transmitidos, incluindo o 
checksum, sofrerem algum erro, então, no receptor, o 
resultado da operação soma não será correto.
 Método relativamente simples de detecção de erros
 Utilizado na transmissão de dados pela internet
 Basicamente 2 métodos para encontrar o checksum:
– Soma propriamente dita
– Ou-Exclusivo entre bits
Detecção de Erros - Checksum
 Método de soma:
1) Realiza-se a soma binária de uma sequência de 
palavras
2) O resultado da soma (checksum) é invertido e 
transmitido junto com a sequência de palavras 
3) O receptor soma todas palavras, incluindo o 
checksum. O resultado deve ser uma sequência de 
1's. Caso contrário, há um erro na transmissão.
Detecção de Erros – Checksum
Exercício
 Dada a sequência de 3 bytes abaixo, calcule o 
checksum pelo método da soma:
10011000 00011001 11000011
Checksum:
 
 A sequência abaixo foi recebida. Como o receptor 
verifica se está correta?
10011000 01011001 11000011 10001011
Detecção de Erros – Checksum
Exercício
 Dada a sequência de 3 bytes abaixo, calcule o 
checksum pelo método da soma:
10011000 00011001 11000011
Checksum: 10001011 (lembrar de inverter o 
resultado da soma antes de enviar a mensagem)
 A sequência abaixo foi recebida. Como o receptor 
verifica se está correta?
10011000 01011001 11000011 10001011
Soma os 4 bytes. Se resultado igual a 11111111, mensagem sem erro. 
Neste caso, o resultado é diferente, portanto há erro.
Detecção de Erros - Checksum
 Método de XOR:
1) Realiza-se a operação XOR entre os bits que 
estão na mesma posição de todas as palavras 
2) O resultado da operação (checksum) é 
transmitido junto com a sequência de palavras 
3) O receptor faz o XOR de todas palavras, 
incluindo o checksum. O resultado deve ser uma 
sequência de 0's. Caso contrário, há um erro na 
transmissão.