Descodificación de listas

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 tasas de error elevadas. El concepto fue propuesto 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, de las cuales una es correcta. Esto permite manejar una mayor cantidad de errores que la que permite la decodificación única.

El modelo de decodificación único en la teoría de la codificación , que está restringido a generar una única palabra de código válida a partir de la palabra recibida, no podía tolerar una fracción mayor de errores. Esto dio como resultado 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 progreso algorítmico significativo por parte de la comunidad de la teoría de la codificación ha cerrado esta brecha. Gran parte de este progreso se basa en un modelo relajado de corrección de errores llamado decodificación de lista, en el que el decodificador genera una lista de palabras de código para los patrones de error patológico del peor caso 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, que es casi siempre el caso (sin embargo, no se sabe que esto sea cierto para todos los códigos). La mejora aquí es significativa en el sentido de que el rendimiento de corrección de errores se duplica. Esto se debe a que ahora el decodificador no está confinado por la barrera de la mitad de la distancia mínima. Este modelo es muy atractivo porque tener una lista de palabras clave es sin duda mejor que simplemente darse por vencido. El concepto 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 desempeña un papel crucial, ya que regula la velocidad a la que es posible una comunicación fiable. Existen dos escuelas de pensamiento principales en cuanto al modelado del comportamiento del canal:

• Modelo de ruido probabilístico estudiado por Shannon en el que el ruido del canal se modela con precisión en el sentido de que el comportamiento probabilístico del canal es bien conocido y la probabilidad de ocurrencia de 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 de código sujeto 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, en teoría 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 hasta el nivel posible en el caso de un modelo de ruido estocástico más débil.

Formulación matemática

Sea un código corrector 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 puede ahora formularse 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 , error vinculado ${\displaystyle x\in \Sigma ^{n}}$ ${\displaystyle e}$

Salida: Una lista de todas las palabras de código 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 de código transmitida , el decodificador intenta generar la palabra de código transmitida colocando su apuesta en una palabra de código que sea "más cercana" a la palabra recibida. La distancia de Hamming entre dos palabras de código se utiliza como métrica para encontrar la palabra de código más cercana, dada la palabra recibida por el decodificador. Si es la distancia de Hamming mínima de un código , entonces existen dos palabras de código y que difieren exactamente en posiciones. Ahora, en el caso en que la palabra recibida es 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 la corrección de errores inequívoca es imposible, si solo insistimos en la decodificación única. Sin embargo, las palabras recibidas como las consideradas anteriormente ocurren solo en el peor de los casos y si uno observa la forma en que las bolas de Hamming se empaquetan en el 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 de código dentro de la distancia de Hamming desde 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 se han estudiado bien 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 se puede ver 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}$

En el marco de la decodificación de listas, en el caso de los errores más graves, el decodificador puede generar una pequeña lista de palabras clave. Con información contextual específica o información adicional, puede ser posible reducir la lista y recuperar la palabra clave transmitida originalmente. 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 ) tiene una pequeña cantidad de palabras de código. Esto se debe a que el tamaño de la lista en sí es claramente un límite inferior en el 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 en 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 pueden decodificarse en listas hasta una fracción de errores que se aproxima a . La cantidad se conoce en la literatura como la 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 recuperar el mensaje. Este es un límite inferior teórico de la información sobre 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 hacer realidad este potencial, necesitamos códigos explícitos (códigos que se puedan construir en tiempo polinomial) y algoritmos eficientes para realizar la codificación y la decodificación. ${\displaystyle pn}$ ${\displaystyle r}$ ${\displaystyle p}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle R}$ ${\displaystyle 1-R}$ ${\displaystyle 1-R}$ ${\displaystyle R}$

(pag,yo)-descodificabilidad de listas

Para cualquier fracción de error y un 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 -decodificable en lista si para cada , el número de palabras de código dentro de la distancia de Hamming desde 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 un código mediante listas 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 puede decodificarse 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 mediante listas con una buena velocidad y un radio de decodificación de listas mucho mayor que En otras palabras, el límite de Johnson descarta la posibilidad de tener una gran cantidad de palabras de código en una bola de Hamming con un 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). Sea y Las dos afirmaciones siguientes son válidas para una longitud de bloque 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 por 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 continuidad a ${\displaystyle q}$ ${\displaystyle p\in (0,1)}$ ${\displaystyle [0,1].}$

Lo que esto significa es que para velocidades que se aproximan a la capacidad del canal, existen códigos decodificables en forma de lista con listas de tamaño polinomial 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, ya que coincide exactamente con la capacidad de un canal simétrico -ario . De hecho, el término "capacidad de decodificación de listas" debería interpretarse 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 velocidad de un código y la fracción de errores que se pueden corregir bajo la decodificación de listas. ${\displaystyle q}$ ${\displaystyle qSC_{p}}$

