Lista de decodificación

En teoría de codificación , la decodificación de listas es una alternativa a la decodificación única de códigos de corrección de errores para grandes tasas de error. La idea fue propuesta por Elias en la década de 1950. La idea principal detrás de la decodificación de listas es que el algoritmo de decodificación, en lugar de generar un único mensaje posible, genera una lista de posibilidades, una de las cuales es correcta. Esto permite manejar una mayor cantidad de errores que los permitidos por la decodificación única.

El modelo de decodificación único en la teoría de la codificación , que está limitado a generar una única palabra de código válida a partir de la palabra recibida, no podría tolerar una mayor fracción de errores. Esto resultó en una brecha entre el rendimiento de corrección de errores para los modelos de ruido estocástico (propuesto por Shannon ) y el modelo de ruido adversario (considerado por Richard Hamming ). Desde mediados de los años 90, un importante progreso algorítmico realizado por la comunidad de la teoría de la codificación ha salvado esta brecha. Gran parte de este progreso se basa en un modelo relajado de corrección de errores llamado decodificación de listas, en el que el decodificador genera una lista de palabras de código para los patrones de error patológicos del peor de los casos donde la palabra de código transmitida real se incluye en la lista de salida. Sin embargo, en el caso de patrones de error típicos, el decodificador genera una única palabra de código, dada una palabra recibida, lo cual es casi siempre el caso (sin embargo, no se sabe que esto sea cierto para todos los códigos). La mejora aquí es significativa porque el rendimiento de corrección de errores se duplica. Esto se debe a que ahora el decodificador no está limitado por la barrera de la mitad de la distancia mínima. Este modelo es muy atractivo porque tener una lista de palabras en clave es ciertamente mejor que simplemente darse por vencido. La noción de decodificación de listas tiene muchas aplicaciones interesantes en la teoría de la complejidad .

La forma en que se modela el ruido del canal juega un papel crucial ya que determina la velocidad a la que es posible una comunicación confiable. Hay dos escuelas de pensamiento principales a la hora de modelar el comportamiento del canal:

• Modelo de ruido probabilístico estudiado por Shannon en el que el ruido del canal se modela precisamente en el sentido de que el comportamiento probabilístico del canal es bien conocido y la probabilidad de que ocurran demasiados o muy pocos errores es baja.
• Modelo de ruido de peor caso o adversario considerado por Hamming en el que el canal actúa como un adversario que corrompe arbitrariamente la palabra clave sujeta a un límite en el número total de errores.

Lo más destacado de la decodificación de listas es que incluso en condiciones de ruido adversas, es posible lograr el equilibrio óptimo teórico de la información entre la tasa y la fracción de errores que se pueden corregir. Por lo tanto, en cierto sentido, esto es como mejorar el rendimiento de corrección de errores al nivel posible en el caso de un modelo de ruido estocástico más débil.

formulación matemática

Sea un código de corrección de errores; en otras palabras, es un código de longitud , dimensión y distancia mínima sobre un alfabeto de tamaño . El problema de decodificación de listas ahora se puede formular de la siguiente manera: ${\displaystyle {\mathcal {C}}}$ ${\displaystyle (n,k,d)_{q}}$ ${\displaystyle {\mathcal {C}}}$ ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle d}$ ${\displaystyle \Sigma }$ ${\displaystyle q}$

Entrada: palabra recibida , límite de error ${\displaystyle x\in \Sigma ^{n}}$ ${\displaystyle e}$

Salida: una lista de todas las palabras en clave cuya distancia de Hamming es como máximo . ${\displaystyle x_{1},x_{2},\ldots ,x_{m}\in {\mathcal {C}}}$ ${\displaystyle x}$ ${\displaystyle e}$

Motivación para decodificar listas

