Detecção e correção de erros - Error detection and correction

Para limpar os erros de transmissão introduzidos pela atmosfera da Terra (à esquerda), os cientistas de Goddard aplicaram a correção de erros Reed-Solomon (à direita), que é comumente usada em CDs e DVDs. Os erros típicos incluem pixels ausentes (branco) e sinais falsos (preto). A faixa branca indica um breve período em que a transmissão foi pausada.

Na teoria da informação e teoria da codificação com aplicações em ciência da computação e telecomunicações , a detecção e correção de erros ou controle de erros são técnicas que permitem a entrega confiável de dados digitais através de canais de comunicação não confiáveis . Muitos canais de comunicação estão sujeitos a ruído de canal e, portanto, podem ser introduzidos erros durante a transmissão da fonte para um receptor. As técnicas de detecção de erros permitem detectar tais erros, enquanto a correção de erros permite a reconstrução dos dados originais em muitos casos.

Definições

A detecção de erros é a detecção de erros causados ​​por ruído ou outras deficiências durante a transmissão do transmissor para o receptor.

A correção de erros é a detecção de erros e a reconstrução dos dados originais sem erros.

História

Na antiguidade clássica, os copistas da Bíblia Hebraica eram pagos por seu trabalho de acordo com o número de pontos (versos). Como os livros em prosa da Bíblia dificilmente eram escritos em pontos, os copistas, para estimar a quantidade de trabalho, tinham que contar as letras. Isso também ajudou a garantir a precisão na transmissão do texto com a produção de cópias subsequentes. Entre os séculos 7 e 10 dC, um grupo de escribas judeus formalizou e expandiu isso para criar a Masorá Numérica para garantir a reprodução precisa do texto sagrado. Incluía contagens do número de palavras em uma linha, seção, livro e grupos de livros, anotando o ponto do meio de um livro, estatísticas de uso de palavras e comentários. Os padrões tornaram-se tais que um desvio mesmo em uma única letra de um rolo da Torá era considerado inaceitável. A eficácia de seu método de correção de erros foi verificada pela precisão da cópia ao longo dos séculos, demonstrada pela descoberta dos Manuscritos do Mar Morto em 1947-1956, datando de cerca de 150 aC-75 dC.

O desenvolvimento moderno de códigos de correção de erro é creditada a Richard Hamming em 1947. A descrição do código de Hamming apareceu em Claude Shannon 's A Teoria Matemática da Comunicação e foi rapidamente generalizada por Marcel JE Golay .

Introdução

Todos os esquemas de detecção e correção de erros adicionam alguma redundância (ou seja, alguns dados extras) a uma mensagem, que os receptores podem usar para verificar a consistência da mensagem entregue e para recuperar dados que foram determinados como corrompidos. Os esquemas de detecção e correção de erros podem ser sistemáticos ou não sistemáticos. Em um esquema sistemático, o transmissor envia os dados originais e anexa um número fixo de bits de verificação (ou dados de paridade ), que são derivados dos bits de dados por algum algoritmo determinístico . Se apenas a detecção de erros for necessária, um receptor pode simplesmente aplicar o mesmo algoritmo aos bits de dados recebidos e comparar sua saída com os bits de verificação recebidos; se os valores não corresponderem, ocorreu um erro em algum ponto durante a transmissão. Em um sistema que usa um código não sistemático, a mensagem original é transformada em uma mensagem codificada que transporta as mesmas informações e que possui pelo menos tantos bits quanto a mensagem original.

Um bom desempenho de controle de erros requer que o esquema seja selecionado com base nas características do canal de comunicação. Os modelos de canal comuns incluem modelos sem memória onde os erros ocorrem aleatoriamente e com uma certa probabilidade, e modelos dinâmicos onde os erros ocorrem principalmente em rajadas . Consequentemente, um erro de detecção e os códigos de correcção podem ser distinguidos geralmente entre -aleatória-erro detecção / correcção de e -erro explosão de detecção / correcção . Alguns códigos também podem ser adequados para uma mistura de erros aleatórios e erros de burst.

Se as características do canal não podem ser determinadas, ou são altamente variáveis, um esquema de detecção de erro pode ser combinado com um sistema para retransmissões de dados errôneos. Isso é conhecido como solicitação de repetição automática (ARQ) e é mais usado na Internet. Uma abordagem alternativa para o controle de erros é a solicitação de repetição automática híbrida (HARQ), que é uma combinação de ARQ e codificação de correção de erros.

Tipos de correção de erros

Existem três tipos principais de correção de erros.

