Detecção e correção de erros
Na teoria da informação e na teoria da codificação com aplicações em ciência da computação e telecomunicações, detecção e correção de erros (EDAC) ou controle de erros são técnicas que permitem a entrega confiável de dados digitais em canais de comunicação não confiáveis. Muitos canais de comunicação estão sujeitos a ruído de canal e, portanto, erros podem ser introduzidos 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
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.
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 pelo seu trabalho de acordo com o número de stichs (linhas do verso). Como os livros em prosa da Bíblia quase nunca 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 massorá 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, observando o ponto central de um livro, estatísticas de uso de palavras e comentários. Os padrões tornaram-se tais que um desvio em até mesmo uma única letra em um pergaminho 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, datados de c.150 aC-75 dC.
O desenvolvimento moderno de códigos de correção de erros é creditado a Richard Hamming em 1947. Uma descrição do código de Hamming apareceu em A Mathematical Theory of Communication de Claude Shannon e foi rapidamente generalizado por Marcel J. E. Golay.
Princípios
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 (sem erros) e anexa um número fixo de bits de verificação (ou dados de paridade), que são derivados dos dados bits por algum algoritmo de codificação. Se a detecção de erro 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 momento durante a transmissão. Se for necessária correção de erro, um receptor pode aplicar o algoritmo de decodificação aos bits de dados recebidos e aos bits de verificação recebidos para recuperar os dados originais sem erros. Num sistema que utiliza um código não sistemático, a mensagem original é transformada numa mensagem codificada com a mesma informação e que tem pelo menos tantos bits como a mensagem original.
O bom desempenho do 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, nos quais os erros ocorrem aleatoriamente e com certa probabilidade, e modelos dinâmicos, nos quais os erros ocorrem principalmente em rajadas. Consequentemente, os códigos de detecção e correção de erros podem geralmente ser distinguidos entre detecção/correção de erros aleatórios e detecção/correção de erros em rajadas. Alguns códigos também podem ser adequados para uma mistura de erros aleatórios e erros de rajada.
Se as características do canal não puderem ser determinadas ou forem altamente variáveis, um esquema de detecção de erros pode ser combinado com um sistema para retransmissões de dados errados. Isso é conhecido como solicitação de repetição automática (ARQ) e é usado principalmente na Internet. Uma abordagem alternativa para 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
A solicitação de repetição automática (ARQ) é um método de controle de erro para transmissão de dados que utiliza códigos de detecção de erro, mensagens de confirmação e/ou confirmação negativa e tempos limite para obter uma transmissão de dados confiável. Um reconhecimento é 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 que o tempo limite ocorra (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 período predeterminado número 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 de retorno, resulta em possivelmente aumento da latência 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, 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.
Correção de erro de encaminhamento
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 vários erros (até a capacidade de o código que está sendo usado) são introduzidos, seja durante o processo de transmissão ou no armazenamento. Como o receptor não precisa solicitar ao remetente a retransmissão dos dados, um backchannel não é necessário na correção de erros de encaminhamento. Os códigos de correção de erros são usados na comunicação da camada inferior, como rede celular, comunicação de fibra ótica de alta velocidade e Wi-Fi, bem como para armazenamento confiável em mídia, como memória flash, disco rígido e RAM.
Códigos de correção de erros geralmente são distinguidos entre códigos convolucionais e códigos de bloco:
- Códigos convolucionais são processados em uma base bit-by-bit. Eles são particularmente adequados para implementação em hardware, e o decodificador Viterbi permite decodificação ideal.
- Códigos de bloco são processados em uma base de bloqueio. Os primeiros exemplos de códigos de bloco são códigos de repetição, códigos Hamming e códigos multidimensionais de verificação de paridade. Eles foram seguidos por um número de códigos eficientes, os códigos Reed-Solomon são os mais notáveis devido ao seu uso comum atual. Os códigos Turbo e os códigos de verificação de paridade de baixa densidade (LDPC) são construções relativamente novas que podem fornecer eficiência quase ideal.
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 de capacidade do canal. Mais especificamente, o teorema diz que existem códigos de modo que, com o aumento do tamanho da 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 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 ocorre porque a prova de Shannon era apenas de natureza existencial e não mostrava como construir códigos que fossem ótimos e tivessem algoritmos de codificação e decodificação eficientes.
Esquemas híbridos
Hybrid ARQ é uma combinação de ARQ e correção de erro direta. Existem duas abordagens básicas:
- As mensagens são sempre transmitidas com dados de paridade FEC (e redundância de deteção de erros). Um receptor decodifica uma mensagem usando as informações de paridade e solicita a retransmissão usando ARQ somente se os dados de paridade não foram suficientes para a decodificação bem sucedida (identificada através de uma verificação de integridade falhada).
- As mensagens são transmitidas sem dados de paridade (apenas com informações de detecção de erros). Se um receptor detectar um erro, ele solicita informações FEC do transmissor usando ARQ, e o usa para reconstruir a mensagem original.
A última abordagem é particularmente atraente em um canal de apagamento ao usar um código de apagamento sem taxa.
Esquemas de detecção de erros
A detecção de erros é mais comumente realizada usando uma função de hash adequada (ou especificamente, uma soma de verificação, verificação de redundância cíclica ou outro algoritmo). Uma função de hash adiciona uma tag de comprimento fixo a uma mensagem, o que permite que os receptores verifiquem a mensagem entregue recalculando a tag e comparando-a com a fornecida.
Existe uma grande variedade de designs de funções de hash diferentes. No entanto, alguns são de uso particularmente difundido devido à sua simplicidade ou à sua 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 rajada).
Codificação de distância mínima
Um código de correção de erro aleatório baseado 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 serem transmitidos, os dados são divididos em blocos de bits. Cada bloco é transmitido um 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 esse 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 ser suscetível a problemas se o erro ocorrer exatamente no mesmo local para cada grupo (por exemplo, "1010 1010 1010" no exemplo anterior seria detectado como correto). A vantagem dos códigos de repetição é que são extremamente simples, sendo inclusive utilizados em algumas transmissões de estações numéricas.
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 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.
Bits de paridade adicionados a cada "palavra" enviadas são chamadas de verificações de redundância transversal, enquanto aquelas adicionadas ao final de um fluxo de "palavras" são chamadas de verificações de redundância longitudinal. Por exemplo, se cada uma de uma série de "palavras" tiver um bit de paridade adicionado, mostrando se houve um número ímpar ou par de uns nessa palavra, qualquer palavra com um único erro nela será detectada. No entanto, não se saberá onde está o erro na palavra. Se, além disso, após cada fluxo de n palavras, uma soma de paridade for enviada, cada bit mostrando se houve um número par ou ímpar de uns naquela posição de bit enviada no grupo mais recente, a posição exata do erro pode ser determinado e o erro corrigido. Este método só tem eficácia garantida, 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.
Soma de verificação
Uma soma de verificação de uma mensagem é uma soma aritmética modular de palavras de código de mensagem de comprimento de palavra fixo (por exemplo, valores de byte). A soma pode ser negada por meio de uma operação de complemento de um antes da transmissão para detectar mensagens totalmente zero não intencionais.
Os esquemas de soma de verificação incluem bits de paridade, dígitos de verificação e verificações de redundância longitudinal. Alguns esquemas de soma de verificação, 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 de 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. É caracterizado pela especificação de um polinômio gerador, que é usado como divisor em uma divisão polinomial longa sobre um corpo finito, tomando os dados de entrada como o dividendo. O restante se torna o resultado.
Um CRC possui propriedades que o tornam adequado para detectar erros de rajada. 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, se as alterações dos dados são acidentais (por exemplo, devido a erros de transmissão) ou introduzidos de forma maliciosa. Qualquer modificação nos dados provavelmente será detectada por meio de um valor de 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) poderá ser usado para segurança adicional. Sem conhecer 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 mínima de Hamming, d, pode detectar até d − 1 erros em uma palavra de código. O uso de 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 no número mínimo de erros a serem detectados for desejado.
Códigos com distância 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.
Aplicativos
Aplicativos que requerem baixa latência (como conversas telefônicas) não podem usar solicitação de repetição automática (ARQ); eles devem usar correção de erro de avanço (FEC). No momento em que um sistema ARQ descobre um erro e o retransmite, os dados reenviados chegarão tarde demais para serem usados.
Aplicações onde o transmissor esquece imediatamente a informação assim que ela é enviada (como a maioria das câmeras de televisão) não podem usar ARQ; eles devem usar FEC porque quando ocorre um erro, os dados originais não estão mais disponíveis.
Aplicações que utilizam ARQ devem possuir um canal de retorno; aplicativos sem canal de retorno não podem usar ARQ.
Aplicações que exigem taxas de erro extremamente baixas (como transferências digitais de dinheiro) 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 é executado em vários níveis:
- Cada quadro Ethernet usa a detecção de erros CRC-32. Os quadros com erros detectados são descartados pelo hardware receptor.
- O cabeçalho IPv4 contém um checksum protegendo o conteúdo do cabeçalho. Os pacotes com checksums incorretos são deixados dentro da rede ou no receptor.
- O checksum foi omitido do cabeçalho IPv6 para minimizar os custos de processamento no roteamento de rede e porque a tecnologia de camada de ligação atual é presumida para fornecer detecção de erro suficiente (ver também RFC 3819).
- UDP tem um checksum opcional que cobre a carga útil e informações de endereçamento nos cabeçalhos UDP e IP. Os pacotes com checksums incorretos são descartados pela pilha de rede. O checksum é opcional em IPv4, e é necessário em IPv6. Quando omitido, presume-se que a camada de link de dados fornece o nível desejado de proteção de erro.
- TCP fornece um checksum para proteger a carga útil e informações de endereçamento nos cabeçalhos TCP e IP. Packets com checksums incorretos são descartados pela pilha de rede, e eventualmente são retransmitidos usando ARQ, seja explicitamente (como através de aperto de mão de três vias) ou implicitamente devido a um tempo limite.
Telecomunicações do espaço profundo
O desenvolvimento de códigos de correção de erros foi fortemente associado à história das missões no espaço profundo devido à extrema diluição da potência do sinal nas distâncias interplanetárias e à disponibilidade limitada de energia a bordo das sondas espaciais. Enquanto as primeiras missões enviavam seus dados não codificados, a partir de 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 foi bem adequado ao ruído a que a espaçonave estava sujeita (aproximadamente correspondendo 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, a espaçonave era suportada por códigos convolucionais (decodificados de forma ideal por Viterbi) que podiam ser concatenados com um código Golay (24,12,8) externo. A nave Voyager 2 também suportava a implementação de um código Reed-Solomon. O código Reed-Solomon-Viterbi (RSV) concatenado permitiu uma correção de erros muito poderosa e permitiu a jornada estendida da espaçonave para Urano e Netuno. Após as atualizações do sistema ECC em 1989, ambas as naves 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 Voyager 2 RSV no mínimo. Os códigos concatenados estão caindo cada vez mais em desuso nas 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 espaço profundo e missões orbitais que são conduzidas sugerem que tentar encontrar um sistema de correção de erros de tamanho único será um problema contínuo. Para missões próximas à Terra, a natureza do ruído no canal de comunicação é diferente daquela experimentada por uma espaçonave em uma missão interplanetária. Além disso, à medida que uma espaçonave aumenta sua distância da Terra, o problema de corrigir o ruído torna-se mais difícil.
Transmissão por satélite
A demanda por largura de banda de 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 são frequentemente usados para melhorar a confiabilidade da mídia de armazenamento de dados. Uma faixa 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 redundância ou arquivos de paridade para recuperar partes 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 e corrigir pequenos erros nas 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, suportam depuração e restauração de dados, o que permite que blocos defeituosos sejam detectados e (espero) recuperados antes de serem usados. Os dados recuperados podem ser reescritos exatamente no mesmo local físico, para poupar blocos em outro lugar no mesmo hardware, ou os dados podem ser reescritos no hardware de substituição.
Memória de correção de erros
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. Essa memória de correção de erros, conhecida como memória ECC ou protegida por EDAC, é particularmente desejável para aplicativos 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.
Controladores de memória com correção de erros tradicionalmente usam códigos 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. Desde que um distúrbio de evento único (SEU) não exceda o limite de erro (por exemplo, um único erro) em qualquer palavra específica entre os 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 fornecer os recursos necessários para a operação da memória ECC, os sistemas operacionais geralmente contêm recursos de relatório relacionados que são usados para fornecer notificações quando erros de software são recuperados de forma transparente. Um exemplo é o subsistema EDAC do kernel do Linux (anteriormente conhecido como Bluesmoke), que coleta os dados de componentes habilitados para verificação de erros dentro de um sistema de computador; além de coletar e relatar os eventos relacionados à memória ECC, ele também suporta outros erros de soma de verificação, incluindo aqueles detectados no barramento PCI. Alguns sistemas também suportam a limpeza de memória para detectar e corrigir erros antes que eles se tornem irrecuperáveis.