04A - UFBA

REDES DE COMPUTADORES
Detecção e Correção de Erros
A Camada de Enlace
Serviços prestados
Serviços da camada
de Enlace
Encapsulamento
Endereçamento
Controle de
erros
Controle de
fluxo
Controle de
acesso
Objetivo da Aula de Hoje
Detecção e Correção de Erros
Tipos
de erros
Detecção de erros
Correção de erros
Tipos de Erros
Entendendo a importância do tratamento de erros
Se
ocorre um erro de 0,1s em uma transmissão de
56Kbps isso implica em 5,6K bits afetados
Como evitar erros?
Impossível, nosso
objetivo é detectá-lo e tratá-lo
Tipos de Erros
Erros Simples
Corresponde
Rajada de erros
Quando
a um erro isolado
uma sequência de bits são corrompidos
Se numa transmissão de uma seqüência de 8bits e
um deles chega corrompido, como descobrir?
Detecção de Erros
Redundância
Receptor
Dados
rejeitados
sim
Transmissor
Dados
Dados
não
Dados &
Redundância
Dados &
Redundância
Meio
Detecção de Erros
Técnicas
Métodos de detecção
Teste de paridade
Teste de redundância
cíclica (CRC)
Checksum
Detecção de Erros
Paridade
Nó receptor
Transmissor
Remove o bit de
paridade e aceita os
dados
Dados
sim
Rejeita
dados
Paridade OK?
não
Cálculo do bit de
paridade
Contagem de
bits
Bits
Meio de transmissão
Detecção de Erros
Paridade
Como
fazer um verificador de paridade?
Que porta lógica faz isso?
Detecção de Erros
Paridade
O
que acontece se a quantidade de erros for par?
10010011 (transmitido)
10010101 (recebido)
Como
resolver isso?
Detecção de Erros
Paridade Combinada
Dados originais
Linhas de paridade
Colunas de paridade
Dados e bits de paridade
Detecção de Erros
Paridade Combinada resolve tudo?
Detecção de Erros
Paridade Combinada resolve tudo?
?
Detecção de Erros
Paridade Combinada resolve tudo?
Dados originais
0
0
0
1
Linhas de paridade
Colunas de paridade
Dados e bits de paridade
Detecção de Erros
Paridade Combinada resolve tudo?
Dados originais
0
0
0
1
Linhas de paridade
Colunas de paridade
Dados e bits de paridade
Detecção de Erros
CRC
Dados
Dados
Divisor
Resto
Dados
Divisor
CRC
zero, aceito
diferente de zero, rejeitado
Receptor
Transmissor
Detecção de Erros
Gerador de CRC (Transmissor)
Dados mais zeros extras
Divisor
Quociente
Quando o bit mais à esquerda for
zero, devemos usar 0000 no lugar do
divisor original.
Resto
Detecção de Erros
Verificador de CRC (Receptor)
Dados + CRC
Divisor
Quociente
Quando o bit mais à esquerda for
zero, devemos usar 0000 no lugar do
divisor original.
Se Resto = 0, OK!
Detecção de Erros
Verificador de CRC (Receptor)
Dados + CRC
Divisor
Quociente
Quando o bit mais à esquerda for
zero, devemos usar 0000 no lugar do
divisor original.
Se Resto = 0, OK!
Detecção de Erros
Exemplo de descarte
Detecção de Erros
CRC
Polinômio
gerador de CRC é o nome dado para a
representação polinomial do divisor, por exemplo...
1101
X3 + X2 + 1
Porque isso é importante
Não deve
ser dividido por x
Garante que são detectaras rajadas de erros de comprimento
igual a do polinômio
Deve ser dividido pelo binômio
x+1
A segunda condição assegura que o CRC encontrará erros em
rajadas de comprimento ímpar
Detecção de Erros
CRC
Polinômio
Divisor
Detecção de Erros
CRC
Detecção de Erros
Checksum
Também
se baseia em redundância
Conceito é simples
Transmissor
Segmenta
o bloco de dados em k blocos de n bits
Soma os K segmentos
Soma é complementada para gerar o checksum
Checksum é enviado com os dados
Detecção de Erros
Funcionamento do Transmissor
1010100100111001
10101001 00111001
10101001+00111001
11100010 (sum)
00011101 (checksum
a ser enviado)
10101001 00111001 00011101
Detecção de Erros
Receptor
Divide
o bloco em k segmentos de dados de n bits
Faz a soma dos segmentos
Gera o checksum
Se dados forem iguais a zero, dados aceitos!
Detecção de Erros
Funcionamento do Receptor
101010010011100100011101
10101001 00111001 00011101
10101001+0111001+00011101
11111111 (sum)
00000000 (checksum)
Correção de Erros
Mas como corrigir erros?
Correção
por Retransmissão
Correção Antecipada
Quando os
dados são recebidos e é verificado que existiu
um erro na transmissão, seria necessário corrigi-lo!
Correção de Erros
Código de Hamming
Escalar
bits de redundância segundo seu código
Para 7 bits seria necessário escalar 4 bits
Número de
bits de dados
m
Numero de bits de redundância
r
Total de bits
m+r
1
2
3
2
3
5
3
3
6
4
3
7
5
4
9
6
4
10
7
4
11
Correção de Erros
Código de Hamming
Mas
como é feito?
R1: 1,3,5,7,9,11
R2: 2,3,6,7,10,11
R4: 4,5,6,7
R8: 8,9,10,11
Correção de Erros
Código de Hamming
r1 cuidará destes bits.
r2 cuidará destes bits.
r3 cuidará destes bits.
r4 cuidará destes bits.
Correção de Erros
Código de Hamming
Corrompido
O bit na posição 7 está errado
Perguntas finais
Qual a vantagem e desvantagem de cada código?
Onde este códigos são utilizados?
Falta apenas um assunto para a prova!