Как вы определяете количество ошибок в алгоритме Уэлча-Берлекампа?

В алгоритме Уэлча-Берлекампа для декодирования кодов Рида-Соломона каждому дается список точек представляющих сообщение с ошибками на в неизвестных местах (и задается алгоритму). Выходными данными является полином, проходящий через все заданные точки, кроме тех, в которых произошли ошибки. $(a_i, b_i)$ $e$ $b_i$ $e$

Метод предполагает решение системы линейных уравнений вида

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

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

для всех где имеет степень а имеет степень не более . Переменные коэффициенты и . $i$ $E$ $e$ $Q$ $e+k$ $E$ $Q$

Чтобы гарантировать, что имеет степень обычно добавляют ограничение, что коэффициент равен 1, к линейной системе выше. Однако на практике не обязательно знать . Один из неэффективных (но все еще полиномиальных) способов решения этой проблемы состоит в том, чтобы попробовать для всех значений, начиная с падая до тех пор, пока не будет найдено решение. $E$ $e$ $x^e$ $e$ $e$ $(n+k-1)/2 - 1$

Мой вопрос: есть ли более эффективный способ определить ? $e$ В качестве альтернативы, есть ли модификация линейной системы, которая позволяет использовать верхнюю границу для вместо точного значения? $e$

В частности, я хочу использовать этот конкретный декодер для кодов Рида-Соломона, а не совсем другой алгоритм, основанный на других методах.

В ответ на ответ DW, вот мой рабочий пример. Все сделано по модулю 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]]

Так что ошибка в третьем пункте.

Когда рассматриваемое полиномиальное уравнение $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} {Икс}^{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$

А включение дает систему в матричной форме: $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]

Последняя строка - это ограничение, что . Применяя гауссовское исключение, получаем $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]

И, выбрав 1 для обеих свободных переменных, мы получим вектор решения

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

Что переводится как

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$

Для я получаю хорошее решение: $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

Обратите внимание, что хотя приведенный выше контрпример был сгенерирован с помощью кода, который я написал с нуля (это было в основном первое, что я попробовал), можно проверить правильность решений вручную, поэтому даже если мой код содержит ошибки, он все еще является действительным контрпримером к заявке. что использование работает. $e=2$

algorithms error-correcting-codes JeremyKun
источник

@DW вектор решения действителен. На самом деле это 1 * 2 + 1 * 1 + 4 * 1 (размерность вектора решения равна единице, поскольку последний столбец матрицы не указан). Мой отказ от является опечаткой здесь, но это правильно в моей реализации. Вы можете увидеть его эффект, например, во второй строке системы, которая использует точку [1, 0], и первые три входа - все ноль, потому что они умножены на 0. Если мой пример неясен, я могу опубликовать мой код на github. Я считаю мой код чистым, но из-за его общности он будет более запутанным.

b_{i}

$b_i$

JeremyKun

Ответы:

Та же самая процедура фактически работает, чтобы исправить любое количество ошибок до . $e$

Требование состоит в том, что многочлен ошибки должен быть равен нулю в каждой точке где произошла ошибка. Ничто не говорит, что оно должно быть нулевым только в тех точках; у вас может быть который равен нулю и в других точках, и это нормально, если его степень равна . $E(x)$ $a_i$ $E(x)$ $e$

Таким образом, если - верхняя граница числа ошибок, будет существовать полином со всеми требуемыми свойствами (т. Имеет степень ровно и равен нулю в каждой точке, где есть ошибка). Например, если ошибок меньше, чем , то существует многочлен который равен нулю при каждой ошибке и нулю в нескольких точках, чтобы число нулей достигло ровно . $e$ $E(x)$ $e$ $e$ $E(x)$ $e$

Наконец, теорема корректности гласит, что если такой многочлен существует, то алгоритм Берлекампа-Уэлча сможет его найти. Таким образом, даже если ошибок меньше, чем , процедура все равно будет корректно работать для идентификации . Когда у вас есть , вы можете определить позиции, которые не содержат ошибок, и затем вы можете декодировать простым способом. $E(x)$ $e$ $E(x)$ $E(x)$ $n-e$

Чтобы задокументировать результат разговора о «контрпримере» в вопросе:

Это на самом деле недопустимый контрпример. Недостаток заключался в подсчете количества ошибок, которые, как вы ожидаете, сможет исправить Berlekamp-Welch. Расстояние равно , поэтому вы должны ожидать, что оно сможет исправить до ошибок (как указывает Ран Г.). В вашем контрпримере и , поэтому , поэтому вы должны ожидать, что эта процедура сможет исправить только одну ошибку, т. Е. . Итак, когда вы запустили процедуру на примере с , нет никаких оснований ожидать, что процедура будет работать правильно. $n-k+1$ $(n-k)/2$ $n=5$ $k=3$ $(n-k)/2=1$ $e=1$ $e=2$

Таким образом, контрпример на самом деле не является контрпримером, и это не противоречит моему ответу выше.

DW
источник

@JeremyKun расстояние поэтому код может исправить до ошибок, верно?

n - k + 1

$n-k+1$

(n - k) / 2

$(n-k)/2$

Ран Г.

Хотя доказательства отсутствуют, объяснение в этом ответе имеет смысл для меня. Установка нулей в «говорит» алгоритму, какие точки он должен игнорировать при интерполяции полинома. Поэтому, пока набор нулей в содержит набор точек, в которых произошли ошибки, декодирование должно работать. В этом случае должно быть больше свободных переменных (чтобы произвольно установить другие места нулей).

E (x)

$E(x)$

E (x)

$E(x)$

Ран Г.

Оооо, это проблема ... что я испортил Синглтон? Таким образом, чтобы проверить, если бы я должен был установить , ввести одну ошибку и установить , то мы должны ожидать, что все сработает. Я попробую это сейчас.

n = 7

$n = 7$

e = 2

$e=2$

JeremyKun

Хорошо, это работает на примерах, которые я примеряю. Отлично!

JeremyKun