автореферат диссертации по радиотехнике и связи, 05.12.13, диссертация на тему:Теория и практика кодирования

На правах рукоииси

МИХАЙЛОВ Владимир Юрьевич

ТЕОРИЯ И ПРАКТИКА КОДИРОВАНИЯ

Специальность: 05.12.13 - Системы, сети и устройства телекоммуникаций

Автореферат

диссертации в виде опубликованной монографии на соискание ученой степени доктора технических наук

Москва-2012

Работа выполнена на кафедре «Радиосистемы передачи информации и управления» Московского авиационного института (национального исследовательского университета)

Официальные оппоненты: доктор технических наук, профессор

Баринов Виктор Владимирович

доктор технических наук, профессор Черевков Константин Владимирович,

доктор технических наук Сизых Вадим Витальевич

Ведущая организация: Учреждение Российской академии наук, Центр

информационных технологий в проектировании (ЦИТП) РАН, г. Москва

Защита состоится «27 марта» 2012 г. совета Д 212.125.02 Московского исследовательского университета) по Волоколамское шоссе, д. 4.

в 10:00 часов на заседании диссертационного авиационного института (национального адресу: 125993, г.Москва, А-80, ГСП-3,

С диссертацией можно ознакомиться в библиотеке Московского авиационного института (национального исследовательского университета).

Автореферат диссертации разослан« " » 2012 г.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность проблемы. Сложные сигналы, построенные на основе кодовых последовательностей, широко применяются в цифровых информационно-телекоммуникационных системах различного назначения. Они потенциально обеспечивают высокие показатели эффективности этих систем, однако реализация всех их возможностей часто затруднена из-за значительного усложнения аппаратно-программных процедур формирования и обработки и (или) в силу больших затрат времени на поиск, обнаружение сигнала и устранение априорной неопределенности по его частоте и задержке. Кроме того, широкое распространение получили многопользовательские информационно-телекоммуникационные системы, сложные кодированные сигналы в которых используются для обеспечения одновременной работы множества абонентов в единой полосе частот. В зависимости от типа и конкретного назначения систем они могут именоваться как асинхронные адресные системы, системы многостанционного доступа с кодовым разделением каналов (CDMA) и т.д. В любом случае системы этого типа используют кодирование для уплотнения (разделения) каналов по форме сигнала.

В командных и асинхронных адресных системах передачи информации требуется создание ансамблей квазиортогоиальных кодовых последовательностей большого размера и высокого качества, гарантирующих малые допустимые Уровни междуканальных помех и высокую надежность доставки информации.

Класс информационно-телекоммуникационных систем, включающий командные системы, асинхронные адресные системы передани информации с кодовым уплотнением каналов (уплотнением по форме), а также системы извлечения информации, интенсивно развиваясь, наиболее требователен к выбору множества (ансамбля) сложных кодированных сигналов.

Указанные причины явились основанием для выбора указанного класса информационно-телекоммуникационных систем в качестве объекта иссследований в диссертационной работе.

К настоящему времени получено большое количество полезных результатов в этой области, а также разработаны и успешно эксплуатируются соответствующие системы, в частности системы CDMA.

Фундаментальными в теоретико-числовой области, области алгебры кодирования и теории кодирования являются работы И.М. Виноградова (основные теоретико-числовые результаты), П. Ланкастера (теория матриц), Э. Берлекэмпа (основы алгебры кодирования), У. Питерсона, Э. Уэдцона (теория помехоустойчивого кодирования), Р. Блейхуга (теория помехоустойчивого кодирования), Т. Касами, Н. Токура, Е. Ивадари, Я.

Инагаки (теория помехоустойчивого кодирования). Фундаментальными и наиболее значимыми в области теории сложных сигналов и ее приложений являются работы Э.Д. Витерби (распознавание неортогональных сигналов), Л.Е. Варакина (теория систем сигналов), В.Б. Пестрякова, В.П. Афанасьева, B.JI. Гурвица и др. (применение шумоподобных сигналов в системах передачи информации), R. Gold (описание квазиортогональных последовательностей с тремя уровнями корреляции - кодов Голда) В.М. Сидельникова (взаимная корреляции последовательностей), В.В. Лосева, Е.Б. Бродской, В.И. Коржика (декодирование сложных сигналов).

Работа И.М. Виноградова «Основы теории чисел» содержит материал, необходимый для описания числовых конечных полей, но недостаточный для реализации соответствующих прикладных алгоритмов. В этом смысле эта фундаментальная работа может рассматриваться в качестве теоретико-числовой базы для развития результатов и представлений, необходимых для построения разнообразных высокоэффективных вычислительных алгоритмов в числовых полях Галуа.

Работа Э. Берлекэмпа «Алгебраическая теория кодирования» является, пожалуй, наилучшим, если не единственным трудом в данной области. Вместе с работами У. Питерсона, Э. Уэлдона «Коды, исправляющие ошибки», Р. Блейхута «Теория и практика кодов, контролирующих ошибки», Т. Кассами, Н. Токура, Е. Ивадари, Я. Инагаки «Теория кодирования» монография Э. Берлекэмпа составляет основу современного конструктивного кодирования. С этой позиции работа П. Ланкастера «Теория матриц» является необходимым звеном в цепи компактных представлений и описаний объектов кодирования и преобразований.

К сожалению, эти замечательные работы системно слабо связаны между собой, что затрудняет разработку методов и прикладных алгоритмов, направленных на высокоэффективное формирование и обработку сложных кодированных сигналов, а также понимание и дальнейшее использование отдельных, достаточно сложных и потенциально полезных результатов прикладными (техническими) специалистами. Кроме того, что более важно, большинство конструктивных результатов, полученных в области алгебраической и прикладной теории кодирования, либо уже нашли свое применение, либо близки к этому. В этом смысле ресурс теоретико-прикладных результатов в данной области близок к исчерпанию, что тормозит дальнейшее качественное совершенствование информационно-телекоммуникационных систем. К сожалению, отечественная школа теории кодирования испытывает нелучшие времена в то время, когда приоритеты в этой области в существенной степени определяют конкурентоспособность проектных и технических решений. Достаточно упомянуть изобретенные в 1993 году К. Берроу (С.

Berrou), А. Главьё (A. Glavieux) и П. Ситимашимой (P. Thitimajshima) турбо-коды, успешно используемые сегодня в системах спутниковой и мобильной связи. Многие типовые прикладные задачи, например, определение примитивных многочленов высоких степеней по-прежнему выполняются путем прямого машинного перебора. Отметим, что в последние десятилетия фундаментальных работ, сопоставимых по значимости с работами Э. Берлекэмпа, У. Питерсона, Э. Уэлдона и других упомянутых выше авторов, было издано очень мало. Из доступных работ в области алгебраической теории кодирования публикаций не было вовсе. В области прикладной теории кодирования достойны упоминания работы В.М. Сидельникова, в частности монографию «Теория кодирования» и «Криптография и теория кодирования», а также ряд работ В.В. Золотарева и Г.В. Овечкина. Современные переводные работы М. Вернера «Основы кодирования», Р. Морелос-Сарагосы «Искусство помехоустойчивого кодирования» являются скорее учебно-справочными пособиями.

Не случайно опубликованный план фундаментальных исследований Российской академии наук на период 2011-2025 гг в разделе 1.4 «Дискретная математика и теоретическая информатика» содержит в качестве одной из научных задач «Развитие теории помехоустойчивых кодов с быстрыми алгоритмами декодирования».

В этой связи развитие алгебраической и прикладной теории кодирования, а также систематизация результатов представляются актуальными задачами.

Работы Р. Голда (R. Gold) посвящены алгебраическому описанию очень полезного подкласса кодовых последовательностей (кодов Голда) с большим ансамблем. К сожалению, ограниченность полученного подкласса кодовых последовательностей не может удовлетворить сегодняшним и перспективным потребностям в формировании квазиортогональных ансамблей сигналов и требует дальнейшего развития математических методов анализа и синтеза кодовых последовательностей с гарантированными корреляционными свойствами.

Работа В.В. Лосева, Е.Б. Бродской, В.И. Коржика «Поиск и декодирование сложных сигналов» описывает оригинальный подход к построению быстрых преобразований, используемых для целей быстрого поиска сложных кодированных сигналов по задержке. К сожалению, описанные преобразования ограничиваются быстрыми преобразованиями Уолша и требуют существенных ресурсов для реализации.

Таким образом, актуальными являются решения таких научно-технических задач, как развитие теории кодирования, теории сигналов, а также разработка на этой основе методов и алгоритмов эффективного формирования и обработки сложных кодированных сигналов в информационно-телекоммуникационных системах рассматриваемого класса.

Научная проблема заключается в разрешении конфликта между растущим количеством абонентов информационно-телекоммуникационных систем и возможностью обеспечить их совместное функционирование с гарантированным качеством при ограничении полосы частот известными средствами построения квазиортогональных ансамблей сложных кодированных сигналов.

Объектом исследования является класс информационно-телекоммуникационных систем, включающий командные системы, асинхронные адресные системы передачи информации с кодовым уплотнением каналов (уплотнением по форме), а также системы извлечения информации, требующие использования множества сложных кодированных сигналов с гарантированными корреляционными свойствами.

Предметом исследования являются аналитические методы, модели, а также алгоритмы, развивающие теорию кодирования, теорию сигналов и их приложения для выбора ансамблей и реализации трактов формирования и обработки сложных кодированных сигналов информационно-телекоммуникационных систем рассматриваемого класса.

Цель и задачи диссертационного исследования. Целью диссертационной работы является разработка новых высокоэффективных аналитических методов и базирующихся на них алгоритмов выбора ансамблей, формирования и обработки сложных кодированных сигналов в информационно-телекоммуникационных системах рассматриваемого класса путем развития разделов теории кодирования, теории сигналов.

Для достижения цели в работе поставлены и решены следующие задачи.

1. Исследование детальных свойств числовой структуры полей Галуа, существенно влияющих на эффективность аналитических представлений полей Галуа и их использования в прикладных задачах кодирования.

2. Разработка эффективных способов отображения элементов абстрактного поля на множество элементов кодовой последовательности, а также унифицированного подхода для представления и генерирования множества примитивных многочленов заданной степени.

3. Создание базы данных и построение таблиц опорных примитивных многочленов до 63 степени.

4. Развитие векторных представлений элементов полей Галуа и разработка на этой основе метода быстрых преобразований в полях Галуа, способствующих повышению эффективности программно-аппаратных реализаций кодеков.

5. Развитие метода синтеза двухкомпонентных кодов с гарантированными уровнями взаимной корреляции.

6. Разработка метода синтеза трехкомпонентных кодов с гарантированными уровнями взаимной корреляции.

7. Разработка методов аналитического и алгоритмического определения вектора начального состояния регистра сдвига, предназначенного для быстрого скачкообразного изменения задержки кодовой последовательности в генераторах ключей и подобных устройствах кодеков.

8. Разработка методов ускоренного поиска длинных кодовых последовательностей по задержке на основе быстрых преобразований в полях Галуа.

Методы исследований. В процессе решения поставленных задач использованы принципы системного подхода и методы общей теории систем, теории чисел, теории множеств, теории матриц, теории сигналов, теории кодирования, теории радиосистем передачи информации и управления, теории телекоммуникаций.

Научная новизна результатов работы. Научная новизна заключается в развитии разделов теории кодирования, теории сигналов в направлениях теоретического и прикладного характера, расширяющих границы применения аналитических методов для синтеза сложных кодированных сигналов с гарантированными свойствами и создания оригинальных высокоэффективных программно-аппаратных средств формирования и обработки сложных кодированных сигналов применителвно к классу информационно-телекоммуникационных систем, включающему командные системы, асинхронные адресные системы передачи информации с кодовым уплотнением каналов (уплотнением по форме), а также системы извлечения информации.

При этом в диссертационной работе были получены следующие новые научные результаты:

1. Новое, модифицированное представление функции двоичного следа элементов поля Галуа, обеспечивающее построение любого минимального многочлена на основе одного опорного многочлена при формировании кодов различного типа.

2. Обобщенный метод синтеза двухкомпонентных кодов произвольной структуры с гарантированными минимальными уровнями взаимной корреляции для использования в информационно-телекоммуникационных системах, требующих увеличенного размера ансамбля кодов по сравнению с ансамблем кодов максимальной длины.

3. Алгебраическая конструкция и метод синтеза трехкомпонентных кодов с гарантированными уровнями взаимной корреляции и сверхбольшим ансамблем для использования в перспективных информационно-телекоммуникационных системах рассматриваемого класса.

4. Расширенный метод аналитического расчета максимальных уровней функций взаимной корреляции кодовых последовательностей максимальной длины с апробацией полученных результатов для быстрой предварительной оценки потенциальных возможностей выбираемого ансамбля кодов в информационно-телекоммуникационных системах рассматриваемого класса.

5. Таблицы опорных примитивных многочленов и векторов начального состояния, обеспечивающие вместе модифицированной функцией двоичного следа формирование любого примитивного многочлена до 63 степени при построении кодов различного типа.

6. Методы аналитического и алгоритмического определения вектора начального состояния генераторов для быстрого скачкообразного изменения задержки кодовой последовательности в устройствах кодеков информационно-телекоммуникационных систем рассматриваемого класса.

7. Методы ускоренного поиска кодовых последовательностей по задержке, основанные на быстрых преобразованиях в непростых полях Галуа.

На рис. 1 представлена схема вклада полученных научных результатов в решение прикладных задач.

Практическая значимость результатов работы состоит в том, что разработанные в ней модели, методы, методики и алгоритмы совместно с базами данных позволяют существенно повысить эффективность реализации и расширить область применения кодеков современных и перспективных информационно-телекоммуникационных систем рассматриваемого класса.

Реализация и внедрение результатов работы. Разработанные в диссертационной работе модели, методы и алгоритмы использованы при выполнении госбюджетной научно-исследовательской работы «Разработка математических методов и алгоритмов формирования и обработки сложных сигналов на основе М-последовательностей» по федеральной научно-технической программе «Научные исследования высшей школы по приоритетным направлениям науки и техники» подпрограмма» (подпрограмма «Информационно-телекоммуникационные технологии», раздел «Теория и техника обработки и формирования сигналов в радиотехнических системах») на 2003-2007 гг. и научно-исследовательской работы «Развитие теории и методов эффективного излучения, приема и обработки сложных кодированных сигналов», этап 16, 2009 г.

Результаты работы внедрены в учебный процесс на каф. 402 факультета радиоэлектроники летательных аппаратов МАИ при подготовке дипломированных специалистов по специальностям и направлениям подготовки 090900, 090900.5 и 090915.

Достоверность научных и практических результатов

Достоверность теоретических результатов обоснована применением адекватного математического аппарата теории чисел, теории множеств и алгебры полей Галуа, а также сопоставлением результатов с известными из литературы. Достоверность прикладных

результатов подтверждена имитационным моделированием.

Рис. 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 печатных листов.

Основные научные положения и результаты, выносимые на защиту.

1. Унифицированное исчерпывающее представление множества минимальных многочленов по заданному опорному многочлену, построенное на основе модифицированной функции двоичного следа элементов поля Галуа, обеспечивающее формирования алгебраических кодов различного типа.

2. Обобщенный метод синтеза двухкомпонентных кодов, позволяющий решить задачу выбора ансамбля путем выполнения более простых операций с кодами максимальной длины. В частности, он позволяет синтезировать наилучшие двухкомпонентные коды на основе синтеза лучших кодов максимальной длины.

3. Конструкция и метод синтеза новых трехкомпонентных кодов с гарантированными уровнями взаимной корреляции и сверхбольшим ансамблем, позволяющий решить задачу выбора ансамбля путем выполнения более простых операций с двухкомпонентными кодами. В частности, он позволяет синтезировать наилучшие трехкомпонентные коды на

основе синтеза лучших двухкомпонентных кодов для использования в перспективных информационно-телекоммуникационных системах рассматриваемого класса. Размер ансамбля кодов этого типа по меньшей мере определяется квадратом размера ансамбля двухкомпонентных кодов.

4. Метод аналитического определения границ максимальных уровней функций взаимной корреляции кодовых последовательностей максимальной длины, позволяющий быстро и точно оценить потенциальные характеристики ансамблей кодовых последовательностей, применяемых в информационно-телекоммуникационных системах рассматриваемого класса. Метод может быть распространен на оценивание границ максимальных уровней функций взаимной корреляции двух- и трехкомпонентных кодовых последовательностей.

5. Методы аналитического и алгоритмического определения вектора начального состояния генераторов, обеспечивающие быстрое произвольное изменение задержки кодовой последовательности в устройствах кодеков информационно-телекоммуникационных систем рассматриваемого класса. Производительность разработанных методов оценивается количеством элементарных операций, представляющих квадратичную функцию от степени порождающего многочлена в отличие от показательной функции для обычных методов. '

6. Метод быстрых преобразований в полях Галуа, обеспечивающий построение высокопроизводительных устройств поиска длинных кодовых последовательностей по задержке путем специального разложения исходных длинных кодовых последовательностей на совокупности более коротких фазируемых последовательностей. Результатом разложения является упрощение оборудования или уменьшение времени поиска, а результатом фазирования - накопление энергии сигнала. При использовании кодов с четной степенью порождающего многочлена длина коротких последовательностей, а следовательно и сложность декодера, уменьшается пропорционально корню квадратному из длины исходной последовательности. Теоретическое обоснование метода быстрых преобразований гарантирует возможность его применения при построении высокопроизводительных кодеков информационно-телекоммуникационных систем, использующих двух- и трехкомпонентные коды.

СОДЕРЖАНИЕ РАБОТЫ

Во введении дана краткая характеристика и структура диссертационной работы, отмечена ее особенность, состоящая в особом внимании к систематизированному изложению доказательств и выводов, составляющих математическую базу теоретико-прикладных результатов работы.

В главе 1 раскрыта область исследований, обоснована актуальность темы диссертационной работы, сформулированы ее цели.

На основе анализа структуры и назначения информационных телекоммуникационных систем выбран класс систем, обладающий общностью требований, предъявляемых к используемым в них сигналам. Показано, что эти сигналы являются сложными кодированными сигналами с большой базой и должны составлять квазиортогональные ансамбли как можно большего размера. К выделенному классу, прежде всего, относятся командные системы, асинхронные адресные системы передачи информации с кодовым уплотнением каналов, а также системы извлечения информации. Большая длина кодовых последовательностей обеспечивает надежность передачи команд и разделения каналов в командных и асинхронных адресных системах соответственно, а также точность измерения параметров сигнала в измерительных системах. Однако, достижение высоких показателей требует существенного усложнения аппаратуры кодеков, алгоритмов их программной реализации и (или) влечет за собой снижение быстродействия. Разумеется, с ростом количества команд, абонентов, различаемых объектов измерений (а это характеризует современное состояние и потребности) эти выводы еще более усугубляются.

В соответствии с выводами Э.Д. Витерби по качеству распознавания неортогональных сигналов, наиболее показательной характеристикой ансамблей сигналов является максимальный уровень корреляции рта между парами кодовых последовательностей. Отсюда становится ясно, что проектирование кодированных сигналов должно следовать минимизации уровней функций автокорреляции (ФАК) и взаимной корреляции (ФВК), которые при наличии эффекта Доплера переходят в двумерные функции ДФАК и ДФВК соответственно.

Таким образом, главными в даннй главе являются следующие результаты и выводы.

1) Наиболее требовательным к выбору ансамблей сложных кодированных сигналов является класс информационных телекоммуникационных систем, включающий командные системы, асинхронные адресные системы передачи информации с кодовым уплотнением каналов, а также системы извлечения информации.

