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 para grandes tasas de error. La noción 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 un mayor número de errores que el permitido 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 de la palabra recibida, no podría tolerar una fracción mayor 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 noventa, el progreso algorítmico significativo de la comunidad de la teoría de la codificación ha superado esta brecha. Gran parte de este progreso se basa en un modelo relajado de corrección de errores denominado decodificación de lista, 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 en los que 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 descodificador genera una única palabra de código única, 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 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 gobierna la velocidad a la que es posible una comunicación confiable. Hay dos escuelas de pensamiento principales para modelar el comportamiento del canal:
- Modelo probabilístico de ruido 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 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 la 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
Dejar ser 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:
Entrada: palabra recibida, límite de error
Salida: una lista de todas las palabras de códigocuya distancia de martilleo de es como máximo .
Motivación para la decodificación de listas
Dada una palabra recibida , que es una versión ruidosa de alguna palabra de código transmitida , el decodificador intenta sacar la palabra de código transmitida colocando su apuesta en una palabra de código que es "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 mínima de Hamming de un código , entonces existen dos palabras de código y que difieren exactamente en posiciones. Ahora, en el caso donde la palabra recibida es equidistante de las palabras en clave y , la decodificación inequívoca se vuelve imposible ya que el decodificador no puede decidir cuál de y para emitir 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 una decodificación única. Sin embargo, recibió palabras como considerados anteriormente ocurren solo en el peor de los casos y si uno mira la forma en que las bolas de Hamming se empaquetan 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 palabra de código dentro de la distancia de Hamming de la palabra recibida. Se ha demostrado que esta afirmación es válida para un código aleatorio seleccionado de un conjunto natural y más aún para el caso de los códigos Reed-Solomon, que está bien estudiado y es bastante ubicuo en las aplicaciones del mundo real. De hecho, la prueba de Shannon del teorema de la capacidad para canales simétricos q -ary puede verse a la luz de la afirmación anterior para códigos aleatorios.
Bajo el mandato de decodificación de listas, para los errores del peor de los casos, el decodificador puede generar una pequeña lista de palabras de código. Con alguna información complementaria o específica del contexto, es posible podar la lista y recuperar la palabra de código 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 de tiempo polinomial, necesitamos la garantía combinatoria de que cualquier bola de Hamming de radio alrededor de una palabra recibida (dónde es la fracción de errores en términos de la longitud del bloque ) tiene una pequeña cantidad de palabras en clave. 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 bloquedel 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 forma no constructiva que los códigos de tarifa existen que se pueden decodificar en lista hasta una fracción de los errores que se acercan . La cantidadEn la bibliografía se hace referencia a 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 tener al menos una fracciónde los símbolos transmitidos para que sea correcta para recuperar el mensaje. Este es un límite inferior de la teoría de la información sobre el número de símbolos correctos necesarios para realizar la decodificación y, con la decodificación de listas, podemos alcanzar potencialmente este límite de la teoría de la información. Sin embargo, para realizar este potencial, necesitamos códigos explícitos (códigos que se pueden construir en tiempo polinomial) y algoritmos eficientes para realizar la codificación y decodificación.
( p , L ) -lista-decodificabilidad
Para cualquier fracción de error y un entero , un codigo se dice que es una lista decodificable 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 clave dentro de la distancia de Hamming de es como máximo
Combinatoria de decodificación de listas
La relación entre la decodificación de listas 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 prueba la existencia de-Lista de códigos decodificables 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 una gran cantidad de palabras de 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.
Capacidad de decodificación de listas
- Teorema (capacidad de decodificación de listas). Dejar y Las siguientes dos declaraciones son válidas para una longitud de bloque suficientemente grande .
- i) Si , entonces existe un -lista de código decodificable.
- ii) Si , luego cada -La lista de código decodificable tiene .
- Dónde
- es el función de entropía -ary definida para y extendido por continuidad a
Lo que esto significa es que para tasas que se acercan a la capacidad del canal, existen códigos decodificables de lista 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 . De hecho, el término "capacidad de decodificación de listas" debería leerse en realidad como la capacidad de un canal adversario en la 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 con la decodificación de listas.
Boceto de prueba
La idea detrás de la prueba es similar a la de la prueba de Shannon para la capacidad del canal simétrico binario donde se elige un código aleatorio y muestra que es -lista-decodificable con alta probabilidad siempre que la tasa Para tarifas que excedan la cantidad anterior, se puede mostrar que el tamaño de la lista se vuelve superpolinomialmente grande.
Un evento "malo" se define como aquel en el que, dada una palabra recibida y mensajes sucede que , para cada dónde es la fracción de errores que deseamos corregir y es la bola de Hamming de radio con la palabra recibida como el centro.
Ahora, la probabilidad de que una palabra en clave asociado a un mensaje fijo yace en una bola de Hamming es dado por
donde la cantidad es el volumen de una bola de Hamming de radio con la palabra recibida como el 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 centrado en cualquier palabra en Dicho de otra manera, el volumen de una bola de Hamming es invariante a la traducción. Para continuar con el bosquejo de 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 evento malo para un determinado es superior delimitado por la cantidad .
Teniendo en cuenta lo anterior, se puede demostrar que la probabilidad de que ocurra "cualquier" evento negativo es menor que . Para mostrar esto, trabajamos nuestro camino sobre todas las posibles palabras recibidas. y cada posible subconjunto de mensajes en
Ahora volviendo a la demostración de la parte (ii), necesitamos mostrar que hay superpolinomialmente muchas palabras en código alrededor de cada cuando la velocidad excede la capacidad de decodificación de listas. Tenemos que demostrar que es superpolinomialmente grande si la tasa . Arreglar una palabra en clave. Ahora, para cada elegido al azar, tenemos
ya que las bolas de Hamming son invariantes a la traducción. De la definición del volumen de una bola de Hamming y del hecho de que se elige uniformemente al azar de también tenemos
Definamos ahora una variable indicadora tal que
Tomando la expectativa del volumen de una bola de Hamming tenemos
Por lo tanto, mediante el método probabilístico, hemos demostrado que si la tasa excede la capacidad de decodificación de la lista, entonces el tamaño de la lista se vuelve superpolinomialmente grande. Esto completa el bosquejo de prueba para la capacidad de decodificación de listas.
Algoritmos de decodificación de listas
En el período de 1995 a 2007, la comunidad de la teoría de la 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 es existir donde es la distancia normalizada o distancia relativa. Sin embargo, para los códigos Reed-Solomon, lo que significa una fracción de errores se pueden corregir. Algunos de los algoritmos de decodificación de listas más destacados son los siguientes:
- Sudán '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 desarrollados por Madhu Sudan .
- Guruswami – Sudan '98 : una mejora en el algoritmo anterior para decodificar listas de códigos Reed – Solomon hastaerrores de Madhu Sudan y su entonces estudiante de doctorado Venkatesan Guruswami .
- Parvaresh – Vardy '05: en un artículo innovador, Farzad Parvaresh y Alexander Vardy presentaron códigos que se pueden decodificar en lista más allá del radio para tarifas bajas . Sus códigos son variantes de los códigos Reed-Solomon que se obtienen evaluando polinomios correlacionados en lugar de solo como en el caso de los códigos Reed-Solomon habituales.
- Guruswami – Rudra '06 - En otro gran avance, Venkatesan Guruswami y Atri Rudra dan códigos explícitos que logran la capacidad de decodificación de listas, es decir, pueden decodificarse por listas hasta el radio para cualquier . En otras palabras, se trata de una corrección de errores con una 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 la Comunicación de la 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 que se ven como un código sobre un alfabeto más grande mediante la combinación cuidadosa de símbolos de palabras en clave.
Debido a su ubicuidad y las agradables propiedades algebraicas que poseen, los algoritmos de decodificación de listas para códigos Reed-Solomon fueron un 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 da el par por , dónde es el el bit de la palabra recibida y el son puntos distintos en el campo finito y un parámetro de error .
Salida : el objetivo es encontrar todos los polinomios de grado como máximo que es la longitud del mensaje tal que por al menos valores de . Aquí, nos gustaría tener lo más pequeño posible para poder tolerar un mayor número de errores.
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) Encuentra un polinomio bivariado distinto de cero tal que por .
Paso 2 : (Hallazgo de raíz / Factorización) Salida de todos los grados polinomios tal que es un factor de es decir . Para cada uno de estos polinomios, verifique si por al menos valores de . Si es así, incluya dicho polinomio en la lista de salida.
Dado el hecho de 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 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 de núcleo duro a partir de permutaciones unidireccionales .
- Predicción de testigos para problemas de búsqueda NP.
- Amplificando la dureza de las funciones booleanas.
- Dureza media de la caja de matrices permanentes o aleatorias.
- Extractores y generadores pseudoaleatorios .
- Rastreo eficiente de traidores.
enlaces externos
- Una encuesta sobre decodificación de listas de Madhu Sudan
- Notas de un curso impartido por Madhu Sudan
- Notas 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 de 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 de progreso trimestral, Laboratorio de investigación de electrónica, MIT, vol. 48, págs. 90–95, 1958.
- Venkatesan Guruswami 's tesis doctoral
- Resultados algorítmicos en la decodificación de listas
- Código plegado Reed-Solomon