Введение к работе
Актуальность темы. Решение широкого круга задач методами математического моделирования требует формирования случайных (псевдослучайных) последовательностей. При проектировании разлігшьгх радиотехнических комплексов и систем связи очень часто приходится решать проблемы имитации и обработки случайных сигналов. В системах технической диагностики шлитация случайных сигналов необходима для исследования работоспособности сложных систем и сетей, встроенного тестового контроля. Как правило, вместо случайных успешно применяются псевдослучайные последовательности (ПСП), которые удовлетворяют определенным критериям случайности (уравновешенность, свойство серий, свойство корреляции и т.д.).
Одним яз методов получения ПСП является их построение на основе разностных множеств (РМ). Для построения ПСП путем рекуррентных вычислительных процедур требуются неприводимые полиномы (НП) над полями Галуа. D качестве генератора ПСП применяются автономные линейные последовательностные машины.
В теории и практике сложных широкополосных сигналов РМ, сбалансированные на один или два уровня, широко применяются для построения дискретно-кодированных последовательностей (ДКП) с хорошими автокорреляционными свойствами. В свою очередь, для построения некоторых РМ используются ШТ.
Спектр применения НП очень широк. НП необходимы для построения ПСП, которые используются для решения задач методом Монте-Карло, для защиты от несанкционированного доступа. Кроме того, НП лежат в основе наиболее распространенных правил кодирования, которые в радиотехнических системах различного назначения применяются для формирования сложных широкополосных сигналов, в системах связи и передачи информации - для .построения циклических кодов, контролирующих и исправляющих ошибки, их декодеров я многих других приложениях.
Т.о., актуальность исследования РМ и НП над конечными полями обусловлена их разнообразным применением в различных областях науки и техники.
Основными параметрами РМ, сбалансированного на m уровней,
b(n, К+Д,Л2.--Дт) являются модуль N, число вычетов К+, число уровней m и
множество значений уровней {Яи} (u = l,mj. - ...
РМ широко применяются для синтеза ДКП, который заключается в поиске новых или деформации известных правил кодирования для достижения заданных пороговых значений параметров ДКІІ. Например, задача синтеза двоичных последовательностей (ДП) со свойством «не более "ктак совпадений» (боковые лепестки периодической автокорреляционной функции ДП ограничены величиной Xmzx) сводится к поиску РМ, ограниченных по уровню величиной Хтах. Т.о., синтез РМ заключается в поиске новых РМ, параметры которых удовлетворяют заданным пороговым значениям. Простейшее решение задачи синтеза РМ связано с перебором большого числа вариантов, который даже при сравнительно небольшом числе переменных невозможно выполнить с помощью ЭВМ. Алгоритмы направленного поиска, позволяющие резко сократить перебор, разработаны В.Е. Гаїггмахером для синтеза ДП со свойством «не более Хтзх совпадений» на основе математического аппарата циклотомнческих чисел.
Интерес к циклотомии был возрожден в 1935г. важными результатами Л. Диксона. Вычисления циклотомических чисел низкого порядка, начатые статьями Л. Диксона, были продолжены другими математиками (Muskat J.B., Whiteman A.L.).
М. Холл использовал математический аппарат циклотомических чисел для описания РМ, сбалансированных на один уровень, а именно для описания РМ квадратичных, биквадратичных, восьмеричных вычетов и РМ, впоследствии названных его именем.
Циклотомические числа нашли свое применение для решения прикладных задач в теории сигналов (Boehmer A.M., Свердлик М.Б.). Попытка реализовать возможности обобщенного анализа и синтеза ДКП привела к разработке В.Е. Гаїггмахером основ теории спектров разности классов вычетов (СРКВ) над простыми полями Галуа, которая позволяет решать задачи анализа, синтеза и формирования ДКП на основе математического аппарата циклотомических чисел. Т.о., теория СРКВ позволяет строить алгоритмы синтеза РМ. Однако, предложенная В.Е. Гантмахером теория СРКВ применима для синтеза РМ лишь но простому модулю. Вместе с тем существование примитивного элемента для чисел N = рт или2рт дает возможность упорядочить смежные классы вычетов и распространить теорию СРКВ на модуль N = р7 или 2р7 .
Одно из решений задачи построения РМ, сбалансированных на один уровень, а
5 именно - РМ Зингера, сводится к поиску НП над полями Гапуа. В зарубежной научно-технической литературе представлены разработки алгоритмов построоїшя НП над простым полем Галуа (Popovici СР.), получения новых примитивных многочленов над GF(p) на основе одного такого многочлена (Alanen J.D., Knuth D.E.), описаны вероятностные алгоритмы для построения НП (Rabin М.О., Caimet J.). В отечественной литературе разработки методов генерирования НП над конечными полями представлены в работах P.P. Варшамова, A.M. Антоняна, Л.И. Гамкрелидзе.
В.Е. Гантмахером предложен алгоритм расчета коэффициентов НП второй и третьей степени над простыми полями Гатуа, однако уже для третьей степени НП алгоритм расчета становится громоздким.
Проведенный обзор показал, что алгоритмов построения НП много, но они очень специализированные - одни применимы только для GF(2), другие только для GF(p), р Ф 0 mod 2, третьи только для п - не простое число и т.д. Кроме того, практически все они неудобны для реализации на ЭВМ. Следовательно, одна из проблем построения НП состоит в необходимости унификации алгоритма вычисления коэффициентов НП и адаптации его к ЭВМ.
Другая проблема состоит в необходимости расширения известных полных таблиц НП, поскольку их объемы уже не удовлетворяют возрастающим потребностям в НП для решения многих прикладных задач. Так для обеспечения криптостойкости систем связи производят многократігую замену НП, взятых из некоторого множества НП. Глобальное множество НП необходимо также для построения ансамблей ДКП, которые применяются в системах связи, например, для обеспечения кодового разделения абонентов при работе в одной и той же полосе частот.
НП с коэффициентами из поля GF(2) применяются для синтеза бинарных последовательностей, пользующихся наибольшей-популярностью у разработчиков радиоэлектронных систем. Поэтому в научно-технической литературе наиболее широко представлены таблицы НП над GF(2).
Опубликованные в 1935 г. таблицы НП над простыми полями нечетной характеристики (Church R.) были ограничены четвертой степенью (п<4) для характеристики р=7. В 1970 г. они были расширены Г. А. Гараковым, поднявшим на единицу границу
для и и добавившим случаи р=11 и n < 4. Другие расширения таблиц предусматривали случаи 11 < р < 37 для irf и 11 < р < 19 для n=3 (Chang JA., Godwin H.I).
Сформулируем перечисленные выше проблемы синтеза РМ и построения НП над конечными полями.
Проблема синтеза разностных множеств заключается в том, что отсутствуют удобные для реализации на ЭВМ методы синтеза РМ по модулю N - рт или 2р7 .
Проблемы построения неприводимых полиномов над конечными полями заключаются в том, что:
отсутствуют удобные для реализации на ЭВМ методы расчета глобального множества НП для заданной характеристики поля и степени полинома над простыми и расширенными полями Галуа;
на нынешнем этапе развития науки и техники существующие полные таблицы НП уже не удовлетворяют запросам разработчиков современных радиотехнических и вычислительных систем.
В диссертации теория СРКВ и метод синтеза РМ на основе СРКВ распространяются на модуль N = рг или 2pY .
Удобный для реализации на ЭВМ алгоритм вычисления коэффициентов НП и их периодов состоит в получении всего множества НП заданной степени на основе одного примитивного полинома и базируется на использовании М-последователыюстей,
смежных классов вычетов по модулю М = qm - 1 и обобщенной формулы расчета коэффициентов. Сокращение вычислений и решение проблемы компактного вывода результатов расчета достигается за счет дуговой структуры М-тюследователыюсти.
Т.о., объектом исследований являются разностные множества и неприводимые полиномы над конечными полями, а предметом исследований - вычислительные методы и программы синтеза РМ и построения полных таблиц НП.
Актуальность работы обусловлена разнообразным применением результатов исследований при решении прикладных задач. Следует отметить, что наиболее эффективным является использование полученных результатов в математическом моделировании для построения генераторов псевдослучайных чисел и в теории сигналов для синтеза ДКІТ.
Актуальность работы обусловлена отсутствием унифицированных регулярных методов синтеза РМ по модулю N=pv HnH2pY, отсутствием быстрых алгоритмов формирования полных таблиц НП над простыми и расширенными полями Галуа произвольной степеїш и произвольной характеристики.
Цель диссертационной работы состоит в разработке удобных дім реализации на ЭВМ методов синтеза РМ по модулю N = рг или2рг и расчета полных таблиц НП над простыми и расширенными полями Галуа, а также в разработке на основе полученных методов алгоритмов и программ для ЭВМ.
Основные научные задачи, решаемые в диссертации:
распространить теорию СРКВ и метод синтеза РМ на основе СРКВ на модуль N = pv или2р7;
разработать алгоритмы и программы синтеза РМ на основе СРКВ;
получить метод расчета коэффициентов НП над простыми и расширенными полями Галуа для заданных характеристики поля и степени НП;
разработать алгоритмы и программы расчета таблиц НП над простыми и расширенными полями Галуа.
Научная новизна, по мнению автора, заключается в том, что:
распространение теории СРКВ на модуль N = ру или 2рт не только является обобщением известной теории СРКВ по простому модулю, но и содержит свойства СРКВ, специфические для модуля N = рт или2ру, а также связь СРКВ по различному модулю;
разработанные программы синтеза РМ и расчета таблиц НП позволяют вычислять РМ и НП с заданными ограничениями на параметры (РМ с ограничением на максимальное число и значение уровней; НП с заданным периодом корней, числом ненулевых коэффициентов, характеристикой поля и др.);
рассчитанные таблицы НП являются самыми полными из известных автору в отечественной и зарубежной научно-технической литературе.
Достоверность научных положений, выводов я рекомендаций, сформулированных в диссертации, подтверждаются результатами:
синтеза РМ, выполненного по методам, предложенным в диссертации;
определение неприводимости полиномов в рассчитанных, таблицах по различным критериям;
обсуждений научных и практических выводов диссертации и их положительной оценкой на научно-технических конференциях различного ранга.
результатами двух НИР, выполненных по теме диссертации при непосредственном участии автора.
Практическая ценность состоит в доведении всех теоретических положений диссертации до вида, удобного разработчику. Результаты расчетов на ЭВМ неприводимых полиномов по предложенным алгоритмам реализованы в виде таблиц, а программы расчета представлены в виде, удобном для пользователя, и зарегистрированы в РосАПО. Результаты синтеза РМ также реализованы в виде таблиц. Программы синтеза РМ на основе нескольких классов вычетов и расчета таблиц НП над расширенными полями Галуа приведены в приложении.
Апробация результатов. Основные положения диссертационной работы докладывались, обсуждались и одобрены на:
-ГГОСНовГУ. 1995,1996;
всероссийской НТК с международным участием "Электроника и информатика". Москва. Зеленоград. 1995;
третьей межведомственной НТК «Проблемные вопросы сбора, обработки и передачи информации в сложных радиотехнических системах». Санкт-Петербург. Пушкин. 1997;
первой международной конференции и выставке «Цифровая обработка сигналов и ее применение». Москва. 1998.
В полном объеме диссертация докладывалась на
- расширенном заседании кафедры прикладной математики НовГУ им. Ярослава
Мудрого, апрель 1998.
Научные результаты опубликованы автором в 8 работах. Из них две книги, 4 печатные работы, 2 отчета о НИР. Зарегистрированы в РосАПО 2 программы для ЭВМ.
9 Структура, Диссертационная работа состоит из введения, грех глав, заключения, списка использованной литературы из 72 наименований и двух приложений.
Введение содержит общую характеристику работы, включающую актуальность, формулировку проблем, цель исследований а также основные задачи, решаемые в диссертации.