2) Разработка методов и алгоритмов выбора квазиортогональных ансамблей сигналов, эффективного формирования и обработки сложных кодированных сигналов в информационных телекоммуникационных системах рассматриваемого класса являются актуальными научно-техническими задачами.

3) Для эффективного решения поставленных задач необходимо дальнейшее развитие теории кодирования и ее составляющих.

В главе 2 систематизированы основные положения и результаты, составляющие математические основы кодирования.

Выполнены подробные доказательства, относящиеся к применению мультипликативных функций Мёбиуса и Эйлера в прикладных задачах кодирования и редко в доступном виде встречающиеся в литературе. В частности, выполнено оригинальное доказательство и интерпретация закона обращения числовых функций, а также функции Эйлера, применяемых для анализа структуры полей Гапуа. Выполненные интерпретации использованы также при построении библиотеки алгоритмов, выполняющих вычисления в полях Галуа.

В приложениях теории чисел и алгебры полей часто приходится решать сравнения первой степени. В диссертационной работе разработан метод эффективного алгоритмического решения сравнений. Сравнение первой степени в виде ах s ¿(mod т),

представляется как эквивалентное ему уравнение

ax = b + ml, (1)

где / - пока произвольное целое число.

Для алгоритмизации поиска решения сравнения такое представление необходимо. Суть алгоритма поиска решения (1) заключается в его последовательном упрощении вплоть до получения тривиального результата. Существует два пути упрощения уравнения, выбираемых на основе анализа чисел ант:

1) если а < т, то выделяется целая часть и остаток от деления т на а;

2) если а > т, то выделяется целая часть и остаток от деления а на т.

В любом случае эти действия на i-м шаге приводят к новому, более простому (вплоть до тривиального) уравнению в виде а,х' = Ь + m,i',

где а,, т, - (возможно) новые коэффициент и модуль соответственно, получаемые в результате выделения целой части и остатка от деления либо т на а, либо а па т ;

*',/" - новые параметры уравнения, получаемые путем замены переменных и формально связанные с аналогичными параметрами, полученными на предыдущем шаге.

По завершению процесса именно эти параметры будут использованы для нахождения искомого решения путем элементарных вычислительных операций.

Подробно проанализирована мультипликативная структура поля Галуа, являющаяся основой для эффективного представления элементов поля с целью дальнейшего выполнения быстрых алгебраических преобразований. Результатом этого анализа явилась следующая система обобщений и выводов, используемая в дальнейших разделах.

