aula7b-redes

Prévia do material em texto

Fundamentos de Redes de Computadores
Professor: Rodrigo da Rosa Righi
Contato: rrrighi@unisinos.br
Aula: 7 - 09 de Abril de 2015
Dia/Horário: Quinta-Feira, 19:30 - 22:23
Você lembra da Aula 8?
Detecção e Correção de Erros
CRC e polinômio Gerador
Quantidade de bits do CRC
Agenda
Detecção e Correção de Erros
Código de Hamming
Método que detecta erros em até 
2 bits e permite correção de 1 bit
Adiciona diversos bits de verificação a um 
conjunto de bits de dados
Detecção e Correção de Erros
Código de Hamming
Cada bit de verificação é a paridade de um sub-
conjunto único de bits de dados
Ao receber um quadro de dados, o receptor 
verifica se os bits de verificação correspondem aos 
bits de dados
Se houver erros na transmissão, os bits de 
verificação que estiverem errados apontam o bit 
que foi alterado
Funcio-
namento
Transmissão da sequência 1001
Ao serem transmitidos, os bits de dados 
devem ser intercalados com os bits de 
verificação
Detecção e Correção de Erros
Código de Hamming
Os bits de verificação ocupam as posições 
correspondenes as potências de 2 
 1 0 0 1
 1 2 3 4 5 6 7
Atenção: Diferentemente do 
usual, teste método numera os 
bits da esquerda para a direita, 
começando de 1
Transmissão da sequência 1001
Detecção e Correção de Erros
Código de Hamming
Para preencher o bit de verificação de posição 1, 
deve-se calcular a paridade considerando os bits de 
dados das posições cuja decomposição contém o 
valor 1
Decompondo todos os bits de dados do exemplo:
3 = 2 + 1
5 = 4 + 1
6 = 4 +2
7 = 4 + 2 + 1
Portanto: O bit de verificação da posição 1 será a 
paridade dos bits 3, 5 e 7, ou seja: 
1 + 0 + 1 = 0
0 1 0 0 1
 1 2 3 4 5 6 7
Atenção de novo: Lembrar que 
qualquer número inteiro 
positivo pode ser decomposto 
em uma soma de potências de 2
Para preencher o próximo bit de verificação, o 
processo se repete:
Para preencher o bit de verificação de posição 2, 
deve-se calcular a paridade considerando os bits de 
dados das posições cuja decoposição contém o valor 
2.
Decompondo todos os bits de dados do exemplo:
3 = 2 + 1
5 = 4 + 1
6 = 4 + 2
7 = 4 + 2 + 1
Portanto: O bit de verificação da posição 1 será a 
paridade dos bits 3, 6 e 7, ou seja: 
1 + 0 + 1 = 0
0 0 1 0 0 1
 1 2 3 4 5 6 7
Transmissão da 
sequência 1001
Detecção e Correção de Erros
Código de Hamming
Por fim, para preencher o bit de verificação de 
posição 4, deve-se calcular a paridade considerando 
os bits de dados das posições cuja decoposição 
contém o valor 4.
Decompondo todos os bits de dados do exemplo:
3 = 2 + 1
5 = 4 + 1
6 = 4 + 2
7 = 4 + 2 + 1
Portanto: O bit de verificação da posição 1 será a 
paridade dos bits 5, 6 e 7, ou seja: 
0 + 0 + 1 = 1
0 0 1 1 0 0 1
 1 2 3 4 5 6 7
Mensagem final enviada 
com Código de Hamming
Transmissão da sequência 1001
Detecção e Correção de Erros
Código de Hamming
Verificação e Correção
Detecção e Correção de Erros
Código de Hamming
Verificação e correção:
Ao receber a seqüência de bits “0011001”, o 
receptor realiza a verificação:
Inicializa um contador qualquer em zero
Para cada bit de verificação, calcula se a 
paridade está correta
Se não estiver, soma ao contador a posição 
do referido bit
Ao final:
Se o contador estiver zerado, os dados 
estão corretos
Senão o valor do contador aponta o bit 
errado
Transmitidos = 0011001
Recebidos - 0011001 (ou seja, sem 
erros)
Cont = 0;
Pos 1. ⇒ 0011001 ⇒ 1 + 0 + 1 = 0 
⇒ ok
Pos 2. ⇒ 0011001 ⇒ 1 + 0 + 1 = 0 
⇒ ok
Pos 4. ⇒ 0011001 ⇒ 0 + 0 + 1 = 1 
⇒ ok
Ao final, o contador é 0, ou seja, os 
dados estão corretos
Transmitidos = 0011001
Recebidos = 0011101 
Cont = 0;
Pos 1. ⇒ 0011101 ⇒ 1 + 1 + 1 = 1 
⇒ erro
Cont = 0 + 1 = 1
Pos 2. ⇒ 0011101 ⇒ 1 + 0 + 1 = 0 
⇒ ok
Pos 4. ⇒ 0011101 ⇒ 1 + 0 + 1 = 0 
⇒ erro
Cont = 1 + 4 = 5
Ao final, o contador é 5, que é o bit 
errado. Basta inverter esse bit
Transmitidos = 0011001
Recebidos = 0011000 
Cont = 0;
Pos 1. ⇒ 0011000 ⇒ 1 + 0 + 0 = 1 
⇒ erro
Cont = 0 + 1 = 1
Pos 2. ⇒ 0011000 ⇒ 1 + 0 + 0 = 1 
⇒ erro
Cont = 1 + 2 = 3
Pos 4. ⇒ 0011000 ⇒ 0 + 0 + 0 = 0 
⇒ erro
Cont = 3 + 4 = 7
Ao final, o contador é 7, que é o bit 
errado. Basta inverter esse bit
Verificação e Correção
Detecção e Correção de Erros
Código de Hamming
Detecção de Erros em 2 bits
O código de Hamming também serve 
para detectar erros em até 2 bits
Detecção e Correção de Erros
Código de Hamming
Somente detecta, mas não corrige
Exemplo:
Transmitidos = 0011001
Recebidos = 0011100
Pos 1. ⇒ 0011100 ⇒ 1 + 1 + 0 = 0 ⇒ ok
Pos 2. ⇒ 0011100 ⇒ 1 + 0 + 0 = 1 ⇒ erro
Pos 4. ⇒ 0011100 ⇒ 1 + 0 + 0 = 1 ⇒ ok
Analisando o Código de Hamming
Tamanho do código a ser transmitido 
depende da quantidade de bits de dados
Detecção e Correção de Erros
Código de Hamming
Código de Hamming sempre desperdiça 
parte da largura de banda enviando bits de 
verificação
Para 4 bits de dados, 7 no total (3 bits de 
verificação)
Para 5 bits de dados, 9 no total ( V V D 
V D D D V D)
Para 11 bits de dados, 15 no total (4 bits 
de verificação)
Para 12 bits de dados, 17 bits no total (5 
bits de verificação)
No exemplo trabalhado, para a 
transmissão de 4 bits de dados são 
necessários ao todo 7 bits
Eficiência de 57% A eficiência aumenta 
quando são 
transmitidos mais bits 
de dados?Sim
Entretanto, quanto mais bits são 
transmitidos, maior a probabilidade de 
erros
Exercícios para o Grau B
Encontre a string que será transmitida ao 
enviar os dados abaixo
Detecção e Correção de Erros
Código de Hamming
010
0100111
0011
11111