автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему: Дискретное преобразование Фурье неэквидистантных временных рядов
Автореферат диссертации по теме "Дискретное преобразование Фурье неэквидистантных временных рядов"
На правах рукописи
Широков Олег Юрьевич
ДИСКРЕТНОЕ ПРЕОБРАЗОВАНИЕ ФУРЬЕ НЕЭКВИДИСТАНТНЫХ ВРЕМЕННЫХ РЯДОВ
Специальность 05.13.18 - "Математическое моделирование, численные методы и комплексы программ"
Автореферат диссертации на соискание ученой степени кандидата технических наук
Работа выполнена на кафедре информационных систем и технологий Государственного образовательного учреждения высшего профессионального образования «Самарский государственный аэрокосмический университет имени академика СП. Королева»
заслуженный работник высшей школы Российской Федерации, доктор технических наук, профессор С.А Прохоров
доктор технических наук, доцент В.И. Батищев
кандидат технических наук, доцент А.Г. Храмов
Ведущая организация: Федеральное государственное унитарное
предприятие НИИ «Экран» (г. Самара)
Защита состоится Л!Ь иссыЩ 2004 года в 10 часов на заседании диссертационного совета Д 212.215.05 при государственном образовательном учреждении высшего профессионального образования «Самарский государственный аэрокосмический университет имени академика СП. Королева» по адресу: 443086, г. Самара, Московское шоссе, 34
С диссертацией можно ознакомиться в библиотеке государственного образовательного учреждения высшего профессионального образования «Самарский государственный аэрокосмический университет имени академика СП. Королева»
Автореферат разослан » 2004 г.
Ученый секретарь диссертационного совета д.т.н., профессор
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность темы. Дискретное преобразование Фурье (ДПФ) лежит в основе широкого круга задач современной цифровой обработки сигналов, главной из которых остается спектральный анализ. Совершенствование элементной базы и методов проектирования позволило значительно расширить возможности аппаратной и программной реализации алгоритмов, повысить точность, быстродействие и другие показатели эффективности. Систематизации данных и разработке новых алгоритмических решений вычисления ДПФ посвящено множество работ как отечественных исследователей (Агаян С. С, Ярославский Л. П., Лабунец В. Г., Чернов В. М. и др.) так и зарубежных (Кули, Тьюки, Виноград, Нуссбаумер и др.).
В последнее время возрастает интерес к анализу характеристик неравномерно дискретизированных последовательностей, когда интервал дискретизации не является постоянной величиной. Подобными последовательностями представляются результаты измерений при решении разнообразных практических задач, например:
- статистические измерения с применением адаптивных систем сбора и обработки информации;
- неточность датирования в многоканальных системах;
- дискретизация с пропусками, сбоями наблюдений;
- стохастическое и квазистохастическое кодирование;
- принципиальная невозможность получения равномерных отсчетов в ходе проведения биомедицинских, теплофизических, океанологических и океанографических исследований и т.д.
В настоящее время сформировались три основных направления статистических измерений вероятностных характеристик неэквидистантных временных рядов (НВР):
- оценка без учета нерегулярности временного рада;
- оценка с предварительным восстановлением ряда в промежуточных точках;
- оценка без восстановления ряда и использованием только существенных от-
Первые два направления ориентированы на применение классической теории оценивания, третье является наиболее актуальным и требует разработки новой теории оценки характеристик, принципов построения и проектирования видов обеспечения и аппаратно-программных средств.
Другим аспектом исследований является повышение эффективности вычислений ДПФ. Следует отметить, что общая сложность алгоритма определяется не только числом арифметических операций — алгебраической сложностью, но и количеством необходимой памяти, стоимостью вспомогательных операций. Эффективность может быть существенно снижена излишней структурной сложностью или некорректной аппаратно-программной реализацией. Отсюда
вытекает основная задача проектирования - соблюдения баланса между перечисленными составляющими в рамках конкретной задачи.
Важным аспектом цифровой обработки является то, что современные динамические системы требуют создания методов вычисления ДПФ по ограниченному набору данных. При этом большее внимание уделяется качественной оценке характеристик сигналов в виду того, что обычно погрешность алгоритмической оценки имеет тот же порядок, что и погрешности, вызванные сокращением объема выборки, нерегулярностью дискретизации процесса и прочими ошибками представления исходного сигнала.
Таким образом, исследование алгоритмов и разработка аппаратно-программных средств оценки ДПФ НВР без восстановления отсчетов является актуальной задачей. Поставленная задача решалась в рамках темы госбюджетной НИР "Разработка методов и прикладных программ моделирования, оптимизации и обработки результатов научных исследований" Самарского государственного аэрокосмического университета (СГАУ).
Целью диссертационной работы является разработка, теоретическое и экспериментальное обоснование алгоритма и метода вычисления ДПФ неравномерно дискретизированных последовательностей, использующего только существенные отсчеты, обладающего низкой арифметической и структурной сложностью, высокой точностью и быстродействием, возможностью вариации параметров алгоритма с целью достижения требуемой точности. Для достижения поставленных целей необходимо:
- провести обзор и сравнительный анализ современных алгоритмов ДПФ, их структурной и алгоритмической сложности;
- разработать обобщенную классификацию способов повышения эффективности алгоритма;
- разработать алгоритм вычисления ДПФ НВР без восстановления пропущенных отсчетов;
- разработать дескрилторный метод вычисления ДПФ НВР, отличающийся повышенным быстродействием по сравнению с прямым методом;
- разработать и реализовать имитационную модель алгоритма для анализа методической погрешности оценки ДПФ НВР;
- провести вычислительные эксперименты для исследования свойств разработанного алгоритма на примере модельных и реальных выборок данных.
Методы исследований. Результаты исследований базируются на положениях теории вероятностей и математической статистики, теории случайных процессов и потоков событий, а также использования системного анализа, численных методов и методов имитационного моделирования. Научная новизна:
- алгоритм оценки ДПФ НВР без восстановления пропущенных отсчетов;
- дескрипторный метод оценки ДПФ НВР и его модификации, отличающийся повышенным быстродействием при сохранении точностных характеристик;
- результаты анализа быстродействия и методической погрешности предлагаемого алгоритма методом имитационного моделирования.
Практической ценностью обладают:
- структуры дескрипторных вычислителей ДПФ;
- комплекс программ имитационного моделирования и оценки ДПФ НВР без восстановления пропущенных отсчетов;
- зависимости оценки ДПФ от специфических характеристик неравномерно дискретизированных сигналов различной природы;
- методика построения дескрипторных вычислителей.
Публикации. По результатам выполненных исследований опубликовано 9 работ, из них 6 статей и тезисы докладов.
Апробация результатов работы. Основные положения докладывались:
- на научно-технической конференции с международным участием "Датчик-2004" (г. Судак, 2004);
- на всероссийской научно-технической конференции "Актуальные проблемы радиоэлектроники" (г. Самара, 2003);
- на межвузовской научно-практической конференции "Компьютерные технологии в науке и образовании" (г. Самара, 2002);
- на заседаниях кафедр "Информационные системы и технологии" и "Радиотехника" СГАУ.
Результаты работы внедрены в учебном процессе кафедры "Информационные системы и технологии" по дисциплинам "Теория информации" и «Проектирование автоматизированных систем научных исследований», используются в ФГУП НИИ "Экран" и инженерно-медицинском центре "Новые приборы" (г. Самара).
Основные положения, выносимые на защиту:
- алгоритм оценки ДПФ неэквидистантных временных рядов без восстановления пропущенных отсчетов;
- дескрипторный метод оценок ДПФ неэквидистантных временных рядов, отличающийся повышенным быстродействием при сохранении точностных характеристик;
- результаты анализа быстродействия и методической погрешности предлагаемого алгоритма методом имитационного моделирования;
- комплекс программ имитационного моделирования и оценки ДПФ неэквидистантных временных рядов без восстановления пропущенных отсчетов.
Структура и состав диссертации. Работа состоит из введения, шести глав, заключения, списка литературы (99 наименований), трех приложений. Общий объем диссертации составляет 171 страницу компьютерной верстки, включая 19 таблиц, 60 рисунков.
Во введении обоснована актуальность работы, сформулированы цели и задачи диссертационных исследований, методы их решения, приведена структура работы и положения, выносимые на защиту.
В первой главе проводится обзор существующих алгоритмов дискретного преобразования Фурье. Рассмотрено множество способов классификации методов расчета дискретного преобразования Фурье, обобщен имеющийся материал с целью выявления путей дальнейшего развития данного направления.
По способу нахождения искомой функции методы делятся на:
1. Прямой метод вычисления ДПФ.
Непосредственным суммированием в соответствии с формулой (1) прямого ДПФ над дискретной периодической последовательностью х(п) длиной N отсчетов, получим совокупность дискретных спектральных составляющих:
2. Косвенные методы вычисления ДПФ.
К данной группе алгоритмов можно отнести, например, ДПФ на основе фильтрации или время-импульсной модуляции.
По характеру построения алгоритмов можно выделить:
1. Классический алгоритм — прямой точный метод вычисления дискретного преобразования Фурье в поле комплексных чисел;
2. Быстрые алгоритмы - представляют собой модификации ДПФ, призванные снизить атгоритмическую сложность вычисления. Идея БПФ состоит в том, чтобы исходную последовательность разбить на более короткие последовательности, ДПФ которых могут быть скомбинированы таким образом, чтобы объединение их дало исходное 1У-точечное ДПФ. Базовыми являются алгоритмы Кули-Тьюки, Гуда-Томаса и Винограда.
Кодирование области значений сигналов в некотором коммутативном кольце с единицей позволяет вычисление ДПФ путем теоретико-числовых преобразований. Развитием указанных алгоритмов являются полиномиальное преобразование Нуссбаумера и гибридный алгоритм Рида-Труонга.
С точки зрения точности метода, алгоритмы можно разделить на точные и приближенные - аппроксимативные, методическая погрешность которых не может быть сведена к нулю.
По способу формирования выходной последовательности различают алгоритмы, рассчитывающие полный спектр сигнала, и алгоритмы расчета отдельных спектральных составляющих (типичный пример-алгоритм Герцеля).
Существуют специализированные алгоритмы обработки вещественных входных последовательностей и алгоритмы расчета ДПФ комплексных сигналов. Последние обладают возможностью расчета ДПФ действительных сигналов удвоенной длины.
Особый интерес представляет спектральный анализ неэквидистантных временных рядов. В этом случае сигнал описывается двумя массивами выборочных данных: массивом мгновенных значений