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