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

Вернуться   Портал аспирантов > Общие > Дискуссионный зал > Физико-математические науки

Ответ
 
Опции темы
Старый 12.01.2011, 14:51   #11
mbk
Advanced Member
 
Аватар для mbk
 
Регистрация: 22.12.2010
Адрес: Московская область
Сообщений: 316
По умолчанию

Цитата:
Сообщение от phys2010 Посмотреть сообщение
см. картинку ниже.
Спасибо за пояснение.
mbk вне форума   Ответить с цитированием
Реклама
Старый 13.01.2011, 09:35   #12
Paul Kellerman
Gold Member
 
Регистрация: 25.06.2005
Адрес: F000:FFF0
Сообщений: 1,804
По умолчанию

Цитата:
Сообщение от phys2010 Посмотреть сообщение
Теперь используем условие, что мы работаем над полем характеристики 2.
В этом случае все четные коэффициенты сравнимы с 0 (по модулю 2), а
нечетные - с единицей. В результате получаем требуемое выражение для производной
Эээ... Как я уже сказал, я не настолько крут, и мне вот эта вещь не совсем
очевидна. Каким образом из того, что характеристика 2, следует обнуление
четных коэффициентов. Поясните плиз! А вообще большое спасибо за ответ.
Paul Kellerman вне форума   Ответить с цитированием
Старый 13.01.2011, 10:02   #13
mbk
Advanced Member
 
Аватар для mbk
 
Регистрация: 22.12.2010
Адрес: Московская область
Сообщений: 316
По умолчанию

Цитата:
Сообщение от PavelAR Посмотреть сообщение
Каким образом из того, что характеристика 2, следует обнуление
четных коэффициентов
Предлагаю следующую версию:
1) в результате дифф-я у коэффициентов появляются дополнительные сомножители, "вылезшие" из степени;
2) допустим, сомножитель четный. Например, он равен 2.
Тогда 2*байт=байт+байт=00000000.
mbk вне форума   Ответить с цитированием
Старый 13.01.2011, 10:10   #14
Paul Kellerman
Gold Member
 
Регистрация: 25.06.2005
Адрес: F000:FFF0
Сообщений: 1,804
По умолчанию

Цитата:
Сообщение от 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-слагаемых, равных степени, и я это по-своему доказал! Ссылку на это пришлю позже.
Paul Kellerman вне форума   Ответить с цитированием
Старый 13.01.2011, 10:18   #15
mbk
Advanced Member
 
Аватар для mbk
 
Регистрация: 22.12.2010
Адрес: Московская область
Сообщений: 316
По умолчанию

Все равно непонятно.
Ведь кратность искажения - это не элемент поля.
mbk вне форума   Ответить с цитированием
Старый 13.01.2011, 10:32   #16
Paul Kellerman
Gold Member
 
Регистрация: 25.06.2005
Адрес: F000:FFF0
Сообщений: 1,804
По умолчанию

Цитата:
Сообщение от mbk Посмотреть сообщение
Ведь кратность искажения - это не элемент поля
Действительно, она не элемент поля, зато она логарифм элемента поля
Paul Kellerman вне форума   Ответить с цитированием
Старый 13.01.2011, 15:10   #17
phys2010
Silver Member
 
Аватар для phys2010
 
Регистрация: 30.12.2010
Адрес: ЦФО, Россия
Сообщений: 852
По умолчанию

Цитата:
Сообщение от 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.
В ней терия конечных полей изложена ясно и достаточно полно.

Последний раз редактировалось phys2010; 13.01.2011 в 16:40.
phys2010 вне форума   Ответить с цитированием
Старый 14.01.2011, 13:41   #18
Paul Kellerman
Gold Member
 
Регистрация: 25.06.2005
Адрес: F000:FFF0
Сообщений: 1,804
По умолчанию

Цитата:
Сообщение от phys2010 Посмотреть сообщение
Берлекэмп Э. Алгебраическая теория кодирования. М.: Мир, 1971
Читал взахлеб Вообще, Берлекэмп - однозначно гений, придумать алгоритм со
сложностью всего ~ t^2 для решения системы уравнений и при этом, чтобы сте-
пень полинома-решения была минимальной... это просто невообразимая крутизна.
Paul Kellerman вне форума   Ответить с цитированием
Старый 14.01.2011, 18:36   #19
phys2010
Silver Member
 
Аватар для phys2010
 
Регистрация: 30.12.2010
Адрес: ЦФО, Россия
Сообщений: 852
По умолчанию

К сожалению мне трудно это оценить...
Слишком далеко все это находится от области моих интересов
phys2010 вне форума   Ответить с цитированием
Старый 17.01.2011, 10:31   #20
Paul Kellerman
Gold Member
 
Регистрация: 25.06.2005
Адрес: F000:FFF0
Сообщений: 1,804
По умолчанию

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

Опции темы

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.



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


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