Gibt es einen Reed-Solomon-ähnlichen Code über Dezimalsymbolen?

8

Ein Reed-Solomon-Fehlerkorrekturcode, der aus N Symbolen besteht, erkennt garantiert bis zu N Einzelsymbol-Ersetzungen in einer beliebig langen Eingabe plus dem ECC selbst und korrigiert garantiert bis zu Etage (N / 2) Einzelsymbol Ersatz in der gleichen.

Ich kann nicht behaupten, die Mathematik hinter Reed-Solomon ECC zu verstehen, aber ich stelle fest, dass alle Implementierungen, die ich finden konnte, auf Symbolen in Basis 16, 64 oder 256 funktionieren. Dies scheint darauf hinzudeuten, dass 1024 usw. auch Grundlagen sind, in denen dies ist Schema kann mit dem richtigen Polynom arbeiten.

Ist es möglich, ein ECC-Schema mit genau den oben genannten Eigenschaften zu haben, das mit Dezimalsymbolen arbeitet? Kann Reed-Solomon für diesen Zweck trivial angepasst werden?

(Diese Frage wird durch meine Antwort auf eine rätselhafte SE-Frage ausgelöst. )

Roman Starkov
quelle

Antworten:

5

Die von Ihnen erwähnte Eigenschaft von Reed-Solomon-Codes wird als maximale Abstandstrennbarkeit bezeichnet, und Codes mit dieser Eigenschaft werden als MDS-Codes bezeichnet . In der Codierungstheorie ist der beliebteste Codetyp ein linearer Code, und diese werden nur über Alphabete definiert, die Primzahlen sind. In der Literatur finden Sie jedoch einige Artikel zu MDS-Codes auf beliebigen Alphabeten. Ich lasse Sie das selbst recherchieren.

Für den speziellen Fall N.=1gibt es einen sehr einfachen MDS-Code, nämlich die Prüfsumme: Sie fügen den Originaldaten eine neue Ziffer hinzu, deren Wert die negierte Summe der anderen Ziffern ist (so dass alle neuen Ziffern Null ergeben). Dieser Code kann jeden einzelnen Fehler erkennen.

Yuval Filmus
quelle
Vergleichen Sie mit dem Fall von Kreditkartennummern: en.wikipedia.org/wiki/Luhn_algorithm
Aaron Brick
Dies ist auch mit dem Verhoeff-Algorithmus und dem Damm-Algorithmus verbunden, die Luhn verbessern, indem jede Transposition in benachbarten Ziffern mit nur einer einzigen Dezimalprüfstelle erfasst wird. Beeindruckend! Luhn erkennt nur einige, während die einfache Mod 10-Prüfsumme keine erkennt (aber für kurze Zahlen kann die Mod 10-Prüfsumme mental überprüft werden, was nützlich sein könnte)
Roman Starkov