En el algoritmo de Welch-Berlekamp para decodificar códigos Reed-Solomon, a uno se le da una lista de puntos representan un mensaje con errores en en ubicaciones desconocidas (y se le da al algoritmo). La salida es un polinomio que pasa por todos los puntos dados, excepto aquellos en los que se produjeron errores.
El método implica resolver un sistema de ecuaciones lineales de la forma
para toda , donde tiene un grado y tiene un grado en la mayoría . Las variables son los coeficientes de y .
Para asegurarse de que tenga un grado generalmente se agrega la restricción de que el coeficiente de es 1 al sistema lineal anterior. Sin embargo, en la práctica uno no necesariamente sabe . Una forma ineficiente (pero aún de tiempo polinomial) de lidiar con esto es probar para todos los valores que comienzan con bajando hasta encontrar una solución.
Mi pregunta es: ¿hay una forma más eficiente de determinar ? Alternativamente, ¿hay alguna modificación en el sistema lineal que le permita a uno usar un límite superior en lugar del valor exacto?
En particular, quiero usar este decodificador específico para códigos Reed-Solomon, y no un algoritmo completamente diferente basado en otras técnicas.
En respuesta a la respuesta de DW, aquí está mi ejemplo de trabajo. Todo se hace módulo 7.
plain message is: [2, 3, 2]
polynomial is: 2 + 3 t^1 + 2 t^2
encoded message is: [[0, 2], [1, 0], [2, 2], [3, 1], [4, 4]]
corrupted message is: [[0, 2], [1, 0], [2, 3], [3, 1], [4, 4]]
Entonces el error está en el tercer punto.
Cuando la ecuación polinómica en cuestión es
Y al enchufar obtiene el sistema en forma de matriz:
[2, 0, 0, 6, 0, 0, 0, 0, 0]
[0, 0, 0, 6, 6, 6, 6, 6, 0]
[3, 6, 5, 6, 5, 3, 6, 5, 0]
[1, 3, 2, 6, 4, 5, 1, 3, 0]
[4, 2, 1, 6, 3, 5, 6, 3, 0]
[0, 0, 1, 0, 0, 0, 0, 0, 1]
La última fila es la restricción de que . Aplicando la eliminación gaussiana obtenemos
[1, 0, 0, 0, 0, 0, 1, 4, 0]
[0, 1, 0, 0, 0, 0, 3, 3, 1]
[0, 0, 1, 0, 0, 0, 0, 0, 1]
[0, 0, 0, 1, 0, 0, 2, 1, 0]
[0, 0, 0, 0, 1, 0, 2, 2, 5]
[0, 0, 0, 0, 0, 1, 4, 5, 2]
Y eligiendo 1 para ambas variables libres obtenemos un vector de solución de
[2, 2, 1, 4, 1, 0, 1, 1]
Lo que se traduce en
E is 2 + 2 t^1 + 1 t^2
Q is 4 + 1 t^1 + 0 t^2 + 1 t^3 + 1 t^4
Y no divide Q . Tenga en cuenta que Q factores como ( t + 6 ) ( t 3 + 2 t 2 + 2 t + 3 )
Para obtengo una buena solución:
system is:
[2, 0, 6, 0, 0, 0, 0]
[0, 0, 6, 6, 6, 6, 0]
[3, 6, 6, 5, 3, 6, 0]
[1, 3, 6, 4, 5, 1, 0]
[4, 2, 6, 3, 5, 6, 0]
[0, 1, 0, 0, 0, 0, 1]
reduced system is:
[1, 0, 0, 0, 0, 0, 5]
[0, 1, 0, 0, 0, 0, 1]
[0, 0, 1, 0, 0, 0, 3]
[0, 0, 0, 1, 0, 0, 3]
[0, 0, 0, 0, 1, 0, 6]
[0, 0, 0, 0, 0, 1, 2]
solution is [5, 1, 3, 3, 6, 2]
Q is 3 + 3 t^1 + 6 t^2 + 2 t^3
E is 5 + 1 t^1
P(x) = 2 + 3 t^1 + 2 t^2 # this is correct!
r(x) = 0
Tenga en cuenta que si bien el contraejemplo anterior fue generado por el código que escribí desde cero (básicamente fue lo primero que probé), uno puede verificar que las soluciones sean válidas a mano, por lo que incluso si mi código tiene errores, sigue siendo un contraejemplo válido para el reclamo que usando funciona.
fuente
Respuestas:
El mismo procedimiento realmente funciona para corregir cualquier número de errores hasta .e
El requisito es que el polinomio de error tenga que ser cero en cada punto a i donde haya un error. Nada dice que tiene que ser cero solo en esos puntos; también puede tener una E ( x ) que sea cero en otros puntos, y eso está bien, siempre que su grado sea e .E(x) ai E(x) e
Entonces, si es un límite superior en el número de errores, existirá un polinomio E ( x ) con todas las propiedades deseadas (es decir, tiene un grado exactamentee E(x) y es cero en cada punto donde hay un error). Por ejemplo, si hay menos de e errores, entonces existe un polinomio E ( x ) que es cero en cada error, y cero en algunos puntos más para obtener el número de ceros hasta exactamente e .e e E(x) e
Finalmente, el teorema de corrección dice que si existe tal polinomio , entonces el algoritmo de Berlekamp-Welch podrá encontrarlo. Entonces, incluso si hay menos de e errores, el procedimiento seguirá funcionando correctamente para identificar E ( xE(x) e . Una vez que tenga E ( x ) , puede identificar n - e posiciones que están libres de errores, y luego puede decodificar de manera directa.E(x) E(x) n−e
Para documentar el resultado de la conversación sobre el "contraejemplo" en la pregunta:
Entonces, el contraejemplo no es en realidad un contraejemplo, y no contradice mi respuesta anterior.
fuente