Encoding / Error Correction Herausforderung

StackOverflow https://stackoverflow.com/questions/2393362

Frage

Ist es zu kodieren und erste 4-Byte-Nachricht in 8 Bytes mathematisch möglich und wenn eine der 8 Bytes vollständig fallen gelassen wird und eine andere ist falsch, die anfängliche 4-Byte-Nachricht zu rekonstruieren? Es gäbe keine Möglichkeit, erneut zu übertragen sein, noch würde die Position der abgelegten Byte bekannt sein.

Wenn man benutzt Reed-Solomon-Fehlerkorrektur mit 4 „Parität“ auf das Ende der 4 „Daten“ Bytes gehefteten Bytes, wie DDDDPPPP, und Sie mit DDDEPPP Ende (wobei E ein Fehler) und ein Paritäts Byte fallen gelassen wurde, glaube ich nicht, es gibt einen Weg, um die erste Nachricht zu rekonstruieren (obwohl korrigiert mich wenn ich falsch bin) ...

Was ist die Multiplikation (oder eine andere mathematische Operation) die anfängliche 4-Byte-Nachricht durch eine Konstante, dann Eigenschaften eines inversen mathematischen Operation verwendet, um zu bestimmen, was Byte fallen gelassen wurde. Oder verhängen einige Einschränkungen für die Struktur der Nachricht so alle anderen Byte Bedürfnisse ungerade sein und die anderen müssen auch sein.

Alternativ kann anstelle von Bytes, es könnte auch 4 Dezimalziffern in irgendeiner Art und Weise in 8 Dezimalziffern codiert sein, in denen Fehler detektiert werden können und unter den gleichen Umständen korrigiert oben erwähnt - keine erneute Übertragung und der Lage des abgelegten Byte nicht bekannt ist, .

Ich suche nach irgendwelchen verrückten Ideen jemand haben könnte ... Irgendwelche Ideen da draußen?

EDIT:

Es kann ein bisschen gekünstelt sein, aber die Situation, dass ich versuche zu lösen ist eine, wo Sie haben, sagen wir mal, einen defekten Drucker, die Drucke aus allen wichtigen Telefonnummern auf ein Formular, das dann per Post an eine Verarbeitungsfirma aus die verwendet OCR die Formulare zu lesen. Die OCR wird nicht perfekt sein, aber es sollte in der Nähe mit nur Ziffern erhalten zu lesen. Der fehlerhafte Drucker könnte ein größeres Problem sein, wo es eine ganze Reihe fallen können, aber es gibt keine Möglichkeit zu wissen, welche es wird fallen, aber sie werden immer in der richtigen Reihenfolge herauskommen, werden es nicht sein getauscht Ziffern.

Die Form so verändert werden könnte, dass es immer druckt einen Raum zwischen den ersten vier Zahlen und die Fehlerkorrektur-Nummern, also 1234 5678, so dass man würde wissen, ob ein 1.234 Anfangs Ziffer fallen gelassen wurde oder ein 5678-Fehlerkorrektur digit wurde fallen gelassen , wenn das das Problem leichter zu lösen macht. Ich denke, ein wenig ähnlich, wie sie Kreditkartennummern über Algorithmus überprüfen, aber in vierstelligen Stücken schneiden.

Wir hoffen, dass eine Klarstellung bietet, was ich suche ...

War es hilfreich?

Lösung

In Abwesenheit von „schön“ algebraischer Struktur, ich vermute, dass es wird schwer sein, ein knappes Schema zu finden, dass Sie die ganzen Weg bis 10 ** 4 Codeworte bekommt, da informationstheoretisch, gibt es nicht viel von schlaff. (Der einzigen unten verwenden kann, um GF (5) für 5 ** 5 = 3125) Glücklicherweise ist das Problem klein genug ist, dass Sie Methode gierig Code-Konstruktion Shannons versuchen könnten (ein Codewort finden, die nicht in Konflikt hat mit einer bereits gewählt, fügen sie es den Satz).

Encode bis zu 35 Bits als eine biquadratische Polynom f über GF (128). Bewerten Sie das Polynom an acht vorgegebenen Punkten x0, ..., X7 und kodieren als 0f (x0) 1f (x1) 0f (x2) 1f (x3) 0f (x4) 1f (x5) 0f (x6) 1f (X7), wo die abwechselnden Nullen und Einsen in der MSB gespeichert.

Beim Dekodieren erster Blick auf der MSBs. Wenn das MSB des Index nicht mod 2 überein, so dass Byte ist beschädigt und / oder es wurde durch eine Deletion nach links verschoben. Angenommen, es ist gut, und verschieben Sie sich nach rechts zurück (möglicherweise mehr verschiedenen möglichen Werten an einem Punkt thesaurierend). Jetzt haben wir mindestens sieben Bewertungen eines vierten Grades Polynom f an bekannten Punkten, von denen höchstens ein korrupt ist. Wir können nun versuchen, alle Möglichkeiten für die Korruption.