Dada una palabra recibida , que es una versión ruidosa de alguna palabra en clave transmitida , el decodificador intenta generar la palabra en clave transmitida apostando en una palabra en clave que esté "más cerca" de la palabra recibida. La distancia de Hamming entre dos palabras en código se utiliza como métrica para encontrar la palabra en código más cercana, dada la palabra recibida por el decodificador. Si es la distancia mínima de Hamming de un código , entonces existen dos palabras de código y que difieren exactamente en sus posiciones. Ahora, en el caso en que la palabra recibida sea equidistante de las palabras de código y , la decodificación inequívoca se vuelve imposible ya que el decodificador no puede decidir cuál de y generar como la palabra de código transmitida original. Como resultado, la mitad de la distancia mínima actúa como una barrera combinatoria más allá de la cual es imposible una corrección de errores inequívoca, si sólo insistimos en una decodificación única. Sin embargo, las palabras recibidas como las consideradas anteriormente ocurren sólo en el peor de los casos y si uno observa la forma en que se empaquetan las bolas de Hamming en un espacio de alta dimensión, incluso para patrones de error más allá de la mitad de la distancia mínima, solo hay una única palabra en clave dentro. Distancia de Hamming de la palabra recibida. Se ha demostrado que esta afirmación es válida con alta probabilidad para un código aleatorio elegido de un conjunto natural y más aún para el caso de los códigos Reed-Solomon , que están bien estudiados y son bastante ubicuos en las aplicaciones del mundo real. De hecho, la prueba de Shannon del teorema de capacidad para canales simétricos q -arios puede verse a la luz de la afirmación anterior para códigos aleatorios. ${\displaystyle y}$ ${\displaystyle c}$ ${\displaystyle d}$ ${\displaystyle {\mathcal {C}}}$ ${\displaystyle c_{1}}$ ${\displaystyle c_{2}}$ ${\displaystyle d}$ ${\displaystyle y}$ ${\displaystyle c_{1}}$ ${\displaystyle c_{2}}$ ${\displaystyle c_{1}}$ ${\displaystyle c_{2}}$ ${\displaystyle y}$ ${\displaystyle e}$ ${\displaystyle c}$ ${\displaystyle e}$

Según el mandato de decodificación de listas, para los peores casos de errores, el decodificador puede generar una pequeña lista de palabras en código. Con alguna información adicional o específica del contexto, es posible podar la lista y recuperar la palabra clave transmitida original. Por lo tanto, en general, este parece ser un modelo de recuperación de errores más sólido que la decodificación única.

Potencial de decodificación de listas

Para que exista un algoritmo de decodificación de listas en tiempo polinomial, necesitamos la garantía combinatoria de que cualquier bola de Hamming de radio alrededor de una palabra recibida (donde es la fracción de errores en términos de la longitud del bloque ) tenga una pequeña cantidad de palabras en código. Esto se debe a que el tamaño de la lista en sí es claramente un límite inferior del tiempo de ejecución del algoritmo. Por lo tanto, requerimos que el tamaño de la lista sea un polinomio en la longitud del bloque del código. Una consecuencia combinatoria de este requisito es que impone un límite superior a la tasa de un código. La decodificación de listas promete cumplir con este límite superior. Se ha demostrado de manera no constructiva que existen códigos de tasa que se pueden decodificar en forma de lista hasta una fracción de los errores que se aproximan . La cantidad se denomina en la literatura capacidad de decodificación de listas. Esta es una ganancia sustancial en comparación con el modelo de decodificación único, ya que ahora tenemos el potencial de corregir el doble de errores. Naturalmente, necesitamos que al menos una fracción de los símbolos transmitidos sean correctos para poder recuperar el mensaje. Este es un límite inferior teórico de la información en la cantidad de símbolos correctos necesarios para realizar la decodificación y, con la decodificación de listas, podemos alcanzar potencialmente este límite teórico de la información. Sin embargo, para aprovechar este potencial, necesitamos códigos explícitos (códigos que puedan construirse en tiempo polinómico) y algoritmos eficientes para realizar la codificación y decodificación. ${\displaystyle pn}$ ${\displaystyle r}$ ${\displaystyle p}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle R}$ ${\displaystyle 1-R}$ ${\displaystyle 1-R}$ ${\displaystyle R}$

( p , L )-lista-decodificabilidad

Para cualquier fracción de error y un número entero , se dice que un código es decodificable en lista hasta una fracción de errores con un tamaño de lista como máximo o -lista-decodificable si para cada , el número de palabras en código dentro de la distancia de Hamming es como máximo ${\displaystyle 0\leqslant p\leqslant 1}$ ${\displaystyle L\geqslant 1}$ ${\displaystyle {\mathcal {C}}\subseteq \Sigma ^{n}}$ ${\displaystyle p}$ ${\displaystyle L}$ ${\displaystyle (p,L)}$ ${\displaystyle y\in \Sigma ^{n}}$ ${\displaystyle c\in C}$ ${\displaystyle pn}$ ${\displaystyle y}$ ${\displaystyle L.}$

