Алгоритм декодирования Паттерсона для кодов Гоппы

От эта вики-страница: дан код Гоппы $\Гамма(г, L)$ и бинарное слово $v=(v_0,...,v_{n-1})$, его синдром определяется как $$s(x)=\sum_{i=0}^{n-1}\frac{v_i}{x-L_i} \mod g(x).$$ Алгоритм Паттерсона для исправления ошибок выглядит следующим образом:

• Рассчитать $$v(x)=\sqrt{s(x)^{-1}-x}\mod g(x)$$ (это предполагает, что $s(x)\ne 0$, что всегда имеет место, если только $v$ принадлежит $\Гамма(г,L)$ и коррекция не требуется).

• Используйте EEA для получения полиномов $а(х)$ и $б(х)$ такой, что $$ а(х)=b(х)v(х)\мод г(х)$$

• Вычислить многочлен $p(x)=a(x)+xb(x)^2$. Предполагая, что исходное слово декодируемо, оно должно быть таким же, как факторизованное локатор ошибок многочлен $$\sigma(x)=\prod_{i\in B}(x-L_i) $$ куда $B=\{i \text{ с.т. } e_i\ne 0\}$.

• Предполагая, что исходное слово декодируемо (т. $|B|<d$ куда $д$ — минимальное расстояние кода), мы просто вычисляем корни $\сигма(х)$: если $L_i$ является корнем, то ошибка, как произошла в в $я$-я позиция.

У меня только один вопрос: как показать, что многочлен $р(х)$ полученное на третьем шаге точно соответствует $\сигма(х)$ как определено выше?

Сначала обратите внимание, что $$\frac{\sigma'(x)}{\sigma(x)}=\sum_{i\in B}\frac 1{x-L_i}$$ и что если мы напишем $С$ для битовых позиций кодового слова код Гоппы определяется как $$\sum_{i\in C}\frac 1{x-L_i}\equiv 0\pmod{g(x)}$$ так что $$\frac{\sigma'(x)}{\sigma(x)}\equiv\sum_{i\in B\ominus C}\frac 1{x-L_i}\pmod{g(x)}$$ а правая сторона просто $с(х)$.

Мы разделились $\сигма(х)$ на мономы нечетной и четной степени, так что мы можем найти многочлены $\sigma_{нечетное}$ и$\sigma_{четный}$ такой, что $$\sigma(x)=x\sigma_{нечетное}(x^2)+\sigma_{четное}(x^2). \qquad (1)$$ Поскольку мы находимся в поле характеристики 2, многочлены только с квадратными членами являются квадратами других многочленов степени не выше $(\градус г-1)/2$ и мы стремимся восстановить $а(х)$ и $б(х)$ удовлетворяющие этой границе степени, такие что $ а (х) ^ 2 = \ сигма_ {четный} (х ^ 2) $ и $b(x)^2=\sigma_{нечетное}$.

Дифференцирование (1) дает $$\sigma'(x)=\sigma_{нечетный}(x^2)$$ и другие $$\frac{\sigma(x)}{\sigma'(x)}=x+\frac{\sigma_{четный}(x^2)}{\sigma_{нечетный}(x^2)}$$ что говорит нам, что $$\frac1{s(x)}-x\equiv \frac{\sigma_{четный}(x^2)}{\sigma_{нечетный}(x^2)}\pmod{g(x)}.$ $ Таким образом, многочлен $в(х)$ эквивалентна рациональной функции $а(х)/б(х)$ что мы ищем по модулю $г(х)$. Расширенный алгоритм Евклида вернет два многочлена, такие что $$\frac{c(x)}{d(x)}\equiv v(x)\pmod{g(x)}$$ с $\градус с$ и $\град д$ оба меньше, чем $(\градус г)/2$ и эти полиномы должны быть равны искомому $а(х)$ и $б(х)$ в противном случае $а(х)d(х)-б(х)с(х)$ является многочленом степени меньше, чем $д$ и делится на $г(х)$. Выздоровев $а(х)$ и $б(х)$ теперь мы можем построить $\сигма(х)=а(х)^2+хб(х)^2$ что является определением $р(х)$ что обычно дают.