5- Tratamento de Erros v7falencar/arquivos-flavio-uerj/redes1/redes1-5-erros-v7.pdfA taxa de código de um método corretor é geralmente mais baixa que a de um método detector, de

N O T A S D E A U L A , R E V 7 . 0 – U E R J 2 0 2 0 – F L Á V I O A L E N C A R D O R Ê G O B A R R O S

Redes de Comunicações 1

Tratamento de Erros

Flávio Alencar do Rego Barros Universidade do Estado do Rio de Janeiro

E-mail: [email protected]

Capítulo

5

UERJ 2020 – versão 7 Redes de Comunicações 1 Pg.1

Erros são introduzidos nos quadros, seja por interferências elétricas, seja por

ruído térmico, ou ainda, por efeitos diversos, principalmente em meios não guiados.

Existem diversas formas de lidar com eles, este é o assunto deste capítulo.

Problemas de sequenciamento de dados (apagamento, duplicação e

reordenamento) podem ser resolvidos com mecanismos de controle de fluxo, mas

distorção e inserção precisarão de métodos para verificar a consistência de dados.

A característica do erro é expressa principalmente em termos do bit error rate

médio, mas também em termos de percentual do tempo que o bit error rate não

ultrapassou certo limite estabelecido, ou ainda em termos do percentual de segundos

“error free”.


Se observarmos o slide 05-3, o número de erros de transmissão é muito maior

que o número de erros de hardware.Muitos tipos diferentes de erros podem acontecer

nas linhas de dados durante uma transmissão. Os mais importantes são:

Inserção: depende das características do meio.

Apagamento: estes dois últimos podem acontecer devido à perda temporária de

sincronização entre emissor e receptor. Apagamento pode também devido a

políticas inadequadas para controle de fluxo (estouro de buffer).

Duplicação: pode acontecer devido a políticas de retransmissão de dados.

Distorção: depende das características do meio.

Reordenamento: devido a diferentes rotas e retardos experimentados por dados.

Os métodos de tratamento de erros acarretam dois tipos de comportamento:

1) Ou lançam mão de redundância na informação transmitida, e o objetivo é

recuperar ou, no mínimo, detectar o erro;

2) Ou lançam mão de mecanismos de retransmissão.

Dependendo do contexto, um ou outro método é o mais adequado (ou mesmo

possível). Pense, por exemplo, nas redes que envolvam satélites ou naves de exploração


espacial. Netas, claramente o primeiro método é desejável, o segundo pode não ser

sequer exeqüível. A Internet, como ela é hoje, lança mão do segundo tipo de mecanismo

por ser gritante a facilidade de retransmitir a informação perdida.

Neste capítulo analisaremos os dois mecanismos, mas o que prevalecerá nos

próximos capítulos serão os métodos de retransmissão.


Para corrigir erros de bits transmitidos existem duas técnicas básicas:

- Forward Error Control (FEC): a redundância colocada na mensagem é suficiente para

reconstruir a mensagem do sinal distorcido. Códigos de transmissão

correspondentes a esta técnica são chamados error correcting codes (ECC).

- Feedback Error Control: o objetivo é retransmitir o dado corrompido. Usa-se um

código chamado error detecting code (EDC).

De pronto, deve-se entender que nem todos os erros poderão ser detectados,

haverá sempre uma taxa de erros residual que pode ser minimizada por acréscimos na

redundância ou melhorias técnicas.

Existem dois tipos básicos de códigos para tratamento de erros:

- códigos de bloco: todo código tem o mesmo comprimento e a codificação para cada

mensagem pode ser estaticamente definida. Sua colocação se dá ao final do dado.

Na Internet este é o tipo dominante.

- códigos convolucionais: o código depende do dado e da mensagem codificada

previamente definida. Resumidamente, podemos dizer que o encodificador troca

de estado cada vez que uma mensagem é processada.

Por fim, que fique claro que métodos corretores seriam preferíveis a métodos

detectores de erro (por latência e por largura de banda!). Porém, a correção exige o

envio de um número maior de bits o tempo todo, o que pode ser inviável, daí os códigos

detectores serem mais populares na Internet. Outra razão forte é que os núcleos de rede

com meios baseados em fibra ótica são muito confiáveis (vide slide 5-3), seria, pois,

desperdício de banda transmitir bits para corrigir erros que, provavelmente, quase nunca

acontecerão!


Outra forma de classificar códigos leva em conta:

