TeleprocessamentoII 01

Prévia do material em texto

Teleprocessamento II 
Detecção e correção de erros 
Teleprocessamento II 
Detecção e correção de erros 
Teleprocessamento II 
Detecção e correção de erros 
Temas deste tópico 
 
1. Controle de erros; 
2. Códigos de detecção de erros; 
3. Códigos de correção de erros; 
Teleprocessamento II 
Detecção e correção de erros 
Controle de erros 
 Alguns canais, como a fibra óptica nas redes de 
telecomunicações, possuem taxas de erro muito pequenas, de 
modo que os erros de transmissão são uma ocorrência rara. Mas 
outros canais, especialmente enlaces sem fios e antigos circuitos 
terminais, possuem taxas de erro muito maiores. Para esses 
enlaces, os erros de transmissão são a norma. Eles não podem 
ser evitados a um custo razoável em termos de desempenho. A 
conclusão é que os erros de transmissão estão aqui para ficar. O 
que precisamos aprender é como lidar com eles. 
Teleprocessamento II 
Detecção e correção de erros 
Controle de erros 
 
 Sabendo da possibilidade de ocorrência de erros na 
transmissão, como podemos nos certificar que as 
informações digitais cheguem ao destino exatamente 
iguais como elas foram enviadas pela fonte ? 
Teleprocessamento II 
Detecção e correção de erros 
Controle de 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. 
 
Para isso é preciso descobrir se os dados estão errados ou não. 
Teleprocessamento II 
Detecção e correção de erros 
Controle de erros 
 Os projetistas de redes desenvolveram duas estratégias 
básicas para lidar com os erros. Ambas acrescentam 
informações redundantes aos dados enviados. Seguem elas: 
• Códigos de detecção de erros 
– Estratégia que inclui redundância suficiente apenas para permitir que 
o receptor deduza que houve um erro (mas não qual erro) e solicite 
uma retransmissão. 
• Códigos de correção de erros 
– Estratégia que inclui mais informações redundantes suficientes para 
permitir que o receptor deduza quais foram os dados transmitidos. 
Teleprocessamento II 
Detecção e correção de erros 
Controle de erros 
Distância de Hamming 
 
• Se duas palavras de código estiverem separadas por uma distância de 
Hamming d, será preciso d erros simples para converter uma na outra. 
– Ex: 11110001 e 00110000 estão a uma distância de Hamming = 3. 
 
• Para calcular a distância de Hamming de um código completo, deve-se 
calcular a distância entre todos os pares de palavras de código. A distância 
mínima é a distância de Hamming. 
• Para se detectar d erros simples, é preciso um código com distância d + 1. 
• Para se corrigir d erros simples, é preciso um código com distância 2d+1. 
Teleprocessamento II 
Detecção e correção de erros 
Controle de erros 
Teleprocessamento II 
Detecção e correção de erros 
Controle de erros 
Teleprocessamento II 
Detecção e correção de erros 
Controle de erros 
Exemplo 01 
 
• Código de detecção de erro com um bit de paridade. 
– O bit de paridade é escolhido de modo que o número de bits 1 na 
palavra de código seja par (ou ímpar). 
– Tal código tem distância 2, pois precisa de 2 erros simples para ir de 
uma palavra válida para uma outra palavra válida. 
– Pode ser usado para se detectar um erro. 
Teleprocessamento II 
Detecção e correção de erros 
Controle de erros 
Exemplo 01 
 
2 
Teleprocessamento II 
Detecção e correção de erros 
Controle de erros 
Exemplo 02 
 
• Código contendo apenas 4 palavras de código válidas: 
 0000000000, 0000011111, 1111100000, 1111111111 
– Tem distância 5, portanto pode corrigir dois erros simples. 
– Se a palavra lida é 0000000111, o sistema sabe que a original é 
0000011111, considerando-se que ocorreu 2 erros simples. 
– Se a palavra correta é 0000000000, mas ocorreu 3 erros simples 
resultando em 0000000111, o erro não pode ser corrigido. 
 
