Escola Náutica Infante Dom Henrique
Departamento de Radiotecnia
Interfaces e Transmissão de dados - 6222
Notas sobre detecção e correcção de erros
V preliminar
Interfaces e Transmissão de dados 6222
Notas sobre detecção e correcção de
erros em transmissão digital de dados
VERSÂO PRELIMINAR
ENIDH - Rui Silva, Maio de 2011
Pág 1 de 68
Escola Náutica Infante Dom Henrique
Departamento de Radiotecnia
Interfaces e Transmissão de dados - 6222
Notas sobre detecção e correcção de erros
V preliminar
Índice
1 – Introdução.......................................................................................................................... 3
1.1 – Modelo do canal binário digital sem memória ....................................................... 3
1.2 – Capacidade do canal binário discreto sem memória ............................................ 4
2 – Tipos de erros em comunicação de dados .................................................................... 4
3 – Caracterização dos erros em comunicações de dados................................................ 4
3.1 – Probabilidade de erro de bit ..................................................................................... 4
3.2 – Probabilidade de erro de trama................................................................................ 4
3.2.1 – Probabilidade de erro de trama em função da probabilidade de erro de bit........ 4
3.2.1 – Probabilidade genérica de erro de trama – Independentemente do numero e
posição dos de bits errados ............................................................................................. 4
4 – Codificação de canal ........................................................................................................ 4
4.1 – Introdução .................................................................................................................. 4
4.2 – Palavra de código ...................................................................................................... 4
4.3 – Códigos lineares de blocos...................................................................................... 4
Código não sistemático: Os bits redundantes após calculados são entrelaçados com
os bits da mensagem: ............................................................................................................ 4
4.3.1 – Distância de Hamming de um código linear de blocos ........................................ 4
4.3.2 – Capacidade de controlo de erros dos códigos lineares de blocos ...................... 4
4.3.3 – Eficiência de um código de blocos c(L,m) ........................................................... 4
5 – Detecção de erros............................................................................................................. 4
5.1 – Detecção de erros por paridade simples ................................................................ 4
5.1.1 – Robustez da detecção de erros por paridade simples......................................... 4
5.1.2 – Resumo do método de detecção por paridade simples....................................... 4
5.2 – Método de detecção de erros por paridade composta.......................................... 4
5.2.1 – Robustez do método de detecção de erros por paridade composta ................... 4
5.2.2 – Resumo do método de detecção de erros por paridade composta ..................... 4
5.3 – Método de detecção de erros por códigos polinomiais ........................................ 4
5.3.1 – Representação polinomiais de números binários ................................................ 4
5.3.2 – Operações base 2 com polinómios...................................................................... 4
5.3.3 – Detecção de erros por CRC ................................................................................. 4
5.3.4 – Desempenho do método de detecção de erros por CRC.................................... 4
5.3.5 – Capacidades de correcção de erros do algoritmo CRC ...................................... 4
5.3.6 – Hardware para implementação do algoritmo CRC .............................................. 4
5.3.7 – Polinómios padrão e implementações comerciais............................................... 4
5.3.8 – Resumo do mecanismo CRC............................................................................... 4
6 – Correcção de erros em transmissão de dados.............................................................. 4
6.1 – Introdução. ................................................................................................................. 4
6.1.1 – Propriedades da codificação de blocos ............................................................... 4
6.1.2 – Pesos de Hamming .............................................................................................. 4
6.2 – Códigos de repetição (3,1)........................................................................................ 4
6.3 – Código de Hamming.................................................................................................. 4
6.3.1 – Desenho de um código de Hamming (7,4,3) ....................................................... 4
6.3.2 – Síndrome de um código de blocos linear............................................................. 4
6.3.3 – Número mínimo de bits de paridade do código de Hamming.............................. 4
6.3.4 – Construção de um código de Hamming (7,4,3) sistemático ................................ 4
6.3.5 – Controlo de erros do código de Hamming (7,4,3) sistemático............................. 4
6.3.6 – Construção de um código de Hamming (7,4,3) não sistemático ......................... 4
6.3.7 – Outras famílias de códigos de Hamming ............................................................. 4
6.3.8 – Sub-conjuntos de famílias de códigos de Hamming............................................ 4
6.4 – Representação matricial de um código de blocos linear. ..................................... 4
6.4.1 – Considerações adicionais sobre o síndrome ....................................................... 4
Referências.............................................................................................................................. 4
Pág 2 de 68
Escola Náutica Infante Dom Henrique
Departamento de Radiotecnia
Interfaces e Transmissão de dados - 6222
Notas sobre detecção e correcção de erros
V preliminar
1 – Introdução
Como estudado em capítulos anteriores, qualquer canal de comunicações, está sujeito
a imparidades. Estas imparidades conduzem a erros na transmissão dos dados e
exigem o desenvolvimento de mecanismos que permitam ao receptor a detecção
automática desses erros para que posteriormente sejam corrigidos.
Um erro de bit é definido como a inversão do valor de um bit à recepção, relativo
ao seu valor original á emissão.
1.1 – Modelo do canal binário digital sem memória
O canal de comunicação digital pode ser representado através do modelo genérico de
um canal de comunicações binárias. Uma vez que os sinais binários são discretos, o
canal é também analisado em termos discretos, através de variáveis aleatórias
discretas.
A figura 1.0, representa este modelo de canal, que não tem memória, ou seja a
transmissão de um bit é independente da transmissão dos bits anteriores.
Figura 1.0 modelo do canal binário
Tendo em conta que a probabilidade de o bit “1” errar é igual à probabilidade de o bit
“0” errar, obtêm-se o modelo do canal binário simétrico representado na figura 1.1.
Figura 1.1 O canal binário simétrico
À saída do canal, os bits são invertidos com probabilidade de erro Peee e chegam
intactos com probabilidade 1- Pe.
A probabilidade de erro de bit será abordada com mais detalhe na secção 3.1.
Pág 3 de 68
Escola Náutica Infante Dom Henrique
Departamento de Radiotecnia
Interfaces e Transmissão de dados - 6222
Notas sobre detecção e correcção de erros
V preliminar
1.2 – Capacidade do canal binário discreto sem memória
A capacidade do canal discreto sem memória é dada pela sua capacidade de
transferência de informação da entrada para a saída. Esta capacidade atinge o seu
valor mínimo quando a probabilidade de erro de bit é 0.5. A figura 1.2 ilustra a
capacidade do canal binário simétrico
Figura 1.2 Capacidade do canal binário simétrico
Pela figura 1.2, verifica-se que a probabilidade de erro no canal binário simétrico
determina qual a sua capacidade C de transferência de informação
A capacidade do canal binário simétrico é máxima para cada um dos extremos do
valor de Pe, pois quando temos Pe = 0, não existem erros, mas quando temos Pe = 1,
todos os bits estão errados bastando invertê-los.
O canal binário simétrico é determinístico para os casos em que a probabilidade
de erro é “0” ou “1”.
A capacidade é “0” quando a probabilidade de erro Pe = 1/2 pois neste caso, os dados
recebidos têm igual probabilidade de serem invertidos para “1” ou para “0”
respectivamente tornando impossível determinar o seu real valor.
Pág 4 de 68
Escola Náutica Infante Dom Henrique
Departamento de Radiotecnia
Interfaces e Transmissão de dados - 6222
Notas sobre detecção e correcção de erros
V preliminar
2 – Tipos de erros em comunicação de dados
Os erros podem ser divididos em três tipos principais:
1 – Erros de bit: (Em Inglês designados bit errors) acontecem quando um ou
mais bits isolados que compõem a mensagem chegam invertidos ao receptor. A
figura 2.1 ilustra um caso onde ocorrem três erros de bit representados a vermelho.
Figura 2.1 Erros isolados de bit
2 – Erros em rajada: (Em Inglês são designados burst errors) acontecem quando
um conjunto de B bits, que começa e acaba com um bit invertido, dista do
próximo conjunto de erros, B ou mais bits.
A figura 2.2 mostra um caso onde existe uma rajada de B=3 erros seguida de outra
de B=5 erros. De acordo com a definição, entre duas rajadas deverão existir pelo
menos igual número de bits que compunham a rajada anterior, sem erros.
Note-se que os erros em rajada não são mais do que erros isolados de bit com
padrões específicos
Figura 2.2 Erros em rajada
3 – Erros de trama: (Em Inglês são designados frame errors) acontecem quando
uma trama contém um ou mais bit errados
Os erros de trama acabam por ser uma consequência dos erros de bit, pois em
comunicação de dados a informação é agrupada e delimitada em tramas de dados.
Basta que um único bit que compõe a trama esteja errado para implicar a retransmissão de toda a trama novamente. (Ver figura 2.3)
Figura 2.3 Trama errada devido a erro de bit
Pág 5 de 68
Escola Náutica Infante Dom Henrique
Departamento de Radiotecnia
Interfaces e Transmissão de dados - 6222
Notas sobre detecção e correcção de erros
V preliminar
3 – Caracterização dos erros em comunicações de dados
A frequência de erros depende de factores internos e externos ao canal de
comunicação, e não são determinísticos. Ou seja, os erros ocorrem aleatoriamente.
Para os caracterizar temos que recorrer à teoria das probabilidades.
3.1 – Probabilidade de erro de bit
A probabilidade de erros de bit Pe define a frequência com que ocorrem erros simples
de bit e não é mais do que a relação entre o número de bit errados e o número total de
bits contados ao longo de um determinado período.
A figura 3.1 ilustra uma situação onde ocorre média 1 bit errado por cada 10 para o
período ∆t da análise: Pe = 2/20 = 0.1
Figura 3.1 Probabilidade de erro de bit de 0.1
Pe =
Ne
Nt
(3.0)
Onde Ne representa o número total de erros e Nt o número total de bit contados num
intervalo de tempo ∆t.
Seja:
N t = rb ∆t
(3.1)
Em que rb representa o débito binário em bit por segundo.
Substituindo 3.1 em 3.0:
Pe =
Ne
rb ∆t
(3.2)
Note-se que ∆t tem que ser suficientemente grande para que a amostra de bits seja
representativa.
A probabilidade de erro de bit também é designada por taxa de erros de bit ou em
Inglês bit error rate (BER)
Pág 6 de 68
Escola Náutica Infante Dom Henrique
Departamento de Radiotecnia
Interfaces e Transmissão de dados - 6222
Notas sobre detecção e correcção de erros
V preliminar
3.2 – Probabilidade de erro de trama
Seguindo o mesmo raciocínio da probabilidade de erro de bit, a probabilidade de erro
de trama (ou taxa de erros de trama) é a frequência de ocorrência de tramas com
erros. É definida pela relação entre o número de tramas erradas e o número total de
tramas recebidas num determinado período de tempo.
A figura 3.2 ilustra uma situação onde a taxa de tramas erradas é PF = 1/3.
Figura 3.2 Probabilidade de erro de trama de 1/3
PF =
N Fe
N tf
(3.3)
Onde NFe representa o número total de tramas com erros e Ntf o número total de
tramas contados num intervalo de tempo ∆t.
Sendo: N ft = rF ∆t
(3.4)
Em que rF é o ritmo de transmissão de tramas em tramas por segundo.
PF =
N Fe
rF ∆t
(3.5)
3.2.1 – Probabilidade de erro de trama em função da probabilidade de erro de bit
Os erros de trama são dependentes dos erros de bit, pois a trama errada é aquela que
contêm 1 ou mais bit errados.
Sendo assim, recorrendo à análise combinatória, facilmente se deduz a probabilidade
de erro de trama em função da probabilidade de erro de bit.
Como exemplo, considere-se a trama T1 da figura 3.3, composta por 3 bit numerados
de 1 a 3.
Cada bit apresenta erros independentes uns dos outros e tem probabilidade individual
de erro Pe
Se cada bit tem probabilidade de erro Pe então a probabilidade de esse mesmo bit
estar correcto (não estar errado) é 1-Pe.
Pág 7 de 68
Escola Náutica Infante Dom Henrique
Departamento de Radiotecnia
Interfaces e Transmissão de dados - 6222
Notas sobre detecção e correcção de erros
V preliminar
Figura 3.3 Trama com 3 bit cada um com Probabilidade de erro Pe
Para que uma trama esteja errada são condições suficientes qualquer um
seguintes acontecimentos:
dos
Acontecimento 1: A trama apresenta 1 bit errado. Esse bit pode estar na posição
1, 2 ou 3 (Ver figura 3.4)
Note-se que sempre que há um bit errado com probabilidade Pe, existem em
simultâneo dois bit correctos com probabilidade 1-Pe.
Sendo assim, e de acordo com a figura 3.4 a combinação de posições possíveis dos
bits errados e correctos são: (bit 1 errado e 2,3 correctos) ou (bit 2 errado e 1,3
correctos) ou (bit 3 errado e 1,2 correctos).
A conjunção “e” é matematicamente uma multiplicação e a disjunção “ou” é
matematicamente uma soma:
. Figura 3.4 Trama T1 com as combinações possíveis de 1 bit errado
O acontecimento 1 é descrito matematicamente pela equação 3.6. É a combinação
de 3 bits agrupados 1 a 1, onde 1 bit está errado com probabilidade Pe e 2 bits estão
correctos com probabilidade 1-Pe.
P(Acontecimento 1) = 3C1 pe1 (1 − pe )
2
(3.6)
Acontecimento 2: A trama apresenta 2 bit errados. Esses bit podem estar
combinados nas posições (1 e 2) , (2 e 3), (1 e 3). (Ver figura 3.5)
Temos agora a seguinte combinação: (bit 1 e 2 errados e 3 correcto) ou (bit 2 e 3
errados e 1 correctos) ou (bit 3 errado e 1,2 correctos).
. Figura 3.5 Trama T1 com as combinações possíveis de 2 bits errados
Pág 8 de 68
Departamento de Radiotecnia
Escola Náutica Infante Dom Henrique
Interfaces e Transmissão de dados - 6222
Notas sobre detecção e correcção de erros
V preliminar
O acontecimento 2 é descrito matematicamente pela equação 3.7 e é a combinação
de 3 bit agrupados 2 a 2, onde 2 estão errados com probabilidade Pe e 1 está correcto
com probabilidade 1-Pe.
P(Acontecimento 2) = 3C2 pe 2 (1 − pe )
1
(3.7)
Acontecimento 3: A trama apresenta 3 bit errados e 0 correctos. Esses bit
podem estar combinados nas posições (1 e 2 e 3). (Ver figura 3.6)
. Figura 3.6 Trama T1 com as combinações possíveis de 3 bit errados
O acontecimento 3 é descrito matematicamente pela equação 3.8 e é a combinação
de 3 bit agrupados 3 a 3, onde 3 estão errados com probabilidade Pe e nenhum está
correcto com probabilidade 1-Pe.
P(Acontecimento 3) = 3C3 pe 3 (1 − pe )
0
(3.8)
Torna-se agora fácil o cálculo da probabilidade de erro de trama, pois uma trama está
errada caso estejamos perante qualquer um dos acontecimentos anteriores
(acontecimento 1) ou (acontecimento 2) ou (acontecimento 3).
Uma vez que o “ou” é representado por uma soma, então a probabilidade da trama T1
estar errada é:
P(Erro em T1) = acontecimento 1 + acontecimento 2 + acontecimento 3
Ou:
P(Erro em T1) = 3C1 pe1 (1 − pe ) + 3C2 pe 2 (1 − pe ) + 3C3 pe 3 (1 − pe )
2
1
0
(3.9)
A equação 3.9 pode ser generalizada pela equação 3.10, para qualquer trama com L
bits de comprimento e i erros.
L
(
PF (L, i ) = ∑ L C i P e 1 − P e
i
L −i
)
(3.10)
i =1
Em que:
L
Ci =
L!
i!(L − i )!
(3.11)
Pág 9 de 68
Escola Náutica Infante Dom Henrique
Departamento de Radiotecnia
Interfaces e Transmissão de dados - 6222
Notas sobre detecção e correcção de erros
V preliminar
3.2.1 – Probabilidade genérica de erro de trama – Independentemente do numero
e posição dos de bits errados
Caso não nos seja relevante o número e posição de errados na trama, é possível
calcular de forma simplificada, a probabilidade de erro de trama partindo do raciocínio
“inverso”:
Para a trama T1 da figura 3.3 não conter erros, é necessário que todos os bits
(1,2 e 3) que a compõem estejam correctos (com probabilidade 1-Pe)
Para a trama estar correcta é suficiente o acontecimento 4
Acontecimento 4.Todos os bits de T1 (1,2,3) estão correctos
O acontecimento 4 é descrito pela equação 3.12: A probabilidade de T1 estar correcta
é a “probabilidade do bit1 estar correcto e probabilidade do bit 2 estar correcto e
probabilidade do bit 3 estar correcto”.
(3.12)
Torna-se agora fácil deduzir a probabilidade de erro de trama, pois não é mais do que:
___
PF = 1 − PF
(3.13)
Substituindo 3.12 em 3.13 vem:
PF = 1 − (1 − Pe )
3
(3.14)
A equação 3.14 pode ser generalizada para uma trama com L bits. De um modo geral
a probabilidade de uma trama estar errada é dada pela equação 3.15:
PF (L ) = 1 − (1 − Pe )
L
(3.15)
4 – Codificação de canal
Neste capítulo iremos abordar a codificação de canal e respectivos códigos de blocos
lineares como técnica fundamental para detecção e correcção de erros em
transmissão de dados.
No capítulo 5, serão abordados códigos específicas para detecção de erros que
funcionam em modo BEC1
No capítulo 6, serão abordados códigos específicas para correcção de erros, que
podem funcionar em modo FEC2 ou BEC
1
BEC – Backward Error Correction. A correcção é feita por pedido de retransmissão ao emissor. Usado
quando a transmissão é nos dois sentidos
Pág 10 de 68
Escola Náutica Infante Dom Henrique
Departamento de Radiotecnia
Interfaces e Transmissão de dados - 6222
Notas sobre detecção e correcção de erros
V preliminar
4.1 – Introdução
Para que seja possível a detecção e correcção de erros é necessária a adição de um
ou mais bits redundantes à mensagem enviada, de forma a permitir que o receptor
verifique a sua integridade e se possível a corrija. O resultado é uma palavra de
código de comprimento superior à mensagem original.
Este processo de adição de bits redundantes é efectuado pelo emissor e é
denominado “codificação de canal”.
No receptor, o procedimento inverso é efectuado (descodificação de canal) de forma a
validar e recuperar a mensagem original
A figura 4.1 ilustra o processo de codificação à emissão e descodificação à recepção.
É possível verificar que o codificador encontra-se imediatamente antes do modulador e
da transmissão dos dados para a linha.
Figura 4.1 O Codificador no processo de comunicação de dados.
O cálculo do valor do(s) bit(s) reduntante(s) é feito a partir da mensagem na fonte, com
base num algoritmo pré-definido.
O procedimento genérico para construção da palavra de código está representado na
figura 4.2. Aqui a palavra de código é a trama enviada e recebida.
2
FEC – Forward Error Correction . A correcção é feita no receptor através de um código de blocos.
Usado quando a transmissão só é possível num sentido
Pág 11 de 68
Escola Náutica Infante Dom Henrique
Departamento de Radiotecnia
Interfaces e Transmissão de dados - 6222
Notas sobre detecção e correcção de erros
V preliminar
. Figura 4.2 Codificação e Descodificação da palavra de código .
Na emissão, o codificador calcula os bits de redundantes de verificação e adiciona-os
à mensagem para construir a palavra de código.
Na recepção, o descodificador recorre ao algoritmo do emissor para separar a
mensagem dos bits redundantes. É com base no valor dos bits redundantes que o
descodificador consegue detectar ou até corrigir erros.
4.2 – Palavra de código
A trama de dados a transmitir, é composta pela palavra de código que por sua vez
contêm os seguintes campos (ver figura 4.3 )
1 - Mensagem de informação tem comprimento total m, que inclui todos os cabeçalhos
e campos das camadas superiores do modelo OSI3
2 – Palavra de código c, de comprimento total L
3 – Bits redundantes de verificação v, com comprimento L-m
Figura 4.3 Palavra de código de comprimento L e v bits de verificação.
3
OSI – Open Systems For Interconnection
Pág 12 de 68
Departamento de Radiotecnia
Escola Náutica Infante Dom Henrique
Interfaces e Transmissão de dados - 6222
Notas sobre detecção e correcção de erros
V preliminar
A palavra de código c, é representada por c (L,m), em que L representa o
comprimento total e m o comprimento da mensagem.
Definição 4.1
O conjunto dos bits de informação mais os bits de verificação é designado por
palavra de código.
A palavra de código pode ser representada por c(L,m)
4.3 – Códigos lineares de blocos.
Um código qualquer é linear quando:
1 – Inclui a palavra de código nula.
2 – A soma de duas palavras de código resulta numa outra palavra de código
Os códigos lineares subdividem-se em:
a) Códigos de blocos
b) Códigos convolucionais
Os códigos objecto de estudo, são os códigos de blocos, em que a palavra de código
c, é um vector de bits desse código. O vector m de mensagem com m bits é dado por:
m = [m 0
m1 ... m m −1 ]
O vector da palavra de código c, tem comprimento L > m bits e contêm os bits da
mensagem e os de verificação dado por:
c = [c 0
... c L −1 ]
O código de blocos pode ser sistemático ou não consoante a posição dos bits
redundantes.
Código sistemático: Os bits de verificação v após calculados são adicionados
todos juntos ao final ou ao início da mensagem e têm comprimento v=L-m
[
c = m0 m1
m1 m2
... m x −1
c =  v0 v1 ... v( L − m ) −1
m0 m1
b0 b1 ... b( L − x ) −1
]
m2 m3 ... mm−1 
Código não sistemático: Os bits redundantes após calculados são entrelaçados
com os bits da mensagem:
c =  m0 v0 m1v1 ... mm−1 ... b( L− m ) −1 
c =  v0 v1m0 m1 ... b( L − m ) −1 ... mm −1 
Note-se que a adição de bits redundantes, cria uma palavra de código e conduz ao
afastamento entre as 2m diferentes mensagens. A figura 4.4 ilustra este afastamento
para m = 2 e L = 3: Código do tipo c(3,2)
Pág 13 de 68
Escola Náutica Infante Dom Henrique
Departamento de Radiotecnia
Interfaces e Transmissão de dados - 6222
Notas sobre detecção e correcção de erros
V preliminar
Figura 4.4 Palavra de código para c(3,2).
4.3.1 – Distância de Hamming de um código linear de blocos
A diferença entre duas palavras de código é denominada distância de Hamming dH.
O seu nome deve-se a Richard Hamming, que juntamente com Claude Shannon
desenvolveram a base da teoria da informação (codificação de fonte e de canal) nos
anos 50, nos laboratórios da BELL nos EUA
Esta distância tem um papel fundamental na determinação das capacidades
correcção e detecção de erros de qualquer código.
de
Definição 4.2
Distância de Hamming – dH : É o número mínimo de bits que diferem 2 palavras
de código entre si ou por outras palavras: é o número de bits necessários para
transformar uma palavra de código noutra
A distância de Hamming é calculada pela operação “ou exclusivo” entre cada um dos
bits das palavras em análise, sendo o seu valor o número de bits a “1” do resultado.
Quando o conjunto de palavras de código sujeitas à avaliação da distância de
Hamming, é o universo de todo o alfabeto conhecido, então interessa encontrar a
distância mínima dmin de Hamming entre todas elas que é designada por: Distância de
Hamming do código completo.
Definição 4.3
Distância de Hamming do código completo– dmin : É a menor das distâncias de
Hamming dH entre todas as palavras de código
Como exemplo considere-se o alfabeto composto pelas seguintes palavras de código:
A = 110011011, B = 111100011 e C = 101110001
A distância de Hamming é calculada fazendo ou exclusivo entre cada uma delas.:
Pág 14 de 68
Departamento de Radiotecnia
Escola Náutica Infante Dom Henrique
Interfaces e Transmissão de dados - 6222
Notas sobre detecção e correcção de erros
A 1 1001 1011
B ⊕ 1 1110 0011
0 0111 1000
A 1 1001 1011
C ⊕ 1 0111 0001
0 1110 1010
V preliminar
B 1 1110 0011
C ⊕ 1 0111 0001
0 1001 0010
A diferença AB = 4, AC = 4 e BC = 3, sendo que a mínima distância entre toda as
palavras de código ocorre entre B e C.
A distância de Hamming de código completo é dmin = 3
Este assunto será novamente abordado e aprofundado no capitulo 6.
4.3.2 – Capacidade de controlo de erros dos códigos lineares de blocos
A distância de Hamming é um parâmetro fundamental para avaliar a capacidade de
um determinado bloco na detecção e correcção de erros.
Para que um código seja capaz de detectar e erros isolados de bit, a sua distância de
Hamming de código completo dmin deverá ser:
d min [det ecção ] = e + 1 [bit]
(4.1)
Para que um código seja capaz de corrigir e erros isolados de bit, a sua distância de
Hamming de código completo dmin deverá ser:
d min [correcção ] = 2e + 1 [bit]
(4.2)
Ou corrige:
e=
d min − 1
[erros] , com e arredondado para baixo.
2
(4.3)
Este assunto será novamente abordado e aprofundado no capitulo 6.
4.3.3 – Eficiência de um código de blocos c(L,m)
Quanto menor for o número de bits adicionados à mensagem mais eficiente será o
código, pois menos bits de overhead4 este contêm. Veremos no capítulo 6, que, de
um modo geral, quanto maior for o número de bits de verificação, maior será a
robustez do código, ou seja, maior será a sua capacidade de detecção ou correcção
de erros
Definição 4.4
Eficiência ou taxa do código (“code rate”). È a relação entre o número total de
bits da mensagem e o numero de total de bits que compõem a palavra de código
e é dada pela equação 4.14.
4
OverHead – Dados binários redundante enviados com a mensagem, que não são informação útil
Pág 15 de 68
Departamento de Radiotecnia
Escola Náutica Infante Dom Henrique
Interfaces e Transmissão de dados - 6222
Notas sobre detecção e correcção de erros
η=
m
L
V preliminar
(4.4)
O desafio está em construir o código mais eficiente possível, mantendo elevada
robustez.
5 – Detecção de erros
Neste capítulo iremos abordar diferentes metodologias para detecção de erros em
transmissão digital de dados. Serão estudados em detalhe códigos de paridade e
códigos cíclicos, que são um sub-conjunto dos códigos de lineares de blocos.
5.1 – Detecção de erros por paridade simples
O método de detecção por bit de paridade simples consiste na adição de 1 único bit de
verificação P pelo emissor, ao final da mensagem transmitida.
No caso de serem utilizada uma mensagem m de comprimento m = 8 bits, a palavra
de código final tem comprimento L = 9 bits c(9,8) é representada na figura 5.1.
O bit redundante P tem o valor 0 ou 1 consoante o número de 1’s existentes na
mensagem seja par ou ímpar respectivamente. (Daqui vem o nome de bit de
paridade).
O receptor vai efectuar novo cálculo de paridade P’ da mensagem recebida e compara
o resultado com o valor do bit P recebido. Caso P’ = P significa que não se detecta
erro.
.
Figura 5.1 Posição do bit de paridade na mensagem transmitida.
Na prática o resultado da contagem do número de “1’s” obtêm-se somando modulo 2
cada um dos bits da mensagem. A soma módulo 2 é efectuada através da operação
lógica binária “ou exclusivo”.
A tabela 5.1 representa a tabela de verdade do “ou exclusivo”, cujo operador tem o
símbolo ⊕ .
Entrada 1
Entrada 2
Saída
0
0
1
1
0
1
0
1
0
1
1
0
Tabela 5.1 Tabela de verdade “ou exclusivo”
Pág 16 de 68
Escola Náutica Infante Dom Henrique
Departamento de Radiotecnia
Interfaces e Transmissão de dados - 6222
Notas sobre detecção e correcção de erros
V preliminar
Como se pode observar, em aritmética modulo 2 (ou exclusivo), as somas não têm bit
de transporte (carry), e as subtracções não têm bit de empréstimo (borrow) o que torna
as operações soma e subtracção exactamente iguais.
O Algoritmo de cálculo de paridade pode ser:
1 - par caso o resultado seja directamente o da operação “ou exclusivo” de cada um
dos bits da mensagem
2 – ímpar, caso o resultado seja a inversão do resultado da operação “ou exclusivo”
de cada um dos bits da mensagem
A figura 5.2 ilustra o circuito lógico envolvido no cálculo do bit de paridade (tanto no
emissor como no receptor) usando o algoritmo de paridade par e ímpar.
Figura 5.2 Posição do bit de paridade na mensagem transmitida.
A palavra de código de bit de paridade é representada pelo vector:
c = [( m0 )
(m1 ) (...) (mm−1 ) (m0 ⊕ m1 ⊕ ... ⊕ mm−1 )]
Mensagem m
Bit de verificação v
5.1.1 – Robustez da detecção de erros por paridade simples
Para aferir a robustez deste método de detecção de erros, vamos validá-lo com alguns
casos práticos de ocorrências de erros.
Admita-se que se quer transmitir o carácter “a” do alfabeto ASCII 5 a 8 bit, utilizando o
algoritmo de paridade par. O valor do bit de paridade obtêm-se directamente da
operação ou exclusivo ( ⊕ )de cada um dos bits de “a”
P = 0 ⊕1⊕1⊕ 0 ⊕ 0 ⊕ 0 ⊕ 0 ⊕1 = 1
5
ASCII American Standard Code for Information Interchange
Pág 17 de 68
Escola Náutica Infante Dom Henrique
Departamento de Radiotecnia
Interfaces e Transmissão de dados - 6222
Notas sobre detecção e correcção de erros
V preliminar
A mensagem enviada será constituída pela palavra de código da figura 5.3
Figura 5.3 Carácter “a” e respectivo bit de paridade par.
Teste 1: Erro num bit.
Admita-se que houve um erro no bit B0 (1º a contar da esquerda para a direita). Ao
receptor chega:
111000011
(P=1)
A operação de verificação de paridade no receptor consiste em calcular novamente a
paridade denominada agora P’ , a partir dos 8 primeiro bit da mensagem (b0-b7)que
correspondem ao carácter “a” e comparar o resultado com a paridade P que vem na
mensagem
P ' = 1⊕1⊕1⊕ 0 ⊕ 0 ⊕ 0 ⊕ 0 ⊕1 = 0
Como P’≠ P, o erro é detectado.
Teste 2: Erro em dois bit.
Admita-se que houve agora dois erros nos bit B0 e B1. Ao receptor chega:
1 0 1 0 0 0 0 1 1 (P=1), P ' = 1 ⊕ 0 ⊕ 1 ⊕ 0 ⊕ 0 ⊕ 0 ⊕ 0 ⊕ 1 = 1
P’= P, o erro não é detectado.
Teste 3: Erro em três bit.
Admita-se que houve agora três erros nos bit B0, B1 e B3. Ao receptor chega:
1 0 1 1 0 0 0 1 1 (P=1), P ' = 1 ⊕ 0 ⊕ 1 ⊕ 1 ⊕ 0 ⊕ 0 ⊕ 0 ⊕ 1 = 0
P’≠ P, o erro é detectado.
E assim sucessivamente. Facilmente se verifica que este método detecta erros de bit
em número ímpar, mas não é capaz de detectá-los em número par.
Pág 18 de 68
Departamento de Radiotecnia
Escola Náutica Infante Dom Henrique
Interfaces e Transmissão de dados - 6222
Notas sobre detecção e correcção de erros
V preliminar
Conclusão:
O método de detecção por bit de paridade simples, detecta todos os erros de bit
em número par, mas não detecta erros de bit em número ímpar. A robustez deste
mecanismo é bastante limitada.
Nota:
Admitindo que se recorre, por exemplo, a mensagens constituídas por caracteres
ASCII com 8 bits, são possível codificar 28 = 256 caracteres diferentes. A palavra de
código (ver secção 4.2) tem comprimento L=9, m=8 e v=1,
Se colocarmos todas as combinações possíveis binárias numa tabela excel, verifica-se
que a distância mínima do código completo é dmin = 2.
Sendo assim, o código (L,m) abordado neste exemplo é do tipo (9,8), com dmin = 2.
De acordo com a equação 4.1, e = d min − 1 = 1, código detecta todos os erros simples
de 1 bit. Adicionalmente ainda é capaz de detectar erros se forem em número ímpar.
De acordo com a equação 4.4, e =
d min − 1
= 0.5 = 0 , logo não tem quaisquer
2
capacidades de correcção de erros.
A probabilidade de detecção deste mecanismo é igual à probabilidade de existirem
erros i em número ímpar e é dada pela equação 5.1, que não é mais do que a
equação 3.10 fazendo i = ímpar.
PDetecção (L, i ) =
L
∑
L
Ci Pe (1 − Pe )
i
L −i
(5.1)
i = ímpar
Inversamente, a probabilidade de não detecção é dada pela equação 5.2
__________
PDetecção (L, i ) = 1 − PDetecção (L, i ) =
L
∑
L
C i Pe (1 − Pe )
i
L −i
i = par
Pág 19 de 68
(5.2)
Escola Náutica Infante Dom Henrique
Departamento de Radiotecnia
Interfaces e Transmissão de dados - 6222
Notas sobre detecção e correcção de erros
V preliminar
5.1.2 – Resumo do método de detecção por paridade simples
Resumo:
Na detecção de erros por paridade simples, a palavra de código transmitida é
formada pela adição de um único bit de verificação ao final de cada carácter
denominado “bit de paridade”. Este bit não é mais do que uma contagem dos
“1” existentes na mensagem através da operação “ou exclusivo”.
Existem dois tipos de paridade simples: Par e Ímpar:
-Paridade par: se o número de bits a “1” for par o bit de paridade é 0.
Qweqweqwe
se o número de bits a “1” for ímpar o bit de paridade é 1.
-Paridade ímpar: se o número de bits a “1” for par o bit de paridade é 1.
Qweqweqwe
se o número de bits a “1” for ímpar o bit de paridade é 0.
Este tipo de detecção é pouco robusta, pois apenas é capaz de detectar
ocorrências de erros em número ímpar de bits.
Principais Aplicações:
Este método aplica-se em ligações entre terminais e sistemas centrais em modo
interactivo (ou seja em modo de envio / recepção de caracteres de texto) que
não requerem grande fiabilidade, isto é, a ligações através da porta série de um
terminal (ou PC) a um qualquer outro sistema utilizando o protocolo RS-232 /
V.24
5.2 – Método de detecção de erros por paridade composta
O método de paridade composta tem como objectivo aumentar a robustez da detecção
de erros existente no mecanismo de paridade simples.
Este método tira partido do facto de uma trama de dados agrupar vários caracteres de
informação. Sendo assim, ficam agora disponíveis dois níveis de verificação. A
paridade simples ou horizontal por cada carácter (estudada anteriormente) e um novo
tipo denominado paridade vertical ou longitudinal que é calculada entre os vários
caracteres.
A figura 5.4, ilustra o conceito. Seja a trama construída pelos caracteres “a” e “b”.
O valor da paridade longitudinal (ou vertical) Pv é calculado através da operação “ou
exclusivo” de cada uma das correspondentes posições dos bit de cada carácter. O
resultado tem o mesmo numero de bits do que o comprimento dos caracteres e é
adicionado ao final da trama num campo específico denominado BCC6
A paridade horizontal (simples( PH é calculada pelo método estudado na secção 5.1 e
é a operação ou exclusivo de cada um dos bit de cada carácter.
6
BCC - Block CheCsum – Bloco de bits de verificação
Pág 20 de 68
Escola Náutica Infante Dom Henrique
Departamento de Radiotecnia
Interfaces e Transmissão de dados - 6222
Notas sobre detecção e correcção de erros
V preliminar
Figura 5.4 Trama com dois caracteres e paridade composta (PH e PV)
O valor dos bits do campo BCC são:
PV 0 = 0 ⊕ 0 = 0
PV 1 = 1 ⊕ 1 = 0
PV 2 = 1 ⊕ 1 = 0
PV 3 = 0 ⊕ 0 = 0
PV 4 = 0 ⊕ 0 = 0
PV 5 = 0 ⊕ 0 = 0
PV 6 = 0 ⊕ 1 = 1
PV 7 = 1 ⊕ 0 = 0
BCC= 0 0 0 0 0 0 1 0
O valor dos bit de paridade horizontal PH(A) e PH(B) são:
PH ( A) = 0 ⊕ 1 ⊕ 1 ⊕ 0 ⊕ 0 ⊕ 0 ⊕ 0 ⊕ 1 = 1
PH ( B ) = 0 ⊕ 1 ⊕ 1 ⊕ 0 ⊕ 0 ⊕ 0 ⊕ 1 ⊕ 0 = 1
Sem considerar as Flags de delimitação, a mensagem enviada pelo emissor seria a da
figura 5.5
Figura 5.5 Trama contendo a mensagem “ab” e paridade composta (PH + BCC)
Ao receber a mensagem, o receptor separar os bits de paridade horizontal e os do
campo BCC do resto da informação
De seguida efectua novamente o cálculo dos bits de paridade e BCC da trama
recebida e compara-os com os que vinham na trama.
Pág 21 de 68
Escola Náutica Infante Dom Henrique
Departamento de Radiotecnia
Interfaces e Transmissão de dados - 6222
Notas sobre detecção e correcção de erros
V preliminar
A trama é considerada sem erros caso os bit de paridade horizontal e os bit do
bloco BCC calculados sejam iguais aos que vêm na trama recebida.
Note-se que agora o comprimento da palavra de código depende do número de
caracteres que compõem a trama. Admitindo n caracteres cada um com m bits, então
a palavra tem L = (m+1).n, m=n.m e v = m+n. Será genericamente do tipo:
((m+1).n , m.n)
5.2.1 – Robustez do método de detecção de erros por paridade composta
Para aferir a robustez deste método de detecção de erros, vamos validá-lo com alguns
casos práticos de ocorrências de erros.
Consideremos a trama de informação T2 representada na figura 5.6 contendo os
caracteres A a F e delimitada por STX-ETX. Recorre-se a paridade horizontal ímpar
e vertical par.
Figura 5.6 Trama T2 sob validação
Para facilitar a construção dos bits de paridade, colocamos os caracteres da trama
alinhados de cima para baixo com os bits organizados numa matriz. (Ver figura 5.7)
Figura 5.7 Trama T2 e respectivas paridades
Pág 22 de 68
Escola Náutica Infante Dom Henrique
Departamento de Radiotecnia
Interfaces e Transmissão de dados - 6222
Notas sobre detecção e correcção de erros
V preliminar
O cálculo das paridades é feito da seguinte forma:
1 – Cálculo da paridade Horizontal Ímpar. Sendo paridade ímpar há que inverter o
resultado da operação ou exclusivo bit a bit (ver figura 4.5).
________________________________________
PH 0 = 0 ⊕ 0 ⊕ 0 ⊕ 0 ⊕ 0 ⊕ 0 ⊕ 1 ⊕ 0 = 0
________________________________________
PH 1 = 0 ⊕ 1 ⊕ 0 ⊕ 0 ⊕ 0 ⊕ 0 ⊕ 0 ⊕ 1 = 1
________________________________________
PH 2 = 0 ⊕ 1 ⊕ 0 ⊕ 0 ⊕ 0 ⊕ 0 ⊕ 1 ⊕ 0 = 1
________________________________________
PH 3 = 0 ⊕ 1 ⊕ 0 ⊕ 0 ⊕ 0 ⊕ 0 ⊕ 1 ⊕ 1 = 0
________________________________________
PH 4 = 0 ⊕ 1 ⊕ 0 ⊕ 0 ⊕ 0 ⊕ 1 ⊕ 0 ⊕ 0 = 1
________________________________________
PH 5 = 0 ⊕ 1 ⊕ 0 ⊕ 0 ⊕ 0 ⊕ 0 ⊕ 1 ⊕ 1 = 0
________________________________________
PH 6 = 0 ⊕ 1 ⊕ 0 ⊕ 0 ⊕ 0 ⊕ 1 ⊕ 1 ⊕ 0 = 1
________________________________________
PH 7 = 0 ⊕ 0 ⊕ 0 ⊕ 0 ⊕ 0 ⊕ 0 ⊕ 1 ⊕ 1 = 1
2 – Cálculo da paridade vertical par. Sendo paridade par, o resultado é a operação
ou exclusivo sem inversão.
PV 0 = 0 ⊕ 0 ⊕ 0 ⊕ 0 ⊕ 0 ⊕ 0 ⊕ 0 ⊕ 0 = 0
PV 1 = 0 ⊕ 1 ⊕ 1 ⊕ 1 ⊕ 1 ⊕ 1 ⊕ 1 ⊕ 0 = 0
PV 2 = 0 ⊕ 0 ⊕ 0 ⊕ 0 ⊕ 0 ⊕ 0 ⊕ 0 ⊕ 0 = 0
PV 3 = 0 ⊕ 0 ⊕ 0 ⊕ 0 ⊕ 0 ⊕ 0 ⊕ 0 ⊕ 0 = 0
PV 4 = 0 ⊕ 0 ⊕ 0 ⊕ 0 ⊕ 0 ⊕ 0 ⊕ 0 ⊕ 0 = 0
PV 5 = 0 ⊕ 0 ⊕ 0 ⊕ 0 ⊕ 1 ⊕ 1 ⊕ 1 ⊕ 0 = 1
PV 6 = 1 ⊕ 0 ⊕ 1 ⊕ 1 ⊕ 0 ⊕ 0 ⊕ 1 ⊕ 1 = 1
PV 7 = 0 ⊕ 1 ⊕ 0 ⊕ 1 ⊕ 0 ⊕ 1 ⊕ 0 ⊕ 1 = 0
O campo BCC da trama é: 0 0 0 0 0 1 1 0, O conjunto de paridades horizontais PH = 0
1 1 0 1 0 1 1 e a trama T2 transmitida é a da figura 5.7.
Pág 23 de 68
Escola Náutica Infante Dom Henrique
Departamento de Radiotecnia
Interfaces e Transmissão de dados - 6222
Notas sobre detecção e correcção de erros
V preliminar
Teste 1: Erro nos bits posição 0 e 3 do carácter A e erro no bit da posição 3 do
carácter B
A trama que chega ao receptor com erros está ilustrada na figura 5.8.
Figura 5.8 Trama T2 com erros
a) Cálculo das paridades horizontais de cada carácter da trama recebida.
________________________________________
PH 1 ' = 1 ⊕ 1 ⊕ 0 ⊕ 1 ⊕ 0 ⊕ 0 ⊕ 0 ⊕ 1 = 1
________________________________________
PH 2 ' = 0 ⊕ 1 ⊕ 0 ⊕ 1 ⊕ 0 ⊕ 0 ⊕ 1 ⊕ 0 = 0
Logo PH’ = 0 1 0 0 1 0 1 1
b) Cálculo das paridades verticais (BCC) de cada carácter da trama
PV 3 ' = 0 ⊕ 1 ⊕ 1 ⊕ 0 ⊕ 0 ⊕ 0 ⊕ 0 ⊕ 0 = 0
Logo BCC’ = 0 0 0 0 0 1 1 0
Verifica-se que BCC = BCC’, e P≠ P’, logo os erros são detectados pois apesar
de serem em número par na horizontal, são em número ímpar numa das
verticais.
Pág 24 de 68
Escola Náutica Infante Dom Henrique
Departamento de Radiotecnia
Interfaces e Transmissão de dados - 6222
Notas sobre detecção e correcção de erros
V preliminar
Teste 2: Erro nos bits posição 1 e 4 do carácter A e erro nos bits da posição 1 e 4
do carácter C
A trama que chega ao receptor com erros está ilustrada na figura 5.9.
Figura 5.9 Trama T2 com erros
a) Cálculo das paridades horizontais de cada carácter da trama recebida.
________________________________________
PH 1 ' = 0 ⊕ 0 ⊕ 0 ⊕ 0 ⊕ 1 ⊕ 0 ⊕ 0 ⊕ 1 = 1
________________________________________
PH 3 ' = 0 ⊕ 0 ⊕ 0 ⊕ 0 ⊕ 1 ⊕ 0 ⊕ 1 ⊕ 1 = 0
Logo PH’ = 0 1 1 0 1 0 1 1
b) Cálculo das paridades verticais (BCC) de cada carácter da trama
PV 1 ' = 0 ⊕ 0 ⊕ 1 ⊕ 0 ⊕ 1 ⊕ 1 ⊕ 1 ⊕ 0 = 0
PV 4 ' = 0 ⊕ 1 ⊕ 0 ⊕ 1 ⊕ 0 ⊕ 0 ⊕ 0 ⊕ 0 = 0
Logo BCC’ = 0 0 0 0 0 1 1 0
Verifica-se que BCC = BCC’, e PH = PH’, logo os erros não são detectados pois
são em número par e em simultâneo nas linhas e colunas.
Pág 25 de 68
Escola Náutica Infante Dom Henrique
Departamento de Radiotecnia
Interfaces e Transmissão de dados - 6222
Notas sobre detecção e correcção de erros
V preliminar
Teste 3: Erro nos bits posição 1 e 4 do carácter A e erro nos bits da posição 1 e 3
do carácter C
A trama que chega ao receptor com erros está ilustrada na figura 5.10.
Figura 5.10 Trama T2 com erros
a) Cálculo das paridades horizontais de cada carácter da trama recebida.
________________________________________
PH 1 ' = 0 ⊕ 0 ⊕ 0 ⊕ 0 ⊕ 1 ⊕ 0 ⊕ 0 ⊕ 1 = 1
________________________________________
PH 3 ' = 0 ⊕ 0 ⊕ 0 ⊕ 1 ⊕ 0 ⊕ 0 ⊕ 1 ⊕ 1 = 0
Logo PH’ = 0 1 1 0 1 0 1 1
b) Cálculo das paridades verticais (BCC) de cada carácter da trama
PV 1 ' = 0 ⊕ 0 ⊕ 1 ⊕ 0 ⊕ 1 ⊕ 1 ⊕ 1 ⊕ 0 = 0
PV 3 ' = 0 ⊕ 0 ⊕ 0 ⊕ 1 ⊕ 0 ⊕ 0 ⊕ 0 ⊕ 0 = 1
PV 4 ' = 0 ⊕ 1 ⊕ 0 ⊕ 0 ⊕ 0 ⊕ 0 ⊕ 0 ⊕ 0 = 1
Logo BCC’ = 0 0 1 1 0 1 1 0
Verifica-se que PH = PH’ e BCC ≠ BCC’, logo os erros apesar de serem em numero
par, não são simultâneos nas linhas e colunas pelo que são detectados.
Fazendo todas as combinações de erros possíveis, verifica-se que os estes só não
são detectados se ocorrerem em número par e em simultâneo nas mesmas
posições da linha e coluna.Sendo um acontecimento muito menos provável,
aumenta em muito a robustez relativamente ao método de detecção por paridade
simples.
Pág 26 de 68
Departamento de Radiotecnia
Escola Náutica Infante Dom Henrique
Interfaces e Transmissão de dados - 6222
Notas sobre detecção e correcção de erros
V preliminar
Conclusão:
O método de paridade composta detecta os seguintes tipos de erros:
Todos os erros em número ímpar de bits independentemente da sua posição nas
linhas ou colunas
Todos os erros em número par de bits desde que estes não ocorram em
simultâneo na mesma linha e coluna.
Não detecta:
1 – Todos os erros em número par que ocorram simultaneamente em
linhas e colunas com por exemplo os das posições da figura 4.9.
A probabilidade de detecção deste mecanismo é igual à probabilidade de existirem
erros i em número ímpar em simultâneo no número de linhas e colunas. Admitindo
uma trama com n bits por linha e k bits por coluna
A equação 5.3 é derivada da equação 5.1 para cobrir ambos os acontecimentos.
PDetecção =
n
∑
n
Ci Pe (1 − Pe ) .
n −i
i
i = ímpar
k
∑
k
C i Pe (1 − Pe )
i
k −i
(5.3)
i = ímpar
Inversamente, a probabilidade de não detecção é dada pela equação 5.4
__________
PDetecção = 1 − PDetecção =
n
∑
i = par
n
k
C i Pe (1 − Pe ) . ∑ k C i Pe (1 − Pe )
i
n −i
i
k −i
(5.4)
i = par
5.2.2 – Resumo do método de detecção de erros por paridade composta
Resumo:
A detecção de erros por paridade composta tira partido do facto de serem
transmitidos vários caracteres numa única trama de informação. Desta forma,
além dos bits de paridade adicionados ao final de cada carácter (paridade
horizontal), serão adicionados novos bit de paridade referentes a cada uma das
posições de bit por cada carácter designados paridade longitudinal. A paridade
longitudinal irá ser depois adicionada ao final da trama num campo designado
BCC.
A probabilidade de detecção de erro aumenta consideravelmente relativamente
ao método de paridade simples pois agora só não são detectados os erros em
número par, que ocorrem simultaneamente nas linhas (paridade horizontal) e
nas colunas (paridade longitudinal)
Utilizam-se essencialmente em protocolos orientados ao carácter:
Príncipais aplicações comerciais:
1 - Protocolo Bysinc (BSC da IBM)
Pág 27 de 68
Departamento de Radiotecnia
Escola Náutica Infante Dom Henrique
Interfaces e Transmissão de dados - 6222
Notas sobre detecção e correcção de erros
V preliminar
5.3 – Método de detecção de erros por códigos polinomiais
O desempenho da detecção de erros pode ainda ser melhorado, recorrendo a um
método denominado CRC7. Este recorre a códigos cíclicos definidos por polinómios
para detectar o erro. Antes de entrarmos no algoritmo de cálculo de CRC iremos rever
algumas operações básicas com polinómios.
5.3.1 – Representação polinomiais de números binários
Um conjunto de k bits pode ser representado como um conjunto de coeficientes de um
polinómio de k termos e ordem k-1.
Por exemplo a sequência M = 1 0 1 1 1 0 0 0 representa um polinómio de 8 termos e
ordem 7.
M ( x) = 1 × X 7 + 0 × X 6 + 1 × X 5 + 1 × X 4 + 1 × X 3 + 0 × X 2 + 0 × X 1 + 0 × X 0 ⇔
M ( x) = X 7 + X 5 + X 4 + X 3 ⇔ M = 10111000
5.3.2 – Operações base 2 com polinómios
Toda a aritmética polinomial é modulo 2, não existindo bit de transporte (carry) ou
empréstimo – (borrow) o que torna somas iguais a subtracções (ver tabela 5.1 da
secção 5.1).
1 – Soma e subtracção de polinómios em base 2
Considere-se os seguintes polinómios a(x) e b(x).
a ( x) = X 5 + X 4 + X 2 + X 0 , b( x) = X 3 + X 2 + X 0
A sua soma módulo 2 (que é igual à subtracção) é:
X5
X4
⊕
X
5
X
4
X
3
X
3
X2
X0
2
0
X
X
1 1 0 1 0 1
,
=
⊕0 0 1 1 0 1
1 1 1 0 0 0
2 – Multiplicação modulo 2 de polinómios
A multiplicação modulo 2 de polinómios é feita recorrendo às regras aritméticas da
multiplicação de exponenciais. Sendo assim há que manter as bases e somar os
expoentes. no final eliminam-se os termos iguais (não esquecer que ou exclusivo de
dois números binários iguais = 0)
7
CRC – Ciclyc Redundancy Check
Pág 28 de 68
Departamento de Radiotecnia
Escola Náutica Infante Dom Henrique
Interfaces e Transmissão de dados - 6222
Notas sobre detecção e correcção de erros
V preliminar
Considere-se os seguintes polinómios a(x) e b(x).
Se o polinómio a(x) tiver grau aj, e b(x) grau bi, o grau de a(x).b(x) será a(j+i)
a ( x) = X 5 + X 4 + X 2 + X 0 =110101
b( x) = X 3 + X 2 + X 0
(
)(
a ( x).b( x) = X 5 + X 4 + X 2 + X 0 X 3 + X 2 + X 0
)
(
a ( x).b( x ) = X 8 + X 7 + X 5 + X 7 + X 6 + X 4 + X 5 + X 4 + X 2 + X 3 + X 2 + X 0
)
a ( x).b( x ) = ( X 8 + X 6 + X 2 + X 0 ) = 101000101
Considere-se agora o seguintes polinómio c(x).
c( x) = ( X + 1) ⇔ c( x ) = X 2 + 2 X + 1 = X 2 + 1
2
3 – Divisão de polinómios em base 2
Para que a divisão de dois polinómios seja possível, eles terão que ser
divisíveis. Sejam dois polinómios quaisquer M(x) e G(x).
M(x) é divisível por G(x) (com G(x) ≠ 0) se existir um quociente da divisão Q(x)
que multiplicado por G(x) e somado do resto R(x) vai dar M(x). Ver equação 5.7
M ( x)
R( x)
= Q( x) ⊕
G ( x)
G ( x)
(5.5)
Com:
G ( x) > 0
(5.6)
M ( x) = Q ( x).G ( x) ⊕ R( x)
(5.7)
Com:
0 ≤ R ( x) < G ( x)
(5.8)
Isto significa que para que M(x) seja divisível por G(x) o grau de M(x) tem que ser
superior a G(x). Caso contrário o quociente Q(x) = 0 e a equação 4.7 não se
verificaria.
Caso o resto da divisão de M(x) por G(x) seja 0, então M(x) é múltiplo de G(x)
Nota: em polinómios base 2, “menor que” significa “com grau menor que”, logo
R(x) tem grau menor que G(x) é maior ou igual a 0.
Pág 29 de 68
Departamento de Radiotecnia
Escola Náutica Infante Dom Henrique
Interfaces e Transmissão de dados - 6222
Notas sobre detecção e correcção de erros
V preliminar
A divisão de M(x) por G(x) pode ser efectuada recorrendo a uma divisão normal
polinomial, tendo em conta que a subtracção e a soma são iguais e efectuam-se
através de “ou exclusivo” .
Como exemplo sejam M(x) = X4+X3+1 e G(x) = X2+1
X4
X3
0
⊕X4
0
X2
0
X3
X2
0
⊕
3
0
X1
0
X2
X1
X0
⊕
X2
0
X0
0
X1
0
X
0
X0
X2
0
X0
X2
X1
X0
O resto R(x) = X1 e o quociente Q(x) = X2+X1+X0
Para conferir a divisão, recorremos à equação 5.7
M ( x) = Q ( x).G ( x) + R ( x) ⇔
(
)(
)
Q ( x).G ( x) + R( x) = X 2 + X 1 + X 0 . X 2 + X 0 + X 1 = X 4 + X 2 + X 3 + X 1 + X 2 + X 0 + X 1
= X + X + X = M ( x)
4
3
0
Está assim provada a divisão.
Nota: A divisão efectuada em representação binária consiste na substituição dos
valores de X por “1”
4 – Multiplicação e divisão de um polinómio por um exponencial de base 2 (2n)
A multiplicação e divisão de um polinómio em base 2 por um exponencial 2n (com a
mesma base) consiste em adicionar ou retirar n zeros á direita do polinómio
Considere-se o polinómio a(x).
a ( x) = X 5 + X 4 + X 2 + X 0 ⇔ a ( x)2n = X 5+ n + X 4+ n + X 2+ n + X 0+ n
Exemplo:
c( x) = a ( x)2 3 = X 8 + X 7 + X 5 + X 3
Ou em representação binária: 1 1 0 1 0 1 x 23 = 1 1 0 1 0 1 0 0 0
Pág 30 de 68
Escola Náutica Infante Dom Henrique
Departamento de Radiotecnia
Interfaces e Transmissão de dados - 6222
Notas sobre detecção e correcção de erros
V preliminar
A divisão:
c( x)
= c( x).2 −3 = X 8−3 + X 7 −3 + X 5 − 3 + X 3−3 = X 5 + X 4 + X 2 + X
23
Note-se que c(x) tem que ser divisível por 23para que a divisão seja possível.
5 – Múltiplos um polinómio em base 2.
Dado o polinómio D(x), se multiplicado por outro polinómio E(x) com apenas 1
coeficiente e de grau >0, o polinómio resultante F(x) é múltiplo de D(x).
Exemplo:
D(x) = X5+X4+X0)
E(x) = X1
F(x) = (X5+X4+X0). X1 = X6+X5+X1
Ou se G(x) = D(x).X2 = X7+X6+X2 , G(x) é outro múltiplo de D(x)
À semelhança da aritmética base 10, se somarmos a um múltiplo qualquer de D(x),
digamos F(x), outro múltiplo de D(x), por exemplo G(x) o resultado é ele também um
múltiplo de D(x)
6 – Polinómios primos.
Um polinómio primo ou irredutível é aquele que não pode ser decomposto em factores.
Por exemplo x 2 + 1 pode ser decomposto em factores ( x + 1)( x + 1) , logo não é primo:
Ou: (x + 1)( x + 1) são os factores primos de x 2 + 1
Segundo este raciocínio, qualquer polinómio que termine em 0, não é primo pois
contêm sempre x como factor.
Alguns exemplos de polinómios primos são
x
x +1
x2 + x +1
x3 + x + 1
x3 + x2 +1
etc.
Os polinómios primos como são irredutíveis têm um papel especial no cálculo do CRC
para detecção de erros como veremos adiante.
Pág 31 de 68
Escola Náutica Infante Dom Henrique
Departamento de Radiotecnia
Interfaces e Transmissão de dados - 6222
Notas sobre detecção e correcção de erros
V preliminar
5.3.3 – Detecção de erros por CRC
Este método baseia-se nas propriedades dos códigos polinomiais estudados
anteriormente e aplica-se essencialmente em transmissão orientada ao bit.
Tal como descrito na secção 4.3, os bits redundantes, aqui denominados CRC, são
adicionados à mensagem num um campo específico denominado FCS8.
A figura 5.11, a palavra de código de comprimento L [bit] , com v = L-m [bit] de
verificação (campo FCS) e campo de informação com m bit.
Figura 5.11 Trama com informação e campo de controlo de erros
Para a geração do CRC, consideremos os seguintes dados:
M(x): É o polinómio mensagem, antes da adição do CRC. Tem grau m+1 ,
comprimento m.
G(x): É o polinómio gerador. Este é conhecido no emissor e no receptor e vai servir
para calcular o valor do CRC. Tem grau L-m e comprimento L-m+1.
L: É o comprimento total da trama que inclui o campo de verificação FCS
(comprimento L-m+1)e a mensagem a enviar (comprimento m)
m: É o comprimento da mensagem original sem o campo de verificação FCS
L-m: É o comprimento do campo de verificação FCS (v bits de verificação formados
pelo CRC).
A mensagem de código final produzida pelo mecanismo CRC tem o formato (L, L-m)
8
FCS – Frame Check Sequence- Campo que contêm os bits de verificação de erros denominados CRC
Pág 32 de 68
Escola Náutica Infante Dom Henrique
Departamento de Radiotecnia
Interfaces e Transmissão de dados - 6222
Notas sobre detecção e correcção de erros
V preliminar
1 – Algoritmo para geração do CRC no emissor
1º Passo: Adicionar (L-m) zeros à direita de M(x) (L-m é o grau de G(x))
M(x).2L-m
2º Passo: Dividir M(x).2L-m pelo polinómio gerador. O resto da divisão R(x) é o
CRC
M(x).2L-m
G(x)
R(x)
Q(x)
3º Passo: Acrescentar o resto da divisão R(x) ao final da trama (campo FCS)
isto é feito recorrendo à soma mod2 da mensagem com o resto. A trama a ser
transmitida é denominada Tx(x).
Tx(x) = M(x).2L-m ⊕ R(x)
Note-se que R(x) tem comprimento igual à ordem de G(x). Acrescentar L-m zeros á
direita da mensagem no 1º passo teve como objectivo permitir que a soma modulo 2
de M(x) com R(x) seja o acrescento de R(x) à direita de M(x), pois R(x) tem L-m bits
de comprimento
2 – Representação de erros no canal
No canal de comunicação, os erros são também eles representados por um
polinómio de erro ε (x) .
O polinómio de erro ε (x) do canal, vai ser somado módulo 2 à mensagem transmitida
Tx(x), pelo que o número de coeficientes a 1 de ε (x ) representam os bit em erro.
4º Passo: Adicionar o polinómio de erros à mensagem transmitida. O resultado
será a mensagem que chega efectivamente ao receptor Rx(x)
Rx(x) = Tx(x) ⊕ ε (x) = M(x).2L-m ⊕ R(x) ⊕ ε (x)
3 – Algoritmo para validação dos dados pelo receptor
5º Passo: O receptor vai dividir a mensagem recebida pelo mesmo polinómio
gerador G(x) (conhecido no emissor e no receptor) e obter o resto da divisão
R(x).
Rx(x)
G(x)
R(x)
Q(x)
Pág 33 de 68
Escola Náutica Infante Dom Henrique
Departamento de Radiotecnia
Interfaces e Transmissão de dados - 6222
Notas sobre detecção e correcção de erros
V preliminar
Caso R(x) seja diferente de zero significa que foram detectados erros na mensagem
recebida. Caso R(x) seja zero significa que não foram detectados erros na
mensagem recebida.
Demonstração 1:
A trama transmitida Tx(x) é a seguinte:
Tx ( x) = M ( x).2 L − m ⊕ R ( x)
Logo, caso não haja erros, à recepção temos Rx(x) = Tx(x) que é dividido novamente
por G(x)
Rx ( x) =
Tx ( x) M ( x).2 L − m ⊕ R( x)
=
G ( x)
G ( x)
(5.9)
De acordo com a equação 5.5, a divisão à recepção da equação 5.9 é transformada
em:
Rx ( x) = Q( x) ⊕
M ( x).2 L − m ⊕ R ( x)
R ( x) R( x )
= Q( x) ⊕
⊕
= Q ( x)
G ( x)
G ( x) G ( x)
Valores iguais dão zero no “ou exclusivo”. A divisão da mensagem sem erros pelo
polinómio gerador G(x) no receptor, dá resto 0 e é igual a Q(x).
A figura 5.12, representa o diagrama blocos do sistema de geração e verificação do
CRC.
Figura 5.12 Diagrama blocos de um sistema CRC
Pág 34 de 68
Escola Náutica Infante Dom Henrique
Departamento de Radiotecnia
Interfaces e Transmissão de dados - 6222
Notas sobre detecção e correcção de erros
V preliminar
Exemplo de aplicação:
Admita-se que se pretende transmitir a sequência binária 100100. Admitindo que o
polinómio de erros do canal ε ( x) = 00101100 e que o polinómio gerador G ( x) = 101 ,
represente a mensagem enviada com o campo FCS e verifique se o receptor detecta
os erros na trama recebida.
1 - Adicionar 2 zeros à direita da mensagem, pois G(x) tem grau 2, dividi-la por G(x) e
somar o resto da divisão R(x).
M(x) = 10010000
100 1 0 0 00 101
101111
0011
⊕ 000
0110
⊕ 101
0110
⊕ 101
0110
⊕ 101
011 0
⊕ 10 1
0 1 1 <= R(x)
⊕ 101
Mensagem enviada = 10010000
⊕
11
Tx(x) = 10010011
A divisão pode ser conferida recorrendo à equação 5.7
M ( x) = Q ( x).G ( x) ⊕ R ( x)
Q(x) 101111
G(x)
* 101
101111
000000
⊕ 101111
Q(x).G(x) = 10010011
Q(x).G(x) 10010011
R(x) ⊕
11
M(x) = 10010000
Pág 35 de 68
Escola Náutica Infante Dom Henrique
Departamento de Radiotecnia
Interfaces e Transmissão de dados - 6222
Notas sobre detecção e correcção de erros
V preliminar
2 – Contaminação da mensagem transmitida pelo polinómio de erros do canal. À
recepção vamos ter: Rx(x) = Tx(x) + ε (x)
Tx(x) => 10010011
ε (x) => ⊕ 00101100
Rx(x) =
10111111
3 – Ver se o receptor consegue detectar os 3 erros de Rx(x), dividindo-a por G(x) e
avaliando o resto R(x).
101 1 1 1 11 101
100110
0001
⊕ 000
0011
⊕ 000
0111
⊕ 101
010 1
⊕ 10 1
0001
⊕ 00 0
0 0 1<= R(x)
⊕ 101
R(x) ≠ 0 => O erro é detectado.
Mais uma vez a divisão pode ser conferida recorrendo à equação 5.7
R x ( x) = Q( x).G ( x) ⊕ R ( x)
Q(x) 100110
G(x)
* 101
100110
000000
⊕ 100110
Q(x).G(x) = 10111110
Q(x).G(x) 10111110
R(x) ⊕
01
Rx(x) = 10111111
Pág 36 de 68
Departamento de Radiotecnia
Escola Náutica Infante Dom Henrique
Interfaces e Transmissão de dados - 6222
Notas sobre detecção e correcção de erros
V preliminar
5.3.4 – Desempenho do método de detecção de erros por CRC
Para avaliar o desempenho deste método interessa re-capitular a operação de divisão
efectuada pelo receptor. De acordo com a figura 5.12, Rx(X) depois de afectado por
erros é dado por:
R x ( x) =
Tx ( x) ⊕ ε ( x )
G ( x)
(5.10)
De acordo com a mesma figura:
Tx ( x) = M ( x).2 L − m ⊕ R( x)
(5.11)
Substituindo 5.10 em 5.11
Rx ( x) =
M ( x).2 L − m ⊕ R ( x) ⊕ ε ( x) M ( x).2 L − m R ( x) ε ( x)
=
⊕
⊕
G ( x)
G ( x)
G ( x) G ( x)
(5.12)
Sabendo que de acordo com a equação 5.5, a divisão:
M ( x).2L − m
R ( x)
= Q( x ) ⊕
G ( x)
G ( x)
(5.13)
Substituindo 5.13 em 5.12:
R x ( x) = Q ( x) ⊕
ε ( x)
R( x) R( x) ε ( x)
⊕
⊕
= Q( x) ⊕
G ( x ) G ( x) G ( x)
G ( x)
(4.14)
O que não é mais do que a equação 5.13, onde o resto é o polinómio de erros.
A equação 4.14 permite concluir que na prática o que o receptor vai analisar é o resto
da divisão de
ε ( x)
G ( x)
. Caso seja 0, não detecta o(s) erro(s), caso contrário, detecta.
Conclusão 1:
Os erros não são detectados sempre que
ε ( x)
G ( x)
tem resto 0. Portanto os erros
não são detectados sempre que ε (x) é igual ou um múltiplo de G (x)
Pág 37 de 68
Departamento de Radiotecnia
Escola Náutica Infante Dom Henrique
Interfaces e Transmissão de dados - 6222
Notas sobre detecção e correcção de erros
V preliminar
Teste 1 – Ocorrência de erros em rajada.
Exemplo: Ocorrência de erros em rajada (burst) r = 4 bit de comprimento
representado pelo polinómio de erros ε (x ) . A rajada começa no 1º bit e acaba no 4º
bit contando da esquerda para a direita
M ( x) = 1100101
G ( x) = 1011
ε ( x) = 1011000000 => Note-se que ε ( x) = G ( x).x 6 logo é múltiplo de G(x), o que
ε ( x)
significa que o resto da divisão de
G ( x)
é 0 logo o erro não é detectado.
Dito de outra forma, qualquer ε (x) que contenha G(x) em qualquer posição
sendo as outras posições = 0, cai dentro de uma rajada de erros não detectado.
Este efeito pode ser melhor observado através da tabela 5.2:
Mensagem enviada Tx(X)
Padrão de erros ε (x)
Mensagem recebida Rx(X)
1 1
1 0
0
1
0
1
1
0
0
0
1
0
0
0
1
0
0
0
0 1
1
1
1
0
1
0
1
0
Tabela 5.2 Padrão de erros não detectado pelo método CRC
Deslocando o padrão de erros para a direita (ou para a esquerda) encontramos 6
combinações possíveis onde, com este G(X), estes erros não seriam detectados
pelo receptor
Sugere-se que o leitor faça a divisão de Rx(X) por G(x) para qualquer posição
possível do padrão de erros ε (x) da tabela 5.2 e confirme que o resto é sempre
0.
Considerações adicionais sobre a detecção de erros em rajada:
O polinómio de erros ε (x) pode ser decomposto em factores:
ε ( x) = r ( x).x i = ( x r −1 + ... + 1) xi
e,
ε ( x)
G ( x)
=
(5.15)
r −1
i
r ( x) xi ( x + ... + x + 1) x
=
G( x)
( x n− x + ...x + 1)
(5.16)
Em que r(x)=(xr-1+..+1) é o polinómio correspondente à rajada de erros de
comprimento r e i representa a distância entre a rajada e o bit mais à direita da trama
recebida Rx(X)
Pág 38 de 68
Escola Náutica Infante Dom Henrique
Departamento de Radiotecnia
Interfaces e Transmissão de dados - 6222
Notas sobre detecção e correcção de erros
V preliminar
Pela equação 5.16,
para que o resto de
 xi 
 x r −1 + ... + x + 1 
