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

На правах рукописи УДК 621.396.98:629.783

Семенов Сергей Александрович

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

Специальность 05.12.14 - Радиолокация и радионавигация

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Москва - 2005

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

Научный руководитель - кандидат технических наук,

доцент Александр Ефимович Фридман.

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

профессор Александр Иванович Перов;

кандидат технических наук,

профессор Владимир Назарович

Харисов.

Ведущая организация - Российский Научно Исследовательский Институт Космического Приборостроения.

Защита состоится «___» _ 2006 года на заседании

диссертационного совета Д 212.125.03 Московского авиационного института (государственного технического университета) по адресу: 125993, Москва, А-80, ГСП-3, Волоколамское шоссе, 4.

С диссертацией можно ознакомиться в библиотеке МАИ. Автореферат разослан «_»_2006 года.

Отзыв, заверенный печатью, просим направлять по адресу: 125993, Москва, А-80, ГСП-3, Волоколамское шоссе, 4.

Ученый секретарь диссертационного совета Д212.125.03 к.т.н. доцент М.И. Сычев

ЛообА-

8/М

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

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

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

Для достижения этой цели в диссертационной работе решаются следующие задачи:

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

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

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

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

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

6. Проводится экспериментальная проверка основных программных блоков навигационного приемника.

Объект исследования настоящей диссертационной работы - полностью программные навигационные приемники.

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

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

Условия получения результатов

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

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

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

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

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

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

2) Синтезирован алгоритм слежения за навигационным сигналом, применимый в программных приемниках.

3) Доказана эффективность и реализуемость алгоритмов слежения за фазой и задержкой навигационного сигнала на основе фильтра Калмана.

4) Выявлены основные аспекты, требующие анализа при разработке конкурентоспособного полностью программного навигационного приемника.

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

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

Публикации. По материалам диссертации опубликовано 3 научные работы.

Положения, выносимые на защиту:

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

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

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

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

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

Структура и объем диссертации. Диссертационная работа состоит из введения, шести глав, заключения и списка литературы из 27 наименований, изложена на 100 (140) страницах машинописного текста.

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

Во введении определено понятие "программная реализация навигационного приемника" как подход, при котором все или большая часть операций по цифровой обработке навигационных сигналов и данных выполняется на программируемых процессорах общего назначения, либо на цифровых сигнальных процессорах (Digital Signal Processor, DSP). Толчком к развитию такого подхода стало появление новых высокопроизводительных процессоров: Pentium IV, TMS320C62xx, Tiger Shark (Analog Devices). Данные процессоры позволяют организовать параллельную обработку большого числа потоков данных при приемлемом энергопотреблении и цене. В последние годы сформировалось целое направление исследований с целью создания программно-реализованного GPS приемника (Software GPS Receiver). Развитие программных навигационных приемников происходит по двум основным направлениям:

1. Приемники с обработкой отсчетов промежуточной частоты в режиме пост-обработки;

2. Приемники с обработкой отсчетов промежуточной частоты в режиме реального времени.

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

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

Она включает в себя:

• Аналоговую радиочастотную часть (РЧ)

• Цифровой программируемый процессор (ЦП)

• Вспомогательные компоненты (ОЗУ, ПЗУ и т.п.).

Цфсеой Пюрамидемгй

Пзоцеооср

Спецопыые устройства «довьвсда

14терфейс Потребителя

Рис. 1 Обобщенная функциональная схема полностью программного навигационного приемника

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

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

Рис. 2 Блок-схема аппаратно-программного комплекса цифровой части программного приемника

Главными особенностями разработанной блок-схемы являются следующие моменты:

• Программный комплекс состоит из независимых модулей (задач), разрабатываемых независимо и обменивающихся данными посредством механизма памяти общего доступа (блок БМ на Рис. 2).

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

Разработанные структура программного обеспечения и операционная оболочка позволяют не только существенно упростить разработку полностью программного навигационного приемника, но и использовать при этом процессоры, имеющие существенные ограничения на размер выполняемого кода (например, АЭ8Р2189).

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

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

Рис.3 Блок-схема алгоритма быстрого поиска.

