Портал аспирантов

Портал аспирантов (http://www.aspirantura.spb.ru/forum/index.php)
-   Физико-математические науки (http://www.aspirantura.spb.ru/forum/forumdisplay.php?f=128)
-   -   Вопрос по алгебраической теории кодирования (http://www.aspirantura.spb.ru/forum/showthread.php?t=6380)

mbk 12.01.2011 14:51

Цитата:

Сообщение от phys2010 (Сообщение 112030)
см. картинку ниже.

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

Paul Kellerman 13.01.2011 09:35

Цитата:

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

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

mbk 13.01.2011 10:02

Цитата:

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

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

Paul Kellerman 13.01.2011 10:10

Цитата:

Сообщение от mbk (Сообщение 112249)
Тогда 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 13.01.2011 10:18

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

Paul Kellerman 13.01.2011 10:32

Цитата:

Сообщение от mbk (Сообщение 112252)
Ведь кратность искажения - это не элемент поля

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

phys2010 13.01.2011 15:10

Цитата:

Сообщение от mbk (Сообщение 112249)
Предлагаю следующую версию:
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 (Сообщение 112250)
Неверно! В поле Галуа 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 14.01.2011 13:41

Цитата:

Сообщение от phys2010 (Сообщение 112373)
Берлекэмп Э. Алгебраическая теория кодирования. М.: Мир, 1971

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

phys2010 14.01.2011 18:36

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

Paul Kellerman 17.01.2011 10:31

Млин... Вот уж не думал, что школьная и институтская алгебра (матан)
могут подложить такие "грабли". Просто еще со школьной скамьи усва-
иваешь, что производная от 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),
ну, а что касается деления логарифмов, она, вроде как, не определена?


Текущее время: 23:49. Часовой пояс GMT +3.

Powered by vBulletin® Version 3.8.8
Copyright ©2000 - 2025, vBulletin Solutions, Inc. Перевод: zCarot
© 2001—2025, «Аспирантура. Портал аспирантов»