Algoritmo de decodificación de listas de Guruswami–Sudan

En la teoría de la codificación , la decodificación de listas es una alternativa a la decodificación única de códigos de corrección de errores en presencia de muchos errores. Si un código tiene una distancia relativa , entonces es posible en principio recuperar un mensaje codificado cuando hasta una fracción de los símbolos de la palabra de código están dañados. Pero cuando la tasa de error es mayor que , esto en general no será posible. La decodificación de listas supera ese problema al permitir que el decodificador genere una lista corta de mensajes que podrían haber sido codificados. La decodificación de listas puede corregir más de una fracción de errores. ${\displaystyle \delta }$ ${\displaystyle \delta /2}$ ${\displaystyle \delta /2}$ ${\displaystyle \delta /2}$

Existen muchos algoritmos de tiempo polinomial para la decodificación de listas. En este artículo, primero presentamos un algoritmo para códigos Reed–Solomon (RS) que corrige hasta errores y se debe a Madhu Sudan . Posteriormente, describimos el algoritmo mejorado de decodificación de listas Guruswami – Sudan , que puede corregir hasta errores. ${\displaystyle 1-{\sqrt {2R}}}$ ${\displaystyle 1-{\sqrt {R}}}$

Aquí se muestra un gráfico de la tasa R y la distancia para diferentes algoritmos. ${\displaystyle \delta }$

https://wiki.cse.buffalo.edu/cse545/sites/wiki.cse.buffalo.edu.cse545/files/81/Graph.jpg

Algoritmo 1 (algoritmo de decodificación de listas de Sudán)

Planteamiento del problema

Entrada: Un campo ; n pares distintos de elementos en ; y números enteros y . ${\displaystyle F}$ ${\displaystyle {(x_{i},y_{i})_{i=1}^{n}}}$ ${\displaystyle F\times F}$ ${\displaystyle d}$ ${\displaystyle t}$

Salida: Una lista de todas las funciones que satisfacen ${\displaystyle f:F\to F}$

${\displaystyle f(x)}$es un polinomio de grado como máximo ${\displaystyle x}$ ${\displaystyle d}$

Para entender mejor el algoritmo de Sudan, es posible que uno quiera conocer primero otro algoritmo que puede considerarse como la versión anterior o la versión fundamental de los algoritmos para decodificar códigos RS de listas: el algoritmo de Berlekamp-Welch . Welch y Berlekamp inicialmente vinieron con un algoritmo que puede resolver el problema en tiempo polinomial con el mejor umbral en ser . El mecanismo del algoritmo de Sudan es casi el mismo que el algoritmo del algoritmo de Berlekamp-Welch, excepto que en el paso 1, uno quiere calcular un polinomio bivariado de grado acotado. El algoritmo de decodificación de listas de Sudan 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 para . ${\displaystyle t}$ ${\displaystyle t\geq (n+d+1)/2}$ ${\displaystyle (1,k)}$ ${\displaystyle t=({\sqrt {2nd}})}$ ${\displaystyle 1-\left({\frac {R}{2}}\right)}$ ${\displaystyle R<0.07}$

Algoritmo

Definición 1 (grado ponderado)

Para pesos , el grado ponderado – del monomio es . El grado ponderado – de un polinomio es el máximo, sobre los monomios con coeficientes distintos de cero, del grado ponderado – del monomio. ${\displaystyle w_{x},w_{y}\in \mathbb {Z} ^{+}}$ ${\displaystyle (w_{x},w_{y})}$ ${\displaystyle q_{ij}x^{i}y^{j}}$ ${\displaystyle iw_{x}+jw_{y}}$ ${\displaystyle (w_{x},w_{y})}$ ${\displaystyle Q(x,y)=\sum _{ij}q_{ij}x^{i}y^{j}}$ ${\displaystyle (w_{x},w_{y})}$

Por ejemplo, tiene -grado 7 ${\displaystyle xy^{2}}$ ${\displaystyle (1,3)}$

Algoritmo:

Entradas: ; { } /* Los parámetros l,m se configurarán más tarde. */ ${\displaystyle n,d,t}$ ${\displaystyle (x_{1},y_{1})\cdots (x_{n},y_{n})}$

Paso 1: Encuentra un polinomio bivariado distinto de cero que satisfaga ${\displaystyle Q:F^{2}\mapsto F}$

• ${\displaystyle Q(x,y)}$tiene como máximo un grado ponderado ${\displaystyle (1,d)}$ ${\displaystyle D=m+ld}$
• Para cada , ${\displaystyle i\in [n]}$

Paso 2. Factoriza Q en factores irreducibles.

Paso 3. Imprima todos los polinomios tales que sea un factor de Q y para al menos t valores de ${\displaystyle f}$ ${\displaystyle (y-f(x))}$ ${\displaystyle f(x_{i})=y_{i}}$ ${\displaystyle i\in [n]}$

Análisis

Hay que demostrar que el algoritmo anterior se ejecuta en tiempo polinómico y genera el resultado correcto. Esto se puede hacer demostrando el siguiente conjunto de afirmaciones.

Reclamación 1:

Si existe una función que satisface (2), entonces se puede encontrar en tiempo polinomial. ${\displaystyle Q:F^{2}\to F}$

Prueba:

Nótese que un polinomio bivariado de grado ponderado como máximo se puede escribir de forma única como . Luego hay que encontrar los coeficientes que satisfacen las restricciones , 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. ${\displaystyle Q(x,y)}$ ${\displaystyle (1,d)}$ ${\displaystyle D}$ ${\displaystyle Q(x,y)=\sum _{j=0}^{l}\sum _{k=0}^{m+(l-j)d}q_{kj}x^{k}y^{j}}$ ${\displaystyle q_{kj}}$ ${\displaystyle \sum _{j=0}^{l}\sum _{k=0}^{m+(l-j)d}q_{kj}x_{i}^{k}y_{i}^{j}=0}$ ${\displaystyle i\in [n]}$ ${\displaystyle q_{kj}}$

Reclamación 2:

Si entonces existe una función que satisface (2) ${\displaystyle (m+1)(l+1)+d{\begin{pmatrix}l+1\\2\end{pmatrix}}>n}$ ${\displaystyle Q(x,y)}$

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. Supongamos que el grado máximo de en es m y el grado máximo de en es . Entonces el grado de será como máximo . Hay que ver que el sistema lineal es homogéneo. La configuración satisface todas las restricciones lineales. Sin embargo, esto no satisface (2), ya que la solución puede ser idénticamente cero. Para garantizar que exista una solución distinta de cero, hay que asegurarse de que el número de incógnitas en el sistema lineal sea , de modo que se pueda tener un 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. ${\displaystyle Q(x,y)}$ ${\displaystyle deg_{x}(Q)}$ ${\displaystyle x}$ ${\displaystyle Q(x,y)}$ ${\displaystyle deg_{y}(Q)}$ ${\displaystyle y}$ ${\displaystyle Q(x,y)}$ ${\displaystyle l}$ ${\displaystyle Q(x,y)}$ ${\displaystyle m+ld}$ ${\displaystyle q_{jk}=0}$ ${\displaystyle (m+1)(l+1)+d{\begin{pmatrix}l+1\\2\end{pmatrix}}>n}$ ${\displaystyle Q(x,y)}$

Reclamación 3:

Si es una función que satisface (2) y es una función que satisface (1) y , entonces divide ${\displaystyle Q(x,y)}$ ${\displaystyle f(x)}$ ${\displaystyle t>m+ld}$ ${\displaystyle (y-f(x))}$ ${\displaystyle Q(x,y)}$

Prueba:

Considere una función . Este es un polinomio en , y argumente que tiene grado como máximo . Considere cualquier monomio de . Como tiene grado ponderado 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 grado como máximo ${\displaystyle p(x)=Q(x,f(x))}$ ${\displaystyle x}$ ${\displaystyle m+ld}$ ${\displaystyle q_{jk}x^{k}y^{j}}$ ${\displaystyle Q(x)}$ ${\displaystyle Q}$ ${\displaystyle (1,d)}$ ${\displaystyle m+ld}$ ${\displaystyle k+jd\leq m+ld}$ ${\displaystyle q_{kj}x^{k}f(x)^{j}}$ ${\displaystyle x}$ ${\displaystyle k+jd\leq m+ld}$ ${\displaystyle p(x)}$ ${\displaystyle m+ld}$

A continuación, argumentamos que es idénticamente cero. Como es cero siempre que , se puede decir que es cero para puntos estrictamente mayores que . Por lo tanto , tiene más ceros que su grado y, por lo tanto, es idénticamente cero, lo que implica ${\displaystyle p(x)}$ ${\displaystyle Q(x_{i},f(x_{i}))}$ ${\displaystyle y_{i}=f(x_{i})}$ ${\displaystyle p(x_{i})}$ ${\displaystyle m+ld}$ ${\displaystyle p}$ ${\displaystyle Q(x,f(x))\equiv 0}$

Encontrar valores óptimos para y . Nótese que y Para un valor dado , se puede calcular el más pequeño para el cual se cumple la segunda condición Al intercambiar la segunda condición se puede llegar a ser como máximo Sustituyendo este valor en la primera condición se puede llegar a ser al menos Luego se minimiza la ecuación anterior de parámetro desconocido . Se puede hacer eso tomando la derivada de la ecuación e igualándola a cero Al hacer eso se obtendrá, Sustituyendo nuevamente el valor en y se obtendrá ${\displaystyle m}$ ${\displaystyle l}$ ${\displaystyle m+ld<t}$ ${\displaystyle (m+1)(l+1)+d{\begin{pmatrix}l+1\\2\end{pmatrix}}>n}$ ${\displaystyle l}$ ${\displaystyle m}$ ${\displaystyle m}$ ${\displaystyle (n+1-d{\begin{pmatrix}l+1\\2\end{pmatrix}})/2-1}$ ${\displaystyle t}$ ${\displaystyle {\frac {n+1}{l+1}}+{\frac {dl}{2}}}$ ${\displaystyle l}$ ${\displaystyle l={\sqrt {\frac {2(n+1)}{d}}}-1}$ ${\displaystyle l}$ ${\displaystyle m}$ ${\displaystyle t}$ ${\displaystyle m\geq {\sqrt {\frac {(n+1)d}{2}}}-{\sqrt {\frac {(n+1)d}{2}}}+{\frac {d}{2}}-1={\frac {d}{2}}-1}$ ${\displaystyle t>{\sqrt {\frac {2(n+1)d^{2}}{d}}}-{\frac {d}{2}}-1}$ ${\displaystyle t>{\sqrt {2(n+1)d}}-{\frac {d}{2}}-1}$

Algoritmo 2 (algoritmo de decodificación de listas Guruswami–Sudan)

Definición

Considere un código Reed-Solomon sobre el campo finito con un conjunto 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 las palabras de código. ${\displaystyle (n,k)}$ ${\displaystyle \mathbb {F} =GF(q)}$ ${\displaystyle (\alpha _{1},\alpha _{2},\ldots ,\alpha _{n})}$ ${\displaystyle r}$ ${\displaystyle \beta =(\beta _{1},\beta _{2},\ldots ,\beta _{n})}$ ${\displaystyle \in }$ ${\displaystyle \mathbb {F} ^{n}}$ ${\displaystyle \leq k}$

La idea es agregar más restricciones al polinomio bivariado, lo que da como resultado el incremento de las restricciones junto con el número de raíces. ${\displaystyle Q(x,y)}$

Multiplicidad

Un polinomio bivariado tiene un cero de multiplicidad en media 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 ${\displaystyle Q(x,y)}$ ${\displaystyle r}$ ${\displaystyle (0,0)}$ ${\displaystyle Q(x,y)}$ ${\displaystyle \leq r}$ ${\displaystyle f(x)}$ ${\displaystyle f(x)}$ ${\displaystyle \qquad }$ ${\displaystyle deg_{x}f(x)}$ ${\displaystyle =}$ ${\displaystyle \max _{i\in I}\{i\}}$

