Códigos de correção de erro, o santo graal da era da informação

Códigos de correção de erro, céu e inferno dos programadores.

Códigos de correção de erro são o Santo Graal da era da informação, eles garantem a transmissão sem falhas do sinal digital seja por via aérea ou através de cabos de cobre precários, mesmo com a presença de influências danosas que os engenheiros chamam de “ruído”.

Só que os códigos de correção de erro tradicionais funcionam melhor com grandes porções de dados: quanto maior a porção, maior é a taxa de transmissão que ele pode ser mandado sem erros. Entretanto, na era da internet, a computação distribuída tem se tornado cada vez mais comum, com diferentes dispositivos trocando pequenas porções de dados distribuídos em longos períodos de tempo.

Nos últimos 20 anos os cientistas têm pesquisado esquemas de código-interativo para abordar o problema das longas sequencias de troca de pequenas porções de dados. Como os algoritmos clássicos, os códigos interativos precisam responder a três perguntas básicas: quanto ruído ele pode tolerar? qual a taxa máxima de transmissão que ele suporta? e quanto tempo é necessário no processo de codificação e decodificação?

Trabalhos anteriores sempre andaram no fio da navalha tentando otimizar as três coisas ao mesmo tempo, mas os engenheiros sempre acabavam tendo que optar por duas delas. Até que os estudantes de engenharia elétrica do MIT surgiram com uma nova abordagem no último simpósio do IEEE, com a intenção de equilibrar finalmente as três questões.

Na prática não é possível saber qual tipo de ruído representa o cenário real. Se fosse possível saber, essa informação poderia ser usada, mas geralmente não é possível saber, então o código gerado tem que ser o mais geral possível. Então, um código que pudesse lidar com um sinal “adversário” conhecido, poderia lidar com qualquer tipo de ruído.

Códigos de correção de erro, tanto os clássicos quanto os interativos, funcionam adicionando alguma informação extra na mensagem a ser transmitida. Eles podem, por exemplo, adicionar alguns bits que descrevem aritmeticamente a relação entre os demais bits da mensagem. Tanto os bits da mensagem, quanto  os bits extras são passíveis de sofrerem corrupção, então decodificar a mensagem é um longo processo de ir para frente a para trás na mensagem até inferir a sequencia correta que está saindo do receptor.

Na comunicação interativa, a tolerância máxima para erros é de 1/4, se o sinal adversário conseguir corromper mais do que isso, a comunicação será comprometida. Alguns modelos de correção de erro podem lidar com taxas acima disso, mas o processo de decodificação é proibitivamente complexo.

Para manter a complexidade baixa, eles adotaram uma técnica chamada decodificação de lista. Ao invés de andar para frente e para trás através dos bits da menagem e dos bits de controle até encontrar a interpretação correta, o algoritmo interage apenas o suficiente para criar uma lista das interpretações mais prováveis. No final dessa “computação mútua” cada dispositivo pode ter uma lista com centenas de entradas.

Entretanto, se cada dispositivo tem apenas um conhecimento imperfeito das mensagens recebidas, ele com certeza tem um conhecimento perfeito das mensagens que mandou. Então, se no final do processamento cada dispositivo trocar sua lista com o outro, eles terão informação suficiente para zerar os palpites errados.

O trabalho apresentado pode estar desencadeando uma nova era no modelo de transmissão digital de conteúdo, sempre sedento por mais banda, mas velocidade e menos erros.

Fonte: SD.