201785 163347 TEE+I+ +1+ +Códigos+de+Detecção+e+Correção+de+Erros

Prévia do material em texto

Tópicos Especiais
de Engenharia I
Códigos de Detecção e 
Correção de Erros
Prof. Fernando Luiz Trazzi Junior
Conteúdo da aula
Introdução a segurança e veracidade dos dados
Códigos de correção e códigos de correção
Checksum
CRC - Cyclic Redundancy Check
Código de Hamming
Introdução
Falha, Erro e Defeito
Confiabilidade dos sistemas
 Os sistemas computacionais devem oferecer 
confiabilidade no seu funcionamento, evitando o 
prejuízo das pessoas que os utilizam e do próprio 
equipamento físico
 Um sistema computacional 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 eletromagnéticas, envelhecimento de 
componentes, curto-circuito, etc.
Erros
 Os erros são inevitáveis em qualquer sistema de 
comunicação real;
 A distribuição dos erros não é homogênea: pode 
ocorrer erros em 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 dos dados de volta à origem);
– 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ódigos 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 
(bits de redundância);
 Esses bits podem ser obtidos a partir da informação 
original e o receptor recalcula os bits extras
Códigos 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ódigos 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 método mais conhecido é o Código de Hamming.
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 transmissor só gera palavras válidas.
 Logo, se o sistema receptor receber alguma palavra 
inválida, trata-se de um erro!
Códigos de 
Detecção e 
Correção de Erros
Detecção de Erros - 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 o receptor não 
consiga detectar os erros.
 No exemplo anterior, se o receptor recebesse a 
sequência:
11010010
 O receptor calcularia o bit de paridade igual a 0, o 
mesmo bit de paridade enviado. Porém, não é 
possível detectar o erro de 2 bits por este método.
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 método de paridade.
 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
 Soma de todas as palavras que são transmitidas e 
depois transmissão do resultado daquela soma 
(checksum) junto com as palavras. 
 Se quaisquer um dos bits transmitidos, incluindo os 
do checksum, sofrer algum erro, então o resultado da 
operação soma não será correto no receptor.
 Método relativamente simples de detecção de erros
 Dois métodos para calcular o checksum:
– Soma aritmética
– Ou-Exclusivo entre bits
Detecção de Erros - Checksum
 Método da soma aritmética:
1) Realiza-se a soma aritmética binária de uma 
sequência de palavras (conjunto de bits)
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
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)
Detecção de Erros – Checksum
Exercício
 Verifique se a sequência abaixo, enviada com 
checksum pelo método da soma, foi recebida 
corretamente ou se há algum erro. Cada palavra 
possui 8 bits e a última palavra é o checksum. 
01100101 10101100 00110011 11011010
Detecção de Erros – Checksum
Exercício
 Verifique se a sequência abaixo, enviada com 
checksum pelo método da soma, foi recebida 
corretamente ou se há algum erro. Cada palavra 
possui 8 bits e a última palavra é o checksum.
01100101 10101100 00110011 11011010
Como o resultado da soma de todas as palavras é 
diferente de 11111111, há erro na sequência de bits.
Detecção de Erros - Checksum
 Método do XOR:
1) Realiza-se a operação XOR entre os bits que estão 
na mesma posiçãode 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 do XOR:
10011000 00011001 11000011
Detecção de Erros – Checksum
Exercício
 Dada a sequência de 3 bytes abaixo, calcule o 
checksum pelo método do XOR:
10011000 00011001 11000011
Checksum: 01000010 
(NÃO é necessário inverter o resultado da soma antes 
de enviar a mensagem)
Detecção de Erros – Checksum
Exercício
 Verifique se a sequência abaixo, enviada com 
checksum pelo método do XOR, foi recebida 
corretamente ou se há algum erro. Cada palavra 
possui 8 bits e a última palavra é o checksum. 
01100101 10101100 00110011 11011010
Detecção de Erros – Checksum
Exercício
 Verifique se a sequência abaixo, enviada com 
checksum pelo método do XOR, foi recebida 
corretamente ou se há algum erro. Cada palavra 
possui 8 bits e a última palavra é o checksum.
01100101 10101100 00110011 11011010
Como o resultado da soma de todas as palavras é 
diferente de 00000000, há erro na sequência de bits.
Detecção de Erros – CRC
Cyclic Redundancy Check
 Uma forma mais confiável de detecção de erros
 É um número, calculado a partir de uma mensagem, 
e transmitido/armazenado 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.
 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 a mensagem 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 deve ser igual a 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.
– Isto é: adição de r bits 0 no final dos bits de dados. Por 
exemplo:
Cálculo do CRC (Exemplo)
O emissor deseja enviar os bits de dados 111100101
O polinômio gerador é G(x) = x5+x3+x2+x0, ou seja, a 
divisão deverá ser feita pelos bits 101101
CRC
Polinômio gerador:
G(x) = x5+x3+x2+x0
r = 5
Adiciona-se 5 bits após
os 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
Um 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
Um 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
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-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 erro:
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
22=
4 3
21=
2
20=
1
Mensagem 1 0 0 1 1 0 0
Posição 7 6 5
22=
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.
d) CRC, com G(x) = x4+x1+x0, a cada 8 bits
e) Código de Hamming, a cada 16 bits
Exercícios
A seguinte sequência é recebida por um receptor, 
que identifica um erro no código:
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,ou seja, qual a mensagem 
original?
Exercícios
Um transmissor deseja enviar para um receptor a 
seguinte sequência de bits:
01001100 10010101 01100001 00001010
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, com um bit de paridade a cada 8 bits
b) Paridade bi-dimensional
c) Checksum pelo método da soma
d) Checksum pelo método do XOR
e) CRC, com G(x) = x6+x4+x1, a cada 16 bits
f) Código de Hamming, a cada 16 bits de dados