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

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

Широков Олег Юрьевич

ДИСКРЕТНОЕ ПРЕОБРАЗОВАНИЕ ФУРЬЕ НЕЭКВИДИСТАНТНЫХ ВРЕМЕННЫХ РЯДОВ

Специальность 05.13.18 - "Математическое моделирование, численные методы и комплексы программ"

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

Самара - 2004

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

Научный руководитель:

заслуженный работник высшей школы Российской Федерации, доктор технических наук, профессор С.А Прохоров

Официальные оппоненты:

доктор технических наук, доцент В.И. Батищев

кандидат технических наук, доцент А.Г. Храмов

Ведущая организация: Федеральное государственное унитарное

предприятие НИИ «Экран» (г. Самара)

Защита состоится Л!Ь иссыЩ 2004 года в 10 часов на заседании диссертационного совета Д 212.215.05 при государственном образовательном учреждении высшего профессионального образования «Самарский государственный аэрокосмический университет имени академика СП. Королева» по адресу: 443086, г. Самара, Московское шоссе, 34

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

Автореферат разослан » 2004 г.

Ученый секретарь диссертационного совета д.т.н., профессор

А.А. Калентьев

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

Актуальность темы. Дискретное преобразование Фурье (ДПФ) лежит в основе широкого круга задач современной цифровой обработки сигналов, главной из которых остается спектральный анализ. Совершенствование элементной базы и методов проектирования позволило значительно расширить возможности аппаратной и программной реализации алгоритмов, повысить точность, быстродействие и другие показатели эффективности. Систематизации данных и разработке новых алгоритмических решений вычисления ДПФ посвящено множество работ как отечественных исследователей (Агаян С. С, Ярославский Л. П., Лабунец В. Г., Чернов В. М. и др.) так и зарубежных (Кули, Тьюки, Виноград, Нуссбаумер и др.).

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

- статистические измерения с применением адаптивных систем сбора и обработки информации;

- неточность датирования в многоканальных системах;

- дискретизация с пропусками, сбоями наблюдений;

- стохастическое и квазистохастическое кодирование;

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

В настоящее время сформировались три основных направления статистических измерений вероятностных характеристик неэквидистантных временных рядов (НВР):

- оценка без учета нерегулярности временного рада;

- оценка с предварительным восстановлением ряда в промежуточных точках;

- оценка без восстановления ряда и использованием только существенных от-

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

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

счетов.

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

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

Таким образом, исследование алгоритмов и разработка аппаратно-программных средств оценки ДПФ НВР без восстановления отсчетов является актуальной задачей. Поставленная задача решалась в рамках темы госбюджетной НИР "Разработка методов и прикладных программ моделирования, оптимизации и обработки результатов научных исследований" Самарского государственного аэрокосмического университета (СГАУ).

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

- провести обзор и сравнительный анализ современных алгоритмов ДПФ, их структурной и алгоритмической сложности;

- разработать обобщенную классификацию способов повышения эффективности алгоритма;

- разработать алгоритм вычисления ДПФ НВР без восстановления пропущенных отсчетов;

- разработать дескрилторный метод вычисления ДПФ НВР, отличающийся повышенным быстродействием по сравнению с прямым методом;

- разработать и реализовать имитационную модель алгоритма для анализа методической погрешности оценки ДПФ НВР;

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

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

- алгоритм оценки ДПФ НВР без восстановления пропущенных отсчетов;

- дескрипторный метод оценки ДПФ НВР и его модификации, отличающийся повышенным быстродействием при сохранении точностных характеристик;

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

Практической ценностью обладают:

- структуры дескрипторных вычислителей ДПФ;

- комплекс программ имитационного моделирования и оценки ДПФ НВР без восстановления пропущенных отсчетов;

- зависимости оценки ДПФ от специфических характеристик неравномерно дискретизированных сигналов различной природы;

- методика построения дескрипторных вычислителей.

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

Апробация результатов работы. Основные положения докладывались:

- на научно-технической конференции с международным участием "Датчик-2004" (г. Судак, 2004);

- на всероссийской научно-технической конференции "Актуальные проблемы радиоэлектроники" (г. Самара, 2003);

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

- на заседаниях кафедр "Информационные системы и технологии" и "Радиотехника" СГАУ.

Результаты работы внедрены в учебном процессе кафедры "Информационные системы и технологии" по дисциплинам "Теория информации" и «Проектирование автоматизированных систем научных исследований», используются в ФГУП НИИ "Экран" и инженерно-медицинском центре "Новые приборы" (г. Самара).

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

- алгоритм оценки ДПФ неэквидистантных временных рядов без восстановления пропущенных отсчетов;

- дескрипторный метод оценок ДПФ неэквидистантных временных рядов, отличающийся повышенным быстродействием при сохранении точностных характеристик;

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

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

Структура и состав диссертации. Работа состоит из введения, шести глав, заключения, списка литературы (99 наименований), трех приложений. Общий объем диссертации составляет 171 страницу компьютерной верстки, включая 19 таблиц, 60 рисунков.

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

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

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

По способу нахождения искомой функции методы делятся на:

1. Прямой метод вычисления ДПФ.

Непосредственным суммированием в соответствии с формулой (1) прямого ДПФ над дискретной периодической последовательностью х(п) длиной N отсчетов, получим совокупность дискретных спектральных составляющих:

(1)

п=0 N *=0

2. Косвенные методы вычисления ДПФ.

К данной группе алгоритмов можно отнести, например, ДПФ на основе фильтрации или время-импульсной модуляции.

По характеру построения алгоритмов можно выделить:

1. Классический алгоритм — прямой точный метод вычисления дискретного преобразования Фурье в поле комплексных чисел;

2. Быстрые алгоритмы - представляют собой модификации ДПФ, призванные снизить атгоритмическую сложность вычисления. Идея БПФ состоит в том, чтобы исходную последовательность разбить на более короткие последовательности, ДПФ которых могут быть скомбинированы таким образом, чтобы объединение их дало исходное 1У-точечное ДПФ. Базовыми являются алгоритмы Кули-Тьюки, Гуда-Томаса и Винограда.

