Como você determina o número de erros no algoritmo Welch-Berlekamp?

No algoritmo Welch-Berlekamp para decodificar códigos de Reed-Solomon, é dada uma lista de pontos representando uma mensagem com erros na em locais desconhecidos (e é dado ao algoritmo). A saída é um polinômio passando por todos os pontos fornecidos, exceto aqueles em que ocorreram erros. $(a_i, b_i)$ $e$ $b_i$ $e$

O método envolve resolver um sistema de equações lineares da forma

b_{i} E (a_{i}) = Q (a_{i})

$b_i E(a_i) = Q(a_i)$

para todo onde tem grau e tem grau no máximo . As variáveis são os coeficientes de e . $i$ $E$ $e$ $Q$ $e+k$ $E$ $Q$

Para garantir que tenha o grau geralmente se adiciona a restrição de que o coeficiente de seja 1 no sistema linear acima. No entanto, na prática, não se sabe necessariamente . Uma maneira ineficiente (mas ainda polinomial de tempo) de lidar com isso é tentar para todos os valores que começam com diminuindo até encontrar uma solução. $E$ $e$ $x^e$ $e$ $e$ $(n+k-1)/2 - 1$

Minha pergunta é: existe uma maneira mais eficiente de determinar ? $e$ Como alternativa, existe uma modificação no sistema linear que permite usar um limite superior em em vez do valor exato? $e$

Em particular, quero usar esse decodificador específico para códigos de Reed-Solomon, e não um algoritmo completamente diferente com base em outras técnicas.

Em resposta à resposta da DW, aqui está o meu exemplo de trabalho. Tudo é feito no módulo 7.

plain message is: [2, 3, 2]
polynomial is: 2 + 3 t^1 + 2 t^2
encoded message is: [[0, 2], [1, 0], [2, 2], [3, 1], [4, 4]]
corrupted message is: [[0, 2], [1, 0], [2, 3], [3, 1], [4, 4]]

Portanto, o erro está no terceiro ponto.

Quando a equação polinomial em questão é $e=2$

b_{i} (e_{0} + e_{1} x + e_{2} x^{2}) - q_{0} - q_{1} x - q_{2} x^{2} - q_{3} x^{3} - q_{4} x^{4} = 0

$b_i(e_0 + e_1x + e_2x^2) - q_0 - q_1x - q_2 x^2 - q_3x^3 - q_4x^4 = 0$

E a inserção de fornece o sistema em forma de matriz: $x = 0,1,2,3,4$

[2, 0, 0, 6, 0, 0, 0, 0, 0]
[0, 0, 0, 6, 6, 6, 6, 6, 0]
[3, 6, 5, 6, 5, 3, 6, 5, 0]
[1, 3, 2, 6, 4, 5, 1, 3, 0]
[4, 2, 1, 6, 3, 5, 6, 3, 0]
[0, 0, 1, 0, 0, 0, 0, 0, 1]

A última linha é a restrição de que . Aplicando a eliminação gaussiana, obtemos $e_2 = 1$

[1, 0, 0, 0, 0, 0, 1, 4, 0]
[0, 1, 0, 0, 0, 0, 3, 3, 1]
[0, 0, 1, 0, 0, 0, 0, 0, 1]
[0, 0, 0, 1, 0, 0, 2, 1, 0]
[0, 0, 0, 0, 1, 0, 2, 2, 5]
[0, 0, 0, 0, 0, 1, 4, 5, 2]

E escolhendo 1 para ambas as variáveis livres, obtemos um vetor de solução de

[2, 2, 1, 4, 1, 0, 1, 1]

O que se traduz em

E is 2 + 2 t^1 + 1 t^2
Q is 4 + 1 t^1 + 0 t^2 + 1 t^3 + 1 t^4

$E$ $Q$ $Q$ $(t + 6) (t^3 + 2t^2 + 2t + 3) \mod 7$

Para , recebo uma boa solução: $e=1$

system is:    
[2, 0, 6, 0, 0, 0, 0]
[0, 0, 6, 6, 6, 6, 0]
[3, 6, 6, 5, 3, 6, 0]
[1, 3, 6, 4, 5, 1, 0]
[4, 2, 6, 3, 5, 6, 0] 
[0, 1, 0, 0, 0, 0, 1]

reduced system is:

[1, 0, 0, 0, 0, 0, 5]
[0, 1, 0, 0, 0, 0, 1]
[0, 0, 1, 0, 0, 0, 3]
[0, 0, 0, 1, 0, 0, 3]
[0, 0, 0, 0, 1, 0, 6]
[0, 0, 0, 0, 0, 1, 2]