Solicitação de repetição automática (ARQ)

O pedido de repetição automática (ARQ) é um método de controle de erro para transmissão de dados que faz uso de códigos de detecção de erros, mensagens de confirmação e / ou confirmação negativa e tempos limite para obter uma transmissão de dados confiável. Uma confirmação é uma mensagem enviada pelo receptor para indicar que recebeu corretamente um quadro de dados .

Normalmente, quando o transmissor não recebe a confirmação antes de ocorrer o tempo limite (ou seja, dentro de um período de tempo razoável após o envio do quadro de dados), ele retransmite o quadro até que seja recebido corretamente ou o erro persista além de um número predeterminado de retransmissões .

Três tipos de protocolos ARQ são Stop-and-wait ARQ , Go-Back-N ARQ e Selective Repeat ARQ .

O ARQ é apropriado se o canal de comunicação tiver capacidade variável ou desconhecida , como é o caso da Internet. No entanto, o ARQ requer a disponibilidade de um canal traseiro , resulta em latência possivelmente aumentada devido a retransmissões e requer a manutenção de buffers e temporizadores para retransmissões, o que, no caso de congestionamento da rede, pode sobrecarregar o servidor e a capacidade geral da rede.

Por exemplo, o ARQ é usado em links de dados de rádio de ondas curtas na forma de ARQ-E ou combinado com multiplexação como ARQ-M .

Continue Correção de Erro

A correção de erros de encaminhamento (FEC) é um processo de adição de dados redundantes , como um código de correção de erros (ECC), a uma mensagem para que ela possa ser recuperada por um receptor mesmo quando houver vários erros (até a capacidade do código ser usados) foram introduzidos, seja durante o processo de transmissão, seja no armazenamento. Uma vez que o receptor não precisa pedir ao remetente a retransmissão dos dados, um backchannel não é necessário na correção de erros de encaminhamento e, portanto, é adequado para comunicação simplex , como a radiodifusão . Os códigos de correção de erros são freqüentemente usados ​​na comunicação da camada inferior , bem como para armazenamento confiável em mídia como CDs , DVDs , discos rígidos e RAM .

Os códigos de correção de erros geralmente são diferenciados entre códigos convolucionais e códigos de bloco :

O teorema de Shannon é um teorema importante na correção direta de erros e descreve a taxa máxima de informação na qual a comunicação confiável é possível em um canal que tem uma certa probabilidade de erro ou relação sinal-ruído (SNR). Este limite superior estrito é expresso em termos da capacidade do canal . Mais especificamente, o teorema afirma que existem códigos tais que, com o aumento do comprimento de codificação, a probabilidade de erro em um canal discreto sem memória pode ser arbitrariamente pequena, desde que a taxa de código seja menor do que a capacidade do canal. A taxa de código é definida como a fração k / n de k símbolos de origem e n símbolos codificados.

A taxa de código máxima real permitida depende do código de correção de erros usado e pode ser menor. Isso porque a prova de Shannon foi apenas de natureza existencial e não mostrou como construir códigos que sejam ótimos e tenham algoritmos de codificação e decodificação eficientes.

Esquemas híbridos

O ARQ híbrido é uma combinação de ARQ e correção de erros direta. Existem duas abordagens básicas:

  • As mensagens são sempre transmitidas com dados de paridade FEC (e redundância de detecção de erro). Um receptor decodifica uma mensagem usando as informações de paridade e solicita a retransmissão usando ARQ apenas se os dados de paridade não forem suficientes para a decodificação bem-sucedida (identificada por meio de uma verificação de integridade com falha).
  • As mensagens são transmitidas sem dados de paridade (apenas com informações de detecção de erro). Se um receptor detectar um erro, ele solicita informações FEC do transmissor usando ARQ e as usa para reconstruir a mensagem original.

A última abordagem é particularmente atraente em um canal de eliminação ao usar um código de eliminação sem taxa .


Esquemas de detecção de erros

A detecção de erros é mais comumente realizada usando uma função hash adequada (ou especificamente, uma soma de verificação , verificação de redundância cíclica ou outro algoritmo). Uma função hash adiciona uma tag de comprimento fixo a uma mensagem, o que permite que os destinatários verifiquem a mensagem entregue recalculando a tag e comparando-a com a fornecida.

Existe uma grande variedade de designs de função hash diferentes. No entanto, alguns são de uso particularmente difundido por causa de sua simplicidade ou adequação para detectar certos tipos de erros (por exemplo, o desempenho da verificação de redundância cíclica na detecção de erros de burst ).

Codificação de distância mínima

