Codificación / corrección de errores Challenge

Question

Es matemáticamente posible para codificar y el mensaje inicial de 4 bytes en 8 bytes y si uno de los 8 bytes se cayó por completo y otro está mal para reconstruir el mensaje inicial de 4 bytes? No habría manera de retransmitir ni tampoco la ubicación del byte caído ser conocido.

Si se utiliza la corrección de errores Reed Solomon con 4 "paridad" bytes viraron a finales de los 4 bytes de "datos", como DDDDPPPP, y se acaba con DDDEPPP (donde E es un error) y un byte de paridad se ha caído, no creo que hay una manera de reconstruir el mensaje inicial (aunque me corrija si estoy equivocado) ...

¿Qué hay de multiplicar (o realizar otra operación matemática) el mensaje inicial 4 byte por una constante, entonces la utilización de propiedades de una operación matemática inversa para determinar lo que se dejó caer byte. O, imponer algunas restricciones sobre la estructura del mensaje para cada byte otras necesidades de ser extraño y los otros tienen que ser par.

Alternativamente, en lugar de bytes, también podría ser de 4 dígitos decimales codificados en una cierta manera en 8 dígitos decimales en que los errores pueden ser detectados y corregidos en las mismas circunstancias mencionadas anteriormente - no retransmisión y la ubicación del byte caído no se conoce .

Estoy buscando cualquier ideas locas que nadie pueda tener ... ¿Alguna idea por ahí?

EDIT:

Puede que sea un poco artificial, pero la situación que estoy tratando de resolver es una de las que tiene, digamos, una impresora defectuosa que imprime los números importantes en un formulario, que se envían luego a una empresa de procesamiento que utiliza OCR para leer los formularios. El OCR no va a ser perfecto, pero debe acercarse con sólo dígitos para leer. La impresora defectuosa podría ser un problema más grande, donde puede caer un número entero, pero no hay forma de saber cuál va a caer, pero siempre va a salir en el orden correcto, no habrá ningún dígito intercambiadas.

La forma puede ser alterado de modo que siempre se imprime un espacio entre los cuatro números iniciales y los números de corrección de errores, es decir, 1234 5678, de modo que uno podría saber si se dejó caer un dígito inicial 1234 o se dejó caer un dígito corrección 5678 error , si eso tiene el problema más fácil de resolver. Estoy pensando en algo similar a la forma en que verifican los números de tarjetas de crédito a través de algoritmos, pero en cuatro trozos dígitos.

Con suerte, que proporciona una aclaración en cuanto a lo que estoy buscando ...

Answer 1

A falta de "buena" estructura algebraica, sospecho que va a ser difícil encontrar un esquema conciso que te lleva todo el camino hasta 10 ** 4 palabras de código, ya que la información teóricamente, no hay mucho de holgura. (La de abajo puede utilizar GF (5) durante 5 ** 5 = 3125.) Afortunadamente, el problema es lo suficientemente pequeño que puede probar el método de código de construcción codiciosos de Shannon (encontrar una palabra en clave que no entre en conflicto con otro ya elegidos, añadirlo a la serie).

---

codificar hasta 35 bits como un polinomio f quartic sobre GF (128). Evaluar el polinomio en ocho puntos predeterminados x0, ..., X7 y codificar como 0f (x0) 1f (x1) 0f (x2) 1f (x3) 0f (x4) 1f (x5) 0f (x6) 1f (x7), donde los ceros y los alternantes se almacenan en el MSB.

En la decodificación, primer vistazo a los MSB. Si el MSB no coincide con el índice de mod 2, entonces ese byte es corrupto y / o que ha sido desplazado a la izquierda una deleción. Asumir que es bueno y cambiar de nuevo a la derecha (posiblemente la acumulación de múltiples valores diferentes posibles en un punto). Ahora tenemos al menos siete evaluaciones de un polinomio de cuarto grado f en los puntos conocidos, de los cuales como máximo uno es corrupto. Ahora podemos probar todas las posibilidades para la corrupción.