Por ejemplo: Sea . ${\displaystyle Q(x,y)=y-4x^{2}}$

https://wiki.cse.buffalo.edu/cse545/sites/wiki.cse.buffalo.edu.cse545/files/76/Fig1.jpg

Por lo tanto, tiene un cero de multiplicidad 1 en (0,0). ${\displaystyle Q(x,y)}$

Dejar . ${\displaystyle Q(x,y)=y+6x^{2}}$

https://wiki.cse.buffalo.edu/cse545/sites/wiki.cse.buffalo.edu.cse545/files/76/Fig2.jpg

Por lo tanto, tiene un cero de multiplicidad 1 en (0,0). ${\displaystyle Q(x,y)}$

Dejar ${\displaystyle Q(x,y)=(y-4x^{2})(y+6x^{2})=y^{2}+6x^{2}y-4x^{2}y-24x^{4}}$

https://wiki.cse.buffalo.edu/cse545/sites/wiki.cse.buffalo.edu.cse545/files/76/Fig3.jpg

Por lo tanto, tiene un cero de multiplicidad 2 en (0,0). ${\displaystyle Q(x,y)}$

De manera similar, si Entonces, tiene un cero de multiplicidad 2 en . ${\displaystyle Q(x,y)=[(y-\beta )-4(x-\alpha )^{2})][(y-\beta )+6(x-\alpha )^{2})]}$ ${\displaystyle Q(x,y)}$ ${\displaystyle (\alpha ,\beta )}$

Definición general de multiplicidad

${\displaystyle Q(x,y)}$tiene raíces en si tiene un cero de multiplicidad en cuando . ${\displaystyle r}$ ${\displaystyle (\alpha ,\beta )}$ ${\displaystyle Q(x,y)}$ ${\displaystyle r}$ ${\displaystyle (\alpha ,\beta )}$ ${\displaystyle (\alpha ,\beta )\neq (0,0)}$

Algoritmo

Sea la palabra de código transmitida , sea el conjunto de soporte de la palabra de código transmitida y la palabra recibida sea ${\displaystyle (f(\alpha _{1}),f(\alpha _{2}),\ldots ,f(\alpha _{n}))}$ ${\displaystyle (\alpha _{1},\alpha _{2},\ldots ,\alpha _{n})}$ ${\displaystyle (\beta _{1},\beta _{2},\ldots ,\beta _{n})}$

El algoritmo es el siguiente:

• Paso de interpolación

Para un vector recibido , construya un polinomio bivariado distinto de cero con grado ponderado de como máximo tal que tenga un cero de multiplicidad en cada uno de los puntos donde ${\displaystyle (\beta _{1},\beta _{2},\ldots ,\beta _{n})}$ ${\displaystyle Q(x,y)}$ ${\displaystyle (1,k)-}$ ${\displaystyle d}$ ${\displaystyle Q}$ ${\displaystyle r}$ ${\displaystyle (\alpha _{i},\beta _{i})}$ ${\displaystyle 1\leq i\leq n}$

${\displaystyle Q(\alpha _{i},\beta _{i})=0\,}$

• Paso de factorización

Encuentra todos los factores de la forma y para al menos valores de ${\displaystyle Q(x,y)}$ ${\displaystyle y-p(x)}$ ${\displaystyle p(\alpha _{i})=\beta _{i}}$ ${\displaystyle t}$ ${\displaystyle i}$

donde & es un polinomio de grado ${\displaystyle 0\leq i\leq n}$ ${\displaystyle p(x)}$ ${\displaystyle \leq k}$

Recuerde que los polinomios de grado tienen una correspondencia uno a uno con las palabras clave. Por lo tanto, este paso genera la lista de palabras clave. ${\displaystyle \leq k}$

Análisis

Paso de interpolación

Lema: El paso de interpolación implica restricciones en los coeficientes de ${\displaystyle {\begin{pmatrix}r+1\\2\end{pmatrix}}}$ ${\displaystyle a_{i}}$