Um código de correção de erros aleatório com base na codificação de distância mínima pode fornecer uma garantia estrita sobre o número de erros detectáveis, mas pode não proteger contra um ataque de pré - imagem .

Códigos de repetição

Um código de repetição é um esquema de codificação que repete os bits em um canal para obter uma comunicação sem erros. Dado um fluxo de dados a ser transmitido, os dados são divididos em blocos de bits. Cada bloco é transmitido algum número predeterminado de vezes. Por exemplo, para enviar o padrão de bits "1011", o bloco de quatro bits pode ser repetido três vezes, produzindo assim "1011 1011 1011". Se este padrão de doze bits foi recebido como "1010 1011 1011" - onde o primeiro bloco é diferente dos outros dois - ocorreu um erro.

Um código de repetição é muito ineficiente e pode estar sujeito a problemas se o erro ocorrer exatamente no mesmo lugar para cada grupo (por exemplo, "1010 1010 1010" no exemplo anterior seria detectado como correto). A vantagem dos códigos de repetição é que eles são extremamente simples e, de fato, são usados ​​em algumas transmissões de estações de números .

Bit de paridade

Um bit de paridade é um bit adicionado a um grupo de bits de origem para garantir que o número de bits definidos (ou seja, bits com valor 1) no resultado seja par ou ímpar. É um esquema muito simples que pode ser usado para detectar um único ou qualquer outro número ímpar (ou seja, três, cinco, etc.) de erros na saída. Um número par de bits invertidos fará com que o bit de paridade pareça correto, mesmo que os dados estejam errados.

Os bits de paridade adicionados a cada "palavra" enviada são chamados de verificações de redundância transversal , enquanto aqueles adicionados no final de um fluxo de "palavras" são chamados de verificações de redundância longitudinal . Por exemplo, se cada uma de uma série de "palavras" de bits m tiver um bit de paridade adicionado, mostrando se havia um número par ou ímpar de unidades nessa palavra, qualquer palavra com um único erro será detectada. Não será conhecido onde está o erro, entretanto. Se, além disso, após cada fluxo de n palavras, uma soma de paridade é enviada, cada bit mostra se houve um número ímpar ou par de unidades nessa posição de bit enviada no grupo mais recente, a posição exata do erro pode ser determinado e o erro corrigido. Esse método só tem garantia de eficácia, no entanto, se não houver mais de 1 erro em cada grupo de n palavras. Com mais bits de correção de erros, mais erros podem ser detectados e, em alguns casos, corrigidos.

Existem também outras técnicas de agrupamento de bits.

Checksum

A soma de verificação de uma mensagem é uma soma aritmética modular de palavras de código de mensagem de um comprimento de palavra fixo (por exemplo, valores de byte). A soma pode ser negada por meio de uma operação de complemento de uns antes da transmissão para detectar mensagens não intencionais de zero.

Os esquemas de checksum incluem bits de paridade, dígitos de verificação e verificações de redundância longitudinal . Alguns esquemas de checksum, como o algoritmo Damm , o algoritmo Luhn e o algoritmo Verhoeff , são projetados especificamente para detectar erros comumente introduzidos por humanos ao escrever ou lembrar números de identificação.

Verificação de redundância Cíclica

Uma verificação de redundância cíclica (CRC) é uma função hash não segura projetada para detectar alterações acidentais em dados digitais em redes de computadores. Não é adequado para detectar erros introduzidos de forma maliciosa. É caracterizada pela especificação de um polinômio gerador , que é usado como divisor em uma divisão longa do polinômio sobre um corpo finito , tomando os dados de entrada como dividendo . O restante se torna o resultado.

Um CRC tem propriedades que o tornam adequado para detectar erros de burst . Os CRCs são particularmente fáceis de implementar em hardware e, portanto, são comumente usados ​​em redes de computadores e dispositivos de armazenamento, como unidades de disco rígido .

O bit de paridade pode ser visto como um CRC de 1 bit de caso especial.

Função hash criptográfica

A saída de uma função hash criptográfica , também conhecida como resumo de mensagem , pode fornecer fortes garantias sobre a integridade dos dados , sejam as alterações dos dados acidentais (por exemplo, devido a erros de transmissão) ou introduzidas de forma maliciosa. Qualquer modificação nos dados provavelmente será detectada por meio de um valor hash incompatível. Além disso, dado algum valor de hash, normalmente é inviável encontrar alguns dados de entrada (além do fornecido) que produzirão o mesmo valor de hash. Se um invasor puder alterar não apenas a mensagem, mas também o valor do hash, um hash com chave ou código de autenticação de mensagem (MAC) pode ser usado para segurança adicional. Sem saber a chave, não é possível para o invasor calcular fácil ou convenientemente o valor de hash com chave correto para uma mensagem modificada.

