Содержание к диссертации
Введение
1. Методы вычисления дискретного преобразования Фурье 12
1.1 Алгоритмы преобразования Фурье дискретной последовательности данных 12
1.2 Методы повышения эффективности преобразования Фурье 17
1.3 Характерные параметры алгоритмов ДПФ 21
Выводы 22
2. Дискретное преобразование Фурье 24
2.1 Математическое описание неэквидистантных временных рядов 24
2.2 Дискретное преобразование Фурье неэквидистантных временных рядов 28
2.3 Дескрипторный метод вычисления ДПФ 31
2.4 Дескрипторный метод вычисления БПФ 42
2.4.1 Дескрипторный метод по алгоритму Кули-Тьюки 43
2.4.2 Дескрипторный метод по алгоритму Винограда 52
2.5 Вычислительная сложность алгоритмов 55
Выводы 57
3. Система имитационного моделирования расчета преобразования Фурье 59.
3.1 Структура программного комплекса 59
3.2 Моделирование входных воздействий 70
3.3 Моделирование потока с нерегулярной дискретизацией 80
3.4 Параметры расчета ДПФ 85
4. Анализ характеристик алгоритмов преобразования Фурье 90
4.1 Погрешность вычисления ДПФ неравномерно дискретизированной последовательности 91
4.2 Анализ времени вычисления ДПФ неравномерно дискретизированной последовательности 103
4.3 Погрешность при сокращении разрядности входного сигнала 107
4.4 Погрешность "ошибочной" адресации 112
4.5 Анализ времени вычисления ДПФ равномерно -дискретизированной последовательности 114
4.6 Анализ времени вычисления ДПФ последовательностей различной длины 124
Выводы 127
5. Спектральный анализ вариабельности сердечного ритма 129
5.1 Общие положения 129
5.2 Оценка спектральной мощности ритмограмм 131
6. Рекомендации по проектированию дескрипторных алгоритмов ДПФ 138
6.1 Общий порядок проектирования 138
6.2 Рекомендации по проведению занятий по изучению дескрипторных алгоритмов ДПФ 141
Заключение 146
Список использованных источников 148
- Методы повышения эффективности преобразования Фурье
- Дескрипторный метод по алгоритму Кули-Тьюки
- Моделирование потока с нерегулярной дискретизацией
- Анализ времени вычисления ДПФ равномерно -дискретизированной последовательности
Введение к работе
Дискретное преобразование Фурье лежит в основе широкого круга задач современной цифровой обработки сигналов, главной из которых остается спектральный анализ /14-17,20-25,36,69/. Систематизации данных и разработке новых алгоритмических решений вычисления ДПФ посвящено множество работ как отечественных исследователей (Агаян С. С, Ярославский Л. П., Лабунец В. Г., Чернов В. М. и др.) так и зарубежных (Кули, Тьюки, Виноград, Нуссбаумер и др.).
Наряду с классическим подходом в последнее время возрастает интерес к анализу характеристик неравномерно дискретизированных последовательностей, когда интервал дискретизации Att не является постоянной величиной. В этом случае сигнал описывается двумя массивами выборочных данных: массивом мгновенных значений {х{) и массивом соответствующих меток времени {/j}. Причем индекс / в этом случае характеризует лишь место отсчёта или метки времени в массивах, где хранятся входные данные, а не характеризует время наступления события. Подобными последовательностями представляются результаты измерений при решении разнообразных задач, например /48/:
статистические измерения с применением адаптивных систем сбора и обработки информации;
неточность датирования в многоканальных системах;
дискретизация с пропусками, сбоями наблюдений;
стохастическое и квазистохастическое кодирование;
потоки отсчетов в цифровых системах передачи информации, использующих коды с обнаружением ошибок, в синхронных многоканальных системах передачи информации с временным уплотнением, в асинхронно-адресных системах связи, в системах передачи информации с многостанционным доступом, в спутниковых системах связи;
- принципиальная невозможность получения равномерных отсчетов в ходе
проведения эксперимента при теплофизических, океанологических и
океанографических исследованиях и т.д.
Таким образом, сформировались три основных направления статистических измерений спектральных характеристик неэквидистантных временных рядов:
оценка без учета нерегулярности временного ряда;
оценка с предварительным восстановлением в промежуточных точках (точках регулярной дискретизации) с учетом модели и критерия восстановления;
оценка без восстановления неэквидистантного временного ряда в промежуточных точках и с использованием только существенных отсчетов или соответствующих им меток времени.
Первые два направления ориентированы на применение классической теории оценивания и соответствующих ей классических алгоритмов и аппаратно-программных средств. Третье является наиболее актуальным и требует разработки новой теории оценки их характеристик, принципов построения и проектирования видов обеспечения и аппаратно-программных средств.
Другим аспектом исследований является повышение эффективности вычислений ДПФ. Совершенствование элементной базы и методов проектирования позволило значительно расширить возможности аппаратной и программной реализации алгоритмов, повысить точность, быстродействие и другие показатели эффективности. Однако, несмотря на постоянный рост быстродействия вычислительных систем, появление специализированных процессоров с адаптированным набором команд не оставляются попытки снизить трудоемкость расчета путем создания новых скоростных алгоритмов преобразования Фурье над дискретными последовательностями данных . /35,58-60,68,75-78,91,98/.
8 Следует отметить, что общая сложность алгоритма определяется не только числом арифметических операций — алгебраической сложностью, но и количеством необходимой памяти, стоимостью вспомогательных операций /59,79,92-94/. Эффективность может быть существенно снижена излишней структурной сложностью или некорректной аппаратно-программной реализацией /88,90,95/. Отсюда вытекает основная задача проектирования -соблюдения баланса между перечисленными составляющими в рамках конкретной задачи.
В последнее время совершенствование алгоритмов БПФ происходит в направлении разработки специальных алгоритмов, например, для расчета преобразования Фурье вещественных последовательностей /30,60,68/. Вряде случаев эффективным решением может служить применение преобразования Хартли /12,13,65,70,96/. Однако, по числу арифметических операций БПХ практически не имеет преимуществ перед БПФ. При этом наиболее весомым преимуществом преобразования Хартли является сокращение объема памяти .коэффициентов в два и более раза. Алгоритмы БПХ имеют более простую, симметричную для прямого и обратного преобразований структуру вычислительного процесса, что дает преимущество при реализации вычислителей конвейерного типа.
Другим перспективным направлением развития является применение полиномиальных и теоретико-числовых преобразований для вычисления ДПФ /9,34,40,62/. Вычисление ДПФ с помощью полиномиальных преобразований основано на использовании корней из 1 в кольцах полиномов. Вычисления проводятся с использованием обычной арифметики без умножения. Если длины последовательностей выражаются составными числами, вычисления могут быть организованы посредством алгоритмов типа БПФ. Для вычисления ДПФ на основе теоретико-числовых преобразований применяются алгоритмы, основанные на использовании одномерных и двумерных циклических сверток. Однако наибольшая эффективность вычислений может быть достигнута только в случае, когда
9 подобные преобразования реализуются с помощью специальных вычислительных средств, эффективно реализующих модулярную арифметику.
Важным аспектом цифровой обработки является то, что современные динамические системы требуют создания методов вычисления ДПФ по ограниченному набору данных. Например, анализ спектральных характеристик нестационарных процессов часто производят разбиением исходной последовательности на несколько коротких, условно стационарных реализаций, с дальнейшим применением метода скользящего БПФ. При этом большее внимание уделяется качественной оценке характеристик сигналов в виду того, что обычно погрешность алгоритмической оценки имеет тот же порядок, что и погрешности, вызванные сокращением объема выборки, нерегулярностью дискретизации процесса и прочими ошибками представления исходного сигнала. Другими словами, определенный круг задач требует создания алгоритмов вычисления ДПФ, главным критерием эффективности которых будет скорость вычислений при возможном сохранении точности.
Целью данного исследования является разработка, теоретическое и экспериментальное обоснование алгоритма и метода вычисления ДПФ неравномерно дискретизированных последовательностей, использующего только существенные отсчеты, обладающего низкой арифметической и структурной сложностью, высокой точностью и быстродействием, возможностью вариации параметров алгоритма с целью достижения требуемой точности.
Для этого необходимо:
провести обзор и сравнительный анализ современных алгоритмов ДПФ, их структурной и алгоритмической сложности;
дать обобщенную классификацию способов повышения эффективности;
разработать алгоритм вычисления ДПФ НВР без восстановления пропущенных отсчетов;
разработать дескрипторный метод вычисления ДПФ НВР, отличающийся повышенным быстродействием по сравнению с прямым методом;
разработать и реализовать имитационную модель алгоритма для оценки методической погрешности оценки ДПФ НВР;
провести вычислительный эксперимент для исследования свойств разработанных методов на примере модельных и реальных выборок данных.
Научная новизна:
алгоритм оценки ДПФ НВР без восстановления пропущенных отсчетов;
дескрипторный метод оценки ДПФ НВР и его модификации, отличающийся повышенным быстродействием при сохранении точностных характеристик;
результаты анализа быстродействия и методической погрешности предлагаемого алгоритма методом имитационного моделирования.
Практическая ценность:
структуры дескрипторных вычислителей ДПФ;
комплекс программ имитационного моделирования и оценки ДПФ НВР
без восстановления пропущенных отсчетов;
зависимости оценки ДПФ от специфических характеристик неравномерно дискретизированных сигналов различной природы;
методика построения дескрипторных вычислителей.
Результаты исследований базируются на положениях теории вероятностей и математической статистики, теории случайных процессов и потоков событий, а также использовании системного анализа, численных методов и методов имитационного моделирования.
Содержание работы:
В первой главе производится обзор существующих алгоритмов дискретного преобразования Фурье, а так же методов повышения эффективности его вычисления. Дана обобщенная классификация
алгоритмов ДПФ. Отмечены два пути повышения скорости вычисления ДПФ — алгоритмический и аппаратный.
Во второй главе приводятся аналитические выражения для расчета ДПФ НВР, рассматривается новый — дескрипторный - способ вычисления ДПФ, базирующийся как на классическом алгоритме вычислений, так и на быстрых методах - БПФ. Приведены структурные схемы вычислителей и оценки алгоритмической сложности.
Третья глава посвящена описанию системы имитационного моделирования расчета ДПФ различных видов случайных сигналов с различными значениями параметров расчета. Данная система может быть использована для оценки точности как классических, так дескрипторных методов расчета ДПФ, а так же спектральной обработки реальных массивов данных.
В четвертой главе приводятся результаты имитационного моделирования расчета ДПФ случайных и псевдослучайных сигналов, анализ критериев для выбора оптимальных значений параметров расчета.
Пятая глава содержит результаты спектрального анализа данных о вариабельности сердечного ритма человека, представляющих собой нестационарный процесс с неравномерной дискретизацией.
В шестой главе приведен общий порядок проектирования дескрипторных алгоритмов ДПФ и рекомендации по проведению практических занятий.
В заключении приводятся основные результаты и выводы, полученные в работе.
Приложения содержат описание пакета прикладных программ имитационного моделирования расчета ДПФ и графические результаты расчетов.
Методы повышения эффективности преобразования Фурье
Таким образом, подав на вход фильтра сигнал v(n) = x(n)W /2, выбрав отсчеты выходной последовательности с номерами п=0, ...2N-ln умножив их на коэффициенты Wk exp(—J7iN), получим iV-точечное ДПФ исходной последовательности х(п).
В литературе /39/ можно найти описание косвенного вычисления ДПФ на основе время-импульсной модуляции. Основой метода служит тот факт, что при малых значениях индекса модуляции амплитудная (время-импульсная) модуляция равнозначна фазовой (а значит и частотной), а спектр модулированного сигнала представляет собой сумму сдвинутых спектров дельта импульсов.
По характеру построения алгоритмов можно выделить: 1. Классический алгоритм — прямой точный метод вычисления дискретного преобразования Фурье в поле комплексных чисел, соответствующий формуле (1.1). 2. Быстрые алгоритмы — представляют собой модификации ДПФ, призванные снизить алгоритмическую сложность вычисления. Основная идея БПФ состоит в том, чтобы исходную последовательность разбить на более короткие последовательности, ДПФ которых могут быть скомбинированы таким образом, чтобы объединение их дало исходное N-точечное ДПФ. Базовыми являются /11/: 1) Алгоритм БПФ Кули-Тьюки; 2) Алгоритм простых множителей Гуда-Томаса; 3) Алгоритм Винограда . __.. .. .. __...... Кодирование области значений сигналов в некотором коммутативном кольце с единицей обеспечивает вычисление ДПФ путем теоретико-числовых преобразований /9,60/. Развитием указанных алгоритмов являются полиномиальное преобразование Нуссбаумера и гибридный алгоритм Рида— Труонга/40,83-85/. С точки зрения точности метода, лежащего в основе вычислений, алгоритмы можно разделить: 1. Точные алгоритмы - алгоритмы, в которых теоретически возможно достижение нулевой погрешности вычислений. Если исключить ошибки систем, связанные с аппаратными ограничениями, то большинство существующих алгоритмов являются точными. 2. Приближенные алгоритмы - аппроксимативные, методическая погрешность которых не может быть сведена к нулю. Так, например, известны методы /39/ спектрального анализа сигналов на основе аппроксимации функцией синуса малых аргументов и на основе аппроксимации корреляционной функции сигнала ортогональными полиномами /45/. По способу обработки входных данных алгоритмы делятся: - алгоритмы, допускающие обработку по мере поступления отсчетов входной последовательности в реальном масштабе времени; - алгоритмы, работа которых требует наличия всей последовательности. По способу формирования выходной последовательности различают алгоритмы, рассчитывающие полный спектр сигнала (таких большинство), и алгоритмы расчета отдельных спектральных составляющих (типичный пример - алгоритм Герцеля)/5,11/. Существуют специализированные алгоритмы оценки ДПФ вещественных входных последовательностей /13,68/ (например, на основе алгоритма Хартли), и алгоритмы расчета ДПФ комплексных сигналов. Последние обладают возможностью расчета ДПФ действительных сигналов удвоенной длины При оценке спектральных характеристик неравномерно дискретизированных процессов непосредственное применение теории ДПФ невозможно, так как исходные данные представляют собой два массива: массив мгновенных значений {xt} и массив соответствующих меток времени {t\}. Причем индекс /.в этом случае характеризует лишь место отсчёта или метки времени в массивах, где хранятся входные данные, а не характеризует время наступления события. Возможны три подхода к анализу подобных сигналов/48/: 1) оценка без учета нерегулярности временного ряда. В этом случае информация о временной расстановке отсчетов не учитывается. В простейшем случае находится некоторый средний интервал дискретизации и применяются классические методы оценивания /72,73/. При этом страдает частотное разрешение, т.к. ДПФ содержит число точек Л/, равное числу существенных отсчетов входного сигнала без учета пропусков. 2) оценка с предварительным восстановлением в промежуточных точках. Данный метод дает хорошие результаты только в случае, когда имеется информация о модели восстановления сигнала в точках регулярной дискретизации /24,46/. Далее будет показано, что применение простейших неадекватных методов восстановления, таких как, например линейная интерполяция сигнала, приводит к существенному искажению высокочастотной области спектра. После проведения операции восстановления также применяются алгоритмы классической теории ДПФ. 3) оценка на основе только существенных отсчетов и соответствующих им меток времени. В данном случае предлагается производить оценку на основе только реальных данных, но с учетом пропущенных отсчетов. Это должно привести: - к снижению погрешности, вызванной неадекватностью алгоритма восстановления сигнала в промежуточных точках; - сохранению частотного разрешения за счет верного датирования отсчетов; - к снижению времени вычислений за счет сокращения объема обрабатываемых данных.
Дескрипторный метод по алгоритму Кули-Тьюки
Рассмотрим возможность модификации быстрых алгоритмов преобразования Фурье в соответствии с предлагаемым методом. Такие вычисления обычно реализуются посредством программ для ЭВМ или цифровых сигнальных процессоров. Как правило, эти алгоритмы организованы в виде многоступенчатых процедур вычисления ДПФ длинной последовательности, через преобразование более коротких последовательностей. Это накладывает определенные ограничения: на использование предлагаемого алгоритма. Процесс вычисления ДПФ сигнальными процессорами может быть организован двумя способами: с использованием вычислений с плавающей или фиксированной точкой. При вычислениях с плавающей точкой точность представления результатов выше, однако, операции с такими числами производятся значительно медленнее. Поэтому довольно часто применяются методы расчета ДПФ в арифметике с фиксированной точкой, а для предотвращения переполнения разрядной сетки используют масштабирование результатов.
Ранее было показано, что для реализации дескрипторного метода вычислений ДПФ необходимо иметь жестко заданный диапазон уровней квантования сигнала. Данный диапазон, а, следовательно, объем памяти, определяется числом разрядов, используемых для представления амплитуды входного сигнала. Однако для эффективной организации вычислений в арифметике с плавающей точкой необходимо значительно большее количество разрядов (типовое минимальное значение - 4 байта). Как следствие этого, потребуется значительно больший объем памяти для хранения коэффициентов дескрипторного преобразования.
Исходя из выше изложенного, далее при описании алгоритмов будет подразумеваться, что расчет выполняется в арифметике с фиксированной точкой.
Произведем модификацию предлагаемого алгоритма для случая, когда длина последовательности N является составным числом N =NjN2. Это позволяет перейти к двумерному преобразованию и использовать для вычислений более эффективные алгоритмы, однако существенно усложняет структуру вычислений.
В соответствии с описанными выше свойствами периодичности и симметричности комплексной экспоненты, входящей в состав (2.5), значения ячеек памяти {Мет} будут определенным образом повторяться. Это является предпосылкой к повышению эффективности вычисления ДПФ путем разбиения последовательности длины N на. последовательности меньшей - длины. Будем называть это понижением порядка дескрипторного алгоритма ДПФ. Данная процедура по аналогии с. классическим алгоритмом Кули-Тьюки должна привести к уменьшению количества арифметических операций, необходимых для вычисления ДПФ /71/.
Рассмотрим алгоритм БПФ Кули-Тьюки по основанию два, который, как известно, состоит из однотипных базовых операций "бабочка", графы которых представлены на рисунке 2.6(a). На их основе составим алгоритм графов для вычислений дескрипторным методом 2.6(6). На рисунке 2.7 представлены модифицированные операции "бабочки" для алгоритмов с прореживанием по времени и частоте.
Согласно рисунку 2.6(a), на каждом этапе вычислений происходит умножение сигнала на поворачивающий коэффициент и накопление результата. Это должно неограниченно увеличивать количество уровней квантования, которые необходимо кодировать. На практике, для избежания переполнения сумматоров производится различного вида масштабирование промежуточных данных путем сдвига данных вправо на определенное число разрядов. Это ограничивает динамический диапазон системы, а следовательно и число кодируемых уровней, что делает возможным замену операции умножения выборкой из памяти (рисунок 2.7).
При исходной разрядности сигнала L на входе каждой "бабочки" сигнал на ее выходе будет содержать максимум L+1 разряд. При использовании схемы масштабирования со сдвигом вправо на один разряд на каждом этапе динамический диапазон системы будет неизменным на всем протяжении вычислений. Т.е. необходимое количество кодируемых уровней квантования при математическом ожидании входного сигнала равном нулю составит; 2 К Однако такая схема масштабирования не всегда дает удовлетворительные результаты по точности вычислений. Ошибка, появляющаяся в результате усечения (округления) результатов после деления, приводит к ошибочной адресации ячеек памяти коэффициентов. Как известно /15,28,97/, ошибки квантования при округлении и усечении являются величинами случайными и имеют равномерный закон распределения. Максимальная ошибка округления составляет половину шага Л 7, выбранного для квантования уровня сигнала. Максимум ошибки усечения вдвое больше и равен Aqy однако данная операция технически значительно проще. Она реализуется простым сдвигом содержимого ячейки памяти на один разряд вправо. На практике, для промежуточного масштабирования результатов используют операции сдвига.
Моделирование потока с нерегулярной дискретизацией
Одним из видов эксперимента, проводимого с помощью системы имитационного моделирования, является возможность вычисления ДПФ, используя входные сигналы произвольной разрядности. Как было показано в главе 2, разрядность входного сигнала при вычислениях дескрипторным методом в значительной степени определяет объем требуемой памяти. Изменение разрядности сигнала на различных участках расчета ДПФ представлено на рисунке 3.18.
Как уже отмечалось, разработанная система имитационного моделирования оценивает погрешность расчета ДПФ. методом образцового сигнала. Вычисления в исследуемых методах ДПФ производится в целых числах и коэффициенты хранятся в виде целого числа со знаком.
В качестве исходного для моделирования на языке Delphi5 слов с малой разрядностью использовался целый тип Shortlnt, представляющий на большинстве современных ЭВМ 8-разрядное слово со знаком и фиксированной точкой /51/. Нужная разрядность слов достигается сдвигом содержимого вправо и отбрасыванием нулевых старших разрядов при вычислениях.
С целью создания равных условий при проведении сравнительных экспериментов как в классическом так и дескрипторном случае используется один двумерный массив элементов Shortlnt. Размерность массива составляет [(n k)modN х пих]. При выполнении классического преобразования в нем хранятся поворачивающие коэффициенты преобразования, и адресация осуществляется Mem\addr,l\. В случае дескрипторного преобразования коэффициенты представляют собой готовые произведения, а в адресации используется текущая амплитуда отсчета: Mem\addr, х(п) \. Этим достигается единообразность структуры массива для всех видов экспериментов, создаваемая компилятором языка Borland Delphi 5.
Восьмиразрядное ограничение разрядности слов в массиве является скорее вынужденным, т.к. значительно сокращает объем требуемой памяти при сохранении массивов и в оперативной памяти и на жестком диске ЭВМ. Однако данное ограничение разрядности вносит в вычисления "погрешность квантования коэффициентов" при сравнении с образцовым сигналом, являющуюся одним из предметов исследований. Другим элементом эксперимента является возможность восстановления сигнала простейшими интерполяционными моделями (рисунок 3.19)/24/: - восстановление ближайшим правым отсчетом; - восстановление ближайшим левым отсчетом; - восстановление ближайшим отсчетом; - восстановление с помощью линейной интерполяции. Важной задачей является оценка времени вычисления преобразования Фурье. В выбранной для моделирования многозадачной операционной системе Windows фиксация малых временных интервалов связана со значительными трудностями. Это связано с тем, что каждая задача/поток выполняется ОС с определенным приоритетом, в соответствии с которым автоматически распределяются ресурсы системы. Другим фактором, вносящим погрешность в измерение времени, является тот факт, что в силу разности архитектур различных процессоров и операционных систем выполнение одних и тех же операций с данными может требовать различного количества командных циклов (приложение 3). Учет всех перечисленных факторов достаточно сложен, поэтому наилучшими условиями для проведения эксперимента является однопроцессорная система с минимумом запущенных процессов (особенно с высокими приоритетами) и минимальным использованием виртуальных и кэш-ресурсов. В разработанной системе имитационного моделирования расчета ДПФ время вычисления можно оценить двумя способами (приложение 2). Первый основан на использовании команды RDTSC (Read Time Stamp Counter) процессоров семейства Pentium. Она возвращает значение внутреннего 64-битного таймера, соответствующее количеству тактов с момента подачи напряжения или сброса процессора. Это значение, измеренное до и после процедуры вычислений, при известной тактовой частоте процессора дает оценку временного интервала. Другой способ основан на использовании функций API операционных систем Windows /3/. Функция QueryPerformanceFrequency позволяет получить частоту инкремента таймера, подключенного по шине ISA или ее аналога в современных наборах микросхем, а функция QueryPerformanceCounter — его текущее значение до и после выполнения процедуры вычисления ДПФ. Если система не может прочитать значение таймера, то функция QueryPerformanceCounter возвращает нуль. Экспериментальные исследования проводятся методом имитационного моделирования. Это позволяет обойти трудности, связанные с аналитической оценкой исследуемых величин и погрешностей. Важным преимуществом при этом является неограниченная возможность повтора эксперимента, причем исходными данными могут служить как модельные значения, так и реальные выборки данных. При анализе свойств дескрипторных алгоритмов будем использовать аппарат теории вероятностей /31,56,57/. Поскольку алгоритмы ДПФ исследуются на моделях случайных сигналов, то методическая погрешность так же будет величиной случайной. Время расчета преобразования является величиной постоянной при фиксированной длине выборки, однако при расчете на ЭВМ тоже будет меняться ввиду особенностей архитектуры и операционных систем. Характер сигналов, выбранных для анализа в главе 3, позволяет говорить об их стационарности и эргодичности. Кроме того, каждая реализация, генерируемая системой имитационного моделирования, приводится к нулевому среднему тх=0. Тогда для анализа будем использовать методику, изложенную в /45,62/: при усреднении по множеству реализаций максимального значения модуля приведенной погрешности Aj доверительная вероятность Ра=0,95 попадания истинного значения в интервал [- А ; А J обеспечивается 29-ю испытаниями независимо от закона распределения.
Анализ времени вычисления ДПФ равномерно -дискретизированной последовательности
В общем случае, процесс проектирования дескрипторных алгоритмов состоит из нескольких этапов: 1. Оценка исходных данных и постановка задачи 2. Выбор алгоритма-прототипа; 3. Расчет параметров алгоритма; 4. Разработка схемы вычислителя или программы; 5. Проверка и анализ результатов. Рассмотрим данную схему более подробно. 1. Оценка исходных данных и постановка задачи На данном этапе разработчик должен проанализировать данные, подлежащие обработке: динамический диапазон выборки, частоту дискретизации, коэффициент сжатия последовательности, поступают ли данные в режиме реального времени или обрабатывается оцифрованный массив данных. Очень полезно, если исходный процесс будет центрирован относительно ноля. Он обязательно должен иметь максимальную амплитуду, не превышающую допустимое значение для данного типа входного аналог-цифрового преобразователя. На основе требований к точности результата вычислений и частотному разрешению, исходя из частоты дискретизации сигнала, выбирается объем выборки данных. На основе данных о коэффициенте сжатия последовательности вычислитель может быть снабжен "детектором ноля", исключающим из обработки нулевые отсчеты. Требования задачи по скорости расчета и в частности режим работы вычислителя будет определять выбор алгоритма-прототипа. Вычисление ДПФ классическим дескрипторным методом можно организовать без использования в схеме арифметико-логического устройства, но данный вид требует значительного объема памяти коэффициентов. Дескрипторные алгоритмы Кули-Тьюки или Винограда менее требовательны к памяти, но имеют более сложную логическую структуру и всегда реализуются программно.
Необходимо рассмотреть ограничения на применение дескрипторных методов в быстрых алгоритмах ДПФ, связанные с погрешностью "ошибочной адресации", вызванной промежуточным масштабированием данных.
После выбора алгоритма-прототипа определяется общее количество коэффициентов, необходимых для вычисления преобразования. На основе свойств базисных функций и вида алгоритма находится количество нетривиальных коэффициентов, требующих размещения в массиве памяти. Это число умножается на количество уровней квантования входного сигнала или на вдвое меньшую величину при центрировании относительно нуля. Результат дает общее число слов памяти для размещения коэффициентов, необходимых для вычисления дескрипторного преобразования.
Данный пункт также связан с выбранным ранее алгоритмом-прототипом. Он определяет требуемый объем микросхем памяти, необходимость применения микропроцессора и устройств выборки-хранения, тактовую частоту работы схемы. Схемная реализация вычислителя будет зависеть от применяемой элементной базы, программная - от оптимальности реализации алгоритма в машинном коде.
На данном этапе проводят тестирование вычислителя на моделях сигналов, близких к исследуемым. Производится анализ скорости вычисления ДПФ и результирующей погрешности оценки.
Одним из вариантов анализа является расчет системы в условиях "наихудшего случая". Эта методика была применена для анализа параметров алгоритмов в главе 4. В этом случае исследователь задается максимальным значением абсолютной погрешности вычисления гармоник. Если по результатам статистических исследований параметры превышают максимально допустимые значения и не удовлетворяют поставленной задаче, исследователь возвращается к расчету параметров реализуемого алгоритма и корректирует значения длины выборки, разрядности входного АЦП, размера слова памяти коэффициентов и корректирует алгоритм промежуточного масштабирования.
Вообще, как и во многих других случаях, приступая к разработке анализатора спектра на основе дескрипторных алгоритмов удобнее сначала разработать программную модель требуемого вычислителя и провести исследования методом имитационного моделирования. Это значительно облегчит процесс подбора параметров алгоритма, обеспечивающих требуемые значения быстродействия и точности вычислений.
Изучение дескрипторных методов расчета дискретного преобразования Фурье может проводиться в рамках разделов, посвященных цифровой обработке сигналов и спектральному анализу, наряду с классическими и быстрыми алгоритмами расчета ДПФ.
Методические указания по проведению практических занятий будут содержать следующие разделы: 1. Общие сведения о методах расчета дискретного преобразования Фурье. Раздел содержит основные определения и расчетные формулы, принятые в теории цифровой обработки сигналов. 2. Дескрипторный метод расчета ДПФ (ДДПФ). 2.1 ДДПФ на основе прямого метода расчета; 2.2 ДДПФ на основе алгоритма Кули-Тьюки по основанию два; 2.3 ДДПФ на основе алгоритма Винограда. В данном разделе дается теория дескрипторного алгоритма, основные формулы для расчета параметров. Раздел может содержать примеры и задачи на построение дескрипторных алгоритмов, оценку вычислительной сложности и эффективности применения различных методов в качестве прототипа. В качестве образца можно использовать примеры расчета 8-точечного ДПФ дескрипторным методом, приведенные в главе 2.