- códigos lineares: toda combinação linear de palavras válidas de código (feitas em

aritmética módulo-2) produz outra palavra de código válida (solução dominante);

- códigos cíclicos: todo deslocamento cíclico de uma palavra de código válida produz

outra palavra de código válida;

- códigos sistemáticos: cada palavra de código inclui os dados originais seguida ou

precedida de um grupo separado de check bits.

Em todos os casos a palavra de código (e) é maior que a palavra de dados (d)

original.

Define-se taxa de código como d/(d + e), que, adicionalmente, nos dá idéia do

overhead envolvido. Para reduzir a taxa de erros de um canal pode exigir diminuir a

taxa de código por um valor correspondente.

A taxa de código de um método corretor é geralmente mais baixa que a de um

método detector, de modo que métodos FEC só são considerados quando é difícil


retornar mensagens de controle do receptor ao emissor. As possíveis razões destas

dificuldades são:

- retardo de transmissão muito longo (pesquisa espacial);

- ausência de canal de retorno (radiodifusão);

- taxas de erro muito altas (redes sem fio).

Certa codificação escolhida permitirá corrigir ou detectar erros conforme a

“distância mínima de Hamming”, onde vale a relação (não demonstraremos, mas vamos

mostrar a sua intuição!):

M – 1 D + C, onde M é a distância mínima entre códigos, D é o número de bits

detectáveis e C é o número de bits corrigíveis. A intuição por trás desta inequação

considera o fato que a distância de Hamming entre dois códigos é o número de bits

necessários trocar para um código válido virar outro código válido. Então:

- para detectar d bits errados, precisa distância de (d + 1) porque não existe modo

de d erros trocar um código válido em outro;

- para corrigir d bits errados, precisa distância de (2d + 1).

Exemplo: Paridade: dH = 2

DETECTA: d + 1 = 2 d = 1 (DETECTA 1 BIT ERROR)

CORRIGE: 2d + 1 = 2 d = ½ (!) (NENHUM)

Exemplo: dH = 3

DETECTA: d + 1 = 3 d = 2 (DETECTA ERRO DUPLO)

CORRIGE: 2d + 1 = 3 d = 1 (CORRIGE UM ERRO)

Como para corrigir tem que detectar, as opções são: 2D; 1D 1C M - 1 D + C

Um problema importante em comunicações é o ERRO RESIDUAL. Trata-se daquele

erro que não é detectado, mas ele está lá, existe! É tarefa para cada método de detecção

ou correção avaliar este erro, quanto menor o erro residual, maior o poder do método.

Por exemplo, para paridade (que só detecta 1 bit errado) o erro residual é dado por:

ER = 1 – p[0 erros] – p[1 erro], como veremos a seguir.


No slide 05-5 (a) a linha cheia mostra como a error rate residual por código

varia com o aumento da taxa de bit error p. A linha pontilhada mostra o mesmo caso

não houvesse paridade (1 – qn). Isto mostra que paridade pode ser útil para dispositivos

com baixo bit error (hardware, memória), porém, é inútil para transmissões em coaxial,

par trançado e sem fio. A figura (b) do mesmo slide mostra a diferença de error rate

para códigos corrigidos e não corrigidos, com um máximo em p = 0.06.

EExxeemmpplloo11:

Seja um código com as palavras válidas:

C0 = 0 0 0 0 0 0 0 0 0 0; C1 = 0 0 0 0 0 1 1 1 1 1; C2 = 1 1 1 1 1 0 0 0 0 0; C3 = 1 1 1 1

1 1 1 1 1 1

Quantos erros podem ser detectados e corrigidos?

R: 4D; 3D-1C; 2D-2C


PPAARRIIDDAADDEE

Via de regra se usa paridade par. A toda mensagem transmitida adiciona-se um bit tal

que a soma deles em módulo 2 dê 0. Também, a taxa de código fica d/(d + 1), significa

que o overhead é baixo. Se a taxa de erros é baixa e não acontece erro de rajada, esta

simplicidade é útil.

Se a probabilidade de múltiplos bits errados é muito baixa, basta proteger a palavra com

paridade (par).

O benefício é reduzir o overhead (1 bit por palavra).

A probabilidade de uma transmissão sem erros é de q(n + 1)

, a probabilidade de um erro

apenas (n bits de dados mais um de paridade) é de (n + 1). p. qn

.

Desta forma, o erro não detectável (erro residual) é como mostrado no slide 05-5,

expresso por 1 – pSEM_ERRO – p1ERRO =

= 1 - q(n + 1)

- (n + 1). p. qn

