En la teoría de la codificación , los códigos Reed-Solomon plegados son como los códigos Reed-Solomon , que se obtienen mapeando Palabras en clave Reed-Solomon sobre un alfabeto más grande mediante la combinación cuidadosa de símbolos de palabras en clave.
Los códigos Reed-Solomon plegados también son un caso especial de los códigos Parvaresh-Vardy .
Usando parámetros óptimos uno puede decodificar con una tasa de R , y lograr un radio de decodificación de 1 - R .
El término "códigos Reed-Solomon plegados" fue acuñado en un artículo por VY Krachkovsky con un algoritmo que presentaba códigos Reed-Solomon con muchos errores aleatorios de "ráfagas en fase" [1] . El algoritmo de decodificación de listas para códigos RS plegados corrige más allá delcon destino a los códigos Reed-Solomon logrados por el algoritmo Guruswami - Sudan para tales errores de ráfaga por fases.
Historia
Uno de los desafíos actuales en la teoría de la codificación es lograr que los códigos de corrección de errores logren una compensación óptima entre la tasa (de codificación) y el radio de corrección de errores. Aunque esto puede no ser posible de lograr en la práctica (debido a problemas de la teoría de codificación de canal ruidoso), teóricamente se pueden lograr compensaciones cuasi óptimas.
Antes de la elaboración de los códigos Reed-Solomon plegados, el mejor radio de corrección de errores logrado era , por códigos Reed-Solomon para todas las tarifas.
Una mejora sobre esto Parvaresh y Vardy consiguieron consolidar los tipos
Para el algoritmo Parvaresh-Vardy puede decodificar una fracción de errores.
Los códigos Reed-Solomon plegados mejoran estas construcciones anteriores y se pueden decodificar en una lista en tiempo polinomial durante una fracción. de errores para cualquier constante .
Definición
Considere un Reed-Solomon código de longitud y dimensión y un parámetro de plegado . Asumir que divide .
Mapeo de códigos Reed-Solomon como este:
dónde es un elemento primitivo en
- .
La versión plegada del código Reed Solomon , denotado es un código de longitud de bloque encima . son solo Códigos Reed Solomon con símbolos consecutivos de palabras de código RS agrupadas.
Descripción gráfica
La definición anterior se aclara mediante el diagrama con , dónde es el parámetro de plegado.
El mensaje se denota por , que cuando se codifica con la codificación Reed-Solomon, consta de valores de a , dónde .
Luego, la agrupación se realiza en grupos de 3 elementos, para dar una palabra de código de longitud sobre el alfabeto .
Algo a observar aquí es que la operación de plegado demostrada no cambia la tasa del código original de Reed-Solomon.
Para probar esto, considere un lineal código, de longitud , dimensión y distancia . La La operación de plegado lo convertirá en un código. Por esto, la tasa será lo mismo.
Códigos Reed-Solomon plegados y encuadernación singleton
Según la versión asintótica del límite único , se sabe que la distancia relativa , de un código debe satisfacer dónde es la tasa del código. Como se demostró anteriormente, dado que la tasa se mantiene, la distancia relativa también cumple con el límite de Singleton.
¿Por qué doblar podría ayudar?
Los códigos Reed-Solomon plegados son básicamente los mismos que los códigos Reed Solomon, solo que se ven en un alfabeto más grande. Para mostrar cómo esto podría ayudar, considere un código Reed-Solomon plegado con. Decodificación de un código Reed-Solomon y un código Reed-Solomon plegado para la misma fracción de erroresson tareas de casi la misma intensidad computacional: se puede desplegar la palabra recibida del código Reed-Solomon plegado, tratarla como una palabra recibida del código Reed-Solomon original y ejecutar el algoritmo de decodificación de listas Reed-Solomon en ella. Obviamente, esta lista contendrá todas las palabras de código Reed-Solomon dobladas dentro de la distancia de la palabra recibida, junto con algunos extras, que podemos expurgar.
Además, decodificar un código Reed-Solomon plegado es una tarea más sencilla. Supongamos que queremos corregir un tercio de los errores. El algoritmo de decodificación elegido debe corregir un patrón de error que corrige cada tercer símbolo en la codificación Reed-Solomon. Pero después de plegar, este patrón de error corromperá todos los símbolos sobrey eliminará la necesidad de corrección de errores. Esta propagación de errores está indicada por el color azul en la descripción gráfica. Esto prueba que para una fracción fija de errores la operación de plegado reduce la flexibilidad del canal para distribuir errores, lo que a su vez conduce a una reducción en el número de patrones de error que deben corregirse.
Podemos relacionar los códigos de Reed Solomon plegados con los códigos de Parvaresh Vardy que codifican un polinomio de grado con polinomios dónde dónde es un polinomio irreducible . Al elegir polinomio irreducible y parámetro deberíamos comprobar si cada polinomio de grado como máximo satisface desde es solo la contraparte modificada de dónde es el elemento primitivo en Por lo tanto, el código RS plegado con símbolos de código agrupados es el código de pedido PV para el conjunto de puntos de evaluación
- .
Si comparamos el código RS plegado con un código PV de orden 2 para el conjunto de puntos de evaluación
podemos ver que en la codificación PV de , para cada y cada aparece en y ,
a diferencia de la codificación FRS plegada en la que aparece solo una vez. Por lo tanto, los códigos PV y RS plegados tienen la misma información, pero solo la tasa de FRS es mayor en un factor dey por lo tanto, la compensación del radio de decodificación de lista es mejor para el código RS plegado simplemente usando la decodificabilidad de lista de los códigos PV. El punto positivo es elegir el código FRS de manera que sean formas comprimidas de código PV adecuado con un rendimiento de corrección de errores similar con una mejor tasa que el código PV correspondiente. Se puede utilizar esta idea para construir un código RS plegado de tasa que son decodificables por lista hasta un radio de aproximadamente por . [2]
Breve descripción general de los códigos Reed-Solomon plegados con decodificación de listas
Un algoritmo de decodificación de listas que se ejecuta en tiempo cuadrático para decodificar el código FRS hasta el radioes presentado por Guruswami. El algoritmo tiene esencialmente tres pasos, a saber, el paso de interpolación en el que se utiliza la interpolación de estilo welch berlekamp para interpolar el polinomio distinto de cero
después de lo cual todos los polinomios con grado satisfaciendo la ecuación derivada de la interpolación. En el tercer paso, se conoce la lista real de palabras de código cercanas al podar el subespacio de solución que tomahora.
Algoritmo de decodificación de lista lineal-algebraica
Guruswami presenta un algoritmo de decodificación de lista de tiempo basado en álgebra lineal, que puede decodificar código Reed-Solomon plegado hasta un radio con un tamaño de lista de . Hay tres pasos en este algoritmo: Paso de interpolación, Paso de búsqueda de raíces y Paso de poda. En el paso de Interpolación intentará encontrar el polinomio del mensaje candidatoresolviendo un sistema lineal. En el paso de búsqueda de raíces, intentará encontrar el subespacio de solución resolviendo otro sistema lineal. El último paso intentará podar el subespacio de solución ganado en el segundo paso. Presentaremos cada paso en detalle a continuación.
Paso 1: el paso de interpolación
Es una interpolación al estilo de Welch-Berlekamp (porque puede verse como la generalización de dimensiones superiores del algoritmo de Welch-Berlekamp). Supongamos que recibimos una palabra en clave de El -código Reed-Solomon plegado como se muestra a continuación
Interpolamos el polinomio distinto de cero
mediante el uso de un parámetro de grado cuidadosamente elegido .
Entonces los requisitos de interpolación serán
Entonces el número de monomios en es
Porque el número de monomios en es mayor que el número de condiciones de interpolación. Tenemos debajo lema
- Lema 1. La satisfacción de la condición de interpolación anterior se puede encontrar resolviendo un sistema lineal homogéneo sobre con como máximo restricciones y variables. Además, esta interpolación se puede realizar en operaciones terminadas . [1]
Este lema nos muestra que el paso de interpolación se puede realizar en un tiempo casi lineal.
Por ahora, hemos hablado de todo lo que necesitamos para el polinomio multivariado. . La tarea restante es centrarse en los polinomios del mensaje..
- Lema 2. Si es un polinomio de mensaje candidato es un polinomio de grado como máximo cuya codificación Plegada Reed-Solomon concuerde con la palabra recibida en al menos columnas con
- luego [2]
Aquí "de acuerdo" significa que todos los los valores en una columna deben coincidir con los valores correspondientes en la palabra de código .
Este lema nos muestra que cualquier polinomio presenta una condición algebraica que debe cumplirse para esos polinomios de mensaje que estamos interesados en la decodificación de listas.
Combinando el Lema 2 y el parámetro , tenemos
Además, podemos obtener el enlace de decodificación
Observamos que el acuerdo fraccionario es
Paso 2: el paso de búsqueda de raíces
Durante este paso, nuestra tarea se centra en cómo encontrar todos los polinomios con grado no mayor a y satisfacer la ecuación que obtenemos del Paso 1, a saber
Dado que la ecuación anterior forma un sistema lineal, las ecuaciones sobre en los coeficientes del polinomio
las soluciones de la ecuación anterior es un subespacio afín de. Este hecho es el punto clave que da lugar a un algoritmo eficiente: podemos resolver el sistema lineal.
Es natural preguntarse qué tan grande es la dimensión de la solución. ¿Existe algún límite superior en la dimensión? Tener un límite superior es muy importante en la construcción de un algoritmo de decodificación de lista eficiente porque simplemente se pueden generar todas las palabras de código para cualquier problema de decodificación dado.
En realidad, tiene un límite superior, como argumenta el lema a continuación.
- Lema 3. Si el orden de Por lo menos (en particular cuando es primitivo), entonces la dimensión de la solución es como máximo . [3]
Este lema nos muestra el límite superior de la dimensión del espacio de solución.
Finalmente, con base en el análisis anterior, tenemos el siguiente teorema
- Teorema 1. Para el código Reed-Solomon plegado de longitud de bloque y tasa lo siguiente es válido para todos los números enteros . Dada una palabra recibida , en tiempo, uno puede encontrar una base para un subespacio de dimensión como máximo que contiene todos los polinomios de mensajes de grado menor que cuya codificación FRS difiere de en como máximo una fracción
- de El posiciones de palabras en clave.
Cuándo , notamos que esto se reduce a un algoritmo de decodificación único con hasta una fracción de errores. En otras palabras, podemos tratar el algoritmo de decodificación único como una especialidad del algoritmo de decodificación de listas. La cantidad es de para las opciones de parámetros que logran un radio de decodificación de lista de .
El teorema 1 nos dice exactamente qué tan grande sería el radio de error.
Ahora finalmente obtenemos el subespacio de la solución. Sin embargo, sigue existiendo un problema. El tamaño de la lista en el peor de los casos es. Pero la lista real de palabras de código cercanas es solo un pequeño conjunto dentro de ese subespacio. Entonces, necesitamos algún proceso para podar el subespacio para reducirlo. Este proceso de poda llevatiempo en el peor de los casos. Desafortunadamente, no se sabe cómo mejorar el tiempo de ejecución porque no sabemos cómo mejorar el límite del tamaño de la lista para el código Reed-Solomon plegado.
Las cosas mejoran si cambiamos el código eligiendo cuidadosamente un subconjunto de todos los grados posibles polinomios como mensajes, el tamaño de la lista muestra ser mucho más pequeño mientras que solo pierde un poco en la tasa. Hablaremos de esto brevemente en el próximo paso.
Paso 3: el paso de la poda
Al convertir el problema de decodificar un código Reed-Solomon plegado en dos sistemas lineales, un sistema lineal que se usa para el paso de interpolación y otro sistema lineal para encontrar el subespacio de la solución candidata, la complejidad del problema de decodificación se reduce exitosamente a cuadrática. Sin embargo, en el peor de los casos, el límite del tamaño de lista de la salida es bastante malo.
Se mencionó en el Paso 2 que si uno elige cuidadosamente solo un subconjunto de todos los grados posibles polinomios como mensajes, el tamaño de la lista se puede reducir mucho. Aquí ampliaremos nuestra discusión.
Para lograr este objetivo, la idea es limitar el vector de coeficientes a un subconjunto especial , que cumple a continuación dos condiciones:
- Condición 1. El conjunto debe ser lo suficientemente grande ).
Esto es para asegurarse de que la tasa se reducirá como máximo en un factor de .
- Condición 2. El conjunto debe tener una intersección baja con cualquier subespacio de dimensión satisfactorio y Este subconjunto se denomina subconjunto evasivo del subespacio.
El límite para el tamaño de la lista en el peor de los casos es , y se puede reducir a un límite relativamente pequeño mediante el uso de subconjuntos evasivos del subespacio.
Durante este paso, como tiene que verificar cada elemento del subespacio de solución que obtenemos del Paso 2, se necesita tiempo en el peor de los casos es la dimensión del subespacio de la solución).
Dvir y Lovett mejoraron el resultado basándose en el trabajo de Guruswami, que puede reducir el tamaño de la lista a una constante.
Aquí solo se presenta la idea que se utiliza para podar el subespacio de la solución. Para conocer los detalles del proceso de poda, consulte los artículos de Guruswami, Dvir y Lovett, que se enumeran en la referencia.
Resumen
Si no consideramos el Paso 3, este algoritmo se puede ejecutar en tiempo cuadrático. A continuación se incluye un resumen de este algoritmo.
Pasos |
|
---|---|
Tiempo de ejecución | |
Radio de error | |
Tamaño de lista |
Ver también
Referencias
- Notas de la conferencia de Atri Rudra : Códigos Reed-Solomon plegados
- Notas de la conferencia de Atri Rudra: Límites
- Un artículo de Atri Rudra y Venkatesan Guruswami : Decodificando Códigos Plegados Reed-Solomon
- Un capítulo sobre decodificación de listas de códigos Reed-Solomon plegados: decodificación de listas de códigos Reed-Solomon plegados
- Notas de la conferencia de Venkatesan Guruswami: límites elementales en códigos
- Notas de la conferencia de Venkatesan Guruswami: Decodificación de listas Doblado Reed-Solomon Code
- Guruswami, Venkatesan (2011). "Decodificación de lista lineal-algebraica de códigos Reed-Solomon plegados". 2011 IEEE 26th Annual Conference on Computational Complexity : 77–85. arXiv : 1106.0436 . Código Bibliográfico : 2011arXiv1106.0436G . doi : 10.1109 / CCC.2011.22 . ISBN 978-1-4577-0179-5.
- Dvirl, Zeev; Lovett, Shachar (2011). "Conjuntos evasivos subespaciales". arXiv : 1110,5696 [ cs.CC ].
- Tesis de doctorado de Kristian Brander : interpolación y decodificación de listas de códigos algebraicos
- Krachkovsky, VY (2003). "Códigos Reed-Solomon para corregir ráfagas de errores por fases". IEEE Trans. Inf. Teoría . 49 (11): 2975–2984. doi : 10.1109 / TIT.2003.819333 .