EDIT: bmm6o ha avanzado la afirmación de que la segunda parte de mi solución es incorrecta. No estoy de acuerdo.

Repasemos las posibilidades para el caso en que los MSBs son 0101101. Supongamos que X es la matriz de bytes enviados e Y es la matriz de bytes recibidos. Por un lado, Y [0], Y [1], Y [2], Y [3] tienen MSBs correctas y se presume que X [0], X [1], X [2], X [3] . Por otro lado, Y [4], Y [5], Y [6] tener MSBs incorrectas y se supone que son X [5], X [6], X [7].

Si X [4] se cae, entonces tenemos evaluaciones correctas siete de f.

Si X [3] se deja caer y X [4] está dañado, entonces tenemos una evaluación incorrecta a los 3, y seis evaluaciones correctas.

Si X [5] se deja caer y X [4] está dañado, entonces tenemos una evaluación incorrecta a los 5, y seis evaluaciones correctas.

Existen más posibilidades además de éstos, pero nunca tienen menos de seis evaluaciones correctas, lo que es suficiente para recuperar f.

Answer 2

creo que tendría que estudiar lo que códigos de borrado que podrían ofrecer. Yo no conozco a ningún límites a mí mismo, pero tal vez algún tipo de código MDS podría lograr esto.

EDIT: Después de una búsqueda rápida he encontrado RSCode biblioteca y en el ejemplo dice 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.

Así se parece código Reed-Solomon es de hecho la respuesta y en realidad se puede conseguir la recuperación de un borrado y un error en el código de 8,4.

Answer 3

códigos de paridad funciona tanto como dos bytes de datos diferentes, no se ven afectados por errores o pérdida y siempre que el error no es igual a cualquier byte de datos, mientras que un byte de paridad se ha perdido, en mi humilde opinión.

Answer 4

códigos de corrección de error puede en borraduras generales de manejar, pero en la literatura se supone conocida la posición de la borradura. En la mayoría de los casos, el borrado será presentado por el demodulador cuando hay poca confianza de que los datos correctos se pueden recuperar desde el canal. Por ejemplo, si la señal no es claramente 0 o 1, el dispositivo puede indicar que los datos se perdió, en lugar de correr el riesgo de la introducción de un error. Desde un borrado es esencialmente un error con una posición conocida, son mucho más fáciles de solucionar.

No estoy seguro de lo que su situación es donde se puede perder un solo valor y todavía se puede estar seguro de que los valores restantes se entregan en el orden correcto, pero no es una situación clásica de codificación de direcciones de teoría.

¿Qué algorithmist se sugiere más arriba es la siguiente: Si se puede restringirse a sólo 7 bits de información, se puede llenar el octavo bit de cada byte con la alternancia de 0 y 1, lo que le permitirá conocer la ubicación del byte falta . Es decir, poner un 0 en el bit alto de bytes 0, 2, 4, 6 y un 1 en los bits altos de los otros. En el extremo receptor, si sólo se recibe 7 bytes, la falta se le han caído de entre los bytes cuyos bits de mayor altura. Por desgracia, eso no es del todo bien: si el borrado y el error son adyacentes, no se puede saber de inmediato que se ha colocado bytes. Por ejemplo, bits altos 0101101 podrían ser el resultado de dejar caer el cuarto byte, o de un error en el 4º byte y soltando el tercero, o de un error en el 4º byte y soltando el quinto.

Se podría utilizar el código lineal:

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

(es decir, se le envía datos como (a, b, c, d, b + c + d, a + c + d, a + b + d, a + b + c) (donde además se implementa con XOR, ya que a, b, c, d son elementos de GF (128))). Es un código lineal con la distancia 4, para que pueda corregir un error de un solo byte. Puede decodificar con síndrome de decodificación , y puesto que el código es auto-dual, la matriz H será el mismo que el anterior.

