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

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

Ответ
 
Опции темы
Старый 08.12.2010, 12:31   #1
Paul Kellerman
Gold Member
 
Регистрация: 25.06.2005
Адрес: F000:FFF0
Сообщений: 1,804
По умолчанию Вопрос по алгебраической теории кодирования

Одними из популярных помехоустойчивых кодов, широко применяемых при
передаче и хранении информации являются коды Рида-Соломона. Однако,
для кодирования и декодирования информации используется специальная
полиномиальная алгебра, заданная над конечным полем Галуа 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 - четное.

Мне интересно, с какого, так сказать, "дуба" это формула упала. Есть ли
где-нибудь и какое-нибудь определение формальной производной, так как
это сделано для производной функции в случае традиционной алгебры или
это просто "нечто", не имеющей пока что никакой математической базы?
Paul Kellerman вне форума   Ответить с цитированием
Реклама
Старый 01.01.2011, 23:26   #2
phys2010
Silver Member
 
Аватар для phys2010
 
Регистрация: 30.12.2010
Адрес: ЦФО, Россия
Сообщений: 852
По умолчанию

PavelAR, посмотрите Б.Л. ван дер Варден, Алгебра, "Наука", 1976. В начале гл.5, на стр. 105, дано алгебраическое определение производной целой рациональной функции для произвольного кольца многочленов без использования понятия непрерывности. В частности - определение производной многочлена над конечным полем.
phys2010 вне форума   Ответить с цитированием
Старый 01.01.2011, 23:50   #3
Ink
Киберпанк
 
Регистрация: 24.04.2009
Сообщений: 10,958
По умолчанию

Б.Л. ван дер Варден, Алгебра, "Наука", 1976. В начале гл.5, на стр. 105
Ink вне форума   Ответить с цитированием
Старый 01.01.2011, 23:57   #4
gav
Silver Member
 
Аватар для gav
 
Регистрация: 03.09.2004
Сообщений: 895
По умолчанию

Как же здорово натыкаться на схожесть аналогичных операций над принципиально различными объектами. Где эту схожесть никак не ожидаешь. Только за это стоит любить математику
gav вне форума   Ответить с цитированием
Старый 11.01.2011, 16:23   #5
mbk
Advanced Member
 
Аватар для mbk
 
Регистрация: 22.12.2010
Адрес: Московская область
Сообщений: 316
По умолчанию

Скорее всего, объект d(L(X))/dX не является обобщением производной в ее классическом понимании, т.к. невозможно сконструировать предельный переход. Я бы трактовал это как линейный оператор, образ которого позволяет дать количественную оценку чувствительности исходного полинома L(X) к "шевелению" элемента Х (конечно, это тоже очень сыро, ведь "шевеление" надо понимать в топологическом смысле).
Кстати, по Ван дер Вардену непонятно, зависит ли значение производной от h (выбранного произвольным образом).
mbk вне форума   Ответить с цитированием
Старый 11.01.2011, 18:02   #6
phys2010
Silver Member
 
Аватар для phys2010
 
Регистрация: 30.12.2010
Адрес: ЦФО, Россия
Сообщений: 852
По умолчанию

Цитата:
Сообщение от mbk Посмотреть сообщение
невозможно сконструировать предельный переход
При алгебраическом подходе к определению производной это требовоние не является обязательным.

Цитата:
Сообщение от mbk Посмотреть сообщение
по Ван дер Вардену непонятно, зависит ли значение производной от h (выбранного произвольным образом).
Никаких условий на выбор переменной h здесь нет. Надо лишь помнить, что при работе с конечными полями выборка, обычно, небольшая.
phys2010 вне форума   Ответить с цитированием
Старый 12.01.2011, 10:37   #7
Paul Kellerman
Gold Member
 
Регистрация: 25.06.2005
Адрес: F000:FFF0
Сообщений: 1,804
По умолчанию

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

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

Ковыряясь конкретно с кодами Рида-Соломона, я имел дело с полем
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 за то, что теперь есть где обсуждать отрас-
левые научные вопросы, не связанные с работой над диссертацией или
преподавательской деятельностью. Вопросов таких очень даже немало.

Последний раз редактировалось Paul Kellerman; 12.01.2011 в 11:11.
Paul Kellerman вне форума   Ответить с цитированием
Старый 12.01.2011, 11:57   #8
phys2010
Silver Member
 
Аватар для phys2010
 
Регистрация: 30.12.2010
Адрес: ЦФО, Россия
Сообщений: 852
По умолчанию

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).
phys2010 вне форума   Ответить с цитированием
Старый 12.01.2011, 12:25   #9
mbk
Advanced Member
 
Аватар для mbk
 
Регистрация: 22.12.2010
Адрес: Московская область
Сообщений: 316
По умолчанию

Интересно, а как здесь устроено умножение?
mbk вне форума   Ответить с цитированием
Старый 12.01.2011, 13:30   #10
phys2010
Silver Member
 
Аватар для phys2010
 
Регистрация: 30.12.2010
Адрес: ЦФО, Россия
Сообщений: 852
По умолчанию

Цитата:
Сообщение от mbk Посмотреть сообщение
Интересно, а как здесь устроено умножение?
В общем случае это можно найти у Ван дер Вардена (неплохая книга для первого чтения). Для небольших полей Галуа см. картинку ниже.
Вложения
Тип файла: zip 2011-01-12_132430.zip (91.1 Кб, 6 просмотров)
phys2010 вне форума   Ответить с цитированием
Ответ

Опции темы

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

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



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


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