EDIT: bmm6o hat den Anspruch weit fortgeschritten, dass der zweite Teil meiner Lösung nicht korrekt ist. Ich bin nicht einverstanden.

Lassen Sie uns Überprüfung der Möglichkeiten für den Fall, dass die MSBs sind 0101101. Es sei X die Byte-Array gesendet und Y ist das Array von Bytes empfangen. Auf dem einen Seite, Y [0], Y [1], Y [2], Y [3] haben korrekt MSBs und vermuten X [0], X [1], X [2], X [3] sein, . Auf der anderen Seite, Y [4], Y [5], Y [6] haben falschen MSBs und X sind, vermutet wird [5], X [6], X [7].

sein

Wenn X [4] fallen gelassen wird, dann haben wir sieben korrekte Auswertungen von f.

Wenn X [3] fallen gelassen wird und X [4] beschädigt ist, dann haben wir eine falsche Bewertung auf 3 und sechs korrekte Auswertungen.

Wenn X [5] fallen gelassen wird und X [4] beschädigt ist, dann haben wir eine falsche Bewertung auf 5 und sechs korrekte Auswertungen.

Es gibt mehr Möglichkeiten, neben diesen, aber wir haben nie weniger als sechs korrekte Bewertungen, die f zu erholen genügen.

Andere Tipps

Ich glaube, Sie müssten studieren, was Löschcodes bieten könnten. Ich kenne keine Grenzen selbst, aber vielleicht eine Art von MDS Code könnte dies erreichen.

EDIT: Nach kurzer Suche fand ich RSCode Bibliothek und in der Beispiel es sagt, dass 

In general, with E errors, and K erasures, you will need
* 2E + K bytes of parity to be able to correct the codeword
* back to recover the original message data.

So sieht aus wie Reed-Solomon-Code in der Tat ist die Antwort und Sie können tatsächlich die Erholung von einer Löschung erhalten und einem Fehler in 8,4-Code.

Parity-Codes arbeiten, solange zwei verschiedene Datenbytes werden nicht durch Fehler oder Verlust betroffen und solange Fehler gleich nicht an Datenbyte, während ein Paritäts Byte verloren, imho.

Fehlerkorrekturcodes können im Allgemeinen Griff Löschungen, aber in der Literatur der Position des Löschens wird als bekannt vorausgesetzt. In den meisten Fällen wird die Löschung durch den Demodulator eingeführt werden, wenn es ein geringes Vertrauen ist, daß die richtigen Daten aus dem Kanal abgerufen werden können. Zum Beispiel, wenn das Signal nicht klar 0 oder 1 ist, kann das Gerät an, dass die Daten verloren gegangen ist, anstatt die Einführung eines Fehlers zu riskieren. Da eine Löschung im Wesentlichen ein Fehler mit einer bekannten Position ist, sind sie viel einfacher zu beheben.

Ich bin mir nicht sicher, was Ihre Situation ist, wo Sie einen einzelnen Wert verlieren können und Sie können immer noch sicher sein, dass die restlichen Werte in der richtigen Reihenfolge geliefert werden, aber es ist nicht eine Situation, klassische Theorie Adressen Codierung.

Was algorithmist oben ist darauf hindeutet, ist dies: Wenn Sie sich nur 7 Bits an Informationen beschränken, können Sie das achte Bit jedes Byte füllen mit abwechselnd 0 und 1, die Ihnen erlauben, die Platzierung des fehlenden Byte zu wissen . Das heißt, legt ein 0 in dem hohen Bit von Byte 0, 2, 4, 6 und ein 1 in dem hohen Bits des anderen. Auf der Empfangsseite, wenn Sie nur 7 Bytes empfangen, wurden die fehlenden ein zwischen Bytes, deren High-Bits übereinstimmen gesunken. Leider ist das nicht ganz richtig: Wenn die Löschung und der Fehler benachbart sind, können Sie nicht sofort wissen, welches Byte fallen gelassen wurde. Z. B. 0101101 High-Bits von Fallenlassen der 4. Byte, oder von einem Fehler im 4. Byte und Fallenlassen der 3. oder von einem Fehler im 4. Byte und Fallenlassen der fünften Folge haben könnte.

Sie könnten den linearen Code verwenden: 

1 0 0 0  0 1 1 1
0 1 0 0  1 0 1 1
0 0 1 0  1 1 0 1
0 0 0 1  1 1 1 0

(dh Sie Daten wie (a, b senden werden, c, d, b + c + d, a + c + d, a + b + d, a + b + c) (wobei zusätzlich umgesetzt wird mit XOR, da a, b, c, d sind Elemente von GF (128))). Es ist ein linearer Code mit Abstand 4, so dass es einen Single-Byte-Fehler korrigieren kann. Sie können mit Syndrom Decodierung und da der Code ist selbst dual, die Matrix H wird die gleiche sein wie oben.