Кодирование области значений сигналов в некотором коммутативном кольце с единицей позволяет вычисление ДПФ путем теоретико-числовых преобразований. Развитием указанных алгоритмов являются полиномиальное преобразование Нуссбаумера и гибридный алгоритм Рида-Труонга.

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

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

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

Особый интерес представляет спектральный анализ неэквидистантных временных рядов. В этом случае сигнал описывается двумя массивами выборочных данных: массивом мгновенных значений {х^ и массивом соответствующих меток времени {/¡}. Причем индекс / в этом случае характеризует лишь место отсчёта или метки времени в массивах, где хранятся входные данные, а не характеризует время наступления события.

В соответствии с общим подходом к оценке характеристик НВР в работе рассматриваются следующие методы:

1. Оценка без учета нерегулярности временного ряда.

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

2. Оценка с предварительным восстановлением в промежуточных точках.

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

3. Оценка на основе только существенных отсчетов и соответствующих им меток времени.

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

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

- сохранению частотного разрешения за счет верного датирования отсчетов;

- к снижению времени вычислений за счет сокращения объема обрабатываемых данных.

В работе рассмотрены методы повышения эффективности вычисления преобразования Фурье. Как известно, вычисление преобразования по формуле (1) требует Ы2 комплексных умножений и N(N—1) комплексных сложений. Различные способы факторизации матрицы преобразования порождают широкий спектр алгоритмов БПФ. В алгоритмах Кули-Тьюки при составном N=N¡N2 число операций умножения сокращается до Алгоритм про-

стых множителей Гуда-Томаса позволяет при взаимно простых и 1Ч2 уменьшить количество операций до О^ЛЭДЛ^+ЛЭД). Перегруппировка операций сложения и умножения по методу Винограда позволяет в 2-3 раза сократить число операций умножения при увеличении числа сложений. Вычисление ДПФ с помощью полиномиальных преобразований основано на использовании корней из 1 в кольцах полиномов. Вычисления проводятся с использованием обычной

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

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

На основе литературы и опыта практических исследований определен набор параметров, наиболее характерно описывающих свойства алгоритма:

- число операций сложения Add;

- число операций умножений Mul;

- количество ячеек памяти вычислителя {Mem}, требуемое для размещения коэффициентов алгоритма;

- число операций чтения из ячейки памяти вычислителя Rd.

Две первые величины характеризуют арифметическую сложность алгоритма и являются основными при оценке быстродействия алгоритма ДПФ. Объем памяти {Мет} определяется числом коэффициентов, необходимых для расчета преобразования Фурье. Данный параметр является одой из характеристик аппаратурной сложности реализации алгоритма. Число обращений к памяти {Мет} характеризует как структурную сложность алгоритма, так и эффективность использования массива памяти.

Таким образом, обзор показал целесообразность разработки:

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

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

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

Для вычисления ДПФ НВР предлагается модифицировать классический алгоритм таким образом, чтобы проводить преобразование только над существенными отсчетами х(п) последовательности длины М = N/

X^XVM+^W S2]exp(-j2*^k) = Yx. Sjexp(-j2A), (2)

где 5, =

Лесли отсчет существенный;

§ _U'ecjlua

2 \0,иначе.

если отсчет модельный;

[О, иначе;

Для этого вводят интервал принудительной дискретизации Aíg. В простейшем случае его можно определить как Ato=Atm¡n; Ato=Atcp; Ato=Atmax. Чтобы однозначно определить отсчет x¡(t,)= x¡(nAt(¡), введем новый индикатор состояния:

1, если ent

МЛ

= п;

М-1

тогда х» = Xх/ 5«■ (3)

I

', иначе.

Тогда предполагаемый объем выборки реализации регулярного ряда:

О

0,5

, при усечении; , при округлении.

(4)

N-1

(5)

(6)

(7)

N = ent[{tu_l-t0)lbtü+A, где Х=|

Общий алгоритм оценки ДПФ НВР:

в=0 /=0 " /=0 п=0 "

Индекс времени прихода существенного отсчета определяется:

n¡ =ent[t¡lál0+X\.

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

¿«0 " i-о

где

- дискретное значение амплитуды сигнала;

signfoi) - знаковая функция.

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

Методическая погрешность вычисления ДПФ по формуле (7) будет отличаться от погрешности формулы (1) на величину: Aj. = А м+ Л,+ A L=Х(к, М, Ato, L) - Х(к),

где

- погрешность объема выборки, определяющаяся коэффициентом сжатия последовательности ксж;

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

Ai - погрешность, обусловленная конечной разрядностью L квантования входных данных.

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

Введем новое функциональное преобразование:

п,

Мет(д„ппк) = д; ехр£/2ж-^к) .

(8)

Все возможные значения преобразования становятся известны

в силу дискретности значений всех его аргументов и ограниченности диапазона их изменения. Это позволяет сформировать матрицу значений Мет[] и использовать ее для расчета ДПФ. Тогда, в общем случае, метод вычисления ДПФ НВР примет вид:

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

Так как при анализе процессов с нулевым средним обычно используют АЦП с симметричным относительно нуля динамическим диапазоном, это позволяет сократить требуемое количество кодируемых уровней до 2^'К Используя свойство периодичности базисных функций имеется возможность в N раз сократить количество хранимых коэффициентов.

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

Начало

__

Ввод х(п)

I -

Формирование адреса

по п„ к '

Выборка из памяти Мет[д„ р, ,к] I

Х(к) = Х(к) + АУч"к

Рисунок 1.

Свойства симметричности позволяют еще вдвое уменьшить количество ячеек с учетом фиксации изменения знака. Для этого можно использовать, например, знаковый разряд адреса из таблицы дескрипторов. Таким образом, для действительной и мнимой частей преобразования достаточно вычислить значения базисных функций на интервале (0; ж/2). Еще более значительное сокращение можно произвести исходя из того, что коэффициенты 0,1 и -1 фактически не требуют размещения в массиве памяти. Так же, в силу ортогональности базисных функций для вычисления действительной и мнимой частей преобразования, можно использовать один массив памяти коэффициентов.

Следует отметить, что регулярная дискретизация является частным случаем НВР, когда ксж=1, а точность предлагаемого метода идентична классической форме ДПФ при условии, что квантование произведений в обоих случаях одинаково.

Предлагаемый метод сокращенных вычислений можно использовать для расчета ДПФ на базе быстрых алгоритмов дискретных преобразований Кули-Тькжи и Винограда. Структура "бабочек" алгоритма по основанию 2 и структура малого алгоритма Винограда представлены на рисунке 2.

АМ = (Ы/к^)1, Ми1 = 0, {Мет} = 2Ь ЛГ2, М = (М/к^)1.

Рисунок 2.

При использовании в методе Кули-Тьюки схемы масштабирования со сдвигом вправо на один разряд на каждом этапе динамический диапазон системы будет неизменным и необходимое количество кодируемых уровней квантования при математическом ожидании входного сигнала равном нулю составит 2Ь'1>. Однако такая схема масштабирования не всегда дает удовлетворительные результаты по точности вычислений.

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

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

1) выполнение предварительных сложений над вектором входного сигнала и формирование вектора адресов;

2) выполнение масштабирования с целью сокращения пространства адресов;

