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

[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]

http://xmages.net/storage/10/1/0/a/e/thumb/thumb_f600415b.png (http://xmages.net/show.php/2251987_van-der-varden-algebra1-png.html)http://xmages.net/storage/10/1/0/a/c/thumb/thumb_111c923b.png (http://xmages.net/show.php/2251991_van-der-varden-algebra2-png.html)

[gav]

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

[mbk]

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

[phys2010]

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


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

по Ван дер Вардену непонятно, зависит ли значение производной от 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]

см. картинку ниже.
Спасибо за пояснение.

[Paul Kellerman]

Теперь используем условие, что мы работаем над полем характеристики 2.
В этом случае все четные коэффициенты сравнимы с 0 (по модулю 2), а
нечетные - с единицей. В результате получаем требуемое выражение для производной
Эээ... Как я уже сказал, я не настолько крут, и мне вот эта вещь не совсем
очевидна. Каким образом из того, что характеристика 2, следует обнуление
четных коэффициентов. Поясните плиз! А вообще большое спасибо за ответ.

[mbk]

Каким образом из того, что характеристика 2, следует обнуление
четных коэффициентов
Предлагаю следующую версию:
1) в результате дифф-я у коэффициентов появляются дополнительные сомножители, "вылезшие" из степени;
2) допустим, сомножитель четный. Например, он равен 2.
Тогда 2*байт=байт+байт=00000000.

[Paul Kellerman]

Тогда 2*байт=байт+байт
Неверно! В поле Галуа n*X не равно XOR (X, i=1..n).

В поле Галуа (2^8) умножение определяется по другому:

a * b = 2^((log2(a) + log2(b)) mod (2^8 - 1))

Где "+" для сложения степеней - это обычное арифметическое, а не ХОR!

Тогда, 2 * байт = 2^((log2(2) + log2(байт)) mod (2^8-1)) = 2^((1 + log2(байт)) mod (2^8-1)) <> 0.

Я на эти грабли уже наступал, и именно поэтому пошел другим более длинным и строгим путем...

Подвох здесь в том, что степень трансформируется не в сомножитель, а в ХОR-сумму, с количеством
одинаковых ХОR-слагаемых, равных степени, и я это по-своему доказал! Ссылку на это пришлю позже.

[mbk]

Все равно непонятно.
Ведь кратность искажения - это не элемент поля.

[Paul Kellerman]

Ведь кратность искажения - это не элемент поля
Действительно, она не элемент поля, зато она логарифм элемента поля :)

[phys2010]

Предлагаю следующую версию:
1) в результате дифф-я у коэффициентов появляются дополнительные сомножители, "вылезшие" из степени;

Именно так! Слагаемое
kL[k]*X^k=L[k]*X^k+....+L[k]*X^k.
С другой стороны, в поле Галуа GF(2^n) справедливо тождество
A+A=0.
Поэтому
2L[k]*X^k=L[k]*X^k+L[k]*X^k=0,
3L[k]*X^k=2L[k]*X^k+L[k]*X^k=L[k]*X^k,
и т.д.

Неверно! В поле Галуа n*X не равно XOR (X, i=1..n).

Вся фишка в том, что в выражении kL*X^k символом k (если мы считаем, что он обозначает элемент поля Галуа) обозначены два (вообще говоря различных) элемента. В сомножителе kL этот символ принимает значения 0 и 1, а в сомножителе X^k - значение любого элемента поля. Чтобы не заморачиваться с этим, проще понимать под выражением n*X сумму n одинаковых элементов X+...+X, где n - натуральное число, а X - элемент поля Галуа. Эквивалентность двух подходов следует из тождества X+X=0.

Кстати, по этой теме есть неплохая книга:
Берлекэмп Э. Алгебраическая теория кодирования. М.: Мир, 1971.
В ней терия конечных полей изложена ясно и достаточно полно.

[Paul Kellerman]

Берлекэмп Э. Алгебраическая теория кодирования. М.: Мир, 1971
Читал взахлеб :) Вообще, Берлекэмп - однозначно гений, придумать алгоритм со
сложностью всего ~ t^2 для решения системы уравнений и при этом, чтобы сте-
пень полинома-решения была минимальной... это просто невообразимая крутизна.

[phys2010]

К сожалению мне трудно это оценить...
Слишком далеко все это находится от области моих интересов :)

[Paul Kellerman]

Млин... Вот уж не думал, что школьная и институтская алгебра (матан)
могут подложить такие "грабли". Просто еще со школьной скамьи усва-
иваешь, что производная от X^k это k*X^k-1, причем k в множителе и
k в степени элементы одного и того же поля вещественных чисел. Когда
начинаешь ковыряться с полями Галуа, то с удивлением обнаруживаешь,
что школьные и институтские знания дают "осечку". Вы были совершенно
правы, при взятии производной от функции X^k в случае поля Галуа, "k",
"слезающая" со степени в множитель также при этом трансформируется
из элемента поля (или кольца???) логарифмов в элемент поля Галуа (GF).
И для корректной трансформации от "k" нужно взять остаток по модулю 2.
То есть, как я уже писал раньше: d(X^k)/dX = (k mod 2)*X^(k-1), k >= 1.

Короче говоря, "множители", "слагаемые" и значения самой переменной X
- элементы поля Галуа, а степени - это уже элементы поля (или кольца?)
логарифмов, где правила сложения, вычитания и умножения такие же как
в школьной алгебре, только все операции делаются по модулю (2^8 - 1),
ну, а что касается деления логарифмов, она, вроде как, не определена?