In dem Fall, wo es einen gefallen Byte, können Sie die Technik verwenden, oben, um zu bestimmen, welches es ist. Sobald Sie das bestimmt haben, sind Decodierung Sie im Wesentlichen einen anderen Code - die „durchstochen“ Code erstellt durch das gegebene Byte fallen. Da die punktierte Codes noch linear ist, können Sie Syndrom Decodierung verwenden, um die Fehler zu bestimmen. Sie würden die Paritätsprüfmatrix für jede der verkürzten Codes berechnen müssen, aber Sie können diese vor der Zeit tun. Der verkürzte Code hat Abstand 3, so dass es keine Single-Byte-Fehler korrigieren kann.

Im Fall von Dezimalstellen, eine Annahme geht mit erster Ziffer ungerade, zweite Ziffer sogar, dritte Ziffer ungerade, etc. - mit zwei Ziffern, Sie erhalten 00-99, die auch in 3 ungerade / dargestellt werden können / ungeradee Ziffern (125 gesamt Kombinationen) - 00 = 101, 01 = 103, 20 = 181, 99 = 789, etc. So eine kodiert zwei Sätze von Dezimalziffern in insgesamt 6 Ziffern, dann werden die letzten beiden Ziffern Signify Dinge über die ersten Sätze von 2 Ziffern oder eine Prüfsumme von einer Art ... Die vorletzte Ziffer, nehme ich an, könnte eine Art von gerade / ungerade-Anzeige auf jedem der ersten 2 Ziffer Anfangsnachrichten (1 = even ersten 2 Ziffern sein, 3 = ungerade ersten beiden Ziffern) und folgen dem Muster der ungeraden sein. Dann könnte die letzte Ziffer der Stelle einer Summe der einzelnen Ziffern der sein, auf diese Weise, wenn eine Ziffer fehlte, wäre es sofort offensichtlich und korrigiert werden konnte die letzte Ziffer richtig war angenommen wird. Obwohl, wäre es Dinge abwerfen, wenn eine der beiden letzten Ziffern wurden fallen gelassen ...

Es sieht theoretisch möglich sein, wenn wir 1-Bit-Fehler-Byte in falsch annehmen. Wir brauchen 3 Bits fallen gelassen Byte und 3 Bits zu identifizieren falsch Byte und 3 Bits zu identifizieren falsch Bit zu identifizieren. Wir haben 3 mal, dass viele zusätzliche Bits.

Aber wenn wir eine beliebige Anzahl von Bits Fehler in der falschen Byte identifizieren müssen, kommt es zu 30 Bits. Auch das Aussehen mit 32 Bit möglich sein, obwohl 32 ein wenig zu nah für meinen Trost ist.

Aber ich weiß nicht heiß zu kodieren, das zu bekommen. Versuchen Turbo?

Tatsächlich, wie Krystian gesagt, wenn Sie einen RS-Code zu korrigieren, sowohl die Nachricht und die „Parität“ Bytes korrigiert werden, solange Sie v haben + 2e <(nk), wobei v die Anzahl der Löschungen (Sie kennen die Position) und e die Anzahl der Fehler. Dies bedeutet, dass, wenn Sie Fehler haben, können Sie bis zu (nk) korrigieren / 2 Fehler, oder (nk-1) Löschungen (etwa das Doppelte der Anzahl der Fehler) oder eine Mischung aus beidem (siehe Blahut den Artikel: Trans Techniken zur Fehlerkontrollcodes und < a href = "http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.84.2084&rep=rep1&type=pdf" rel = "nofollow"> ein universeller Reed-Solomon-Decoder ).

Was ist noch schöner ist, dass Sie überprüfen können, dass die Korrektur erfolgreich war: durch Überprüfung, dass das Syndrom-Polynom enthält nur 0-Koeffizienten, wissen Sie, dass die Meldung + Paritätsbytes sind beide richtig. Sie können das tun, bevor zu überprüfen, ob die Nachricht eine Korrektur benötigt, und auch können Sie die Prüfung tun, nachdem die Decodierung beide zu überprüfen, dass die Nachricht und das Paritätsbytes vollständig repariert wurden.

Das gebundene v + 2e <(n-k) optimal ist, kann man nicht besser machen (das ist, warum Reed-Solomon ist ein optimalen Fehlerkorrekturcode genannt). In der Tat ist es möglich, über diese Grenze hinaus gehen mit Brute-Force annähert, bis zu einem bestimmten Punkt (können Sie gewinnen 1 oder 2 weitere Symbole für jeweils 8 Symbole) mit

Nicht verbunden mit StackOverflow
scroll top