= 0 ⇒ resto 
=
0
∨
resto


=0
G ( x)
G ( x)
 G ( x) 


ε ( x)
Ora como G(x), tem um termo em (x + 1), , nunca poderá ter xi como múltiplo, ou seja
xi dividido por G(x) =xn-x …+ x+1, nunca dará resto 0 quaisquer que sejam os outros
termos de G(x).
Resta então saber quando é que o resto da divisão de r(x)=xr-1+...+x+1 por G(x) é ou
não zero.
Caso 1: O grau de r(x) é inferior ao de G(x), (r-1 < L-m ou r < L-m+1 ou r ≤ L-m)
A divisão não é possível pelo os erros são detectados sempre que o grau
de r(x) for menor que o grau de G(x).
Caso 2: O grau de r(x) é igual ao de G(x), (r-1 = L-m => r = L-m+1)
A divisão de r(x) por G(x) dá resto 0, pelo que os erros não são detectados
sempre que ε (x) seja múltiplo de G(x). Foi o que sucedeu no exemplo da
tabela 4.1.
A probabilidade do caso 2 ocorrer, é reduzida e calcula-se da seguinte forma:
A rajada tem comprimento r. Por definição terá que começar em 1 e acabar em 1,
tendo os bit intermédios qualquer valor (ver figura 5.13).
Figura 5.13 Erros em rajada de comprimento r
O primeiro e último bit são sempre 1, tanto na rajada r(x), como G(x) que começa e
acaba sempre em 1. Então o padrão de bits que varia e que poderá ou não coincidir
com G(x) terá comprimento r-2=L-m-1:
Existem portanto 2r-2 combinações de bit possíveis que cabem dentro de r-2=L-m-1.
(Por exemplo caso r-2 seja 3, existem 8 combinações possíveis de bit desde 000 a
111).
Podemos então dizer que existem 2r-2 (ou 2L-m-1) diferentes polinómios G(x) que
poderão coincidir com r(x).
Nº de casos possíveis: 2r-2= 2L-m-1
Nº de casos favoráveis: 1, Pois existe apenas um polinómio G(x) que coincide com
r(x) (Este foi o exemplo da tabela 4.1)
Pág 39 de 68
Escola Náutica Infante Dom Henrique
Departamento de Radiotecnia
Interfaces e Transmissão de dados - 6222
Notas sobre detecção e correcção de erros
V preliminar
A probabilidade de o padrão da rajada ser igual a G(x), admitindo que a probabilidade
de ocorrência do 0 é igual à do 1 é dada pela equação 5.17:
 1 
