Qual seria uma generalização natural de uma verificação de paridade de bytes?

Question

Suponha que tenhamos um grupo de n bytes. Pode-se adicionar uma verificação muito básica (e não particularmente confiável) da consistência desses dados armazenando um byte adicional (N + 1) contendo XOR exclusivo de todos os bytes originais. Será suficiente para detectar um único erro de byte durante a transmissão.

No problema prático que estou tentando resolver, se ocorrer um erro durante a transmissão, eu realmente saberei quando o erro ocorreu e qual byte contém o erro. Em seguida, o conhecimento do byte (N + 1) é suficiente para recuperar o byte incorreto simplesmente xoring todos os bytes corretos com o (n + 1) o byte.

Os erros que podem ocorrer no meu aplicativo realmente ocorrem em rajadas de 1 ou vários bytes, eu denotarei esse número como M. Não pode haver mais do que uma única explosão por grupo de n bytes. Na verdade, quando ocorre um erro, meu canal de transmissão retorna N-M bytes, juntamente com o marcador da posição onde os bytes foram perdidos.

Minha pergunta é: O que seria (existe?) Uma maneira natural de generalizar o esquema de correção de erros simples (m= 1) usando um único byte XOR para o caso em que a explosão de erro pode conter bytes ignorados? É possível fazer este tipo específico de correção de erros usando apenas m bytes?

Answer 1

para $ i \ in \ {0, \ ldots, m-1 \} $ , adicione um novo byte que é a soma (ou xor) de cadaByte cujo índice é igual a $ i $ mod $ m $ .Por exemplo, se $ m= 2 $ , um byte é a soma de todos os bytes nas posições uniformes, e a outra é a soma de todos os bytes emas posições ímpares.Como as rajadas têm comprimento no máximo $ m $ , cada uma dessas somas só irá perder um único byte.