Na teoria de códigos, os códigos fonte (do inglês fountain codes, também conhecidos como códigos de apagamento sem taxa fixa) são uma classe de códigos de apagamento com a propriedade de que uma sequência potencialmente ilimitada de símbolos de codificação pode ser gerada a partir de um dado conjunto de símbolos fonte, de tal forma que os símbolos fonte originais podem, idealmente, ser recuperados a partir de qualquer subconjunto dos símbolos de codificação de tamanho igual ou apenas ligeiramente maior do que o número de símbolos fonte. O termo fonte ou sem taxa fixa (rateless) refere-se ao fato de que esses códigos não exibem uma taxa de código fixa. Um código fonte é ótimo se os

k

{\displaystyle k}

símbolos fonte originais puderem ser recuperados de quaisquer

k

{\displaystyle k}

símbolos de codificação recebidos com sucesso (isto é, excluindo aqueles que foram apagados). Conhecem-se códigos fonte que possuem algoritmos eficientes de codificação e decodificação e que permitem a recuperação dos

k

{\displaystyle k}

símbolos fonte originais a partir de quaisquer

k ′

{\displaystyle k'}

símbolos de codificação com alta probabilidade, onde

k ′

{\displaystyle k'}

é apenas ligeiramente maior que

k

{\displaystyle k}

. Os códigos LT foram a primeira realização prática dos códigos fonte. Posteriormente, os códigos Raptor e os códigos online foram introduzidos, alcançando complexidade de tempo linear para codificação e decodificação através de um estágio de pré-codificação dos símbolos de entrada. A Codificação de rede triangular alcança codificação e decodificação lineares usando codificação não-linear, e decodificação usando o método de substituição reversa.

Aplicações Os códigos fonte são aplicáveis de forma flexível em uma taxa de código fixa, ou onde uma taxa de código fixa não pode ser determinada a priori, e onde é necessária a codificação e decodificação eficientes de grandes quantidades de dados. Um exemplo é o de um carrossel de dados, onde um arquivo grande é continuamente transmitido para um conjunto de receptores. Usando um código de apagamento de taxa fixa, um receptor que perde um símbolo fonte (devido a um erro de transmissão) enfrenta o problema do colecionador de cupons: ele deve receber com sucesso um símbolo de codificação que ainda não possui. Esse problema torna-se muito mais aparente ao usar um código de apagamento de comprimento curto tradicional, pois o arquivo deve ser dividido em vários blocos, cada um sendo codificado separadamente: o receptor agora deve coletar o número necessário de símbolos de codificação ausentes para cada bloco. Usando um código fonte, basta que um receptor recupere qualquer subconjunto de símbolos de codificação com tamanho ligeiramente maior que o conjunto de símbolos fonte. (Na prática, a transmissão é tipicamente agendada para um período de tempo fixo por um operador com base nas características da rede e dos receptores e na confiabilidade de entrega desejada, e assim o código fonte é usado a uma taxa de código que é determinada dinamicamente no momento em que o arquivo é agendado para ser transmitido.) Outra aplicação é a do ARQ híbrido em cenários de multicast confiável: a informação de paridade solicitada por um receptor pode ser potencialmente útil para todos os receptores no grupo multicast.

Em padrões Os códigos Raptor são os códigos fonte mais eficientes no momento, tendo algoritmos de codificação e decodificação de tempo linear muito eficientes, e exigindo apenas um pequeno número constante de operações XOR por símbolo gerado, tanto para a codificação quanto para a decodificação. A RFC 5053 da IETF especifica detalhadamente um código Raptor sistemático, que foi adotado em múltiplos padrões além da IETF, como dentro do padrão MBMS do 3GPP para entrega de arquivos de transmissão e serviços de streaming, no padrão IPDC do DVB-H para entrega de serviços IP sobre redes DVB e no DVB-IPTV para entrega de serviços de TV comercial sobre uma rede IP. Este código pode ser usado com até 8.192 símbolos fonte em um bloco fonte, e um total de até 65.536 símbolos codificados gerados para um bloco fonte. Este código tem uma sobrecarga de recepção relativa média de 0,2% quando aplicado a blocos fonte com 1.000 símbolos fonte, e tem uma sobrecarga de recepção relativa de menos de 2% com probabilidade de 99,9999%. A sobrecarga de recepção relativa é definida como os dados de codificação extras necessários além do comprimento dos dados fonte para recuperar os dados fonte originais, medidos como uma porcentagem do tamanho dos dados fonte. Por exemplo, se a sobrecarga de recepção relativa é de 0,2%, isso significa que dados fonte com tamanho de 1 megabyte podem ser recuperados a partir de 1,002 megabytes de dados de codificação. Um código Raptor mais avançado, com maior flexibilidade e melhor sobrecarga de recepção, chamado RaptorQ, foi especificado na RFC 6330 da IETF. O código RaptorQ especificado pode ser usado com até 56.403 símbolos fonte em um bloco fonte e um total de até 16.777.216 símbolos codificados gerados para um bloco fonte. Este código é capaz de recuperar um bloco fonte a partir de qualquer conjunto de símbolos codificados igual ao número de símbolos fonte no bloco fonte com alta probabilidade e, em casos raros, a partir de um número ligeiramente maior do que o número de símbolos fonte no bloco fonte. O código RaptorQ é parte integrante da instanciação ROUTE especificada na ATSC A-331 (ATSC 3.0).

Para armazenamento de dados Os códigos de apagamento são usados em aplicações de armazenamento de dados devido à enorme economia no número de unidades de armazenamento para um determinado nível de redundância e confiabilidade. Os requisitos de design do código de apagamento para armazenamento de dados, particularmente para aplicações de armazenamento distribuído, podem ser bastante diferentes em relação aos cenários de comunicação ou streaming de dados. Um dos requisitos da codificação para sistemas de armazenamento de dados é a forma sistemática, ou seja, os símbolos originais da mensagem fazem parte dos símbolos codificados.[carece de fontes]? A forma sistemática permite a leitura dos símbolos da mensagem sem a necessidade de decodificação a partir de uma unidade de armazenamento. Além disso, como a largura de banda e a carga de comunicação entre os nós de armazenamento podem ser um gargalo, códigos que permitem comunicação mínima são muito benéficos, particularmente quando um nó falha e uma reconstrução do sistema é necessária para alcançar o nível inicial de redundância. A esse respeito, espera-se que os códigos fonte permitam um processo de reparo eficiente em caso de falha: quando um único símbolo codificado é perdido, não deve ser exigida muita comunicação e computação entre os outros símbolos codificados a fim de ressuscitar o símbolo perdido. De fato, a latência de reparo às vezes pode ser mais importante do que a economia de espaço de armazenamento. Os códigos fonte reparáveis são projetados para atender aos objetivos de design de código fonte para sistemas de armazenamento. Uma pesquisa detalhada sobre códigos fonte e suas aplicações pode ser encontrada em. Uma abordagem diferente para o armazenamento distribuído usando códigos fonte foi proposta no Liquid Cloud Storage. O Liquid Cloud Storage baseia-se no uso de um grande código de apagamento, como o código RaptorQ especificado na RFC 6330 da IETF (que fornece uma proteção de dados significativamente melhor do que outros sistemas), usando um processo de reparo em segundo plano (que reduz significativamente os requisitos de largura de banda de reparo em comparação com outros sistemas) e usando uma organização de dados em fluxo contínuo (streaming), o que permite acesso rápido aos dados mesmo quando nem todos os símbolos codificados estão disponíveis.

Ver também Códigos online Codificação de rede linear Compartilhamento de segredos Códigos Tornado, o precursor dos códigos fonte

Referências

Bibliografia Amin Shokrollahi and Michael Luby (2011). «Raptor Codes». Now Publishers. Foundations and Trends in Communications and Information Theory. 6 (3–4): 213–322. doi:10.1561/0100000060 Luby, Michael (2002). «LT codes». The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings. [S.l.: s.n.] pp. 271–282. ISBN 0-7695-1822-2. doi:10.1109/sfcs.2002.1181950 A. Shokrollahi (2006), «Raptor Codes», IEEE Transactions on Information Theory, 52 (6), pp. 2551–2567, Bibcode:2006ITIT...52.2551S, doi:10.1109/tit.2006.874390 . P. Maymounkov (novembro 2002). «Online Codes» (PDF). (Technical Report) David J. C. MacKay (2003). Information Theory, Inference, and Learning Algorithms. [S.l.]: Cambridge University Press. Bibcode:2003itil.book.....M. ISBN 0-521-64298-1 M. Luby, A. Shokrollahi, M. Watson, T. Stockhammer (outubro 2007), Raptor Forward Error Correction Scheme for Object Delivery, RFC 5053 !CS1 manut: Nomes múltiplos: lista de autores (link). M. Luby, A. Shokrollahi, M. Watson, T. Stockhammer, L. Minder (maio 2011), RaptorQ Forward Error Correction Scheme for Object Delivery, RFC 6330 !CS1 manut: Nomes múltiplos: lista de autores (link).