Na teoria de códigos, os códigos Tornado são uma classe de códigos de apagamento que suportam a correção de erros. Os códigos Tornado requerem uma constante de blocos redundantes a mais do que os códigos de apagamento de Reed-Solomon (que são mais eficientes em relação aos dados), mas são muito mais rápidos de gerar e podem corrigir apagamentos de forma mais rápida. Implementações de códigos Tornado baseadas em software são cerca de 100 vezes mais rápidas em comprimentos pequenos e cerca de 10.000 vezes mais rápidas em comprimentos maiores do que os códigos de apagamento de Reed-Solomon. Desde a introdução dos códigos Tornado, muitos outros códigos de apagamento semelhantes surgiram, com destaque para os códigos Online, códigos LT e códigos Raptor.

Os códigos Tornado usam uma abordagem em camadas. Todas as camadas, exceto a última, usam um código de correção de erros LDPC, que é rápido, mas tem chance de falha. A camada final usa um código de correção de Reed-Solomon, que é mais lento, mas é ótimo em termos de recuperação de falhas. Os códigos Tornado determinam a quantidade de níveis, o número de blocos de recuperação em cada nível e a distribuição usada para gerar blocos para as camadas não finais.

Visão geral Os dados de entrada são divididos em blocos. Blocos são sequências de bits que têm todas o mesmo tamanho. Os dados de recuperação usam o mesmo tamanho de bloco que os dados de entrada. O apagamento de um bloco (de entrada ou de recuperação) é detectado por algum outro meio. (Por exemplo, um bloco do disco não passa em uma verificação CRC ou um pacote de rede com um determinado número de sequência nunca chegou).

O número de blocos de recuperação é determinado pelo usuário. Em seguida, o número de níveis é determinado junto com o número de blocos em cada nível. O número em cada nível é determinado por um fator que é menor que um. Se existirem blocos de entrada, o primeiro nível de recuperação terá blocos, o segundo terá , o terceiro terá , e assim por diante.

Todos os níveis de recuperação, exceto o final, usam um LDPC, que funciona por meio da operação XOR (Ou Exclusivo). O XOR opera em valores binários, 1s e 0s. é 1 se e tiverem valores diferentes e 0 se e tiverem os mesmos valores. Se for dado o resultado de e , é possível determinar o valor de . () Da mesma forma, se for dado o resultado de e , pode-se determinar o valor de . Isto se estende a múltiplos valores, de modo que, dado o resultado de e quaisquer 3 dos valores, o valor que falta pode ser recuperado.

Portanto, os blocos de recuperação no nível um são apenas o XOR de algum conjunto de blocos de entrada. Da mesma forma, cada um dos blocos de recuperação no nível dois é o XOR de algum conjunto de blocos do nível um. Os blocos usados no XOR são escolhidos aleatoriamente, sem repetição. No entanto, a quantidade de blocos combinados via XOR para formar um bloco de recuperação é escolhida a partir de uma distribuição muito específica para cada nível.

Como o XOR é uma operação rápida e os blocos de recuperação são um XOR de apenas um subconjunto dos blocos na entrada (ou em um nível de recuperação inferior), os blocos de recuperação podem ser gerados rapidamente.

O nível final é um código de Reed-Solomon. Os códigos de Reed-Solomon são ótimos em termos de recuperação de falhas, mas lentos para gerar e recuperar. Como cada nível tem menos blocos do que o anterior, o código de Reed-Solomon tem um pequeno número de blocos de recuperação para gerar e para usar na recuperação. Portanto, mesmo que o Reed-Solomon seja lento, ele só tem uma pequena quantidade de dados para processar.

Durante a recuperação, o código de Reed-Solomon é recuperado primeiro. É garantido que isto funcionará se o número de blocos ausentes no penúltimo nível for menor do que os blocos presentes no nível final.

Descendo de nível, o nível de recuperação LDPC (XOR) pode ser usado para recuperar o nível abaixo dele com alta probabilidade se todos os blocos de recuperação estiverem presentes e o nível inferior tiver, no máximo, blocos a menos do que o nível de recuperação. O algoritmo de recuperação consiste em encontrar algum bloco de recuperação que tenha apenas um de seu conjunto gerador ausente no nível inferior. Então, o XOR do bloco de recuperação com todos os blocos que estão presentes é igual ao bloco ausente.

Questões de patente Os códigos Tornado foram anteriormente patenteados nos Estados Unidos da América. As patentes US6163870 A (depositada em 6 de novembro de 1997) e US 6081909 A (depositada em 6 de novembro de 1997) descrevem os códigos Tornado e expiraram em 6 de novembro de 2017. As patentes US6307487 B1 (depositada em 5 de fevereiro de 1999) e US6320520 B1 (depositada em 17 de setembro de 1999) também mencionam códigos Tornado e expiraram em 5 de fevereiro de 2019 e 17 de setembro de 2019, respectivamente.

Citações Michael Luby criou os códigos Tornado.

Ver também

Código de apagamento Código Raptor

Referências

Bibliografia

Ligações externas

Uma descrição acessível da CMU (PostScript) e outra de Luby no International Computer Science Institute (PostScript) .