Прямое исправление ошибок
У меня есть поток данных со следующими свойствами:
- Двоичный
- Динамическая длина
- Поставляется блоками по 20 бит
- Любые случайные биты могут перевернуться, что приведет к ошибке (вероятность того, что соседние биты перевернутся вместе, не выше)
- Я хотел бы использовать около 16 бит для данных и 4 для избыточности на блок, но я готов изменить это число.
- Вероятность того, что бит верный, составляет около 97%.
- В идеале код мог бы исправлять 2 бита на блок.
- Количество блоков будет небольшим, обычно 1-6.
Какой код можно использовать в этом сценарии? Я подумал о Риде-Соломоне, но, согласно этой статье, это был бы плохой выбор:
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.
Я также изучал Bossen's b-adjacent algorithm, но, похоже, он разработан с учетом того, что смежные битовые перевороты имеют более высокую вероятность возникновения.
Ответы
Смоделируя ваши ошибки как биномиальные, давайте посмотрим, что произойдет, если вы исправите одну ошибку:
Вероятность ошибки 0 или 1 равна $$q=(1-p)^{20}+20(1-p)^{19}p$$ что примерно $0.88$ для $p=0.03,$ поэтому ваша закодированная вероятность ошибки при исправлении одной ошибки равна $0.12$.
Вероятность ошибки без кодирования равна $1-(1-p)^{20}$ который вокруг $0.456$ так что вы получите значительное улучшение, если будете использовать кодирование.
Согласно этой статье, приведенной здесь$r\geq 3,$ и $2^{r-1}+1\leq n\leq 2^r-1,$ существует $[n,n-r,3]$сокращенный код Хэмминга с некоторыми хорошими свойствами обнаружения двойных ошибок. Когда$n=20,$ это дает $r=5,$ так что у вас есть $[n,n-r,3]=[20,15,3]$ исправление одиночной ошибки сокращенным кодом Хэмминга, и вы можете передавать $k=15$ бит на блок длины $n=20.$