Detecção de Erros – Paridade

Detecção de Erros – Paridade
Verificação de Paridade
– Esse tipo de detecção consiste em acrescentar um bit (de
paridade) a cada conjunto de bits da mensagem (caractere) de
modo a ter as seguintes características:
• Paridade Par
– Acrescenta um bit 1 ou um bit 0 às mensagem para que o número total
de bits 1 seja par
• Paridade Ímpar
– Acrescenta um bit 1 ou um bit 0 às mensagem para que o número total
de bits 1 seja ímpar
– Assim, uma mensagem com k bits se torna uma palavra de
código com n = k + 1 bits
• ASCII: utiliza 7 bits para codificação da informação (k = 7) e 1 bit para
paridade (n = 7)
– O método de detecção de erros por paridade é pouco eficiente
• Se houver um número par de bits errados, o esquema de paridade não
consegue detectar a ocorrência de erros
Detecção de Erros – Paridade
Exemplo de Detecção de Erros – Paridade Par (k=3)
x1
x2
x3
P
0
0
0
0
0
0
1
1
0
1
0
1
0
1
1
0
1
0
0
1
1
0
1
0
1
1
0
0
1
1
1
1
Detecção de Erros – Paridade
Exemplo de Detecção de Erros – Paridade Ímpar (k=3)
x1
x2
x3
P
0
0
0
1
0
0
1
0
0
1
0
0
0
1
1
1
1
0
0
0
1
0
1
1
1
1
0
1
1
1
1
0
Detecção de Erros – BSC
Block Sum Check (BSC)
– Probabilidade de um bloco de caracteres conter erros ⇒ taxa de
erro de bloco
– Usa conj. de bits de paridade calculado pelo no. total de
caracteres transmitidos em um frame
– Exemplo:
x1 x2
x3
x4 | Pr(impar) ⇒
1
0
0
0 |⇒0
0
1
1
0 |⇒1
1
0
1
1 |⇒0
------------------------0
1
0
1
| 1 Pc(par) ⇓
Detecção de Erros – CRC
Cyclic Redundance Check (CRC)
– No Transmissor, um bloco de k bits é representado por um
polinômio de ordem k – 1
• Bloco: 1 0 1 1 0 0 0 1 ⇒ p7 + p5 + p4 + 1
• Polinômio é dividido mod2 por um polinômio gerador de ordem n,
tendo um quociente e um resto de ordem n – 1
• Frame de k bits de informação seguidos dos n bits correspondentes
ao resto da divisão de ordem n – 1 (Frame Check Sum - FCS)
– No Receptor, o polinômio de ordem k – 1, correspondente aos k
primeiros bits recebidos, é dividido pelo mesmo polinômio gerador
usado no Transmissor
• O resto da divisão é comparado com os n últimos bits recebidos
• Se forem iguais, não há erros
• Se os bits forem diferentes, cada bit diferente representa um erro
Detecção de Erros – CRC
– CRC-12
• Caracteres de 6 bits
• FCS de 12 (p12 + p11 + p3 + p2 + p + 1)
– CRC-16
• Caracteres de 8 bits
• FCS de 16 (p16 + p15 + p2 + 1)
– CRC-32
• Caracteres de 8 bits
• FCS de 32 (p32+p26+p23+p22+p16+p12+p11+p10+p8+p7+p5+p4+p2 +p+1)
Exemplos de
Códigos de Bloco
Correção de Erros – Códigos de Bloco
Códigos de Hamming
– Foram descobertos por R.W. Hamming e constituem um código
perfeito (para correção de um único erro)
– Os códigos de Hamming apresentam m ≥ 2 e apresentam:
n = 2m − 1
k = n−m
– A distância mínima é sempre igual a 3, independente do número de
bits de paridade usado, de modo que podem detectar até 2 erros e
corrigir apenas 1 erro:
d min = 3
3 ≥ t1 + 1
3 ≥ 2 ⋅ t2 + 1
– As k linhas da matriz PT consistem em palavras de m bits com 3 ou
mais bits 1
Correção de Erros – Códigos de Golay
Códigos de Golay
– São códigos de correção de erros cíclicos perfeitos (para correção
3 erros) que podem ser gerados pelos polinômios:
g1 ( p ) = 1 + p 2 + p 4 + p 5 + p 6 + p10 + p11
g 2 ( p ) = 1 + p + p 5 + p 6 + p 7 + p 9 + p11
– Os códigos de Golay apresentam as seguintes características:
n = 23
k = 12
– A distância mínima é sempre igual a 7, independente do número
de bits de paridade usado, de modo que podem detectar até 6
erros e corrigir até 3 erros:
d min = 7
7 ≥ t1 + 1
7 ≥ 2 ⋅ t2 + 1
Correção de Erros – Códigos BCH
Códigos BCH
– Foram descobertos por Bose, Chaudhuri e Hocquenghem
– São os códigos de correção de erros cíclicos mais eficientes
• Constituem uma família de códigos de bloco cíclicos que englobam
os códigos de Hamming
• Enquanto os códigos de Hamming conseguem detectar no máximo
2 erros e corrigir apenas 1, os códigos BCH permitem detectar e
corrigir um número bastante grande de erros
– Exemplo: BCH (64,127) pode corrigir até 10 erros
– Os códigos BCH apresentam m ≥ 3 e apresentam:
n = 2m − 1
k ≥ n − m ⋅ t2
– A distância mínima é dada por:
d min ≥ t1 + 1 d min ≥ 2 ⋅ t 2 + 1
Correção de Erros – Códigos Reed Solomon
Códigos de Reed Solomon
– São um subconjunto dos códigos BCH que opera num nível de
bloco ao invés de bit
– Em outras palavras, a seqüência de informação é primeiramente
empacotada em blocos menores que são tratados como um
novo conjunto de k símbolos para serem empacotados num
bloco supercodificado de n símbolos
– Dessa maneira, o decodificador é capaz de detectar e corrigir
blocos completos de erros
– O emprego de códigos de Reed Solomon permite corrigir uma
seqüência grande de erros (erros em rajadas) que ocorrer com
freqüência nas transmissões em canais com desvanecimento e
nas reproduções de CDs contendo riscos
• Normalmente são associados a entrelaçadores
Correção de Erros – Códigos Reed Solomon
– Os códigos de Reed Solomon apresentam:
n = 2m − 1
k = n − 2 ⋅ t2
– Considerando que a palavra de código é composta por m bits,
devem satisfazer a seguinte condição:
0 < k < n < 2m − 2
– A distância mínima é dada por:
d min = n − k + 1
– E a capacidade de correção é dada por:
n − k 
t2 = 
 2 
Modulação Codificada
em Treliça (TCM)
Modulação Codificada em Treliça – TCM
Modulação Codificada em Treliça
Partição – 8PSK
Modulação Codificada em Treliça – TCM
Modulação Codificada em Treliça
Modulação Codificada em Treliça – TCM
Modulação Codificada em Treliça
Modulação Codificada em Treliça – TCM
Modulação Codificada em Treliça