Некоторые свойства многочленов и их использование в задачах связи (стр. 3 из 3)
Единственный известный способ генерации М-последовательности заключается в использовании для этой цели регистра сдвига с обратными связями [6]. Этот регистр (за счет наличия обратной связи) имеет бесконечную импульсную реакцию, поэтому при любом ненулевом воздействии выдает периодически повторяющуюся импульсную последовательность. Эта последовательность имеет максимальный период (если многочлен неприводим), равный
, (15)где k – порядок многочлена. В этом регистре выполняется вычисление очередного символа решением уравнения вида
.Например, для стандартного мнногочлена
уравнение
обеспечивает вычисление
, (16)где t – номер символа в последовательности. При
t = 0 а16(-1), а12(-1),
а5(-1) – вектор начального воздействия. Очевидно, что он – ненулевой.
В силу периодичности М-последовательности при каждом применении не обязательно выполнять процедуру генерации, достаточно запомнить один из ее сдвигов, все остальные значения могут быть восстановлены циклическим сдвигом последовательности.
Поэтому достаточно лишь однократно сформировать М-последовательность, запомнить ее и многократо применять при возникновении потребности.
Поставим задачу – вычислить М-последовательность или один из ее сдвигов по генераторному многочлену G(x), не прибегая к процедуре генерации по уравнению (15). Кроме того, определим, сколько вообще существует разных М-последовательностей в векторном пространстве размерности 2Т, поскольку ответа на этот вопрос на сегодня не существует. Одну из этих последовательностей (младшей степени) будем называть базисной и обозначать как Ф0(х). Остальные последовательности получим циклическим сдвигом, т.е. вычислением
. (17)Для решения задачи определения базисной М-последовательности воспользуемся выражением (9), где дополнительно отметим, что последовательность Е(х) представима в виде произведения нескольких пар прямой-взаимный многочлен.
Например,
Для n = 3:
Для n = 4:
, где 
Для n = 5:
Учитывая, что в М-последовательности всегда четно число единиц (вес последовательности) легко показать, что М-последовательность без остатка делится как на (х+1), так и на G(x),F(x), поэтому
. (18)Остальные последовательности получают циклическим сдвигом, в соответствии с формулой (16).
Определим
. (19)Учитывая, что обе части сравнения и модуль имеют общий множитель
, после деления получим
и 
. (20)Таким образом, базисная М-последовательность может быть получена из разложения (9), все остальные значения которой получаются из (17) или (19).
По аналогии с (17) запишем, что М-последовательность, порожденная взаимным многочленом
. (21)Учтем, что
, тогда 
.С учетом изложенного, покажем, что М-последовательности, порожденные взаимными многочленами, взаимны.
Теорема 6. М-последовательности, порожденные взаимными многочленами, взаимны, т.е.
.Доказательство:
Поскольку
, то: 
В силу симметрии F(x) (следствие 3 теоремы 5)
,что и требовалось доказать.
Пример.
Пусть Т=15 разложение принимает вид:
Отсюда следует, что разных М-последовательностей, которые могут быть использованы для решения задач связи в пространстве
, столько, сколько пар прямой-взаимный многочлен в разложении . В частности, в пространстве размерности 7 (генераторный полином 3 степени) существует только одна М-последовательность. В пространстве размерности 15 (генераторный полином 4 степени) также существует только одна М-последовательность. В пространстве размерности 31 (генераторный полином 5 степени) существует три М-последовательности. Таким образом, разложение на простые сомножители бинома , выделение пар прямой-взаимный многочлен определяет общее количество М-последовательностей длины Т в пространстве и их генераторные многочлены.6.Полученные результаты
Выполненная работа дала возможность ответить на поставленные в разделе 3 вопросы:
– обнаруживающие свойства циклического кода не связаны со структурой кодового полинома, поэтому при равновероятно распределенной ошибке вероятность остаточной ошибки декодера не зависит от структуры полинома одной и той же степени. При неравновероятной статистике вероятность остаточной ошибки декодера определяется структурой потока ошибок и является предметом дальнейших исследований;
– альтернативой общепринятой процедуре построения кодеров циклических кодов, основанной на использовании регистров сдвига с обратными связями, являются процедуры, описываемые уравнениями (7) и (11), (12) и (13), которые в отличие от общепринятых схем не требуют битовых операций и, следовательно, проще программируются;
– альтернативой общепринятой процедуре построения генераторов М-последовательностей, основанной на использовании регистров сдвига с обратными связями, являются процедуры, описываемые уравнениями (18) и (20);
– разных М-последовательностей в пространстве
, разных кодовых полиномов столько, сколько пар "прямой- взаимный" многочлен в разложении двучлена .Выводы
Полученные результаты расширяют возможности кодирующих устройств, обеспечивают возможность вычисления М-последовательностей в векторном пространстве мощности2Т.
Список литературы
1. Варакин Л.Е. Системы связи с шумоподобными сигналами. – М.: Радио и связь, 1985. – 384с.
2. Ф.Дж. Мак-Вильямс, Н.Дж.Слоэн. Теория кодов, исправляющих ошибки. – М.: Связь,1979. – 744с.
3. А. Молдовян, Н. Молдовян, Б. Светлов. Криптография. – СПб.: Лань, 2001. – 320с.
4. Лега Ю.Г., Лисицына Е.С., Фауре Э.В., Швидкий В.В. Основные характеристики систем цикловой синхронизации, использующих последовательности быстрого поиска // Вісник ЧДТУ. – 2006. - №1.
5. Новик Д.А. Эффективное кодирование. – М.: Энергия, 1965. – 235с.
6. Р. Лидл, Г. Нидеррайтер. Конечные поля (в двух томах). – М.: Мир, 1988. – 822с.
7. Рекомендация Международного консультативного комитета по телефонии и телеграфии V-41. Женева, 1976.