Correction d'erreur directe
J'ai un flux de données avec les propriétés suivantes:
- Binaire
- Longueur dynamique
- Livré en blocs de 20 bits
- Tout bit aléatoire peut basculer créant une erreur (il n'y a pas plus de probabilité que les bits adjacents se retournent ensemble)
- Je voudrais utiliser environ 16 bits comme données et 4 pour la redondance par bloc, mais je suis ouvert à modifier ce nombre
- La probabilité qu'un bit soit correct est d'environ 97%
- Idéalement, le code serait capable de corriger 2 bits par bloc
- Le nombre de blocs sera plutôt faible, généralement de 1 à 6.
Quel serait un bon code à utiliser dans ce scénario? J'ai pensé à Reed-Solomon, mais d'après cet article ce serait un mauvais choix:
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.
J'ai également examiné Bossen's b-adjacent algorithm, mais il semble être conçu en tenant compte du fait que les retournements de bits adjacents ont une probabilité plus élevée de se produire.
Réponses
Modélisant vos erreurs en binôme, voyons ce qui se passe si vous corrigez une seule erreur:
La probabilité de 0 ou 1 erreur est $$q=(1-p)^{20}+20(1-p)^{19}p$$ qui est approximativement $0.88$ pour $p=0.03,$ donc votre probabilité d'erreur codée lors de la correction d'une erreur est $0.12$.
La probabilité d'erreur sans codage est $1-(1-p)^{20}$ qui est autour $0.456$ vous obtenez donc une nette amélioration si vous utilisez le codage.
Selon cet article ici donné$r\geq 3,$ et $2^{r-1}+1\leq n\leq 2^r-1,$ il y a un $[n,n-r,3]$code Hamming raccourci avec de belles propriétés de détection d'erreur double. Quand$n=20,$ cela donne $r=5,$ donc vous avez un $[n,n-r,3]=[20,15,3]$ une seule erreur corrigeant le code Hamming raccourci et vous pouvez transmettre $k=15$ bits par bloc de longueur $n=20.$