Aula 05
Detecção e Controle de
Erro
Prof. Dr. S. Motoyama
1
Problema 3: Detecção de erro (ED)
• Em meios físicos de transmissão, erros de transmissão podem ocorrer. As probabilidades de erro são diferentes para cada meio. • Duas abordagens gerais para tratamento de erros:
– Código corretor de erro
– Código detector de erro + um mecanismo de correção de erro quando os erros são detectados.
– Inserção de redundâncias para detecção ou correção de erro.
• Métodos de detecção de erro:
– Teste de redundância cíclica (Cyclic redundancy check, CRC)
– Soma de verificação (Checksum)
2
ED: Detecção de erro
• Códigos detectores de erro são normalmente inseridos em mais do que uma camada, por ex.,
–
–
–
–
HTTP
TCP (16-bits checksum para o cabeçalho de TCP e dados)
IPv4 (16-bits checksum para o cabeçalho de IP)
PPP/Ethernet (CRC-16, CRC-32 para o todo o quadro)
3
ED: paridade bi-dimensional
• A paridade 2-dim detecta todos os erros de 1, 2 e 3 bits, e a maioria dos erros de 4 bits.
Bits de paridade 0101001 1
Dados
Bytes de
Paridade
1101001
0
1011110
1
0001110
1
0110100
1
1011111
0
1111011
0
4
ED: Checksum
• Idéia básica:
– Some todas as palavras que são transmitidas e depois transmita o resultado daquela soma. 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. • Checksum na Internet:
– Um transmissor soma palavras de 16 bits usando a aritmética complemento de 1, e guarda o resultado no campo checksum. – Um receptor realiza a operação de checksum em todas as palavras de 16 bits. Se não há erro, o resultado deve ser tudo
1.
5
ED: Checksum
• A aritmética complemento de 1:
– Um inteiro negativo -x é representado como o complemento de x. Cada bit de x é invertido.
– O “vai 1” do bit mais significativo deve ser somado ao resultado • Por exemplo: checksum de palavras de 4 bits
– Dados: 1010 1100, e o seu checksum: 1000.
(0101+0011=1000)
– Dados enviados: 1010