Código Tornado - Tornado code

Na teoria da codificação , os códigos Tornado são uma classe de códigos de eliminação que oferecem suporte à correção de erros . Os códigos Tornado requerem um C constante mais blocos redundantes do que os códigos de eliminação Reed-Solomon mais eficientes em dados , mas são muito mais rápidos de gerar e podem corrigir apagamentos com mais rapidez. As implementações baseadas em software de códigos de tornado são cerca de 100 vezes mais rápidas em comprimentos pequenos e cerca de 10.000 vezes mais rápido em comprimentos maiores do que os códigos de eliminação de Reed-Solomon. Desde a introdução dos códigos Tornado, muitos outros códigos de eliminação semelhantes surgiram, principalmente os códigos online , códigos LT e códigos Raptor .

Os códigos de 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 Reed-Solomon, que é mais lento, mas é ideal em termos de recuperação de falhas. Os códigos de tornado determinam quantos níveis, quantos 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. Os blocos são sequências de bits do mesmo tamanho. Os dados de recuperação usam o mesmo tamanho de bloco dos dados de entrada. O apagamento de um bloco (entrada ou recuperação) é detectado por algum outro meio. (Por exemplo, um bloco do disco não passa na verificação CRC ou um pacote de rede com um determinado número de sequência nunca chega.)

O número de blocos de recuperação é fornecido pelo usuário. Então, 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 B que é menor que um. Se houver N blocos de entrada, o primeiro nível de recuperação terá blocos B * N, o segundo terá B * B * N, o terceiro terá B * B * B * N e assim por diante.

Todos os níveis de recuperação, exceto o final, usam um LDPC, que funciona por xor (ou exclusivo). Xor opera em valores binários, 1s e 0s. A xou B será 1 se A e B tiverem valores diferentes e 0 se A e B tiverem os mesmos valores. Se você receber o resultado de (A xou B) e A, você pode determinar o valor de B. (A xou B xou A = B) Da mesma forma, se você receber o resultado de (A xou B) e B, você pode determinar o valor para A. Isso se estende a vários valores, portanto, dado o resultado de (A xou B xou C xou D) e quaisquer 3 dos valores, o valor ausente 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, os blocos de recuperação no nível dois são, cada um, o xor de algum conjunto de blocos no nível um. Os blocos usados ​​no xor são escolhidos aleatoriamente, sem repetição. No entanto, o número de blocos xor'ed para fazer um bloco de recuperação é escolhido a partir de uma distribuição muito específica para cada nível.

Como 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 Reed – Solomon. Os códigos Reed-Solomon são ótimos em termos de recuperação de falhas, mas são lentos para gerar e recuperar. Como cada nível tem menos blocos do que o anterior, o código Reed – Solomon tem um pequeno número de blocos de recuperação para gerar e usar na recuperação. Portanto, embora Reed – Solomon seja lento, ele tem apenas uma pequena quantidade de dados para lidar.

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

Indo mais baixo, 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 abaixo estiver faltando no máximo C 'menos blocos do que o nível de recuperação. O algoritmo de recuperação é encontrar algum bloco de recuperação que tenha apenas um de seu conjunto gerador faltando 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.

Problemas de patentes

Os códigos do Tornado foram patenteados anteriormente nos Estados Unidos da América. As patentes US6163870 A (depositadas em 6 de novembro de 1997) e US 6081909 A (registradas em 6 de novembro de 1997) descrevem os códigos Tornado e expiraram em 6 de novembro de 2017. As patentes US6307487 B1 (registradas em 5 de fevereiro de 1999) e US6320520 B1 (registradas 17 de setembro de 1999) também mencionam os 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.

links externos

Uma descrição legível de CMU (PostScript) [1] e outra de Luby no International Computer Science Institute (PostScript) [2] .

Veja também

Notas

Referências

  • M. Mitzenmacher (2004). "Fontes digitais: uma pesquisa e um olhar para o futuro". Proc. 2004 IEEE Information Theory Workshop (ITW) .
  • M. Luby , M. Mitzenmacher , A. Shokrollahi , D. Spielman , V. Stemann (1997). "Códigos Práticos de Resiliência às Perdas". Anais do Vigésimo Nono Simpósio Anual da ACM em Teoria da Computação : 150–159. CS1 maint: vários nomes: lista de autores ( link )
  • M. Luby , M. Mitzenmacher , A. Shokrollahi (1998). "Análise de processos aleatórios via avaliação de árvore e ou". Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms : 364–373. CS1 maint: vários nomes: lista de autores ( link )