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

Prévia do material em texto

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.Detecção de Erros – Checksum
Exercício
 Dada a sequência de 3 bytes abaixo, calcule o 
checksum pelo método de XOR.
10011000 00011001 11000011
Checksum: 01000010 (NÃO é necessário 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 01000010
XOR dos 4 bytes. Se resultado igual a 00000000, mensagem sem erro. 
Neste caso, o resultado é diferente, portanto há erro.
Detecção de Erros – CRC
Cyclic Redundancy Check 
 Uma forma mais confiável de deteção de erros
 É um número, calculado a partir de uma mensagem 
e armazenado/transmitido junto com ela. 
 Na recepção/recuperação da mensagem, basta 
simplesmente recalcularmos o CRC e compará-lo 
com o valor original
– se forem iguais, as probabilidades são grandes de 
que não houve erros no processo, caso contrario, 
certamente houve erros.
 Método relativamente simples de detecção de erros
 Utilizado na transmissão de dados pela internet
Detecção de Erros – CRC
 Emissor/receptor concordam num polinômio 
gerador G(x), em que quanto maior for o seu grau 
maior será a capacidade de detecção de erros. Ex.:
 G(x) = x5 + x4 + x2 + x0 = (110101)2
 O cálculo de CRC é realizado através de uma 
operação de divisão aplicada a números binários.
 Há uma diferença na divisão: as operações são 
substituídas por operações lógicas de ou exclusivo 
(XOR)
Cálculo do CRC
 Um emissor deseja enviar D com d bits de dados.
 Um código de CRC R com r bits de comprimento 
deve ser gerado e anexado aos dados antes do 
envio.
 O receptor e o emissor conhecem um padrão de bits 
denominado G, com (r + 1) bits de comprimento.
 O bit mais significativo do gerador (mais à esquerda) 
deve ser 1.
Cálculo do CRC
 A base para o cálculo de R (código de CRC) é a 
fórmula:
 2r é o deslocamento dos bits de dados à esquerda r 
casas.
– Isso é: adição de r bits 0 no final dos bits de dados. 
Por exemplo:
Cálculo do CRC
 O emissor deseja enviar os bits de dados 111100101
 O gerador são os bits 101101
 Como calcular o CRC antes de enviar os dados???
CRC
Polinômio gerador:
G(x) = x5+x3+x2+x0
r = 5
Adiciona-se 5 bits no 
final dos bits de dados
Cálculo do CRC
 Após calcular o CRC cujos bits são 01010, o emissor 
envia os bits de dados mais os bits de CRC.
 O receptor utiliza os bits enviados e divide pelo 
gerador para verificar se os bits estão corretos.
Resto igual a zero:
Dados recebidos 
corretamente
Cálculo do CRC - Exercício
 O emissor deseja enviar os bits de dados 10101110
 O polinômio gerador é: G(x) = x4+x3+x0
1) Qual o padrão de bits do polinômio gerador?
2) Quantos bits deverão ser adicionados aos bits de 
dados? Qual o overhead? 
3) Qual o código CRC? 
4) Qual a sequência de bits enviada para o receptor?
5) Como o receptor verifica se os bits recebidos 
estão corretos? 
Cálculo do CRC - Exercício
 O emissor deseja enviar os bits de dados 10101110
 O polinômio gerador é: G(x) = x4+x3+x0
1) Qual o padrão de bits do polinômio gerador?
11001
2) Quantos bits deverão ser adicionados aos bits de 
dados? Qual o overhead? 4; overhead = 50%
3) Qual o código CRC? 1011
4) Qual a sequência de bits enviada para o receptor?
101011101011
5) Como o receptor verifica se os bits recebidos 
estão corretos? Ver slide anterior
CRC no STM32
AN4187
Application note
Using the CRC peripheral in the STM32 family
CRC no STM32
Detecção e Correção de Erros
Código de Hamming
 Código para a detecção de 
erros em transmissões de 
dados binários. Foi criado 
por Richard Hamming em 
1950.
 Permite a detecção e 
correção de um erro em um 
bloco de dados.
 Utiliza a técnica de inserção 