= 2− ( L − m −1)
r −2 
2


P(r(x) = G(x)) = 
(5.17)
E a probabilidade de não detecção de erros cuja rajada tem comprimento igual ao do
polinómio gerador é dada pela equação 5.18
P(não detecção quando r = G) = 1 − 2− ( L − m −1)
(5.18)
Caso 3: O grau de r(x) é maior que o de G(x), (r-1 > L-m )
Como se observa pela equação 5.16, a divisão de r(x) por G(x) dá resto 0, e
não detecta os erros se e só se r(x) for múltiplo de G(x) (ou seja se r(x) tiver
G(x) como factor).
Cálculo do nº de casos em que r(x) é múltiplo de G(x). (expressão 4.19).
r(x) = Q(x).G(x)
r ( x) = x r −1 + ... + 1 = ( x r −1−( L − m ) + .. + 1)( x L − m + ... + x + 1)
Q(x)
(5.19)
G(x)
A expressão 5.19 mostra que sendo Q(x) um factor de G(x), e tendo G(x) grau L-m,
então Q(x) tem que ter grau r-1-(L-m)
É o mesmo que dizer que Q(x) tem comprimento r-1-(L-m)-1 = r-2-(L-m)
Existem agora 2r-2-L-m polinómios que podem ser Q(x), o que causaria que os erros
não fossem detectados.
Nº de casos favoráveis: 2r-2-L-m -1
Nº de casos possíveis: 2r-2
A probabilidade do caso 3 ocorrer é então dado pela equação 5.20:
 2r − 2 −( L − m ) 