Código de correção de erro

Qualquer código de correção de erros pode ser usado para detecção de erros. Um código com distância de Hamming mínima , d , pode detectar até d - 1 erros em uma palavra de código. Usar códigos de correção de erros baseados em distância mínima para detecção de erros pode ser adequado se um limite estrito do número mínimo de erros a serem detectados for desejado.

Códigos com distância de Hamming mínima d = 2 são casos degenerados de códigos de correção de erros e podem ser usados ​​para detectar erros únicos. O bit de paridade é um exemplo de código de detecção de erro único.

Formulários

Os aplicativos que exigem baixa latência (como conversas telefônicas) não podem usar a solicitação de repetição automática (ARQ); eles devem usar correção de erro direta (FEC). No momento em que um sistema ARQ descobrir um erro e retransmiti-lo, os dados reenviados chegarão tarde demais para serem utilizáveis.

Os aplicativos em que o transmissor esquece imediatamente as informações assim que são enviadas (como a maioria das câmeras de televisão) não podem usar o ARQ; eles devem usar FEC porque quando ocorre um erro, os dados originais não estão mais disponíveis.

Os aplicativos que usam ARQ devem ter um canal de retorno ; aplicativos sem canal de retorno não podem usar ARQ.

Os aplicativos que exigem taxas de erro extremamente baixas (como transferências de dinheiro digital) devem usar ARQ devido à possibilidade de erros incorrigíveis com FEC.

A engenharia de confiabilidade e inspeção também faz uso da teoria dos códigos de correção de erros.

Internet

Em uma pilha TCP / IP típica , o controle de erros é realizado em vários níveis:

  • Cada quadro Ethernet usa detecção de erro CRC-32 . Os quadros com erros detectados são descartados pelo hardware do receptor.
  • O cabeçalho IPv4 contém uma soma de verificação protegendo o conteúdo do cabeçalho. Os pacotes com somas de verificação incorretas são descartados na rede ou no receptor.
  • A soma de verificação foi omitida do cabeçalho IPv6 para minimizar os custos de processamento no roteamento da rede e porque a tecnologia da camada de link atual é considerada capaz de fornecer detecção de erros suficiente (consulte também RFC 3819).
  • O UDP tem uma soma de verificação opcional que cobre a carga útil e as informações de endereçamento nos cabeçalhos UDP e IP. Os pacotes com somas de verificação incorretas são descartados pela pilha de rede . A soma de verificação é opcional no IPv4 e necessária no IPv6. Quando omitido, presume-se que a camada de link de dados fornece o nível desejado de proteção contra erros.
  • O TCP fornece uma soma de verificação para proteger a carga útil e as informações de endereçamento nos cabeçalhos TCP e IP. Os pacotes com somas de verificação incorretas são descartados pela pilha da rede e, eventualmente, são retransmitidos usando ARQ, seja explicitamente (como por meio de handshake de três vias ) ou implicitamente devido a um tempo limite .

Telecomunicações espaciais

O desenvolvimento de códigos de correção de erros foi fortemente acoplado à história das missões espaciais devido à extrema diluição da potência do sinal em distâncias interplanetárias e à disponibilidade limitada de energia a bordo de sondas espaciais. Enquanto as primeiras missões enviaram seus dados não codificados, começando em 1968, a correção digital de erros foi implementada na forma de códigos convolucionais ( decodificados de forma subótima) e códigos Reed-Muller . O código Reed-Muller era adequado para o ruído ao qual a espaçonave estava sujeita (correspondendo aproximadamente a uma curva de sino ), e foi implementado para a espaçonave Mariner e usado em missões entre 1969 e 1977.

As missões Voyager 1 e Voyager 2 , que começaram em 1977, foram projetadas para fornecer imagens coloridas e informações científicas de Júpiter e Saturno . Isso resultou em requisitos de codificação aumentados e, portanto, as espaçonaves eram suportadas por códigos convolucionais ( decodificados por Viterbi de maneira ideal ) que podiam ser concatenados com um código de Golay externo (24,12,8) . A nave Voyager 2 adicionalmente suportou uma implementação de um código Reed-Solomon . O código concatenado Reed – Solomon – Viterbi (RSV) permitiu uma correção de erros muito poderosa e possibilitou a longa jornada da espaçonave para Urano e Netuno . Após as atualizações do sistema ECC em 1989, os dois ofícios usaram a codificação V2 RSV.