3) выборка требуемых значений произведений из массива памяти;

4) выполнение постсложений и формирование результирующего вектора.

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

Система представляет собой приложение для операционных систем семейства Windows, разработанное на языке Delphi5\ состоит из запускаемого модуля и набора библиотек (DLL), содержащих процедуры вычисления входных сигналов, дискретизирующих последовательностей и ДПФ (рисунок 3).

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

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

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

Рисунок 3.

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

- периодической дискретизации со случайными пропусками наблюдений;

- аддитивной случайной дискретизации.

Имеется возможность восстановления сигнала простейшими моделями:

- ближайшим отсчетом;

- линейной интерполяцией.

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

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

Проанализирован характер распределения погрешности в условиях дискретизации с пропусками. Показано, что при регулярных пропусках наблюдений в спектре появляются гармоники высших порядков. Дискретизация же со случайным законом пропуска наблюдений проявляется в появлении широкополосного шума. Показано, что восстановление пропущенных отсчетов простейшими моделями - ближайшим отсчетом и линейной интерполяцией - целесообразно только для широкополосных сигналов, т.к. приводит подавлению высокочастотных составляющих спектра. Получены графики, иллюстрирующие пределы изменения абсолютного значения погрешности. Так, при сокращении числа существенных отсчетов в 5 раз, данная погрешность может достигать (20-г80)% для различных моделей дискретизации.

Исследована погрешность, вызванная сокращением разрядной сетки на входе вычислителя. Так, при сокращении сетки на 75% абсолютное значение погрешности составляет (3 4-20)% для различных моделей сигналов. Построенные графики позволяют утверждать, что для любых моделей сигналов погрешность, вызванная сокращением количества разрядов, имеет значительно меньший порядок, чем погрешность, вызванная неравномерностью дискретизации. Таким образом, при использовании дескрипторных методов объем памяти вычислителя может быть значительно сокращен.

Получены оценки погрешности, обусловленной промежуточным масштабированием в дескрипторном методе Кули-Тьюки. При использовании сдвига результата каждой "бабочки" на один разряд вправо данная погрешность для гармонических сигналов практически неизменна при любом значении коэффициента сжатия последовательности и составляет (10-5-20)%. Для широкополосных сигналов при большом проценте пропущенных отсчетов вносимая погрешность маскируется.

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

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

0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1

Параметр дискретизации

Рисунок 4.

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

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

I 16 и II 2Л 1« 1И 14 411 1«

Рисунок 5.

1 Прохоров С. А. Методика и результаты обработки вариабельности сердечного ритма, (частное сообщение)

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

базе разработанной системы имитационного моделирования.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

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

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

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

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

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

- псевдослучайного процесса на основе суммы гармонических составляющих;

- широкополосного и узкополосного коррелированного случайного процесса.

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

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

8. В работе приведен общий порядок проектирования дескрипторных алгоритмов расчета ДПФ на базе классических и быстрых алгоритмов-прототипов ДПФ.

СПИСОК РАБОТ, ОПУБЛИКОВАННЫХ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Овсянников А. С, Прохоров С. А., Широков О. Ю. Алгоритмы одномерного быстрого преобразования Фурье // Сборник научных трудов. Перспективные информационные технологии в научных исследованиях, проектировании и обучении. Самара, СГАУ, 2001, с. 109-118.

2. Прохоров С. А., Широков О. Ю. Дискретное преобразование Фурье неэквидистантных временных рядов// Тезисы докладов научно-техн. конференции "Датчик-2004".- Судак, 2004.

3. Широков О. Ю. Анализ времени выполнения ДПФ НВР // Вестник СГАУ. Актуальные проблемы радиоэлектроники. Вып8. Самара, ИПО СГАУ, 2002, с.66-68.

4. Широков О. Ю. Анализ составляющих методической погрешности оценки корреляционных функций неэквидистантных временных рядов // Вестник СГАУ. Актуальные Проблемы Радиоэлектроники. Вып1. Самара, ИПО СГАУ, 1999, с.57-63.

5. Широков О. Ю. Краткий обзор быстрых алгоритмов преобразования Хартли // Вестник СГАУ. Актуальные проблемы радиоэлектроники. Вып 5. Самара, ИПО СГАУ, 2001, с. 105-107.

6. Широков О. Ю., Прохоров С. А., Овсянников А. С. Дескрипторные алгоритмы преобразования Фурье // Вестник СГАУ. Актуальные проблемы радиоэлектроники. Вып 6. Самара, ИПО СГАУ, 2001, с.94-99.

7. Широков О. Ю., Прохоров С. А., Овсянников А. С. Дескрипторные алгоритмы преобразования Фурье // Тезисы докладов межвуз. научно-практ. конференции "Компьютерные технологии в науке и образовании" (Самара, 4 нояб. 2002 г.). - Самара, 2002, с 54-55.

8. Широков О. Ю. Способ формирования входных воздействий для систем имитационного моделирования // Вестник СГАУ. Актуальные проблемы радиоэлектроники. Вып 3. Самара, ИПО СГАУ, 2000, с.87-91.

9. Широков О. Ю. Система имитационного моделирования расчета ДПФ // Тезисы докладов всеросс. научно-техн. конференции "Актуальные проблемы радиоэлектроники" (Самара, 30 июня 2003 г.). - Самара, 2003, с. 35.