−( L−m)
=2
r −2
 2

P(r(x) > G(x)) = 
(5.20)
Consequentemente, a probabilidade de não detecção de erros cuja rajada tem
comprimento superior ao do polinómio gerador é dada pela equação 5.21
P(não detecção quando r > G) = 1 − 2− ( L − m )
Pág 40 de 68
(5.21)
Departamento de Radiotecnia
Escola Náutica Infante Dom Henrique
Interfaces e Transmissão de dados - 6222
Notas sobre detecção e correcção de erros
V preliminar
Conclusão 2:
Desde que G(x) tenha um termo em (x+1), todos os erros em rajada de
comprimento menor que o nº de bits do polinómio gerador são detectados.
Quase todos os erros em rajada cujo comprimento r é maior ou igual ao nº de
bits do polinómio gerador são detectados.
A fracção de erros em rajada que não é possível detectar é:
1: 2-(L-m-1) se r = L-m+1, onde L-m+1 é o comprimento do polinómio gerador.
2: 2-(L-m) se r > L-m+1, onde L-m+1 é o comprimento do polinómio gerador.
Teste 2 – Ocorrência de erros em um bit isolado.
Caso haja erros simples de bit, então ε ( x) = x i , em que i representa o bit em erro.
Ora seguindo o raciocínio anterior, para que
ε ( x)
G ( x)
tenha resto 0, ε (x ) tem
obrigatoriamente que ser divisível por G(x).
Para garantir que ε (x) nunca é divisível por G(x) basta fazer G(x) > ε (x) (G(x) tenha
mais termos que ε (x) ). Ver secção 5.3.2 para mais detalhes dobre divisão de
polinómios. O polinómio mais simples com dois termos é x+1.
Conclusão 3:
Todos os erros de bit isolados são detectados deste que G(x) contenha 2 ou
mais termos.
Pág 41 de 68
Departamento de Radiotecnia
Escola Náutica Infante Dom Henrique
Interfaces e Transmissão de dados - 6222
Notas sobre detecção e correcção de erros
V preliminar
Teste 3 – Ocorrência de erros de bit em número ímpar
Pode ser provado que em aritmética modulo 2, nenhum polinómio com número ímpar
de termos se dividido por x+1 terá resto 0.
É o mesmo que dizer que x+1 nunca é um múltiplo de um polinómio com número
ímpar de termos, pois o resultado é sempre outro polinómio com número par de
termos.
Demonstração:
Seja ε (x ) qualquer polinómio com número ímpar de termos: ε ( x) = x 2 + x + 1
Multiplicar ε ( x)( x + 1) = x 3 + x 2 + x + x 2 + x + 1 = x 3 + 1 resulta noutro polinómio com
número par de termos. Logo (x+1) não é múltiplo de um polinómio com número impar
de termos.
Seja ε ( x) = x 3 + x + 1 ⇔ ε ( x)( x + 1) = x 4 + x 2 + x + x 3 + x + 1 , resulta noutro com
número par de termos.
Seja ε ( x) = x 5 + x 4 + x 3 + x + 1 ⇔ ε ( x)( x + 1) = x 6 + x 3 + x 2 + 1 , resulta noutro com
número par de termos.
Seja ε ( x) = x 5 + x 3 + 1 ⇔ ε ( x)( x + 1) = x 6 + x 5 + x + 1 , resulta noutro com número par
de termos.
E assim sucessivamente.
Generalizando:
(
) (
Tente-se por hipótese dividir (x + 1) x k 1 + ... + x kn = x k 1+1 + ... + x kn +1 + x k 1 + ... + x kn
)
Caso todas as potências anteriores sejam diferentes, o polinómio resultante terá
sempre número par de termos.
Conclusão 4:
Se existirem erros em número ímpar, ε (x) tem número ímpar de termos e a sua
divisão por (x+1) não dá resto 0. Logo também não terá resto 0 a sua divisão por
um múltiplo qualquer de (x+1).
Se G(x) não for primo e múltiplo de x+1 então todos os erros em número ímpar
são detectados.
Pág 42 de 68
Escola Náutica Infante Dom Henrique
Departamento de Radiotecnia
Interfaces e Transmissão de dados - 6222
Notas sobre detecção e correcção de erros
V preliminar
Teste 4 – Ocorrência de erros de bit em número par
Erros em número par são representados genericamente pelo polinómio de erro
ε ( x) = x i + x j com i > j.
(
)
Factorizando ε ( x) = x i x i − j + 1 .
É assim suficiente afirmar que os erros serão detectados caso o resto da divisão de
x k + 1 por G(x) não dê resto 0, para qualquer valor de k até ao comprimento total da
(
)
trama (isto é até i-j)
Existem polinómios conhecidos como por exemplo G ( x ) = x 15 + x 14 + 1 que não
(
)
dividem x k + 1 .
A demonstração destes polinómios pode ser aprofundada em [PETER01], onde se
conclui que para detectar erros de bit isolados em número par G(x) tem que ter pelo
menos 3 termos.
Conclusão 5:
Existem polinómios que não dividem (xk+1), para qualquer k até ao valor do
comprimento da trama. Este tipo de polinómios com pelo menos 3 termos
protegem todos os erros de bit em número ímpar
5.3.5 – Capacidades de correcção de erros do algoritmo CRC
O mecanismo CRC também apresenta capacidades de correcção de erros. Este
assunto não será objecto exaustivo de estudo, mas aqui fica uma breve introdução:
1 – Cada padrão de erros ε (x ) para ser corrigível tem que gerar um resto único após
a divisão da mensagem recebida (com erros) por G(x).
Este resto pode ser denominado o síndrome da mensagem. (Ver capítulo 6, para
mais detalhes sobre o tema).
Por outras palavras, cada padrão de erros para se corrigível tem que gerar um
síndroma que seja único.
Pág 43 de 68
Escola Náutica Infante Dom Henrique
Departamento de Radiotecnia
Interfaces e Transmissão de dados - 6222
Notas sobre detecção e correcção de erros
V preliminar
Sendo assim, o procedimento para correcção de erros é o seguinte:
1 – Dividir de Rx(x) = Tx(x) ⊕ ε (x ) por G(x) e obter o resto R(x).
2 – Obter ε (x ) , por exemplo através de uma tabela de correspondências de
cada padrão de ε (x ) com cada um dos restos R(x) (Denominada tabela de
síndromes).
3 –Subtrair ε (x) de Tx(x), para obter a mensagem original transmitida sem os
erros.
Note-se que processo de correcção de erros é muito mais complexo que o de
detecção, pois o descodificador necessita de guardar e processar enormes tabelas de
síndrome durante o passo 2.
A correcção de erros simples de bit ou em rajada é, no entanto relativamente simples
através de um registo de deslocamento, mas a correcção de erros de bit aleatórios é
bastante complexa.
Adicionalmente, este processo implica que o receptor guarde temporariamente toda a
mensagem recebida Rx(X) durante o processo de cálculo e comparação do passo 2,
gerando atrasos que poderão em alguns casos, ser inaceitáveis.
5.3.6 – Hardware para implementação do algoritmo CRC
O Hardware necessário para implementar o CRC consiste em registos de
deslocamento e somadores módulo 2 (portas lógias ou exclusivo)
São necessários tantos registos de deslocamento quanto o grau do polinómio gerador
G(x). O dividendo é deslocado da esquerda para a direita começando pela ordem mais
elevada.
A figura 5.14 ilustra um divisor por um polinómio G(x) = 1 + X2 + X3 + X4 + X5
Figura 5.14 Estrutura de Hardware divisor por 1 + X2 + X3 + X4 + X5
Pág 44 de 68
Escola Náutica Infante Dom Henrique
Departamento de Radiotecnia
Interfaces e Transmissão de dados - 6222
Notas sobre detecção e correcção de erros
V preliminar
A figura 5.15 ilustra um divisor polinomial genérico de grau n
1 + ... + c n −3 X n −3 + c n − 2 X n − 2 + c n −1 X n −1 + c n X n
O divisor é composto por n registos de deslocamento, somadores e multiplicadores
dos coeficientes de cada um dos termos.
Figura 5.15 Estrutura de Hardware divisor polinomial de grau n
5.3.7 – Polinómios padrão e implementações comerciais
De forma a garantir a robustez do método CRC, existem alguns polinómios
especialmente escolhidos e normalizados por diversas instituições de
telecomunicações internacionais. Relembre-se que o polinómio tem que ser conhecido
em todos os intervenientes na comunicação de dados.
CRC-8
X8+X2+X+1, cujos factores primos são (X+1)(X7+X6+X5+X4+X3+X2+1)
Utilização comercial: Em transmissão de dados via ondas electromagnéticas.
Protocolo 802.16 (Wi-MAX) em conjunto com outros métodos de correcção de erros.
CRC-CCITT
X16+X12+ X5+1 cujos factores primos são (X+1)(X15+X14+X13+X12+X4+X3+ X2+ X+1)
Utilização: Estes são protocolos utilizados em redes de abrangência alargada.
Protocolo HDLC, SDLC e PPP 9 por defeito.
9
HDLC – High Level Data Link Control
SDLC – Synchrounous data link control
PPP – Point to Point protocol
Pág 45 de 68
Escola Náutica Infante Dom Henrique
Departamento de Radiotecnia
Interfaces e Transmissão de dados - 6222
Notas sobre detecção e correcção de erros
V preliminar
IBM-CRC-16 (ANSI10)
X16+X15+ X2+1 cujos factores primos são (X+1)(X15+X+ 1)
Utilização: Estes são protocolos utilizados em redes de abrangência alargada WAN
Protocolo HDLC e SDLC
802.3
x32+x26+x23+x22 +x16+x12+x11+x10 +x8+x7+x5+x4+x2+x+1 sendo um polinómio primo não
é factorizável.
Utilização: Estes são protocolos utilizados em redes de abrangência local (LAN) e
opcionalmente em protocolos de redes de abrangência alargada WAN
Protocolo Ethernet e também PPP opcionalmente.
5.3.8 – Resumo do mecanismo CRC
Resumo detecção de erros por CRC
O CRC, permite implementar um mecanismo poderoso de detecção e correcção de
erros baseado em códigos cíclicos (polinomiais). O mecanismo funciona adicionando o
resto da divisão da mensagem original por um polinómio gerador G(x). São assim
adicionados n+1 bit redundantes à trama, num campo denominado CRC ou FCS (n é
o grau do polinómio gerador).
O mecanismo CRC é bastante robusto e permite detectar os seguintes tipos de erros:
1 – Todos os erros simples de bit.
2 – Todos os erros de dois bit deste que G(x) tenha pelo menos 3 termos.
3 – Todos os erros de bit em número ímpar desde que G(x) termine em x+1
4 – Todos os erros em rajada desde que o comprimento da rajada seja menor que o
número de bits de G(x).
5 – Quase todos os erros em rajada com comprimento maior ou igual que G(x).
Não detecta:
1 – Erros em rajada cujo comprimento seja igual G(x) e que o padrão da rajada seja o
de G(x).
Adicionalmente o CRC permite corrigir erros simples de bit ou em rajada através de
estruturas de hardware relativamente simples
10
ANSI – American National Standards Institute
Pág 46 de 68
Escola Náutica Infante Dom Henrique
Departamento de Radiotecnia
Interfaces e Transmissão de dados - 6222
Notas sobre detecção e correcção de erros
V preliminar
6 – Correcção de erros em transmissão de dados
Neste capítulo serão abordados códigos que permitem detectar e corrigir erros. Para
que um determinado código tenha capacidades de correcção de erros, tem em
primeiro lugar que ser capaz de detectar esse erro. Serão abordados códigos de
blocos do tipo repetição de de Hamming.
Os códigos correctores de erros, funcionam normalmente em modo FEC, não
excluindo no entanto a possibilidade de funcionarem no modo BEC, caso não
consigam corrigir os erros.
6.1 – Introdução.
Tal como os humanos, os computadores recorrem a um alfabeto de palavras de
código, para comunicarem entre si. Caso se percam algumas letras ou mesmo
palavras desse alfabeto durante a comunicação, a mensagem pode continuar a ser
entendida pelos interlocutores, pois é possível descodificar uma palavra sem alguns
dos caracteres desde que esta não coincida com outra palavra.
No caso dos humanos, mesmo que os erros transformem uma palavra noutra, pode
ser possível entender a mensagem pelo sentido da frase.
Por exemplo se o emissor enviar: “Olá! Está tudo bem contigo?”
E se devido ao ruído, ao receptor chegar: “Olá! Está tede bom contego?”
Apesar da troca e perda de caracteres, o ser humano, receptor, consegue, associar
cada uma das palavras à correspondente palavra mais próxima e válida do conjunto
de palavras que conhece.
Sendo assim, caso se construa um alfabeto binário cujas palavras de código sejam
suficientemente diferentes entre elas (distantes) pode ser possível que o receptor
seja capaz de associá-la univocamente à palavra do alfabeto binário mais próxima
que conhece.
Esta associação não é mais do que a capacidade de correcção do erro.
Para permitir a detecção e correcção de erros, são adicionados determinados número
de bits de paridade (verificação) de modo a aumentar a distância entre palavras de
código (Ver secção 4.3, figura 4.4) e garantir a distância adequada à outra palavra
mais próxima, ou seja para garantir que duas palavras não se confundam entre si após
ocorrência de determinado número de erros.
Pág 47 de 68
Escola Náutica Infante Dom Henrique
Departamento de Radiotecnia
Interfaces e Transmissão de dados - 6222
Notas sobre detecção e correcção de erros
V preliminar
6.1.1 – Propriedades da codificação de blocos
A diferença entre duas palavras de código foi introduzida na secção 4.3.1 é chamada
distância de Hamming dH.que é calculada pela operação “ou exclusivo” entre cada
um dos bits das duas palavras em análise sendo o seu valor o número de bits a “1” do
resultado.
Quando temos mais do que duas palavras de código sujeitas a avaliação, interessa
encontrar a distância mínima dmin de Hamming entre todas elas e é designada:
Distância de Hamming do código completo.
Quanto maior for a distância de Hamming, mais distantes estão as palavras de código
entre si, o que significa que mais facilmente poderão ser corrigidas, pois são
necessários mais erros de bit para as transformar em outras palavras pertencentes ao
mesmo alfabeto.
Para palavras de comprimento fixo L, a distância de Hamming é uma métrica no
espaço vectorial das palavras desse comprimento.
A título de exemplo consideremos as palavras de código com comprimento L=3. Estas
podem ser representadas graficamente através de um cubo onde as distâncias entre
os vértices desse cubo representam as distâncias entra cada uma das palavras. Esta
representação está na figura 6.1 a)
Figura 6.1 Cubo de distâncias entre palavras de código de 3 bit
A figura 6.1 b) representa a distância entre cada uma destas palavras de código.
Estas são medidas pelo número de vértices no caminho entre a origem e o destino.
Por exemplo a distância entre 000 e 101 é 2 e o caminho possível está a vermelho
enquanto o que a distância entre 000 e 111 é 3 estando um dos caminhos possíveis
representados a azul.
Pág 48 de 68
Departamento de Radiotecnia
Escola Náutica Infante Dom Henrique
Interfaces e Transmissão de dados - 6222
Notas sobre detecção e correcção de erros
V preliminar
Como introduzido na secção 4.3.2, a distância de Hamming necessário para que o
código consiga detectar e erros isolados de bit é dada pela equação 4.1:
d min [det ecção ] = e + 1 [bit]
Justificação: A ocorrência de e erros simples não conseguem transformar uma
palavra de código válida, noutra palavra válida, pois seriam necessários e = dmin bits
para que tal ocorresse.
Note-se que, no entanto, poderão existir duas palavras de código à mesma distância,
não sendo possível por isto determinar univocamente qual a correcta.
Na secção 4.3.2, foi também abordado que a distância de Hamming necessário para
que o código consiga corrigir e erros isolados de bit é dada pelas equações 4.2 e
4.3:
d min [correcção ] = 2e + 1 [bit], Ou corrige: e =
d min − 1
[erros] , com e arredondado para
2
baixo.
Justificação: As palavras de código válidas estão tão longe umas das outras, que
mesmo com e erros simples de bit a palavra de código original, está mais próxima de
qualquer outra palavra de código permitindo determiná-la de forma unívoca.
Note-se que a capacidade de detecção não é infinita, pois quanto maior e, maior d, o
que implica um maior número de bits redundantes a adicionar à mensagem,
diminuindo a eficiência e aumentando o processamento a efectuar no receptor.
Demonstração:
A figura 6.2 ajuda a ilustrar as capacidades de detecção e correcção de erros num
código.
Figura 6.2 capacidade de detecção e correcção de erros dmin = 3
Considere um alfabeto constituído exclusivamente pelas palavras de código C1 = 0110
e C2 = 1011 da figura 6.2.
A sua distância dH = dmin = 3. A ocorrência de 1 erro vai transformar C1 em 0111. O
receptor vai então escolher a palavra mais próxima que é C1.
No entanto, caso haja um segundo erro de bit, e a palavra recebida seja 1111, esta
agora dista 1 bit de C2 e 2 bit de C1. O receptor iria escolher erradamente C2
existindo erro de estimação.
Pág 49 de 68
Escola Náutica Infante Dom Henrique
Departamento de Radiotecnia
Interfaces e Transmissão de dados - 6222
Notas sobre detecção e correcção de erros
V preliminar
Se entretanto surgisse um terceiro erro de bit, que transformasse 1111 em 1011, então
o receptor iria aceitar C2 como sendo a palavra correcta, o que seria uma palavra em
erro não detectada, pois o que aconteceu foi que os erros foram em número suficiente
para transformar uma palavra de código válida noutra palavra de código válida.
Conclui-se que este código teve capacidade para detectar até 2 erros de bit (círculos a
branco), e capacidade para corrigir até 1 erro simples de bit.
Considere-se agora o alfabeto da figura 6.3, constituído pelas palavras de código:
B1 = 01111 e B2=10100.
Agora dmin = 4.
Figura 6.3 capacidade de detecção e correcção de erros dmin = 3
Seguindo o mesmo raciocínio, dois erros isolados de bit transformam C1 em 10111.
Ora 10111 dista 2 bit de C1 e 2 bit de C2. Sempre que a palavra recebida está
equidistante de duas palavras de código válidas, a correcção de erros não é possível.
Sendo assim, este alfabeto com dmin = 4 é capaz de detectar até 3 erros de bit
(círculos a branco), mas continua a não ser capaz de corrigir erros em mais do que 1
bit.
Observa-se também pelas figuras 6.2 e 6.3 que sempre que dmin é par, existe uma
palavra com erros equidistante de duas palavras de código válidas. Esta é a
justificação do arredondamento para baixo da equação 4.3
Estão então demonstradas as equações 4.1, 4.2 e 4.3
6.1.2 – Pesos de Hamming
O peso de Hamming (w) de uma palavra de código é o número de bits não nulos
dessa palavra.
Sejam as palavras de código cy e cz, duas palavras distintas de um código de blocos
linear, então a sua distância de Hamming é igual ao peso do seu vector soma
(módulo 2)
d H ( c y , cz ) = w ( c y ⊕ c z )
(6.1)
Pág 50 de 68
Departamento de Radiotecnia
Escola Náutica Infante Dom Henrique
Interfaces e Transmissão de dados - 6222
Notas sobre detecção e correcção de erros
V preliminar
Por exemplo, dados cy = 00010 e cz = 01110,
dH = 2.
w (00010 ⊕ 01110) = w (01100) = 2
Consequentemente, a distancia de Hamming do código completo dmin desse código é
dada por:
d min = min y ≠ z  dH ( c y , cz ) 
(6.2)
Sendo o código linear, a soma modulo 2 de duas palavras resulta noutra palavra de
código diferente do vector nulo. Sendo assim, a distância mínima do código completo
é dada por:
d min = min w(c k )
(6.3)
Sendo ck qualquer palavra de código diferente do vector nulo.
Definição 6.1
O peso de Hamming w de uma palavra de código é o número de bits não nulos
dessa palavra. A distância mínima do código completo é igual ao valor mínimo
de w retirando o vector nulo
6.2 – Códigos de repetição (3,1).
Os códigos de repetição foram desenvolvidos de forma a provocarem um
espaçamento das palavras de código tal que a distância de Hamming de código
completo seja dmin = 3. (Foi com base nestes códigos que Hamming desenvolveu os
códigos de Hamming estudados adiante na secção 4.3)
De acordo com as equações 4.1 e 4.3, os códigos de repetição permitem detectar 2
bits errados e corrigir 1 único bit em erro.
A técnica de construção de código é bastante simples e consiste em repetir cada 0 ou
o 1 duas vezes transformando uma mensagem m de 1 bit de comprimento numa
palavra de código com 3 bits de comprimento.
A tabela 6.1 ilustra o mapeamento entre a mensagem m de 1 bit de comprimento e
apalavra de código c.
Mensagem Palavra de código
0
1
000
111
Tabela 6.1 Código de repetição (3,1)
Pág 51 de 68
Escola Náutica Infante Dom Henrique
Departamento de Radiotecnia
Interfaces e Transmissão de dados - 6222
Notas sobre detecção e correcção de erros
V preliminar
A Figura 6.4 ilustra o espaçamento provocado pela repetição
Figura 6.4 Espaçamento das palavras do código de repetição (3,1)
No receptor, A descodificação é feita por maioria. O algoritmo é o seguinte:
1 - Caso a maioria dos bits de cada palavra de código seja 1, descodifica 1
2 - Caso a maioria dos bits de cada palavra de código seja 0, descodifica 0
Ou:
Número de bits a 1 >
L
, descodifica “1”, Caso contrário descodifica “0”
2
Este código pode funcionar nos modos FEC e ARQ.
A probabilidade de não ser capaz de correcção de erros é igual à probabilidade de
existirem i erros em número superior a
__________ _____
L
P (det ecção) = ∑ Pe (1 − Pe )
i
L
, com i ∈ N .
2
L −i
(6.4)
L
i>
2
6.3 – Código de Hamming.
Este tipo de códigos constitui uma família de códigos lineares de blocos e foram
desenvolvidos por Richard Hamming nos anos 50 nos laboratórios BELL nos EUA.
São códigos capazes de corrigir erros unitários de bit e detectar de 1 a 2 erros
isolados de bit.
Num canal binário simétrico, a probabilidade individual de erro de bit é Pe. Ora de
acordo com a equação 3.10, a probabilidade de existência de erros numa palavra de
comprimento L, é dada por:
Probabilidade de erros num único bit: P ( L,1) = C1L p1e (1 − pe )
Pág 52 de 68
L −1
Escola Náutica Infante Dom Henrique
Departamento de Radiotecnia
Interfaces e Transmissão de dados - 6222
Notas sobre detecção e correcção de erros
Probabilidade de erros em 2 bits: P ( L, 2 ) = C2L p e2 (1 − pe )
Probabilidade de erros em 3 bits: P ( L,3) = C3L p 3e (1 − pe )
V preliminar
L−2
L −3
E assim sucessivamente. Demonstra-se é muito mais provável a ocorrência de erros
em 1 bit do que a ocorrência de erros em 2 ou mais bits.
Desta forma, justifica-se plenamente o critério seguido por Hamming [HAMM01]
Sendo assim, todos os códigos de Hamming têm dmin=3.
Os códigos de Hamming são ainda definidos por um parâmetro inteiro v ≥ 2 (v é o
número de bits de verificação) tal que:
( L, m ) = ( 2v − 1, 2v − 1 − v )
(6.5)
Definição 6.2
Códigos de Hamming (L,m) são códigos correctores de erros unitários definidos
pelo parâmetro inteiro v (número de bits de verificação) tal que:
asaasddmin = 3
asaasd ( L, m ) = 2v − 1, 2v − 1 − v
(
)
Os códigos também podem ser representados por 3 parâmetros: c(L,m,dmin), onde
dmin representa a distância de Hamming do código completo. Esta será a convenção
adoptada daqui em diante.
Os códigos de Hamming podem ainda ser sistemáticos ou não sistemáticos
6.3.1 – Desenho de um código de Hamming (7,4,3)
A lógica por detrás do desenho de um código de Hamming (7,4,3) sistemático não é
complexa. Recorde-se que num código sistemático os bits redundantes são
adicionados ao final da palavra de código (ver secção 4.2).
O código de Hamming (7,4,3) é composto por uma mensagem m com 4 bit de
comprimento (permite codificar todos os caracteres hexadecimais de 0 a F) e 3 bits de
verificação (comprimento total L = 7 )
A eficiência deste código, de acordo com a equação 4.4 é : η =
Pág 53 de 68
m 4
= = 0.57
L 7
Escola Náutica Infante Dom Henrique
Departamento de Radiotecnia
Interfaces e Transmissão de dados - 6222
Notas sobre detecção e correcção de erros
V preliminar
Procedimento:
1 – Dividir a mensagem em sub-conjuntos mais pequenos de bits chamados subconjuntos de paridades.
2 – Adicionar um bit de paridade por cada um dos sub-conjuntos. (A paridade pode ser
par ou ímpar não sendo relevante para este caso)
3 – Garantir que cada um dos bits da mensagem não pertença exclusivamente a um
sub-conjunto de paridades
Implica que sempre que existam erros em número par se não são detectados por um
sub-conjunto, sê-lo-ão por outro
O ponto 3 é muito importante, pois garante que quando há erros em número par num
dos sub-conjuntos, existem sempre erros em número ímpar noutro sub-conjunto,
ultrapassando a limitação da paridade simples.
Consideremos então a mensagem m, de comprimento m = 4 bits:
m = [ m0 m1 m 2 m 3 ]
De seguida serão criados 3 sub-conjuntos de paridade P0, P1 e P2 como ilustra o
diagrama de Venn da figura 6.5
Figura 6.5 Diagrama de Venn com sub-conjuntos de paridade de m
Os bits de m, são agora distribuídos pelas intersecções de cada conjunto de acordo
com a figura 6.6. Assim, garantimos que cada um dos bits de paridade cobre todas as
diferentes combinações ímpares de bit. Por outras palavras não existem grupos de
dois bits (incluindo P0,P1 eP2) que não sejam abrangidos por mais do que um subconjunto de paridade.
Figura 6.6 Diagrama de Venn com sub-conjuntos de paridade e bits de m
Pág 54 de 68
Escola Náutica Infante Dom Henrique
Departamento de Radiotecnia
Interfaces e Transmissão de dados - 6222
Notas sobre detecção e correcção de erros
V preliminar
As equações dos bits de paridade são as seguintes:
P0 = m 0 ⊕ m 1 ⊕ m 3
P1 = m 0 ⊕ m 2 ⊕ m 3
P2 = m 1 ⊕ m 2 ⊕ m 3
(6.6)
Ora caso à recepção existam erros nos bit de paridade P1 e P2, o bit m2 está errado
pois é o único que é comum a P1 e P2.
E caso existisse um erro no bit de paridade P0? O erro só poderia estar no próprio bit
de paridade P0, pois qualquer um dos outros bit em erro causaria também inversões
em P1 ou P2.
6.3.2 – Síndrome de um código de blocos linear
Definição 6.3
Síndrome é um vector de código composto pela soma modulo 2 dos bits da
mensagem e o respectivo bit de paridade Os bits a “1” do vector síndrome
indicam os bit de paridade que foram trocados (que sinalizam erro)
Na prática, o receptor vai calcular a soma dos bits que pertencem a cada um dos subconjuntos de paridade (incluindo o de paridade). Este resultado é denominado
r
síndrome e é representado pelo vector E
No código de Hamming (7,4,3) objecto de estudo existem três bits de síndrome a
calcular (um por cada bit de paridade).
As equações do síndrome são as seguintes:
E0 = m0 ⊕ m1 ⊕ m3 ⊕ P0
E1 = m0 ⊕ m2 ⊕ m3 ⊕ P1
E2 = m1 ⊕ m2 ⊕ m3 ⊕ P2
(6.7)
r
Caso o vector síndrome E = [ E2
E1
E0 ] seja 000, significa que não existiram erros.
Caso contrário, vai indicar o bit onde existe o erro.
Com base no código anterior e olhando para o diagrama de Venn da figura 6.4,
podemos calcular as 8 combinações possíveis de valores do vector síndrome e
apresentá-los numa tabela (tabela 6.1)
Pág 55 de 68
Escola Náutica Infante Dom Henrique
Departamento de Radiotecnia
Interfaces e Transmissão de dados - 6222
Notas sobre detecção e correcção de erros
E2E1E0
000
001
010
011
100
101
110
111
V preliminar
Correcção do erro unitário de bit
Não são detectados erros
P0 em erro. O erro localiza-se no próprio bit P0.
P1 em erro. O erro localiza-se no próprio bit P1.
P0 e P1 em erro. O bit comum a P0 e P1 é m0. O erro localiza-se em m0
P2 em erro. O erro localiza-se no próprio bit P2.
P0 e P2 em erro. O bit comum a P0 e P1 é m1. O erro localiza-se em m1
P1 e P2 em erro. O bit comum a P0 e P1 é m2. O erro localiza-se em m2
P1,P2 e P3 em erro. O bit comum a P0, P1 e P2 é B3. O erro localiza-se em m3
Tabela 6.1 Valores possíveis do vector síndrome e respectiva correcção de erros para
o código de Hamming (7,4,3)
r
O vector síndrome E , permite-nos obter 8 correcções possíveis: Sem erros, 4 bits da
mensagem em erro ou os 3 bit de paridade em erro.
O receptor tem que conhecer a tabela dos valores possíveis do vector síndrome para
descodificar a mensagem e corrigir o erro.
6.3.3 – Número mínimo de bits de paridade do código de Hamming
O número de mínimo de bits redundantes de um código de Hamming, calcula-se com
base no comprimento da palavra de código c
Tendo c, L bits de comprimento (incluindo v bits de verificação) significa que poderão
existir erros de bit unitários em L diferentes posições
Como cada posição do erro é identificada por uma combinação distinta dos bits do
síndrome (ver tabela 5.1) em que vector nulo implica que não há erros, tem que haver
tantas combinações diferentes de 0, quantas as posições do bit errado ou seja:
Têm que existir tantas combinações de bits possíveis do vector síndrome
diferentes do vector nulo, quantos o número de bits da palavra de código (L)
Em qualquer código temos:
2v diferentes combinações de síndrome
2v-1 diferentes combinações de síndrome, diferentes de 0.
L possíveis posições de erros unitários na palavra de código.
L ≤ 2v − 1
(6.8)
Pela equação 6.8, sendo v = L-m, fixando o valor da mensagem m, obtêm-se v
mínimo necessário para garantir a correcção do erro.
Pág 56 de 68
Escola Náutica Infante Dom Henrique
Departamento de Radiotecnia
Interfaces e Transmissão de dados - 6222
Notas sobre detecção e correcção de erros
V preliminar
6.3.4 – Construção de um código de Hamming (7,4,3) sistemático
Dada a equação 6.6 de paridades, facilmente se constrói o universo do código de
Hamming sistemático denominado no nosso caso, α(7,4,3). Os pesos de Hamming
são obtidos recorrendo à definição 6.1
Teremos 8 palavras diferentes e 24 = 16 possíveis combinações de bits.
Os bits redundantes serão adicionados ao final da palavra pois o código é
sistemático.
Palavra de código α(7,4)
Nome
A
B
C
D
E
F
G
H
I
J
L
M
N
O
P
Q
m3m2m1m0
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
v2v1v0
000
011
101
110
110
101
011
000
111
100
010
001
001
010
100
111
Peso de
Hamming (w)
w
0
3
3
4
3
4
4
3
4
3
3
4
3
4
4
7
Tabela 6.2 Alfabeto completo e pesos de Hamming do código α(7,4,3)
6.3.5 – Controlo de erros do código de Hamming (7,4,3) sistemático
A capacidade de controlo de erros dependem da distância de Hamming do código
completo dmin e é dada pelas equações 4.1 e 4.2
A dmin pode ser facilmente obtida pelo peso de Hamming w (ver equação 6.3)
d min = min w (α ) = 3 , como seria de esperar.
Sendo assim, de acordo com as equações 4.1 e 4.3 confirma-se que este código é
capaz de detectar até 2 erros isolados de bit e corrigir 1 erro isolado de bit.
Pág 57 de 68
Escola Náutica Infante Dom Henrique
Departamento de Radiotecnia
Interfaces e Transmissão de dados - 6222
Notas sobre detecção e correcção de erros
V preliminar
Teste 1 – Recepção com erro num dos bits
Admitamos que ao receptor chega a seguinte palavra: 0110 111 (Palavra de código
“G” com o bit v2 errado)
O receptor vai calcular o vector síndrome da palavra de código recebida:
E0 = m0 ⊕ m1 ⊕ m3 ⊕ P0 = 0 ⊕ 1 ⊕ 0 ⊕ 1= 0
E1 = m0 ⊕ m2 ⊕ m3 ⊕ P1= 0 ⊕ 1 ⊕ 0 ⊕ 1 = 0
E2 = m1 ⊕ m2 ⊕ m3 ⊕ P2= 1 ⊕ 1 ⊕ 0 ⊕ 1 = 1
E = [1 0 0 ], ora de acordo com a tabela de descodificação do receptor (Tabela 6.1),
este síndrome corresponde ao bit de verificação v2 com erro, portanto a palavra é
facilmente corrigida invertendo esse bit.
Deixa-se ao critério do leitor fazer outras experiências com erros simples de bit noutras
palavras de código em qualquer posição e concluir que o erro é sempre corrigido.
6.3.6 – Construção de um código de Hamming (7,4,3) não sistemático
Caso se entrelace11 inteligentemente os bits de paridade pela palavra de código,
Hamming demonstrou que é possível que, em caso de erro, o vector síndroma
identifique o valor da posição do bit em erro, simplificando o processo de
descodificação.
As posições dos bits de verificação são as posições que são potências de base 2,
desde 1 até ao comprimento da mensagem m.
O número de bits de verificação v a utilizar é igual ao número de potências de base 2
desde 0 até ao comprimento da mensagem m.
v =  20
2...
2m 
A construção deste código é bastante simples. Considere-se um código do tipo (7,4,3)
em que a mensagem m = 1010
11
Ao entrelaçamento dos bits redundantes pela palavra de código designa-se código não sistemático (ver
secção 4.2)
Pág 58 de 68
Departamento de Radiotecnia
Escola Náutica Infante Dom Henrique
Interfaces e Transmissão de dados - 6222
Notas sobre detecção e correcção de erros
V preliminar
Procedimento de codificação
Passo 1:
Numerar a palavra de código da direita para a esquerda com as posições de cada bit
começando em 1 até ao comprimento total L (neste caso L = 7). Assinalar com X as
posições dos bits redundantes (são as posições que são potências de base 2)
7
6
5
22= 4
3
X
21= 2
20= 1
X
X
Passo 2:
Preencher as posições diferentes de X com os bit da palavra m por ordem
7
6
5
22= 4
3
21= 2
20= 1
1
0
1
X
0
X
X
Passo 3:
Calculo dos bits de paridade: Efectuar a soma módulo 2 do valor das posições em
binário de cada um dos bit a “1”
r
111 (7) ⊕ 101 (5) = 010 => v = [ 0 1 0]
Passo 4:
Preencher as posições diferentes de X com os bits de paridade pela ordem obtida.
7
6
5
22= 4
3
21= 2
20= 1
1
0
1
0
0
1
0
A palavra de código a transmitir é c1 = 1010010
Procedimento de descodificação
No procedimento de descodificação, o receptor vai somar módulo 2, os valores das
posições dos bits de estão a 1. Este é o vector síndrome. Caso seja 0, não há erros.
Caso seja diferente de 0 indica a posição do bit errado.
Teste 1: Recepção sem erros:
c1‘= 1010010
r
O vector síndrome é : 111 (7) ⊕ 101 (5) ⊕ 010 (2) => E = [ 0
O que significa que não foram detectados erros.
Pág 59 de 68
0 0]
Departamento de Radiotecnia
Escola Náutica Infante Dom Henrique
Interfaces e Transmissão de dados - 6222
Notas sobre detecção e correcção de erros
V preliminar
Teste 2: Recepção com erro num dos bits:
Admita-se que o bit da posição 3 vem com erro.
c1‘= 1010110
r
O vector síndrome é : 111 (7) ⊕ 101 (5) ⊕ 011 (3) ⊕ 010 (2) => E = [ 0 1 1]
Como se vê o resultado é 3, bastando ao receptor inverter o bit correspondente a
essa posição da palavra de código.
6.3.7 – Outras famílias de códigos de Hamming
De acordo com a equação 6.8 e definição 6.2, poderão ser derivadas outras famílias
de códigos de Hamming (L,m)
A tabela 6.3 ilustra cada uma das famílias de acordo com o parâmetro v=L-m, e
respectiva eficiência
L
4
11
26
57
120
247
501
m
7
15
31
63
127
255
511
η
0.57
0.73
0.84
0.91
0.94
0.968
0.982
Tabela 6.3 Diferentes famílias de códigos de Hamming
Verifica-se que a eficiência aumenta à medida que o tamanho da palavra de código
aumenta, no entanto este aumento implica um aumento de complexidade do
codificador, e a criação de atrasos que poderão ser intoleráveis ao ter que juntar e
processar elevados números de bits e combinações de palavras de código.
6.3.8 – Sub-conjuntos de famílias de códigos de Hamming
Vale a pena referenciar que é comum a codificação de Hamming aplicada a
mensagens de comprimento diferente dos referidos na tabela 6.3 Consideremos por
exemplo uma mensagem de 8 bit.
Neste caso, sendo m = 8, temos bits redundantes nas posições: 20, 21, 22, 23
Obtemos agora uma palavra de código de comprimento L = 12, m =8 e v = 4.
É importante referir que este é um conjunto reduzido (ou sub-conjunto) da família de
código (11,15).
Pág 60 de 68
Departamento de Radiotecnia
Escola Náutica Infante Dom Henrique
Interfaces e Transmissão de dados - 6222
Notas sobre detecção e correcção de erros
V preliminar
O algoritmo de codificação de Hamming não sistemático é exactamente igual ao
descrito na secção 6.3.6,
A título de exemplo, a codificação deste sub-conjunto para m = 10001101, é a
seguinte
Passo 1
Assinalar com X as posições dos bits redundantes
12
11
10
9
3
2 =8
7
6
5
X
2
2=4
3
X
1
0
2 =2
2=1
X
X
Passo 2
Preencher as posições diferentes de X com os bit da palavra m por ordem
12
11
10
9
23 = 8
7
6
5
22= 4
3
21 = 2
20= 1
1
0
0
0
X
1
1
0
X
1
X
X
Passo 3
Cálculo dos valores dos bits de verificação
r
1100 (12) ⊕ 0111 (7) ⊕ 0110 (6) ⊕ 0011 (7) = 1110 => v = [1 1 1 0]
12
11
10
9
23 = 8
7
6
5
22= 4
3
21 = 2
20= 1
1
0
0
0
1
1
1
0
1
1
1
0
Passo 4:
Preencher as posições diferentes de X com os bits de paridade pela ordem obtida.
A palavra de código a transmitir é c2 = 100011101110
Sugere-se que o leitor calcule o vector síndroma e confirme que este código corrige os
erros unitários de bit.
Pág 61 de 68
Departamento de Radiotecnia
Escola Náutica Infante Dom Henrique
Interfaces e Transmissão de dados - 6222
Notas sobre detecção e correcção de erros
V preliminar
6.4 – Representação matricial de um código de blocos linear.
Cada palavra de um código de blocos linear pode ser escrita na forma matricial:
1 - Codificação
A codificação não é mais do que a multiplicação do vector mensagem m de dimensões
[1,m] pela matriz geradora G de dimensões [ (m), (m+v)]
c = mG
(6.9)
A matriz geradora G designa-se por matriz geradora de código e é definida de forma
a cumprir os seguintes requisitos:
1 – Não possui o vector nulo
2 – Não tem duas linhas iguais
A matriz geradora G é sempre composta por duas sub-matrizes:
1 - Matriz identidade com dimensão mxm, ou seja com a mesma dimensão da
mensagem
2 Matriz de paridades P, com dimensões mxv, que contêm o sistema de equações
para cálculo dos bits de paridade.
G = [ I mxm | Pmxv ]
(6.10)
A título de exemplo é apresentada a matriz G1, geradora do código de Hamming
sistemático (7,4,3) estudado na secção 6.3.4.
m3 m2 m1 m0 P2 P1 P0
1