de bits redundantes no 
bloco de dados
Código de Hamming
Codificação:
1) Os bits da palavra de código são numerados a 
partir da direita, começando por 1;
2) É acrescentada informação redundante em 
posições que são potência de 2 (20=1, 21=2, 22=4, ...)
3) Os restantes são preenchidos com k bits de dados 
conhecidos, isto é, com a mensagem a transmitir;
 Ex.: Transmissão da mensagem: 1001
Posição 7 6 5 22=4 3 21=2 20=1
Mensagem 1 0 0 ? 1 ? ?
Código de Hamming
4) Cálculo dos bits de controle: conversão para binário 
das posições onde o bit de dados é igual a 1 
3 → 011
7 → 111
5) Aplicação de XOR aos valores obtidos:
0 1 1
xor 1 1 1
1 0 0
Posição 7 6 5 22=4 3 21=2 20=1
Mensagem 1 0 0 ? 1 ? ?
Código de Hamming
6) Inserção dos valores obtidos nas respectivas 
posições do bits de redundância
Posição 7 6 5 22=4 3 21=2 20=1
Mensagem 1 0 0 1 1 0 0
Código de Hamming
Decodificação:
1) Conversão para binário das posições onde o bit 
é igual a 1:
3 → 011
4 → 100
7 → 111
Posição 7 6 5 22=4 3 21=2 20=1
Mensagem 1 0 0 1 1 0 0
Código de Hamming
2) Aplicação do XOR aos valores obtidos:
0 1 1
1 0 0
xor 1 1 1
0 0 0
 Se o resultado for = 0, não houve erros na 
transmissão
 Se o resultado for ≠ 0, o resultado obtido convertido 
para decimal é igual à posição do erro
Código de Hamming
Código recebido sem erros: 
0 1 1
1 0 0
xor 1 1 1
0 0 0
Código recebido com erro:
1 0 0
xor 1 1 1
0 1 1 → 3 (posição do erro)
Posição 7 6 5 2
2=
4 3
21=
2
20=
1
Mensagem 1 0 0 1 1 0 0
Posição 7 6 5 2
2=
4 3
21=
2
20=
1
Mensagem 1 0 0 1 0 0 0
Código de Hamming – Exercício
 O emissor deseja enviar os bits de dados 10101110
1) Quantos bits de redundância deverão ser 
adicionados aos bits de dados? Qual o overhead?
2) Qual a sequência de bits enviada para o receptor?
3) Como o receptor verifica se os bits recebidos 
estão corretos?
Código de Hamming – Exercício
 O emissor deseja enviar os bits de dados 10101110
1) Quantos bits de redundância deverão ser 
adicionados aos bits de dados? Qual o overhead?
Resposta: 4 bits, overhead = 50% 
2) Qual a sequência de bits enviada para o receptor?
Resposta: 101001110010
3) Como o receptor verifica se os bits recebidos 
estão corretos?
Resposta: 1) Conversão para binário das posições onde os bits 
são iguais a 1; 2) Operação de XOR entre os valores binários. 3) 
Se resultado igual a 0, o código não tem erro.
Exercícios
Um transmissor deseja enviar para um receptor a 
seguinte sequência de bits: 1001 0110 0001 1001
Qual a sequência de bits a ser enviada pelo 
transmissor, considerando a inclusão de bits de 
redundância de acordo com os códigos de detecção e 
correção de erros abaixo?
a) Paridade, a cada 8 bits de dados
b) Paridade bi-dimensional, com diagrama de 4x4 bits
c) Checksum de 4 bits pelo método da soma binaria.
d) CRC, com G(x) = x6+x5+x1+x0, a cada 16 bits
e) Código de Hamming, a cada 16 bits
Exercícios
A seguinte sequência é recebida por um receptor:
011000101000
Caso o método de detecção e correção de bits seja o 
código de Hamming, responda:
a) Qual bit foi recebido com erro?
b) Qual a sequência de bits correta, desconsiderando 
os bits de redundância?
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 29
	Slide 30
	Slide 31
	Slide 32
	Slide 33
	Slide 34
	Slide 35
	Slide 36
	Slide 38
	Slide 39
	Slide 40
	Slide 41
	Slide 42
	Slide 43
	Slide 44
	Slide 45
	Slide 46
	Slide 47
	Slide 48