¿Existe un código tipo Reed-Solomon sobre símbolos decimales?

8

Se garantiza que un código de corrección de errores Reed-Solomon que consta de N símbolos detectará hasta N reemplazos de un solo símbolo en una entrada arbitrariamente larga más el propio ECC, y también se garantiza que corrige hasta un solo símbolo de piso (N / 2) reemplazos en el mismo.

No puedo decir que entiendo las matemáticas detrás de Reed-Solomon ECC, pero noto que todas las implementaciones que pude encontrar operan en símbolos en la base 16, 64 o 256. Esto parece sugerir que 1024, etc., también son bases en las que esto esquema puede operar con el polinomio correcto.

¿Es posible tener un esquema de ECC con exactamente las propiedades anteriores que funciona con símbolos decimales? ¿Puede Reed-Solomon ser adaptado trivialmente para este propósito?

(Esta pregunta es provocada por mi respuesta a una pregunta desconcertante. SE )

Roman Starkov
fuente

Respuestas:

5

La propiedad de los códigos Reed – Solomon que usted menciona se conoce como Máxima distancia de separación, y los códigos con esta propiedad se conocen como códigos MDS . En la teoría de la codificación, el tipo de código más popular es un código lineal, y estos solo se definen sobre alfabetos que son potencias primarias. Sin embargo, en la literatura puede encontrar algunos documentos sobre códigos MDS en alfabetos arbitrarios; Te dejaré investigar eso tú mismo.

Para el caso específico norte=1, hay un código MDS muy simple, a saber, suma de comprobación: agrega a los datos originales un nuevo dígito cuyo valor es la suma negada de los otros dígitos (de modo que todos los dígitos nuevos sumen cero). Este código puede detectar cualquier error individual.

Yuval Filmus
fuente
Compárese con el caso de los números de tarjetas de crédito: en.wikipedia.org/wiki/Luhn_algorithm
Aaron Brick
Eso también se vincula con el algoritmo Verhoeff y el algoritmo Damm que mejoran en Luhn al detectar cada transposición en dígitos adyacentes utilizando solo un solo dígito de control decimal. ¡Impresionante! Luhn solo detecta algunos, mientras que la suma de verificación simple mod 10 no detecta ninguno (pero para números cortos, la suma de verificación mod 10 se puede verificar mentalmente, lo que podría ser útil)
Roman Starkov