Подписано в печать 21.05.2004. Объем 1,0 усл. печ. л. Тираж 100 экз.

Отпечатано с готовых оригинал-макетов

»13764

ВВЕДЕНИЕ

1. МЕТОДЫ ВЫЧИСЛЕНИЯ ДИСКРЕТНОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ

1.1 Алгоритмы преобразования Фурье дискретной последовательности данных

1.2 Методы повышения эффективности преобразования Фурье

1.3 Характерные параметры алгоритмов ДПФ 21 Выводы

2. ДИСКРЕТНОЕ ПРЕОБРАЗОВАНИЕ ФУРЬЕ

2.1 Математическое описание неэквидистантных временных рядов

2.2 Дискретное преобразование Фурье неэквидистантных временных рядов

2.3 Дескрипторный метод вычисления ДПФ 3 ^

2.4 Дескрипторный метод вычисления БПФ

2.4.1 Дескрипторный метод по алгоритму Кули—Тьюки

2.4.2 Дескрипторный метод по алгоритму Винограда

2.5 Вычислительная сложность алгоритмов 55 Выводы

3. СИСТЕМА ИМИТАЦИОННОГО МОДЕЛИРОВАНИЯ РАСЧЕТА ПРЕОБРАЗОВАНИЯ ФУРЬЕ* ' ' 5?.

3.1 Структура программного комплекса

3.2 Моделирование входных воздействий

3.3 Моделирование потока с нерегулярной дискретизацией

3.4 Параметры расчета ДПФ

4. АНАЛИЗ ХАРАКТЕРИСТИК АЛГОРИТМОВ ПРЕОБРАЗОВАНИЯ ФУРЬЕ

4.1 Погрешность вычисления ДПФ неравномерно 91 дискретизированной последовательности

4.2 Анализ времени вычисления ДПФ неравномерно 103 дискретизированной последовательности

4.3 Погрешность при сокращении разрядности входного сигнала

4.4 Погрешность "ошибочной" адресации

4.5 Анализ времени вычисления ДПФ равномерно -дискретизированной последовательности

4.6 Анализ времени вычисления ДПФ последовательностей различной длины

Выводы

5. СПЕКТРАЛЬНЫЙ АНАЛИЗ ВАРИАБЕЛЬНОСТИ СЕРДЕЧНОГО РИТМА

5.1 Общие положения

5.2 Оценка спектральной мощности ритмограмм

6. РЕКОМЕНДАЦИИ ПО ПРОЕКТИРОВАНИЮ ДЕСКРИПТОРНЫХ АЛГОРИТМОВ ДПФ

6.1 Общий порядок проектирования

6.2 Рекомендации по проведению занятий по изучению дескрипторных алгоритмов ДПФ

Дискретное преобразование Фурье лежит в основе широкого круга задач современной цифровой обработки сигналов, главной из которых остается спектральный анализ /14-17,20-25,36,69/. Систематизации данных и разработке новых алгоритмических решений вычисления ДПФ посвящено множество работ как отечественных исследователей (Агаян С. С., Ярославский Л. П., Лабунец В. Г., Чернов В. М. и др.) так и зарубежных (Кули, Тьюки, Виноград, Нуссбаумер и др.).

Наряду с классическим подходом в последнее время возрастает интерес к анализу характеристик неравномерно дискретизированных последовательностей, когда интервал дискретизации ^ не является постоянной величиной. В этом случае сигнал описывается двумя массивами выборочных данных: массивом мгновенных значений и массивом соответствующих меток времени {/¡}. Причем индекс / в этом случае характеризует лишь место отсчёта или метки времени в массивах, где хранятся входные данные, а не характеризует время наступления события. Подобными последовательностями представляются результаты измерений при решении разнообразных задач, например /48/:

- статистические измерения с применением адаптивных систем сбора и обработки информации;

- неточность датирования в многоканальных системах;

- дискретизация с пропусками, сбоями наблюдений;

- стохастическое и квазистохастическое кодирование;

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

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

Таким образом, сформировались три основных направления статистических измерений спектральных характеристик неэквидистантных временных рядов:

- оценка без учета нерегулярности временного ряда;

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

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

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

Другим аспектом исследований является повышение эффективности вычислений ДПФ. Совершенствование элементной базы и методов проектирования позволило значительно расширить возможности аппаратной и программной реализации алгоритмов, повысить точность, быстродействие и другие показатели эффективности. Однако, несмотря на постоянный рост быстродействия вычислительных систем, появление специализированных процессоров с адаптированным набором команд не оставляются попытки снизить трудоемкость расчета путем создания новых скоростных алгоритмов преобразования Фурье над дискретными последовательностями данных /35,58-60,68,75-78,91,98/.

Следует отметить, что общая сложность алгоритма определяется не только числом арифметических операций — алгебраической сложностью, но и количеством необходимой памяти, стоимостью вспомогательных операций /59,79,92-94/. Эффективность может быть существенно снижена излишней структурной сложностью или некорректной аппаратно-программной реализацией /88,90,95/. Отсюда вытекает основная задача проектирования — соблюдения баланса между перечисленными составляющими в рамках конкретной задачи.

В последнее время совершенствование алгоритмов БПФ происходит в направлении разработки специальных алгоритмов, например, для расчета преобразования Фурье вещественных последовательностей /30,60,68/. Вряде случаев эффективным решением может служить применение преобразования Хартли /12,13,65,70,96/. Однако, по числу арифметических операций БПХ практически не имеет преимуществ перед БПФ. При этом, наиболее весомым преимуществом преобразования Хартли является сокращение объема памяти .коэффициентов в два и более раза. Алгоритмы БПХ имеют более простую, симметричную для прямого и обратного преобразований структуру вычислительного процесса, что дает преимущество при реализации вычислителей конвейерного типа.

Другим перспективным направлением развития является применение полиномиальных и теоретико-числовых преобразований для вычисления ДПФ /9,34,40,62/. Вычисление ДПФ с помощью полиномиальных преобразований основано на использовании корней из 1 в кольцах полиномов. Вычисления проводятся с использованием обычной арифметики без умножения. Если длины последовательностей выражаются составными числами, вычисления могут быть организованы посредством алгоритмов типа БПФ. Для вычисления ДПФ на основе теоретико-числовых преобразований применяются алгоритмы, основанные на использовании одномерных и двумерных циклических сверток. Однако наибольшая эффективность вычислений может быть достигнута только в случае, когда подобные преобразования реализуются с помощью специальных вычислительных средств, эффективно реализующих модулярную арифметику.

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

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

