Upload
ericalago
View
10
Download
0
Embed Size (px)
DESCRIPTION
Conteúdo de Alta disponibilidade
Citation preview
SISTEMAS PARA INTERNET
ALTA DISPONIBILIDADE DE SERVIOS WEB
PROF. NAPOLEO PVOA RIBEIRO FILHO
Cdigos para deteco e correo de erros
Cdigos de deteco de erros:
Paridade, checksum, CRC (Cyclic Redundancy Check)
Cdigos de deteco e correo de erros: Cdigo de Hamming
Cdigos de deteco de erros
uma tarefa simples
Nem sempre possvel solicitar uma retransmisso
Todos os mtodos utilizam a insero de bits extras.
Um mtodo ineficiente mas muito usado a paridade
Um mtodo mais eficiente o CRC
Paridade Consiste basicamente no ato do transmissor
adicionar um bit de redundncia aps um determinado nmero de bits (normalmente um byte)
n par de 1s: paridade par
n mpar de 1s: paridade mpar
000, 011, 101, 110: so mensagens transmitidas sem erro, tendo em conta que o ltimo bit o de paridade
Paridade Exemplo: o caractere A no cdigo ASCII
representado por 1000001
O bit P de paridade calculado e transmitido:
1000001P->n par de 1s: P=0, logo se transmite 10000010!
O receptor calcula a paridade da mensagem e compara-a com o bit P recebido: P = paridade -> transmisso correta
Paridade Esse processo pode ser vulnervel se houver mais
do que um erro, permitindo assim que este passe at ao destino sem ser identificado:
Exemplo: 11010010 - devolve o valor 0 mas existe erro
Tcnica usada em muitas aplicaes de hardware, onde uma operao pode ser repetida em caso de dificuldade, ou onde til a simples deteco de erros.
Checksum Consiste na transmisso de todas as palavras
juntamente com o resultado da sua soma binria
Inclui o bit de transporte
Inverso do valor dos bits do checksum
!
!
A B Soma Transporte
0 0 0 0
0 1 1 0
1 0 1 0
1 1 0 1
Checksum
Exemplo: checksum de 2 palavras de 8 bits
Dados iniciais: 00111101 00001101
Checksum: 01001010
Checksum invertido: 10110101
Checksum Dados enviados: 00111101, 00001101 e 10110101 (checksum
invertido)
No receptor, as palavras so novamente somadas e comparadas com o checksum enviado.
Se qualquer um dos dados transmitidos, incluindo o checksum, sofrerem algum erro, ento a soma do novo checksum com o checksum invertido enviado ser diferente de 1.
01001010 -> novo checksum 10110101 -> checksum invertido 11111111 -> sem erro
Checksum00110001 -> palavra enviada 00001101 -> palavra enviada 00110110 -> novo checksum 10110101 -> checksum envertido 11101011 -> houve erro na transmisso ! Valor recebido incorretamente, com erro no 3 ou
5 bit (de qualquer palavra enviada, inclusive o checksum)
CRC (Cyclic Redundancy Check)
Esquema mais eficiente
Emissor/receptor concordam em um polinmio gerador G(x), em que quanto maior for seu grau, maior ser a capacidade de deteco de erros.
Nesse polinmio tanto o bit de maior ordem quanto o de menor ordem devem ser iguais a 1
A palavra inicial de k bits representada por um polinmio de X de ordem k-1
palavra inicial: 10110001
polinmio: x7+x5+x4+1
Execuo: o polinmio p(x) representado pela palavra inicial somada aos bits de paridade e deve ser divisvel por G(x);
O receptor tenta dividir p(x) por G(x). Se houver resto 0,houve um erro de transmisso;
Se houver um erro, em vez de se receber o polinmio T(x), recebe-se T(x)+E(x);
Cada bit 1 de E(x) corresponde a um bit invertido
T(x)/G(x) sempre zero, logo o resultado E(x)/G(x)
CRC (Cyclic Redundancy Check)
Exemplo -> mensagem a transmitir: 10111011
Polinmio gerador: G(x)=x4+x+1 -> 10011
Acrescenta-se a mensagem inicial a quantidade de zeros equivalentes ao grau de G(x): 101110110000
Seguidamente divide-se a mensagem pelo polinmio gerador
A diviso de dois polinmios (na sua forma binria) feita recorrendo operao (XOR)
CRC (Cyclic Redundancy Check)
CRC (Cyclic Redundancy Check)
O resto da diviso finalmente adicionado mensagem original. Assim a mensagem a ser transmitida :
101110111111
Para decodificar a mensagem, o procedimento deve ser repetido.
!
!
!
!
CRC (Cyclic Redundancy Check)
Cdigos de correo de erros
Podem recuperar o dado original a partir do cdigo com erros.
Consistem na criao de cdigos extras que detectam situaes invlidas mas que mantm a identidade do dado original.
O conceito mais bsico e mais importante desses cdigos a distncia de Hamming, utilizada para a criao de cdigos de correo.
Cdigo de Hamming Os bits da palavra de cdigo so numerados a
partir da esquerda, comeando por 1.
acrescentada informao redundante em posies pr-definidas, ou seja, os bits que so potncia de 2 vo ser bits de controle (2n).
Os restantes so preenchidos com k bits de dados conhecidos, isto , a mensagem a ser transmitida.
Exemplo -> Mensagem: 1001
!
!
!
!
!
Cdigo de Hamming
1=2 2=2 3 4=2 5 6 7
1 1 0 0 1
2 ? ? ?
3 ? ? 1 ? 0 0 1
Os bits de controle so calculados, convertendo para binrio as posies 2n e valor=1.
3 - 011 e 7 - 111
Aplicao da XOR aos valores no ponto anterior
0 1 1 1 1 1 1 0 0 3 2 1
Cdigo de Hamming
Depois feita a insero dos valores nas respetivas posies dos bits de paridade.
!
A mensagem a ser transmitida :
0011001
!
!
Cdigo de Hamming
1=2 2=2 3 4=2 5 6 7
1 1 0 0 1
2 ? ? ?
3 0 0 1 1 0 0 1
Converso para binrio das posies = 1.
Aplicao do XOR aos valores obtidos no ponto anterior:
Se o resultado for = 0, no houve erros na transmisso
Se for 0, o resultado obtido convertido para decimal igual posio do erro
Cdigo de Hamming - decodificaro
Cdigo de Hamming - decodificaro