0
G1 = [ I 4 x 4 | P4 x 3 ] = 
0

0
0 0 0 0 1 1

1 0 0 1 0 1
0 1 0 1 1 0

0 0 1 1 1 1 
Repare-se como a matriz de paridades representada a vermelho implementa o
sistema de equações de paridade em cada uma das colunas, descrito pela equação
6.6.
P0 = m 0 ⊕ m 1 ⊕ 0 ⊕ m 3
P1 = m 0 ⊕ 0 ⊕ m 2 ⊕ m 3
P2 = 0 ⊕ m 1 ⊕ m 2 ⊕ m 3
Pág 62 de 68
Departamento de Radiotecnia
Escola Náutica Infante Dom Henrique
Interfaces e Transmissão de dados - 6222
Notas sobre detecção e correcção de erros
V preliminar
De acordo com a equação 6.9, o alfabeto de código de Hamming (7,4,3) que foi
representado na tabela 6.3, é obtido pela multiplicação do vector mensagem pela
matriz geradora G1.
α ( 7, 4,3) = [ m3 m2 m1
1

0
m0 ] 
0

0
0 0 0 0 1 1

1 0 0 1 0 1
0 1 0 1 1 0

0 0 1 1 1 1 
Note-se que qualquer outra sub-matriz geradora geradora de paridade P, que
contenha pelo menos dois bit a 1 por cada linha é uma matriz geradora de um código
de Hamming (7,4,3). Estes são os casos, por exemplo das matrizes geradoras G2 e
G3.
1