Combinatoria de decodificación de listas.

La relación entre la decodificabilidad de la lista de un código y otros parámetros fundamentales como la distancia mínima y la velocidad se ha estudiado bastante bien. Se ha demostrado que cada código se puede decodificar mediante listas utilizando listas pequeñas más allá de la mitad de la distancia mínima hasta un límite llamado radio de Johnson. Esto es bastante significativo porque demuestra la existencia de códigos decodificables en lista de buena velocidad con un radio de decodificación de lista mucho mayor que. En otras palabras, el límite de Johnson descarta la posibilidad de tener un gran número de palabras en código en una bola de Hamming de radio ligeramente mayor que lo que significa que es posible corregir muchos más errores con la decodificación de listas. ${\displaystyle (p,L)}$ ${\displaystyle {\tfrac {d}{2}}.}$ ${\displaystyle {\tfrac {d}{2}}}$

Capacidad de decodificación de listas

Teorema (capacidad de decodificación de listas). Sean y Las siguientes dos afirmaciones son válidas para bloques de longitud suficientemente grande . ${\displaystyle q\geqslant 2,0\leqslant p\leqslant 1-{\tfrac {1}{q}}}$ ${\displaystyle \epsilon \geqslant 0.}$ ${\displaystyle n}$

i) Si , entonces existe un código decodificable de lista. ${\displaystyle R\leqslant 1-H_{q}(p)-\epsilon }$ ${\displaystyle (p,O(1/\epsilon ))}$

ii) Si , entonces cada código decodificable en lista tiene . ${\displaystyle R\geqslant 1-H_{q}(p)+\epsilon }$ ${\displaystyle (p,L)}$ ${\displaystyle L=q^{\Omega (n)}}$

Dónde

${\displaystyle H_{q}(p)=p\log _{q}(q-1)-p\log _{q}p-(1-p)\log _{q}(1-p)}$

es la función de entropía -aria definida y extendida por la continuidad a ${\displaystyle q}$ ${\displaystyle p\in (0,1)}$ ${\displaystyle [0,1].}$

Lo que esto significa es que para velocidades que se acercan a la capacidad del canal, existen listas de códigos decodificables con listas de tamaño polinómico que permiten algoritmos de decodificación eficientes, mientras que para velocidades que exceden la capacidad del canal, el tamaño de la lista se vuelve exponencial, lo que descarta la existencia de algoritmos de decodificación eficientes.

La prueba de la capacidad de decodificación de listas es significativa porque coincide exactamente con la capacidad de un canal simétrico ario . De hecho, el término "capacidad de decodificación de listas" debería leerse como la capacidad de un canal adversario bajo decodificación de listas. Además, la prueba de la capacidad de decodificación de listas es un resultado importante que señala el equilibrio óptimo entre la tasa de un código y la fracción de errores que se pueden corregir con la decodificación de listas. ${\displaystyle q}$ ${\displaystyle qSC_{p}}$

Bosquejo de prueba

La idea detrás de la prueba es similar a la prueba de Shannon para la capacidad del canal simétrico binario donde se selecciona un código aleatorio y muestra que es decodificable en lista con alta probabilidad siempre que la tasa. Para tasas que excedan la cantidad anterior, Se puede demostrar que el tamaño de la lista se vuelve superpolinomialmente grande. ${\displaystyle BSC_{p}}$ ${\displaystyle (p,L)}$ ${\displaystyle R\leqslant 1-H_{q}(p)-{\tfrac {1}{L}}.}$ ${\displaystyle L}$

Un evento "malo" se define como aquel en el que, dada una palabra recibida y mensajes sucede que , para cada lugar está la fracción de errores que deseamos corregir y es la bola de Hamming de radio con la palabra recibida como centro . ${\displaystyle y\in [q]^{n}}$ ${\displaystyle L+1}$ ${\displaystyle m_{0},\ldots ,m_{L}\in [q]^{k},}$ ${\displaystyle {\mathcal {C}}(m_{i})\in B(y,pn)}$ ${\displaystyle 0\leqslant i\leqslant L}$ ${\displaystyle p}$ ${\displaystyle B(y,pn)}$ ${\displaystyle pn}$ ${\displaystyle y}$