Deja donde y ${\displaystyle Q(x,y)=\sum _{i=0,j=0}^{i=m,j=p}a_{i,j}x^{i}y^{j}}$ ${\displaystyle \deg _{x}Q(x,y)=m}$ ${\displaystyle \deg _{y}Q(x,y)=p}$

Entonces, ........................(Ecuación 1) ${\displaystyle Q(x+\alpha ,y+\beta )}$ ${\displaystyle =}$ ${\displaystyle \sum _{u=0,v=0}^{r}}$ ${\displaystyle Q_{u,v}}$ ${\displaystyle (\alpha ,\beta )}$ ${\displaystyle x^{u}}$ ${\displaystyle y^{v}}$

dónde ${\displaystyle Q_{u,v}}$ ${\displaystyle (x,y)}$ ${\displaystyle =}$ ${\displaystyle \sum _{i=0,j=0}^{i=m,j=p}}$ ${\displaystyle {\begin{pmatrix}i\\u\end{pmatrix}}}$ ${\displaystyle {\begin{pmatrix}j\\v\end{pmatrix}}}$ ${\displaystyle a_{i,j}}$ ${\displaystyle x^{i-u}}$ ${\displaystyle y^{j-v}}$

Prueba de la ecuación 1:

${\displaystyle Q(x+\alpha ,y+\beta )=\sum _{i,j}a_{i,j}(x+\alpha )^{i}(y+\beta )^{j}}$

${\displaystyle Q(x+\alpha ,y+\beta )=\sum _{i,j}a_{i,j}{\Bigg (}\sum _{u}{\begin{pmatrix}i\\u\end{pmatrix}}x^{u}\alpha ^{i-u}{\Bigg )}{\Bigg (}\sum _{v}{\begin{pmatrix}i\\v\end{pmatrix}}y^{v}\beta ^{j-v}{\Bigg )}}$.................Usando la expansión binomial

${\displaystyle Q(x+\alpha ,y+\beta )=\sum _{u,v}x^{u}y^{v}{\Bigg (}\sum _{i,j}{\begin{pmatrix}i\\u\end{pmatrix}}{\begin{pmatrix}i\\v\end{pmatrix}}a_{i,j}\alpha ^{i-u}\beta ^{j-v}{\Bigg )}}$

${\displaystyle Q(x+\alpha ,y+\beta )=\sum _{u,v}}$ ${\displaystyle Q_{u,v}(\alpha ,\beta )x^{u}y^{v}}$

Prueba del lema:

El polinomio tiene un cero de multiplicidad en si ${\displaystyle Q(x,y)}$ ${\displaystyle r}$ ${\displaystyle (\alpha ,\beta )}$

${\displaystyle Q_{u,v}}$ ${\displaystyle (\alpha ,\beta )}$ ${\displaystyle \equiv }$ ${\displaystyle 0}$de tal manera que ${\displaystyle 0\leq u+v\leq r-1}$

${\displaystyle u}$puede tomar valores como . Por lo tanto, el número total de restricciones es ${\displaystyle r-v}$ ${\displaystyle 0\leq v\leq r-1}$

${\displaystyle \sum _{v=0}^{r-1}{r-v}}$ ${\displaystyle =}$ ${\displaystyle {\begin{pmatrix}r+1\\2\end{pmatrix}}}$

Por lo tanto, se pueden realizar varias selecciones y cada selección implica restricciones en los coeficientes de ${\displaystyle {\begin{pmatrix}r+1\\2\end{pmatrix}}}$ ${\displaystyle (u,v)}$ ${\displaystyle a_{i}}$

Paso de factorización

Proposición:

${\displaystyle Q(x,p(x))\equiv 0}$Si es un factor de ${\displaystyle y-p(x)}$ ${\displaystyle Q(x,y)}$

Prueba:

Dado que, es un factor de , se puede representar como ${\displaystyle y-p(x)}$ ${\displaystyle Q(x,y)}$ ${\displaystyle Q(x,y)}$

