2014 dxdy logo

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

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




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

Вот тут то у меня и начинаются сложности, реализовать пытаюсь с помощью 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 
Аватара пользователя
Это потому, что в книге коэффициенты в степенной форме, а матлаб выдает в стандартном базисе. Например, $\alpha^{225} = \alpha^4 + \alpha^2 + \alpha + 1 $ представляется двоичным числом $10111_2 = 23$

 
 
 [ Сообщений: 2 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group