Erros e Protocolos de Recuperação
Códigos detectores e correctores de erros.
Instituto Superior de Engenharia de Lisboa
Departamento de Engenharia, Electrónica, Telecomunicações e
Computadores
Redes de Computadores
Características do canal
• BER (Bit Error Rate)
• Probabilidade de ter 1 bit errado num intervalo de tempo
• (Influencia o tamanho máximo das tramas)
• PErrorFrame
n
Perroframe = ∑
i =1
( )(1 − p )
n
i
n −i
p i = 1 − (1 − p )
n
p = probabilidade de um bit ser corrompido = BER
1-p = probabilidade de um bit não ser corrompido
n = número de bits de uma trama
2007-02-26
Erros e Tecnicas de Detecção e Correcção
2
Tipo de erros no canal de transmissão
• Erros isolados (Single bit error)
• Erros seguidos (Burst errors ou erros em rajada)
– Burst: conjunto de B bits, que começa e acaba com um bit errado e que
dista do próximo burst, B ou mais bits
2007-02-26
Erros e Tecnicas de Detecção e Correcção
3
Erros de transmissão: soluções
• Métodos detectores de erros
–
–
–
–
Feedback (backward) error control
Redundância
Algoritmo de detecção
Retransmissão
• Métodos correctores de erros
– Forward Error Control (FEC)
– Exigem uma maior redundância
– Algoritmo de correcção
2007-02-26
Erros e Tecnicas de Detecção e Correcção
4
Métodos detectores de erros
• Bit de paridade
• Detecta todos os erros em número ímpar de bits
• Ao nível do caracter
• Paridade de coluna (com bit de paridade)
•
•
•
•
Ao nível da trama
Detecta todos os erros em número ímpar de bits
Detecta todos os erros em número par de bits em número ímpar de linhas
Detecta alguns erros em número par de bits em número par de linhas
• Checksum (com bit de paridade)
• Ao nível da trama
• Detecta mais erros que a paridade de coluna
2007-02-26
Erros e Tecnicas de Detecção e Correcção
5
Métodos detectores de erros
Bit de paridade
2007-02-26
Erros e Tecnicas de Detecção e Correcção
6
Métodos detectores de erros
Paridade de coluna
2007-02-26
Erros e Tecnicas de Detecção e Correcção
7
Métodos detectores de erros
Cyclic Redundancy Check (CRC)
CRC - Cyclic Redundancy Check
ou FCS (Frame Check Sequence) ou códigos polinomiais
Resto da divisão de módulo 2 da mensagem por um gerador, adicionando à mensagem.
Detecta:
•
•
•
•
todos os erros em 2 bits
todos os erros em número ímpar de bits
todos os erros em burst menor que 16 bits
quase todos (99.99%) os erros em burst maior ou igual que 16 bits
2007-02-26
Erros e Tecnicas de Detecção e Correcção
8
Cyclic Redundancy Check
• M(x) é a mensagem a transmitir.
• G(x) é o polinómio gerador de grau n
(com n+1 bits).
• A trama a transmitir será:
M(x) x 2n
.....
......
....
G(x)
Q(x)
R(x)
– M(x) x 2n + R(x)
• G(x) é conhecido pelo receptor e pelo
transmissor.
• A escolha de G(x) determina quais os
tipos de erros que são detectados.
2007-02-26
Erros e Tecnicas de Detecção e Correcção
Mensagem
n bits
M(x)
R(x)
Trama transmitida
9
Cyclic Redundancy Check
Teoria de códigos polinomiais
Exemplos de
códigos geradores
2007-02-26
Erros e Tecnicas de Detecção e Correcção
10
CRC – Cálculo do código no transmissor
• M(x)=11100110 G(x)=11001
11100110 0000 | 11001
0010111
10110110
011100
00101 00
011 010
00 0110
• Mensagem enviada: 11100110 0110
2007-02-26
Erros e Tecnicas de Detecção e Correcção
11
CRC – Verificação da trama no receptor (sem erros)
• Mensagem recebida: 11100110 0110
• M(x)=11100110 G(x)=11001
11100110 0110 |11001
0010111
10110110
011100
00101 01
011 001
00 0000
2007-02-26
Erros e Tecnicas de Detecção e Correcção
12
CRC – Verificação da trama no receptor (com erros)
• Mensagem recebida: 11110010 0110
• M(x)=11100110 G(x)=11001
11110010 0110 | 11001
0011101
10101111
001000 0
00100 11
010 101
01 1000
0 0001
• Detectou erro porque a divisão não deu resto zero.
2007-02-26
Erros e Tecnicas de Detecção e Correcção
13
CRC – Exemplo com erro no código CRC
2007-02-26
Erros e Tecnicas de Detecção e Correcção
14
Implementação hardware do algoritmo de CRC
Transmissor
G(x)=x3+1
2007-02-26
Erros e Tecnicas de Detecção e Correcção
15
Implementação hardware do algoritmo de CRC
Receptor
2007-02-26
Erros e Tecnicas de Detecção e Correcção
16
Métodos correctores de erros
• Códigos de Hamming
–
–
–
–
Corrige erros de bit
Não aplicável em situações de erros de rajada
Pouco utilizado em comunicações de dados
Utilizável em sistemas de memórias semicondutores
• Códigos convolucionais
–
–
–
–
Mais indicado para comunicações de dados
A informação a ser transmitida sofre uma convolução
Cada bit transmitido vai depender dos bits anteriores
Exemplos de códigos correctores: Hamming, convolucional, outros (Reed Solomon)
2007-02-26
Erros e Tecnicas de Detecção e Correcção
17
Códigos correctores – terminologia
• Codeword é o conjunto formado pelos bits de informação e os bits de
protecção.
• Distância de Hamming (d) é o número mínimo de bits que diferem entre si
quaisquer duas palavras do código.
– detecta todos os n bits errados (pode detectar mais mas não exaustivamente) d=n+1
– corrige todos os n bits errados d=2n+1
– ex: código com bit de paridade d=2
2007-02-26
Erros e Tecnicas de Detecção e Correcção
18
Sumário e bibliografia
• Sumário:
– Códigos detectores de erro
• Bit de paridade
• Soma de bloco
• CRC
– Códigos correctores de erro
• Códigos de Hamming
• Bibliografia
– “Data Communications, Computer Networks and Open Systems”, Fred Halsall,
Cap 2;
2007-02-26
Erros e Tecnicas de Detecção e Correcção
19