Continue Correção de Erro

Question

Tenho um fluxo de dados com as seguintes propriedades:

• Binário
• Comprimento dinâmico
• Vem em blocos de 20 bits
• Quaisquer bits aleatórios podem virar, criando um erro (não há mais probabilidade de que bits adjacentes sejam virados juntos)
• Eu gostaria de usar cerca de 16 bits como dados e 4 para redundância por bloco, mas estou aberto para alterar esse número
• A probabilidade de um bit estar correto é de cerca de 97%
• Idealmente, o código seria capaz de corrigir 2 bits por bloco
• A quantidade de blocos será bastante pequena, geralmente 1-6.

Qual seria um bom código para usar neste cenário? Pensei em Reed-Solomon, mas de acordo com este artigo , seria uma escolha ruim:

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. 

Eu também examinei Bossen's b-adjacent algorithm, mas parece ter sido projetado levando em consideração que bit flips adjacentes têm maior probabilidade de acontecer.

Answer 1

Modelando seus erros como binomiais, vamos ver o que acontece se você corrigir um único erro:

A probabilidade de 0 ou 1 erro é $$q=(1-p)^{20}+20(1-p)^{19}p$$ que é aproximadamente $0.88$ para $p=0.03,$ portanto, sua probabilidade de erro codificada ao corrigir um erro é $0.12$.

A probabilidade de erro sem codificação é $1-(1-p)^{20}$ que está por aí $0.456$ então você obtém uma melhoria considerável se usar codificação.

De acordo com este papel aqui dado$r\geq 3,$ e $2^{r-1}+1\leq n\leq 2^r-1,$ há um $[n,n-r,3]$código de Hamming encurtado com algumas boas propriedades de detecção de erro duplo. Quando$n=20,$ isto dá $r=5,$ então você tem um $[n,n-r,3]=[20,15,3]$ código de Hamming encurtado de correção de erro único e você pode transmitir $k=15$ bits por bloco de comprimento $n=20.$