Для этого необходимо:

- провести обзор и сравнительный анализ современных алгоритмов ДПФ, их структурной и алгоритмической сложности;

- дать обобщенную классификацию способов повышения эффективности;

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

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

Практическая ценность: структуры дескрипторных вычислителей ДПФ; комплекс программ имитационного моделирования и оценки ДПФ НВР без восстановления пропущенных отсчетов; зависимости оценки ДПФ от специфических характеристик неравномерно дискретизированных сигналов различной природы; методика построения дескрипторных вычислителей.

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

Содержание работы:

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

Во второй главе приводятся аналитические выражения для расчета ДПФ НВР, рассматривается новый — дескрипторный — способ вычисления ДПФ, базирующийся как на классическом алгоритме вычислений, так и на быстрых методах - БПФ. Приведены структурные схемы вычислителей и оценки алгоритмической сложности.

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

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

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

В шестой главе приведен общий порядок проектирования дескрипторных алгоритмов ДПФ и рекомендации по проведению практических занятий.

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

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

ВЫВОДЫ

В данной главе подведены итоги экспериментальных исследований вычисления ДПФ НВР дескрипторным методом, проведенные методом имитационного моделирования.

1. Получены зависимости погрешности расчета ДПФ при неравномерной дискретизации для различных моделей сигналов. При этом погрешность может достигать (80-ь90)% при коэффициентах сжатия Ксж> 5.

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

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

4. Отмечено, что применение дескрипторного алгоритма позволяет повысить скорость вычисления на (20-ь40)% в зависимости от платформы ЭВМ и программной реализации. Большего выигрыша можно добиться аппаратной реализацией дескрипторного метода на основе схем, представленных в главе 2.

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

6. Применение ДПФ НВР дает больший выигрыш в скорости вычислений, чем алгоритм с логическим блоком, исключающим из обработки нулевые отсчеты.

7. Проведен анализ погрешности, вызванной промежуточным масштабированием данных при вычислении дескрипторным методом на основе алгоритма Кули-Тьюки. Данная погрешность может составлять (10-40)% в зависимости от характера анализируемой последовательности.

8. Сравнительный анализ для различных длин входной последовательности показал, что выигрыш в скорости расчета ДПФ дескрипторным методом лежит в пределах (20ч-40)% и несколько меньше для последовательностей большой длины.

5. СПЕКТРАЛЬНЫЙ АНАЛИЗ ВАРИАБЕЛЬНОСТИ СЕРДЕЧНОГО РИТМА

5.1 ОБЩИЕ ПОЛОЖЕНИЯ

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

Наиболее информативным методом определения ВРС служит спектральный анализ. Чаще всего используется обработка кардиоинтервалограмм с помощь алгоритмов БПФ на количестве точек не менее 256. В соответствии с международным стандартом в спектральном разложении выделяют четыре характерные зоны /77,78/:

1. Ultra Low Friquency (ULF) - зона сверх низких частот (0 - 0.0033 Гц)

2. Very Low Friquency ( VLF) - зона очень низких частот (0.0033 - 0.05 Гц)

3. Low Friquency (LF) - зона низких частот (0.05 - 0.15 Гц )

4. High Friequency (HF) - зона высоких частот (0.15- 0.5 Гц) Типичный график спектрального анализа кардиоинтервалограммы представлен на рисунке 5.1.

Рисунок 5.1

Типичное представление спектрального анализа ВСР.

Частотную зону ULF включают в анализ только при разложении в ряд Фурье результатов суточного мониторирования ЭКГ. Она не связана с проявлениями быстрой регуляции и ее происхождение до сих пор неизвестно. Диагностически значимыми являются мощности остальных трех зон спектра, отвечающих 5-минутной ЭКГ, а также отношение мощности LF к мощности зоны HF и значение частоты, при которой амплитуда спектра имеет максимум в зоне LF.

Метод БПФ по отношению к кардиоинтервалограмме имеет определенную математическую некорректность, т.к. по оси абсцисс откладывается не время, а номер последующего кардиоинтервала. гг(п) п

ГГо гг 1

ГГ2 rrj

Рисунок 5.2

Эту неточность пытаются устранить, предлагая анализировать методом БПФ не кардиоинтервалограмму, а функцию - x(t), которая строится из исходной кардиоинтервалограммы методом сплайновой кубической интерполяции, при квантовании функции x(t) с шагом 250 мс /77,78/.

Другим способом устранения указанного недостатка является применение теории неэквидистантных временных рядов для оценки спектрального разложения кардиоинтервалограммы. Входные данные представляют собой временной ряд значений /^-интервалов, т.е. массив интервалов времени между сердечными ритмами. Для дальнейшего анализа преобразуем данный массив в двумерный таким образом, чтобы значению /^-интервала соответствовало его положение на временной оси (рисунок 5.2) гг(0 1 гг о гг2

ГГ I гг3

ГГо ГГ) ГГ2 ГГз

Рисунок 5.2

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

5.2 ОЦЕНКА СПЕКТРАЛЬНОЙ МОЩНОСТИ РИТМОГРАММ

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

Таким образом, кардиоинтервалограмма представляет собой нестационарный процесс, т.е. его математическое ожидание является функцией времени. Ранее для уменьшения влияния тренда использовались различные методики, такие как визуальное выделение стационарных участков с последующим "клонированием" до нужного объема выборки; оценка отклонений методом наименьших квадратов; метод скользящего БПФ и др /77,78/.

На рисунке 5.3 приведены результаты оценивания математического ожидания одной и той же реализации в различных ортогональных базисах: ортогональных на конечном (Лежандра, Чебышева), полубесконечном (Лагерра) и бесконечном (Эрмита) интервалах. На правых рисунках для удобства сравнения качества центрирования приведены результаты повторного центрирования в тех же ортогональных базисах. а) базис Лагерра

• ем « б) базис Лежандра в) базис Чебышева г) базис Эрмита

Рисунок 5.3

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

