Naprzód korekcja błędów

Question

Mam strumień danych o następujących właściwościach:

• Dwójkowy
• Długość dynamiczna
• Dostępny w blokach po 20 bitów
• Dowolne losowe bity mogą się odwrócić, tworząc błąd (nie ma większego prawdopodobieństwa, że ​​sąsiednie bity zostaną zamienione razem)
• Chciałbym użyć około 16 bitów jako danych i 4 do nadmiarowości na blok, ale jestem otwarty na zmianę tej liczby
• Prawdopodobieństwo, że trochę się zgadza, wynosi około 97%
• Idealnie byłoby, gdyby kod był w stanie poprawić 2 bity na blok
• Liczba bloków będzie raczej niewielka, zwykle 1-6.

Jaki byłby dobry kod do wykorzystania w tym scenariuszu? Myślałem o Reed-Solomonie, ale według tego artykułu byłby to kiepski wybór:

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. 

Przyjrzałem się również temu Bossen's b-adjacent algorithm, ale wydaje się, że został zaprojektowany z uwzględnieniem tego, że sąsiednie przerzuty bitów mają większe prawdopodobieństwo wystąpienia.

Answer 1

Modelując swoje błędy jako dwumian, zobaczmy, co się stanie, jeśli poprawisz pojedynczy błąd:

Prawdopodobieństwo wystąpienia błędu 0 lub 1 wynosi $$q=(1-p)^{20}+20(1-p)^{19}p$$ czyli w przybliżeniu $0.88$ dla $p=0.03,$ więc Twoje zakodowane prawdopodobieństwo błędu podczas poprawiania jednego błędu wynosi $0.12$.

Prawdopodobieństwo błędu bez kodowania wynosi $1-(1-p)^{20}$ który jest w pobliżu $0.456$ więc możesz uzyskać znaczną poprawę, jeśli używasz kodowania.

Zgodnie z tym artykułem podanym tutaj$r\geq 3,$ i $2^{r-1}+1\leq n\leq 2^r-1,$ tam jest $[n,n-r,3]$skrócony kod Hamminga z kilkoma ładnymi właściwościami wykrywania podwójnych błędów. Kiedy$n=20,$ to daje $r=5,$ więc masz $[n,n-r,3]=[20,15,3]$ pojedynczy błąd korygujący skrócony kod Hamminga i możesz transmitować $k=15$ bity na blok długości $n=20.$