0
G2 = 
0

0
0 0 0 0 1 1
1


1 0 0 1 0 1
0
G
=
3
0
0 1 0 1 1 0 ,


0 0 1 1 1 1 
0
0 0 0 0 1 1

1 0 0 1 0 1
0 1 0 1 1 0

0 0 1 1 1 1 
Sugere-se que o leitor construa diferentes alfabetos de código com base em G2 e G3
e que verifique que o código resultante tem dmin = 3 e corrige erros de 1 bit.
2 - Descodificação
Em termos matriciais, a descodificação é semelhante à codificação. Agora a palavra
de código recebida é multiplicada por uma matiz de mxv dimensões designada por
matriz de teste de paridade : HT
O resultado deste multiplicação é o vector síndrome E de dimensões 1xv
E = cH T
(6.11)
A matriz HT tem a seguinte forma:
P 
HT =  
 Iv 
(6.12)
HT é ortogonal à matriz geradora G, de forma a que:
Pág 63 de 68
Escola Náutica Infante Dom Henrique
Departamento de Radiotecnia
Interfaces e Transmissão de dados - 6222
Notas sobre detecção e correcção de erros
GH = [ I m
T
0 L 0 
P  
P]   =  M
M 
I
 v  0 L 0 


V preliminar
(6.13)
O resultado da equação 6.13 é a matriz nula de mxv bits:
De acordo com a equação 6.9, a palavra de código vem codificada na forma c = mG ,
então substituindo 6.9 em 6.11:
E = cH T = mGH T = [ 0 L 0]
(6.14)
O resultado da equação 5.15 é o vector nulo de dimensão 1xv.
A título de exemplo é apresentada a matriz H1T, de teste de paridades do código de
Hamming sistemático (7,4,3) estudado na secção 6.3.4.
Esta matriz tem o formato da equação 6.12, e é dada por:
0
1