Анализ результатов показывает:

1. При повторном центрировании НВР с использованием ортогональных базисов Лежандра и Чебышева в модели математического ожидания возникают осцилляции;

2. Центрированная реализация НВР с использованием ортогонального базиса Лагерра по внешнему виду напоминает нестационарный процесс по математическому ожиданию;

3. Лучшие результаты следует ожидать при использовании ортогонального базиса Эрмита.

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

5. Разработан комплекс программ имитационного моделирования оценки дискретного преобразования Фурье для работы под управлением операционных систем семейства Windows. Система реализует как классические, так и предлагаемые дескрипторные методы вычисления ДПФ, используя модели сигналов с различными корреляционными и частотными свойствами с регулярной и нерегулярной дискретизацией;

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

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

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

9. В работе приведен общий порядок проектирования дескрипторных алгоритмов расчета ДПФ на базе классических и быстрых алгоритмов ДПФ. Даны рекомендации по проведению практических занятий по изучению дескрипторных методов вычисления ДПФ.

Работа выполнена на базе научной лаборатории НИЛ-50 кафедры "Информационные системы и технологии" факультета "Информатика" в рамках темы госбюджетной НИР "Разработка методов и прикладных программ моделирования, оптимизации и обработки результатов научных исследований". Разработанная система имитационного моделирования может быть применена в учебном процессе для изучения свойств как классических, так и дескрипторных методов вычисления дискретного Фурье сигналов различной природы.

1. Аллен Дж.Б., Рабинер Р. Унифицированный подход к кратковременному преобразованию Фурье и синтезу сигналов. ТИИЭР, 1977, т.65, с.45-53.

2. Андрианов С. Точное измерение времени в программах // Мир ПК.-2003.-выпЗ.- С. 120-124.

3. Антонью А. Цифровые фильтры: анализ и проектирование: Пер с англ. — М.: Радио и связь, 1983. 320 с.

4. Арро И. О. Обобщенный алгоритм сокращенного вычисления дискретного преобразования Фурье // Радиоэлектроника.- 1987.- № 12.-С.5-10.

5. Бахтиаров Г. Д., Тищенко А. Ю. Реализация устройства цифровой обработки сигналов на основе алгоритма БПФ, — Зарубежная радиоэлектроника, 1975, №9, с. 71-98.

6. Белый А. А., Бовбель Е. И., Микулович В. И. Алгоритмы быстрого преобразования Фурье и их свойства, — Зарубежная радиоэлектроника, 1979, №2, с. 3-29.

7. Берестетский А. А. Алгоритм вычисления быстрого преобразования Фурье в конечном числе точек, Радиоэлектроника, 1991, №3, с. 100-102.

8. Бовбель Е. И., Кухарчик П. Д., Рубанов Н. С. Алгоритмы вычисления дискретных преобразований Фурье и сверток на основе теоретико-числовых преобразований в прямых суммах конечных полей. . 1993, с. 2026-2032.

9. Богомолов Ю. А., Левшин В. П., Стручев В. Ф. Вычисление свертки и дискретного преобразования Фурье методом Винограда, Зарубежная радиоэлектроника, 1984, №3, с.3-17.

10. Блейхут Р. Быстрые алгоритмы цифровой обработки сигналов: Пер. с англ. М.: Мир, 1989. - 448 с.:ил.

11. Бьюнеман О. Многомерные преобразования Хартли. ТИИЭР, 1987, N2, с.97-98.

12. Власенко В. А., Лаппа Ю. М., Ярославский Л. П. Дискретное преобразование Хартли как альтернатива дискретному преобразованию Фурье в цифровой обработке сигналов // Радиоэлектроника.-1989.-№12.-С.5-11.(Изв. учеб. заведений).

13. Голд Б., Рейдер Ч. Цифровая обработка сигналов. М.: Сов. Радио, 1973.368 с.

14. Гольденберг Л. М. и др. Цифровая обработка сигналов: Учеб. Пособие для вузов/ Л. М. Гольденберг, Б. Д. Матюшкин, М. Н. Поляк. 2-изд., перераб. и доп. - М.: Радио и связь, 1990 - 256 е.: ил.

15. Гольденберг Л. М., Левчук Ю. П., Поляк М. Н. Цифровые фильтры.- М: Связь, 1974.-160 с.

16. Гоноровский И. С. Радиотехнические цепи и сигналы: Учебник для вузов.-3-е изд., перераб. и доп. -М.: Сов. Радио, 1977. 608 с.

17. Горелов Г. В. Нерегулярная дискретизация сигналов М.: Радио и связь, 1982.- 256 с, ил. (стат. теория связи. Вып. 17)

18. Гофман В.,Хамоненко А. Ое1рЫ5 в подлиннике.ВНУ-СПб,2001.-800 с.

19. Грибанов Ю. И., Мальков В. Л. Спектральный анализ случайных процессов.- М.:Энергия, 1974.-240 е., ил.

20. Дженкинс Г., Ватте Д. Спектральный анализ и его приложения. 4.1. М.: Мир, 1971.-320 с.

21. Дженкинс Г., Ватте Д. Спектральный анализ и его приложения. 4.2. — М.: Мир, 1972.-288 с.

22. Залманзон JT. А. Преобразования Фурье, Уолша, Хаара и их применение в управлении, связи и других областях. М.: Наука, 1989.

23. Зеленко Л. С. Методы, алгоритмы и программное обеспечениекорреляционного анализа неэквидистантных временных рядов -Диссканд. техн. наук Самара: 1994- 226с.

24. Кей С. М., Марил С. J1. Современные методы спектрального анализа. ТИИЭРт. 69, №11, 1981, с.3-47.

25. Кнут Д. Е. Искусство программирования для ЭВМ.-М.: Мир, 1976, 724 с.

26. Крамер Г., Лидбеттер М. Стационарные случайные процессы.- М.: Мир, 1969.- 400 с.

27. Кузенков В. Д. Методы и устройства цифровой обработки сигналов -Куйбышев: КуАИ, 1988. 96 с.

28. Кулаичев А. П. Компьютерный контроль процессов и анализ сигналов. М: НПО "Информатика и компьютеры", 1999, с.7-127.