O Comitê Consultivo para Sistemas de Dados Espaciais atualmente recomenda o uso de códigos de correção de erros com desempenho semelhante ao código da Voyager 2 RSV, no mínimo. Os códigos concatenados estão cada vez mais caindo em desuso com as missões espaciais e são substituídos por códigos mais poderosos, como códigos Turbo ou códigos LDPC .

Os diferentes tipos de missões espaciais e orbitais conduzidas sugerem que tentar encontrar um sistema de correção de erros que sirva para todos será um problema contínuo. Para missões próximas à Terra, a natureza do ruído no canal de comunicação é diferente daquela que uma nave espacial em uma missão interplanetária experimenta. Além disso, à medida que uma espaçonave aumenta sua distância da Terra, o problema de correção de ruído se torna mais difícil.

Transmissão por satélite

A demanda por largura de banda do transponder de satélite continua a crescer, alimentada pelo desejo de fornecer televisão (incluindo novos canais e televisão de alta definição ) e dados IP. A disponibilidade do transponder e as restrições de largura de banda limitaram esse crescimento. A capacidade do transponder é determinada pelo esquema de modulação selecionado e pela proporção da capacidade consumida pelo FEC.

Armazenamento de dados

Os códigos de detecção e correção de erros costumam ser usados ​​para melhorar a confiabilidade da mídia de armazenamento de dados. Uma trilha de paridade capaz de detectar erros de bit único estava presente no primeiro armazenamento de dados em fita magnética em 1951. O código retangular ideal usado em fitas de gravação codificadas em grupo não apenas detecta, mas também corrige erros de bit único. Alguns formatos de arquivo , particularmente formatos de arquivo , incluem uma soma de verificação (geralmente CRC32 ) para detectar corrupção e truncamento e podem empregar arquivos de redundância ou paridade para recuperar porções de dados corrompidos. Os códigos Reed-Solomon são usados ​​em CDs para corrigir erros causados ​​por arranhões.

Os discos rígidos modernos usam códigos Reed-Solomon para detectar erros menores corretos em leituras de setor e para recuperar dados corrompidos de setores com falha e armazenar esses dados nos setores sobressalentes. Os sistemas RAID usam uma variedade de técnicas de correção de erros para recuperar dados quando um disco rígido falha completamente. Sistemas de arquivos como ZFS ou Btrfs , bem como algumas implementações de RAID , oferecem suporte para depuração e resilvering de dados , o que permite que blocos defeituosos sejam detectados e (com sorte) recuperados antes de serem usados. Os dados recuperados podem ser reescritos exatamente no mesmo local físico, em blocos sobressalentes em outro lugar no mesmo hardware, ou os dados podem ser reescritos no hardware de reposição.

Memória corretora de erros

A memória dinâmica de acesso aleatório (DRAM) pode fornecer proteção mais forte contra erros de software , contando com códigos de correção de erros. Tal memória corretora de erros, conhecida como memória protegida por ECC ou EDAC , é particularmente desejável para aplicações de missão crítica, como computação científica, financeira, médica, etc., bem como aplicações extraterrestres devido ao aumento da radiação no espaço.

Os controladores de memória com correção de erros tradicionalmente usam códigos de Hamming , embora alguns usem redundância modular tripla . A intercalação permite distribuir o efeito de um único raio cósmico potencialmente perturbando vários bits fisicamente vizinhos em várias palavras, associando bits vizinhos a palavras diferentes. Contanto que um evento único upset (SEU) não exceda o limite de erro (por exemplo, um único erro) em qualquer palavra particular entre acessos, ele pode ser corrigido (por exemplo, por um código de correção de erro de bit único), e a ilusão de um sistema de memória livre de erros pode ser mantida.

Além do hardware que fornece recursos necessários para a operação da memória ECC, os sistemas operacionais geralmente contêm recursos de relatórios relacionados que são usados ​​para fornecer notificações quando os erros de software são recuperados de forma transparente. Um exemplo é o kernel Linux 's EDAC subsistema (anteriormente conhecido como Bluesmoke ), que recolhe os dados a partir de componentes verificando-habilitado a erros dentro de um sistema de computador; além de coletar e relatar os eventos relacionados à memória ECC, ele também oferece suporte a outros erros de soma de verificação, incluindo aqueles detectados no barramento PCI . Alguns sistemas também suportam limpeza de memória para detectar e corrigir erros antes que eles se tornem irrecuperáveis.

Veja também

Referências

Leitura adicional

links externos