В соответствии с этой схемой, входной сигнал подвергается преобразованию Фурье (блок ОРТ(2)), затем умножается на Фурье-образ опорного сигнала. Полученная последовательность подвергается обратному преобразованию Фурье (блок ГОРТ(3)). Полученная таким образом комплексная последовательность позволяет оценить наличие сигнала и его положение по задержке. Несмотря на достоинства такого подход, в работе показано, что непосредственное вычислений корреляционных интегралов по формулам

Г = ЪУь-Усг О)

к=к0

ко+Н

& = Ел

*=*0

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

{ук } - последовательность оцифрованных отсчетов на выходе

радиочастотной части;

Усг > Ухг " опорные последовательности.

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

Программный коррелятор построен в соответствии со схемой, приведенной на Рис.4.

Рис. 4. Схема коррелятора (один канал)

Видно, что в процессе вычисления корреляционных интегралов необходимо:

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

• Вычислить опорную кодовую последовательность;

• Вычислить опорную последовательность промежуточной частоты;

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

Формализуя вышесказанное, можно отметить, что задача коррелятора состоит в вычислении свертки между входным сигналом и опорными последовательностями С А кода и промежуточной частоты, которая задается формулой:

{¿я} - последовательность моментов времени оцифровки в пределах периода СА кода;