solution is [5, 1, 3, 3, 6, 2]
Q is 3 + 3 t^1 + 6 t^2 + 2 t^3
E is 5 + 1 t^1
P(x) = 2 + 3 t^1 + 2 t^2 # this is correct!
r(x) = 0

Observe que, embora o contra-exemplo acima tenha sido gerado pelo código que escrevi do zero (foi basicamente a primeira coisa que tentei), pode-se verificar se as soluções são válidas manualmente, portanto, mesmo que meu código esteja com erros, ainda é um contra-exemplo válido para a reivindicação que usar funciona. $e=2$

algorithms error-correcting-codes JeremyKun
fonte

@DW o vetor da solução é válido. Na verdade, é 1 * 2 + 1 * 1 + 4 * 1 (a dimensionalidade do vetor da solução é uma fora porque a última coluna da matriz é deixada de fora). fora o é um erro de digitação no artigo aqui, mas está correto na minha implementação. Você pode ver seu efeito, por exemplo, na segunda linha do sistema que usa o ponto [1, 0], e as três primeiras entradas são zero porque são multiplicadas por 0. Se meu exemplo não estiver claro, posso postar meu código no github. Considero meu código limpo, mas seria mais confuso devido à sua generalidade.

b_{i}

$b_i$

precisa saber é o seguinte

O mesmo procedimento realmente funciona para corrigir qualquer número de erros até . $e$

O requisito é que o polinômio de erro seja zero em todos os pontos que houve um erro. Nada diz que deve ser zero apenas nesses pontos; você pode ter um que é zero em outros pontos também, e tudo bem, desde que seu grau seja . $E(x)$ $a_i$ $E(x)$ $e$

Portanto, se for um limite superior do número de erros, haverá um polinômio com todas as propriedades desejadas (ou seja, possui um grau exatamente é zero em todos os pontos em que há um erro). Por exemplo, se houver menos de erros, existe um polinômio que é zero a cada erro e zero em mais alguns pontos para obter o número de zeros exatamente . $e$ $E(x)$ $e$ $e$ $E(x)$ $e$

Finalmente, o teorema da correção diz que, se esse polinômio existe, o algoritmo de Berlekamp-Welch será capaz de encontrá-lo. Portanto, mesmo se houver menos de erros, o procedimento ainda funcionará corretamente para identificar . Depois de ter , você pode identificar posições que são livres de erros, e então você pode decodificar de forma simples. $E(x)$ $e$ $E(x)$ $E(x)$ $n-e$

Para documentar o resultado da conversa sobre o "contra-exemplo" na pergunta:

Na verdade, esse não é um contra-exemplo válido. A falha estava no cálculo de quantos erros você deveria esperar que a Berlekamp-Welch pudesse corrigir. A distância é , portanto, você deve esperar que seja capaz de corrigir até erros (como Ran G. indica). No seu contra-exemplo e , então , portanto, você deve esperar apenas que este procedimento seja capaz de corrigir um erro, ou seja, . Portanto, quando você executou o procedimento em um exemplo com , não há motivo para esperar que o procedimento funcione corretamente. $n-k+1$ $(n-k)/2$ $n=5$ $k=3$ $(n-k)/2=1$ $e=1$ $e=2$

Portanto, o contra-exemplo não é na verdade um contra-exemplo e não contradiz minha resposta acima.

DW
fonte

@JeremyKun a distância é para que o código possa corrigir até erros, certo?

n - k + 1

$n-k+1$

(n - k) / 2

$(n-k)/2$

Ran G.

Embora uma prova esteja faltando, a explicação nesta resposta faz sentido para mim. Definir zeros em "informa" o algoritmo em que pontos ele deve ignorar ao interpolar o polinômio. Portanto, desde que o conjunto de zeros em contenha o conjunto de pontos em que os erros ocorreram, a decodificação deve funcionar. Nesse caso, deve haver mais variáveis livres (para definir os outros locais de zeros de maneira arbitrária).

E (x)

$E(x)$

E (x)

$E(x)$

Ran G.

Ooooh, esse é o problema ... que eu errei o limite de Singleton? Portanto, para verificar, se eu definir , introduzir um único erro e definir , devemos esperar que tudo dê certo. Vou tentar isso agora.

n = 7

$n = 7$

e = 2

$e=2$

precisa saber é o seguinte

Ok, isso funciona nos exemplos em que estou experimentando. Excelente!

precisa saber é o seguinte

Como você determina o número de erros no algoritmo Welch-Berlekamp?

Respostas: