algorithm - telecomunicaciones - tecnicas de correccion de errores
Codificación/Desafío de corrección de errores (7)
¿Es matemáticamente factible codificar un mensaje inicial de 4 bytes en 8 bytes y si uno de los 8 bytes se elimina completamente y otro es incorrecto para reconstruir el mensaje inicial de 4 bytes? No habría manera de retransmitir ni se conocería la ubicación del byte descartado.
Si uno usa la corrección de errores Reed Solomon con 4 bytes de "paridad" agregados al final de los 4 bytes de "datos", como DDDDPPPP, y termina con DDDEPPP (donde E es un error) y se ha eliminado un byte de paridad , No creo que haya una manera de reconstruir el mensaje inicial (aunque me corrija si me equivoco) ...
¿Qué hay de multiplicar (o realizar otra operación matemática) el mensaje inicial de 4 bytes por una constante, y luego utilizar las propiedades de una operación matemática inversa para determinar qué byte se eliminó? O bien, imponga algunas restricciones en la estructura del mensaje para que todos los demás bytes sean impares y los demás sean uniformes.
Alternativamente, en lugar de bytes, también podrían ser 4 dígitos decimales codificados de alguna manera en 8 dígitos decimales donde los errores podrían detectarse y corregirse en las mismas circunstancias mencionadas anteriormente: no se conoce la transmisión y no se conoce la ubicación del byte perdido.
Estoy buscando ideas locas que alguien pueda tener ... ¿Alguna idea por ahí?
EDITAR:
Puede ser un poco artificial, pero la situación que estoy tratando de resolver es una en la que tiene, digamos, una impresora defectuosa que imprime números importantes en un formulario, que luego se envía por correo a una empresa de procesamiento que utiliza OCR Para leer los formularios. El OCR no va a ser perfecto, pero debería acercarse con solo dígitos para leer. La impresora defectuosa puede ser un problema mayor, donde puede caer un número entero, pero no hay forma de saber cuál caerá, pero siempre saldrán en el orden correcto, no se intercambiarán ningún dígito.
El formulario podría modificarse para que siempre imprima un espacio entre los cuatro números iniciales y los números de corrección de errores, es decir, 1234 5678, para que se sepa si se eliminó un dígito inicial de 1234 o un dígito de corrección de errores 5678, si hace que el problema sea más fácil de resolver. Estoy pensando en algo similar a cómo verifican los números de las tarjetas de crédito mediante un algoritmo, pero en trozos de cuatro dígitos.
Con suerte, eso proporciona alguna aclaración sobre lo que estoy buscando ...
Creo que necesitarías estudiar qué códigos de borrado te podrían ofrecer. Yo no conozco ningún límite, pero tal vez algún tipo de código MDS pueda lograr esto.
EDITAR: Después de una búsqueda rápida encontré la biblioteca RSCode y en el example 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í que parece que el código Reed-Solomon es la respuesta y que en realidad puede obtener una recuperación de un borrado y un error en el código 8,4.
En ausencia de una estructura algebraica "bonita", sospecho que va a ser difícil encontrar un esquema conciso que le permita llegar a 10 ** 4 palabras de código, ya que, teóricamente, no hay mucha holgura. (El de abajo puede usar GF (5) para 5 ** 5 = 3125.) Afortunadamente, el problema es lo suficientemente pequeño como para que puedas probar el codicioso método de construcción de códigos de Shannon (encuentra una palabra en clave que no entre en conflicto con una ya elegida, añadirlo al conjunto).
Codifique hasta 35 bits como un polinomio quártico f sobre GF (128). Evalúe el polinomio en ocho puntos predeterminados x0, ..., x7 y codifique como 0f (x0) 1f (x1) 0f (x2) 1f (x3) 0f (x4) 1f (x5) 0f (x6) 1f (x7), donde los ceros alternos y unos están almacenados en el MSB.
Cuando decodifiques, primero mira los MSBs. Si el MSB no coincide con el mod de índice 2, entonces ese byte está dañado y / o se ha desplazado hacia la izquierda por una eliminación. Supongamos que es bueno y gírelo hacia la derecha (posiblemente acumulando múltiples valores posibles diferentes en un punto). Ahora tenemos al menos siete evaluaciones de un polinomio quártico en puntos conocidos, de los cuales uno es corrupto. Ahora podemos probar todas las posibilidades de la corrupción.
EDIT: bmm6o ha adelantado la afirmación de que la segunda parte de mi solución es incorrecta. Estoy en desacuerdo.
Revisemos las posibilidades para el caso donde los MSB son 0101101. Supongamos que X es la matriz de bytes enviados y Y es la matriz de bytes recibidos. Por un lado, Y [0], Y [1], Y [2], Y [3] tienen MSB correctos y se presume que son X [0], X [1], X [2], X [3] . Por otro lado, Y [4], Y [5], Y [6] tienen MSB incorrectos y se presume que son X [5], X [6], X [7].
Si X [4] se cae, entonces tenemos siete evaluaciones correctas de f.
Si X [3] se cae y X [4] se corrompe, entonces tenemos una evaluación incorrecta en 3 y seis evaluaciones correctas.
Si X [5] se cae y X [4] se corrompe, entonces tenemos una evaluación incorrecta en 5 y seis evaluaciones correctas.
Hay más posibilidades además de estas, pero nunca tenemos menos de seis evaluaciones correctas, lo que es suficiente para recuperar f.
En el caso de los dígitos decimales, suponiendo que uno va con el primer dígito impar, el segundo dígito par, el tercer dígito impar, etc. - con dos dígitos, obtiene 00-99, que se puede representar en 3 dígitos impares / pares / impares (125 en total combinaciones) - 00 = 101, 01 = 103, 20 = 181, 99 = 789, etc. Así que uno codifica dos conjuntos de dígitos decimales en 6 dígitos totales, luego los dos últimos dígitos significan cosas sobre los primeros conjuntos de 2 dígitos o suma de comprobación de algún tipo ... El siguiente al último dígito, supongo, podría ser algún tipo de indicador par / impar en cada uno de los mensajes iniciales de 2 dígitos iniciales (1 = incluso los 2 primeros dígitos, 3 = los primeros dos dígitos impares) y sigue el patrón de ser extraño. Entonces, el último dígito podría ser el lugar de una suma de los dígitos individuales, de esa manera, si faltara un dígito, sería inmediatamente aparente y podría corregirse suponiendo que el último dígito fuera correcto. Aunque, tiraría cosas si uno de los últimos dos dígitos se cayera ...
En realidad, como dijo Krystian, cuando corrijas un código RS, tanto el mensaje Y los bytes de "paridad" se corregirán, siempre que tengas v + 2e <(nk) donde v es el número de borrados (conoces la posición ) y e es el número de errores. Esto significa que si solo tiene errores, puede corregir hasta (nk) / 2 errores, o (nk-1) borrados (aproximadamente el doble del número de errores), o una combinación de ambos (vea el artículo de Blahut: Transformar técnicas para códigos de control de errores y un decodificador universal Reed-Solomon ).
Lo que es aún mejor es que puede verificar que la corrección fue exitosa: al verificar que el polinomio del síndrome solo contiene 0 coeficientes, sabe que los bytes del mensaje + paridad son correctos. Puede hacerlo antes para verificar si el mensaje necesita alguna corrección, y también puede hacer la verificación después de la decodificación para verificar que tanto el mensaje como los bytes de paridad se repararon por completo.
El límite v + 2e <(nk) es óptimo, no puede hacerlo mejor (por eso Reed-Solomon se llama un código de corrección de errores óptimo). De hecho, es posible ir más allá de este límite utilizando enfoques de fuerza bruta, hasta cierto punto (puedes ganar 1 o 2 símbolos más por cada 8 símbolos) usando la decodificación de listas , pero aún es un dominio en su infancia, no sé De cualquier implementación práctica que funcione.
Los códigos de corrección de errores pueden, en general, manejar borrados, pero en la literatura se asume que se conoce la posición del borrado. En la mayoría de los casos, el demodulador introducirá el borrado cuando haya poca confianza en que se puedan recuperar los datos correctos del canal. Por ejemplo, si la señal no es claramente 0 o 1, el dispositivo puede indicar que los datos se perdieron, en lugar de arriesgar la introducción de un error. Dado que un borrado es esencialmente un error con una posición conocida, son mucho más fáciles de corregir.
No estoy seguro de cuál es su situación en la que puede perder un solo valor y aún puede estar seguro de que los valores restantes se entregan en el orden correcto, pero no es una situación que aborda la teoría de la codificación clásica.
Lo que sugiere la algorítmica anterior es esto: si puede limitarse a solo 7 bits de información, puede completar el octavo bit de cada byte con la alternancia de 0 y 1, lo que le permitirá conocer la ubicación del byte faltante. Es decir, ponga un 0 en el bit alto de los bytes 0, 2, 4, 6 y un 1 en los bits altos de los otros. En el extremo receptor, si solo recibe 7 bytes, el que faltó se habrá eliminado de entre los bytes cuyos bits altos coinciden. Desafortunadamente, eso no es del todo correcto: si el borrado y el error son adyacentes, no se puede saber de inmediato qué byte se eliminó. Por ejemplo, los bits altos 0101101 podrían resultar de la caída del 4to byte, de un error en el 4º byte y de la 3ª entrada, o de un error en el 4º byte y de la 5ª entrada.
Podrías usar 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, enviará datos como (a, b, c, d, b + c + d, a + c + d, a + b + d, a + b + c) (donde la adición se implementa con XOR, ya que a, b, c, d son elementos de GF (128))). Es un código lineal con distancia 4, por lo que puede corregir un error de un solo byte. Puede decodificar con la decodificación del síndrome y, como el código es auto-dual, la matriz H será la misma que la anterior.
En el caso de que haya un byte perdido, puede utilizar la técnica anterior para determinar cuál es. Una vez que haya determinado eso, básicamente estará decodificando un código diferente: el código "perforado" creado al eliminar ese byte dado. Dado que el código perforado aún es lineal, puede usar la decodificación del síndrome para determinar el error. Tendría que calcular la matriz de comprobación de paridad para cada uno de los códigos abreviados, pero puede hacerlo antes de tiempo. El código acortado tiene la distancia 3, por lo que puede corregir cualquier error de un solo byte.
Los códigos de paridad funcionan siempre que dos bytes de datos diferentes no se vean afectados por un error o una pérdida y mientras que el error no sea igual a ningún byte de datos mientras se pierda un byte de paridad, imho.
Parece ser teóricamente posible si asumimos un error de 1 bit en un byte incorrecto. Necesitamos 3 bits para identificar el byte perdido y 3 bits para identificar el byte incorrecto y 3 bits para identificar el bit incorrecto. Tenemos 3 veces más bits adicionales.
Pero si necesitamos identificar cualquier error de número de bits en un byte incorrecto, se trata de 30 bits. Incluso eso parece ser posible con 32 bits, aunque 32 está demasiado cerca para mi comodidad.
Pero no sé caliente para codificar para conseguir eso. Trate de turbocódigo?