НЕКОТОРЫЕ СВОЙСТВА МНОГОЧЛЕНОВ И ИХ ИСПОЛЬЗОВАНИЕ В ЗАДАЧАХ СВЯЗИ
Лисицына Е.С.,
Фауре Э.В.,
Швыдкий В.В., к.т.н., доцент,
Щерба А.И. , к.ф-м.н., доцент
Черкасский государственный технологический университет
Вестник ЧГТУ,№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.
Доказательство:
Пусть
Или
Тогда
,
что и требовалось доказать.
Следствие.
Если мощность пространства увеличивается в 2m
раз, а вектор сдвигается на k разрядов, то взаимный к нему многочлен определяется как A^(x)xm-k
.
Теорема 3. Взаимный многочлен суммы многочленов одной и той же степени равен сумме взаимных многочленов, т.е.
.
Доказательство
Пусть
или
Обозначим взаимный многочлен к ,тогда
что и требовалось доказать.
Теорема 4. Взаимный многочлен произведения многочленов одной и той же степени равен произведению взаимных многочленов, т.е.
.
Доказательство
Пусть
или .
Тогда
что и требовалось доказать.
Следствие.
Если
, или ,
то или .
Таким образом, вычет взаимного многочлена по взаимному модулю есть многочлен взаимный к вычету прямого многочлена по прямому модулю. Это значит, что кодирование по прямому или взаимному модулю совершенно равноценны и однозначно связаны (взаимно друг в друга пересчитываются).
Теорема 5. Взаимный взаимного многочлена есть прямой многочлен, т.е.
Доказательство
Если
, то
что и требовалось доказать.
Следствие 1. Сумма (произведение) прямого и взаимного к нему многочленов есть симметричный многочлен, т.е. если
1. , то ;
2. , то .
Доказательство:
1. ,
что и требовалось доказать.
2. ,
что и требовалось доказать.
Следствие 2. Сумма, произведение и частное симметричных многочленов есть симметричный многочлен, т.е. если
и , то
1. ;
2. ;
3. .
Доказательство:
,
что и требовалось доказать;
,
что и требовалось доказать.
3. Пусть, т.е. .
Тогда
Отсюда
,
что и требовалось доказать.
5.2. Применение новых свойств многочленов к задачам связи
Применение новых свойств многочленов к задачам помехоустойчивого кодирования
Типовые (стандартные) процедуры помехоустойчивого кодирования базируются на вычислении вычета (остатка или контрольной суммы) в регистре сдвига с обратными связями [7]:
, (4)
где G(x) – неприводимый многочлен, образующий код, а А(х) – вектор информационной части блока.
Полученный остаток дополняет блок и передается по каналу связи на приемную станцию. По принятому блоку
, (5)
где – вектор ошибки, вычисляется синдром ошибки:
. (6)
Вычисление контрольной суммы в кодере и синдрома ошибки в декодере выполняется одинаковыми регистрами сдвига кодера и декодера. Стандартный кодер систем передачи данных для оговорен рекомендацией V-41 МККТТ [7].
Логичным является следующий вопрос:
– имеют ли одинаковую обнаруживающую способность полиномы одной и той же степени (включая взаимные)?
Прежде всего отметим, что контрольная сумма есть вычет информационного многочлена по модулю образующего полинома, т.е.:
(7)
где – элемент кольца вычетов по модулю G(x).
Вычислим вычет инверсного к информационному многочлена:
(8)
Отметим, что для циклического кода Боуза-Чоудхури-Хоквингема (БЧХ кода) длину информационной части блока берут из условия , где k – степень кодового полинома, а L – длина блока. Это значит, что длина информационной части блока не должна превышать длины периода кольца вычетов.
Всегда можно выбрать L=T, а любой двучлен вида представить в виде
.
Учтем, что:
– неприводимый многочлен делит без остатка двучлен, что обозначает ;
– многочлены и имеют одинаковую степень, поэтому.
Отсюда прямой и взаимный многочлен без остатка делит не только, но и .
Поэтому, если неприводимый многочлен несимметричен, т.е. , то имеет место следующее разложение:
. (9)
Учитывая, что
– симметричные многочлены, то F(x) – также симметричный многочлен, степень которого равна d = (T-1)-2k.
Здесь – взаимные несимметричные многочлены (их произведение есть симметричный многочлен). Симметричные многочлены, если они имеются в разложении, записываются отдельно (например, Е(х), (х+1)) или входят в F(x) (см., например, в разложении ).
Учитывая, что
,
получим, что
(10)
т.е. вычеты прямого и инверсного многочленов равны друг другу.
Для вычетов:
– прямого многочлена по взаимному модулю;
– взаимного многочлена по взаимному модулю;
– взаимного многочлена по прямому модулю запишем:
(11)
(12)
где
– элемент кольца вычетов по модулю G^(x).
(13)
Сравнивая (7) и (13), (11) и (12) заметим, что и есть соответственно прямой и обратный элемент кольца вычетов по модулю G(x), связанные, соответственно, как . Аналогично и есть соответственно прямой и обратный элемент кольца вычетов по модулю , . Отсюда следует, что:
1. контрольная сумма прямой и инверсной последовательности равны, кодирование прямой или инверсной последовательности равноценны;
2. процедура кодирования по прямому и взаимному модулю, прямого или взаимного информационного многочлена однотипны. Поэтому, не имеет значения порядок считывания информационных символов в процессе кодирования, важно лишь, какие элементы кольца (прямые или обратные) берутся для кодирования по прямому или взаимному кодовому полиному;
3. кодирующее устройство не обязательно строить в виде регистра сдвига с обратными связями.
Кодирующее устройство может реализовать любую из процедур (7,11,12 или13).
В этом случае кодер может быть представлен структурой, показанной на рис.1 и содержать:
- генератор элементов кольца;
- накапливающий сумматор, который складывает элементы кольца или , взвешенные с весом бита данных(0 или 1) .
|
Рис.1 Структурная схема БЧХ кодера
Данный кодер отличает то полезное свойство, что он не требует битовых операций и обеспечивает легкую смену кодового полинома. В силу этих обстоятельств легко выполняется как аппаратная, так и программная реализация такого кодека для БЧХ кода.
Декодер вычисляет синдром по уравнению (6), при этом, если ε(х) = 0, то S(х) = = 0. Однако, если S(х) = 0, то это не означает, что ε(х) = 0.
Возможна ситуация, когда S(х) = 0 при ε(х) ≠ 0. Эта ситуация есть необнаружение ошибки декодером или остаточная ошибка декодера. Очевидно, ошибка декодирования возникает тогда, когда вектор ошибки кратен порождающему полиному, т.е
. (14)
Если кадр входных данных имеет длину L, то мощность вектора ошибки ε(х) равна 2L
, мощность множества необнаруженных ошибок D(x) равна 2(L-k)
, при этом ошибки на оси 0,1,2,3… 2L
(такую ось можно получить, если записать все вектора ошибки в виде (1), положив хj
= 2j
) распределены равномерно через G(х) ошибок.
Поскольку мощность множества ошибок определяется только степенью порождающего многочлена и не зависит от его структуры и веса (веса по Хэммингу), то все коды, порожденные полиномом одной и той же степени (включая взаимные многочлены) имеют одинаковую обнаруживающую способность. Меняется лишь расположение необнаруживаемых ошибок на числовой оси. Это вовсе не означает, что вероятность остаточной ошибки декодера будет одинакова для любого полинома одной и той же степени. Вероятность остаточной ошибки декодера будет определяться тем, как часто "использует" канал связи ту или иную конфигурацию ошибок, т.е. зависит от статистики ошибок в канале. Отметим, что при равномерном распределении ошибок в канале связи вектора ошибки равномерно распределены по числовой оси, поэтому при любой длине блока доля необнаруженных ошибок не меняется. Отметим также, что с учетом теоремы 1 контрольная сумма прямого и взаимного кодового многочлена взаимны, поэтому они взаимно легко пересчитываются одна в другую и поэтому число неприводимых многочленов степени "k", которые можно использовать для помехоустойчивого кодирования равно числу пар "прямой-взаимный" многочлен.
Применение новых свойств многочленов к задачам генерации псевдослучайных последовательностей (ПСП)
ПСП, в частности, в такой разновидности, как последовательности максимального периода
(М-последовательности) широко используются практически во всех блочных системах передачи данных для обеспечения цикловой синхронизации, в системах связи с шумоподобными сигналами (ШПС) и т.д.
Единственный известный способ генерации М-последовательности заключается в использовании для этой цели регистра сдвига с обратными связями [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.