Refinando-se o método, pode-se transformar o esquema de paridade (que vimos

que é apenas detector) para corretor de erro colocando-se paridade por cada linha e por


cada coluna, conforme o esquema ilustrado no slide 05-6. Neste caso, a taxa de código é

dada por 12/(12 + 8) = 0.6, significando, no entanto, overhead muito alto. Deve-se

perceber a solução de compromisso envolvida (mais bits de overhead (pior!) X maior

poder de correção (melhor)).

EExxeemmpplloo22: Paridade par apresenta M = 2 (certifique-se disto!). Quantos bits podem ser

detectados? Quantos bits podem ser corrigidos?

R: 1; 0

EExxeemmpplloo33: Considere paridade par colocada para proteger a transmissão de 15 bits. Se a

probabilidade de um bit se transmitido errado é de 10-4

(bit error rate), ache a taxa de

erro residual (erro não detectado), considerando distribuição binomial.

R: 1,2 x 10-6


EExxeemmpplloo44:

Respostas: a) 1; 3,96%

b) 0.5; 2,12%

Este exemplo (slide 05-7) facilita a percepção do que se ganha ou perde com códigos

corretores de erro. (o problema como um todo será feito em sala). Observe:

O código dado é protegido contra erro simples em cada um dos três primeiros bits

transmitidos, mas não para erros múltiplos ou para erro no quarto bit. Se p é a

probabilidade de um bit vir errado, q = 1 – p é a probabilidade dele não vir errado. Se

fossem 3 bits de dados com paridade:

Código vem perfeitamente certo com probabilidade q4

Código vem com um erro nos três primeiros bits: 4p.q3 (4 formas de 1 bit errado)

Probabilidade de não vir certo, NEM ser detectado o erro: 1 – (q4 + 4p.q

3) , que é o erro

residual, ou o erro que não pode ser corrigido.

Mas o que existe são códigos redundantes. Só é possível erro se o quarto bit vier errado:

error rate = 1 - q = 2%; erro residual = (há erro no quarto bit + há erro de qualquer tipo

nos 3 primeiros bits – há erros detectáveis nos 3 primeiros bits) = (p) + (1 – q3) – (3pq

2)

= 2.12%

O importante é perceber que reduziu o bit error À CUSTA de aumentar a

redundância (desperdiçou-se 12 códigos dentre 16 possíveis para reduzir o bit error),

apesar de estarmos agora transmitindo os códigos tão rápido quanto eles são produzidos.

Como este esquema é, em parte, corretor de erros, observe que o error rate por

código recebido é sinônimo de erro residual, ou seja, erro que não pode ser detectado

(ou corrigido).


RREEDDUUNNDDÂÂNNCCIIAA EE OOVVEERRHHEEAADD

Vamos sistematizar nosso raciocínio.

Seja a distribuição de bits de dados e de verificação como indicado no slide 05-

8. Pensemos que a necessidade é de apenas detectar 1 bit em falha.

Para todo código de (d + r) bits haverá (d + r) códigos que possam resultar em erro de 1

bit (compare e comprove!), portanto, dentre as 2d possíveis precisaremos (d + r + 1)

palavras (check bits) para protegê-lo contra erros de 1 bit, conseqüentemente, o número

total de palavras a enviar será:

(d + r + 1).2d

Por outro lado, o número de mensagens possíveis é: 2(d + r)

Então:

(d + r + 1) 2d

2(d + r)

.

logo:

(d + r + 1) 2r

Na tabela do slide 05-8 se encontram alguns tamanhos de dados com a

correspondente necessidade de check bits e também do overhead envolvido.


EExxeemmpplloo55: a) Qual o maior tamanho de dados protegidos para erros de 1 bit caso se use

7 check bits ?

b) Qual o code rate associado?

R: 120; 0.945

Diferente de paridade cujo poder de código é restrito (só detecta 1 bit errado!), o

código de Hamming permite corrigir erros de 1 bit. Nunca é demais lembrar que em

termos práticos este é o caso que interessa para comunicações onde não é possível ou

viável a retransmissão (por exemplo, NASA se comunicando com suas naves).



CCÓÓDDIIGGOO DDEE HHAAMMMMIINNGG

Trata-se de um código corretor de erros do tipo bloco linear. Os check bits

ocupam as posições de potência de 2 e calculam paridade par. A colocação dos bits se

dá a partir da esquerda para direita (acompanhe no slide 05-10). A lei de formação é a

seguinte: um bit da posição k é verificado pelos check bits que contribuam em potência

