¯\_(ツ)_/¯
Detecção e correção de erro (Error detection and correction)
- O que são e como funcionam os códigos corretores de erros ?
Definição
São técnicas que permitem a entrega de dados de modo mais confiável através dos canais de comunicação.
Introdução
Detecção e Correção, são termos que caminham juntos sendo impossível a aplicação do segundo sem a eficácia do primeiro.
Os canais de comunicação no nível físico de modo geral são suscetíveis a sensíveis falhas, causando muitas vezes a perda ou fragmentação de dados.
"Funcionamento, quais os princípios por trás da técnica, é possível o código "corrigir" pra algo diferente dos dados originais ?"
Existem 2 métodos mais conhecidos para correção de erros:
Solicitação de repetição
automática (ARQ - Automatic repeat request):
Utiliza "acknowledgements" (confirmações através de mensagens enviadas pelo receptor indicando que recebeu corretamente um quadro de dados ou pacote )
e "timesout" (períodos de tempo que antecedem uma confirmação de recebimento) de modo a realizar uma transmissão de dados confiável. Caso o emissor não receba uma confirmação do receptor antes que o "timeout" complete seu ciclo, o pacote é retransmitido até a origem receber uma confirmação ou ultrapassar um número pré-definido de tentativas.
acknowledgements

timeout

Existem 3 protocolos principais que utilizam o método ARQ.
Todos tem base no Sliding window protocol.
2- O segundo método é o Forward error correction (Avançado corretor de
erro):
O remetente codifica o código de forma redundante usando um código de correção de erros(ECC), através da redundância adicionada ao código o receptor recupera os dados originais, em geral os dados reconstruídos são considerados
"os mais prováveis" dados originais.
A base para esse método, são os trabalhos de Richar Hamming, autor do código de Hamming e código Hamming(7,4).
Os 2 principais métodos (ARQ e FEC) quando combinados corrigem pequenos erros e evitam a retransmissão e os principais erros
são corrigidos através de 1 pedido de retransmissão : esse processo é chamado de (HARQ) hybrid automatic repeat request.
Os principais princípios que fazem parte da base para a aplicação são:
A explicação da lógica utilizada vai além do escopo dessa resposta, mas verificando os links, ou fazendo uma pesquisa aprofundada sobre as nomeações acima pode-se encontrar o total esclarecimento do funcionamento.
- "Quais as limitações, qual a melhor taxa que se pode esperar na prática?"
Hoje em dia, devido ao avanço na confecção dos meios físicos, a tolerância em alguns meios é perto de 0 (fibra ótica), e pode ser conquistado
em alguns laboratórios especiais. No entanto a diversidade de meios, nos faz considerar por exemplo as transmissões via rádio
que dependem de um ambiente controlado, o que não é possível no dia dia, pois chuvas, ventos, topologia e outros detalhes naturais ou não, interferem
diretamente na comunicação.
Para quadros codificados pelo CCSDS código Reed-Solomon , menos de 1 em 40.000 quadros errados podem escapar da detecção.
- "Há algum ponto a partir do qual os códigos se tornam excessivamente
longos (tendendo pro infinito, é claro)?"
Em tese, a teoria do algorítimo, afirma ser uma sequência finita de instruções. Os algorítimos de detecção e correção, são relativamente curtos, pois atuam sobre partes de tamanho definido (pacotes). No entanto, essa asserção é aplicada aos meios comerciais simples, e levando em consideração a criptografia militar, sondas espaciais e outras aplicações, creio que realmente podem tender pro "infinito", ou algumas milhões de linhas... Apesar que o uso da lógica serve exatamente para inibir está ideia, eu acho...
- "E esses códigos corrigem erros em posições arbitrárias nos dados
(ex.: início, meio, fim, 1 bit a cada 8, qualquer combinação das
anteriores, etc) ou só alguns tipos de erro específicos?"
Eles atuam sobre partes pré-determinadas dos pacotes, ou seja, sim, a arbitrariedade no caso não é o começo, meio ou fim, mas o erro detectado em si.
O Comité Consultivo para Sistemas Espaciais de Dados ( CCSDS ) define o protocolo utilizado para a transmissão de dados de instrumentos de nave espacial através do canal do espaço profundo. Segundo este padrão, uma imagem ou outros dados enviados a partir de um instrumento de nave espacial é transmitida utilizando um ou mais pacotes, variando de 7 a 65.542 bytes, incluindo o cabeçalho do pacote. Esses por sua vez são transmitidos através de quadros de até 2048 bytes.
"Em que cenários isso é usado na prática?"
Internet
Telecomunicações no espaço profundo
Radiodifusão via satélite
Armazenamento de dados
Memória com correção de erro
"Existem bibliotecas prontas pra fazer isso, ou é preciso implementar
à mão, caso a caso (dependendo das particularidades de cada aplicação)?"
O conjunto de códigos e protocolos utilizados para a construção de progrmas direcionados a essas tarefas é denominado Protocolos elementares de enlace de dados.
E o código do protocolo é por sua vez um conjunto de classes.
Algumas definições utilizadas nos protocolos apresentados são armazenadas no arquivo protocol.h
#define MAX_PKT 1024 // Packet size in bytes
typedef enum {false,true} boolean;
typedef unsigned int seq_nr // seq or ack numbers
typedef struct {unsigned char data[MAX_PKT];} packet
typedef enum {data, ack,nak} frame_kind
typedef struct{
frame_kind kind;
seq_nr seq;
seq_nr ack;
packet info;
} frame;
void waif_for_event(event_type *event);
void from_network_layer(packet *p);
void to_network_layer(packet *p);
void from_physical_layer(frame *r);
void to_physical_layer(frame *s);
void start_timer(seq_nr k);
void stop_timer(seq_nr k);
void start_ack_timer(void);
void stop_ack_timer(void);
void enable_network_layer(void);
void disalbe_network_layer(void);
insira o código aqui
#define inc(k) if(k<MAX_SEQ) k++; else k=0
Exemplos de protocolos e códigos
Pipelining e recuperação de erros. Efeito de um erro quando (a) o tamanho da janela receptora é igual a 1 e quando (b) o tamanho da janela receptora é grande

Nota sobre esclarecimento:
Na pratica esses protocolos são utilizados de forma embutida nos hardwares responsáveis pela transmissão e recepção dos dados, e são
abstraídos das camadas mais próximas do usuário final, por isso passa desapercebido.
Agradecimento especial a Tanenbaum