Código de fonte

Na teoria da codificação, códigos de fonte (também conhecidos como códigos de eliminação sem taxa) são uma classe de códigos de eliminação com a propriedade de que uma sequência potencialmente ilimitada de símbolos codificados podem ser gerados a partir de um determinado conjunto de símbolos da fonte, de modo que os símbolos da fonte originais podem ser idealmente recuperados de qualquer subconjunto de símbolos da codificação de tamanho igual ou, apenas ligeiramente, maior do que o número de símbolos da fonte. O termo fonte ou sem taxa (indicador, variação) refere-se ao fato de que esses códigos não exibem uma taxa de código fixa.

Um código de fonte é ideal se os símbolos da fonte k originais podem ser recuperados de qualquer símbolo da codificação recebido com sucesso de qualquer k (ou seja, excluindo aqueles que foram apagados). Códigos de fonte são conhecidos por terem algoritmos, de codificação e decodificação, eficientes que permitem a recuperação dos símbolos da fonte k originais de qualquer dos símbolos da codificação k’ com alta probabilidade, onde k’ é apenas ligeiramente maior que k.

Os códigos LT foram a primeira realização prática dos códigos de fonte. Códigos Raptor e códigos online foram posteriormente introduzidos e alcançaram complexidade de codificação e decodificação linear de tempo por meio de um estágio de pré-codificação dos símbolos de entrada.

Informações sobre a disponibilidade de um software eficiente de implementação do código RaptorQ especificado na RFC 6330 IETF, podem ser encontradas na página web Rq SDK em BitRipple.

Os códigos fonte são flexivelmente aplicáveis:

• à uma taxa de código fixa,
• ou onde uma taxa de código fixa não pode ser determinada a priori
• e onde a codificação e a decodificação eficiente de grandes quantidades de dados são necessárias.

Um exemplo é o de um carrossel de dados, onde algum arquivo grande é transmitido continuamente para um conjunto de receptores.^[1] Usando um código de eliminação de taxa fixa, um receptor sem um símbolo da origem (devido a um erro de transmissão) enfrenta o problema do coletor de cupons: ele deve receber com sucesso um símbolo da codificação que ainda não possui. Este problema se torna muito mais aparente ao usar um código de eliminação de comprimento curto tradicional, pois o arquivo deve ser dividido em vários blocos (cada um sendo codificado separadamente): o receptor deve agora coletar o número necessário de símbolos da codificação ausentes para cada bloco. Usar um código de fonte, é suficiente para um receptor recuperar qualquer subconjunto de símbolos da codificação de tamanho ligeiramente maior do que o conjunto de símbolos da fonte. Na prática, a transmissão normalmente é programada por um operador para um período fixo de tempo com base nas características da rede e dos receptores e confiabilidade de entrega desejada. Portanto, o código fonte é usado em uma taxa de código que é determinada dinamicamente no momento em que o arquivo está programado para ser transmitido.

Outra aplicação é a de ARQ híbrido em cenários de multicast confiáveis: a informação de paridade que é solicitada por um receptor pode ser potencialmente útil à todos os receptores no grupo multicast.

Códigos Raptor são os códigos de fonte mais eficientes no momento,^[2] tendo algoritmos de codificação e decodificação linear de tempo muito eficientes e exigindo apenas um pequeno número constante de operações XOR por símbolo gerado para codificação e decodificação.^[3]

