Interfaces e transmissão de dados
3 Camada de ligação de dados
Camada de ligação de dados. Sincronismo e detecção de erros
3 – Camada de ligação de dados
Responsável:
Rui Silva
Data:
1ª Ano 2º Semestre 2010 / 2011
Versão
Pág.:
2.2
1/19
Interfaces e transmissão de dados
Camada de ligação de dados. Sincronismo e detecção de erros
3.1.2 Detecção e correcção de erros
3.1.2 – Detecção e correcção de erros
Responsável:
Rui Silva
Data:
1ª Ano 2º Semestre 2010 / 2011
Versão
Pág.:
2.2
2/19
Interfaces e transmissão de dados
3.1.2.2 FEC
Camada de ligação de dados. Sincronismo e detecção de erros
3.1.2.2 – FEC – Forward Error Correction
Responsável:
Rui Silva
Data:
1ª Ano 2º Semestre 2010 / 2011
Versão
Pág.:
2.2
3/19
Interfaces e transmissão de dados
Introdução
Camada de ligação de dados. Sincronismo e detecção de erros
Detecção e correcção de erros
Forward error correction (FEC)
•Recorre aos códigos correctores de erros (Hamming, Convolucional, Reed Solomon, etc...)
•Tal como anteriormente, é transmitida informação redundante (adicional), aos bits de
informação, que formam uma palavra de código (codeword)
•O receptor corrige os erros através da procura da palavra de código mais próxima da
mensagem recebida (mais próxima = maior probabilidade)
Responsável:
Rui Silva
Data:
1ª Ano 2º Semestre 2010 / 2011
Versão
Pág.:
2.2
4/19
Interfaces e transmissão de dados
Camada de ligação de dados. Sincronismo e detecção de erros
Detecção e correcção de erros
Forward error correction (FEC)
•Análise de Hamming (1950)
•Hamming estabeleceu as principais bases teóricas para detecção e correcção de erros
Definições:
•Palavra de código (codeword): é o conjunto formado pelos bits de informação e os bits redundantes:
m são o número de bits de informação ou de dados
r são o número de bits redundantes ou de código
l são o número de bits que compõem a palavra de código, em que: l = m + r
•Distância de Hamming (d): é o número mínimo de bits que duas palavras de código diferem entre si
A distância de Hamming é calculada pela operação XOR das duas palavras de código
Ex: Considere as palavras de código:10001001 e 10110001
10001001
⊕10110001
00111000 =>Diferem entre si de três posições de bit (onde o resultado foi 1)
São necessários 3 bits = d, para transformar uma palavra de código noutra.
Responsável:
Rui Silva
Data:
1ª Ano 2º Semestre 2010 / 2011
Versão
Pág.:
2.2
5/19
Interfaces e transmissão de dados
Camada de ligação de dados. Sincronismo e detecção de erros
Detecção e correcção de erros
Forward error correction (FEC)
•Análise de Hamming (1950)
•Duas palavras de código com d = n, requerem n erros de bit simples para converter uma na outra
•Todas as combinações de bits de dados são possíveis: 2 m bits de dados ( m = nº de bits de dados)
l
m
r
m+r
•Nem sempre todas as combinações de bits redundantes 2 = 2 .2 = 2
são possíveis
(Depende da forma como são calculados os bits redundantes)
•Dado o algoritmo para cálculo dos bits redundantes, é possível construir a lista completa das
palavras de código possíveis e desta achar duas, cuja distância de Hamming seja mínima. Esta
distância é chamada distância de Hamming do código completo.
Responsável:
Rui Silva
Data:
1ª Ano 2º Semestre 2010 / 2011
Versão
Pág.:
2.2
6/19
Interfaces e transmissão de dados
Camada de ligação de dados. Sincronismo e detecção de erros
Detecção e correcção de erros
Forward error correction (FEC)
•Análise de Hamming (1950)
•Propriedades da detecção e correcção de erros
•Para detectar n erros, é necessário um código com uma distância de Hamming:
d = n + 1 bits (4.9)
•Prova: A ocorrência de n erros simples não conseguem transformar uma palavra de código válida
noutra palavra de código válida. (Seriam necessários n=d como verificado no slide 55). No entanto
poderão existir duas palavras de código válidas à mesma distância não sendo por isso possível
saber em todos os casos qual a correcta. (Detecta erros em todos estes casos e corrige-os apenas
em alguns)
•Para corrigir n erros, é necessário um código com uma distância de Hamming: d = 2 n + 1 bits (4.10)
d −1
Ou corrige n =
erros com n arredondado para baixo
2
•Prova: As palavras de código válidas estarão tão longe, que mesmo com n erros simples, a
palavra de código original está mais próxima que qualquer outra palavra de código, podendo ser
determinada de forma unívoca.
Responsável:
Rui Silva
Data:
1ª Ano 2º Semestre 2010 / 2011
Versão
Pág.:
2.2
7/19
Interfaces e transmissão de dados
Camada de ligação de dados. Sincronismo e detecção de erros
Detecção e correcção de erros
Forward error correction (FEC)
•Análise de Hamming (1950)
•Exemplo de aplicação distância de Hamming
•Considere um alfabeto de código com apenas 4 palavras de código válidas:
A=0000000000
B=0000011111
C=1111100000
D=1111111111
Distância de Hamming: d = 5
Detecta n = d − 1 = 4 . Todos os erros de 4 bits
Corrige n =
d −1
= 2 . Todos os erros de 2 bits
2
•Considere que se recebe a palavra de código 0011011111
•Tem a probabilidade Pe 7 (1 − Pe ) 3 de ser A
•Tem a probabilidade Pe 2 (1 − Pe ) 8 de ser B
Seria corrigida para a palavra B, pois é a que
se encontra mais “próxima” ou provável da
palavra recebida.
•Tem a probabilidade Pe 8 (1 − Pe ) 2 de ser C
•Tem a probabilidade Pe 3 (1 − Pe ) 7 de ser D
Responsável:
Rui Silva
Data:
1ª Ano 2º Semestre 2010 / 2011
Versão
Pág.:
2.2
8/19
Interfaces e transmissão de dados
Código de Hamming
Camada de ligação de dados. Sincronismo e detecção de erros
Detecção e correcção de erros
Forward error correction (FEC)
•Código de Hamming : Contrução das palavras de código para:
•Distância de Hamming d= 3.
•Corrige todos os erros de
n=
d −1
=1
2
bit em cada palavra de código (codeword)
•Numerar os bits da direita para a esquerda começando em 1
0
1
2
k
•Posições dos bits correctores são todas as posições que são potências de 2: 2 , 2 , 2 ...(2 = m )
com k inteiro ≥ 0 (2k = m. Representa o nº de bits de informação [sem bits redundantes])
Para o caso de dados com m= 8 bits, as posições dos bits correctores serão: 20, 21 , 22 e 23
•Todas as outras posições são bits de dados.
•Conteúdo dos bits correctores: soma (XOR) do valor da posição de cada bit da palavra de
código que se encontrar a 1 (Paridade)
Responsável:
Rui Silva
Data:
1ª Ano 2º Semestre 2010 / 2011
Versão
Pág.:
2.2
9/19
Interfaces e transmissão de dados
Camada de ligação de dados. Sincronismo e detecção de erros
Algoritmo de construção do código de Hamming
Detecção e correcção de erros
Forward error correction (FEC)
•Código de Hamming - Exemplo
•Mensagem a transmitir:
10001101 (8 bits)
1 – Colocação dos bits correctores nas posições que são potências de 2
•Como temos 8 bits, as potências de 2 são: 2 0 , 21 , 2 2 e 2 3
Posição do bit
Valor
12
11
10
9
23 = 8 7
6
5
22 = 4 3
X
X
21 = 22 0 = 1
X
X
•Nota: Verifica-se que a palavra de código irá conter 12 bits ( 4 redundantes)
2 – Colocação da mensagem a transmitir nas posições em falta:
12
11
10
9
1
0
0
0
23 = 8 7
X
1
6
5
1
0
X
Responsável:
Data:
Rui Silva
22 = 4 3
1
21 = 22 0 = 1
X
1ª Ano 2º Semestre 2010 / 2011
X
Versão
Pág.:
2.2
10/19
Interfaces e transmissão de dados
Camada de ligação de dados. Sincronismo e detecção de erros
Detecção e correcção de erros
Forward error control (FEC) – detecção e correcção de erros
•Código de Hamming - Exemplo
3 – Cálculo dos valores dos bits redundantes:
•É a soma (XOR) do valor da posição de cada bit da palavra de código que se encontrar a 1
Posição do bit
Valor
12
11
10
9
1
0
0
0
23 = 8 7
X
1
6
5
1
0
22 = 4 3
X
21 = 22 0 = 1
1
X
X
1100 (12 ) ⊕ 0111 ( 7 ) ⊕ 0110 ( 6 ) ⊕ 0011 (3) = 1110
4 – Substituir o X pelo valor calculado:
•Palavra de código a transmitir: 100011101110
Responsável:
Rui Silva
Data:
1ª Ano 2º Semestre 2010 / 2011
Versão
Pág.:
2.2
11/19
Interfaces e transmissão de dados
Camada de ligação de dados. Sincronismo e detecção de erros
Algoritmo de detecção e correcção de erros do código de Hamming
Detecção e correcção de erros
Forward error correction (FEC)
•Código de Hamming – Recepção
•À recepção é efectuada a soma (XOR) do valor da posição de cada bit da palavra de
código que se encontrar a 1
•Caso o resultado seja igual a 0 -> Indica que não houve erros
•Caso o resultado seja diferente de 0 -> Indica a posição onde houve o erro.
Responsável:
Rui Silva
Data:
1ª Ano 2º Semestre 2010 / 2011
Versão
Pág.:
2.2
12/19
Interfaces e transmissão de dados
Camada de ligação de dados. Sincronismo e detecção de erros
Detecção e correcção de erros
Forward error correction (FEC)
•Código de Hamming – Recepção sem erros
•Palavra de código transmitida: 100011101110
•Palavra de código recebida: 100011101110
1100 (12 ) ⊕ 1000 (8) ⊕ 0111 ( 7 ) ⊕ 0110 ( 6 ) ⊕ 0100 ( 4 ) ⊕ 0011 (3) ⊕ 0010 ( 2 ) = 0000
•Código de Hamming – Recepção com erros
•Palavra de código transmitida: 100011101110
•Palavra de código recebida: 100011001110
1100 (12 ) ⊕ 1000 (8) ⊕ 0111 ( 7 ) ⊕ 0100 ( 4 ) ⊕ 0011 (3) ⊕ 0010 ( 2 ) = 0110 ( 6 )
•Ocorreu um erro de bit na posição 6. O receptor só tem de o inverter.
Responsável:
Rui Silva
Data:
1ª Ano 2º Semestre 2010 / 2011
Versão
Pág.:
2.2
13/19
Interfaces e transmissão de dados
Características
Camada de ligação de dados. Sincronismo e detecção de erros
Detecção e correcção de erros
Forward error correction (FEC)
•Código de Hamming - Características
•Corrige todos os erros simples de bit na palavra de código
•Pouco eficiente para erros em rajada.
•Nº de bits necessários para uma codificação Hamming de m bits de dados
- m + r bits redundantes de verificação
-Com r bits de verificação é possível representar valores entre 0 (não usado) e 2 r − 1
- r é o menor inteiro que verifica a condição:
2 r −1 ≥ m + r
(4.10)
- Note-se que o comprimento total da palavra de código: l = m + r
Responsável:
Rui Silva
Data:
1ª Ano 2º Semestre 2010 / 2011
Versão
Pág.:
2.2
14/19
Interfaces e transmissão de dados
Eficiência e famílias do Código
Camada de ligação de dados. Sincronismo e detecção de erros
Detecção e correcção de erros
Forward error correction (FEC)
•Código de Hamming – Outras famílias de código e eficiência
m
l
4
7
m
l
0.57
11
15
0.73
26
31
0.84
57
63
0.91
120
127
0.94
247
255
0.968
502
511
0.982
η=
•A eficiência aumenta à medida que o
tamanho do bloco aumenta
•No entanto, à medida que o tamanho
do bloco aumenta, surgem
dificuldades:
•Complexidade do codificador
aumenta
•É preciso juntar muitos bits
antes de transmitir, o que pode
criar atrasos intoleráveis
Responsável:
Rui Silva
Data:
1ª Ano 2º Semestre 2010 / 2011
Versão
Pág.:
2.2
15/19
Interfaces e transmissão de dados
Exercicios de aplicação
Camada de ligação de dados. Sincronismo e detecção de erros
Forward error correction (codificação de Hamming). Exercicios de aplicação
1 - Considere um alfabeto constituído pelas duas palavras de código:
A: 1110 1100
B: 1010 0011
a) Qual a distância de Hamming ?
b) Quantos erros de bit é este código capaz de detectar?
c) Quantos erros de bit é este código capaz de corrigir ?
d) Ao receptor chega a seguinte palavra 1111 1000. Qual a palavra que o receptor escolheria ?
2 - Considere a seguinte mensagem de 8 bits a transmitir: 1000 0001
a)
Codifique-a em Hamming
b)
Suponha que ocorre um erro no 6º bit da mensagem codificada (contando da direita para a
esquerda). Indique as operações matemáticas realizadas pelo receptor para detectar e corrigir
o erro.
c)
Calcule a eficiência do código para o caso considerado (mensagens de 8 bits).
Responsável:
Rui Silva
Data:
1ª Ano 2º Semestre 2010 / 2011
Versão
Pág.:
2.2
16/19
Interfaces e transmissão de dados
Resumo
Camada de ligação de dados. Sincronismo e detecção de erros
Resumo
Capítulo 3 – Camada de ligação de dados
•3.1.2.2 FEC (Forward Error Correction)
•Introdução
•Análise de Hamming
•Códigos de Hamming
•Exemplos de correcção de erros
•Eficiência e famílias de código de Hamming
Responsável:
Rui Silva
Data:
1ª Ano 2º Semestre 2010 / 2011
Versão
Pág.:
2.2
17/19
Interfaces e transmissão de dados
Camada de ligação de dados. Sincronismo e detecção de erros
Referências
Stallings – Data and Computer communications Cap. VI (Transmissão de dados e correcção de erros)
Ahmad –Data Communications Principles for fixed and mobile networks Cap. V (Camada ligação dados )
Leon Garcia – Communication Networks, Cap. III (Detecção e correcção de erros)
Halsall –Data Communications, Computer Networks and Open Systems 4th Edition Cap. III (Transmissão de dados)
Tanembaum –Computer Networks 4th Edition Cap. II (data link layer)
Glover & Grant –Digital Communications Cap. X (Transmissão de dados)
Purser – Introduction to error correction codes Cap. I (Introduction)
Gilbert Held –Data Communications Networking devices Cap I (Error Detection and Correction)
Responsável:
Rui Silva
Data:
1ª Ano 2º Semestre 2010 / 2011
Versão
Pág.:
2.2
18/19
Interfaces e transmissão de dados
Camada de ligação de dados. Sincronismo e detecção de erros
FIM
Responsável:
Rui Silva
Data:
1ª Ano 2º Semestre 2010 / 2011
Versão
Pág.:
2.2
19/19