${\displaystyle Q(x,y)=L(x,y)(y-p(x))}$ ${\displaystyle +}$ ${\displaystyle R(x)}$

donde, es el cociente que se obtiene al dividir por es el resto ${\displaystyle L(x,y)}$ ${\displaystyle Q(x,y)}$ ${\displaystyle y-p(x)}$ ${\displaystyle R(x)}$

Ahora, si se reemplaza por , , solo si ${\displaystyle y}$ ${\displaystyle p(x)}$ ${\displaystyle Q(x,p(x))}$ ${\displaystyle \equiv }$ ${\displaystyle 0}$ ${\displaystyle R(x)}$ ${\displaystyle \equiv }$ ${\displaystyle 0}$

Teorema:

Si , entonces es un factor de ${\displaystyle p(\alpha )=\beta }$ ${\displaystyle (x-\alpha )^{r}}$ ${\displaystyle Q(x,p(x))}$

Prueba:

${\displaystyle Q(x,y)}$ ${\displaystyle =}$ ${\displaystyle \sum _{u,v}}$ ${\displaystyle Q_{u,v}}$ ${\displaystyle (\alpha ,\beta )}$ ${\displaystyle (x-\alpha )^{u}}$ ${\displaystyle (y-\beta )^{v}}$...........................De la ecuación 2

${\displaystyle Q(x,p(x))}$ ${\displaystyle =}$ ${\displaystyle \sum _{u,v}}$ ${\displaystyle Q_{u,v}}$ ${\displaystyle (\alpha ,\beta )}$ ${\displaystyle (x-\alpha )^{u}}$ ${\displaystyle (p(x)-\beta )^{v}}$

Dado, mod ${\displaystyle p(\alpha )}$ ${\displaystyle =}$ ${\displaystyle \beta }$ ${\displaystyle (p(x)-\beta )}$ ${\displaystyle (x-\alpha )}$ ${\displaystyle =}$ ${\displaystyle 0}$

Por lo tanto, mod ${\displaystyle (x-\alpha )^{u}}$ ${\displaystyle (p(x)-\beta )^{v}}$ ${\displaystyle (x-\alpha )^{u+v}}$ ${\displaystyle =}$ ${\displaystyle 0}$

Por lo tanto, es un factor de . ${\displaystyle (x-\alpha )^{r}}$ ${\displaystyle Q(x,p(x))}$

Como se demostró anteriormente,

${\displaystyle t\cdot r>D}$

${\displaystyle t>{\frac {D}{r}}}$

${\displaystyle {\frac {D(D+2)}{2(k-1)}}>n{\begin{pmatrix}r+1\\2\end{pmatrix}}}$donde LHS es el límite superior del número de coeficientes de y RHS es el lema demostrado anteriormente. ${\displaystyle Q(x,y)}$

${\displaystyle D={\sqrt {knr(r-1)}}\,}$

Por lo tanto, ${\displaystyle t=\left\lceil {\sqrt {kn(1-{\frac {1}{r}})}}\right\rceil }$

Sustituto , ${\displaystyle r=2kn}$

${\displaystyle t>\left\lceil {\sqrt {kn-{\frac {1}{2}}}}\right\rceil >\left\lceil {\sqrt {kn}}\right\rceil }$

Por lo tanto, se ha demostrado que el algoritmo de decodificación de listas Guruswami-Sudan puede decodificar listas de códigos Reed-Solomon hasta con errores. ${\displaystyle 1-{\sqrt {R}}}$

Referencias

• https://web.archive.org/web/20100702120650/http://www.cse.buffalo.edu/~atri/courses/coding-theory/
• https://www.cs.cmu.edu/~venkatg/pubs/papers/listdecoding-NOW.pdf
• http://www.mendeley.com/research/algebraic-softdecision-decoding-reedsolomon-codes/
• RJ McEliece. El algoritmo de decodificación Guruswami-Sudan para códigos Reed-Solomon.
• M Sudan. Descodificación de códigos Reed Solomon más allá del límite de corrección de errores.