Ahora bien, la probabilidad de que una palabra clave asociada con un mensaje fijo se encuentre en una bola de Hamming está dada por ${\displaystyle {\mathcal {C}}(m_{i})}$ ${\displaystyle m_{i}\in [q]^{k}}$ ${\displaystyle B(y,pn)}$

${\displaystyle \Pr \left[C(m_{i})\in B(y,pn)\right]={\frac {\mathrm {Vol} _{q}(y,pn)}{q^{n}}}\leqslant q^{-n(1-H_{q}(p))},}$

donde la cantidad es el volumen de una bola de Hamming de radio con la palabra recibida como centro. La desigualdad en la relación anterior se deriva del límite superior del volumen de una pelota de Hamming. La cantidad proporciona una muy buena estimación del volumen de una bola de Hamming de radio centrado en cualquier palabra. Dicho de otra manera, el volumen de una bola de Hamming es invariante en la traducción. Para continuar con el esquema de prueba, evocamos el límite de unión en la teoría de la probabilidad que nos dice que la probabilidad de que ocurra un mal evento para un determinado está limitada superiormente por la cantidad . ${\displaystyle Vol_{q}(y,pn)}$ ${\displaystyle pn}$ ${\displaystyle y}$ ${\displaystyle q^{H_{q}(p)}}$ ${\displaystyle p}$ ${\displaystyle [q]^{n}.}$ ${\displaystyle (y,m_{0},\dots ,m_{L})}$ ${\displaystyle q^{-n(L+1)(1-H_{q}(p))}}$

Teniendo en cuenta lo anterior, se puede demostrar que la probabilidad de que ocurra "cualquier" evento negativo es menor que . Para mostrar esto, analizamos todas las posibles palabras recibidas y cada posible subconjunto de mensajes en ${\displaystyle 1}$ ${\displaystyle y\in [q]^{n}}$ ${\displaystyle L}$ ${\displaystyle [q]^{k}.}$

Pasando ahora a la prueba de la parte (ii), debemos demostrar que hay muchas palabras de código superpolinomiales alrededor de cada cuando la velocidad excede la capacidad de decodificación de listas. Necesitamos demostrar que es superpolinomialmente grande si la tasa . Corregir una palabra clave . Ahora, por cada elegido al azar, tenemos ${\displaystyle y\in [q]^{n}}$ ${\displaystyle |{\mathcal {C}}\cap B(y,pn)|}$ ${\displaystyle R\geqslant 1-H_{q}(p)+\epsilon }$ ${\displaystyle c\in {\mathcal {C}}}$ ${\displaystyle y\in [q]^{n}}$

${\displaystyle \Pr[c\in B(y,pn)]=\Pr[y\in B(c,pn)]}$

ya que las bolas de Hamming son invariantes de traducción. De la definición del volumen de una bola de Hamming y del hecho de que se elige uniformemente al azar, también tenemos ${\displaystyle y}$ ${\displaystyle [q]^{n}}$

${\displaystyle \Pr[c\in B(y,pn)]=\Pr[y\in B(c,pn)]={\frac {\mathrm {Vol} (y,pn)}{q^{n}}}\geqslant q^{-n(1-H_{q}(p))-o(n)}}$

Definamos ahora una variable indicadora tal que ${\displaystyle X_{c}}$

${\displaystyle X_{c}={\begin{cases}1&c\in B(y,pn)\\0&{\text{otherwise}}\end{cases}}}$

Tomando la expectativa del volumen de una bola de Hamming tenemos

${\displaystyle {\begin{aligned}E[|B(y,pn)|]&=\sum _{c\in {\mathcal {C}}}E[X_{c}]\\[4pt]&=\sum _{c\in {\mathcal {C}}}\Pr[X_{c}=1]\\[4pt]&\geqslant \sum q^{-n(1-H_{q}(p)+o(n))}\\[4pt]&=\sum q^{n(R-1+H_{q}(p)+o(1))}\\[4pt]&\geqslant q^{\Omega (n)}\end{aligned}}}$

Por lo tanto, mediante el método probabilístico, hemos demostrado que si la tasa excede la capacidad de decodificación de listas, entonces el tamaño de la lista se vuelve superpolinomialmente grande. Esto completa el boceto de prueba para la capacidad de decodificación de listas.

