Содержание к диссертации
Введение
1. Методы решения задач морской навигации в судовой навигационно-информационной сети и постановка задачи исследования 17
1.1 Математическое содержание траекторных задач морской навигации на плоскости и сфере 17
1.1.1 Классификация и выбор решаемых задач в траекторном процессоре судовой навигационно-информационной сети 17
1.1.2 Математическое содержание траекторных задач на плоскости 19
1.1. .3 Математическое содержание траекторных задач на сфере 23
1.1.4. Особенности математического содержания траекторных задач на плоскости и сфере 28
1.2 Базовая структура и пути повышения эффективности работы вычислительных средств судовой навигационно-информационной сети при решении траекторных задач 32
1.3 Алгоритмы координатных преобразований для реализации вращения вектора 39
1.4 Анализ алгоритмов вращения вектора для решения траекторных задач морской навигации в судовой навигационно-информационной сети 46
1.5 Развитие структуры судовой навигационно-информационной сети и постановка задачи исследования 48
2. Синтез алгоритмов дискретного вращения вектора для решения задач морской навигации в судовой навигационно-информационной сети
2.1 Синтез алгоритмов дискретного линейного вращения вектора методом численного интегрирования 51
2.2 Частные алгоритмы дискретного линейного вращения вектора 60
2.3 Геометрия трехмерного вращения вектора. Дискретное кватернионное преобразование 62
2.4 Вычислительные возможности алгоритмов дискретных кватернионных преобразований 2.4.1 Прямые и обратные преобразования 65
2.4.2 Вычисление произведений синусно-косинусных сочетаний 69
3. Исследование сходимости и точности алгоритмов дискретных кватернионных преобразований 75
3.1. Анализ сходимости алгоритмов дискретных кватернионных преобразований 75
3.2 Общая структура ошибки алгоритма дискретного кватернион ного преобразования 77
3.3 Методическая, трансформируемая и суммарная погрешности алгоритма дискретного кватернионного преобразования 80
4. Представление траекторных задач морской навигации алгоритмами дискретных кватернионных преобразований по данным информационных потоков судовой навигационно- информационной сети 86
4.1 Особенности представления траектории судна алгоритмами дискретного кватернионного преобразования 86
4.2 Представление задачи автосопровождения алгоритмами дискретных кватернионных преобразований
4.3 Представление задач автопрокладки и проигрывания маневра алгоритмами дискретных кватернионных преобразований 96
4.4 Определение пройденного расстояния алгоритмами дискретных кватернионных преобразований 99
4.5 Методика выбора шага алгоритма дискретного кватернионного преобразования 101
5. Аппаратурная реализация траекторного процессора судовой навигационно-информационной сети. математическое моделирование и оценка эффективности алгоритмов дискретных кватернионных преобразований 114
5.1. Аппаратурная реализация траєкторного процессора судовой навигационно-информационной сети 114
5.2. Программная реализация траекторных задач алгоритмами дискретных кватернионных преобразований 119
5.3. Результаты математического моделирования траекторных задач алгоритмами дискретных кватернионных
преобразований 122
5.4. Оценка эффективности применения алгоритмов дискретных кватернионных преобразований для решения траекторных задач 128
5.4.1 Количественная оценка эффективности 128
5.4.2 Качественная оценка эффективности 134
Заключение 136
Литература
- Особенности математического содержания траекторных задач на плоскости и сфере
- Геометрия трехмерного вращения вектора. Дискретное кватернионное преобразование
- Общая структура ошибки алгоритма дискретного кватернион ного преобразования
- Представление задачи автосопровождения алгоритмами дискретных кватернионных преобразований
Введение к работе
Диссертационная работа посвящена разработке алгоритмов дискретных линейных кватернионных преобразований, сокращающих и распараллеливающих вычисления при решении задач морской навигации в судовых навигационно-информационных сетях (СНИС).
Развитие информационных технологий и совершенствование технических средств навигации (ТСН) привело к объединению ТСН в рамках судового навигационно-информационного комплекса (СНИК), необходимой составляющей которого, согласно конвенционным требованиям, является транспондер автоматической информационной системы (АИС). Это позволяет судам и оператору системы управления движения судов (СУДС) автоматически обмениваться информацией сгенерированной и обработанной в СНИК, что в настоящий момент играет важную роль в обеспечении безопасности мореплавания. Развитие ТСН, входящих в СНИС приводит к увеличению информационных потоков и росту объема вычислений. Такие задачи, как расчет прогнозируемых и исполнительных траекторий судна [1], определение параметров движения, обеспечивающих безопасное плавание [2], а также элементов сближения маневрирующих судов [3] в настоящее время находят решение в СНИС[4],[5], что позволяет повысить безопасность мореплавания. Многие задачи судовождения решаются как в реальном так и в ускоренном масштабах времени (РМВ и УМВ). Это требует повышения производительности вычислительных средств (ВС) СНИС при высоком уровне их надежности. Такая необходимость обусловлена тем, что рост объема вычислений, реализуемых процессором в единицу времени приводит к повышению нагрузки на ВС, увеличению вероятности случайной ошибки в вычислениях, к росту времени решения задач и снижению точности расчетов в РМВ и УМВ [6],[7]. Традиционное решение проблемы повышения производительности за счет реализации вычислений в мощных универсальных процессорах не всегда эффективно. Такой путь приводит к усложнению аппаратной архитектуры ВС, повышению энергопотребления системы в целом и введению эффективных систем охлаждения [8]. Вышеперечисленные факторы снижают надежность вычислительного блока и повышают его стоимость [9],[10]. Современная статистика по судам, запрашивающим технический ремонт в порту Новороссийск, показывает, что 4% случаев выхода из строя таких терминальный частей СНИС, как новых РЛС/САРП и ЭКДИС обусловлены отказом вычислительных средств и в 9% - отказы средств энергообеспечения, что является подтверждением того, что надежность бортовых ВС остается актуальной проблемой в современных условиях. Одновременное удовлетворение таких противоречивых показателей работы ВС как производительность и надежность характеризует эффективность ВС, на повышения которой ориентированы разрабатываемые в работе алгоритмы.
Проблема производительности является актуальной для многих разработчиков ВС. В прошлом повышение производительности универсальных процессоров в основном происходило за счет увеличения тактовой частоты. Однако в настоящий момент практически все ведущие разработчики ВС, такие как Intel, AMD, Тега, Level One, IBM, Cray Research и др. пришли к тому, что дальнейшее повышение частоты оказалось неэффективным из-за ряда фундаментальных физических барьеров, связанных с повышением потребляемой мощности, выделением тепла, задержками при обращении к памяти, архитектурными ограничениями [11]. Выходом из сложившейся ситуации стало разделение задачи на множество одновременных операций и их распределение среди ряда небольших вычислительных устройств [12],[13],[14],[15],[16],[17]. Именно этот путь в настоящее время выбран ведущими производителями вычислительной техники, как наиболее перспективное решение проблемы повышения эффективности ВС как универсальных, так и специализированных [11],[18]. Эффективность подхода, основанного на реализации вычислений в проблемно-ориентированной аппаратуре, называемой сопроцессорами, расширителями, контроллерами, конверторами и др., заключается в следующем:
- проблемно-ориентированные ВС, реализующие специальные методы реализации конкретных задач, отличаются повышенной эффективностью, в сравнении с универсальными. Практика разработки ВС показала, чем выше производительность, тем уже класс эффективно решаемых ими задач [19];
- предоставляется возможность распараллеливания вычислений и, как следствие, увеличение производительности. Параллельная организация вычислений как на аппаратном, так и на программном уровне лежит в основе разделения вычислительного процесса на множество одновременных однотипных операций, реализуемых в проблемно-ориентированных ВС и является в настоящее время мощным инструментом, позволяющим повысить производительность [18],[19];
- проблемно-ориентированные средства отличаются простой аппаратной архитектурой и высокой надежностью [10], что выгодно отличает их при эксплуатации на подвижных объектах, в частности на борту судна.
Необходимо отметить, что распараллеливание и проблемная ориентация вычислений, выбранные ведущими производителями ВС в качестве генерального пути повышения эффективности ВС (ярким примером является оглашенная корпорацией Intel концепция «Разделяй и властвуй» [11]), не являются новыми, но давно признаны и реализуются в подавляющем большинстве специализированных технических средств, систем и приборов, в том числе навигационных.
Заметим, что аппаратурный состав специализированных ВС, как правило, базируется на основе процессоров общего назначения. Причиной этому является их массовое производство и низкая стоимость. При этом, специализация закладывается включением специальной аппаратуры, архитектура которой реализует проблемно-ориентируемые методы вычислений тех задач, которые требуют выполнения большого объема вычислений традиционными способами. Как правило, к такой аппаратуре относятся ВС работающие в жестком режиме реального времени [19]. Так, основное большинство производителей навигационных радаров, такие как DataBridge, JRC, Kelvin Huges, Furuno, Anschutz (радары линейки Pathfinder/ST) и др. для задач построения радарной развертки в РМВ используют отдельный процессор (как правило универсальный), с параллельно подключенной специальной аппаратурой, такой как графические контроллеры, контроллеры ввода/вывода (часто используется несколько контроллеров для каждого вида отображаемой информации) и др. [20],[21],[22],[23],[24]. Задачи цифровой обработки сигнала в подавляющем большинстве РЛС также реализуются в специальной аппаратуре [25],[26]. В других навигационных приборах, работающих в режиме реального времени, таких как лаги, эхолоты, приемоиндикаторы спутниковых навигационных систем (ПИ СНС), вычисления также реализуются в проблемно-ориентированных ВС [27],[28],[29].
Тенденция реализации вычислений в проблемно-ориентированных ВС, вместе с растущим объемом информации навигационного характера (конвенционное внедрение АИС, обмен данных между приборами по протоколам NMEA, IEE и др.) привели к целесообразности решения навигационных задач в спецпроцессорах и контроллерах реализующих специальные методы вычислений. Примеров - множество, среди них, такие известные современные РЛ станции, как Furuno FR-8051/8111/8251, задачи автоматической радиолокационной прокладки (АРП) в которых решаются в спецпроцессоре [30], линейка РЛС JMA 5110/5106/5104 (производитель JRC), где задачи АРП решаются в рамках отдельной платы на базе спецпроцессора [31], РЛС PATHFINDER®/ST МК2 RADAR, задачи АРП в которой возложены на специальный Tracking Processor [25] и многие другие. Разработке и совершенствованию специальных методов решения навигационных задач как на аппаратном, так и на программном уровне посвящены труды таких ученых как Бранец [32], Д. Парини [33], Van der Veer [34], [35] и др. Обобщая вышеизложенное отметим, что эффективность современных вычислительных средств во многом определяется их аппаратной архитектурой, отображающей проблемно-ориентированные методы и основанные на них алгоритмы. Роль методов вычислений является основополагающей в специализированной аппаратуре, где за счет проблемной ориентации достигаются повышенная производительность и надежность ВС. Вопрос специализации ВС является особо актуальным в бортовой аппаратуре, т.е в терминальной части СНИС, от которой требуется высокая производительность и надежность при решении задач в РМВ и УМВ по данным информационных потоков СНИС. В частности, эффективность решения навигационных задач на современной этапе также определяется проблемной ориентацией ВС, при этом задача совершенствования методов вычислений остается актуальной благодаря росту объема вычислений, встречающимся случаям отказа ВС и систем энергообеспечения.
В общем случае, снижение объема вычислений при обработке информационных потоков СНИС позволяет достичь следующих технических и экономических преимуществ [8], [9], [10]:
- увеличение объема решаемых задач без повышения производительности вычислительных средств;
- уменьшение нагрузки на вычислительные средства и, как следствие, снижение вероятности случайных ошибок;
- возможность реализации вычислений в менее мощных вычислительных средствах, отличающихся пониженным энергопотреблением и простой архитектурой, что повышает надежность вычислительного блока и снижает его стоимость и эксплуатационные затраты.
Таким образом, эффективные методы вычислений и основанные на них алгоритмы должны быть ориентированы на специфику решаемых задач в плане сокращения объема и распараллеливания вычислений. Большинство вычислений навигационного характера, выполняемых при обработке информационных потоков СНИС, описываются аппаратом тригонометрии как на плоскости, так и в пространстве. Наиболее эффективный в настоящее время подход к выполнению тригонометрических преобразований, вращением вектора положен в работах Дж. Волдера, Дж. Меджита, Дж. Уолтера в конце 50-х и в 60-х годах [36], [37], [38]. Результатом стал известный алгоритм Волдера, реализующий ортогональное преобразование плоского ортонормированного базиса и устройство на его основе - CORDIC (Coordinate rotation digital computer - цифровой компьютер для преобразования координат). Далее, в работах российских и зарубежных ученых, таких как Банков В. Д. [39], [40], Смолов В. Б. [41], [42], Каляев А. В. [43], Духнич Е. В. [44], [45], [46], [47] Деревесков С. О. [48], Д. Парини [33], Van der Veer [34],[35],[49], J. Delosme [50], [51], S. Hsiao [52], [53], G. Cavalaro [54], [55], S. Paul [56], A. Elster [57], S. Freeman [58] и др. проведено обобщение алгоритмов вращения вектора и рассматривались вопросы реализации различных математических и прикладных задач (в том числе и навигационных) алгоритмами дискретных линейных преобразований (ДЛП), основывающимися на алгоритме Волдера.
Однако при весомом сокращении объема вычислений алгоритмы ДЛП имеют ряд существенных недостатков. Во-первых, независимо от величины угла для его отработки необходимо выполнить фиксированное количество итераций, равное разрядности углов. Поэтому такие алгоритмы неэффективны в задачах морской навигации, требующих пошагового вращения вектора на малые углы, таких как задачи автосопровождения, проигрывания маневра расхождения судов и др. Во-вторых, данные алгоритмы реализуют «псевдовращение» и им присущ такой недостаток, как удлинение вектора. Использование любого из существующих методов компенсации удлинения [59], [60] (модифицированных алгоритмов Волдера) вызывает значительное усложнение вычислений.
Альтернативный подход к реализации вращения вектора предложен в работах Владимирова В. В. [61], [62], [63], [64]. Предложенные алгоритмы выполняют «естественное», а не «псевдо», трехмерное дискретное линейное вращение вектора вокруг произвольно направленной оси в шкале угловой метрики, методом численного интегрирования. Такие алгоритмы имеют преимущества в сравнении с другими при реализации вращений на малые углы, в частности, исключается удлинение вектора. Более того, базовым операндом вращения, реализуемого этими алгоритмами является трехмерная (а не плоская как в алгоритме Волдера) матрица, в общем случае реализующая кватернионное преобразование, что позволяет существенно сократить объем вычислений в трехмерном пространстве. Однако использование предложенных алгоритмов для решения задач навигации проблематично по следующим причинам. Реальные процессы, реализацию которых необходимо описать, являются функциями от времени, тогда как аргументами реализуемых преобразований являются углы. Отсутствие временной зависимости не предоставляет возможности учета изменения параметров движения судна и требует перемасштабирования углов вращения на каждом шаге. Поэтому, решение задач, как в РМВ, так и в УМВ будет проблематичным: нарушение интервалов отсчета данных и индикации результатов, усложнение организации вычислительного процесса ввиду невозможности учета изменения шага, и, как следствие, снижение точности отработки и затруднение её итоговой оценки. Кроме того, метод численного интегрирования в этих алгоритмах реализован только по формуле прямоугольников (интегрирование с недостатком), что ограничивает точность вычислений.
Целью диссертационной работы является разработка алгоритмов дискретных кватернионных преобразований (ДКП), реализующих трехмерное вращение вектора в шкале времени и обеспечивающих сокращение объема вычислений, что способствует повышению надежности бортовых вычислительных средств входящих в состав СНИС и, как следствие, повышению безопасности мореплавания. Исходными данными для синтеза являются результаты анализа математического содержания и известных методов реализации навигационных задач по данным информационных потоков СНИС.
Результаты работы направлены на сокращение объема и распараллеливание вычислений, при реализации задач морской навигации в судовой навигационно-информационной сети.
Объектом исследования являются алгоритмы для решения траекторных задач морской навигации по данным информационных потоков СНИС: спутниковых навигационных систем (СНС) и автоматических идентификационных систем (АИС) в траекторном процессоре СНИС, как составной части терминала телекоммуникаций.
Основные теоретические положения и прикладные вопросы, решенные автором, изложены в пяти разделах диссертационной работы.
В первом разделе приводится классификация задач навигации с целью выбора из них наиболее проблематичных с точки зрения вычислительных мощностей, требуемых для их реализации. На основе математического содержания задач навигации производится выбор наиболее эффективного метода решения - алгоритмы координатных преобразований, основанных на вращении вектора.
Приводится проблемно-ориентированный состав задач, решаемых в судовой навигационно-информационной сети (СНИС) на современном уровне и обосновывается целесообразность введения в состав вычислительных средств СНИС траєкторного процессора для достижения максимальной эффективности разрабатываемых алгоритмов. Приводятся и исследуются известные алгоритмы рационального вращения вектора. По результатам анализа приведенных алгоритмов ставится задача синтеза и формулируется задача исследования.
Второй раздел посвящен синтезу алгоритмов дискретного линейного вращения вектора методом численного интегрирования по Стилтьесу. Из общего вида алгоритма получены частные формы. Анализируется геометрия
координатного преобразования, реализуемого полученными алгоритмами. По результатам анализа алгоритмы получают обобщенное название - алгоритм дискретного кватернион ного преобразования (ДКП). Исследуются вычислительные возможности алгоритма ДКП. В третьем разделе доказывается сходимость алгоритма ДКП, исследуются общая структура ошибки алгоритма ДКП, приводятся и выводятся формулы для количественной оценки её составляющих. В результате получена формула суммарной погрешности алгоритма ДКП, на основании которой базируется оценка интервала сходимости в зависимости от заданной величины допустимой ошибки, что необходимо для практического использования алгоритма при решении задач навигации по данным информационных В четвертом разделе приводится обобщенный подход к описанию траектории судна алгоритмами ДКП. Описывается применение алгоритмов ДКП для решения конкретных навигационных задач, решаемых в терминалах СНИС, таких как автосопровождение, автопрокладка, проигрывание маневра и определение текущего значения пройденного расстояния. Приводится методика выбора шага алгоритма ДКП в зависимости от требуемого интервала решения задачи и величины допустимой погрешности.
В пятом разделе описывается примеры аппаратурной и программной реализации алгоритма ДКП, приводятся результаты проверки теоретических оценок точности, выполненной методом математического моделирования на основе данных реальных информационных потоков. Доказывается состоятельность применения алгоритмов ДКП для решения навигационных задач в СНИС путем сравнительного анализа вычислительной сложности задач навигации, реализованных алгоритмами ДКП, как описано в разд. 4 и тех же задач, но решенных ранее известными методами.
Научная новизна представлена следующими результатами: - разработан новый класс алгоритмов, получивших название алгоритмов дискретных кватернионных преобразований и реализующих вращение вектора в трехмерном пространстве в шкале времени. В отличие от ранее известных, алгоритмы ДКП реализуют вращение вектора по формулам интегрирования различных порядков - прямоугольников, трапеций и парабол;
- исследована и доказана сходимость алгоритмов ДКП;
- получены формулы оценки трансформируемой и суммарной погрешностей алгоритма ДКП, предложена методика выбора шага алгоритма ДКП в зависимости от заданного интервала решения задач и допустимой ошибки вычислений;
- на основании полученных результатов исследования предложен обобщенный подход к реализации траекторных задач алгоритмами ДКП по данным информационных потоков СНИС.
Практической ценностью полученных в диссертации результатов является снижение объема вычислений при обработке информационных потоков СНИС и возможность распараллеливания вычислений в рамках предложенного алгоритма ДКП при решении задач морской навигации, что позволяет увеличить объем (перечень) решаемых вычислительными средствами задач без повышения их мощности, а, следовательно, повысить надежность и уменьшить аппаратурную сложность, энергопотребление и стоимость вычислительных средств терминалов СНИС.
Исследования проводились с использованием методов математического аппарата линейной алгебры, дифференциального и интегрального счисления, дискретной линейной алгебры, теории рядов и математического моделирования.
При выполнении работы использовались полученные самостоятельно автором теоретические результаты и совместные разработки, выполненные на кафедре «Технические средства судовождения» Морской государственной академии им. адмирала Ф. Ф. Ушакова.
Особенности математического содержания траекторных задач на плоскости и сфере
В настоящее время в СНИК решается практически полный перечень задач навигации [68], в том числе и выделенные для рассмотрения в диссертационной работе траекторные задачи. Резолюцией ИМО А.817, сформулировавшей эксплуатационные требования к электронным картографическим навигационно-информационым системам (ЭКНИС), или ECDIS на базе электронных навигационных карт (ЭНК) практически определен их базовый приборный состав: - РЛС (САРП); - приемоиндикатор (ПИ) GNSS; - гирокомпас (ГК); -лаг; центральный процессор, решающий основные навигацинно-информационные задачи ECDIS и являющийся диспетчером системы; - контролеры периферийных устройств; - монитор ECDIS.
Введение АИС в состав СНИК обеспечивает возможность обмена информацией с другими участниками движения и оператором системы управления движения судами, образуя тем самым навигационно-информационную сеть. В результате СНИК является составной (терминальной) частью систем, сетей и устройств телекоммуникаций (специальность 05.12.13). Обобщенная структура СНИК, учитывающая современный приборный состав, представлена на рис. 1.2.
Наличие информационного канала АИС позволяет обновлять навигационную информацию в СНИК и обмениваться ею с другими участниками движения в режиме реального времени, образуя систему телекоммуникаций - судовую навигациошю-информационную сеть, структура которой представлена на рис. 1.3
Состав задач, решаемых в СНИК приведен на рис. 1.5. Современный этап характеризуется развитием новых технических средств навигации (ТСН) и информационных систем связи отдельных участников движения, что увеличивает объем информационных потоков в СНИС и расширяет круг решаемых в СНИК задач и, значит, увеличивает объём вычислений. Так, конвенционное внедрение АИС предполагает учет маневренных элементов судна при расхождении и, соответственно, возможности прогноза траектории, как собственного судна, так и судов-целей. Современный этап развития ТСН характеризуется также внедрением средств высокоточной обсервации [69] (различные варианты DGPS) и стабилизации траектории [70], что позволяет осуществлять практически непрерывный контроль за местоположением в сложной навигационной обстановке.
Необходимо отметить, что в настоящее время широкое внедрение, сравнительно низкая стоимость и высокая производительность универсальных вычислительных средств (процессоров общего назначения) позволяет программно реализовать все вычисления на их базе. Однако такой путь реализации вычислений имеет ряд существенных недостатков. Увеличение объема вычислений в РМВ и УМВ приводит к повышению нагрузки на универсальные ВС. Как следствие, повышается вероятность случайной ошибки в вычислениях и достоверность полученных результатов снижается [8],[71]-[74]. Таким образом, очевиден факт, что увеличение объема информационных потоков в СНИС требует повышение производительности универсальных ВС в терминалах СНИС. Однако такой путь не всегда оптимален, так как высокопроизводительные универсальные ВС обладают большим энергопотреблением и не отличаются высокой надежностью, которая является неотъемлемой характеристикой бортовых ВС. Этот факт привел к тому, что на современном этапе высокопроизводительные универсальные ВС редко используются в судовых терминалах СНИС.
Аппаратурные и технологические проблемы, связанные с увеличением объема вычислений приводят к целесообразности реализации вычислений в специализированных вычислительных средствах (включения в вычислительный блок дополнительных процессоров, специализированных вычислительных устройств - контроллеров и конверторов). Специализированные (проблемно-ориентированные) ВС, в сравнении с универсальными, имеют следующие преимущества: - более простая архитектура обеспечивает более высокую степень их надежности; - более высокая производительность вследствие специализации ВС и параллельной организации вычислительного процесса; - уменьшение материальных затрат на техническую эксплуатацию и в случае ремонта; - повышается живучесть вычислительного блока, так как выход из строя проблемно-ориентированного ВС не отражается на решении других задач.
На современном этапе практически все ТСН, в том числе решающие траекторные задачи, имеют в своем составе специализированные ВС. Так, в подавляющем большинстве современных ЭКНИС и РЛС задачи построения изображения, обработки сигнала, большинство задач фильтрации реализованы в специализированных процессорах, в состав которых входят контроллеры, фильтры, конверторы с аппаратурной или программной реализацией вычислений.
Выделенные для рассмотрения траекторные задачи во многих САРП и ЭКНИС также реализованы в проблемно-ориентированных вычислительных средствах. Примеров такой реализации множество. От сравнительно старых моделей, например ЭКНИС «DataBridge 2000», где решение траекторных задач возложено на навигационный контроллер [20], до современных моделей, таких как Furuno FR-8051/8111/8251, задачи автоматической радиолокационной прокладки (АРП) в которых решаются в спецпроцессоре [30], линейка РЛС JMA 5110/5106/5104 (производитель JRC), где задачи АРП решаются в рамках отдельной платы на базе спецпроцессора [31], РЛС PATHFINDER/ST МК2 RADAR, задачи АРП в которой возложены на специальных Tracking Processor [25] и многие другие
Реализация задач в проблемно-ориентированном вычислительном устройстве имеет следующие положительные особенности: - снижается нагрузка на универсальные вычислительные средства, освобождаются мощности для реализации других задач; - повышается достоверность результатов вычислений, производимых в рамках всего вычислительного блока на рис. 1.2; - повышается надежность вычислительного блока в целом; - снижаются эксплуатационные затраты увеличивается срок эффективной эксплуатации.
Геометрия трехмерного вращения вектора. Дискретное кватернионное преобразование
Полная аналогия параметров вращений в (2.33) и (2.31) позволяет сделать вывод о том, что алгоритм (2.30) реализует кватернионное преобразование с параметрами вращения (2.31). Матричная запись такого преобразования имеет вид R(t) = A(t)R0, (2.34) or2(/)+[l-a2(0]cos6»(0 a(!)P(t)[l-cos0(t)]-y(t)sme(t) a(t)fi(t)W-cose(t)] + y(t)s\n9(t) /72(0 + [l- 2(0]cos ?(0 -» «( MOP - cos 0(0] - КО sin W) Ж0К0И - cos 0(t)] + a(t) sin 9(t) где ДО = a{t)y{t){\ - cos 0(0] + /?(0sin 0(0 1 /7(0К0П - cos 9(t)] - or(0 sin (0 r2(0+P- №080(0 , Ввиду того, что ДЛВ (2.30) реализует кватернионное преобразование (2.32), в дальнейшем изложении алгоритм (2.30) назван алгоритмом дискретного кватерн ионного преобразования (ДКП).
Очевидно, что ДКП (2.30), являясь наиболее полным и общим случаем трехмерного вращения вектора, будет иметь свои частности. Эти частности, являясь составляющими общего вида ДКП и их комбинациями, дают ряд разновидностей как плоских, так и пространственных координатных преобразований. Рассмотрим эти разновидности, а конкретнее -вычислительные возможности алгоритма ДКП.
При прямых координатных преобразованиях исходный вектор До ={ха,Уо,2о} или его модуль R = {ДДО} (координата R может принадлежать любой из осей X,Y,Z) разворачиваются по частным углам ах,ау,аг алгоритма ДКП (2.30), в результате получаем координаты {x,y,z} преобразованного вектора R . Рассмотрим частные случаи такого вращения и их комбинации. Для этого дополним (2.30) выражениями для отработки углов [67] операторами направления вращения \\},еслиаи = 0 и зададим начальные условия 1й,ат =a„ie{x,y,z}. (2.37) Для вращения в плоскости XOY (2.37) следующим образом R0,ax0=0,ayO =0,al0=a:. (2.38)
С учетом (2.38) алгоритм ДКП (2.30), реализующий вращение, например по формуле трапеций (2.28), сводится к виду Я 1-Я+ ..(з ,- м)Д«,. (2-39) (2.40) - матрица частного вращения на угол а,. При , = 0 получим вектор R = {xM,yM,zliX), представлягощий собой результат преобразования Я - Е R0, где Es = rcosaz -sina; 0 sma. cosa, 0 0 0 1 соответствующие вращениям в плоскостях YOZ и XOZ. Реализуемые алгоритмом ДКП 3 поворота по углам а, принято называть частными вращениями.
Поочередно задавая а, и последовательно выполняя преобразования R-E,R0 для каждого le{x,y,z} получим результат, соответствующий транспозиции матриц частных вращений системы координат XYZ, т.е. R=FRD, где F = E,EaEtt, l,m,nz{x,y,z},i m n. Таким образом, при последовательной реализации частных вращений по углам а, алгоритм ДКП реализует еще б различных преобразований в трехмерном пространстве.
Задавая в алгоритме (2.30) один из операторов Q =0 и отрабатывая алгоритм по двум оставшимся Q , а затем реализуя ДКП по неотработанному углу, получим реализацию преобразования вида R=ElAm nR0, где АПЛ матрица, полученная из (2.33) путем нулевого задания направляющего косинуса с / -й осью системы координат. Меняя очередность отработки, получим реализацию преобразования вида R = AmjiElR i. Покажем порядок выполняемых вычислений на примере выполнения алгоритмом (2.28) преобразования R=AXjEj0. (2.45)
Алгоритму ДКП задаются начальные условия (2.38) и вычисляется результат преобразования (2.40) по алгоритму (2.39). Принимая полученные координаты R за начальные, зададим алгоритму ДКП начальные данные х0=х,Уа =У 2й =z axo =ах,ау0=ау,ал =0. (2.46) С учетом (2.46) алгоритм (2.28) сводится к виду і+і= і+тД3г/"гі-і)Да 1 Л+і=Л-уГх(Зг,-2,ч)Д«,; (2-47) ZM =-4,( -xhl)Aay +-I(2y,-yl_l)baI+zl. При = =0 полученные координаты вектора R = {xM,y, zM}являются результатом преобразования (2.45). Таким образом, алгоритм ДКП также реализует 6 преобразований вида R=E,AIIII1R0 и R=Ar) EiR0. Наконец, при задании начальных условий R0,ccx0 =а1,ауО=ау,а:0 =а: (2.48) алгоритм (2.30) реализует одновременное вращение по углам а, или, с учетом равенств ах = ав,ау = pO,az = уб, (2.49) кватернионное преобразование (2.33). Обобщая вышеизложенное, отметим, что алгоритм ДКП реализует 16 различных прямых преобразований в трехмерном пространстве.
Общая структура ошибки алгоритма дискретного кватернион ного преобразования
Для рассмотрения общей структуры ошибки запишем выражение для приращения Ak координаты к в уравнениях (2.1) в следующем виде Ak(t) = \h{t)co, {t)dt - \l{t)o)h (t)dt, (3.8) t і где k,l,hs{x,y,z}, кФІ Ь. Дифференцируя (3.8), получим dbk(t) = d[h{t)da,{t)}-d[l(t)da„(t)]. Используя формулу разложения дифференциала произведения функций, запишем dAk(t) = h{l)d[da, (/)] + da, (t)dh(t) - l(t)d[dah(t)] - dah (t)dl(t). (3.9)
Полагая, что на интервале Д/=/(+,-/,- разности SAk = dAk,Sh(t) = dh(t), SI(t) = dl(t),S[da,(t)] = d[dal(t)],S[dah(t)] = d[dah(t)] являются погрешностями координат и дифференциалов углов, перезапишем (3.9) в виде SAk(t) = h(t)S[da, (/)] + da, (/) &(/) - l(t)S[dah (/)] - dah (/)#(/). (3.10) При численном интегрировании (3.8) на интервале Л/ можно записать „, (/)Л А(0,/( /(/), А«/, da,{t\Lah da„(t), (3.11)
С учетом (3.11) выражение (3.10) примет вид Й 1+ = [й,й агй +AallSh,] + [-lA i -Аа„Д] + 0+], (3-12) где //і(/+1) - методическая погрешность координаты і, появившаяся при численном интегрировании (3.8) на шаге Д/. Если в формуле (3.12) величины ЗИ„(Я„$&ацМ),АНМ) являются погрешностями текущих координат и приращений углов алгоритма (2.30), то «5ДАг/+ будет погрешность приращения вычисляемой к -ой координаты или самой координаты на і + 1-м шаге. Для оценки предельной ошибки 5fi+{ функции f = ke {x,y,z} зададим - Да, =тах{Даи , Давида,, }; R где -у= - компоненты координат, геометрическая сумма которых равна л/3 модулю вращаемого вектора R, что соответствует применению алгоритма (2.30) для реализации траекторных задач, как будет показано в подразд. 4.1 -4.4.
Положим также, что знаки слагаемых (3.12), выделенных в квадратные скобки одинаковы. При этом с учетом (3.13) выражение (3.12) примет вид 2R $м=гЬа&+- ёЬам+мЬ, (3.14) где //(н-1) - методическая погрешность вычисления координаты /на / +1 -м шаге. Из (3.14) видно, что погрешность SfU]n координате на текущем шаге является следствием её наличия на предыдущем ($/,), а также погрешности в приращении угла SAaH].
Таким образом, первое слагаемое (3.14) представляет собой трансформируемую погрешность Sf и имеет накапливающийся характер.
Для 0+ 2)-го шага источником трансформируемой погрешности будут также второе и третье слагаемые (3.14). Заметим, что величина Sf, в (3.14), определяющая значение SffT+l, является ошибкой в координатах с предыдущего шага и будет зависеть от ошибок исходных координат Sf0 и погрешностей, появляющихся и накапливающихся в процессе вычислений. Очевидно, что убудет присутствовать только на первом шаге и является составной частью $j+t.
Второе слагаемое (3.14) представляет собой погрешность в текущей координате вследствие ошибки приращений текущих углов SAal+l, а, следовательно, присутствует и будет накапливаться как сумма на каждом шаге. Обозначим такую ошибку Sf .
Появление методической ошибки /І/[ также свойственно каждой итерации алгоритма (2.30), и, следовательно, эта погрешность суммируется по всем итерациям и составит величину pf-J.
Учитывая рассмотренный характер накопления погрешностей, и производя суммирование выражения (3.14) по всем / + 1 итерациям получим общую структуру погрешности алгоритма (2.30) в координате на / +1 - м шаге 8fM=Sf0+df?+ Sf%+nl{, (3.15) где -#;г=4ї ; (зле) -/й =ЇХ,. (3-17) Аналитические зависимости методической и трансформируемых погрешностей, а также рабочие формулы, связывающие значения допустимой погрешности в вычислениях Мдіті шага Д/ и интервала Т, приводятся в следующем подразд.
Представление задачи автосопровождения алгоритмами дискретных кватернионных преобразований
При реализации вычислений с шагом Д; пройденное судном расстояние определяется по формулам (1.50), (1.51). В подразд. 4.2 приводился порядок реализации вычислений алгоритмом ДКП по формуле (1.50) (вычисления по п.п. а) - г), результатом которых являлись значения (4.33). (4.35)). В настоящем подразделе предлагается альтернативный подход к реализации вычислений с использованием алгоритма ДКП, реализующем вращение в трехмерном пространстве.
Путь судна, пройденный за время Д/, определяется как модуль разности ам последовательных положений геоцентрических векторов Ri={xl,yi,zi} и RM={xM,yM,zHl}. Очевидно, что а,+1 имеет координаты а,={Д „Ду„Дг,}, (4.44) а пройденное на шаге расстояние равно AsH 0,1=7 /2+ + /1. (4-45)
Вычисления по формулам (4.44), (4.45) выполняются алгоритмом ДКП следующим образом. На текущий момент координаты геоцентрического вектора Rl = {xl,y,,zl) известны из задачи отработки траектории (см. подразд. 4.1). Отработка траектории судна алгоритмом (2.30) по приращениям Д , и дя, осуществляется поворотом вектора й,={х,, ,г;} на углы (4.8).
Отметим, что преобразования (4.8) реализуются алгоритмом ДКП по п. б) подразд. 4.2 и содержат одну итерацию плоского вращения и две операции умножения. По координатам Я, ={x,,y,,z,.} и приращениям (4.8) алгоритмом ДКП рассчитываются текущие значения приращений (4.44) и координаты вектора Ri+l ={x,+i,yMl,z,+1}. Алгоритм (2.28), на текущем шаге реализующий отработку траектории и вычисляющий приращения (4.44), имеет вид (4.46). Для определения Д по формуле (4.45) алгоритму ДКП необходимо реализовать два плоских вращения (см. алгоритмы вычисления модуля при начальных данных s0=0. Количественный состав преобразований, выполняемый алгоритмом ДКП на шаге Д/ при определении пройденного расстояния, приведен в табл. 4.3,
Отметим, что определение пройденного судном расстояния вращением геоцентрического вектора в трехмерном пространстве требует выполнения алгоритмом ДКП большего количества операций, чем на плоскости, однако при выполнении вычислений в траекторном процессоре увеличение времени решения будет незначительным.
Количество и точность вычислений, производимых алгоритмом ДКП при решении этой и вышеприведенных задач зависит от значения шага At, методика выбора которого приводится в следующем подразделе.
Траекторный процессор Центральныйпроцессор Сложение(вычитание) Умножение Вращение Деление п итераций одна итерация 3 2 2 2 4,5. Методика выбора шага алгоритма дискретного кватернионного преобразования Напомним, что шаг At = const выбирается для каждого порядка п є {0,1,2} алгоритма ДКП (2.30) исходя из заданного интервала решения Т и величины допустимой погрешности вычислений Mdun. Ниже приводится методика выбора шага.
Реализация траекторных задач по алгоритму ДКП выполняется набором прямых и обратных преобразований векторов. Прямые преобразования выполняются с шагом At, которому соответствуют текущие приращения углов, а обратные - с наперед заданными приращениями угла вращения Да,. Для выбора шага исходя из интервала Т и требуемой точности решения траекторных задач необходимо оценить погрешности каждого вида преобразования. Основная формула для оценки предельной ошибки вращения вектора методом численного интегрирования получена в подразд. 3.3 (3.32).
Очевидно, что ошибки в координатах, возникающие при реализации первого преобразования, будут являться ошибками начальных данных (Sf0) для второго и так далее.
С помощью формул (3.32), (3.33) оценим величину предельной ошибки для различных интервалов Т и порядков п алгоритма ДКП. Отметим, что для траекторных задач погрешности 6/0 и SAa в (3.32) представляют собой максимальные ошибки в координатах и приращениях координат судна Sf0=max{S p,SX\, (4.48) SAa = тах{бА р,ЗАЛ]. (4.49)
Так как ошибки (4.48) и (4.49) в общем случае имеют вероятностную природу, то их учет весьма затруднителен. Очевидно, что вне зависимости от используемого метода вычисления погрешности (4.48), (4.49) будут влиять на точность результатов вычислений. Поэтому для выработки обобщенной методики выбора шага алгоритма ДКП и возможности сравнения результатов вычислений с истинным эталонным значением текущие и прогнозируемые координаты судна принимаются за истинные, а ошибки (4.48), (4.49) -равными нулю. В этом случае предельная ошибка в координате (3.32) зависит только от величины максимальной методической ошибки на итерации /ІМ И значения
Да, выбираемого из условия (3.27). Как видно из формул (3.18) - (3.20) значение // зависит от скорости изменения параметров движения судна, а также их производных.