de 2 para o número k. A produção e transmissão na fonte, e a recepção e verificação no

destino estão indicados no slide 05-10, mostrando um exemplo de transmissão correta e

outro exemplo de transmissão com falha (slide 05-11).

Observe no slide 05-11 que se no mesmo exemplo anterior dois bits estão

errados (P2 = 0; X6 = 0), vamos obter na recepção:

C1 = 0 + 1 + 0 + 1 = 0 (LSB)

C2 = 0 + 1 + 0 + 1 = 0

C4 = 0 + 0 + 0 + 1 = 1 (MSB), então (100)BIN = (4)DEC, ou seja, vai nos dizer

erradamente na recepção que o bit 4 está errado!

Conclusão: O código só é válido para erros de 1 bit.


Picos de ruídos, ecos, “crosstalk” afetam uma transmissão de bits em seqüência.

Nas boas linhas telefônicas, por exemplo, a probabilidade de um bit errado é de 10-5

,

mas dado que um bit tem erro, a probabilidade que o próximo bit também tenha erro

sobe para 0.5!!!

EExxeemmpplloo 66: Suponha códigos de 1000 bits transmitidos por um canal com bit error de

10-6

. Verifique o overhead, usando Hamming e usando paridade.

R: 1,1% e 0.1%. (Talvez resolução em aula)OBS IMPORTANTE ÀS PAMPAS:

Com tráfego em rajadas, ambos (Hamming ou paridade) resultam inúteis! (por quê?)

Um truque para corrigir erros em rajadas com o código de Hamming consiste em

transmitir por colunas, restaurar a matriz original que agora, mesmo em presença de

erros em rajadas, só terá 1 erro por palavra (detalhes deste artifício fogem do escopo

deste curso. No entanto, além dos cursos desta matemática específica, aprofundar esta

análise de erro pode interessar a processamento de imagens, etc.


Vamos agora nos debruçar sobre o método de análise de erro mais popular para

transmissões pela Internet, o CRC, o Código de Redundância Cíclica.

Representação Polinomial:Presta-se a codificar uma palavra de dados de (n) bits em

um código de (n + k) bits, com vistas a preservar a integridade dos dados.

Operações são baseadas em aritmética módulo-2 com as seguintes propriedades:

aa)) soma, subtração – são operações equivalentes a OR-exclusivo.

bb)) divisão – similar à divisão binária, com a parte da subtração feita em módulo-2.

cc)) multiplicação – também similar, mas usando a característica: X + X = 0

(Ver também anexo Análise de Abrangência do Método Polinomial)

No slide 05-13 se mostra uma transmissão de dados de 3 bits que são convertidos em 4

bits pela multiplicação do polinômio (x + 1).

EExxeemmpplloo 77: Faça a operação (x + 1) + (x2 + x + 1) operando de três maneiras: por OR-

exclusivo, algebricamente e por propriedades de aritmética módulo-2. Compare.

R: 1 0 0; x2; x

2 (todas as maneiras dão o mesmo valor!)


CCRRCC

O próximo código que estudaremos é o CRC (Cyclic Redundance Code) que é

também um subconjunto de códigos lineares. É baseado na aritmética polinomial feita

em módulo 2 onde operações de soma e de subtração são idênticas (perceba que a soma

não tem carry e a subtração não tem borrow), a soma de um polinômio por ele mesmo

dá zero e podemos ainda definir as operações de multiplicação e de divisão. A

multiplicação de polinômios em módulo 2 é exemplificada no slide 05-13, onde

codificamos 3 bits de dados em 4 bits de código. O resultado é um código testador de

paridade com code rate de ¾.

Neste método, ambos, transmissor e receptor, concordam em relação ao

polinômio gerador G(x), contendo (r + 1) bits, onde r é o número de bits CRC

inseridos, e onde os bits de mais alta e mais baixa ordem são “1”.

Algoritmo CRC:

M(x) = polinômio inicial com m bits;

G(x) = código gerador (concordância entre RX e TX) com (r + 1) bits

Nestes termos, o algoritmo é implementado assim:

a) desloca M(x) de r posições à esquerda acrescentando zeros à direita.

b) divide xr M(x) por G(x) e obtém o resto R(x).

c) o código a transmitir será xr M(x) – R(x) = T(x). Na recepção: T(x)/G(x) = 0, caso a

mensagem não contenha erro; T(x)/G(x) 0, caso a mensagem contenha erro e o