Вывод 1. Корневая структура GF(p")

Поскольку все элементы поля GF(p") являются корнями многочлена хр -х,то

г"-1

хр - х = (х-Д) или, исключая нулевой элемент поля,

*"--'-1 = П(дг-Д),

i-i

где Д, Д, ! - все ненулевые элементы поля GF(p").

Вывод 2. Разложение GF(p") на неприводимые (минимальные) многочлены

Поскольку все элементы поля GF(p") являются корнями своих минимальных многочленов, то

х""-* = Пт,(х), (2)

/-i

где т,(х) - минимальный многочлен, а к - их количество в данном поле. При произвольном простом р минимальные многочлены

т^х) = х; т1(х) = 1 + х; т,(х) = 2 + х;...; m^x) = (р-1) + х степени 1 имеют корни jc = 0;x = l;jr = 2;...;x = р — 1 соответственно и тем самым принадлежат одновременно расширению поля, его подполям (если они существуют) и основному полю GF(p) .

Вывод 3. Корни минимальных многочленов

Любой минимальный многочлен т,(х) можно представить своим набором корней Д .,

т,

т.е. ш,(х) = Р1(х-Д^);ш1<и. .h

Все множество корней минимального многочлена /п((х) степени больше 1 представляется рядом элементов Д, ДУ, fif,..., pf ', поэтому

т,(*) = П (*-#'');>«,*»».

7=0

Вывод 4. Степени минимальных многочленов

Степени т, всех минимальных многочленов т,(х), включая многочлены степени 1 в поле GF(^>"), являются делителями и, причем сумма степеней всех минимальных многочленов должна быть равна

2>,=/>"- (3)

1-1

Вывод 5. Порядки корней минимальных многочленов

Порядок е, корня любого минимального многочлена т:(х) в поле С/Г(р") является делителем р" -1, причем возможны следующие варианты:

a) если степень т, минимального многочлена тДх) меньше п (при этом т, обязан быть делителем л ), то е,= р"' -1;

b) если степень т, минимального многочлена шДх) равна л и тДх) - не примитивный многочлен, то е, < р" -1 и не может быть представлен в форме е( = р* -1, где к < и;

c) если степень /и, минимального многочлена т,(.х) равна п и щ(х) - примитивный многочлен, то е{=р"~ 1, причем корень /«,(*) в этом случае является примитивным элементом поля.

Вывод 6. Количество минимальных многочленов заданной степени

Из (2), (3) следует

=£<«/„ (4)

<1\т

где т - любой делитель и (в частном случае т-п)\ суммирование ведется по всем <1 - делителям т, а М11 - количество минимальных многочленов степени с1.

Для определения количества неприводимых (минимальных) многочленов применим формулу обращения Мёбиуса

для функции

= (5)

d\m

Принимая в (5) F (cl) = dMd и G(m) = рт, приходим к (4), откуда следует

"I d\m

где Мт - количество минимальных многочленов степени m.

Формула использована в диссертационной работе для построения таблиц статистики многочленов до 63 степени включительно.

Вывод 7. Алгебраическое представление элементов поля Галуа GF(p")

Поскольку в поле GF{p") существует аддитивная группа, то каждый элемент /? поля GF(p") может быть представлен в виде линейной комбинации: Р = я„_|й"-1 +я„_2а""2 + ... + я0,

где а, - элементы GF(p), a a - примитивный элемент поля GF(p").

Отсюда следует, что при заданном a существует другое, эквивалентное представление элемента /? - в виде р-значного (в частном случае двоичного) набора (вектора размерности п )

А = (£г0,а,,...,а„.,).

На основе этих выводов выработан общий подход к анализу структуры полей Галуа произвольного порядка.

Одно из самых интересных свойств полей Галуа порядка 2" - возможность существования в них подполей (или вложенных полей) меньшего порядка 2"' ( п, < и ) при условии, что п, является делителем п. Это означает существование в поле G F (2") минимальных многочленов степени меньше п. Среди всех элементов такого поля существуют ak, являющиеся корнями минимального многочлена степени и, и имеющие порядок 2"' -1. Структура таких полей зависит от конкретных чисел п, я, и их делителей. Если исходное число п - простое, то можно точно сказать, что все минимальные многочлены имеют степень п, и в поле GF(2") вложенных полей не существует. Но при этом совсем не обязательно, что порядок корней всех минимальных многочленов равен 2" -1. Действительно, рассматривая циклическую выборку элементов поля с шагом к

„10 I 2 к ik

убеждаемся в том, что порядок элемента ак будет иметь максимальное значение 2" -1 только при выполнении условия (А,2"-1) = 1. Кроме того, можно точно сказать, что порядок элемента ак не будет иметь вид 2' -1, где I < п.

Пример выполнения анализа структуры полей Галуа

Сравним структуры полей Галуа при и = 5,6,11. Числа 5,11 являются простыми, а следовательно, все минимальные многочлены в полях будут иметь

степень 5 и 11 соответственно. На этом сходство этих полей заканчивается. Число N = 2' -1=31 является простым, поэтому минимальные многочлены будут также примитивными. Число N = 2" -1 = 2047 = 23x89 имеет два делителя, причем ни один из делителей не имеет вид 2' — 1, где 1<п. Это означает, что в поле С/г(2") подполей меньшего порядка (за исключением исходного двоичного поля коэффициентов многочленов) нет (11 - число простое). Поэтому элементы а4 при условиях, (к, 23) или (¿,89) являются корнями непримитивных многочленов, а порядки этих корней будут иметь величину 89 и 23 соответственно.

Все четные числа и имеют хотя бы два делителя, следовательно, в полях ОР(22"') всегда существуют подполя 2"') и минимальные многочлены степени и, = п / 2. Поскольку 6 = 2x3, то в поле Галуа существуют подполя ОР(21) и GF(21).

Вследствие этого элементы ак поля ОГ(26) при условии, что числа к делят числа (26-1)/(22 -1) = 21 или (26-1)/(23 -1) = 9, являются корнями минимальных многочленов степеней меньше л. Если же к делят числа 22 —1 = 3 или 23-1 = 7, то соответствующие им элементы ак будут являться корнями непримитивных многочленов степени п.

Таким образом, главными в данной главе являются следующие результаты и выводы.

1) Выполнено оригинальное доказательство и интерпретация закона обращения числовых функций, а также функции Эйлера, применяемых для анализа структуры полей Галуа. Выполненные интерпретации использованы также при построении библиотеки алгоритмов, выполняющих вычисления в полях Галуа.

2) Разработан метод эффективного алгоритмического решения сравнений первой степени, используемый в дальнейшем в главах 4 и 5 при решении прикладных задач и, в частности при разработке метода аналитического определения границ максимальных уровней функций взаимной корреляции кодовых последовательностей максимальной

длины, позволяющего быстро и точно оценить потенциальные характеристики ансамблей кодовых последовательностей и метода быстрых преобразований в полях Галуа, обеспечивающего построение высокопроизводительных устройств поиска длинных кодовых последовательностей по задержке путем специального разложения исходных длинных кодовых последовательностей на совокупности более коротких фазируемых последовательностей.

3) Выполнены обобщения и выводы по анализу тонкой структуры полей Галуа, используемые в дальнейшем в главах 4 и 5 при решении прикладных задач и, в частности, при построении библиотеки алгоритмов.

В главе 3 систематизированы линейные переключательные схемы, являющиеся одной из продуктивных моделей представления элементов поля Галуа (в векторной форме) и выполнения быстрых преобразований в полях Галуа. В частности, подробно рассмотрены схемы вычислений в полях Галуа, примеры которых приведены на следующих рисунках.

£(*)=д:3+* + 1

« Ь)

Рис. 2. Вычисление а' и а'1 в поле С.Р(23)

Используем для иллюстрации примитивный многочлен g(x) = х3 +х + \ над полем СР(2) с корнем а . Схема деления любого элемента поля О/^(23) на g(x) приведена на рис. 2.

Если в ячейку младшего разряда поместить единицу, а в остальные ячейки - нули, то последовательные сдвиги регистра в варианте схемы а) дадут представление последовательных степеней элемента а, начиная с а° = 1. В варианте схемы Ь) направление сдвига изменено, поэтому эта схема вычисляет последовательные степени а'.

Схемы вычислений степеней а и а~' могут применяться совместно, например для умножения двух элементов поля. Поместим сомножитель ак в регистр сдвига на схеме на рис. 2 а), а сомножитель а1 в регистр сдвига в схеме на рис. 2 Ь) и синхронно выполним в этих схемах сдвиг содержимого до тех пор, пока в схеме на рис. 26) не появится представление а" = 1. Ясно, что это произойдет через / тактов работы обеих схем, вследствие чего в схеме на рис. 2 а) появится представление элемента ак*'. Те же схемы можно использовать и для поиска элемента, обратного заданному элементу а*. Для этого

запишем представление элемента ак в регистр сдвига схемы на рис. 2а), а представление а" = 1 - в регистр сдвига схемы на рис. 26). Произведем синхронно сдвиги до тех пор, пока в регистре сдвига схемы на рис. 2 а) не появится представление а0 = 1. Ясно, что это произойдет через 2"-1 -к тактов и в регистре сдвига схемы на рис. 26) появится

представление элемента а2 = а'к, т.е. обратного элементу ак. Приведенная схема по существу является обощенной схемой вычисления в полях Галуа.

Найден способ краткого векторного описания схемы деления на заданный многочлен, являющейся основой для векторных вычислений в полях Галуа и построения декодеров. Пример исходной схемы показан на рис. 3.

X6 =1 + Х3 +Х4 +Х5 10 Выход

т

тт

«Фмпивныйг» разряд

Вход Ф Ф Ф Ф © ф . Н

1 Ж ж 1 А

..Т Выход

Рис. 3. Схема для деления на многочлен #(*) = х6 + х* + х* + х3 +1.

Алгоритм работы схемы в каждом такте можно выразить выражением

в|+|=(А(+|ег>;_,с')®(в.->), (6)

где В,, Вм - двоичные вектора содержимого регистра сдвига в <-м и / +1 -м тактах работы схемы соответственно;

В, -> - означает «чистый», т.е. без учета воздействия обратной связи, сдвиг В| вправо;

Ам = [ам, 0,..., 0} - двоичный вектор входных данных;

Ъ\_х - содержимое старшего разряда регистра сдвига в / -м такте работы;

в* - векторное представление выражения g(x) + дс6 = х5 + х* + х3 +1.

Смысл выражения (6) становится более понятным, если добавить к схеме на рис. 3 дополнительный «фиктивный» разряд (он маркирован штриховой окантовкой), никак не влияющий на работу схемы. Тогда (6) полезно преобразовать к виду

Вм=(АтФ(в|-^))Фб;с,

где в - векторное представление выражения многочлена g(x) = х6 + хь + х* + х3 +1. В этом алгоритме сначала выполняется операция А|+, © (В, —>), означающая сдвиг содержимого регистра сдвига вправо с замещением младшего разряда новым значением а(+|. При этом в дополнительном разряде появляется значение Ь'г, которое при Ь'г = 1

формирует цепь обратной связи (показана штриховой линией) в виде векторного представления многочлена g(x). Вектор G, суммируясь с новым содержимым регистра сдвига, формирует выходной сигнал схемы (показан штриховой линией). При таком представлении схема вычисляет значение текущего остатка по модулю многочлена g(x). Эта модель использована в диссертационной работе для алгоритмической генерации элементов поля Галуа.

Таким образом, главными в данной главе являются следующие результаты и выводы.

1) Разработана обобщенная схема вычислений в полях Галуа на ЛПС.

2) Разработана векторная модель вычислений в полях Галуа, использованная для алгоритмизации вычислений в полях Галуа.

В главе 4 выполнен детальный анализ поля Галуа и его элементов, проанализированы варианты эффективного, с точки зрения решения разнообразных прикладных задач, представления элементов поля Галуа, методы их отображения на элементы кодовой последовательности, методы построения минимальных многочленов, а также сформулирована идея и приведено математическое обоснование быстрых преобразований в полях Галуа.

Решение большинства практических задач кодирования связано с построением и обработкой упорядоченных множеств элементов, т.е. множеств элементов, перечисляемых по определенному правилу. Найдено полезная для алгоритмических вычислений связь между элементами поля Галуа и элементами числового поля по простому модулю.

Доказано, что подмножество из первых М = ^^—— степеней первообразного корня g

п

по простому модулю р" -1 содержит по одному числу, представляющему степень корня каждого из примитивных многочленов, существующих в поле GF(p"), т.е. подмножество чисел g°, g, g2,..., gM_l по модулю р" — 1 является подмножеством чисел, являющихся степенями следующего подмножества элементов абстрактного поля GF(p"):

or1', а*', а4',..., ак" , где а - примитивный элемент, a ft, = g1'1 (mod р" -1), причем к1 не является решением сравнения ft = kf' (mod р" -1) ни при каких 1 < i < М\ 1 < j < п -1.

Практическое значение заключается в том, что для определения соответствующего примитивного многочлена достаточно знать лишь один из его корней.

