Desafio de Codificação / Correção de Erros

Question

É matematicamente viável codificar e a mensagem inicial de 4 bytes em 8 bytes e se um dos 8 bytes estiver completamente descartado e outro está errado em reconstruir a mensagem inicial de 4 bytes? Não haveria maneira de retransmitir nem a localização do byte caído.

Se alguém usa a correção de erro de Reed Solomon com 4 "paridade" bytes presos no final dos 4 "dados" bytes, como ddddppp, e você acaba com dddeppp (onde e é um erro) e um byte de paridade foi descartado , Não acredito que haja uma maneira de reconstruir a mensagem inicial (embora me corrija se eu estiver errado) ...

Que tal multiplicar (ou executar outra operação matemática) a mensagem inicial de 4 bytes por uma constante e depois utilizar propriedades de uma operação matemática inversa para determinar qual byte foi descartado. Ou impor algumas restrições à estrutura da mensagem para que todos os outros bytes precisem ser estranhos e os outros precisam ser uniformes.

Como alternativa, em vez de bytes, também pode ser 4 dígitos decimais codificados de alguma maneira em 8 dígitos decimais, onde os erros podem ser detectados e corrigidos nas mesmas circunstâncias mencionadas acima - nenhuma retransmissão e a localização do byte caído não é conhecido.

Estou procurando alguma idéias malucas que alguém possa ter ... alguma idéia por aí?

EDITAR:

Pode ser um pouco artificial, mas a situação que estou tentando resolver é aquela onde você tem, digamos, uma impressora defeituosa que imprime números importantes em um formulário, que são enviados por correio para uma empresa de processamento que usa OCR para ler os formulários. O OCR não será perfeito, mas deve chegar perto de apenas dígitos para ler. A impressora defeituosa pode ser um problema maior, onde pode cair um número inteiro, mas não há como saber qual deles cairá, mas eles sempre serão lançados na ordem correta, não haverá dígitos trocados.

O formulário pode ser alterado para que sempre imprima um espaço entre os quatro números iniciais e os números de correção de erros, ou seja, 1234 5678, para que se soubesse se um dígito inicial de 1234 foi descartado ou um dígito de correção de erro 5678 foi descartado, se isso facilita a solução do problema. Estou pensando um pouco parecido com a forma como eles verificam os números de cartão de crédito via algoritmo, mas em quatro dígitos.

Felizmente, isso fornece alguns esclarecimentos sobre o que estou procurando ...

Answer 1

Na ausência de uma estrutura algébrica "agradável", suspeito que será difícil encontrar um esquema conciso que o leve a 10 ** 4 filhos de código, já que a informação teoricamente, não há muita folga. (O abaixo pode usar GF (5) para 5 ** 5 = 3125.) Felizmente, o problema é pequeno o suficiente para que você possa experimentar o método ganancioso de construção de código de Shannon (encontre um filhote de código que não conflito com um já escolhido, adicione -o ao conjunto).

---

Encoda até 35 bits como um polinomial quartico F sobre GF (128). Avalie o polinômio em oito pontos predeterminados x0, ..., x7 e codifique como 0f (x0) 1f (x1) 0f (x2) 1f (x3) 0f (x4) 1f (x5) 0f (x6) 1f (x7), onde os zeros alternados e os são armazenados no MSB.

Ao decodificar, primeiro olhe para os MSBs. Se o MSB não corresponder ao Index Mod 2, esse byte será corrupto e/ou foi deslocado deixado por uma exclusão. Suponha que seja bom e volte para a direita (possivelmente acumulando vários valores possíveis diferentes em um ponto). Agora, temos pelo menos sete avaliações de um polinomial quartico em pontos conhecidos, dos quais no máximo um é corrupto. Agora podemos tentar todas as possibilidades para a corrupção.

EDIT: BMM6O avançou a alegação de que a segunda parte da minha solução está incorreta. Discordo.

Vamos revisar as possibilidades para o caso em que os MSBs são 0101101. Suponha que X seja a matriz de bytes enviados e Y é a matriz de bytes recebidos. Por um lado, y [0], y [1], y [2], y [3] têm MSBs corretos e presume -se que seja x [0], x [1], x [2], x [3] . Por outro lado, y [4], y [5], y [6] têm MSBs incorretos e presume -se que seja x [5], x [6], x [7].

Se x [4] for descartado, temos sete avaliações corretas de f.

Se x [3] for descartado e x [4] for corrompido, temos uma avaliação incorreta em 3 e seis avaliações corretas.

Se x [5] for descartado e x [4] for corrompido, temos uma avaliação incorreta em 5 e seis avaliações corretas.

Existem mais possibilidades além dessas, mas nunca temos menos de seis avaliações corretas, que basta para recuperar f.

Answer 2

Eu acho que você precisaria estudar o que códigos de apagamento pode oferecer a você. Não conheço nenhum limite, mas talvez algum tipo de código MDS possa conseguir isso.

Editar: Após uma pesquisa rápida, encontrei Rscode biblioteca e no exemplo isso diz que

In general, with E errors, and K erasures, you will need
* 2E + K bytes of parity to be able to correct the codeword
* back to recover the original message data.

Portanto, parece que o código Reed-Solomon é realmente a resposta e você pode realmente recuperar um apagamento e um erro em 8,4.

Answer 3

Os códigos de paridade funcionam enquanto dois bytes de dados diferentes não forem afetados por erro ou perda e, desde que o erro não seja igual a nenhum byte de dados enquanto um byte de paridade é perdido, o IMHO.

Answer 4

