Resumo: Código de Correção de Erros em Computadores

Paridade Combinada = Nesse esquema além da paridade de caracter, instala-se uma paridade para o bloco de caracteres, permitindo-se a detecção e recuperação de 1 erro por caracter , a detecção de dois erros por caracter, e havendo falha de detecção no caso de erros quádruplos. A paridade vertical (VRC), consiste em acrescentar um bit de paridade para cada caracter transmitido. Enquanto que a paridade longitudinal (LRC), consiste em acrescentar um bit de paridade para cada nível de bit dentro do byte de um bloco, inclusive para o bit de paridade vertical. À utilização desses dois métodos (VRC + LRC) em conjunto, dá-se o nome de Paridade Combinada. A paridade combinada possibilita a formação do bloco de checagem do caracter (BCC), obtido de todos os bits formados pelo VRC e LRC. Quando a mensagem chegar ao destino, o equipamento receptor calcula um novo BCC a partir dos bits recebidos e compara-o com o BCC recebido ao final da mensagem (que foi calculado pelo equipamento transmissor). Ocorrendo igualdade entre esses BCCs, a mensagem recebida será considerada correta, sendo aceita e processada. Caso contrário, a mensagem será considerada incorreta, pedindo-se assim uma retransmissão.

Echoplex

Echoplex é uma técnica no qual o receptor envia de volta (ou ecoa) cada caracter à medida que são recebidos. Quando um caracter ecoado é recebido em erro pelo remetente original, não é possível saber se os dados foram recebidos corretamente no destino e misturados no caminho de retorno, ou se eles foram recebidos com erro pelo receptor. De qualquer forma, alguma informação de erro chega ao transmissor.

CRC – Cyclic Redundancy Checking

CRC ou método polinomial de detecção de erros onde, na transmissão, os dados de informação a serem transmitidos são transformados em um polinômio D(x) em função dos bits. O polinômio D(x) é multiplicado pelo termo de maior grau de um polinômio gerador G(x). O resultado desta multiplicação será um novo polinômio D'(x) que será dividido pelo polinômio gerador G(x). O resto desta divisão R(x) será enviado ao término da transmissão de D(x). Dependendo do tipo de protocolo utilizado, esse “resto” leva diferentes nomes (BCC no protocolo BSC e FCS no protocolo X.25). Na recepção, os dados recebidos serão divididos pelo mesmo polinômio gerador G(x). Se o resto desta divisão for igual a zero, significa que não houve erros na transmissão; caso contrário, foi detectado um erro na transmissão e mensagem deve ser reenviada.

Paridade de bloco (Horizontal Redundancy Checking) – HRC

Aqui é adicionado um caractere ao fim de um bloco de comprimento fixo de

caracteres, onde cada bit é o resultado da aplicação da função ? sobre os bits de

posição correspondente dos caracteres do bloco. Se houver uma inversão de dois bits em um caractere não detectada pela VRC, ela será pela HRC.

Fonte: http://www.inf.ufsc.br/~jef/ApostilaRedes.pdf

Código de Hamming: O código de Hamming é um código de detecção, isto é, permite não apenas detectar erro de um bit, mas também a localização do bit errado. Considere uma palavra de 8 bits. Numere os bits de m1m2m3m4m5m6m7m8. A esse dado de 8 bits vamos acrescentar 4 bits adicionais, formando o código de Hamming de 12 bits. Vejamos como podemos formar o código de Hamming. Numere os bits do código de Hamming como sendo:

x1x2x3x4x5x6x7x8x9x10x11x12

Sejam

x3 = m1

x5 = m2

x6 = m3

x7 = m4

x9 = m5

x10 = m6

x11 = m7

x12 = m8

Os 4 bits adicionais x1; x2; x4 e x8 são assim calculados, onde representa a operação ou exclusivo:

x1 = x3 _ x5 _ x7 _ x9 _ x11

x2 = x3 _ x6 _ x7 _ x10 _ x11

x4 = x5 _ x6 _ x7 _ x12

x8 = x9 _ x10 _ x11 _ x12

Observe que, dados bits A e B, a operação ou exclusivo C = A _ B calcula o bit

paridade (par) dos bits dados.

