Jak określić liczbę błędów w algorytmie Welch-Berlekamp?

W algorytmie Welcha-Berlekampa do dekodowania kodów Reeda-Solomona podaje się listę punktów reprezentujących komunikat z błędami na w nieznanych lokalizacjach (i otrzymuje się do algorytmu). Wyjście jest wielomianem przechodzącym przez wszystkie podane punkty z wyjątkiem tych, w których wystąpiły błędy.$(a_i, b_i)$$e$$b_i$$e$

Metoda polega na rozwiązaniu układu równań liniowych formy

dla wszystkich gdzie ma stopień a ma stopień co najwyżej . Zmienne są współczynnikami i .$i$$E$$e$$Q$$e+k$$E$$Q$

Aby upewnić się, że ma stopień zwykle dodaje się ograniczenie, że współczynnik wynosi 1 do układu liniowego powyżej. W praktyce jednak niekoniecznie wiadomo . Jednym nieefektywnym (ale wciąż wielomianowym sposobem) radzeniem sobie z tym jest wypróbowanie dla wszystkich wartości zaczynających się od , aż do znalezienia rozwiązania.$E$$e$$x^e$$e$$e$$(n+k-1)/2 - 1$

Moje pytanie brzmi: czy istnieje bardziej skuteczny sposób na określenie ? $e$Alternatywnie, czy istnieje modyfikacja układu liniowego, która pozwala na użycie górnej granicy na zamiast dokładnej wartości?$e$

W szczególności chcę użyć tego konkretnego dekodera dla kodów Reeda-Solomona, a nie zupełnie innego algorytmu opartego na innych technikach.

W odpowiedzi na odpowiedź DW, oto mój działający przykład. Wszystko odbywa się modulo 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]]

Zatem błąd tkwi w trzecim punkcie.

Gdy omawiane równanie wielomianowe wynosi$e=2$

Podłączenie daje układ w postaci macierzy:$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]

Ostatni wiersz jest ograniczeniem, że . Stosując eliminację Gaussa otrzymujemy$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]

I wybierając 1 dla obu wolnych zmiennych otrzymujemy wektor rozwiązania

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

Co przekłada się na

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

I nie dzieli . Zauważ, że współczynniki jak$E$$Q$$Q$$(t + 6) (t^3 + 2t^2 + 2t + 3) \mod 7$

Dla mam dobre rozwiązanie:$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

Zauważ, że chociaż powyższy kontrprzykład został wygenerowany przez kod, który napisałem od zera (była to zasadniczo pierwsza rzecz, której próbowałem), można sprawdzić, czy rozwiązania są poprawne ręcznie, więc nawet jeśli mój kod jest wadliwy, nadal jest prawidłowym kontrprzykładem do roszczenia że użycie działa.$e=2$

Ta sama procedura faktycznie koryguje dowolną liczbę błędów do $e$.

Wymagany jest wielomian błędu $E(x)$ w każdym punkcie musi wynosić zero $a_i$gdzie wystąpił błąd. Nic nie mówi, że musi to być zero tylko w tych punktach; możesz mieć$E(x)$ w innych punktach jest to zero i to jest w porządku, pod warunkiem, że ma stopień $e$.

Więc jeśli $e$ jest górną granicą liczby błędów, będzie wielomian $E(x)$ ze wszystkimi pożądanymi właściwościami (tj. ma dokładnie stopień $e$i wynosi zero w każdym punkcie, w którym wystąpił błąd). Na przykład, jeśli jest ich mniej niż$e$ błędy, wtedy istnieje wielomian $E(x)$ to zero przy każdym błędzie i zero w kilku kolejnych punktach, aby dokładnie zwiększyć liczbę zer $e$.

Wreszcie twierdzenie o poprawności mówi, że jeśli taki wielomian $E(x)$istnieje, wówczas algorytm Berlekamp-Welch będzie w stanie go znaleźć. Tak więc, nawet jeśli jest ich mniej niż $e$ błędy, procedura będzie nadal działać poprawnie w celu identyfikacji $E(x)$. Kiedy już to zrobisz$E(x)$, możesz zidentyfikować $n-e$ pozycje, które są wolne od błędów, a następnie można dekodować w prosty sposób.

Aby udokumentować wynik rozmowy na temat „kontrprzykładu” w pytaniu:

To właściwie nie jest prawidłowy kontrprzykład. Wada polegała na obliczeniu, ile błędów należy oczekiwać od Berlekamp-Welch, aby móc je poprawić. Odległość wynosi$n-k+1$, więc powinieneś oczekiwać, że będzie w stanie poprawić do $(n-k)/2$błędy (jak wskazuje Ran G.). W twoim kontrprzykładzie$n=5$ i $k=3$, więc $(n-k)/2=1$, więc powinieneś oczekiwać, że ta procedura będzie w stanie poprawić jeden błąd, tj. $e=1$. Więc kiedy uruchomiłeś procedurę na przykładzie z$e=2$, nie ma powodu, aby oczekiwać, że procedura będzie działać poprawnie.

Zatem kontrprzykład nie jest tak naprawdę kontrprzykładem i nie jest sprzeczny z moją odpowiedzią powyżej.