Некоторые свойства многочленов и их использование в задачах связи (стр. 1 из 3)

НЕКОТОРЫЕ СВОЙСТВА МНОГОЧЛЕНОВ И ИХ ИСПОЛЬЗОВАНИЕ В ЗАДАЧАХ СВЯЗИ

Лисицына Е.С.,

Фауре Э.В.,

Швыдкий В.В., к.т.н., доцент,

Щерба А.И. , к.ф-м.н., доцент

Черкасский государственный технологический университет

Вестник ЧГТУ,№4,2006, стр134-140

Постановка проблемы

Создание эффективных систем передачи данных, используемых для передачи основных информационных потоков, обеспечивающих жизнедеятельность современного общества (речь, изображение, данные ЭВМ), базируется на использовании современной математической базы и, в частности, на теории конечных полей.

Теория конечных полей нашла широкое применение при решении задач помехоустойчивого кодирования, шифрования, передачи данных сигналами с большой базой (шумоподобных сигналов - ШПС) [1,2,3,4] и т.п.

В этих системах информация передается блоками (кадрами, пакетами), в связи с чем каждый блок может быть представлен многочленом (вектором) фиксированной размерности вида:

. (1)

Отметим, что старший коэффициент а_n многочлена А(х) может равняться нулю. Записью А_n(х)=А(х) подчеркивается тот факт, что рассматриваются многочлены из линейного пространства размерности не выше "n+1".

Инверсный многочлен обозначим как:

(2) или, что тоже самое,

,

где Е_n(х) – единичный многочлен размерности n, такой, что все элементы вектора равны единице.

Обозначим взаимный (двойственный) многочлен, у которого обратный порядок считывания символов, как:

. (3)

Под симметричным многочленом понимаем такой, что

.

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

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

В [2] указано, что корни взаимного многочлена обратным корням исходного прямого многочлена, а многочлен взаимный к неприводимому – неприводим. В работе [5] показано, что условием самосинхронизации префиксных кодов является непрефиксность взаимного кода. Этими известными фактами исчерпывается применяемость свойств взаимных многочленов в решении задач связи. Очевидно, что дополнительные исследования свойств и связей прямых инверсных и взаимных многочленов расширит круг решаемых задач.

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

2. Выделение нерешенных ранее частей общей проблемы

К числу нерешенных задач современной техники передачи данных, связанных со свойствами многочленов, можно отнести следующие.

1. Как связаны обнаруживающие свойства циклического кода со структурой кодового полинома и его весом?

2. Как связаны между собой обнаруживающие свойства прямого и взаимного кодового полинома. Этот вопрос может быть сформулирован проще – какой код лучше: по прямому или по взаимному многочлену, и чем они отличаются?

3. Общепринятой схемой построения генераторов М-последовательностей и кодеров циклических кодов являются схемы, основанные на использовании регистров сдвига с обратными связями. Существуют ли иные схемы построения генераторов М-последовательностей и кодеров циклических кодов? Чем они отличаются от регистровых?

4. Сколько разных М-последовательностей в пространстве

и как они связаны между собой?

5. Сколько разных проверочных полиномов степени "n" может быть использовано?

3. Постановка задачи

Целью настоящей работы является выявление новых свойств взаимных и инверсных многочленов и их применение для решения задач связи, таких как помехоустойчивое кодирование с кодами Боуза-Чоудхури-Хоквингема (БЧХ кодами), использование шумоподобных сигналов, а также задач синхронизации с шумоподобными синхросигналами.

5. Решение задачи

Новые свойства многочленов

Рассмотрим дополнительно свойства взаимных многочленов, для чего сформулируем несколько теорем.

Теорема 1. Взаимный многочлен произведения вектора на скаляр равен произведению взаимного многочлена сомножителя на этот скаляр, т.е.

Доказательство:

Если

,

то

,

что и требовалось доказать.

Теорема 2. Сдвиг вектора не изменяет взаимный многочлен, т.е.

, а изменяет только размерность пространства до значения n+k.

Доказательство:

Пусть

Или

Тогда

,

что и требовалось доказать.

Следствие.

Если мощность пространства увеличивается в 2^m раз, а вектор сдвигается на k разрядов, то взаимный к нему многочлен определяется как A^(x)x^m-k.

Теорема 3. Взаимный многочлен суммы многочленов одной и той же степени равен сумме взаимных многочленов, т.е.

.

Доказательство

Пусть

или

Обозначим

взаимный многочлен к ,тогда

что и требовалось доказать.

Теорема 4. Взаимный многочлен произведения многочленов одной и той же степени равен произведению взаимных многочленов, т.е.

.

Доказательство

Пусть

или .

Тогда

что и требовалось доказать.

Следствие.

Если

, или ,

то

или .

Таким образом, вычет взаимного многочлена по взаимному модулю есть многочлен взаимный к вычету прямого многочлена по прямому модулю. Это значит, что кодирование по прямому или взаимному модулю совершенно равноценны и однозначно связаны (взаимно друг в друга пересчитываются).

Теорема 5. Взаимный взаимного многочлена есть прямой многочлен, т.е.

Доказательство

Если

, то

что и требовалось доказать.

Следствие 1. Сумма (произведение) прямого и взаимного к нему многочленов есть симметричный многочлен, т.е. если

1.

, то ;

2.

, то .

Доказательство:

1.

,

что и требовалось доказать.

2.

,

что и требовалось доказать.

Следствие 2. Сумма, произведение и частное симметричных многочленов есть симметричный многочлен, т.е. если

и , то

1.

;

2.

;

3.

.

Доказательство:

,

что и требовалось доказать;

,

что и требовалось доказать.

3. Пусть

, т.е.

.

Тогда

Отсюда

,