Teleprocessamento II 
Detecção e correção de erros 
Controle de erros 
 Quando é vantajoso somente detectar os erros? 
 
• Em canais altamente confiáveis (ex.: fibra) 
• Comunicações de tempo real. 
• Dados intolerantes a erros. 
• É possível esperar por retransmissão. 
Teleprocessamento II 
Detecção e correção de erros 
Controle de erros 
 Quando é vantajoso corrigir os erros? 
 
• Em canais com muito ruído (ex.: enlaces sem fio) 
• Comunicações simplex. 
• Não é possível esperar por retransmissão. 
Teleprocessamento II 
Detecção e correção de erros 
Controle de erros 
Teleprocessamento II 
Detecção e correção de erros 
Controle de erros 
EDC = Bits de detecção e correção 
de erros (redundância); 
D = Dados protegidos por 
verificação de erro, podem incluir 
campos de cabeçalho. 
 
Detecção de erro não 100% 
confiável! 
• Protocolo pode perder alguns erros, 
mas raramente. 
• Maior campo EDC gera melhor 
detecção e correção. 
Teleprocessamento II 
Detecção e correção de erros 
Técnicas 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; 
• Alguns exemplos de métodos de detecção são. 
– Verificação de Paridade. 
– CRC (Cyclic Redundant Check). 
– Checksum. 
 
Teleprocessamento II 
Detecção e correção de erros 
Técnicas de Detecção de Erros 
Paridade de um Único Bit 
 
• Utiliza-se um Bit extra inserindo ao conjunto de bits do código 
transmitido. 
• Paridade par e paridade impar. 
• Paridade par, o bit extra assume o valor 0 ou 1 de modo que o total de 
bits 1 seja par. 
– Exemplo: 
 P 0 1 1 1 0 0 0 
P 0 1 1 1 1 0 0 
1 0 1 1 1 0 0 0 
0 0 1 1 1 1 0 0 
Teleprocessamento II 
Detecção e correção de erros 
Técnicas de Detecção de Erros 
Teleprocessamento II 
Detecção e correção de erros 
Técnicas de Detecção de Erros 
 Paridade Bidimensional 
 
• Detecta e corrige erros de único bit. 
Teleprocessamento II 
Detecção e correção de erros 
Técnicas de Detecção de Erros 
 CRC (Cyclic Redundant Check*) 
* Verificação de Redundância Cíclica 
 
• Muito usada na prática (Ethernet, 802.11 WiFi, ATM). 
• Se baseia em tratar sequências de bits. 
• Analisa bits de dados, D, como um número binário. 
• Escolha padrão de bits r + 1 (gerador), G. 
 
Teleprocessamento II 
Detecção e correção de erros 
Técnicas de Detecção de Erros 
 CRC (Cyclic Redundant Check*) 
* Verificação de Redundância Cíclica 
 
• Objetivo: escolher r bits de CRC, R, tal que: 
– <D,R> exatamente divisível por G (módulo 2); 
– receptor sabe G, divide <D,R> por G. Se resto diferente de zero: erro detectado! 
– pode detectar todos os erros em rajada menores que r + 1 bits. 
Teleprocessamento II 
Detecção e correção de erros 
Técnicas de Detecção de Erros 
 CRC (Cyclic Redundant Check*) 
* Verificação de Redundância Cíclica 
 
• Exemplos CRC: 
– Queremos: 𝐷. 2𝑟 XOR 𝑅 = 𝑛𝐺 
 
de modo equivalente: 
 𝐷. 2𝑟 = 𝑛𝐺 XOR 𝑅, 
 
de modo equivalente: 
se dividirmos D . 2r por G, queremos resto R 
𝑅 = resto
𝐷.2𝑟
𝐺
. 
Teleprocessamento II 
Detecção e correção de erros 
Técnicas de Detecção de Erros 
Checksum 
 
