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

[mbk]

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

см. картинку ниже.

Спасибо за пояснение.

[Paul Kellerman]

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

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

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

[mbk]

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

Каким образом из того, что характеристика 2, следует обнуление
четных коэффициентов

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

[Paul Kellerman]

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

Тогда 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]

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

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

Действительно, она не элемент поля, зато она логарифм элемента поля

[phys2010]

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

Предлагаю следующую версию:
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,
и т.д.

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

Неверно! В поле Галуа 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]

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

Берлекэмп Э. Алгебраическая теория кодирования. М.: Мир, 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),
ну, а что касается деления логарифмов, она, вроде как, не определена?