Введение к работе
Актуальность проблемы. Сложные сигналы, построенные на основе кодовых последовательностей, широко применяются в цифровых информационно-телекоммуникационных системах различного назначения. Они потенциально обеспечивают высокие показатели эффективности этих систем, однако реализация всех их возможностей часто затруднена из-за значительного усложнения аппаратно-программных процедур формирования и обработки и (или) в силу больших затрат времени на поиск, обнаружение сигнала и устранение априорной неопределенности по его частоте и задержке. Кроме того, широкое распространение получили многопользовательские информационно-телекоммуникационные системы, сложные кодированные сигналы в которых используются для обеспечения одновременной работы множества абонентов в единой полосе частот. В зависимости от типа и конкретного назначения систем они могут именоваться как асинхронные адресные системы, системы многостанционного доступа с кодовым разделением каналов (CDMA) и т.д. В любом случае системы этого типа используют кодирование для уплотнения (разделения) каналов по форме сигнала.
В командных и асинхронных адресных системах передачи информации требуется создание ансамблей квазиортогональных кодовых последовательностей большого размера и высокого качества, гарантирующих малые допустимые уровни междуканальных помех и высокую надежность доставки информации.
Класс информационно-телекоммуникационных систем, включающий командные системы, асинхронные адресные системы передачи информации с кодовым уплотнением каналов (уплотнением по форме), а также системы извлечения информации, интенсивно развиваясь, наиболее требователен к выбору множества (ансамбля) сложных кодированных сигналов.
Указанные причины явились основанием для выбора указанного класса информационно-телекоммуникационных систем в качестве объекта иссследований в диссертационной работе.
К настоящему времени получено большое количество полезных результатов в этой области, а также разработаны и успешно эксплуатируются соответствующие системы, в частности системы CDMA.
Фундаментальными в теоретико-числовой области, области алгебры кодирования и теории кодирования являются работы И.М. Виноградова (основные теоретико-числовые результаты), П. Ланкастера (теория матриц), Э. Берлекэмпа (основы алгебры кодирования), У. Питерсона, Э. Уэлдона (теория помехоустойчивого кодирования), Р. Блейхута (теория помехоустойчивого кодирования), Т. Касами, Н. Токура, Е. Ивадари, Я.
Инагаки (теория помехоустойчивого кодирования). Фундаментальными и наиболее значимыми в области теории сложных сигналов и ее приложений являются работы Э.Д. Витерби (распознавание неортогональных сигналов), Л.Е. Варакина (теория систем сигналов), В.Б. Пестрякова, В.П. Афанасьева, В.Л. Гурвица и др. (применение шумоподобных сигналов в системах передачи информации), R. Gold (описание квазиортогональных последовательностей с тремя уровнями корреляции - кодов Голда) В.М. Сидельникова (взаимная корреляции последовательностей), В.В. Лосева, Е.Б. Бродской, В.И. Коржика (декодирование сложных сигналов).
Работа И.М. Виноградова «Основы теории чисел» содержит материал, необходимый для описания числовых конечных полей, но недостаточный для реализации соответствующих прикладных алгоритмов. В этом смысле эта фундаментальная работа может рассматриваться в качестве теоретико-числовой базы для развития результатов и представлений, необходимых для построения разнообразных высокоэффективных вычислительных алгоритмов в числовых полях Галуа.
Работа Э. Берлекэмпа «Алгебраическая теория кодирования» является, пожалуй, наилучшим, если не единственным трудом в данной области. Вместе с работами У. Питерсона, Э. Уэлдона «Коды, исправляющие ошибки», Р. Блейхута «Теория и практика кодов, контролирующих ошибки», Т. Кассами, Н. Токура, Е. Ивадари, Я. Инагаки «Теория кодирования» монография Э. Берлекэмпа составляет основу современного конструктивного кодирования. С этой позиции работа П. Ланкастера «Теория матриц» является необходимым звеном в цепи компактных представлений и описаний объектов кодирования и преобразований.
К сожалению, эти замечательные работы системно слабо связаны между собой, что затрудняет разработку методов и прикладных алгоритмов, направленных на высокоэффективное формирование и обработку сложных кодированных сигналов, а также понимание и дальнейшее использование отдельных, достаточно сложных и потенциально полезных результатов прикладными (техническими) специалистами. Кроме того, что более важно, большинство конструктивных результатов, полученных в области алгебраической и прикладной теории кодирования, либо уже нашли свое применение, либо близки к этому. В этом смысле ресурс теоретико-прикладных результатов в данной области близок к исчерпанию, что тормозит дальнейшее качественное совершенствование информационно-телекоммуникационных систем. К сожалению, отечественная школа теории кодирования испытывает нелучшие времена в то время, когда приоритеты в этой области в существенной степени определяют конкурентоспособность проектных и технических решений. Достаточно упомянуть изобретенные в 1993 году К. Берроу (С.
Berrou), А. Главьё (A. Glavieux) и П. Ситимашимой (P. Thitimajshima) турбо-коды, успешно используемые сегодня в системах спутниковой и мобильной связи. Многие типовые прикладные задачи, например, определение примитивных многочленов высоких степеней по-прежнему выполняются путем прямого машинного перебора. Отметим, что в последние десятилетия фундаментальных работ, сопоставимых по значимости с работами Э. Берлекэмпа, У. Питерсона, Э. Уэлдона и других упомянутых выше авторов, было издано очень мало. Из доступных работ в области алгебраической теории кодирования публикаций не было вовсе. В области прикладной теории кодирования достойны упоминания работы В.М. Сидельникова, в частности монографию «Теория кодирования» и «Криптография и теория кодирования», а также ряд работ В.В. Золотарева и Г.В. Овечкина. Современные переводные работы М. Вернера «Основы кодирования», Р. Морелос-Сарагосы «Искусство помехоустойчивого кодирования» являются скорее учебно-справочными пособиями.
Не случайно опубликованный план фундаментальных исследований Российской академии наук на период 2011-2025 гг в разделе 1.4 «Дискретная математика и теоретическая информатика» содержит в качестве одной из научных задач ((Развитие теории помехоустойчивых кодов с быстрыми алгоритмами декодирования».
В этой связи развитие алгебраической и прикладной теории кодирования, а также систематизация результатов представляются актуальными задачами.
Работы Р. Голда (R. Gold) посвящены алгебраическому описанию очень полезного подкласса кодовых последовательностей (кодов Голда) с большим ансамблем. К сожалению, ограниченность полученного подкласса кодовых последовательностей не может удовлетворить сегодняшним и перспективным потребностям в формировании квазиортогональных ансамблей сигналов и требует дальнейшего развития математических методов анализа и синтеза кодовых последовательностей с гарантированными корреляционными свойствами.
Работа В.В. Лосева, Е.Б. Бродской, В.И. Коржика «Поиск и декодирование сложных сигналов» описывает оригинальный подход к построению быстрых преобразований, используемых для целей быстрого поиска сложных кодированных сигналов по задержке. К сожалению, описанные преобразования ограничиваются быстрыми преобразованиями Уолша и требуют существенных ресурсов для реализации.
Таким образом, актуальными являются решения таких научно-технических задач, как развитие теории кодирования, теории сигналов, а также разработка на этой основе методов и алгоритмов эффективного формирования и обработки сложных кодированных сигналов в информационно-телекоммуникационных системах рассматриваемого класса.
Научная проблема заключается в разрешении конфликта между растущим количеством абонентов информационно-телекоммуникационных систем и возможностью обеспечить их совместное функционирование с гарантированным качеством при ограничении полосы частот известными средствами построения квазиортогональньгх ансамблей сложных кодированных сигналов.
Объектом исследования является класс информационно-телекоммуникационных систем, включающий командные системы, асинхронные адресные системы передачи информации с кодовым уплотнением каналов (уплотнением по форме), а также системы извлечения информации, требующие использования множества сложных кодированных сигналов с гарантированными корреляционными свойствами.
Предметом исследования являются аналитические методы, модели, а также
алгоритмы, развивающие теорию кодирования, теорию сигналов и их приложения для
выбора ансамблей и реализации трактов формирования и обработки сложных
кодированных сигналов информационно-телекоммуникационных систем
рассматриваемого класса.
Цель и задачи диссертационного исследования. Целью диссертационной работы является разработка новых высокоэффективных аналитических методов и базирующихся на них алгоритмов выбора ансамблей, формирования и обработки сложных кодированных сигналов в информационно-телекоммуникационных системах рассматриваемого класса путем развития разделов теории кодирования, теории сигналов.
Для достижения цели в работе поставлены и решены следующие задачи.
-
Исследование детальных свойств числовой структуры полей Галуа, существенно влияющих на эффективность аналитических представлений полей Галуа и их использования в прикладных задачах кодирования.
-
Разработка эффективных способов отображения элементов абстрактного поля на множество элементов кодовой последовательности, а также унифицированного подхода для представления и генерирования множества примитивных многочленов заданной степени.
-
Создание базы данных и построение таблиц опорных примитивных многочленов до 63 степени.
-
Развитие векторных представлений элементов полей Галуа и разработка на этой основе метода быстрых преобразований в полях Галуа, способствующих повышению эффективности программно-аппаратных реализаций кодеков.
-
Развитие метода синтеза двухкомпонентньгх кодов с гарантированными уровнями взаимной корреляции.
6. Разработка метода синтеза трехкомпонентных кодов с гарантированными уровнями
взаимной корреляции.
7. Разработка методов аналитического и алгоритмического определения вектора
начального состояния регистра сдвига, предназначенного для быстрого скачкообразного
изменения задержки кодовой последовательности в генераторах ключей и подобных
устройствах кодеков.
8. Разработка методов ускоренного поиска длинных кодовых последовательностей по
задержке на основе быстрых преобразований в полях Галуа.
Методы исследований. В процессе решения поставленных задач использованы принципы системного подхода и методы общей теории систем, теории чисел, теории множеств, теории матриц, теории сигналов, теории кодирования, теории радиосистем передачи информации и управления, теории телекоммуникаций.
Научная новизна результатов работы. Научная новизна заключается в развитии разделов теории кодирования, теории сигналов в направлениях теоретического и прикладного характера, расширяющих границы применения аналитических методов для синтеза сложных кодированных сигналов с гарантированными свойствами и создания оригинальных высокоэффективных программно-аппаратных средств формирования и обработки сложных кодированных сигналов применителвно к классу информационно-телекоммуникационных систем, включающему командные системы, асинхронные адресные системы передачи информации с кодовым уплотнением каналов (уплотнением по форме), а также системы извлечения информации.
При этом в диссертационной работе были получены следующие новые научные результаты:
-
Новое, модифицированное представление функции двоичного следа элементов поля Галуа, обеспечивающее построение любого минимального многочлена на основе одного опорного многочлена при формировании кодов различного типа.
-
Обобщенный метод синтеза двухкомпонентных кодов произвольной структуры с гарантированными минимальными уровнями взаимной корреляции для использования в информационно-телекоммуникационных системах, требующих увеличенного размера ансамбля кодов по сравнению с ансамблем кодов максимальной длины.
3. Алгебраическая конструкция и метод синтеза трехкомпонентных кодов с
гарантированными уровнями взаимной корреляции и сверхбольшим ансамблем для
использования в перспективных информационно-телекоммуникационных системах
рассматриваемого класса.
-
Расширенный метод аналитического расчета максимальных уровней функций взаимной корреляции кодовых последовательностей максимальной длины с апробацией полученных результатов для быстрой предварительной оценки потенциальных возможностей выбираемого ансамбля кодов в информационно-телекоммуникационных системах рассматриваемого класса.
-
Таблицы опорных примитивных многочленов и векторов начального состояния, обеспечивающие вместе модифицированной функцией двоичного следа формирование любого примитивного многочлена до 63 степени при построении кодов различного типа.
-
Методы аналитического и алгоритмического определения вектора начального состояния генераторов для быстрого скачкообразного изменения задержки кодовой последовательности в устройствах кодеков информационно-телекоммуникационных систем рассматриваемого класса.
7. Методы ускоренного поиска кодовых последовательностей по задержке,
основанные на быстрых преобразованиях в непростых полях Галуа.
На рис. 1 представлена схема вклада полученных научных результатов в решение прикладных задач.
Практическая значимость результатов работы состоит в том, что разработанные в ней модели, методы, методики и алгоритмы совместно с базами данных позволяют существенно повысить эффективность реализации и расширить область применения кодеков современных и перспективных информационно-телекоммуникационных систем рассматриваемого класса.
Реализация и внедрение результатов работы. Разработанные в диссертационной работе модели, методы и алгоритмы использованы при выполнении госбюджетной научно-исследовательской работы «Разработка математических методов и алгоритмов формирования и обработки сложных сигналов на основе М-последовательностей» по федеральной научно-технической программе «Научные исследования высшей школы по приоритетным направлениям науки и техники» подпрограмма» (подпрограмма «Информационно-телекоммуникационные технологии», раздел «Теория и техника обработки и формирования сигналов в радиотехнических системах») на 2003-2007 гг. и научно-исследовательской работы «Развитие теории и методов эффективного излучения, приема и обработки сложных кодированных сигналов», этап 16, 2009 г.
Результаты работы внедрены в учебный процесс на каф. 402 факультета радиоэлектроники летательных аппаратов МАИ при подготовке дипломированных специалистов по специальностям и направлениям подготовки 090900, 090900.5 и 090915.
Достоверность научных и практических результатов
Достоверность теоретических результатов обоснована применением адекватного математического аппарата теории чисел, теории множеств и алгебры полей Галуа, а также сопоставлением результатов с известными из литературы. Достоверность прикладных результатов подтверждена имитационным моделированием.
Новое, модифицированное представление функции двоичного следа элементов поля
Галуа, обеспечивающее построение любого минимального многочлена на основе одного
опорного многочлена при формировании кодов различного типа (і)
Обобщенный метод синтеза двухкомпонентных кодов произвольной структуры с га- -
рантированнымн минимальными уровнями взаимной корреляции для использования в
информационно-телекоммуникационных системах, требующих увеличенного размера
ансамбля кодов по сравнению с ансамблем кодов максимальной длины (2)
Алгебраическая конструкция и метод синтеза трикомпонентних кодов с гарантиро
ванными уровнями взаимной корреляции и сверхбольшим ансамблем для использо
вания в перспективных информационно-телекоммуникационных системах (з
Расширенный метод аналитического расчета максимальных уровней функций взаимной корреляции кодовых последовательностей максимальной длины с апробацией полученных результатов для быстрой предварительной оценки потенциальных возможностей выбираемого ансамбля кодов в информационно-телекоммуникационных системах (4)
Таблицы опорных примитивных многочленов и векторов начального состояния, (5
обеспечивающие вместе модифицированной функцией двоичного следа формирование любого примитивного многочлена до 63 степени при построении кодов различного типа
Методы аналитического и алгоритмического определения вектора начального состояния генераторов для быстрого скачкообразного изменения задержки кодовой последовательности в устройствах кодеков информационно-телекоммуникационных систем (б;
Методы ускоренного поиска кодовых последовательностей по задержке, основанные на
быстрых преобразованиях в непростых полях Галуа Щ
Рис. 1. Сксма вклада иаучныя результатов в решение прикладных задач
Апробации результатов работы. Материалы диссертационной работы обсуждались на Всесоюзной научно-технической конференции "Методы и микроэлектронные средства преобразования и обработки сигналов" (Рига, 1983), на II Всесоюзной научно-технической конференции "Развитие теории и техники сложных сигналов" (Москва, 1983), на научно-технических конференциях предприятий НИИП, ЦНИИМАШ (Москва, 1984, 1986), на международной научно-технической конференции «Новые информационные технологии» (Рига, 1992), на международной научно-практической конференции "Высшая школа в новых социально-экономических условиях (Санкт-Петербург, 1994), на научно-методической конференции "Современная учебная техника и образовательные технологии" (Нижний Новгород, 1996), на международных научно-технических конференциях «Информационные технологии и математическое моделирование систем» (Италия, 2006; Греция 2009, Франция 2010).
Публикации. По теме диссертационного исследования опубликовано 46 работ (17 без соавторов), в том числе 4 рецензируемых монографии, 15 научных статей, из них 3 в изданиях из перечня рецензируемых научных журналов, рекомендованных ВАК, 1 статья в зарубежном журнале, входящем в базу Web of Science, 4 учебных пособия, 4 авторских свидетельства, 19 тезисов докладов на конференциях.
Структура диссертации. Диссертация состоит из введения, пяти глав с выводами и списками использованной литературы из 33 наименований и двух приложений, включающих в себя таблицу статистики многочленов в полях Галуа и таблицу опорных примитивных многочленов вместе с векторами начальных состояний для степеней многочленов до 63. Объем диссертации составляет 19 печатных листов.
