10 bit Generatorpolynom korrigiert die Hälfte aller 2-Bit-Fehler aus 42 Bit

[Moritz G. (mbydq2)]

Ich habe versucht mit einem zyklischen 10bit Polynom 2-Bit-Fehler in 
einem 42 Bit Codewort zu korrigieren.
Mit dem richtigen Polynom kann man über die Hälfte der 2-Bit-Fehler 
korrigieren. Man erkauft es sich mit der Überdeckung eines 2-Bit-Fehlers 
durch einen 1-Bit-Fehler, also dem erhöhten Risiko, dass ein 
2-Bit-Fehler als 1-Bit-Fehler falsch korrigiert wird, wenn man den 
1-Bit-Fehler korrigiert.
Um alle 2-Bit-Fehler zu korrigieren müssten >18Bit Redundanz angefügt 
werden. >+56% korrigieren 100% von 4%; +31,25% korrigieren >50% von 
4,76%. Um alle 1-Bit-Fehler zu korrigieren wären eh +10Bit/+31,26% 
nötig, die 50% der 2-Bit-Fehler sind daher kostenlos.
Das im Internet leicht zu findende CRC-10 Polynom {633h, 11000110011b} 
ist zur Korrektur ungeeignet; es ist für Erkennung ausgewählt.
Um für möglichst viele 2-Bit-Fehler genau ein Syndrom zu haben eignen 
sich die Generatorpolynome: {585h, 1413d, 10110000101b}, {50Dh, 1293d, 
10100001101b}, {495h, 1173d, 10010010101b}, {549h, 1353d, 10101001001b}.
Wenn man die Bits vor und nach dem Senden vertauscht kann man gezielt 
bestimmte 2-Bit-Fehler korrigierbar machen.
Im angehängten Archiv befinden sich Dateien mit C-Code und AVR-asm 
(GF(2) Polynomdivision) sowie eine Korrekturtabelle für 495h.
Das Fazit dieses Projektes ist für mich, (dass ich beim Programmieren zu 
viele Fehler mache bzw. mehr Planung und Abstand lohnen) dass mehr als 
ein Bit vollständig zu korrigieren sich i.A. nicht lohnt. {Der 
Aufwandt}/{die Kosten} {ist}/{sind} beträchtlich und übersteigen den 
Nutzen. Aber man kann Polynome finden, die die korrekten Codewörter so 
verteilen, dass viele den Mindestabstand einhalten (gleichmäßig verteilt 
sind) und viele sich in einem Raumbereich häufen. Man sollte die 
Korrektur nie so auslegen, dass von den schwersten Fehlern die man 
behandeln will, alle korrigierbar sind, meist reichen wenige Bit mehr 
als für (F-1)-Bit-Fehler notwendig schon aus, um viele der F-Fehler zu 
korrigieren.
Bei kleinen Codewörtern ist schon 1-Bit-Fehlerkorrektur zu teuer und 
Fehler eh zu unwahrscheinlich, bei großen Codewörtern wird die 
Korrekturtabelle zu teuer (µC). Für Verfahren mit Tabelle gibt es einen 
Sweet-Spot im Bereich 40 bis 80 Bit Codewortlänge.
Die Details in einem:
http://tinyu rl.com/7cet9po
http://krz.ch/BYoU
(Zip-Archiv) zusammengefasst.