Lista de decodificabilidad de los códigos Reed-Solomon

En 2023, basándose en tres trabajos fundamentales, ^{[1] [2] [3]} los teóricos de la codificación demostraron que, con alta probabilidad, los códigos Reed-Solomon definidos sobre puntos de evaluación aleatorios son listas decodificables hasta la capacidad de decodificación de listas sobre alfabetos de tamaño lineal. .

Algoritmos de decodificación de listas

En el período de 1995 a 2007, la comunidad de teorías de codificación desarrolló algoritmos de decodificación de listas progresivamente más eficientes. Algoritmos para códigos Reed-Solomon que pueden decodificar hasta el radio de Johnson que existe donde es la distancia normalizada o distancia relativa. Sin embargo, para los códigos Reed-Solomon, esto significa que se puede corregir una fracción de los errores. Algunos de los algoritmos de decodificación de listas más destacados son los siguientes: ${\displaystyle 1-{\sqrt {1-\delta }}}$ ${\displaystyle \delta }$ ${\displaystyle \delta =1-R}$ ${\displaystyle 1-{\sqrt {R}}}$

• Sudan '95: el primer algoritmo de decodificación de listas no trivial conocido para códigos Reed-Solomon que logró una decodificación de listas eficiente hasta los errores desarrollados por Madhu Sudan . ${\displaystyle 1-{\sqrt {2R}}}$
• Guruswami–Sudan '98 : una mejora del algoritmo anterior para decodificar listas de códigos Reed-Solomon hasta los errores de Madhu Sudan y su entonces estudiante de doctorado Venkatesan Guruswami . ${\displaystyle 1-{\sqrt {R}}}$
• Parvaresh–Vardy '05: en un artículo innovador, Farzad Parvaresh y Alexander Vardy presentaron códigos que se pueden decodificar en listas más allá del radio para tasas bajas . Sus códigos son variantes de los códigos Reed-Solomon que se obtienen evaluando polinomios correlacionados en lugar de como en el caso de los códigos Reed-Solomon habituales. ${\displaystyle 1-{\sqrt {R}}}$ ${\displaystyle R}$ ${\displaystyle m\geqslant 1}$ ${\displaystyle 1}$
• Guruswami–Rudra '06: en otro avance más, Venkatesan Guruswami y Atri Rudra brindan códigos explícitos que logran capacidad de decodificación de listas, es decir, se pueden decodificar listas hasta el radio de cualquier . En otras palabras, se trata de corrección de errores con redundancia óptima. Esto respondió a una pregunta que había estado abierta durante unos 50 años. Este trabajo ha sido invitado a la sección Research Highlights de Communications of the ACM (que está “dedicada a los resultados de investigación más importantes publicados en Ciencias de la Computación en los últimos años”) y fue mencionado en un artículo titulado “Coding and Computing Join Forces” en la edición del 21 de septiembre de 2007 de la revista Science. Los códigos que se les dan se denominan códigos Reed-Solomon plegados, que no son más que códigos Reed-Solomon simples, pero vistos como un código sobre un alfabeto más grande mediante un cuidadoso agrupamiento de símbolos de palabras clave. ${\displaystyle 1-R-\epsilon }$ ${\displaystyle \epsilon >0}$

Debido a su ubicuidad y las agradables propiedades algebraicas que poseen, los algoritmos de decodificación de listas para códigos Reed-Solomon fueron el foco principal de los investigadores. El problema de decodificación de listas para códigos Reed-Solomon se puede formular de la siguiente manera:

Entrada : Para un código Reed-Solomon, se nos proporciona el par for , donde es el décimo bit de la palabra recibida y los son puntos distintos en el campo finito y un parámetro de error . ${\displaystyle [n,k+1]_{q}}$ ${\displaystyle (\alpha _{i},y_{i})}$ ${\displaystyle 1\leq i\leq n}$ ${\displaystyle y_{i}}$ ${\displaystyle i}$ ${\displaystyle \alpha _{i}}$ ${\displaystyle F_{q}}$ ${\displaystyle e=n-t}$

Salida : El objetivo es encontrar todos los polinomios de grado como máximo, cuál es la longitud del mensaje tal que para al menos valores de . Aquí nos gustaría tener el menor número posible para que se pueda tolerar un mayor número de errores. ${\displaystyle P(X)\in F_{q}[X]}$ ${\displaystyle k}$ ${\displaystyle p(\alpha _{i})=y_{i}}$ ${\displaystyle t}$ ${\displaystyle i}$ ${\displaystyle t}$