resto dá indicação do número de bits invertidos, até o limite de r bits.

EExxeemmpplloo 88: Se o dado a ser transmitido é 1 0 1 1 1 0 e o polinômio gerador é 1 0 0 1,

aplique o algoritmo CRC e conclua o código transmitido.

R: 1 0 1 1 1 0 0 1 1

No slide 05-14 é feito um exemplo do cálculo da mensagem T(x) a ser

transmitida operando em binário. Possivelmente em aula faremos o mesmo usando


polinômios. Observe que o resultado T(x) deve ser divisível por G(x), polinômio

gerador que é conhecido tanto na transmissão, quanto na recepção.

A estrutura do CRC é mostrada no slide 05-14. Observe que multiplicar um

polinômio por 2k significa deslocar o código k vezes para a esquerda. Desta forma,

D * 2r XOR (R) produz a estrutura mostrada no mesmo slide.

Precisamos portanto determinar R tal que G divida D * 2r XOR R sem

apresentar resto, ou seja:

D * 2r XOR R = nGMultiplicando ambos os lados por (XOR R ):

{D * 2r XOR R} XOR R = nG XOR R , então:

{D * 2r XOR 0 = nG XOR R , então:

(D * 2r) = nG XOR R, agora se dividirmos D * 2

r por G o valor do resto será R, ou

seja:

RR == rreessttoo {{DD ** 22r //GG}}


Depois de aplicado um método de detecção de erro no receptor, pode ser o caso

de haver retransmissão de um quadro perdido ou inútil. Para isto é comum a

combinação de dois mecanismos: confirmações (ACK) e timeouts. As técnicas que

usam estes mecanismos para entrega confiável de quadros (ou pacotes, ou segmentos)

são chamadas ARQ (Automatic Repeat Request) e as duas principais que analisaremos

neste capítulo são: Parar-Esperar e Janela Deslizante.


A técnica Parar-Esperar pode ser feita via reconhecimentos positivos (ACK),

reconhecimento negativo (NACK) ou reconhecimento contínuo.

Métodos de reconhecimento positivo ou negativo apresentam os inconvenientes:

1. Duplicação de quadros: o receptor recebe quadros duplicados caso o ACK chegue ao

emissor após expirar o tempo, e quando o reconhecimento é descartado por causa de

erro;

2. Pouca eficiência: para cada quadro transmitido circula outro de controle em sentido

inverso.

Para meios muito confiáveis (fibras óticas, por exemplo) o reconhecimento contínuo

é o mais sensato; para meios ruidosos (meios não guiados, por exemplo)

reconhecimento positivo é o mais sensato; para comunicação em grupo (multicast) o

mais sensato é reconhecimento negativo acoplado a alguma estratégia de localização da

recuperação da falha para não gerar excesso de tráfego de controle e o esmagamento do

emissor (problema conhecido como implosão de feedback). Este assunto voltará a ser

debatido no capítulo da camada de transporte em Redes 2.


A principal limitação do algoritmo Parar-Esperar é que ele permite que o

emissor tenha apenas um quadro pendente no enlace a cada vez, o que pode ser muito

abaixo da capacidade do enlace (produto retardo-largura de banda é baixo).

O Reconhecimento Contínuo abre chance para uma estratégia mais elaborada,

chamada Janela Deslizante, onde, após negociação entre receptor e transmissor,

quadros são enviados pelo emissor sem necessidade de reconhecimentos, até o limite da

janela. Quando o receptor preenche sua janela de recepção, ele reconhece toda uma

janela. O emissor ao receber o reconhecimento da janela transmitida pode finalmente

liberar os quadros armazenados em buffer, movendo a janela para os quadros seguintes.

Os slides 05-17 até 05-23 (tem esta forma para dar uma dinâmica da ação do método em

aula) tratam desta técnica em etapas parciais e sucessivas.

Portanto, a primeira função da Janela Deslizante é entregar quadro de modo

confiável com o aumento do grau de utilização do enlace. A segunda função da Janela

Deslizante é preservar a ordem que os quadros são transmitidos. O terceiro papel da

Janela Deslizante é oferecer um mecanismo de realimentação que permita o emissor

cadenciar sua transmissão (isto é chamado Controle de Fluxo).


Mais importante que aplicar técnicas de retransmissão no nível do enlace

(escopo local) será aplica-las em um escopo global. Por isso, este assunto também

voltará a ser debatido no capítulo da camada de transporte, quando analisarmos o

protocolo TCP.

EExxeemmpplloo 88: Analise a limitação em termos de utilização do enlace da técnica Esperar-

Parar considerando um enlace de 1,5 Mbps com RTT = 45 ms e quadros de 1 MB.

R: 12.5 %

Perceba que neste capítulo estudamos formas de tratar erro no nível das camadas

mais baixas de redes. No mundo das redes este estudo foi perdendo importância com a

melhoria tecnológica dos meios guiados, particularmente fibra ótica. Registramos aqui

que com o impulso observado nas redes móveis sem fio, todo este estudo voltou à baila.


Deve ficar claro que existirão outras razões de erro, por exemplo, aqueles

colocados pelos protocolos ou pela topologia de redes. Tratar erros em redes é

atribuição de todas as camadas, porém, além deste tratamento no nível físico e de

enlace, sobressai o tratamento a ser dado na camada de transporte (com o controle de

fluxo e de congestionamento e as questões de confiabilidade na entrega), mas isto é

assunto para outro capítulo ...

Arquivos de apoio:

Para teoria de erros de transmissão, err_control.pdf

Para teoria de códigos CRC, crc_theory.pdf


ANEXO: Análise de Abrangência do Método Polinomial

(este anexo desenvolve o tema, mas não é parte integrante do curso. Deve ser visto

como acréscimos a quem se interessa pelo tema)

Seja T(x) transmitido; T(x) + R(x) recebido.

a) se T’(x) = T(x) , então E(x) = 0 0

b) se T’(x) T(x) , então (T(x) + E(x))/G(x) = T(x)/ G(x) + E(x)/G(x) = E(x)/G(x), ou

seja, os erros que contém G(x) são ignorados, todos os outros detectados.

Um erro de transmissão fica sem ser detectado somente se o resto da divisão

E(x)/G(x) for zero.

Se E(x) é de um grau mais baixo que G(x), a divisão deixa sempre resto, o que

significa que rajadas de erros de comprimento r ou menos são detectáveis.

Se E(x) = xi i determina o bit errado. Se G(x) contiver dois ou mais termos,

ele não divide exatamente E(x), ou seja, todos os erros simples serão detectados.

Se E(x) = xi + x

j = x

i (x

i - j + 1), a condição de erros duplos serem detectados é

que G(x) não divida (xk + 1) para k até um máximo valor de i – j (na prática, até o maior

valor do quadro).

Se houver um número ímpar de bits errados, E(x) vai conter um número ímpar

de termos. Como não existe um polinômio com número ímpar de termos, que tenha (x +

1) como fator no sistema módulo 2, ao ser (x + 1) um fator de G(x) , isto implica que

TODO NÚMERO ÍMPAR DE ERROS SERÁ DETECTADO. A prova disto pode

ser vista no problema 5.4 da lista de exercícios.

Conclusões:

1) Padrões internacionais de CRC: G(x) com 8-, 12-, 16-, 32-bits, como:

