2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.



Начать новую тему Ответить на тему
 
 Код Рида-Соломона.Порождающий полином
Сообщение23.04.2015, 17:06 


06/06/11
60
Здравствуйте, пытаюсь реализовать передачу сообщения как в реальных радионавигационных системах. Есть замечательная книга "Авиационная электросвязь", где перечислены все стандарты и форматы сообщений. Из нее получил сведения о том как дополнять сообщение кодом, который впоследствии можно было бы использовать для восстановления у траченых данных, собственно кодом Рида-Соломона.

Вот тут то у меня и начинаются сложности, реализовать пытаюсь с помощью Matlab.

Вот выдержка из книжки:

3.6.3.3.5 FEC приложения. FEC приложения вычисляется с использованием данных приложения с помощью
систематического (255, 249) кода Рида-Соломона (R-S) фиксированной длины.
3.6.3.3.5.1 Определяющий поле примитивный полином R-S кода, $р(х)$, имеет следующий вид:
$$p(x) = x^8 + x^7 + x^2 +x+1$$
3.6.3.3.5.2 Образующий полином R-S кода, $g(x)$, описывается выражением:
$$g(x)=\prod\limits_{i=120}^{125}(x-\alpha^i)=x^6+\alpha^{176}x^5+\alpha^{186}x^4 + \alpha^{244}x^3+\alpha^{176} x^2+\alpha^{156} x+\alpha^{225}$$

где $\alpha$ представляет собой квадратный корень из $p(x)$, используемый для построения поля Галуа размером 28,
GF(256), а $\alpha^i$ – это $i$-й примитивный элемент в GF(256).

Вот тут у меня сразу возникает несколько вопросов:
1) Почему $i=120$? Есть ли этому причина?
2) Как это раскрыть так скобки можно? Не совсем понимаю. Я понял только про свободный член - там получается $\alpha^{120+121+122+123+124+125}=\alpha^{735}=\alpha^{225}$ и все отлично, но как считать промежуточные степени? Там отрицательные $\alpha$ получаются и я не очень знаком с арифметикой в полях Галуа, чтобы что-нибудь с этим поделать.

Но суть не в этом, в Mathlab существует очень полезная штука - Communications Toolbox для автоматизации процесса генерации кода Рида-Соломона. И простого получения степеней примитивного элемента позволяет нам добиться функция
Код:
rsgenpoly
, куда в качестве фактических параметров подается длинна всего сообщения, длинна полезного сообщения(т.е. за вычетом кода Р-С), десятичная запись примитивного полинома(В нашем случае $1 1 1 0 0 0 0 1 1_2=391_{10}$) $p(x)$, и то самое $i=120$ происхождение которого и вызвало у меня вопрос.
Иными словами, я хочу написать:
Код:
rsgenpoly(255,249,391,120)

И получить ответ
Код:
ans = GF(2^8) array. Primitive polynomial = D^8+D^7+D^2+D+1 (391 decimal)

Array elements =

           1         176          186         244          176         156          225


Но получаю совершенно другое:

Код:
ans = GF(2^8) array. Primitive polynomial = D^8+D^7+D^2+D+1 (391 decimal)

Array elements =

           1         217          99          62         217         130          23


Я не вполне понимаю откуда взялись эти числа.

Для того, чтобы удостовериться в правильности работы функции rsgenpoly я решил покатать по примерам, взял книжку: "Упрощение кодера Рида – Соломона при использовании альтернативных простых полиномов, образующих расширения полей Галуа Д. В. Клейко, Н. В. Лямин". И прогнал некоторые примеры, которые там предлагаются. И примеры из книжки работают просто идеально.

Почему же функция не работает на моем примере?

 Профиль  
                  
 
 Re: Код Рида-Соломона.Порождающий полином
Сообщение23.04.2015, 18:12 
Заслуженный участник
Аватара пользователя


06/10/08
6422
Это потому, что в книге коэффициенты в степенной форме, а матлаб выдает в стандартном базисе. Например, $\alpha^{225} = \alpha^4 + \alpha^2 + \alpha + 1 $ представляется двоичным числом $10111_2 = 23$

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 2 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group