1

T
H = 1
1

0
0

1 1
1 0

0 1

1 1
0 0

1 0
0 1 
Repare-se que a vermelho está a matriz geradora de paridades e a preto a matriz
identidade.
Pág 64 de 68
Escola Náutica Infante Dom Henrique
Departamento de Radiotecnia
Interfaces e Transmissão de dados - 6222
Notas sobre detecção e correcção de erros
V preliminar
Teste 1 – Recepção sem erros
Vamos admitir que é recebida a palavra de código denominada “G” na tabela 6.2.
G = 0110 011
O receptor vai calcular o vector síndrome (equação 6.14)
0
1

1

T
E = cH = [ 0 1 1 0 0 1 1] 1
1

0
0

1 1
1 0

0 1

1 1  = [ 0 0 0]
0 0

1 0
0 1 
Como seria de esperar, sem erros o síndrome é nulo
Teste 2 – Recepção sem erros
Vamos admitir que é recebida a palavra de código “G” com um bit errado.
G = 0110 111
O síndrome é agora:
0
1

1

T
E = cH = [ 0 1 1 0 1 1 1] 1
1

0
0

1 1
1 0

0 1

1 1  = [1 0 0]
0 0

1 0
0 1 
Este é exactamente o mesmo resultado obtido na secção 5.3.5 , teste 1, e sinaliza
correctamente o bit em erro.
Pág 65 de 68
Escola Náutica Infante Dom Henrique
Departamento de Radiotecnia
Interfaces e Transmissão de dados - 6222
Notas sobre detecção e correcção de erros
V preliminar
6.4.1 – Considerações adicionais sobre o síndrome
Caso existam erros que possam ser corrigidos, ao receptor chegará uma palavra de
código Rx afectada pelo vector de erro ε
Rx = c ⊕ ε
(6.15)
O padrão de erro ε vai originar um síndrome não nulo:
E = Rx H T = ( c ⊕ ε ) H T = mGH T + ε H T
(6.16)
[0 ... 0]
Verifica-se que o síndrome apenas depende do padrão de erro ε , o que significa
que é possível construir uma tabela de síndromas a partir de uma associação do
padrão de erro com HT
Como exemplo considere-se uma palavra de código de 7 bit de comprimento, e
respectivo padrão de erro:
Caso o primeiro bit esteja errado, temos
ε = [1 0 0 0 0 0 0] .H T
= 1ª linha de HT
Caso o segundo bit esteja errado temos:
ε = [ 0 1 0 0 0 0 0] .H T
= 2ª linha de HT
E assim sucessivamente para todos os padrões de 1 bit em erro,. Para o caso do
código α ( 7, 4, 3) estudado na secção 6.3.5, a tabela de síndromas e correspondente
padrão de erro estão ilustrados na tabela 6.4
Desta tabela de síndromes obtêm-se a matriz HT com a ajuda da equação 6.16.
Padrão de erro ε
0000000
1000000
0100000
0010000
0001000
0000100
0000010
0000001
Observação
Sem erros
1º Bit em erro
2º Bit em erro
3º Bit em erro
4º Bit em erro
5º Bit em erro
6º Bit em erro
7º Bit em erro
Síndrome E =cHT
000
111
110
101
011
001
010
100
Tabela 6.4 Tabela de síndromes para cada padrão de erro
Pág 66 de 68
Escola Náutica Infante Dom Henrique
Departamento de Radiotecnia
Interfaces e Transmissão de dados - 6222
Notas sobre detecção e correcção de erros
V preliminar
Nota:
É possível fazer coincidir o valor do síndrome com a posição do bit em erro.
Para tal basta fazer uma lista equivalente à da tabela 6.4, com os síndromes
desejados para cada padrão do erro.
Após calcular a matriz HT retira-se a sub-matriz de paridades P.
Pela tabela 6.4, observamos ainda que cada padrão de erros de 1 bit gera um e
apenas um síndrome,
O número total de síndromas é dado pela equação 6.8: Neste exemplo de código com
3 bit de verificação temos
diferentes de 0.
2v − 1 = 23 − 1 = 7 diferentes
combinações de síndrome
Devido a esta particularidade, os códigos de Hamming são designados códigos
perfeitos
Definição 5.5
Um código perfeito é aquele em que cada erro de bit corresponde apenas um
síndrome.
Pág 67 de 68
Escola Náutica Infante Dom Henrique
Departamento de Radiotecnia
Interfaces e Transmissão de dados - 6222
Notas sobre detecção e correcção de erros
V preliminar
Referências
[PETER01] W.W. Peterson, D.T. Brown, Cyclic codes for error detection, Proceedings
of the IRE, Volume 49, pages 228-235, Jan 1961.
[HAMM01] R. W. Hamming, Error Detecting and Error Correcting Codes. Bell
System Technical Journal, vol. 29, pp. 147-160, April, 1950.
Pág 68 de 68