[gav]

PavelAR
Вот уж не думал, что школьная и институтская алгебра (матан)
могут подложить такие "грабли".
Школьная и институтская математика здесь совершенно непричем! Эти "грабли" - исключительно продукт нашего мозга, склонного отождествлять неотождествимое и строить аналогию в неаналогичном. Ни в институте, ни, тем более, в школе, Вам никто не обещал, что производная в поле Галуа будет дакой же, как и в действительных числах. Наоборот, надо ставить вопрос об удивительном, что они так похожи!

[phys2010]

что касается деления логарифмов, она, вроде как, не определена?

Рассмотрим вновь выражение kL*X^k. Предположим, что мы пока не определили конкретный вид поля над которым работаем. В этом случае сомножитель kL=L+...+L, где символом k обозначено число слагаемых (некоторое натуральное число). С другой стороны, сомножитель X^k=X*...*X, где симколом k обозначено уже число сомножителей. Очевидно, что обоих случаях k - одно и тоже натуральное число. Теперь фиксируем поле. Если оно характеристики 0 (например, поле вещественных чисел), то оно содержит множество натуральных чисел и поэтому смысл символа k не меняется - его можно считать элементом поля. Если же мы имеем поле Галуа GF(2^n), то ситуация меняется. В этом случае для сомножителя kL мы должны использовать таблицу сложения (из которой следует тождество X+X=0), а для сомножителя X^k - таблицу умножения (из которой следует тождество X^q=X, где q=2^n). Причем L и X являются элементами поля, а вот символ k им не является. Этим символом обозначено лишь количество (натуральное число) слагаемых и сомножителей соответственно. И это количество в обоих сомножителях совпадает (кстати, при таком подходе школьная и институтская алгебра работают :)). Поэтому определять деление на этом множестве (множестве натуральных чисел) некорректно.
PS
Можно, конечно, символы k в сомножителях kL и X^k вложить в поле Галуа (и тогда деление выполняться будет, поскольку k^{q-1}=1). Но тогда элементы, соответствующие символу k, будут различаться и это приведет к ненужному усложнению текста.

[Paul Kellerman]

Продолжаем тему... Следующий вопрос чуток другого плана...

Итак пусть задано простое конечное поле Галуа GF(p), где p - разумеется простое,
в котором сложение и умножение выполняется с помощью операций, соответсвую-
щих операциям сложения и умножения по модулю (p) с точки зрения привычной ал-
гебры поля действительных чисел. В поле GF(p) существует (и необязательно один)
примитивный элемент с помощью которого можно получить все ненулевые элементы
поля GF(p), путем возведения его в соответствующие степени 0, 1,..., p - 2. Сами
степени мы можем называть "логарифмами по основанию примитивного элемента" .

Так вот, пусть есть простое поле GF(p), пусть имеется множество {0, 1, ... , p - 2}
логарифмов по основанию примитивного элемента поля для всех ненулевых элемен-
тов поля GF(p). Зададим для множества логарифмов операции сложения и умноже-
ния, соответствующие операциям сложения и умножения по модулю (p - 1) с точки
зрения алгебры поля действительных чисел. А тогда, можно ли считать множество
логарифмов с двумя заданными операциями "коммутативным кольцом с единицей"?

[phys2010]

Да. В кольце целых чисел классы вычетов по произвольному положительному числу x состоят из тех чисел, которые при делении на x дают остаток y. Чтобы сложить или перемножить два класса вычетов нужно сложить или соответственно перемножить их представители и привести результат к его наименьшему неотрицательному остатку от деления на x. В вашем случае x=p-1 и поэтому x - четное число отличное от 2. Следовательно указанное множество логарифмов является коммутативным кольцом с единицей, в котором есть делители нуля (если p-1 не есть степень двойки).

[Paul Kellerman]

множество логарифмов является коммутативным кольцом с единиц
Спасибо большое! То есть для любого простого поля Галуа GF(p), p >= 3, можно пос-
троить соответствующее ему кольцо логарифмов LR(p - 1), LR - сокр. Logarithm Ring.
Причем, в случае: p = 3, мы получаем LR(2), которое также является и полем GF(2).

Теперь я могу спать спокойно :)

Вопрос второй, чтобы уж совсем успокоиться :)

А могу ли я утверждать, что циклическая мультипликативная группа, состоящая
из множества всех ненулевых элементов поля GF(p) и определенной в ней опера-
ции умножения (по модулю p), изоморфна циклической аддитивной группе, сос-
тоящей из множества соответствующих логарифмов и определенной в ней опера-
ции сложения (по модулю p - 1). То есть, для любых ненулевых a, b и с из GF(p),
таких что: с = a * b (по правилам умножения поля GF(p)), имеются соответству-
ющие u, v и w из LR(p - 1): w = u + v (по правилам сложения в кольце LR(p - 1)),
ну и соответственно, соответствие в обратном направлении также справедливо?

[phys2010]

Вопрос второй, чтобы уж совсем успокоиться

Любые две циклические группы одного порядка изоморфны (вне зависимости от явного вида операций, заданных на них). Изоморфизм определяется отображением (любого) порождающего элемента одной группы в (любой) порождающий элемент другой группы.

[Paul Kellerman]

Спасибо большое, теперь все ясно.

[Paul Kellerman]

Как и обещал, выкладываю свой взгляд на вывод формулы для формальной
производной полинома, заданного над конечным полем GF(2^m), ну и также
адаптация схемы Горнера для вычисления значения формальной производной
полинома при заданном аргументе x, ну и аппаратная реализация вычисления.