Con la formulación anterior, la estructura general de los algoritmos de decodificación de listas para códigos Reed-Solomon es la siguiente:

Paso 1 : (Interpolación) Encuentre un polinomio bivariado distinto de cero tal que para . ${\displaystyle Q(X,Y)}$ ${\displaystyle Q(\alpha _{i},y_{i})=0}$ ${\displaystyle 1\leq i\leq n}$

Paso 2 : (Búsqueda de raíces/Factorización) Genere todos los polinomios de grado tales que sean un factor de ie . Para cada uno de estos polinomios, verifique si tiene al menos valores de . Si es así, incluya dicho polinomio en la lista de salida. ${\displaystyle k}$ ${\displaystyle p(X)}$ ${\displaystyle Y-p(X)}$ ${\displaystyle Q(X,Y)}$ ${\displaystyle Q(X,p(X))=0}$ ${\displaystyle p(\alpha _{i})=y_{i}}$ ${\displaystyle t}$ ${\displaystyle i\in [n]}$ ${\displaystyle p(X)}$

Dado que los polinomios bivariados se pueden factorizar de manera eficiente, el algoritmo anterior se ejecuta en tiempo polinómico.

Aplicaciones en teoría de la complejidad y criptografía.

Los algoritmos desarrollados para la decodificación de listas de varias familias de códigos interesantes han encontrado aplicaciones interesantes en la complejidad computacional y el campo de la criptografía . A continuación se muestra una lista de muestra de aplicaciones fuera de la teoría de la codificación:

• "Construcción de predicados fundamentales a partir de permutaciones unidireccionales" .
• Predicción de testigos para problemas de búsqueda de NP.
• Amplificación de la dureza de las funciones booleanas.
• Dureza promedio de matrices permanentes o aleatorias.
• Extractores y generadores pseudoaleatorios .
• Rastreo eficiente de traidores.

Referencias

1. Brakensiek, Josué; Gopi, Sivakanth; Makam, Visu (2 de junio de 2023). "Los códigos genéricos Reed-Solomon logran capacidad de decodificación de listas". Actas del 55º Simposio Anual de ACM sobre Teoría de la Computación . STOC 2023. Nueva York, NY, EE. UU.: Asociación de Maquinaria de Computación. págs. 1488-1501. arXiv : 2206.05256 . doi :10.1145/3564246.3585128. ISBN 978-1-4503-9913-5.
2. Guo, Zeyu; Zhang, Zihan (6 de noviembre de 2023). "Los códigos Reed-Solomon perforados aleatoriamente logran la capacidad de decodificación de listas sobre alfabetos de tamaño polinómico". 2023 64.º Simposio anual del IEEE sobre fundamentos de la informática (FOCS) . FOCS 2023, Santa Cruz, California, EE. UU. IEEE. págs. 164-176. arXiv : 2304.01403 . doi :10.1109/FOCS57990.2023.00019. ISBN 979-8-3503-1894-4.
3. Alrabiah, Omar; Guruswami, Venkatesan; Li, Ray (2023). "Los códigos Reed-Solomon perforados aleatoriamente logran capacidad de decodificación de listas en campos de tamaño lineal". arXiv : 2304.09445 [cs.IT].

enlaces externos

• Una encuesta sobre la decodificación de listas realizada por Madhu Sudan
• Apuntes de un curso impartido por Madhu Sudan
• Apuntes de un curso impartido por Luca Trevisan
• Apuntes de un curso impartido por Venkatesan Guruswami
• Apuntes de un curso impartido por Atri Rudra
• P. Elias, "Lista de decodificación de canales ruidosos", Informe técnico 335, Laboratorio de investigación en electrónica, MIT, 1957.
• P. Elias, "Códigos de corrección de errores para decodificación de listas", IEEE Transactions on Information Theory, vol. 37, págs. 5 a 12, 1991.
• JM Wozencraft, "List decoding", Informe de progreso trimestral, Laboratorio de investigación en electrónica, MIT, vol. 48, págs. 90–95, 1958.
• Tesis doctoral de Venkatesan Guruswami
• Resultados algorítmicos en la decodificación de listas
• Código Reed-Salomón plegado