Blockerkennung im wiederholten Strom

Question

Ich muss einen Datenblock von einem wiederholten Datenstrom wiederherstellen. Ich suche zu sehen, welche Algorithmen möglicherweise bereits dafür existieren, da es sich nicht wie eine neuartige Situation anfühlt.

Hier sind die Einzelheiten:

1. Es gibt einen n-langen Datenblock in einem Stream
2. Der Block wird im Stream viele Male wiederholt
3. Die Daten sind stark beschädigt, einige Bytes könnten einfach falsch sein, wo andere als fehlend erkannt werden können (Löschungen)
4. Es gibt eine Funktion F(data) Dies kann sagen, wenn ein Block gültige Daten darstellt (die Wahrscheinlichkeit eines falsch positiven positiven ist praktisch Null)
5. F Kann auch einen Wahrscheinlichkeitswert liefern, der selbst wenn der Block keine gültigen Daten ist, ob der Block selbst gültig ist (aber nur zu viel Korruption ist, um wiederhergestellt zu werden)
6. Die Wahrscheinlichkeit von beschädigten Daten ist im Vergleich zu fehlenden Daten sehr niedrig

Angenommen, ich habe diesen Datenstrom und möchte die 10 -Länge -Sequenz wiederherstellen 1234567890. Die Daten sind nur ein grobes visuelles Beispiel (ich kann nicht garantieren, dass die Wiederherstellung aus diesem Bit tatsächlich möglich ist). EIN . repräsentiert ein fehlendes Byte und <break> Zeigt einen unbekannten Datenblock an (keine Daten und keine Länge bekannt). Beachten Sie auch die Qs als Beispiel für korrupte Daten.

23.5678901.3456789<break>2345678..1..4567QQ012345678..3456

Wie kann ich einen solchen Datenstrom und eine Wiederherstellung wahrscheinlich nutzen, wahrscheinlich Blöcke von N -Daten? Da die tatsächlichen Daten die Wiederherstellung der Vorwärtsfehler enthalten, muss die Blockwiederherstellung nicht perfekt sein. Alles, was es tun muss, ist wahrscheinliche rekonstruierte Datenblöcke und die F Funktion wird versuchen, Fehlerwiederherstellung zu machen. So erwarte ich F Fill muss mehrmals aufgerufen werden.

Ich würde gerne etwas Besseres finden, als nur anzurufen F An jedem Punkt im Stream könnte die Fehlerrate hoch genug sein, damit kein einzelner Laufblock von N wiederhergestellt werden kann - die Wiederholungen im Stream müssen irgendwie verwendet werden.

Answer 1

Ich denke, was Sie wollen, ist ohne weitere Annahmen unmöglich zu tun F.

Betrachten Sie den folgenden, ziemlich einfachen Datenstrom für eine Zieldatenlänge von 5:

123441233512245113451255513555 ...

Beachten Sie, dass kein einzelner Block enthält 12345 (unsere ursprünglichen Daten). Um eine ordnungsgemäße Kombination von Datenteilen zu finden, hätten Sie eine Überprüfung alle Kombinationen im Allgemeinen. Was ist die Wahrscheinlichkeit, dass eine andere Kombination als ein anderer als 12345 wird akzeptiert von F? Und dies ist auf einem Stream ohne verlorene oder korrupte Symbole und ignoriert das Problem von Überschneidungen zwischen Blöcken, die zufällig gültige Daten sein können!

Daher denke ich, dass ein Puffer von Größe $ n $ und läuft bleibt F In jedem Zeitschritt ist das Beste, was Sie tun können. Beachten Sie, dass Sie die Bewertung von überspringen können F Wenn im Puffer ein korruptes Symbol vorliegt (vorausgesetzt, Sie können diese identifizieren). Sie haben jedoch immer noch das Problem von Überlappungsfehlern und falschen gültigen Blöcken.

Sie haben mehr Potenzial, wenn F hat schöne Eigenschaften, zum Beispiel, wenn es in der Lage ist, gültig zu identifizieren Teile von Dateien. Dann können Sie nur maximal gültige Teile speichern und diese zusammenstellen. Außerdem kann das Formatieren des Datenstroms helfen. Ein einfaches Beispiel wäre Marker für den Beginn eines Datenblocks (die Probleme mit Überschneidungen beseitigen und die Anzahl der Anrufe an verringern F). Darüber hinaus können übliche Annahmen wie "Fehlerwahrscheinlichkeit klein" auf eine vollständige kopierte Kopie der Daten zu tun haben. Viele Protokolle brechen zusammen, wenn praktisch jedes andere Symbol korrupt ist.

All dies sind keine neuen Probleme. Ich schlage vor, weiter zu lesen

• Fehlererkennung und Korrekturcodes,
• Codes im Allgemeinen und
• Kommunikationsprotokolle.