• Usado na Internet (protocolo TCP) com as seguintes etapas: no emissor a 
mensagem é dividida em grupos de 16 bits, e o checksum é inicializado 
como zero. 
• Todos os grupos de 16 bits são somados usando-se a adição de 
complemento um, então a soma écomplementada e se torna o 
checksum, que é enviado junto com os dados. 
• No receptor, a mensagem (inclusive o checksum) é dividida em grupos de 
16 bits, que são somadas usando complemento um. 
 
Teleprocessamento II 
Detecção e correção de erros 
Técnicas de Detecção de Erros 
Checksum 
 
• Realiza a transmissão de todas as palavras junto com o resultado da soma 
binária de todas elas. 
– Inclui o bit de transporte; 
– Inversão do valor dos bits do checksum. 
 
• A soma é complementada e se torna o novo checksum, se o valor do 
checksum for zero, a mensagem é aceita, caso contrário é rejeitada. 
 
 
Teleprocessamento II 
Detecção e correção de erros 
Técnicas de Detecção de Erros 
Checksum 
 
• Dado os dados iniciais de duas palavras de 8 bits: 00111101 00001101 
00111101 + 00001101 = 01001010 -> Checksum 
 10110101 -> Checksum invertido 
 
• O emissor envia o checksum invertido ao receptor. 
• Em seguida, no receptor as palavras são novamente somadas e 
comparadas com checksum que foi enviado, ou seja, checar a soma. 
 
 
 
Teleprocessamento II 
Detecção e correção de erros 
Técnicas de Detecção de Erros 
Checksum 
 
• Se em qualquer um dos dados transmitidos tiver algum erro este será 
descoberto, pois, no receptor, é recalculado e ocorre a soma do novo 
checksum com o checksum enviado, que terá um resultado diferente de 
“1”. 
 
 
 
Teleprocessamento II 
Detecção e correção de erros 
10000001 
10110100 
10100100 
00011011 
11001101 
Teleprocessamento II 
Detecção e correção de erros 
Técnicas de Correção de Erros 
 
• Mecanismo que permite que o receptor localize e 
corrija o(s) erro(s) sem precisar da retransmissão. 
 
• Alguns exemplos de métodos de correção são. 
– códigos de Hamming; 
– códigos de convolução binários; 
– códigos de Reed-Solomon; 
– códigos de verificação de paridade de baixa densidade. 
 
Teleprocessamento II 
Detecção e correção de erros 
Técnicas de Correção de Erros 
Códigos de Hamming 
 
1. Os bits da palavra de código são numerados a partir da esquerda, 
começando por 1; 
2. É acrescentada informação redundante em posições pré-definidas, ou 
seja, os bits que são potência de 2 vão ser bits de controle (2𝑛); 
3. Os restantes são preenchidos com k bits de dados conhecidos, isto é, 
com a mensagem a transmitir; 
Teleprocessamento II 
Detecção e correção de erros 
Técnicas de Correção de Erros 
Códigos de Hamming 
 
4. Cálculo dos bits de controle, isto é, conversão para binário das posições 
≠2𝑛 e valor=1; 
 3 – 011 
 7 – 111 
5. Aplicação do OU Exclusivo (XOR – ⊕) aos valores obtido no ponto 
anterior 
 0 1 1 
 1 1 1 
 1 0 0 
 3ª 2ª 1ª; 
Teleprocessamento II 
Detecção e correção de erros 
Técnicas de Correção de Erros 
Códigos de Hamming 
 
6. Inserção dos valores obtidos nas respectivas posições do bits de 
paridade (ponto 2.); 
 
 
 
 
 
 
7. Mensagem a transmitir: 00110011 
Teleprocessamento II 
Detecção e correção de erros 
Técnicas de Correção de Erros 
Códigos de Hamming – Descodificação 
 
1. Conversão para binário das posições = 1; 
 
2. Aplicação do OU Exclusivo (XOR -⊕) aos valores obtido no ponto 
anterior: 
 
• Se o resultado for = 0, não houve erros na transmissão 
• Se for ≠ 0, o resultado obtido convertido para decimal é igual à 
posição do erro 
Teleprocessamento II 
Detecção e correção de erros 
Técnicas de Correção de Erros 
Códigos de Hamming 
 
• Exemplo