51 pág.
Pré-visualização | Página 1 de 2
Sistemas Embarcados II Aula 2 – Códigos de Detecção e Correção de Erros Prof. Fernando Luiz Trazzi Junior Conteúdo da aula UNIDADE 2: Segurança da veracidade dos dados: Códigos de correção e códigos de validação 2.1 Introdução a segurança e veracidade dos dados em sistemas embarcados 2.2 Código de correção de erros 2.3 Checksum 2.4 CRC - Cyclic Redundancy Check 2.5 Código de Hamming Introdução Falha, Erro e Defeito Confiabilidade dos sistemas Os sistemas embarcados devem oferecer confiabilidade no seu funcionamento, evitando o prejuízo das pessoas que os utilizam e do próprio equipamento físico Um sistema de computação funciona através da transferência de informação desde o nível de circuito integrados até aos níveis mais altos, como por exemplo gravação no disco ou comunicação entre computadores. Está sujeito a diversos erros, como os causados por interferências electromagnéticas, envelhecimento de componentes, curto-circuitos, ... Erros São inevitáveis em qualquer sistema de comunicação real; A distribuição dos erros não é homogênea: bits isolados ou em “rajadas” (bursts) de erros, com 8 ou mais bits sucessivos errados; Deve-se levar em conta o meio físico de transmissão de dados, para incluir maior ou menor redundância na transmissão, a fim de garantir que a informação recebida seja confiável. Erros Possíveis abordagens no tratamento de erros: – Ignorar o erro; – Eco (transmissão à origem de reflexos dos dados recebidos); – Sinalizar o erro; – Detectar e solicitar a retransmissão em caso de erro; – Detectar e corrigir os erros na recepção de forma automática. Código de Detecção de Erros Detectar um erro é uma tarefa mais simples do que detectar e corrigir; Nem sempre é possível solicitar uma retransmissão; Todos os métodos utilizam a inserção de bits extras; – Esses bits podem ser obtidos a partir da informação original e o receptor recalcula os bits extras Código de Detecção de Erros Um método ineficiente mas muito utilizado para detectar erros é a Paridade; Outro método é o checksum Um método mais eficiente é o uso de um código polinomial ou CRC (Cyclic Redundancy Check); Código de Detecção e Correção de Erros Códigos de correção podem recuperar o dado original a partir do código com erros; Consistem na criação de códigos extras que detectam situações inválidas mas que mantém a identidade do dado original; O conceito mais básico e mais importante desses códigos é a distância de Hamming, utilizada para a criação de códigos de correção. Redundância de um código Quantidade total de bits transmitidos n = m+r Overhead: r/m Palavras válidas Seja um código binário com m bits, então existem 2m mensagens válidas São agregados r bits para a verificação de erros, resultando uma mensagem com: n = m + r bits – 2m+r palavras possíveis – 2m palavras são válidas – 2m(2r-1) palavras são inválidas O sistema só gera palavras válidas. Logo, se surgir alguma palavra inválida, trata-se de um erro! Detecção de Erros - Paridade Paridade – Consiste basicamente no ato do transmissor adicionar um bit de redundância após um determinado número de bits Número par de 1’s → paridade par Número ímpar de 1’s → paridade impar Ex.: 000, 011, 101, 110 são mensagens transmitidas sem erro, tendo em conta que o último bit é o de paridade Detecção de Erros - Paridade Exemplo: Deseja-se transmitir a seguinte sequência de bits: 1000001 Deve-se inserir o bit P de paridade: 1000001P → número par de 1’s → P = 0 Portanto, a sequência de bits transmitida é: 10000010 O receptor calcula a paridade da mensagem e compara-a com o bit P recebido: P = paridade → transmissão correta Detecção de Erros - Paridade Este processo pode ser vulnerável se houver mais do que um erro, permitindo assim que este passe até ao destino sem ser identificado. No exemplo, se o receptor recebesse a sequência: 11010010 O bit de paridade seria 0, mas o erro existe Detecção de Erros - Paridade Tem capacidade de detectar número ímpar de erros Não corrige erro, somente detecta Detecção de Erros – Paridade Exercício Calcular o bit de paridade das seguintes sequências de bits: a) 10010010 b) 11001001 c) 01010001 d) 11101110 Detecção de Erros – Paridade Exercício Calcular o bit de paridade das seguintes sequências de bits: a) 100100101 b) 110010010 c) 010100011 d) 111011100 Detecção de Erros - Paridade Bidimensional Generalização bidimensional do esquema de paridade de bit único. O receptor não somente pode detectar que ocorreu um erro de um bit único, como identificar o bit e corrigi-lo. A paridade 2-dim detecta todos os erros de 1, 2 e 3 bits, e a maioria dos erros de 4 bits. – 2 erros na mesma coluna e 2 erros na mesma linha não são detectados Detecção de Erros - Paridade Bidimensional Detecção de Erros - Paridade Bidimensional Erro de 4 bits não detectável: Detecção de Erros – Paridade Bidimensinal – Exercício Deseja-se transmitir 4 bytes de dados. Calcular os bits de paridade bidimensional 10010010 11001001 01010001 11101110 Detecção de Erros – Paridade Bidimensinal – Exercício Deseja-se transmitir 4 bytes de dados. Calcular os bits de paridade bidimensional 100100101 110010010 010100011 111011100 111001000 Detecção de Erros – Paridade Bidimensinal – Exercício Caso o receptor receba a seguinte sequência de bits com erro, como seria feita a correção? 100100101 110110010 010100011 111011100 111001000 Detecção de Erros - Checksum A ideia é somar todas as palavras que são transmitidas e depois transmitir o resultado daquela soma (checksum) junto com as palavras. Se quaisquer dos dados transmitidos, incluindo o checksum, sofrerem algum erro, então, no receptor, o resultado da operação soma não será correto. Método relativamente simples de detecção de erros Utilizado na transmissão de dados pela internet Basicamente 2 métodos para encontrar o checksum: – Soma propriamente dita – Ou-Exclusivo entre bits Detecção de Erros - Checksum Método de soma: 1) Realiza-se a soma binária de uma sequência de palavras 2) O resultado da soma (checksum) é invertido e transmitido junto com a sequência de palavras 3) O receptor soma todas palavras, incluindo o checksum. O resultado deve ser uma sequência de 1's. Caso contrário, há um erro na transmissão. Detecção de Erros – Checksum Exercício Dada a sequência de 3 bytes abaixo, calcule o checksum pelo método da soma: 10011000 00011001 11000011 Checksum: A sequência abaixo foi recebida. Como o receptor verifica se está correta? 10011000 01011001 11000011 10001011 Detecção de Erros – Checksum Exercício Dada a sequência de 3 bytes abaixo, calcule o checksum pelo método da soma: 10011000 00011001 11000011 Checksum: 10001011 (lembrar de inverter o resultado da soma antes de enviar a mensagem) A sequência abaixo foi recebida. Como o receptor verifica se está correta? 10011000 01011001 11000011 10001011 Soma os 4 bytes. Se resultado igual a 11111111, mensagem sem erro. Neste caso, o resultado é diferente, portanto há erro. Detecção de Erros - Checksum Método de XOR: 1) Realiza-se a operação XOR entre os bits que estão na mesma posição de todas as palavras 2) O resultado da operação (checksum) é transmitido junto com a sequência de palavras 3) O receptor faz o XOR de todas palavras, incluindo o checksum. O resultado deve ser uma sequência de 0's. Caso contrário, há um erro na transmissão.
