Vorwärtsfehlerkorrektur

Question

Ich habe einen Datenstrom mit folgenden Eigenschaften:

• Binär
• Dynamische Länge
• Kommt in Blöcken von 20 Bits
• Beliebige Bits können umdrehen und einen Fehler verursachen (es besteht keine größere Wahrscheinlichkeit, dass benachbarte Bits zusammen umdrehen).
• Ich möchte ungefähr 16 Bit als Daten und 4 für Redundanz pro Block verwenden, aber ich bin offen, diese Nummer zu ändern
• Die Wahrscheinlichkeit, dass ein Bit korrekt ist, liegt bei 97%
• Idealerweise kann der Code 2 Bits pro Block korrigieren
• Die Anzahl der Blöcke ist eher gering, normalerweise 1-6.

Was wäre ein guter Code für dieses Szenario? Ich dachte an Reed-Solomon, aber laut diesem Artikel wäre es eine schlechte Wahl:

if a data stream is not characterized by error bursts or drop-outs but by random single bit errors, 
a Reed-Solomon code is usually a poor choice. More effective codes are available for this case. 

Ich habe auch nachgesehen Bossen's b-adjacent algorithm, aber es scheint so konzipiert zu sein, dass benachbarte Bit-Flips eine höhere Wahrscheinlichkeit haben, dass sie auftreten.

Answer 1

Wenn Sie Ihre Fehler als Binomial modellieren, sehen wir uns an, was passiert, wenn Sie einen einzelnen Fehler korrigieren:

Die Wahrscheinlichkeit von 0 oder 1 Fehlern ist $$q=(1-p)^{20}+20(1-p)^{19}p$$ das ist ungefähr $0.88$ zum $p=0.03,$ Ihre codierte Fehlerwahrscheinlichkeit bei der Korrektur eines Fehlers ist also $0.12$.

Die Fehlerwahrscheinlichkeit ohne Codierung beträgt $1-(1-p)^{20}$ das ist um $0.456$ Wenn Sie also Codierung verwenden, erhalten Sie eine ziemliche Verbesserung.

Nach diesem hier gegebenen Papier$r\geq 3,$ und $2^{r-1}+1\leq n\leq 2^r-1,$ es gibt eine $[n,n-r,3]$verkürzter Hamming-Code mit einigen schönen Eigenschaften zur Erkennung doppelter Fehler. Wann$n=20,$ das gibt $r=5,$ Also hast du eine $[n,n-r,3]=[20,15,3]$ Einzelfehlerkorrektur verkürzter Hamming-Code und Sie können senden $k=15$ Bits pro Längenblock $n=20.$