Вопрос по алгебраической теории кодирования

[Paul Kellerman]

Одними из популярных помехоустойчивых кодов, широко применяемых при
передаче и хранении информации являются коды Рида-Соломона. Однако,
для кодирования и декодирования информации используется специальная
полиномиальная алгебра, заданная над конечным полем Галуа GF(2^8). В
частности при декодировании блока информации (принятого из канала пе-
редачи информации или считанного с носителя информации) для отыска-
ния локаторов искажений с помощью, так называемого, синдрома ошибок
ищется полином локаторов искажений (по алгоритму Берлекэмпа-Месси),
потом он приравнивается нулю и находятся корни уравнения, из которых
легко выделяются сами локаторы искажений, ну а потом вычисляется так
называемый полином величин ошибок (с помощью полинома локаторов и
синдрома ошибок), и так называемая, формальная производная полинома
локатора ошибок. Далее с помощью полинома величин, формальной про-
изводной полинома локаторов и найденных ранее корней, легко вычисля-
ются сами величины ошибки, и делается исправление искаженного блока.

Мой вопрос, собственно говоря, связан с формальной производной поли-
нома локаторов. В большинстве литературе (в том числе и в зарубежной)
просто приводится готовая формула для производной, как бы упавшая с
потолка, без каких-либо пояснений насчет, откуда взялась эта формула.

Обозначим, сам полином локаторов: L(X) = L[0] + L[1]*X + ... + L[v]*X^v
Где, операции + и * выполняются по правилам алгебры для поля Галуа,
X - формальный аргумент, вместо которого можно численно подставлять
любой элемент поля Галуа, а v - предполагаемая кратность искажений.
Тогда согласно литературе производная полинома локаторов выглядит:

d(L(X))/dX = L[1] + L[3]*X^2 + L[5]*X^4 + ... + L[w]*X^(w-1)

где, w = v, если v - нечетное, иначе w = v - 1, если v - четное.

Мне интересно, с какого, так сказать, "дуба" это формула упала. Есть ли
где-нибудь и какое-нибудь определение формальной производной, так как
это сделано для производной функции в случае традиционной алгебры или
это просто "нечто", не имеющей пока что никакой математической базы?

[phys2010]

PavelAR, посмотрите Б.Л. ван дер Варден, Алгебра, "Наука", 1976. В начале гл.5, на стр. 105, дано алгебраическое определение производной целой рациональной функции для произвольного кольца многочленов без использования понятия непрерывности. В частности - определение производной многочлена над конечным полем.

[Ink]

Б.Л. ван дер Варден, Алгебра, "Наука", 1976. В начале гл.5, на стр. 105

[gav]

Как же здорово натыкаться на схожесть аналогичных операций над принципиально различными объектами. Где эту схожесть никак не ожидаешь. Только за это стоит любить математику

[mbk]

Скорее всего, объект d(L(X))/dX не является обобщением производной в ее классическом понимании, т.к. невозможно сконструировать предельный переход. Я бы трактовал это как линейный оператор, образ которого позволяет дать количественную оценку чувствительности исходного полинома L(X) к "шевелению" элемента Х (конечно, это тоже очень сыро, ведь "шевеление" надо понимать в топологическом смысле).
Кстати, по Ван дер Вардену непонятно, зависит ли значение производной от h (выбранного произвольным образом).

[phys2010]

Сообщение от mbk

невозможно сконструировать предельный переход

При алгебраическом подходе к определению производной это требовоние не является обязательным.

Сообщение от mbk

по Ван дер Вардену непонятно, зависит ли значение производной от h (выбранного произвольным образом).

Никаких условий на выбор переменной h здесь нет. Надо лишь помнить, что при работе с конечными полями выборка, обычно, небольшая.

[Paul Kellerman]

Спасибо всем за отклики! Я, честно говоря, не очень надеялсь на то,
что кто-то откликнется, слишком уж специфичная тема обсуждения.

А теперь господа математики, не убивайте сразу, плиз, за то, что я
изложу ниже. Я не так крут, как хотелось бы, но все же стараюсь

Ковыряясь конкретно с кодами Рида-Соломона, я имел дело с полем
GF(2^8), в котором под операцией а + b, понималася побитовый ХОR
между а и b. В коэффициентах полинома фактически "сидит" одно из
256 значений соответствующих байтов, которое трактуется как один
из элементов поля GF(2^8). Число элементов в поле тоже ровно 256.
И соответственно, операция + в полиномиальном представлении это
тоже фактически побитовый XOR. Исходя из такой "частной" трактов-
ки, я поковырявшись немного, придумал вот такое вот определение:

dL(X)/dX = limit ((L(X XOR e) XOR L(X)) / e, e -> 0);

Где, е - некое формальное бесконечное малое (которое разумеется не
имеет никакого смысла в конечном поле), и используется только лишь
для аналитических преобразований. Подразумевается, что в конечном
итоге мы либо избавимся от "e", либо получим выражение где оно будет
присутствовать в некоторой целой положительной степени и мы ее ту-
по поменяем на нуль - и, то что останется - это и будет аналитическое
выражение формальной производной. И используя именно такое опреде-
ление я получил в точности искомую формулу формальной производной
для полинома L(X), заданного над конечным полем. Как вам такой заход?

В частности, d(const)/dX = 0; d(const*X)/dX = const; d(const*(X^2))/dX = 0;

Далее я в мучениях вывел, что d(const*(X^j))/dX = const*(X^(j-1))*(j mod 2).

После этого уже легко получил dL(X)/dX = XOR (L[j]*(X^(j-1))*(j mod 2), j = 1..k-1)

P.S. Спасибо большое Jacky за то, что теперь есть где обсуждать отрас-
левые научные вопросы, не связанные с работой над диссертацией или
преподавательской деятельностью. Вопросов таких очень даже немало.

[phys2010]

PavelAR, в принципе Ваш подход тоже имеет право на жизнь. Но доказать формулу для производной можно гораздо элегантнее и проще.

Исходный полином имеет вид:
L = L[0] + L[1]*X+ L[2]*X^2+ L[3]*X^3 + ... + L[v]*X^v.
Выражение производной (по Ван дер Вардену, точнее - общепринятое):
L' = L[1] + 2*L[2]*X+ 3*L[3]*X+... + vL[v]*X^v.
Теперь используем условие, что мы работаем над полем характеристики 2. В этом случае все четные коэффициенты сравнимы с 0 (по модулю 2), а нечетные - с единицей. В результате получаем требуемое выражение для производной:
L' = L[1] + L[3]*X+... + L[w]*X^w,
где w = v, если v - нечетное, иначе w = v - 1. Очевидно, что данная формула справедлива для произвольного поля Галуа GF(2^n).

[mbk]

Интересно, а как здесь устроено умножение?

[phys2010]

Сообщение от mbk

Интересно, а как здесь устроено умножение?

В общем случае это можно найти у Ван дер Вардена (неплохая книга для первого чтения). Для небольших полей Галуа см. картинку ниже.