En el caso donde hay un byte caído, se puede utilizar la técnica anterior para determinar de cuál se trata. Una vez que haya determinado que, básicamente estás decodificar un código diferente - el código "pinchado" creado por dejar caer ese byte dado. Dado que el código perforado sigue siendo lineal, se puede usar el síndrome de decodificación para determinar el error. Usted tendría que calcular el href="http://en.wikipedia.org/wiki/Parity-check_matrix" rel="nofollow noreferrer"> de control de paridad matriz

Answer 5

En el caso de dígitos decimales, asumiendo que uno va con el primer dígito impar, segundo dígito, incluso, tercer dígito impar, etc - con dos dígitos, se obtiene 00-99, que se puede representar en 3 incluso / dígitos impares impares / (125 combinaciones en total) - 00 = 101, 01 = 103, 20 = 181, 99 = 789, etc. así que uno codifica dos conjuntos de dígitos decimales en 6 dígitos total, entonces los dos últimos dígitos Signify cosas acerca de los primeros conjuntos de 2 dígitos o una suma de comprobación de algún tipo ... El penúltimo dígito, supongo, podría ser algún tipo de indicador de par / impar en cada uno de los mensajes iniciales de 2 dígitos iniciales (1 = incluso primeros 2 dígitos, 3 = impar dos primeros dígitos) y seguir el patrón de ser impar. Entonces, el último dígito podría ser el lugar de la de la suma de los dígitos individuales, de esa manera, si un dígito faltaba, sería inmediatamente evidente y podría ser corregido suponiendo que el último dígito era correcta. Aunque, sería tirar cosas fuera de si uno de los dos últimos dígitos se dejaron caer ...

Answer 6

Parece ser teóricamente posible si asumimos error de 1 bit en el byte equivocado. Necesitamos 3 bits para identificar los bits byte caído y 3 para identificar bytes mal y 3 bits para identificar poco mal. Tenemos 3 veces mayor que la cantidad de bits adicionales.

Pero si tenemos que identificar cualquier número de bits de error en el byte mal, se trata de 30 bits. Incluso parece ser que es posible con 32 bits, aunque 32 es un poco demasiado cerca para mi comodidad.

Pero no sé caliente para codificar para conseguir eso. Trate turbocode?

Answer 7

En realidad, como dijo Krystian, cuando corrija un código RS, serán corregidos tanto el mensaje como los bytes de "paridad", siempre y cuando tenga v + 2e <(NK), donde v es el número de borrones que ( conocer la posición) y e es el número de errores. Esto significa que si sólo tiene errores, puede corregir hasta (nk) / 2 errores, o (NK-1) borraduras (aproximadamente el doble del número de errores), o una mezcla de ambos (véase artículo de Blahut: Transformar técnicas para los códigos de control de errores y < a href = "http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.84.2084&rep=rep1&type=pdf" rel = "nofollow"> un universales decodificador Reed-Solomon ).

Lo que es aún más bonito es que se puede comprobar que la corrección se ha realizado correctamente: comprobando que el polinomio síndrome sólo contiene 0 coeficientes, usted sabe que los bytes de paridad mensaje + son ambos correctos. Puede hacerlo antes de comprobar si el mensaje necesita ninguna corrección, y también se puede hacer el registro de entrada después de la decodificación para comprobar que tanto el mensaje y los bytes de paridad fueron completamente reparados.

El límite v + 2e <(n-k) es óptima, no se puede hacer mejor (por eso Reed-Solomon se llama un código de corrección de errores óptima). De hecho, es posible ir más allá de este límite se aproxima usando fuerza bruta, hasta un cierto punto (se puede ganar 1 o 2 símbolos más por cada 8 símbolos) usando lista de decodificación , pero aún así es un dominio en su infancia, no sé de cualquier aplicación práctica que funciona.