Bosquejo de la prueba

La idea detrás de la prueba es similar a la de la prueba de Shannon para la capacidad del canal binario simétrico , donde se elige un código aleatorio y se demuestra que es decodificable en lista con alta probabilidad siempre que la tasa. Para tasas que exceden 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 y mensajes recibidos , sucede que , para cada donde es 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 a un mensaje fijo se encuentre en una bola de Hamming viene 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 bola de Hamming. La cantidad da una muy buena estimación del volumen de una bola de Hamming de radio centrada en cualquier palabra en Dicho de otra manera, el volumen de una bola de Hamming es invariante en la traducción. Para continuar con el esbozo de la prueba, conjuramos 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 malo es menor que . Para demostrarlo, trabajamos sobre todas las posibles palabras recibidas y cada posible subconjunto de mensajes en ${\displaystyle 1}$ ${\displaystyle y\in [q]^{n}}$ ${\displaystyle L}$ ${\displaystyle [q]^{k}.}$

Ahora, volviendo a la prueba de la parte (ii), necesitamos demostrar que hay una cantidad superpolinómica de palabras clave alrededor de cada cuando la tasa excede la capacidad de decodificación de la lista. Necesitamos demostrar que es superpolinómicamente grande si la tasa . Fijemos una palabra clave . Ahora, para cada elegida 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)]}$

Dado que las bolas de Hamming son invariantes en la traslación, a partir de la definición del volumen de una bola de Hamming y del hecho de que se elige de manera uniforme 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 superpolinómicamente grande. Esto completa el esbozo de prueba para la capacidad de decodificación de listas.

Decodificabilidad de la listaCó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 decodificables en listas 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ía de codificación desarrolló algoritmos de decodificación de listas cada vez más eficientes. Existen algoritmos para códigos Reed-Solomon que pueden decodificar hasta el radio de Johnson, que es donde es la distancia normalizada o la 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 errores desarrollado 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 por 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 pueden decodificarse 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 hacerlo simplemente 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 gran avance, Venkatesan Guruswami y Atri Rudra proporcionan códigos explícitos que logran la capacidad de decodificación de listas, es decir, se pueden decodificar en 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 proporcionan 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 la agrupación cuidadosa de símbolos de palabras de código. ${\displaystyle 1-R-\epsilon }$ ${\displaystyle \epsilon >0}$

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

Entrada : Para un código Reed-Solomon, se nos proporciona el par para , donde es el bit n 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 que es la longitud del mensaje tal que para al menos valores de . Aquí, nos gustaría tener lo más pequeño posible para que se pueda tolerar una mayor cantidad 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) Generar todos los polinomios de grado tal que sea un factor de, es decir , . Para cada uno de estos polinomios, verificar si para al menos valores de . Si es así, incluir dicho polinomio en la lista de resultados. ${\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 polinomial.

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 en el campo de la criptografía . A continuación se incluye una lista de ejemplo de aplicaciones fuera de la teoría de codificación:

• Construcción de predicados hard-core 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 media de las cajas permanentes de matrices aleatorias.
• Extractores y generadores pseudoaleatorios .
• Rastreo eficiente de traidores.

Referencias

1. Brakensiek, Joshua; Gopi, Sivakanth; Makam, Visu (2 de junio de 2023). "Los códigos genéricos Reed-Solomon alcanzan la capacidad de decodificación de listas". Actas del 55.º Simposio anual de la ACM sobre teoría de la computación . STOC 2023. Nueva York, NY, EE. UU.: Association for Computing Machinery. 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 alcanzan la capacidad de decodificación de listas sobre alfabetos de tamaño polinomial". 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS) . FOCS 2023, Santa Cruz, CA, 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 sobre campos de tamaño lineal". arXiv : 2304.09445 [cs.IT].

Enlaces externos

• Una encuesta sobre la decodificación de listas realizada por Madhu Sudan
• Notas de un curso impartido por Madhu Sudan
• Apuntes de un curso impartido por Luca Trevisan
• Notas de un curso impartido por Venkatesan Guruswami
• Notas de un curso impartido por Atri Rudra
• P. Elias, "Decodificación de listas para canales ruidosos", Informe técnico 335, Laboratorio de investigación electrónica, MIT, 1957.
• P. Elias, "Códigos de corrección de errores para la decodificación de listas", IEEE Transactions on Information Theory, vol. 37, págs. 5–12, 1991.
• JM Wozencraft, "Decodificación de listas", Informe trimestral de progreso, 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 de Solomon de Reed doblado