Т( - значение задержки между входным сигналом и копией СА последовательности;

со - частота опорного генератора промежуточной частоты;

(р0 - фаза опорного генератора промежуточной частоты на момент начала

эпохи;

5(7) - входной сигнал (смешанный с шумом); СА(¡) - опорная СА последовательность.

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

С точки зрения вычислительных затрат, многоканальный аккумулятор (перемножитель-сумматор) является критической частью программного коррелятора. Проведенные расчеты показывают, что даже для частоты дискретизации 3 МГц количество операций умножения и сложения составляет около 1108в секунду.

N

(2)

где:

Для сокращения вычислительных затрат в десятки раз предлагается так называемый алгоритм параллельного перемножения-суммирования. Применительно к случаю бинарно-квантованных входного сигнала и сигнала копии, он основан на том, что в каждый дискретный момент времени сигнал копии к-го канала записывается в к-й разряд быстродействующего регистра процессора. Так в 32-разрядном целочисленном процессоре в одном регистре размещаются сигналы копии 32-х каналов. Тогда перемножение входного сигнала с 32-мя сигналами копий реализуется одной операцией ХСЖ (исключающее ИЛИ), т.е. выполняется за один такт процессора. Далее, суммирование также может быть выполнено параллельно для всех каналов всего за несколько тактов.

Для того чтобы точно описать возможные варианты алгоритмов быстрого суммирования, рассмотрим суммирование бинарных величин:

г"

5 = , где Ь, может принимать значения 0 или1. (3)

1=1

Пусть последовательность ... является последовательностью битов в

бинарном представлении 51, последовательность {С^} С¡, ... С^ — совокупность их битов переноса. Тогда рекуррентный алгоритм суммирования можно представить в виде последовательности следующих операций:

Ск° = 8°к = 0, к= 1...Ы

С,' = в/"1 А Ь,

Б,' = в,м© Ь, (4)

С2' = Бг'"1 АС]'

82 = 82 Ф С1

Сз1 = Бзи А С2' Бз1 = Бз'"'® С2'

где:

Сы' - Бм'1А См.!1

1= 1.. .2Ы - номер входного отсчета; к=1...К - номер разряда;

S'k - значение к-го бита после того, как были

просуммированы i входных бита;

С'к - бит переноса из разряда к после суммирования i

входных бит;

Л - логическая операция AND;

Ф - логическая операция XOR.

Таким образом ,нетрудно видеть, что возможно организовать параллельное суммирование 32 независимых битовых потоков, соответствующих синфазным и квадратурным подканалам 16 каналов приемника. Даже записанный в простейшем виде (4) параллельный сумматор дает 40% выигрыш по сравнению с последовательной обработкой 32 каналов (для 1024 отсчетов). Модифицированный алгоритм, использующий разбиение разрядов сумматора на группы, позволяет довести выигрыш быстродействия до 8 раз.

В третьей главе анализируются особенности нескольких типов корреляторов. Преобразуем (2) к виду:

А,=^Ю-СА((„-г,

где:

со0 - номинальная промежуточная частота (конструкционная

константа);

ОЗф, - псевдодоплеровское смещение, вызванное смещением

частоты задающего генератора навигационного приемника от номинала и относительным движением приемника и спутника;

СА

<р01 - начальная фаза СА кода опорного сигнала на момент

начала 1-ого интервала интегрирования.

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

1. Положить величину <p^f = 0, a Nt изменять от эпохи к эпохе таким

образом, чтобы момент времени Tt начала нового интервала

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

2. Положить величину Nt = const, соответствующую длительности 1

CA

миллисекунды по шкале времени приемника, величину (p0l

устанавливать равной фазе CA кода входного сигнала в момент времени

г,, соответствующий началу нового интервала накопления

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

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

Пусть fmc - частота основного задающего генератора приемника, тогда, с учетом отклонения частоты этого генератора от расчетного номинал, можно записать:

f = f° +Аf

J ose J ose ose

где:

- номинальная частота задающего генератора; Af°sc - смещение частоты задающего генератора от номинала.

Тогда частоты гетеродина и шкалы времени можно записать как:

(6)

где: а , Р -соответствующие константы.

Для упрощения рассмотрения, предположим, что все величины здесь и далее, не зависят от времени (если это не оговорено особо).

Частота сигнала на входе коррелятора в этом случае:

Усогг У¡ук Уск>р ^ (Уо«с А/шс ) ^"<к>р

Предположим, спутник излучал сигналы в моменты и п0 системной шкале времени. Соответственно, сигналы достигли антенны приемника в моменты tx и по системной и ) , ) по внутренней шкалам (Рис. 5).

Рис. 5. Расположение событий на шкалах времени Введем обозначения: т0 =

Г = м(Г2)-н(Г,) В соответствии с классическим определением, величину

Ар = (и(?2)-{ 2°)-(и(',)-',°)

будем трактовать как приращение псевдодальности. Покажем, что величина

Ь<Р = Ь<РС0ГГ-(/1-СС-СС\? связана с Лр простым соотношением: Ар__ 1

(9)

В (8) величина А<рсогг представляет собой приращение фазы сигнала на входе коррелятора за интервал времени —. В работе доказано, что &<рсогг также

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

Ьфсогг = Г0

1

1 +

ск>р

(Ю)

7° +7

<¿7/7

и, кроме того:

^ охс "-Нов

fn.SC

/О +/• /-0

/ J ОБС

/1+4/;

./я» У(¡ор Уо$с

(11)

Из (10), (8) и (11) получим:

Jgpsrfdop Jose j

___

л ~ \ > '{fgprttfisr06'öCc+Xo)-^' л T7

JgpirJdop JgpsKJdop Jose

Josi^fosc fgpsrfdop

f f

Jose Jeps

f

Jose

(12)

Соотношение (12) можно переписать в виде:

_ г-(С

Ар:

gps

(13)

Величина Д <рсогг является непосредственно измеряемой, Т - известно. Отметим важные особенности (13):

• отсутствует явная зависимость от

• отсутствует явная зависимость от т0

• в выражение входят либо конструкционные константы, либо известные величины, либо непосредственно измеряемые величины.

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

• Улучшается процесс сходимости, увеличивается вероятность захвата при заданном соотношении сигнал/шум и ошибке начального целеуказания по частоте.

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

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

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

Выберем вектор состояния в виде

х=

9

<Р' в

где:

<Р в

псевдодоплеровская фаза;

производная псевдодоплеровской фазы по времени; величина, для которой справедливо соотношение

р = в + Л • <р.

Уравнение динамики системы в дискретном представлении можно записать как:

"1 г 0"

= 0 1 0 хх*+£*+1 где:

0 0 1

"1 г 0"

р = 0 1 0 - матрица перехода от состояния к к состоянию к+1;

0 0 1

- вектор-столбец ошибок с нормально распределенными

компонентами с нулевым средним. Ковариационная матрица для £ равна:

СОУЕ = =

1 2

<7<р 2 Т О

р 2

О

О О

ав-х

Определим набор измерений для обновления состояния фильтра Калмана:

У =

<Р Р

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

р = в + Х-(р Тогда уравнение измерения примет вид:

= Н х

+ Ц

1 О о X 0 1

+ ц

Ковариационная матрица вектора измерений:

2

соуц = К =

О

О <т,

Здесь мы предположили, что измерения (ри р независимы.

При синтезе фильтра учтем соотношения малости между основными величинами, а именно:

• величина -■]рп не превышает 10~2 оборота в установившемся режиме.

Среднее квадратическое отклонение измерения (СКО) псевдодальности

л/<7^ «30 метров, СКО оценки параметра в -^р33 ~ 1 метра,

12 2 следовательно, Я ■ рп « ръг, <тв .

• Дисперсия измерения фазы аф2 »1 • Ю-4 оборота2,

следовательно, аф

«<та

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

л» eXtr

Pi* 1

л» '

<pt+1 /J «1г + 1

P.. + О",

P21 />11 +

_Pn _

P 33 + a в

r-A<p Г' Д <P T-bp

- расчет сглаженного вектора состояния.

1 -

U.+-7) О7»+

о>~

0 о

Рзз

зз +сгв

коэффициент усиления фильтра.

Р^, =

■ Ри

■ Рг\

"П

v /

+ ст„

+ а

■ Р21 + Pll '^21 -Р21 Р22

I?.!

£

• Рзз

ковариационная матрица сглаженного состояния.

Следовательно, фильтр распался на две квазинезависимые подсистемы -подсистема фазовых компонент и подсистема псевдодальности. Суммарные вычислительные затраты при этом существенно ниже, чем при обновлении единого вектора состояния размерности (3:1).

В пятой главе приводятся результаты разработки оптимального по критерию точность-быстродействие представления плавающих чисел и основных алгоритмов для работы с числами в таком представлении. Действительно, для навигационного приемника (с учетом динамических диапазонов используемых величин) вполне достаточно относительной точности представления 5*10"9. Стандартные же представления допускают либо тип FLOAT (точность 10"6) либо DOUBLE (точность 10"16). Первый тип не обеспечивает требуемой точности, второй - явно избыточен. Использую тип DOUBLE, мы вынуждены тратить ресурсы процессора на достижение ненужной точности. В качестве альтернативы рассмотрим плавающее число с размером мантиссы 32 бита (один регистр) и

размером экспоненты также 32 бита. Относительная точность такого представления, определяемая размером мантиссы, составляет 5*1 О*10, что достаточно для поставленных выше задач. Расположение мантиссы и экспоненты в отдельных регистрах позволяет реализовывать быстрые алгоритмы для работы с числами в данном представлении. Например, часто встречающаяся при решении навигационной задачи процедура вычисления квадратного корня может быть реализована способом, позволяющим получить более чем двухкратное приращение скорости вычисления. Приведены примеры некоторых алгоритмов и их реализация на конкретных процессорах (в частности, на АЯМ922Т).

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

15

V

и

10

5

О

-5

-Ю

О 2000 4000 6000 8000 10000

Т1те, пггсес

Рис. 6. Зависимость ускорения пользователя от времени

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

16ё.

&

I- 6

0

ъ ь

1 6

Э

I

-4 4 5.

2

о

-2

■4

-6

О 2000 40QQ 6000 8000 100GG

Time, msec

Рис. 7. Зависимость ошибки оценки частоты от времени

Представленная на Рис. 7 зависимость ошибки оценки частоты входного сигнала от времени показывает, что в таких условиях:

• Наблюдается устойчивое слежения в течении всего времени моделирования (включая момент начала маневра).

• Максимальная ошибка оценки частоты не превосходит 4 Гц.

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

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

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

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

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

5. На основе анализа динамических диапазонов используемых величин предлагается специальное плавающее представление, являющееся оптимальным с точки зрения точности и вычислительных затрат. Кроме того, предложены эффективные алгоритмы, реализующие наиболее "времяемкие" функции, а именно: тригонометрические и вычисления квадратного корня.

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

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

24 Р в 1 0 4

Основные публикации по теме диссертации:

1. A.Fridman, S.Semenov. "Architectures of Software GPS Receivers", GPS Solutions, Vol.3, No.4, Spring 2000, pp. 58-64. John Wiley & Sons, Inc.

2. A.Fridman, S.Semenov "Architecture of Software of TFAG50 Low-Cost Low Power GPS/GLONASS Receiver", Proceeding of the 14th International Technical Meeting ION GPS-2001, pp.768-777, Salt Lake City, September, 2001.

3. Р.В.Бакитько, П.А.Гридин, В.П.Польщиков, С.А.Семенов, А.Е.Фридман. "Двухчастотный GPS приемник с многоканальным коррелятором на FPGA", Доклад на конференции НИИКП, Москва, 2003

ПРАКТИЧЕСКАЯ РЕАЛИЗАЦИЯ

Изложенные алгоритмы были применены в серийно выпускающемся СР8/0,01ЧА88 навигационном приемнике ТРАС50. Высокие потребительские характеристики последнего наглядно демонстрируют практическую ценность проделанной работы.

Глава 1. Общая структура программных навигационных приемников.

1.1. Основные подходы к построению аппаратно-программных комплексов навигационных приемников.

1.2. Основные типы программных навигационных приемников.

1.3. Основные особенности программных навигационных приемников.

1.4. Области применения программных навигационных приемников.

1.5. Структура аппаратно-программного комплекса цифровой части программного навигационного приемника.

1.5.1. Особенности программных навигационных приемников с постобработкой данных.

1.6. Выводы по главе 1.

Глава 2. Существующие методы поиска, обнаружения и слежения за навигационными сигналами.

2.1. Модуль поиска и обнаружения.

2.2. Слежение за параметрами сигнала и формирование измерений для решения навигационной задачи.

2.3. Алгоритмы верхнего уровня.

2.4. Выводы по главе 2.

Глава 3. Программный многоканальный коррелятор навигационного сигнала.

3.1. Общий подход к построению программного коррелятора.

3.2. Генерация опорного сигнала промежуточной частоты.

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

3.2.2. Практические схемы вычисления опорного сигнала промежуточной частоты

3.3. Генерация битов СА кода.

3.4. Многоканальный аккумулятор.

3.5. Синхронные и асинхронные корреляторы.

3.5.1. Асинхронный коррелятор.

3.5.2. Синхронный коррелятор.

3.6. Выводы по главе 3.

Глава 4. Программная реализация канальных алгоритмов.

4.1. Фазовые соотношения на выходе коррелятора.

4.2. Влияние конечной точности вычислений и сравнение вычислительной емкости различных подходов формирования измерений.

4.3. Построение совместной петли слежения за фазой и задержкой.

4.4. Анализ ошибок, возникающих при переходе к упрощенной модели слежения

4.5. Выделение битов навигационного сообщения в условиях синхронного коррелятора

4.5.1. Определение положения границы бита навигационного сообщения.

4.6. Выводы по главе 4.

Глава 5. Эффективные алгоритмы плавающей арифметики на основе специального представления операндов.

5.1. Общие аспекты, точность и быстродействие.

5.2. Вычисление квадратного корня.

5.3. Вычисление синуса и косинуса.

5.4. Методика тестирование библиотечных процедур.

5.5. Выводы по главе 5.

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

6.1. Тестирование МКК.

6.1.1. Методика тестирования МКК.

6.1.2. Результаты тестирования МКК.

6.2. Раздельное тестирование модулей слежения за фазой и задержкой сигнала.

6.2.1. Методика тестирования петли слежения за фазой сигнала.

6.2.2. Результаты тестирования петли слежения за фазой сигнала.

6.2.3. Методика тестирования петли слежения за задержкой сигнала.

6.2.4. Результаты тестирования петли слежения за задержкой сигнала.

6.3. Тестирование совместной работы петель слеженияза фазой и задержкой сигнала

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

6.3.2. Результаты тестирования совместногй работы петель слежения.

6.4. Выводы по главе 6.

Под программной реализацией навигационного приемника понимается такой подход, при котором все или большая часть операций по цифровой обработке навигационных сигналов и данных выполняется на программируемых процессорах общего назначения, либо на цифровых сигнальных процессорах (Digital Signal Processor, DSP). Толчком к развитию такого подхода оказалось появление новых высокопроизводительных процессоров, например Pentium IV, TMS320C62xx или новое поколение ADSP фирмы Analog Devices серии Tiger Shark на которых, в принципе, можно выполнять цифровую обработку множества навигационных сигналов за практически приемлемое время.

В последние годы сформировалось целое направление исследований с целью создания программно-реализованного GPS приемника (Software GPS Receiver). Развитие программных навигационных приемников происходит по двум основным направлениям:

1. Приемники с обработкой отсчетов промежуточной частоты в режиме постобработки [2], [15], [19], [20];

2. Приемники с обработкой отсчетов промежуточной частоты в режиме реального времени [6], [7], [14], [21].

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

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

Объект исследования настоящей диссертационной работы - полностью программные навигационные приемники.

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

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

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

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

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

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

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

6. Экспериментальная проверка основных программных блоков навигационного приемника.

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

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

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

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

2. Синтезирован оптимальный алгоритм слежения за навигационным сигналом.

3. Доказана эффективность и реализуемость алгоритмов слежения за фазой и задержкой навигационного сигнала на основе фильтра Калмана.

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

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

Положения, выносимые на защиту:

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

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

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

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

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

Основные публикации по теме диссертации:

A.Fridman, S.Semenov. Architectures of Software GPS Receivers. GPS Solutions, Vol.3, No.4, Spring 2000, pp. 58-64. John Wiley & Sons, Inc.

A.Fridman, S.Semenov "Architecture of Software of TFAG50 Low-Cost Low Power GPS/GLONASS Receiver", Proceeding of the 14th International Technical Meeting ION GPS-2001, pp.768-777, Salt Lake City, September, 2001.

Р.В.Бакитько, П.А.Гридин, В.П.Полыциков, С.А.Семенов, А.Е.Фридман. Двухчастотный GPS приемник с многоканальным коррелятором на FPGA. Доклад на конференции НИИКП, Москва, 2003

6.4. Выводы по главе 6

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

2. Результаты, полученные при тестировании петель слежения показали, что разработанные алгоритмы слежения, помимо высокой вычислительной эффективности, обладают высокой точностью, возможностью следить за слабыми сигналами (не более 30 Дб) и в условиях высокой динамики пользователя (свыше 15g).

Глава 7. Заключение

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

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

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

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

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

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

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

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

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

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

1. В. Н. Харисов, А. И. Перов, В. А. Болдин "Глобальная Спутниковая Радионавигационная Система ГЛОНАСС", Москва, ИПРЖР, 1998

2. Gabriele Belle et al "The U. S. Air Force Academy GPS Flight Experiment Using The Navsys TIDGET", Proceeding of the 10th International Technical Meeting ION GPS-97, pp.783-795, Nashville, Tennessee, September, 1997

3. David M. Lin, James B. Y. Tsui "Acquisition Schemes for Software GPS Receiver", Proceeding of the 11th International Technical Meeting ION GPS-98, pp.317-325, Nashville, Tennessee, September, 1998

4. Sergey V. Lyusin, Ilia G. Khazanov, Sergey V. Likhovid "Fast Acquisition by Matched Filter Technique for GPS/GLONASS Receivers", Proceeding of the 11th International Technical Meeting ION GPS-98, pp.307-315, Nashville, Tennessee, September, 1998

5. John J. Schamus, James B. Y. Tsui "Acquisition to Tracking and Coasting for Software GPS Receiver", Proceeding of the 12th International Technical Meeting ION GPS-99, pp.325-328, Nashville, Tennessee, September, 1999

6. Andrey Bochkovski et al "SoftFlex: An Advanced Approach to Design of GNSS Receiver With Software Correlator", Proceeding of the 12th International Technical Meeting ION GPS-99, pp.353-362, Nashville, Tennessee, September, 1999

7. Vimala C. et al "Accord's Next Generation High Performance GPS/WAAS Receiver based on the Soft-Correlator", Proceeding of the 13th International Technical Meeting ION GPS-2000, pp.329-336, Nashville, Tennessee, September, 2000

8. Ville Eerola "Rapid Parallel Signal Acquisition", Proceeding of the 13 th International Technical Meeting ION GPS-2000, pp.810-816, Nashville, Tennessee, September, 2000

9. David M. Lin, James B. Y. Tsui "Comparison of Acquisition Methods for Software GPS Receiver", Proceeding of the 13th International Technical Meeting ION GPS-2000, pp.2385-2390, Nashville, Tennessee, September, 2000

10. David M. Lin, James B. Y. Tsui "An Efficient Weak Signal Acquisition Algorithm for a Software GPS Receiver", Proceeding of the 14th International Technical Meeting ION GPS-2001, pp.115-119, Salt Lake Sity, September, 2001

11. Dr. Chung Yang "FFT Acquisition of Periodic, Aperiodic, Puncture and Overlaidth

12. Code Sequences in GPS", Proceeding of the 14 International Technical Meeting ION GPS-2001, pp. 137-147, Salt Lake Sity, September, 2001

13. Alexander Fridman, Serguei Semenov "Architecture of Software of TFAG50 Low-Cost Low Power GPS/GLONASS Receiver", Proceeding of the 14th International Technical Meeting ION GPS-2001, pp.768-777, Salt Lake Sity, September, 2001

14. Kent Krumvieda et al "A Complete IF Software GPS Receiver: A Tutorial about the Details", Proceeding of the 14th International Technical Meeting ION GPS-2001, pp.789-811, Salt Lake Sity, September, 2001

15. R. Pratt, D. J. Molyneux "Post Processing Algorithms for Translator-Type GPS Receiver", Proceeding of the 15th International Technical Meeting ION GPS-2002, pp.695-702, Nashville, Tennessee, September, 2002

16. David M. Lin, James B. Y. Tsui "A Weak Signal Tracking Technique for a Stand-Along Software GPS Receiver", Proceeding of the 15th International Technical Meeting ION GPS-2002, pp.2534-2538, Nashville, Tennessee, September, 2002

17. John J. Schamus, David M. Lin, James B. Y. Tsui "Real Time Software GPS Receiver", Proceeding of the 15th International Technical Meeting ION GPS-2002, pp.2561-2565, Nashville, Tennessee, September, 2002

18. Jr. Tomas, "Digital Signal Processor and processing method for GPS receivers," US Patent US4821294

19. Alison K. et al. "GPS tracking system," US Patent US5379224

20. Analog Devices, Engineer To Engineer Note EE 24

21. S. Bondarenko et al "A High Energy (up to 120 Gev) Hadron Shower Detector", Nuclear Instruments and Methods, vol. C, pp. 712-732, 1996

22. M.L. Psiaki "Smoother-Based GPS Signal Tracking in a Software Receiver", Proceeding of the 14th International Technical Meeting ION GPS-2001, pp.29002913, Nashville, Tennessee, September, 2001

23. Alexander Fridman, Serguei Semenov "Architectures of Software GPS Receivers", GPS Solutions, Vol. 3, No. 4, Spring 2000, pp. 58-64

24. Verhaegen, Van Dooren "Numerical aspects of different Kalman filter implenentation", IEEE Transactions on Automatic Control, Vol. AC-31

25. W. Parkinson, J. Spilker "Global Positioning System: Theory and Applications", Vol. I, pp. 363, American Institute of Aeronautics and Astronautics, Inc., Washington.

26. Р.В.Бакитько, П.А.Гридин, В.П.Полыциков, С.А.Семенов, А.Е.Фридман. Двухчастотный GPS приемник с многоканальным коррелятором на FPGA. Доклад на конференции НИИКП, Москва, 2003