İleri hata düzeltme

Question

Aşağıdaki özelliklere sahip bir veri akışım var:

• İkili
• Dinamik uzunluk
• 20 bitlik bloklar halinde gelir
• Herhangi bir rasgele bit ters çevrilerek bir hata oluşturabilir (bitişik bitlerin birlikte dönme olasılığı daha fazla değildir)
• Veri olarak yaklaşık 16 bit ve blok başına artıklık için 4 bit kullanmak istiyorum, ancak bu sayıyı değiştirmeye açığım
• Biraz doğru olma olasılığı yaklaşık% 97'dir
• İdeal olarak, kod blok başına 2 biti düzeltebilir
• Blokların miktarı oldukça küçük, genellikle 1-6 olacaktır.

Bu senaryoda kullanmak için iyi bir kod nedir? Reed-Solomon'u düşündüm, ancak bu makaleye göre bu kötü bir seçim olurdu:

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. 

Ayrıca araştırdım Bossen's b-adjacent algorithm, ancak bitişik bit çevirmelerinin gerçekleşme olasılığının daha yüksek olduğu göz önünde bulundurularak tasarlanmış görünüyor.

Answer 1

Hatalarınızı iki terimli olarak modelleyerek, tek bir hatayı düzeltirseniz ne olacağını görelim:

0 veya 1 hata olasılığı $$q=(1-p)^{20}+20(1-p)^{19}p$$ yaklaşık olarak $0.88$ için $p=0.03,$ yani bir hatayı düzeltirken kodlanmış hata olasılığınız $0.12$.

Kodlama olmadan hata olasılığı $1-(1-p)^{20}$ hangisi etrafta $0.456$ bu yüzden kodlamayı kullanırsanız oldukça gelişme elde edersiniz.

Burada verilen bu makaleye göre$r\geq 3,$ ve $2^{r-1}+1\leq n\leq 2^r-1,$ bir $[n,n-r,3]$bazı hoş çift hata algılama özellikleriyle kısaltılmış Hamming kodu Ne zaman$n=20,$ bu verir $r=5,$ yani sende var $[n,n-r,3]=[20,15,3]$ kısaltılmış Hamming kodunu düzelten tek hata ve iletebilirsiniz $k=15$ uzunluk bloğu başına bit sayısı $n=20.$