29. Кумерсан Р., Гупта П. К. Алгоритм БПФ для простых множителей на основе арифметики действительных чисел. ТИИЭР, 1985, т.73, №7, С.98-100.

30. Левин Б. Р. Теоретические основы статистической радиотехники. Кн. 1. Изд. 2. М,: Сов. Радио, 1974. -552 С.

31. Лем Г. Аналоговые и цифровые фильтры: Пер с англ. М.: Мир, 1982. -592 с.

32. Лосев В. В. Микропроцессорные устройства обработки информации. Алгоритмы цифровой обработки: Учеб. Пособие для вузов. Мн.: Выш. шк., 1990.- 132 е.: ил.

33. Маккелан Дж. Г., Рейдер Ч. М. Применение теорий чисел в цифровой обработке сигналов. М.: Радио и связь, 1983.

34. Малоземов В. Н., Третьяков А. А. Новый подход к алгоритму Кули-Тьюки И Вестник СПбГУ. Сер. 1. 1997. Вып. 3 (№15). С. 57-60.

35. Марпл, Стенли Лоренс. Цифровой спектральный анализ и его приложения/ Пер. с англ. О. И. Хабарова, Г.А. Сидоровой, Под ред. И. С. Рыжака: М.: Мир, 1990.-584 е.: ил.

36. Мизин И. А., Матвеев А. А. Цифровые фильтры.-М.: Связь, 1979. 287 с.

37. Микросхемы памяти. ЦАП и АЦП: Справочник-2—е изд.,стереотип / О. Н. Лебедев, А-Й. К. Марцинкявичюс, Э-А. К. Багданские и др.; — М.: КубК-а, 1996-384 е.: ил.

38. Мясникова Н. В. Спектральный анализ сигналов по амплитудным и временным параметрам на основе измерительного эксперимента. — Дисс. докт. техн. наук Пенза: 2001. — 345с.

39. Нуссбаумер Г. Быстрое преобразование Фурье и алгоритмы вычисления сверток: Пер. с англ.-М.:Радио и связь, 1985. -248 е., ил.

40. Озеров В. Delphi. Советы программистов. Символ-Плюс, 2002.-912 с.

41. Овсянников А. С., Прохоров С. А., Широков О. Ю. Алгоритмы одномерного быстрого преобразования Фурье // Сборник научных трудов. Перспективные информационные технологии в научных исследованиях, проектировании и обучении. Самара, СГАУ, 2001, с. 109-118.

42. Опенгейм А. В., Шафер Р. В. Цифровая обработка сигналов: Пер с англ.-М.: Связь 1979.-416 с.

43. Остапенко А. Г., Сушков А. Б. и др. Рекурсивные фильтры на микропроцессорах. М.: Радио и связь, 1988.

44. Прохоров С. А. Аппроксимативный анализ случайных процессов.- 2-е изд., перераб. и доп./Самар. гос. аэрокосм. ун-т. Самара, 2001. 380 е.: ил.

45. Прохоров С. А. Измерение вероятностных характеристик при неравномерной дискретизации случайных процессов — Дисс. докт. техн. наук — Куйбышев: 1987 — 409с.

46. Прохоров С. А. Математическое описание и моделирование случайных процессов/Самар. гос. аэрокосм. ун-т. Уральск, 2001. 209 е.: ил.

47. Прохоров С. А. Прикладной анализ неэквидистантных временных рядов/Самар. гос. аэрокосм. ун-т. — Уральск, 2001. 375 е.: ил.

48. Прохоров С. Л., Широков О. Ю. Дискретное преобразование Фурье неэквидистантных временных рядов// Тезисы докладов научно-техн. конференции "Датчик-2004".- Судак, 2004.

49. Рабинер П., Гоулд Б. Теория и применение цифровой обработки сигналов.//Пер. с англ./Под ред. Ю.Н. Александрова.-М.: Мир, 1978.-848 с.

50. Рихтер Дж. Windows для профессионалов: Программирование для Windows 95 и Windows NT на базе WIN32API. М.: Издательский отдел "Русская редакция" ТОО "Channel Trading Ltd.", 1997. - 712 с.

51. Свердлик М. Б. Матричная интерпретация и вычислительная эффективность алгоритмов БПФ// Радиотехника и электроника.—1984.-№.29.-№2.-с.265-274.

52. Свердлик М. Б., Троянский А. В. Обобщенное матричное описание алгоритма БПФ, Радиоэлектроника, 1995, №7, с. 27-33.

53. Сергиенко А. Б. Цифровая обработка сигналов: Учеб. Пособие для вузов/ ISBN: 5-318-00666-3, 2002. 608 с.

54. Специализированные процессоры для высокопроизводительной обработки данных/ O.JI. Бандман, H.H. Миренков, С.Г. Седухин и др. -Новосибирск: Наука. Сиб. отделение, 1988. 208 с.

55. Цветков Э. И. Методические погрешности статистических измерений —JI: Ленинградское отделение Энергоатомиздата, 1984.- 144 е., ил.

56. Цветков Э. И. Основы теории статистических измерений. — 2-е изд., перераб. и доп. Л.: Ленингр. отд-ние, 1986. - 256 с.

57. Цифровая обработка информации на основе быстродействующих БИС/ С.А. Гамкрелидззе, A.B. Завьялове, П.П. Мальцев и др.; Под ред. В.Г. Домрачева.-М.: Энергоатомиздат, 1988.-136 с.

58. Чеголин П. М. Автоматизация спектрального и корреляционного анализа.- М.: Энергия, 1969.-383 с.

59. Чернов В. М. Алгоритмы дискретного преобразования Фурье с представлением данных в полях алгебраических чисел // Автоматика и вычислительная техника, Вып. 4, 1994, с.64-69.

60. Широков О. Ю. Анализ времени выполнения ДПФ НВР // Вестник СГАУ. Актуальные проблемы радиоэлектроники. Вып8. Самара, ИПО СГАУ, 2002, с.66-68.

61. Широков О. Ю. Анализ составляющих методической погрешности оценки корреляционных функций неэквидистантных временных рядов // Вестник СГАУ. Актуальные Проблемы Радиоэлектроники. Вып 1. Самара, ИПО СГАУ, 1999, с.57-63.