ATM - CRC-8 (para cabeçalho de 5 bytes)

Link IEEE - CRC-32

2) Cada um dos padrões de CRC pode detectar rajadas de erros de menos que (r + 1)

bits e qualquer número ímpar de bits.

Além do mais, sob certas hipóteses, uma rajada maior que (r + 1) bits é

detectada com probabilidade 1 – 0.5r.


Prova:

Com (m + r) bits transmitidos existem 2m+r possíveis padrões de erros. O número de

múltiplos inteiros de G(x) de grau r na palavra de código de comprimento (m + r) é

igual a 2m

. Cada múltiplo pode ser considerado como uma soma infinita de m fatores,

onde cada fator é obtido pelo deslocamento para a esquerda do gerador polinomial na

palavra de dados, podendo, portanto, ser deslocado m posições. Cada um destes m

fatores estará presente ou ausente do múltiplo final, dado os 2m

possíveis múltiplos. Isto

significa que a fração 2m

/2m + r

= 1/2r de todos os erros aleatórios são perdidos.

Alguns casos:

1) r = 16 10-5

de todos os padrões de erros são perdidos.

2) No exercício 5.2 da lista, se G(x) = x3 + 1; r = 3, então:

a) Detecta rajadas de até 3 bits;

b) Detecta qualquer número ímpar de erros;

c) Probabilidade de detectar rajada de 4 bits: 1 – 1/23 = 87.5%

Documents

5- Tratamento de Erros v7falencar/arquivos-flavio-uerj/redes1/redes1-5-erros-v7.pdfA taxa de código de um método corretor é geralmente mais baixa que a de um método detector, de