Agora suponha que esses 12 bits são lidos como sendo:

y1y2y3y4y5y6y7y8y9y10y11y12

Se não houver erro, então cada yi é igual seu respectivo xi.

1 Se houver erro em um bit apenas, é possível detectar esse erro e corrigi-lo.

Para isso fazemos o seguinte cálculo de 4 bits, denominados k1; k2; k3 e k4:

k1 = y1 _ y3 _ y5 _ y7 _ y9 _ y11

k2 = y2 _ y3 _ y6 _ y7 _ y10 _ y11

k3 = y4 _ y5 _ y6 _ y7 _ y12

k4 = y8 _ y9 _ y10 _ y11 _ y12

Se k1 = k2 = k3 = k4 = 0, então não há erro.

Senão o número binário codificado pelos 4 bits,

k4k3k2k1

determina a posição do bit errado. Isto é, se

k4k3k2k1 = 0111

então o bit y7 está errado.

Referência:

Vera Pless. Introduction to the theory of error-correcting codes. New York : Wiley, 1982, ISBN 0471086843

 

O código de Reed-Salomon é uma forma de FEC (Forward Correction Error) e é utilizada no ADSL para trazer resiliência adicional contra o ruído da linha [3] [4] [6] [8].

O código de Reed-Solomon é um subtipo do código cíclico BCH (Bose-Chaudhuri-Hocquenghem) que foi desenvolvido para executar correção de erros múltiplos, é não binário (mulsímbolo). Tome-se como exemplo um símbolo b-bit, onde tem-se q=2b símbolos possíveis (codewords – palavras código). Atribuindo um valor para b=8 bits (da literatura, um código comum), o que apresenta 256 símbolos possíveis. Um código de Reed-Solomon (n,k) é também um código de bloco, onde em k símbolos de informação que estão inseridos no codificador, n símbolos de palavra-código aparecem na saída. Neste tipo de código, os símbolos de palavra-código estão limitados como sendo, em sua maioria, n<=q+1 símbolos de comprimento (apesar desta relação de n<=q+1 ser normalmente usada como premissa de projeto). (Obs: Códigos Reed Solomon podem ser estendidos para n = q e n = q +1 em comprimento médio) [5].

Por exemplo, se forem utilizados grupos de 6 bits (64k), códigos de Reed Solomon podem ser gerados. Um código Reed Solomon (64,40) consistiria de palavras código de 64 X 6 = 384 bits, cada uma contendo 240 bits de informação, tratados como 40 símbolos de 6 bits.  No código (64,40) descrito anteriormente, temos comprimento de palavras-código de q=26=64 bit. A fração de possíveis palavras-código de 64 símbolos de comprimento é utilizada como palavra-código se 64-24 = 2-144. O que demonstra a grande capacidade de detecção e correção de erro, neste caso particular, pode-se corrigir erros de até 12 símbolos.

Quantos bits seriam necessários para codificarmos um sinal que tenha 16 estados diferentes

São 4 bits:

 

0000 – 1o. estado

0001 – 2o.

0010 – 3o.

0011 – 4o.

0100 – 5o.

0101 – 6o.

0110 – 7o.

0111 – 8o.

1000 – 9o.

1001 – 10o.

1010 – 11o.

……

1111 – 16o.

com 8 bits pode-se ter até 256 estados e com 16 bits são 64353 (64k)

Usando a paridade par, qual o bit que deve ser acrescido aos bits 01001001 a ser transmitido

Quando se usa paridade par e a quantidade de bits 1 for PAR o bit de paridade será 1 senão será 0. O raciocínio é o mesmo para a paridade impar, se a quantidade de 1 for IMPAR o bit de paridade será 1 senão será 0, assim no exercício a cadeia de bits é 01001001, existem 3 bits 1 logo é um quantidade impar de 1s, como a paridade desejada é PAR o bit de paridade é “0” e o caracter a ser transmitido será 010010010. Portanto é “0” .

Qual o modo de transmissão existente diante de um jogo de futebol televisionado?

Modo de transmissão SIMPLEX, o sentido do fluxo de dados é único, isto é, o dispositivo  A  será sempre o transmissor e o dispositivo B o receptor.