Planteamiento del problema
Entrada: un campo; n pares distintos de elementos en ; y enteros y .
Salida: una lista de todas las funciones satisfactorio
es un polinomio en de grado como máximo
| | ( 1 ) |
Para comprender mejor el algoritmo de Sudán, es posible que desee conocer primero otro algoritmo que pueda considerarse como la versión anterior o la versión fundamental de los algoritmos para la decodificación de listas de códigos RS: el algoritmo de Berlekamp-Welch . Welch y Berlekamp vinieron inicialmente con un algoritmo que puede resolver el problema en tiempo polinomial con el mejor umbral en ser - estar . El mecanismo del algoritmo de Sudán es casi el mismo que el del algoritmo de Berlekamp-Welch, excepto que en el paso 1, se quiere calcular un polinomio bivariado dela licenciatura. El algoritmo de decodificación de listas de Sudán para el código Reed-Solomon, que es una mejora del algoritmo de Berlekamp y Welch, puede resolver el problema con. Este límite es mejor que el límite de decodificación único por .
Algoritmo
Definición 1 (grado ponderado)
Para pesas , la - grado ponderado de monomio es . La - grado ponderado de un polinomio es el máximo, sobre los monomios con coeficientes distintos de cero, de la - grado ponderado del monomio.
Por ejemplo, posee -grado 7
Algoritmo:
Entradas: ; {} / * Los parámetros l, m se configurarán más tarde. * /
Paso 1: Encuentra un polinomio bivariado distinto de cero satisfactorio
- posee -grados ponderados como máximo
- Para cada ,
| | ( 2 ) |
Paso 2. Factoriza Q en factores irreductibles.
Paso 3. Genere todos los polinomios tal que es un factor de Q y para al menos t valores de
Análisis
Hay que demostrar que el algoritmo anterior se ejecuta en tiempo polinomial y genera el resultado correcto. Eso se puede hacer demostrando el siguiente conjunto de afirmaciones.
Reclamación 1:
Si una función satisfaciendo (2) existe, entonces uno puede encontrarlo en tiempo polinomial.
Prueba:
Tenga en cuenta que un polinomio bivariado de -grados ponderados como máximo se puede escribir de forma única como . Entonces uno tiene que encontrar los coeficientes satisfaciendo las limitaciones , para cada . Este es un conjunto lineal de ecuaciones en las incógnitas {}. Se puede encontrar una solución utilizando la eliminación gaussiana en tiempo polinomial.
Reclamación 2:
Si entonces existe una función satisfactorio (2)
Prueba:
Para garantizar que exista una solución distinta de cero, el número de coeficientes en debe ser mayor que el número de restricciones. Suponga que el grado máximo de en es my el grado máximo de en es . Entonces el grado de será como máximo . Hay que ver que el sistema lineal sea homogéneo. El ajustesatisface todas las restricciones lineales. Sin embargo, esto no satisface (2), ya que la solución puede ser idénticamente cero. Para asegurarse de que exista una solución distinta de cero, uno debe asegurarse de que el número de incógnitas en el sistema lineal sea, para que uno pueda tener un valor distinto de cero . Dado que este valor es mayor que n, hay más variables que restricciones y, por lo tanto, existe una solución distinta de cero.
Reclamación 3:
Si es una función que satisface (2) y es la función que satisface (1) y , luego divide
Prueba:
Considere una función . Este es un polinomio en, y argumentan que tiene un grado como máximo . Considere cualquier monomio de . Desde posee -grados ponderados como máximo , se puede decir que . Por lo tanto, el término es un polinomio en de grado como máximo . Por lo tanto tiene un grado como máximo
Luego argumenta que es idénticamente cero. Desde es cero siempre que , se puede decir que es cero para estrictamente mayor que puntos. Por lo tantotiene más ceros que su grado y, por lo tanto, es idénticamente cero, lo que implica
Encontrar valores óptimos para y . Tenga en cuenta que y Por un valor dado , se puede calcular el más pequeño para lo cual se cumple la segunda condición Intercambiando la segunda condición uno puede obtener ser como máximo Sustituyendo este valor en la primera condición se puede obtener ser al menos A continuación, minimice la ecuación anterior de parámetro desconocido . Uno puede hacer eso tomando la derivada de la ecuación e igualando eso a cero Al hacer eso, obtendrá, Sustituyendo de nuevo el valor en y uno obtendrá
Definición
Considere un Código Reed-Solomon sobre el campo finito con set de evaluación y un entero positivo , el decodificador de listas Guruswami-Sudan acepta un vector como entrada, y genera una lista de polinomios de grado que están en correspondencia 1 a 1 con palabras de código.
La idea es agregar más restricciones al polinomio bivariable lo que da como resultado el incremento de restricciones junto con el número de raíces.
Multiplicidad
Un polinomio bivariable tiene un cero de multiplicidad a significa que no tiene término de grado , donde el grado x de se define como el grado máximo de cualquier término x en
Por ejemplo: Let .
https://wiki.cse.buffalo.edu/cse545/sites/wiki.cse.buffalo.edu.cse545/files/76/Fig1.jpg
Por eso, tiene un cero de multiplicidad 1 en (0,0).
Dejar .
https://wiki.cse.buffalo.edu/cse545/sites/wiki.cse.buffalo.edu.cse545/files/76/Fig2.jpg
Por eso, tiene un cero de multiplicidad 1 en (0,0).
Dejar
https://wiki.cse.buffalo.edu/cse545/sites/wiki.cse.buffalo.edu.cse545/files/76/Fig3.jpg
Por eso, tiene un cero de multiplicidad 2 en (0,0).
Del mismo modo, si Luego, tiene un cero de multiplicidad 2 en .
Definición general de multiplicidad
posee raíces en Si tiene un cero de multiplicidad a Cuándo .
Algoritmo
Sea la palabra clave transmitida , ser el conjunto de soporte de la palabra de código transmitida y la palabra recibida
El algoritmo es como sigue:
• Paso de interpolación
Para un vector recibido , construye un polinomio bivariado distinto de cero con grado ponderado de como máximo tal que tiene un cero de multiplicidad en cada uno de los puntos dónde
• Paso de factorización
Encuentra todos los factores de de la forma y por al menos valores de
dónde Y es un polinomio de grado
Recuerde que los polinomios de grado están en correspondencia 1 a 1 con palabras de código. Por lo tanto, este paso genera la lista de palabras de código.
Análisis
Paso de interpolación
Lema: el paso de interpolación implica restricciones sobre los coeficientes de
Dejar dónde y
Luego, ........................ (Ecuación 1)
dónde
Prueba de la ecuación 1:
- ................. Usando expansión binomial
Prueba de lema:
El polinomio tiene un cero de multiplicidad a Si
- tal que
- puede tomar valores como . Por lo tanto, el número total de restricciones es
Por lo tanto, se pueden realizar varias selecciones para y cada selección implica restricciones en los coeficientes de
Paso de factorización
Proposición:
Si es un factor de
Prueba:
Desde, es un factor de , se puede representar como
dónde, es el cociente obtenido cuando está dividido por es el resto
Ahora si es reemplazado por , , sólo si
Teorema:
Si , luego es un factor de
Prueba:
........................... De la Ecuación 2
Dado, modificación
Por eso, modificación
Por lo tanto, es un factor de .
Como se demostró anteriormente,
donde LHS es el límite superior del número de coeficientes de y RHS es el Lema probado anteriormente.
Por lo tanto,
Sustituir ,
Por lo tanto, se demostró que el algoritmo de decodificación de listas de Guruswami-Sudan puede decodificar listas de códigos Reed-Solomon hasta errores.