В главе 2 определено алгебраически полное, но неоднозначное соответствие между элементами поля Галуа CF(p") и всеми минимальными многочленами степени п и менее. Причина неоднозначности - абстрактный характер поля Галуа и невозможность

явного представления корней минимальных многочленов. Это не является ограничением для решения теоретических задач, однако создает определенные трудности для практики кодирования. Действительно, доказать, что корнем минимального многочлена f(x) = \ + x + x4 в GF(2") является корень а, а не а1, невозможно. Однозначное соответствие может быть дано только в случае четкого указания хотя бы одного минимального примитивного многочлена, например /¡(х), и его корня а . 13се остальные соответствия после этой договоренности уже становятся однозначными. Следствием этой договоренности является создание разными авторами таблиц минимальных многочленов. Хотя, в целом, выбор f,(x) следует определенному правилу - выбирается многочлен с минимальным количеством ненулевых коэффициентов, причем предпочтение отдается ненулевым «оэффициентам при меньшей степени х - разночтения все-таки существуют.

Существует и другая проблема. На тот момент времени, когда таблицы многочленов (см. Берлекэмп Э. Алгебраическая теория кодирования. - М.: Мир, 1971) формировались, эффективная цифровая техника только создавалась, да и потребности практики были не сопоставимы с сегодняшними. Современное положение вещей таково, что в сложных информационных системах, использующих помехоустойчивое кодирование и шифрование данных, стремятся выбирать многочлены более сложной структуры, т.е. с большим количеством ненулевых коэффициентов и с большей степенью. Такие многочлены в указанных таблицах, скорее всего, отсутствуют.

Наконец, нельзя не считаться и с такой проблемой практического свойства, как длинные записи многочленов и их степеней.

Современный подход к устранению или хотя бы к минимизации возможных конфликтов состоит следующем. Во-первых, таблицы многочленов в той или иной форме следует хранить в базах данных, что обеспечивает целостность и высокую скорость извлечения данных . Во-вторых, возможно, более эффективно регенерировать требуемый многочлен на основе /(*), что приводит к необходимости хранения только f}(x) для каждой степени и. Следуя этому подходу, в диссертационной работе создана база данных и сгенерированы таблицы опорных примитивных многочленов до 63 включительно.

Отдельными проблемами теории и практики кодирования является отображение элементов абстрактного поля Галуа на элементы (например, двоичные) кодовой последовательности и построение минимальных многочленов для конструирования разнообразных кодов.

Обычно отображение элементов поля Галуа на элементы кодовой последовательности дается так называемой функцией двоичного следа

Однако, в диссертации показано, что формальное определение любого минимального многочлена степени т <, п опирается не на эту функцию, а на функцию

Я1 —I

Г,.. (Л =

<•0

которая совпадает с (7) только при т = п.

В противном случае между двумя функциями устанавливается следующая связь

я/лт

Имея в виду смысл и полезность функции Трт(Р), в работе введено ее определение. Под Трт(Р) при т<п понимается след корпя р многочлена /(х) степени т<п в основном поле СР(р). Это определение названо модифицированной функцией двоичного следа (МФДС) в отличие от стандартной функции двоичного следа (СФДС) в виде Тр(Р). На основе этой функции получены соотношения для произвольного минимального многочлена /к(х) степени т при заданном значении к:

.=0 ^ИЧ^.Л-!

, где р = ак\ (к, 2"-1) = 1;

к|( - лидеры всех смежных классов по подгруппе Н = {1,2,..., 2""'}, имеющие одинаковый вес иг=п-\\

1У(к{1) - функция, возвращающая двоичный вес числа к^.

В этой главе также найдена ассоциация функции следа с аналогичным по названию формальной функции матрицы (след матрицы). Доказано, что функция Тт(р1) непосредственно связывается с общепринятым понятием следа /г( А) матрицы А вида

Р" 0 0 р"

0 0 ••• Р"~ для которой построен характеристический многочлен с(х) вида Р-х 0 0

с(х) = с!е1

0

0 0 ••• р^'-х При этом справедливо с(х) = т(х).

На основе этих результатов разработана высокоэффективная алгебраическая библиотека, позволяющая быстро найти любой минимальный многочлен заданной степени по известному /Х(х) и числовому значению к. Эти результаты являются существенным вкладом в теорию и практику кодирования.

Дальнейший материал главы 4 развивает векторные представления элементов полей Галуа.

Первым введено векторное представление, основанное на содержимом регистра сдвига. В этом варианте представления каждому элементу а' ставится в соответствие не его двоичный след Т(а'), а следующий двоичный вектор

А1 размерности и, где а(4; =Т(а'*у).

Данной представление выделяется тем, что четко указывает на однозначность интерпретации исходного или начального состояния регистра сдвига: «нулевое»

состояние определяется вектором А0 =(а0,а...... ая_,). Кроме того, данное представление

дает возможность алгоритмически решать уравнения

а' + а' = а"', заменяя его уравнением А, + А) = Ат).

Решение заключается в поиске такого количества последовательных сдвигов т^, при котором регистр сдвига содержал бы двоичный вектор А^. Отметим, что первые п векторов А„, А,,..., Ап_, являются линейно независимыми, поскольку в противном случае многочлен, корнем которого является а , не был бы примитивным. Это дает возможность единственным способом представить любой вектор, например А^, в виде линейной комбинации множества линейно независимых векторов:

Ап=•

(=0

где Ь" - двоичные коэффициенты, которые, в общем виде пока не могут быть найдены.

В работе найден метод представления любого вектора через линейно независимую систему векторов. Пусть известно решение алгебраического уравнения

1 + а = а',

Из этих соотношений следует

(8)

1-0

где к - любое целое число по модулю N = 2"

О,

24 ¡ = 0;

Л, - коэффициенты многочлена И(х), корнем которого является а .

Иными словами, (8) дает представление любого вектора через линейно независимую систему векторов, если т + кI при любом целом к пробегает полную систему вычетов по модулю N = 2" - Поскольку выбор значения т' совершенно произволен, то достаточно выполнения условия (т\ М) = 1. Полученный результат является аналитическим и в математическом смысле привлекательным, однако практическое его использование, конечно же, связано с построением вычислительного алгоритма.

Второе векторное представление основано на схеме деления многочленов (схема декодера), представленной на рис. 4.

Обратная связь

Рис. 4. Схема для вычисления а' по модулю примитивного многочлена Дальнейший материал главы посвящен проработке новой идеи быстрых преобразований в полях Галуа. Возможность построения быстрых преобразований в

полях Галуа существует при наличии в поле С/г(2") подполей ), где пк - один

из делителей числа п. Если какой-либо элемент а1 6 ОР(2") является одновременно примитивным элементом подполя (7/^(2"'), то все степени этого элемента

аи е С-Р(2"'), I = 0,2"' - 2, по определению, пробегают все ненулевые элементы этого подполя. Это означает, что в полях, обладающих указанными свойствами, существует возможность разложения элементов поля 2") по элементам подполей 6/^(2"'). Математически эта операция соответствует разложению поля на смежные классы по подгруппе, представляющей собой элементы подполя О/'Х2"'). Если рассматривать кодовую последовательность как временную последовательность символов, то выборки символов исходной М-последовательности длиной N = 2" — 1, взятые с шагом Ь = (2" — 1)/ (2"' -1), являются символами некоторой «короткой» последовательности

длиной Nк = 2"' -1 (в специальной литературе часто такие преобразования называют децимациями). Поскольку начальный номер символа исходной М-последовательности, с которого начинается выборка, может быть произвольным, то в результате взятия всех возможных выборок формируется совокупность «коротких» последовательностей

¿>((1Х + у')гц), у = 0,£-1 одинаковой длины Ык=2п> -1. Этот процесс демонстрируется на рис. 5.

Показывается, что все «короткие» последовательности являются М-последователыюстями той же самой длины и структуры, но с различными взаимными сдвигами. Свойства рассматриваемых преобразований существенным образом зависят от структуры конкретных полей Галуа, поэтому в качестве примера рассмотрим случай

22р-1 (2"-1)(2"+1)

п = 2р\ пк = р\ = 2Р -1, I = ——- = --- = 2Р + \, т.е. рассматривается вариант

разложения исходной М-последовательности на совокупность «коротких» М-последовательностей длиной Ы,=2Р - I. Совокупность «коротких» последовательностей можно записать в виде

6((2" +1)1 + } + г), / = 0,2" - 2, у = 0,2",

а т - неизвестный начальный сдвиг (задержка) исходной кодовой последовательности. Символы этой последовательности как функции целочисленного / могут быть описаны как отображение элементов подполя GF(2') в двоичное поле йР(2) с помощью функции двоичного следа. Параметром каждой последовательности, характеризующим смещение при взятии выборки, будет являться индекс j. Он же, совместно с г , будет определять относительный сдвиг каждой «короткой» последовательности с номером у. По определению двоичный след любого элемента поля равен

Учитывая, что 2" (2" +1) з 2" +1 (mod 22" -1),

сгруппируем члены с одинаковыми множителями при дискретной переменной i

Г(ог(2'+п,+^r) = at12'*"' (a'+r + а1'и"'>) +

+a2(2'.l),(a^r+a2'(/tr))2+ + (9)

На этом этапе можно сделать следующие выводы.

1. Число членов в (9) равно р, а не 2р, как это должно быть в выражении для двоичного следа элемента в поле характеристики 2р, что указывает на то, что фактически получен след элемента подполя GF{2я) в GF(2).

2. Элемент у = а'*' +a7'u") является элементом подполя GF(2P), поскольку

(aJ" +a2'('"Y =aJ" + a"(/"> и у*т=у^,.

3. Элемент af2'*n = у является элементом подполя GF(2P), поскольку у2' - у.

Таким образом, получим

Па»'^") = Тр{у%г), (10)

где запись Тр(.) трактуется как двоичный след элемента подполя GF(2P). Из (10) видно, что представленный след действительно является ;-м символом «короткой» М-последовательности, полученной в результате взятия выборки из исходной последовательности с шагом 2' +1 и смещением j относительно «алгебраического» нуля. Все сказанное справедливо, если j + (mod 2'' +1). В противном случае а'*' = а2'и*'\ yJtr = 0 и все символы получаемой «короткой» последовательности равны 0, т.е. х(аа'*[)"'") = 0 или, при использовании представления символов в виде симметричных уровней,

s ia{Vtlv*JtT) = +l. Этот случай соответствует формированию «вырожденной» последовательности, состоящей из всех +1.

Идея быстрых преобразований состоит в фазировании всех «коротких» М-последовательностей кроме вырожденной и накоплении энерши символов на каждой позиции i. В результате накопления получается одна «короткая» М-последовательность длиной 2Р символов, но с возросшей в 2Р раз энергией в одном символе. Очевидно, что обработка такой последовательности обычным коррелятором или согласованным фильтром может быть выполнена в 2Р +1 раз быстрее, чем исходной. Энергию, содержащуюся в 2Р-] символах «вырожденной» последовательности, можно учесть,

выполняя отдельное накопление ее символов и добавляя этот результат к полному результату корреляционной обработки «короткой» М-последовательности. Структурные схемы вариантов трастов обработки, реализующих описанную идею, подробно рассмотрены в главе 5.

Таким образом, главными в данной главе являются следующие результаты и выводы.

1) На основе понятия первообразного корня разработан аналитический способ перечисления необходимого и достаточного множества корней всех примитивных многочленов в простом поле Галуа.

2) Разработан метод перечисления в заданном поле Галуа всех минимальных многочленов по заданному опорному многочлену.

3) Сгенерирована таблица опорных многочленов до степени 63 включительно.

4) Введена модифицированная функция двоичного следа (МФДС), установлена ее связь со стандартной функцией двоичного следа (СФДС). Разработана методика применения МФДС для генерации минимальных многочленов и СФДС - для отображения элементов поля Галуа на элементы двоичного кода.

5) Установлена связь МФДС с двоичным следом специальной характеристической матрицы, составленной из корней многочлена.

6) Разработаны векторные представления элементов поля Галуа для их эффективного перечисления с помощью ЛПС и построения эффективных вычислительных схем в полях Галуа.

7) Выполнено математическое обоснование построения быстрых преобразований в полях Галуа.

В главе 5 выполнено решение ряда прикладных задач кодирования в информационных телекоммуникационных системах рассматриваемого класса алгебраическими методами, полученными в диссертационной работе.

Решаемые прикладные задачи разделены на два класса:

- синтез квазиортогональных ансамблей кодовых последовательностей;

- синтез эффективных устройств кодирования и декодирования.

Эти задачи в наибольшей степени отвечают поставленной в работе цели. В качестве объекта синтеза квазиортогональных ансамблей сигналов выбран класс кодовых последовательностей, включающий коды максимальной длины и составные коды, построенные на их основе - двух- и трехкомпонентные составные коды. Такой выбор обусловлен следующими соображениями.

Во-первых, эти коды - алебраические и к ним применимы результаты, получепные в предыдущих разделах работы, а следовательно можно было достаточно легко получить оценку эффективности использования этих результатов.

Во-вторых, выбранный класс кодов, исключая трехкомпонентные составные коды, широко применяется в информационн-телекоммуникационных системах выбранного класса, а следовательно можно было достаточно легко оценить область и варианты использования результатов, полученных в предыдущих разделах работы.

При решении поставленных задач использована следующая формальная модель ФВК:

где г - сдвиг первой М-последовательности относительно своего «нулевого» начального состояния,

а число к удовлетворяет условию (к, Щ = 1 и описывает структуру второго кода.

На основе этого определения найдены основные свойства ФВК кодов максимальной длины, существенно расширяющие границы знаний о них.

Основные свойства ФВК кодов максимальной длины

1. Свойство ФВК при сдвигах из одного смежного класса

Определим ФВК при всех сдвигах вида т1',} =0,1,...,и-1, принадлежащих одному смежному классу по мультипликативной подгруппе Н = {1,2,4,...,2"~1}. С учетом свойства

5(дс2') = , получим

вк (т2') = § )5(а" ) = ) = вк (г).

|>0 1-0

Этот результат означает, что при расчетах ФВК исчерпывающим множеством всех возможных сдвигов х является подмножество лидеров смежных классов, что существенно сокращает затраты вычислительного времени.

2. Свойство ФВК эквивалентных пар кодовых последовательностей

Рассмотрим теперь ФВК последовательностей, порождающие многочлены которых имеют корнями Д = а1 и рк, т.е.

1.0 1=0

откуда путем замены переменных ¡1 =>получим

в,{т) = ва{г1).

Этот результат позволяет существенно сократить число перебираемых пар М-последовательностей при расчете ФВК, поскольку полпый перебор оказывается избыточным. Доказанное свойство ФВК позволяет точно отобразить значения ФВК любой пары кодовых последовательностей на значения ФВК другой пары, в которой первая («опорная») последовательность всегда фиксирована (например, порождается многочленом с корнем а ).

3. Свойство ФВК симметричных пар кодовых последовательностей

Взяв за основу предыдущее свойство, рассмотрим ФВК М-последовательностей при условии _ № е 2' mod N. Числа l,k имеют тот же смысл, что и в предыдущем пункте, а число j - произвольно в диапазоне от 0 до п-1. С учетом свойства S(x1') = S(x), получим

¡«0 («О 1=о

Объединив данное свойство с предыдущим, получим результат

e„{t)=ea>{ti)=eaj(-t),

который показывает, что в множестве пар последовательностей, определенных в свойством 2, остаются пары последовательностей (назовем их симметричными), ФВК которых взаимно отображаются друг на друга, причем эти пары заранее известны и строго подчиняются правилу Ik н 2' mod N.

4. Свойство суммы значений ФВК

N-l N-1 МЛ

г-0 (-О г-0

При выводе результата учтено, что сумма всех значений символов М-последоввтельности любой структуры равпа -1.

5. Свойство суммы квадратов значений ФВК

£ * V) = IW) +1)2 - 2 ~ JV, где

г-0 т-0

х х ж**+/)§$(«•<*+jo).

r-0 icGHl'ifCFO') "О

Выполняя суммирование, получим

г "О

Свойства 4 и 5 могут быть иснользоваяы для моделирования уровней ФВК случайным процессом с гауссовским распределением. Кроме того, они используются в построении методов синтеза квазиортогональных ансамблей сигналов.

Далее в главе выполнен полный синтез ансамблей М-последовательностей с тремя уровнями ФВК.

Полный синтез ансамблей М-последовательностей с тремя уровнями ФВК

Первоначально такой ансамбль был синтезирован Р.Голдом для нечетных значений л степени многочлена. Распределение уровней ФВК имеет вид

( О, Т{сГ) = 0, 2я"'-1 +2("п'\ Г(а') = 1, 2"~2 +2("'3),г. _2<«*1)п Т(а') = 1 2"~2 —

В диссертационной работе выполнен полный синтез ансамблей для четного п. Его результатом является распределение уровней в виде

Ч Т(а') = 1; Т(а') = 0, а' = Д* + Дг', Ма вк (т)+1 = +2("*1)л, Т(а') = 0, а' = 1 ■+ Д2" + Дг', М. , -2<"*т, Т{а') = 0, аг = 1 + Д/ + Д2', Ы.

где М„ = 2Л"' + 2""2 -1; М, = 2"'1 + и М. = 2""5 - г'"""'2.

Записи в соотношениях приведены в форме «значение уровня, условия, количество уровней». Как видно, отличительными особенностями ФВК для четных и являются: - несколько большее (в -у/2 раз) значение максимальных уровней ФВК; -большее (приблизительно в 1,5 раза) количество уровней -1.

Вторая особенность в ряде случаев оказывается востребованной на практике, поскольку по сравнению с нечетным и вероятность появления высокого уровпя взаимной корреляции уменьшается приблизительно вдвое.

Далее выполнен обобщенный синтез двухкомпонентных составных кодов с гарантированными уровнями ФАК и ФВК.

Обобщенный синтез двухкомпонентных составных кодов с гарантированными уровнями ФАК и ФВК

Двухкомпонентные коды с наилучшими характеристиками в смысле распределения и значения максимальных уровней, а также размера ансамбля впервые синтезированы Р.Голдом. Однако им не были выполнены все необходимые доказательства и не были найдены все последовательности с указанными свойствами.

Двухкомпонентные коды предназначены для формирования квазиортогональных ансамблей большого размера. Полный размер ансамбля в классе кодов максимальной

длины N = 2П -\ равен , если допускается использование циклических

и

сдвигов, Мли М1 = ^ - в противном случае, где <р(№) - функция Эйлера, и

Для последовательностей Голда полный размер ансамбля составляет Мю = и

Мго = Л(1<Г)М, соответственно, где Д(ЛГ) - количество различных пар кодовых последовательностей максимальной длины, составляющих классические коды Голда. Для вычислений ФАК используется алгебраическая модель

дм

01л № = £(1+)+<Л1 + О),

где г - целочисленный сдвиг М-последовательности структуры 1, Я*О - аргумент корреляционной функции вл (1), а индекс «Л» идентифицирует ФАК. В результате преобразований получается соотношение, связывающее значения ФАК двухкомпонентного кода со значениями ФВК кодов максимальной длины, составляющих двухкомпонентный код, т.е.

= гДе значения у0(Я), у,(А) удовлетворяют соотношениям

Разумеется, при нулевом аргументе ФАК достигает своего максимального значения 01Л(О) = N .Данный вывод справедлив для любого значения к.

Для вычислений ФВК использована следующая алгебраическая модель

н-1 .

= + )). гДе г1>Тг~ целочисленные сдвиги М-

1-0

последовательностей структуры 1 при формировании различных двухкомпонентных последовательностей; Я - аргумент ФВК, а индекс «См идентифицирует взаимно-

корреляционную функцию. При этом варианты г, = г3 не могут рассматриваться, иначе ФВК вырождается в ФАК.

Принимая следующие обозначения (при т, +Л*г2;Л*0) аг,*л + а'1 = а"'(л,'1,',>\ 1 + ал , получим 02С(Л) = в(уа(Л,т1,т1)-и,(Л)).

Таким образом, и в7С{Л) приводится к значениям ФВК исходных М-последовательностей. Данный вывод также справедлив для любого значения к.

Различия в результирующих соотношениях состоят в том, что элемент а"•(д',|''>) при некоторых г,,г2 * г, может быть нулевым элементом поля, что приводит к особой форме выражения для функции взаимной корреляции.

В зависимости от значения Л и соотношения между г, и г3 значения ФВК двухкомпонентных кодов в особых точках могут приводиться к значениям боковых выбросов ФАК. Рассмотрим эти две особые точки. Они определяются условиями г, + Я = г2; А ^ 0 и г, * г2; /I = 0 соответственно. Анализ показал, что значения ФВК двухкомпонентных кодов в этих точках равны -1. В остальных точках значения ФАК и ФВК двухкомпонентных кодов принадлежат одному и тому же множеству.

Таким образом, первый этап синтеза квазиортогональных кодов завершен со следующими результатами:

1) вне зависимости от значения к значения ФАК при Л ф 0 и ФВК двухкомпонентных кодов принадлежат одному и тому же множеству значений;

2) эти значения исчерпываются значениями ФВК исходных М-последовательностей;

3) в особых точках значения ФВК двухкомпонентных кодов равны -1.

Эти результаты, в частности, сразу же определяют наилучшие возможные (с точки зрения максимальных боковых уровней ФАК и ФВК) двухкомпонентные коды, получаемые на основе исходных М-последовательпостей с трехуровневой ФВК, описанных выше.

Второй этап синтеза - нахождение распределения уровней ФАК и ФВК двухкомпонентных кодов - выполним при условиях, наиболее благоприятных для получения квазиортогональных ансамблей, то есть при условиях существования трехуровневых ФВК исходных компонентов.

Так же как и для кодов максимальной длины сначала были найдены основные свойства ФАК и ФВК двухкомпонентных кодов.

1. Свойство суммы значений ФАК

Д.О "О ЛоО

Учитывая трехуровневый характер ФВК исходных компонентов, получим

Х(02,(Л) +1) = (0т„ + -М.), где

■ы

+1 - максимальное положительное значение уровня модифицированной ФВК для последовательностей с трехуровневой ФВК, а Л/,, М_ - означают количество положительных и отрицательных уровней ФАК при Я * 0 соответственно.

2. Свойство суммы квадратов ФАК

Л-1

Поскольку трехуровневый характер ФВК исходных компонентов сохраняется, то необходимо найти количество положительных и отрицательных уровней +1 аналогично выводу свойства 1. Это соотношение удобно рассмотреть в форме

+ =К„+1)1К + где

М^+М

N + 1 в.к(т) + \ /, г.ч

+—--(I-5(а )),п-нечетпные

N + 1 вАт) +1 .

--1—!--2, п - четные

4 4

Отсюда следует, что для получения наилучшей формы ФАК двухкомпонентных последовательностей с наименьшим количеством ненулевых уровней ФАК при Я * О необходимо подобрать такое значение г, чтобы достичь максимального отрицательного значения функции . Однако с ростом п получаемый выигрыш уменьшается.

Полученные результаты достаточны для определения распределения уровней ФАК при Я Ф 0, которое в общем виде имеет вид:

02„(Л) + 1 =

О, Л/0

К .гДе -(^„+0, М-

01)

N-2 в_к(г) + \

2 2 3(ЛГ + 1) (9_Дт) + 1

+ (1 - г)), п- нечетные

п-четные

M _Af + l | g.t(r)+l 1 -S(a')

'{0(T) + \f g(f)+l 2(0m„+l) fm„+l

(g(r) + l)2 gfr) + l

Л

для нечетных n;

M = M =-+ *--1 для четных n.

8 8

Аналогичные свойства ФВК двухкомпонентных кодов выглядят так.

1. Свойство суммы значений ФВК

= +a*) = 0(r,)í>(r2).

Л.О »О .1-0

Учитывая трехуровневый характер ФВК, перепишем полученный результат в виде № + !) = +где

д.о

.. .. Af + l + (g(r,) + 1)(g(r2) + l)-(g(T,) + l)-(g(r2) + l)

М -М =-i—--——---—i—1--—*—í-а - количество

+1 "

шал

положительных и отрицательных уровней ФВК соответственно.

2. Свойство суммы квадратов ФВК

S или Х(Й2С(1)+1)2 = +

где М + М +1)'.

К.,+1)

Распределение уровней ФВК определяется в форме, аналогичной (11): 0, Мй

в1С(Я) +1 = - в^ +1, Мл , где значения определяются следующим

-(^ + 1), М

образом М,

N+1 +1

= 2"-2+2("-wí;

2^+lJ 2 - 2^+lJ 2 0mtt+\

= 2"' -1 для нечетных п, что полностью совпадает с

Л.+»,

распределением уровней ФВК М-последовательностей для нечетных и, полученным ранее.

Анализ распределения ФВК двухкомпонентных кодов для случая четных п дает следующий результат

21(9+1) 2 вт„ +1

\ 1Ш / (ОЯН

= и ы+1

21^+1

. 1. ^ + ^ _ 2"'1 _ 2(п"4)'2 ■

' 2 0т„ +1 ГЛкХ

м„ = ы -

' N+1 42

= 2" -1-2"'

что также полностью совпадает с распределением уровней ФВК М-последовательностей для четных п, полученным ранее.

С целью расширения границ и областей использования алгебраических кодов в диссертационной работе предложена модель и выполнен синтез трехкомпонентных кодов.

Синтез трехкомпонентных составных кодов с гарантированными уровнями ФАК и ФВК

Полный размер ансамбля в классе кодов максимальной длины N = 2" - \ равен

»у хг «у РМ

М, = ——- N, если допускается использование циклических сдвигов, или Мг = ——- - в

п п

противном случае, где <р{И) - функция Эйлера.

Для последовательностей Голда полный размер ансамбля при тех же условиях составляет Мп = и Мп = Л(Л')Л', соответственно, где Л(Л0 - количество

различных пар кодовых последовательностей максимальной длины, составляющих классические коды Голда.

Для трехкомпонентных составных кодов полный размер ансамбля при тех же условиях составляет и Мп = , соответственно, где - количество

различных пар кодовых последовательностей максимальной длины, составляющих трехкомпонентные коды.

На рис. 6 приведена конструкция трехкомпонентных кодов в виде обобщенной структурной схемы формирователя, где МО 1 - генератор М-последователыюсти

структуры 1; МО 2 - генератор М-последовательности структуры 2; МС 3 - генератор М-последовательности структуры 3; С, (х) - блок линейного суммирования первых п сдвигов М-последовательности структуры 1 для получения М-последовательности с произвольным сдвигом г; 02(л) - блок линейного суммирования первых п сдвигов М-послсдовательности структуры 2 для получения М-последовательности с произвольным сдвигом е\ Ф - блок сумматоров по модулю два; /¡(; + г) = Г(а'"); Р2(/ + е) = Г(а('+1)*'); Р,(«) = Т(а>'); Рг(¿,т,е) = Т(а"')+Т(а°")к')+Т(а*>).

Рис. 6. Обобщенная структурная схема формирователя трехкомпонентных кодовых последовательностей

Перечислим условия, при которых проводится анализ характеристик корреляционных функций:

а, (О = <р{Р^)) = ; о, (0 = *(Р2(0) = ); а3(/) = р(Р3(/)) = 5(а""); а10',т,£) = <г»(?1.(/,г,е)) = 5(в,"+а</">''+в"'); Л, = 2'1 +1; А, = 2'1 +1; £(•) преобразование аддитивной группы двоичных элементов (0, 1) в мультипликативную группу (+1, -1), а числа /,,/2 удовлетворяют условиям (/,,л) = 1;(/2,и) = 1,/, *1г. Иными словами, числа /„ /2 не должны иметь общих делителей с числом п.

Для расчетов использованы следующие алгебраические модели:

= = + (12) 1=0 <-0

для расчета ФАК, г де г, с - целочисленные сдвиги М-последовательностей структуры 1 и 2, а X* 0 - аргумент корреляционной функции 6>]Л(А); индекс 3 является признаком трехкомпонентного кода, а индекс «А» идентифицирует ФАК; 1 + ад = а"", \ + ахк] - а"**', ] + /' = а"1*1 и

для расчета ФВК, где г,, ер г2, г2- целочисленные сдвиги М-последовательностей структуры 1 и 2 при формировании различных трехкомпонентных последовательностей; Я - аргумент ФВК, а индекс «С» идентифицирует ФВК; а'1*' +а'' =

+а-л 1+ аи' = а"{Л)к>. При этом варианты г, = г2, с, = е2 не могут

рассматриваться совместно, иначе ФВК вырождается в ФАК.

Различия в результирующих соотношениях состоят в том, что элементы ,

а"<д,£"Г1и' при произвольных т1,т2,е1,е2 могут быть нулевыми элементами поля, что приводит к особым формам выражений для функций взаимной корреляции.

В зависимости от значений соотношений между г, и г2, е, и е2 значения ФВК трехкомпонентных кодов в особых точках могут приводиться к значениям ФВК двухкомпонентных кодов или значениям боковых выбросов ФАК. Эти особые точки рассмотриваются отдельно. В остальных точках, как видно из сопоставления выражений, значения ФАК и ФВК трехкомпонентных кодов принадлежат одному и тому же множеству. Поскольку при синтезе квазиортогональных кодов наиболее важными показателями корреляционных функций являются их максимальные значения, а не распределение, то в дальнейшем анализируется выражение (12) при Я* 0 как более простое, а индекс, идентифицирующий ФАК и ФВК, опускается. Выражение (12) удается привести в виду

0, (Я, г, е) +1 = 5 [ра* + {ра* )*' + {рау> )*' ][б, (А, тр, е) +1 ] (13)

для любого элемента поля р, откуда следует, что для фиксированного набора Л, г, г для любого Р с условием а* + ^(Л»^) * ® • где

ГМ^-Р*"1* +рг'аг',,"к'+р1Ьа"к' +р2"аг"^' =

= а"> [(/&*"> )2" + (Ра)г" ] + а"' [(Ра"' )2" + (ра" )г" ]

ФВК в3(Я,т,е) +1 отображается на любое значение ±[бДЛ,г/,,£) + 1], где тр пробегает все возможные значения (см. рис. 7).

Рис. 7. Пояснение соотношения (13)

Данный вывод означает одно из двух событий: либо значения в2{Лугр,е) + \ = 0 при всех тр и, следовательно, 0)(Л,г,е) + \ = 0 (рис. 7а), либо для данного набора Л,т,е введенное предположение неверно и удается подобрать Р с условием а"' + = О,

так что значение в}(Л,т,е) +1 отображается на значение ±[в1(Л,е) + \] (рис. 7Ь), где

03(Л,£-) +1= £ 5[х'|а(г+"|)'1 ч-х^'а"'*1] - ФВК второй и третьей компонентов составной последовательности.

Выводы по результатам синтеза

1. Уровни ФВК, так же как и боковые уровни ФАК рассматриваемых трсхкомпонентных последовательностей, в результате синтеза либо определены явно,

либо отображены на соответствующие уровни ФВК двухкомпонентных кодовых последовательностей, аналогичных последовательностям Голда.

2. Уровни ФВК, так же как и боковые уровни ФАК рассматриваемых трехкомпонентных последовательностей, могут отображаться на уровни ФВК двухкомпонентных кодовых последовательностей, составленных из всех возможных трех пар кодовых последовательностей, составляющих трехкомпонентный код. При этом в двух из трех сочетаний пар отображение происходит на уровни, известные из синтеза двухкомпонентных кодов.

3. В тех случаях, когда отображение уровней ФВК, так же как и боковых уровней ФАК рассматриваемых трехкомпонентных последовательностей, происходит на уровни ФВК двухкомпонентных кодовых последовательностей, составленных из второго и третьего компонентов трехкомпонентных последовательностей, значения этих уровней не определяются точно как результат данного синтеза. Это означает, что дополнительным этапом полного синтеза является основанный на расчете ФВК правильный выбор указанных компонентов трехкомпонентных последовательностей. Иными словами, данный случай сводится к синтезу двухкомпонентных кодов заданного типа.

Аналитическое оценивание ФВК

Другим полезным обоснованием выбора квазиортогональных ансамблей кодовых последовательностей является аналитическое оценивание ФВК. В работе эта задача решена для кодов максимальной длины, порождаемых многочленами четных степеней. Для них ФВК приводится к виду

вк (г) = )S{a'k) = 2"(М -1) -1, (14)

/-о

где к - число, определяющее структуру коррелируемой последовательности, причем (k,N) = 1 и к = 1 (mod (2я -1)); г - параметр задержки второй последовательности относительно «алгебраического нуля» или аргумент ФВК; М - число решений уравнения

(15)

относительно параметра v = {0,l,...,2''}; а е GF{2ip) - примитивный элемент поля GF(2lp)\ у е GF(2r) - произвольный элементподполя GF(2P).

Схема вариантов решений уравнения (15), определяющих значения ФВК, приведена на рис. 8

Варианты решения уравнения а"*' + аук = у

©

©

©

у = 0

г = ?г(2'-1)

(<7*.2" + 1) = 1

(Ч„2> + 1) = 1

У = У\ + Уг;

Уг ~ а"к _I

у = X + X

_I

V

®Г

т = у

2'+ !) = <*,

2"+1)

(.Як -1,2Р +1) = 1

(*г,2' + 1) = 1

I (дк-1,2'+1) = Л

- Единственное решение - -4— - —

дг = 0 (тос! ¿/1)

--сЗ] решений

Я,* о

тФ Д2'+1)

тос!

<7, = 0 (тос! с12)

1 ¿г решений ---

................ Нет решений

Рис. 8. Схема вариантов решений уравнения (15)

Представляя к в виде к = дк(2р -1) + \, получим, что все множество значений к разбивается на три подмножества, которые представлены схемами а, Ь, с на рис. 9.

Оценка количества решений в зависимости от к

а)

Ь)

с)

Рис. 9. Оценка количества решений М

Анализ вариантов решений на рис. 9 показывает, что лучшие с точки зрения минимального значения максимального уровня ФВК результаты получаются при выборе значений к, удовлетворяющих следующей системе уравнений:

'(?*-!. е,.) = 1; при/ = 1,2,...,тр, (16)

(2<7*-1,0 = 1

из которой следует, что самые жесткие ограничения на выбор значений дк накладывает минимальный делитель е, числа 2Р +1, значение которого зависит от свойств числа р. Представим минимальный делитель в форме е, = 2° +1 и найдем условия, при которых 2е +1 делит е, = 2' +1. Нетрудно установить, что таким условием является р = (2(+])е, где />1 - целое число. Отсюда, в частности, следует, что минимальный делитель е, = 3 соответствует значению е = 1 и любому нечетному числу р = 21 +1, а минимальный делитель е, = 5 - значению е = 2 и любому четному числу вида р - 2(21 +1). Кроме того, анализ показывает, что для некоторых четных значений р числа 2Р +1 могут быть простыми. В частности, скорее всего, многие (но не все) из чисел Ферма вида 2, + 1;р = 2* являются простыми. В этой ситуации система (16) имеет решение для любых значений дк . Однако для чисел р вида р - 2'(2др +1); у > 0; др > 0

числа 2Р +1 имеют минимальный делитель е, = 22+1. Итак, при поиске наилучших кодовых последовательностей рассматриваемого подкласса система (16) может быть заменена системой

(?*.е,) = 1;

• (?4-1,е,) = 1; (17)

. -1, е,) = 1

и все возможные ее решения соответствуют четырем вариантам представления чисел

Р-

1) нечетные р вида р = 2г +1, для которых е, = 3;

2) четные р вида р = 2(21 +1), для которых е, = 5 ;

3) четные р вида р = 2' такие, что числа Ферма вида 2Р +1 - простые;

4) четные р вида р = 2' (2^ +1); / > 1; > 0, для которых е, = 22' +1.

Вариант 1: р = 2г +1; е, = 3

Для этого варианта система (17) решения не имеет, а следовательно, этот вариант соответствует либо условию (дк,2р + 1) = ^, либо условию (дк-\,2р+1 ) = </2, где

= = е, = 3 . В частности, если / = 2; р = 5, ТО минимальное значение дк по условию (дк, 2Р +1) = равно 3, что соответствует к = 47 (см. рис. 10Ь). При этом

(<7, -1,2Р +1) = 1, полное число решений М = 5 и максимальный уровень ФВК в соответствии с (14) равен

вк(т) = 2р(М-\)-\ = 2р*7 -1.

Вариант 2: р = 2(2/ +1); е, = 5

Для этого варианта система (17) имеет два решения, а следовательно, этот вариант соответствует условиям (дк, 2" +1) = 1, -1, 2Г +1) = 1. В частности, если I = 1; р = 6, то минимальное значение дк, удовлетворяющее (17), равно 2, что соответствует к.= 127 (см. рис. Юс). При этом полное число решений М = 3 и максимальный уровень ФВК в соответствии с (14) равен

вк{т) = 2Р(М= 2Л+1 -1.

Вариант 3: р-2", число 2Г +1 - простое

Для этого варианта система (17) имеет также два решения, а следовательно, этот вариант соответствует условиям (дк, 2Р + 1) = 1, (дк -1,2р + 1) = 1. В частности, если ■у = 1;р = 4, то минимальное значение дк, удовлетворяющее (17), равно 2, что соответствует А = 31 (см. рис. 10а). При этом полное число решений М = 3 и нижняя граница максимального уровеня ФВК в соответствии с (14) равна вк (г) = 2я (Л/ — 1) — 1 = 2Р+1 — 1.

Отметим, что при существовании дополнительных подполей могут появляться не рассмотренные в данном анализе дополнительные решения. Рассматриваемый вариант как раз обладает указанным свойством. Поэтому, скорее всего, будут существовать значения к, при которых уровень ФВК величиной 2Р-1 будет превышен. Действительно, при к = 47 (дк =3), 61 (дк = 4) количество решений М = 5, что соответствует уровню 0Дг) = 2"*2-1,апри к = \9(дк =5) М = 4, что соответствует уровню вк(т) = 3*2р-I.

М-1 ■

п=а; к=31

Рис. 10. Фрагменты ФВК

Вариант 4. р = 2> (2дг +1); у > 1; др > 0, е, = 21' +1.

Для этого варианта возможен выбор цк таких, что система (17) имеет два решения, вследствие чего полное число решений М = 3 и максимальный уровень ФВК в соответствии с (17) равен

вк(г) = 2Р{М-\)- \ = 2Р*' -1.

Таким образом, полученные результаты могут быть использованы как для построения квазиортогональных составных последовательностей типа кодов Голда, так и для предварительной отбраковки заведомо «плохих» комбинаций кодов, например при алгоритмическом формировании ансамблей.

Оценка двумерной функций корреляции

При наличии доплеровского смещения частоты качество ансамблей сигналов должно описываться уже двумерной ФВК (ДФВК). Однако применить методы алгебры для ее точного описания и расчета невозможно. Тем не менее в диссертационной работе получен ряд результатов, полезных для расчета и оценивания ДФВК. Учитывая комплексный характер результата, получаемого на выходе корреляционного приемника, Для оценки качества ансамбля сигналов обычно используют модуль или квадрат модуля взаимной функции неопределенности (ВФН)

4'14(г,А) = |Лр4(Г,Й)|2 =

= + а*)соя ^/,(/-/) I

/-0 /-О V " )

которая приводится к виду

(г. И) = Тц (г, И) -А1м = А1X сов^ Нт ) в,к (т + цт-Ут), (18)

где

+ -О = £5(а'+'(1+ «"))£(«* (1+а-)) (19)

1-0

представляет собой значение ФВК кодовых последовательностей в(| + т + цт) = 5(а/+г(1 + а™)) и Ьк0 + ут) = 5(а1к(1 + аяк)). На основе анализа (18) получены следующие свойства ДФВК.

Свойство 1ДФВК

Пусть известна совокупность значений x¥lk(rq,h)0, полученная в единственной точке

(сечении) h на оси частот для всех возможных изоморфных отображений а = /?',

Nt0

(q,N) = l. Тогда известно множество значений ВФН во всех точках (сечениях) ~—g на

Nt0

оси частот при фиксированном значении г, где g пробегает все значения в соответствии с условием qh = g(mod N), то есть

К(г.*) = *)= + Л. -"»). где

представляет собой ФВК эквивалентных кодовых последовательностей с порождающими многочленами, имеющими корни p,fik при условии а =/}ч, (q,N) -1. Значения ФВК (20) на основании свойства 2 ФВК, полученные ранее в этой главе, отображаются на соответствующие значения 0[k(e + -у„) (19), а следовательно, полностью известив при анализе ФВК.

Таким образом, соотношения (5.58) и (5.61) вместе представляют собой особую процедуру быстрого преобразования в полях Галуа для расчета ДФВК. Из общего свойства 1 следует также ряд полезных частных свойств.

Свойство 2 ДФВК

Пусть q = 2',j = \,2,...,n-\. Тогда 4>;,(r,W).

\ a j

\2

4jk(T2J,h)a, поскольку при

таких значениях q изменения структуры пар кодовых последовательностей не происходит. Таким образом, существует взаимная связь между частотными и временными сечениями ВФН.

Свойство ЗДФВК

Заменяя в (18) И на N-И и учитывая, что = получим

(г, N -h)a= \ I (z, h)a, что указывает на симметрию (без учета

амплитудных множителей) значений ВФН относительно точки -(2""'-1) на оси

частот.

Свойство 4ДФВК

Данное свойство является следствием свойства 2 при выполнении условия Ы -к = И2' (то<1 Щ

или А(2"/ +1) = 0(тоё Ы). При этом выполняется соотношение

Верхняя граница ДФВК (ВФН)

Основой для оценки является соотношение (18). Грубая, но вполне достаточная верхняя граница ВФН может быть получена при жестких предположениях о том, что ФВК 9)к (т + /у,, - vm) при любых значениях г,/и имеют максимально возможные значения

впп = max(0lt(r+ -О), причем со знаком, соответствующим знаку cosí —Am] в

{N )

выражении (5.58). При этих допущениях получим

значение нормированной ФВК.

Таким образом, значения ВФН никогда не могут превышать максимальных уровней

Другим классом прикладных задач, решаемых в данной главе, является синтез эффективных устройств кодирования и декодирования. Современные средства поддержки оперативности, масштабируемости, безопасности работы информационных телекоммуникационных систем требуют построения гибких кодеров, способных быстро перестраивать параметры кодирования и, в частности, задержку кодовой последовательности.

Методы быстрого изменения задержки кодовой М-последовательности

Один из предлагаемых методов основан на быстром определении начального вектора состояния регистра сдвига. С целью математического обоснования метода получен закон

в

втш, где в - -ой- - максимальное

N

ФВК.

преобразования /¡-разрядного двоичного вектора = в

любую его компоненту для произвольного порождающего многочлена /(х), где <р

- произвольное целое число; у/ - целое число в диапазоне от 0 до п -1.

Далее задача состоит в том, чтобы представить элемент а2 в виде многочлена

л-1 л

= по модулю порождающего многочлена /(*) = > т.е.

(=0 1-4

а2"' = Оп_](х) + Н(х)/(х). Для каждого конкретного многочлена /(*) можно определить и многочлен С?п_, (х). Имея в виду, что при построении устройств формирования М-последователыюстей структура порождающего многочлена фиксирована, фиксированным оказывается также и многочлен (х), в результате чего получим

О ; у/ = 2/;

(21)

Из (21) следует, что в общем случае для выполнения преобразования (назовем его

"л-1"

извлечением квадратного корня) требуется не л-разрядпьгй, а л +

-разрядный

двоичный вектор. При задании исходного л-разрядного вектора это потребует

"л-1"

дополнительного формирования недостающих л-1

символов путем выполнения

операций сдвига регистра в стандартной схеме генератора М-последовательности,

изображенной на рис. 11.

I , 1 1 1 ,

н п-1 | ... » 1 ; 1 ? Ь

1- ■1 4. «1 * Г

1 V 1 ... ь 1 1

1 1 1 1 1

Н ® 1

вэ

Рис. 11. Генератор кода максимальной длины Итак, алгоритм определения л-разрядного вектора А

>2* '

соответствующего

последовательности с фазовым сдвигом, вдвое превышающим фазовый сдвиг исходной последовательности, соответствующей вектору , состоит из следующих шагов:

1) определение вида преобразующего многочлена (3„_, (дг) (операция выполняется один раз при заданном порождающем многочлене /(*);

«-разрядной комбинации в регистре сдвига;

3) определение искомого вектора путем выполнения преобразования (21). Нетрудно видеть, что повторение приведенной последовательности операций qa раз, используя в каждом такте текущую комбинацию в качестве исходной «-разрядной комбинации, позволяет за шагов алгоритма преобразовать исходный вектор А^ в

комбинацию , для чего обычный алгоритм, использующий последовательный сдвиг

символов последовательности, требует <р(2^'-1) операций. Полученный частный алгоритм использован в работе для построения общего алгоритма определения вектора начального состояния А^ при произвольном £ в виде Ь = 2'1 + 2Ь +... + 2®'1, или

откуда следует, что указанные выше операции, выполняемые последовательно над текущим вектором ^ - раз в сочетании со сдвигом' на один символ для каждого ( = 1,2,...,/,, обеспечат получение вектора, соответствующего сдвигу V = 2'1' Л относительно начального вектора А,. Последнее является следствием того, что разработанный алгоритм в целом формирует вектор, фазовый сдвиг которого есть результат умножения исходного начала отсчета на Ь. Так, если в качестве исходной начальной комбинации взять А0, то преобразование отсутствует. Завершающая операция,

производящая умножение текущей фазы на 2'', является несимметричной и выполняется отдельно. Таким образом, для реализации рассмотренного метода следует задать начальный вектор А, и выполнить следующие операции:

1) найти разложение Ь в виде (22);

2) для каждого / = 1,2,...,/,-1 последовательно q¡ -раз выполнить операции, необходимые для преобразования (21) и операцию сдвига на один символ, принимая на каждом ;-м шаге текущий вектор в качестве нового значения начального вектора;

3) выполнить раз при / = I, операции, необходимые для преобразования (21).

2) генерирование дополнительных

символов путем - сдвигов исходной

(22)

Описанный выше алгоритм предполагает известность начального вектора А, для произвольного многочлена. Вектор А, тривиально связан с вектором А0, а для определения последнего в работе создана и используется специальная программа. В приложении 2 приведена таблица опорных примитивных многочленов степени до 63 включительно вместе с соответствующими им векторами нулевого начального состояния А0. Этот метод можно рекомендовать для аппаратурной реализации алгоритма.

Одна из сложнейших проблем в реализации рассмотренного алгоритма -алгоритмический расчет преобразующего многочлена G„_, (х). Разработан метод и алгоритм, позволяющий значительно ускорить эти вычисления. Он представляется в виде следующих шагов.

1) Записать в (2и-7)-разрядный регистр сдвига символы по следующему правилу

где верхние индексы (1 или 0) отображают новое и старое состояние разрядов регистра сдвига соответственно. При этом начальное состояние соответствует элементу а и равно {010...0}. Операция перезаписи соответствует возведению данного представления элемента в квадрат.

2) Произвести п-1 сдвигов содержимого (2и-7)-разрядного регистра сдвига, п последних разрядов которого хранят вычисление текущего элемента (точнее, многочлена, представляющего этот элемент) по модулю порождающего многочлена f{x). По окончании (п-1)-го сдвига в п последних разрядах регистра содержится результат вычисления квадрата текущего элемента по модулю f(x).

3) Повторить операции п.п. 2 и 3 п-2 раза. Результатом (п-1) циклов сдвига и (п-1) циклов перезаписи является л-разрядная комбинация, соответствующая коэффициентам многочлена Gn_,(a).

Очевидно, что при больших значениях п полное количество элементарных операций (п -1)2 « 2""1, что и определяет значительно более высокую эффективность указанного подхода к построению рассматриваемого алгоритма.

Разработан также аналитический метод определения начального вектора состояния регистра сдвига для частного случая представления порождающего многочлена в виде

Дх) = 1 + х* +х". Метод

основан на решениях диофантова уравнения вида

/ = ш + Лп-к). Результатом применения метода является нахождение символа кода в виде Т(а') = £ {С^},, (23)

т-0, ти12

где /(=/,-;'; 1'2 =/2+У, где /, ] удовлетворяют соотношению Г3 + т = ]{п - к), а /,, ¡2, /3 связаны между собой следующим образом

4-1,п

И-*

; =1-(,п-гг(п-к).

Подробное исследование коэффициентов суммы (23) дал следующий результат |С*=алЬ, после чего вычисление (23) становится тривиальным.

Таким образом, верхняя граница количества шагов вычислений по формуле (23) может быть оценена как

М =

п-к

N

п(п-к)

в худшем предположении, что I = N. Нетрудно убедиться,

что выигрыш в количестве операций описанного метода определения символа вектора состояния регистра сдвига по сравнению с традиционным (генерацией с помощью схемы на рис. 11) составляет приблизительно п(п-к) и достаточно быстро растет с ростом и.

Одним из основных этапов работы асинхронных адресных, измерительных и других информационных телекоммуникационных систем является вхождение в режим синхронизации по времени, или устранение априорной неопределенности по задержке. Часто этот этап называется этапом поиска сложного сигнала по задержке. Эта задача по своей роли в теории и практике кодирования является задачей декодирования.

Методы быстрого поиска М-последовательноствй по задержке

В диссертационной работе предложены методы быстрого поиска М-последовательностей по задержке. Выполнено теоретическое обоснование методов ускоренной обработки кодовых последовательностей с четной и нечетной непростой степенью порождающего многочлена. Методы базируются на разработанных быстрых преобразованиях в непростых полях Галуа, описанных в главе 4. Разработаны варианты реализации устройств быстрого поиска кодовых М-последовательностей с нечетной степенью порождающего многочлена. Схема одного из вариантов с параметрами п = п,п2, и, = и2 = 3, N = 2"1"1 -1 = 511, получающая корреляционную сумму А(т - Г0) за один период кода максимальной длины приведена на рис. 12.

Рис. 12. Корреляционное устройство.

На этом рисунке:

s(i) = S(a') - М-последовательность;

т - неизвестная задержка;

т0 - управляемая задержка опорной М-последовательности;

ГМП - генератор М-последовательности;

СТЧ - синтезатор тактовой частоты, управляя которым, изменяют задержку г0;

- накопительный сумматор со сбросом и выдачей результата в момент сброса.

Для простоты считается, что все элементы цифрового коррелятора работают на тактовой частоте M-последовательносги, хотя на практике она может быть значительно выше. Допустим также, что задержка М-последовательности принимает дискретные значения, равные пт,, где п - целое, а г, - длительность символа М-последовательности.

Покажем, что использование предложенного выше метода обработки позволит получить 2"' -1 = 7 полных корреляционных сумм за один период М-последовательности при незначительном усложнении оборудования. Схематическое изображение первого варианта реализации, простого для понимания принципа работы устройства, но довольно емкого в оборудовании, представлено на рис. 13. Счетчик по модулю 511 определяет текущий номер последовательности s(i + г), который проверяется в ПЗУ на

принадлежность одному из множеств /",...,Г6,1". Каждое из подмножеств /'

определяется путем выборок чисел i с заданным шагом L. Множество /" определяет вырожденную «короткую» последовательность, состояющую из всех нулей. По результату проверки приходящий на вход отсчет s(i + r) сортируется в каналы 0,...6, 7 соответственно. Таким образом, если есть синхронизация, то в каждом канале от 0-го до 6-го накапливаются по 64 символа принимаемой кодовой последовательности и результат представляет собой 7 символов «короткой» М-последовательности, а в 8-м канале накапливается вырожденная последовательность из 63-х единиц принимаемой

последовательности 5(/ + г), соответствующих двоичному следу нулевого элемента поля GF(23).

Рис. 13. Схема параллельной обработки

Как было показано ранее, выборки исходной кодовой последовательности, взятые с шагом 73, образуют «короткую» М-последовательность, поэтому значения ФАК этой последовательности с добавлением суммы из 8-го канала равны значениям ФАК исходной М-последовательности в точках, отстоящих друг от друга на 73 позиции. Следовательно, на обнаружение пика ФАК требуется время в 7 раз меньшее, чем для схемы на рис. 12, при условии, что обработка полученных значений ФАК будет укладываться в период их поступления, т.е. в период М-последовательности, как и в первом варианте. Одним из наиболее сложных в реализации устройств в схеме на рис. 13 является ПЗУ емкостью 511x3 бит, управляющий демультиплексором. С учетом этого недостатка разработан второй, более простой вариант реализации схемы управления демультиплексором, представленный на рис. 14. За счет относительно небольшого усложнения схемы объем ПЗУ уменьшился в 7 раз. Можно заметить, что т0 управляется в пределах от 0 до 73, что достаточно для получения всех точек ФАК принимаемой М-последовательности, однако при необходимости управление в больших пределах может быть получено записью кода в счетчик по модулю 7. Объем ПЗУ может быть еще уменьшен в 9 раз при использовании свойств множеств Г, Г, но для рассматриваемого примера М-последовательности длиной 511 символов выигрыша в оборудовании не будет. Однако для более длинных последовательностей может быть получен значительный выигрыш, поэтому разработан и 3-й вариант реализации алгоритма (рис. 15).

Рис. 14. Схема управления демультиплексором

К демультиплексору

Рис. 15. Усовершенствованный вариант схемы управления демультиплексором В этом варианте используется следующее свойство множества Г : если текущий номер символа / принадлежитр-множеству (i е /*), то символы с номерами /2' (/=0,1,...,6) будут

принадлежать каналу с номером 2' р (mod 7) и ¿2' е Гр так как если i е 1'р, то и ¡21 е l'p.

Поэтому в ПЗУ могут храниться только коды номеров каналов, соответствующих минимальным представителям смежных классов номеров символов.

Операцию умножения на 2 по модулю 2" -1 выполняет циклический л-разрядный регистр сдвига. Тогда упрощенный алгоритм определения принадлежности номера символа к соответствующему множеству будет следующий:

1) текущий номер символа М-последовательности сдвигается влево / раз по модулю 511, пока в ПЗУ не будет найден минимальный представитель того класса, к которому принадлежал текущий номер;

2) полученный на выходе ПЗУ в результате предыдущей операции номер канала сдвигается влево такое же количество раз, но уже по модулю 7, полученное число есть номер канала, в который распределяется текущий символ кодовой последовательности.

Блок задержки сдвигов выполняет функцию хранения количества выполненных сдвигов до получения минимального элемента из ПЗУ.

Глава завершается синтезом псевдошумовых сигналов с нормированными характеристиками. Детерминированные псевдошумовые сигналы с заданными свойствами (законом распределения амплитуд, спектральным составом) часто требуются для построения моделей устройств и (или) каналов. Предложена оригинальная схема генератора псевдошумовых сигналов на основе длинных кодов максимальной длины, который в отличие от известных устройств при увеличении длины кодовой последоЬательности (а следовательно и точности моделирования) не уменьшает ширину спектра шумового сигнала.

Таким образом, главными в данной главе являются следующие результаты и выводы.

1) Найдены общие свойства функций взаимной корреляции кодов максимальной длины.

2) Выполнен обобщенный синтез двухкомпонентных кодов с тремя уровнями взаимной корреляции.

3) Предложена конструкция и выполнен синтез трехкомпонентных составных кодов с гарантированными уровнями корреляции.

4) Разработана теоретико-числовая модель аналитического оценивания функций взаимной корреляции. Выполнена ее апробация.

5) Найдена верхняя граница двумерной функции взаимной корреляции.

6) Разработаны методы аналитического и алгоритмического определения вектора начального состояния генераторов для быстрого скачкообразного изменения задержки кодовой последовательности в устройствах кодеков информационных телекоммуникационных систем.

7) Разработаны методы ускоренного поиска длинных кодовых последовательностей по задержке, основанные на быстрых преобразованиях в непростых полях Галуа.

8) Выполнен синтез псевдошумовых сигналов с нормированными характеристиками.

СПИСОК ПУБЛИКАЦИЙ

1. Витомский Е.В., Михайлов В.Ю. Структурный метод анализа безопасности инфокоммуникационных систем //Телекоммуникации. -2012. -№1. - С. 31-35.

2. Михайлов В.Ю. Теория и практика кодирования. Научное издание, М.: МАИ-ПРИНТ, 2010.-307 с.

3. Безопасное информационное взаимодействие. Коллективная монография. Под ред. Р.Б. Мазепы и В.Ю. Михайлова. Научное издание, М.: МАИ-ПРИНТ, 2010. - 186 с.

4. Михайлов В.Ю., Мазепа Р.Б. Кодирование, шифрование и запутывание информации. Цели, задачи, представление и особенности применения / Информационные технологии и математическое моделирование систем 2009-2010 // Труды международной научно-технической конференции. М., 2010.

5. Михайлов В.Ю., Мазепа Р.Б. Разработка методов и инструментальных средств обнаружения вредоносного и исследующего ПО / Информационные технологии и математическое моделирование систем 2009-2010 // Труды международной научно-технической конференции. М., 2010.

6. Михайлов В.Ю., Мазепа Р.Б. Основы теории кодирования. Научное издание, М.: МАИ-ПРИНТ, 2009. - 458 с.

7. Проблемы безопасного информационного взаимодействия в распределенной среде. Коллективная монография. Под ред. Р.Б. Мазепы и В.Ю. Михайлова. Научное издание, М.: МАИ-ПРИНТ, 2009. - 258 с.

8. Красильникова О.С., Михайлов В.Ю. Проблемы динамического управления режимами работы, состоянием и поведением распределенных приложений / Информационные технологии и математическое моделирование систем 2006-2008 // Материалы международной научно-технической конференции. М.: Радитехника, 2008.

9. Красильникова О.С., Михайлов В.Ю. Методы повышения эффективности распределенных приложений / Информационные технологии и математическое моделирование систем 2006-2008 // Материалы международной научно-технической конференции. М.: Радитехника, 2008.

10. Корнилов A.M., Михайлов В.Ю. Принципы проектирования информационных систем оперативного взаимодействия / Информационные технологии и математическое моделирование систем 2006-2008 // Материалы международной научно-технической конференции. М.: Радитехника, 2008.

11. Корнилов A.M., Михайлов В.Ю. Принципы использования файловой системы в логических каналах / Информационные технологии и математическое моделирование

систем 2006-2008 // Материалы международной научно-технической конференции. М.: Радитехника, 2008.

12. Агринский Н.М., Михайлов В.Ю. Разработка автоматизированного подхода к проектированию компьютерных систем информационного взаимодействия / Информационные технологии и математическое моделирование систем 2006-2008 // Материалы международной научно-технической конференции. М.: Радитехника, 2008.

13. Агринский U.M., Михайлов В.Ю. Использование универсальных шаблонов в проектировании информационных систем / Информационные технологии и математическое моделирование систем 2006-2008 // Материалы международной научно-технической конференции. М.: Радитехника, 2008.

14. Михайлов В.Ю., Мазепа Р.Б. Концепция проектирования защищенных систем информационного взаимодействия / Информационные технологии и математическое моделирование систем 2006-2008 // Материалы международной научно-технической конференции. М.: Радитехника, 2008.

15. Михайлов В.Ю., Мазепа Р.Б. Системный подход к безопасности информационного взаимодействия / Информационные технологии и математическое моделирование систем 2006-2008 // Материалы международной научно-технической конференции. М.: Радитехника, 2008.

16. Bychenkov S., Mikhaylov V., Sakaniva К. Fast Acquisition of PN Sequences in DS/CDMA Systems. IEICE TRANS. FUNDAMENTALS, VOLE85-A, NO.ll NOVEMBER 2002.

17. Майоров А.Б., Михайлов В.Ю. Безопасность клиент-серверных информационных систем / Будущее авиации и космонавтики 2001 // Тематический сборник научных трудов. Изд. МАИ, 2001.

18. Михайлов В.Ю., Волков A.A., Демин М.П. Методы дистанционного управления процессом автоматизированного обучения / Материалы научно-методической конференции "Современная учебная техника и образовательные технологии". Нижний Новгород, 1996.

19. Михайлов В.Ю., Волков A.A., Демин М.П. Комплекс программных средств для изучения принципов построения и управления базами данных / Материалы научно-методической конференции "Современная учебная техника и образовательные технологии". Нижний Новгород, 1996.

20. Михайлов В.Ю., Волков A.A., Демин М.П. Программный комплекс для углубленного изучения и освоения принципов обмена данными в сети / Новые

информационные технологии в университетском образовании. НИИ МИОО, Новосибирск, 1996.

21. Михайлов В.Ю., Демин М.П., Лапушкина H.A. О комплексном обеспечении перехода образования на новые информационные технологии / Тезисы докладов международной научно-практической конференции «Высшая школа в новых социально-экономических условиях». Санкт-Петербург, 1994.

22. Михайлов В.Ю. Математические основы анализа и синтеза сложных сигналов и процедур их обработки. Учебное пособие. М.: Изд. МАИ, 1994.

23. Куприянов А.И., Михайлов В.Ю., Черкасов В.В. Цифровые радиоэлектронные устройства преобразования и обработки информации. Учебное пособие. М.: - Изд. МАИ, 1993

24. Быченков C.B., Михайлов В.Ю. Об автоматизации процесса выбора сложных сигналов в радиосистемах / Методы представления и обработки информации в радиотехнических системах // Межвузовский сб.науч. трудов, 1993.

25. Михайлов В.Ю., Степанников В.М. Современный Бейсик для IBM PC. Среда, язык, программирование. Учебно-справочное пособие. М.: Изд.МАИ, 1993.

26. Михайлов В.Ю. Система автоматизированного проектирования сложных дискретных сигналов в радиосистемах связи, управления и навигации / Тезисы докладов международной конференции "Новые информационные технологии", Рига, 1992.

27. Михайлов В.Ю. Обучающая система «Сложные дискретные сигналы в системах связи, управления и навигации» / Тезисы докладов международной конференции "Новые информационные технологии", Рига, 1992.

28. Михайлов В.Ю., Чернявский Д.М. Методы повышения эффективности устройств вхождения в связь по задержке с М-последовательностями / Вопросы повышения эффективности радиотехнических систем II Межвузовский сб.науч. трудов, 1992.

29. Михайлов В.Ю., Куприянов А.И. О формировании широкополосных псевдогауссовых шумовых процессов / Вопросы повышения помехоустойчивости и эффективности радиотехнических систем // Межвузовский сборник научных трудов, 1991.

30. Способ и устройство формирования широкополосных псевдогауссовых шумовых сигналов: Решение о выдаче A.c. по заявка №4287622/09 / Михайлов В.Ю., Захаров Е.К., Курбатов A.B., Куприянов А.И., Суслов Н.В.

31. Способ генерирования помех. A.c. №308790 (СССР) / Михайлов В.Ю., Куприянов А.И., Суслов Н.В.

32. Михайлов В.Ю., Курбатов A.B. Оценка размера ансамбля квазиортогональных сигналов / Алгоритмы помехоустойчивого приема радиотехнических сигналов // Межвузовский сборник научных трудов. М.: МИРЭА, 1989.

33. Михайлов В.Ю. Анализ эффективности алгоритмов формирования ПСП с различной задержкой / Вопросы проектирования РСУПИ // Тематический сборник научных трудов. М.: МАИ, 1989.

34. Бондаренко O.E., Михайлов В.Ю. Расчет и конструирование MC и МП. Методические указания по курсовому проектированию. М.: МАИ, 1989.

35. Михайлов В.Ю. Дискретные модели и их использование в задачах оптимизации структуры радиосистем / Расчетно-имитационные модели при проектировании информационно- управляющих систем // Тематический сборник научных трудов. М.: МАИ, 1986.

36. Михайлов В.Ю., Куприянов А.И. Генерирование узкополосных шумовых процессов с калиброванными спектральными характеристиками / Методы обработки сигналов в радио технических системах // Межвузовский научных трудов. М.: МИРЭА, 1986.

37. Генератор узкополосных псевдогауссовых шумовых сигналов. A.c. №1309872 (СССР) / Михайлов В.Ю., Куприянов А.И., Захаров Е.К., Суслов Н.В.

38. Куприянов А.И., Лукашев Е.М., Михайлов В.Ю., Обухов Н.В., Савинов В.А., Чижов В.И, Радиосистемы управления и передачи информации. Учебное пособие к лабораторным работам. М.: МАИ, 1984.

39. Михайлов В.Ю. Регулярный метод синтеза квазиортогональных ансамблей М-последовательностей. // Радиотехника и электроника. - 1984. -№9. - С. 1838-1840.

40. Березин JI.B., Михайлов В.Ю., Горицин B.JI. Применение аппарата двоичного программирования в задачах повышения эффективности сложных систем путем оптимизации их структуры / Проблемы повышения эффективности радиотехнических систем и устройств // Тематический сборник научных трудов. М.: МАИ, 1984.

41. Михайлов В.Ю., Горицин B.J1. Применение двоичного программирования в задачах диагностики отказов радиосистем / Методы и устройства обработки сигналов в радиотехнических системах // Сборник научых трудов МИРЭА, М.: МИРЭА, 1983.

42. Генератор узкополосных псевдогауссовых шумовых сигналов. A.c. №1083331 (СССР) / Михайлов В.Ю., Куприянов А.И., Блинков А.И.

43. Михайлов В.Ю. О свойствах подкласса двоичных М-последовательностей с гарантированным максимальным уровнем взаимной корреляции. Тезисы докладов II

1 2 " Э и О О

60

Всесоюзцой^НТК «Развитие теории и техники сложных сигналов», М.: Радио и связь, 1983/' / 1

Михайлов В.Ю. Использование свойств М-последовательностей для ускорения их поиска по задержке. Тезисы докладов II Всесоюзной НТК «Развитие теории и техники сложных сигналов», М.: Радио и связь, 1983.

45. Михайлов В.Ю. Метод ускоренной цифровой обработки сигналов, построенных на основе М-последовательностей. Расширенные тезисы докладов Всесоюзной НТК "Методы и микроэлектронные средства преобразования и обработки сигналов", Рига, 1983.

46. Михайлов В.Ю. О расчете максимальных значений функции взаимной корреляции М-последовательностей. // Радиотехника и электроника, - 1982. - №6. - С. 1219-1221.

2012097951

Множительный центр МАИ (НИУ) Заказ от// £7/ 2012 г. Тираж МОъю.

2012097951