A RFC 5053 IETF especifica em detalhes um código Raptor sistemático, que foi adotado em vários padrões além do IETF (como dentro do padrão MBMS 3GPP para entrega de arquivos e serviços de streaming, o padrão IPDC DVB-H para entrega de serviços IP em redes DVB e DVB-IPTV para entrega serviços comerciais de TV em 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 de origem com 1.000 símbolos de origem e tem uma sobrecarga de recepção relativa de menos de 2% com probabilidade de 99,9999%.^[4] A sobrecarga de recepção relativa é definida como os dados de codificação extras necessários além do comprimento dos dados de origem para recuperar os dados de origem originais, medidos como uma porcentagem do tamanho dos dados de origem. Por exemplo, se a sobrecarga de recepção relativa for 0,2%, isso significa que os dados de origem de tamanho 1 megabyte podem ser recuperados de 1,002 megabytes de dados de codificação.

Um código Raptor mais avançado com maior flexibilidade e sobrecarga de recepção melhorada, chamado RaptorQ, foi especificado na RFC 6330 IETF. O código RaptorQ especificado pode ser usado com até 56.403 símbolos fonte em um bloco de origem e um total de até 16.777.216 símbolos codificados gerados para um bloco de origem. Este código é capaz de recuperar um bloco de origem de qualquer conjunto de símbolos codificados igual ao número de símbolos de origem no bloco de origem com alta probabilidade e, em casos raros, de um pouco mais do que o número de símbolos de origem no bloco de origem.

O código RaptorQ é uma parte integrante da instanciação ROUTE especificada em ATSC 3.0 criado pelo Advanced Television Systems Committee, também chamado Next Gen TV. Mais especificamente, o código RaptorQ é especificado em A-331: Padrão de sinalização, entrega, sincronização e proteção de erro do ATSC 3.0, conforme listado na lista de padrões ATSC. O ATSC 3.0 é uma instanciação prática de uma transmissão de internet, isto é, fornece mecanismos para entrega confiável de streaming de vídeo e arquivos para muitos receptores (incluindo receptores móveis) usando um canal de transmissão (broadcast) unidirecional. Os exemplos de casos de uso incluem o fornecimento de dados para ensino à distância e o fornecimento de atualizações de firmware e dados de mídia e entretenimento para automóveis.

Códigos de eliminação são usados em aplicativos de armazenamento de dados devido à grande economia no número de unidades de armazenamento para um determinado nível de redundância e confiabilidade. Os requisitos de design de código de eliminação para armazenamento de dados, particularmente para aplicativos de armazenamento distribuído, podem ser bastante diferentes em relação aos cenários de comunicação ou streaming de dados. Um dos requisitos de codificação para sistemas de armazenamento de dados é a forma sistemática, isto é, os símbolos da mensagem original são parte dos símbolos codificados. A forma sistemática permite a leitura dos símbolos da mensagem sem a necessidade de decodificar 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, os códigos que permitem a comunicação mínima são muito benéficos, especialmente quando um nó falha e uma reconstrução do sistema é necessária para atingir o nível inicial de redundância. A esse respeito, os códigos fonte devem permitir um processo de reparo eficiente em caso de falha: quando um único símbolo codificado é perdido, ele não deve exigir muita comunicação e computação entre outros símbolos codificados para ressuscitar o símbolo perdido. Na verdade, a latência de reparo às vezes pode ser mais importante do que a economia de espaço de armazenamento. Os códigos de fonte reparáveis^[5] são projetados para atender aos objetivos de design de código de fonte para sistemas de armazenamento. Uma pesquisa detalhada sobre os códigos de fonte e suas aplicações pode ser encontrada em ^[6]

Uma abordagem diferente para o armazenamento distribuído usando códigos de fonte foi proposta em "armazenamento em nuvem líquida (liquid cloud storage)".^[7][8] O "armazenamento em nuvem líquida (liquid cloud storage)" é baseado no uso de um grande código de eliminação, como o código RaptorQ especificado na RFC 6330 IETF (que fornece 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 fluxo de dados (que permite acesso rápido aos dados mesmo quando nem todos os símbolos codificados estão disponíveis).

• Códigos online
• Codificação de rede linear
• Compartilhamento secreto
• Código tornado, o precursor dos "códigos de fonte"

Referências

• Amin Shokrollahi and Michael Luby (2011). «Raptor codes». Now Publishers. Foundations and trends in communications and information theory (em inglês). 6 (3 e 4): 213 à 322. doi:10.1561/0100000060 

• Luby, Michael (2002). «LT Codes». IEEE symposium on foundations of computer science (em inglês): 271 à 282. ISBN 0-7695-1822-2. doi:10.1109/sfcs.2002.1181950 

• A. Shokrollahi (2006), «Raptor codes», IEEE Transactions on information theory (em inglês), 52 (6): 2551 à 2567, doi:10.1109/tit.2006.874390 .

• P. Maymounkov (novembro de 2002). «Online codes» (PDF). Technical report (em inglês) 

• David J. C. MacKay (2003). Information theory, inference and learning algorithms (em inglês). [S.l.]: Cambridge University Press. Bibcode:2003itil.book.....M. ISBN 0-521-64298-1 

• M. Luby, A. Shokrollahi, M. Watson, T. Stockhammer (outubro de 2007), Raptor forward error correction scheme for object delivery (em inglês), RFC 5053  !CS1 manut: Nomes múltiplos: lista de autores (link).

• M. Luby, A. Shokrollahi, M. Watson, T. Stockhammer, L. Minder (maio de 2011), RaptorQ forward error correction scheme for object delivery (em inglês), RFC 6330  !CS1 manut: Nomes múltiplos: lista de autores (link).