62. Широков О. Ю. Краткий обзор быстрых алгоритмов преобразования Хартли // Вестник СГАУ. Актуальные проблемы радиоэлектроники. Вып 5. Самара, ИПО СГАУ, 2001, с. 105-107.

63. Широков О. Ю. Способ формирования входных воздействий для систем имитационного моделирования // Вестник СГАУ. Актуальные проблемы радиоэлектроники. Вып 3. Самара, ИПО СГАУ, 2000, с.87-91.

64. Широков О. Ю., Прохоров С. А., Овсянников А. С. Дескрипторные алгоритмы преобразования Фурье // Вестник СГАУ. Актуальные проблемы радиоэлектроники. Вып 6. Самара, ИПО СГАУ, 2001, с.94-99.

65. Яцмирский М. Н. Алгоритм быстрого преобразования Фурье вещественной последовательности // Радиоэлектроника.-1987.-№12.-С.53-55.(Изв. учеб. заведений).

66. Bateman A., Yates W. Digital Signal Processing Design, Pitman Publishing, London, UK 1988.

67. Bracewell R. N. Discrete Hartly transform // I. Opt. Soc. Am. -1983, -V. 73.-N12.-P. 1832-1835.

68. Burrus C. S., Parks T. W. DFT/FFT and Convolution Algorithms, Wiley Interscience, NY 1985.

69. Buyer's Guilde To DSP Processors. Third Edition/ Berkeley Design Technjlogy Inc., (http://www.bdti.com), 1997.

70. Cooley J. W., Tukey J. W. An algorithm for the machine calculation of complex Fourier series. Math. Comput., 1965, v. 19, №4, p. 297 -301.

71. D. M. Bland, T. I. Laasko and Aa. J. Tarczynski, "Analysis of algorithms for a Non-Uniform Discrete Fourier Transform", Int. Symp. On Circuits and Systems (ISCAS'96), vol. 2, pp. 453-456, Atlanta, Georgia, USA, May 12-15, 1996.

72. D. M. Bland, T. I. Laasko and Aa. J. Tarczynski, "Application of NUT-DFT for Resampling Nonuniformly Samled Signals", Int. Symp. On Circuits and Systems (ISCAS'96), vol. 2, pp. 586-589, Atlanta, Georgia, USA, May 12-15, 1996.

73. Fast Fourier Transforms / Walker J. S.: CRC Press, 1996.

74. Good I J. The Interaction Algorithm and Practical Fourier Analysis, J. Royal Statist. Soc., Ser. B 20 (1958): 36-375; addendum, 22 (1960): 372-375.

75. Guo H., Sitton G. A. Burrus C. S. The Quick Fourier Transform: An FFT Based on Symmetries. IEEETrans. On Signal Processing, 1998, vol. 46, №2, p. 335-340.

76. Hon EH, Lee ST Electronic evaluations of the fetal heart rate patterns preceding fetal death, further observations. Am J Obstet Gynec 1965; 87: 81426.

77. Johnson H. W., Burrus C. S. The design of optimal DFT algorithms using dynamic programming. IEEE Transactions on Acoustics, Speech and Signal Processing, 31:378-387, April 1983.

78. Kaneko T.K., Liu B. Accumulation of round-off errors in fast Fourie transforms. J. Assoc. Comput. Math. 17, 637-654 (1970)

79. Lynn P. A., Fuerst W. Introductory Digital Signal Processing. John Wiley and Sons, UK 1988.

80. Numerical Recipes in C: The Art of Scientific Computing. Second Edition/ William H. Press, Saul A. Teukolsky, William T. Vetterling, Brian P. Flannery: Cambridge University Press, 1992.

81. Nussbaumer H.J. DFT computation by fast polynomial transform algorithms. Electron. Lett. 15, 701-702 (1979).

82. Nussbaumer H. J. Fast polynomial transform methods for multidumensional DFTs. Proc. JCASSP-80, April 9-11, 1980, Denver, Colorado, pp. 235-237.

83. Nussbaumer H. J. New Algorithms for Convolution and DFT Based on Polynomial Transforms. IEEE 1978 Intern. Conf. Acoust., Speech, Signal Processing Proc., pp. 683-641.

84. PDSP16515A, Stand Alone FFT Processor, Advance Information. Mitel Corporation 1998 Publication No. DS3922 Issue No. 1.5 October 1996.

85. PDSP16510A, Stand Alone FFT Processor, Advance Information. Mitel Corporation 1998 Publication No. DS3475 Issue No. 4.4 May 1996.

86. Programs for Digital Signal Processing. ISBN 0-87942-127-4, New York, IEEE Press, 1979.

87. The FFT Demystified / Engineering Productivity Tools Ltd. (http://www.eptools.com), 1999.

88. Rabiner L.R., Gold B. Theory and Application of Digital Signal Processing. Prentice-Hall, Englewood cliffs, N.J. 1975

89. Rader C.M., Brenner N.M. A New Principle for Fast Fourier Transformation, IEEE Trans. Acoust., Speech, Signal Proc. ASSP-24 (1976): 2664-265.

90. Sebastian Egner S., Püschel M. Automatic Generation of Fast Discrete Signal Transforms/ IEEE Transactions On Signal Processing, Vol. 49, No. 9, September 2001.

91. Selesnick I. W., Burrus C. S. Automatic Generation of Prime Length FFT Programs/ Department Electrical and Computer Engeneering, Rice University, Houston, 1995.-29 pp.

92. Sepiashvili D. Performance Models and Search Methods for Optimal FFT Implementations /Electrical and Computer Engeneering Department, Carnegie Mellon University, 2000. 92 pp.

93. Steven W. Smith. The Scientist and Engineer's Guide to Digital Signal Processing / California Technical Publishing, 1997.

94. Wang Z. Fast algorithms for the discrete W. transform and for the discrete Fourier transform // IEEE Trans.: ASSP-32.-1984.-P.803-816.

95. Welch P. D. A fixed-point fast Fourie transform error analysis. IEEEE Trans. AU-17, 151-157(1969).

96. Winograd S. A New Method for Computing DFT. IEEE Intern. Conf. Acoust., Speech and Signal Processing Proc., pp. 366-368 (1977).

97. Winograd S. On computing the discrete Fourie transform/ Math. Comput. 32, 175-199(1978).