Почему мое уравнение не оценивается правильно? - PullRequest
Новая
       16

Почему мое уравнение не оценивается правильно?

0 голосов
/ 08 ноября 2019

Итак, я делаю BCH-декодер для универа в Python. Он принимает 10-значное кодовое слово с ошибками или без них и должен обнаруживать и исправлять любые найденные ошибки. Для двойной коррекции ошибок существует математическая формула для определения положения и величины этих ошибок: формула для ошибок pos и mag 

i = (-Q + ((Q^2-4*P*R)^(1/2))/2*P)<br/>
j = (-Q - ((Q^2-4*P*R)^(1/2))/2*P)

b = (i*s1-s2)/(i-j)<br/>
a = s1-b

Я уже правильно рассчитал QPR и s1, s2. Итак, я отлаживаю с этим примером ( 2 ошибка BCH пример ). Он имеет число 8888880747, передаваемое на 8899880747, поэтому в позициях 3 и 4 имеются ошибки 2, причем их величина равна единице. Пока моя программа генерирует правильные syndromes(s1 to s4 - 2,7,3,3) и правильные значения PQR (10,7,10)но при выполнении вычислений для i и j я получаю значения, отличные от примера - 10.7 и 10.6 в отличие от 3 и 4. Вот мой код для i и j:

#work out error positions i and j
sqrt = ((Q**2 - 4*P*R) % 11)**(1/2)
i = (((-Q+sqrt)/(2*P))%11)
j = (((-Q-sqrt)/(2*P))%11)

Кто-нибудь может увидеть, что я делаю не так? Благодаря.

1 Ответ

0 голосов
/ 08 ноября 2019

Операции предназначены для выполнения в GF(11), другими словами, они предназначены для выполнения в моде 11. Квадратные корни и деление в моде 11 отличаются от действительных чисел.

Существуют усовершенствованные алгоритмы для выполнения как квадратных корней, так и модульных инверсий, но для чисел от 11 можно просто использовать грубую силу или предварительно вычислить таблицу. Пойдите с первыми принципами здесь. Для sqrt (x) попробуйте [0,1,2, ... 10] и посмотрите, какой из них в квадрате равен x. Это квадратный корень. Для деления (обратного) 1 / x попробуйте [0,1,2, ... 10] и посмотрите, какое из них при умножении на x равно 1 mod 11. Теперь мы добавим это значение, чтобы получить i = 3, j= 4.

Итак, пройдя через мод расчетов 11, имеем:

P, Q, R = (10,7,10) (Q ** 2 - 4 * P *R) = -351, -351% 11 = 1 Это удобно, поскольку квадратный корень из 1 - это всего лишь 1 mod 11. Глядя на следующие два уравнения, мы видим, что нам нужно будет вычислить 1 / (2 * P) mod 11другими словами, нам нужно найти обратное значение 2 * P mod 11, то есть (2P) -1 mod 11. 2 * P% 11 = 20% 11 = 9. Используя все возможности, мынайдите, что 9 -1 мод 11 равен 5.

...