¿Cómo incorporar borraduras (lugares de error conocido) en localizador de error Reed-Solomon de cómputo?

Question

Estoy implementando Reed-Solomon de corrección de errores para los formatos de código de barras 2D (parte de la ZXing proyecto). Ya tiene un trabajo de implementación, que me las arreglé para crear, sobre todo hace años, cuando yo entendía las matemáticas más.

La aplicación sólo corrige los errores (malinterpretar la palabra clave en ubicación desconocida), no borraduras (ubicación conocida). Por supuesto, borraduras puede ser trivialmente tratados como errores en el olvido de que usted sabe la ubicación, pero la utilización de un extra de corrección de errores de la palabra de esta manera. En su lugar, yo sé que uno tiene que utilizar el conocimiento de la ubicación del error para poder corregir el máximo número posible de errores.

Entiendo que el conocimiento de la ubicación le permite construir parte del error localizador de polinomio. Si los lugares son $j_1$, $j_2$, ... a continuación, parte del error localizador polinomio es

$\sigma(x) = (1 - \exp(j_1)x) (1 - \exp(j_2)x)\cdots$

Lo que aún no sé es cómo utilizar esta en el algoritmo! ¿Cómo funciona el error localizador de usar esto como un punto de partida para localizar el resto de los errores? Siento que es algo tan simple como multiplicar o dividir algo por este parcial error localizador de polinomio.

Estoy usando el algoritmo de Euclides para encontrar el error localizador de corrección de error y el polinomio, no de Berlekamp-Massey. El algoritmo es más o menos el uno en el PDF417 página de la Wikipedia.

Answer 1

Zhiyuan Yan y me presentó un documento sobre este tema en el 2009 IEEE Simposio Internacional sobre Teoría de la Información. No voy a referirme a las Actas de este Simposio, porque la versión en línea está oculto detrás de Del IEEE paywall y debido a que el algoritmo dado no es correcta. La versión corregida está disponible en arxiv. Aquí es lo que el resumen dice.

El algoritmo de Euclides extendido (EEE) para que el polinomio mayor de los divisores comunes es comúnmente utilizado en la solución de la clave de la ecuación en la decodificación de Reed-Solomon (RS) de los códigos, y más generalmente en el CIISB en la decodificación. Para esta aplicación en particular, las iteraciones en el EEE se detuvo cuando el grado del polinomio resto cae por debajo de un umbral. Mientras determinar el grado de un polinomio es una tarea sencilla para los seres humanos, implementación de hardware de esta parada de la regla es más complicado. En este trabajo se describe una versión modificada de la EEE que está específicamente adaptado a la decodificador RS problema. Este algoritmo modificado requiere ningún grado de cómputo o comparación con un umbral, y se utiliza un número fijo de iteraciones. Otra ventaja de esta versión modificada en su aplicación a los errores-y-borraduras decodificación problema para RS códigos significativos ahorros de hardware puede ser logrado a través de la perfecta cálculo.

Answer 2

He encontrado la solución(s):

• ya sea calcular el Forney síndrome de down (mediante el cálculo de erasures_locator * síndrome de down, donde * es el campo de galois polinomio de multiplicación).
• modificar su decodificación iterativa del algoritmo (BM o Euclidiana o de otro tipo) directamente de la cuenta para los borrones localizador polinomio en la inicialización, y retocando un par de otras variables (como el número de iteraciones que se deben restar por el número de trazos), a continuación, usted directamente puede decodificar borraduras, al mismo tiempo, como los errores sin necesidad de utilizar el Forney síndrome de down (sólo el estándar de síndrome de down). Una fe de erratas decodificador utilizando Euclidiana algoritmo se describe a continuación: algoritmos Eficientes para la codificación Reed-Solomon códigos con borrones, Todd Mateer. Yo también describe cómo hacer que con el de Berlekamp-Massey algoritmo en este de MANERA posterior.

Ambos métodos dan el mismo resultado, he verificado en mi aplicación (he implementado ambos enfoques).

Tenga en cuenta que probablemente hay otros enfoques más allá de estos dos, pero a mi conocimiento, son por mucho el más común.