Os códigos de correção de erro podem, em geral, manipular apagamentos, mas na literatura a posição do apagamento é assumida conhecida. Na maioria dos casos, o apagamento será introduzido pelo desmodulador quando houver baixa confiança de que os dados corretos podem ser recuperados do canal. Por exemplo, se o sinal não estiver claramente 0 ou 1, o dispositivo poderá indicar que os dados foram perdidos, em vez de arriscar a introdução de um erro. Como um apagamento é essencialmente um erro com uma posição conhecida, eles são muito mais fáceis de corrigir.

Não tenho certeza de qual é a sua situação em que você pode perder um único valor e ainda pode ter certeza de que os valores restantes são entregues na ordem correta, mas não é uma situação que a teoria da codificação clássica aborda.

O que o algoritmista está sugerindo acima é o seguinte: se você pode se restringir a apenas 7 bits de informação, poderá preencher o 8º bit de cada byte com 0 e 1 alternados, o que permitirá que você conheça a colocação do byte ausente. Ou seja, coloque um 0 no alto bit de bytes 0, 2, 4, 6 e 1 nos altos bits dos outros. No final do recebimento, se você receber apenas 7 bytes, o faltando será retirado entre os bytes cujos bits altos correspondem. Infelizmente, isso não está certo: se o apagamento e o erro são adjacentes, você não pode saber imediatamente qual byte foi descartado. Por exemplo, os bits altos 0101101 podem resultar de abandonar o 4º byte, ou de um erro no 4º byte e cair o 3º, ou de um erro no 4º byte e cair o 5º.

Você pode usar o código linear:

1 0 0 0  0 1 1 1
0 1 0 0  1 0 1 1
0 0 1 0  1 1 0 1
0 0 0 1  1 1 1 0

(ou seja, você enviará dados como (a, b, c, d, b+c+d, a+c+d, a+b+d, a+b+c) (onde a adição é implementada com xor, já que A, B, C, D são elementos de GF (128))). É um código linear com a distância 4, para que possa corrigir um erro de byte. Você pode decodificar com decodificação da síndrome, e como o código é auto-dual, a matriz H será a mesma que acima.

No caso em que há um byte caído, você pode usar a técnica acima para determinar qual é. Depois de determinar isso, você está essencialmente decodificando um código diferente - o código "perfurado" criado soltando esse byte dado. Como o código perfurado ainda é linear, você pode usar a decodificação da síndrome para determinar o erro. Você teria que calcular o Matriz de verificação de paridade Para cada um dos códigos encurtados, mas você pode fazer isso com antecedência. O código reduzido tem a distância 3, para que possa corrigir qualquer erro de bytes.

Answer 5

No caso de dígitos decimais, assumindo que um acompanha o primeiro dígito ímpar, segundo dígito, mesmo, terceiro dígito ímpar, etc - com dois dígitos, você obtém 00-99, que pode ser representado em 3 dígitos ímpares/ímpares (125 no total Combinações) - 00 = 101, 01 = 103, 20 = 181, 99 = 789, etc. Portanto, codifica dois conjuntos de dígitos decimais em 6 dígitos no total, então os dois últimos dígitos significam coisas sobre os primeiros conjuntos de 2 dígitos ou A Soma de verificação de algum tipo ... o próximo ao último dígito, suponho, pode ser algum tipo de indicador ímpar/uniforme em cada uma das mensagens iniciais iniciais iniciais de 2 dígitos (1 = até 2 primeiros dígitos, 3 = ímpares de dois primeiros dígitos) e Siga o padrão de ser estranho. Então, o último dígito pode ser o local de uma soma dos dígitos individuais, assim se um dígito estivesse faltando, seria imediatamente aparente e poderia ser corrigido assumindo que o último dígito estava correto. Embora, isso jogaria as coisas se um dos dois últimos dígitos fosse descartado ...

Answer 6

Parece ser teoricamente possível se assumirmos um erro de 1 bit no byte errado. Precisamos de 3 bits para identificar byte caído e 3 bits para identificar bytes errados e 3 bits para identificar o bit errado. Temos 3 vezes que muitos pedaços extras.

Mas se precisarmos identificar qualquer número de erros de bits em byte errado, ele chega a 30 bits. Mesmo isso parece ser possível com 32 bits, embora 32 esteja um pouco perto demais para o meu conforto.

Mas eu não sei quente para codificar para conseguir isso. Experimente o turbocódigo?

Answer 7

Na verdade, como Krystian disse, quando você corrige um código RS, a mensagem e os bytes de "paridade" serão corrigidos, desde que você tenha v+2e <(nk) onde v é o número de apagamentos (você sabe a posição ) e E é o número de erros. Isso significa que, se você tiver apenas erros, poderá corrigir erros até (NK)/2, ou (NK-1) apaga (sobre o dobro do número de erros) ou uma mistura de ambos (ver Artigo de Blahut: Técnicas de transformação para códigos de controle de erros e Um decodificador universal de Reed-Solomon).

O que é ainda mais agradável é que você pode verificar se a correção foi bem -sucedida: ao verificar se o polinômio da síndrome contém apenas 0 coeficientes, você sabe que a mensagem+paridade bytes estão corretos. Você pode fazer isso antes para verificar se a mensagem precisa de alguma correção e também pode fazer a verificação após a decodificação para verificar se a mensagem e os bytes de paridade foram completamente reparados.

O v+2e ligado <(nk) é ideal, você não pode fazer melhor (é por isso que o Reed-Solomon é chamado de código de correção de erro ideal). De fato, é possível ir além desse limite usando abordagens de fortaleza bruta, até um determinado ponto (você pode ganhar 1 ou 2 símbolos para cada 8 símbolos) usando listar decodificação, mas ainda é um domínio em sua infância, não conheço nenhuma implementação prática que funcione.