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

ЛИЧНЫЙ КАБИНЕТ 

 

Здравствуйте гость!

 

Логин:

Пароль:

 

Запомнить

 

 

Забыли пароль? Регистрация

Повышение уникальности

Предлагаем нашим посетителям воспользоваться бесплатным программным обеспечением «StudentHelp», которое позволит вам всего за несколько минут, выполнить повышение уникальности любого файла в формате MS Word. После такого повышения уникальности, ваша работа легко пройдете проверку в системах антиплагиат вуз, antiplagiat.ru, etxt.ru или advego.ru. Программа «StudentHelp» работает по уникальной технологии и при повышении уникальности не вставляет в текст скрытых символов, и даже если препод скопирует текст в блокнот – не увидит ни каких отличий от текста в Word файле.

Результат поиска


Наименование:


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

Информация:

Тип работы: Реферат. Предмет: Математика. Добавлен: 25.05.2010. Сдан: 2010. Уникальность по antiplagiat.ru: --.

Описание (план):


35
РЕФЕРАТ
по дисциплине «Анализ временных рядов»
на тему:
«Алгоритм фильтрации, пример на основе БПФ»
СОДЕРЖАНИЕ
Введение
1. Основы алгоритмов БПФ
2. Алгоритм БПФ с прореживанием по времени
3. Программа и пример реализации алгоритма БПФ с прореживанием по времени
4. Алгоритм БПФ с прореживанием по частоте
5. Применение метода БПФ для вычисления обратного ДПФ (ОДПФ)
6. Применение БПФ для вычисления реакции ЦФ
7. Другие быстрые алгоритмы вычисления дискретного преобразования Фурье
7.1 Обобщенный алгоритм Кули-тьюки с произвольным основанием с множителями поворота
7.2 Алгоритм простых множителей
7.3 Алгоритм винограда
8. Анализ точности реализации алгоритмов БПФ
Заключение
Список использованных источников
ВВЕДЕНИЕ
В основе преобразования Фурье (ПФ) лежит чрезвычайно простая, но исключительно плодотворная идея - почти любую периодическую функцию можно представить суммой отдельных гармонических составляющих (синусоид и косинусоид с различными амплитудами A, периодами Т и, следовательно, частотами щ).
Неоспоримым достоинством ПФ является его гибкость - преобразование может использоваться как для непрерывных функций времени, так и для дискретных.
ПФ часто применяется при решении задач, возникающих в теории автоматического регулирования и управления, в теории фильтрации и т.д. Разберем один из примеров. Имеется некий линейный фильтр - изготовленный то ли в виде набора спаянных между собой резисторов, конденсаторов и катушек индуктивности, то ли в виде модульной конструкции интегральных микросхем. Известен также входной сигнал (на рис. 1 в качестве входного сигнала изображена дельта-функция, то есть импульс исчезающе короткой длительности и бесконечно большой амплитуды). Необходимо определить, какой сигнал появится на выходе нашего фильтра.
Рисунок 1 - Исследование линейного фильтра
Ход решения этой задачи зависит от того, какую позицию мы предпочтем. Выберем временной путь решения (верхняя половина рис. 2) - придется входной сигнал записать как функцию времени SBX(t) и использовать импульсную характеристику фильтра h(t), то есть математическую запись его работы во времени. Отправимся по частотному пути (нижняя половина рис. 2) - нужно будет оперировать уже не с самим входным сигналом, а с его спектром gbx(щ). Да и алгоритм работы нашего фильтра потребуется представить в частотной области - в виде частотной характеристики K(щ). Для этого воспользуемся помощью «магического стекла» ПФ.
Рисунок 2 - Быстрое преобразование Фурье
Итак, два пути - какой из них избрать? По-видимому, тот, который проще. Во всяком случае, в большинстве практических задач предпочтение отдается частотному направлению.
Если выполнять ДПФ входной последовательности, впрямую - строго по исходной формуле, то потребуется много времени (особенно если количество входных отсчетов велико). Конструктивнее использовать принцип «разделяй и властвуй», лежащий в основе алгоритма БПФ. Согласно ему входная последовательность делится на группы (например, четные и нечетные отсчеты), и для каждой из них выполняется ДПФ, а затем полученные результаты объединяются. В итоге получается ДПФ входной последовательности - и существенная экономия времени. Поэтому описанный алгоритм так и назвали - быстрое преобразование Фурье.
В данном реферате рассмотрим более подробно быстрое преобразование Фурье.
1. ОСНОВЫ АЛГОРИТМОВ БПФ
Дискретное преобразование Фурье (ДПФ) X(k) конечной последователъности х(пТ), п=О, 1,..., N-1 определяется согласно (1.1), (1.2):
(1.1)
(1.2)
причем является периодической последовательностью с периодом N, так как т=О, 1, 2… Непосредственное вычисление ДПФ (5.1) при комплексных значениях х(пТ) требует для каждого значения k (N - 1) умножений и (N - 1) сложений комплексных чисел или 4 (N -1) умножений и (2N - 2) сложений действительных чисел, а для всех N значений k=0, 1,…, N -1 требуется примерно N2 умножений и N2 сложений комплексных чисел. Таким образом, для больших значений N (порядка нескольких сотен или тысяч) прямое вычисление ДПФ (1.1) требует выполнения весьма большого числа арифметических операций умножения и сложения, что затрудняет реализацию вычисления в реальном масштабе времени процессов и спектров.
Быстрым преобразованием Фурье называют набор алгоритмов, реализация которых приводит к существенному уменьшению вычислительной сложности ДПФ (1.1). Исходная идея этих алгоритмов состоит в том, что N-точечная последовательность разбивается, на две более короткие, например на две (N/2)точечные последовательности, вычисляются ДПФ для этих более коротких последовательностей и из этих ДПФ конструируется ДПФ исходной последовательности. Для двух (N/2)-точечных последовательностей требуется примерно умножений комплексных чисел, т. е. число умножений (а также сложений) уменьшается примерно в 2 раза. Аналогично вместо вычисления ДПФ (Н/2)-точечной последовательности можно вычислить ДПФ для двух (Н/4)-точечных последовательностей и таким образом вновь уменьшить требуемое число умножений и сложений. Если N=2v, v>O и целое, то процесс уменьшения размера ДПФ может быть продолжен до тех пор, пока не останутся только 2-точечные ДПФ. При этом общее число этапов вычисления ДПФ будет равно v=log2 N, а число требуемых арифметических операций для вычисления N-точечной ДПФ будет порядка Nv, т.е. уменьшается примерно в N/log2N раз. Так, при N=1000 для прямого вычисления ДПФ согласно (1.1) требуется примерно N2 = 106 операций комплексных умножений и сложений, а при использовании алгоритмов БПФ таких операций требуется всего порядка 104, т. е. объем вычислений сокращается примерно на два порядка.
Рассмотрим два алгоритма БПФ: с прореживанием по времени (в которых требуется перестановка отсчетов входной последовательности х(пТ)) и с прореживанием по частоте (в которых требуется перестановка отсчетов выходной последовательности Х(k)).
2. АЛГОРИТМ БПФ С ПРОРЕЖИВАНИЕМ ПО ВРЕМЕНИ
Пусть требуется вычислить ДПФ (1.1) при N=2v, где v>O. где v>O целое (если N 2V, то можно последовательность х(пТ) дополнить в конце нулевыми элементами так, чтобы длина результирующей последовательности была степенью 2).
Разобьем исходную N-точечную последовательность х(пТ)=хv (п), где v =log2 N. п=О...., N -1, на две (N/2)-точечные последовательности Хv-1,0(п) и Хv-1,1 (п), состоящие соответственно из четных и нечетных членов х (пТ), т. е.
(2.1)
При этом N-точечное ДПФ (1.1) можно записать в виде
(2.2)
Учитывая, что получаем
(2.3)
Где и - (N/2)-точечные ДПФ соответственно последовательностей и :
; .
Так как Xv (k) должно быть определено для N точек (k=0, 1,..., N-1), а Хv-1,0(k) и Хv-1,1(k) определяются толькo для N/2 точек (k=0, 1,..., N/2-1), доопределим (2.3) для значений k=N/2, N/2+1,...,N-1; учитывая, что Хv-1,0(k) и Хv-1,1(k)периодические функции с периодом Н/2, можно записать
Xv (k+N/2)= Хv-1,0 (k+N/2) + Хv-1,1 (k+N/2)= Хv-1,0 (k)- Хv-1,1 (k),
(2.4)
Так как = = -1.
Формулы (2.3) и (3.4) дают алгоритм вычисления N-точечной ДПФ через (N/2)-точечных ДПФ. Этот алгоритм можно представить направленным графом, имеющим вид «бабочки»
Рисунок 3 - граф имеющий вид «бабочки»
(рис.3, а), в котором выходные числа с и d получаются из входных чисел а и b по правилам
(2.5)
В качестве примера граф на рис.3, б представляет операции (2.3) и (2.4). Аналогично можно теперь выразить (N/2)-точечные ДПФ Хv-1,0 (k) и Хv-1,1(k) через (N/4)-точечные ДПФ:
(2.6а)
И
(2.7б)
где Хv-2,0(k) и Хv-2,1(k) - соответственно (N/4)-точечные ДПФ четных Хv-2,0(n) и нечетных Хv-2,1(п)
членов последовательности Хv-1,0 (п), а Хv-2,2(k) и Хv-2,3 (k)-соответственно (N/4)-точечные ДПФ четных Хv-2,2 (п) и нечетных Хv-2,3 (п) членов последовательности Хv-1,1(п).
Процесс уменьшения размера ДПФ от М до M/2, где М равна степени 2, продолжается до тех пор, пока на v-м шаге (v = log2 N, где N-исходный размер ДПФ) не окажутся только 2-точечные ДПФ Ф(k), k=0,1, для двухточечных последовательностей (п), п = 0,1, определяемые из соотношений
(2.8)
Последние вычисляются без операции умножения.
Пример 1. Построим алгоритм БПФ с прореживанием по времени для N=8=23, v=3, т. е. для последовательности х(пТ), п=0,1,2,З,4.5,6,7. Разобьем согласно (2.1) исходную последовательность х (пТ) = х3 (п) на две последовательности: x2,0 (п) и х2,1(n),-состоящие соответственно из четных и нечетных членов х3 (п):

\ (2.9)
Рисунок 4 - Алгоритм 8-точечного БПФ
Теперь вновь разобьем последовательности (2.9) на последовательности из нечетных и четных членов последовательностей (2.9):
(2.10)
Последовательности (2.10) являются уже двухточечными.
Теперь, используя алгоритм, представленный графом «бабочка» (см. рис.3, а), строим алгоритм 8-точечного БПФ (рис.4). Вначале построим исходный массив. Как видно из (2.10), он из элементов последовательности х(n)=х(nТ), n=0,1... 7, причем на входах первого графа «бабочка» первой ступени помещаются числа х(0) и х(4). На входах второго графа «бабочка» -числа х(2) и х(6), на входах третьей «бабочки» - х(l) и х(5) и на входах четвертой «бабочки» - x(3) и x (7).
Таким образом, если предположить, что последовательность Х(п) записывается в массив ячеек памяти, то удобно осуществить размещение х(п) в следующем порядке (рис.2): х(0), х(4), Х(2), х(6), х(1), х(5), х(3), х(7). Легко заметить, что элементы этой последовательности получаются из исходной х(п) в соотnетствии с двоичной инверсией номеров, т. е. число х(п) с номером в двоичном представлении п=(пv-1,..., n0) запоминается в ячейке памяти с номером =(n0,..., пv-1). Так, число х(4) с номером в двоичном представлении 4(10) = 100(2) запоминается в ячейке с номером 001(2)=1(10), а число х(3), где 3(10) =011(2), запоминается в ячейке с номером 110(з) =6(10) и т. д. Итак, можно считать, что начальная ступень преобразования Х0 (k), k=0,I... 7, получатся просто в результате прореживания (в указанном смысле) исходной временной последовательности х(пТ), п=0, I...7, т. е Х0 (k) = х (T), где k = - двоично-инверсное представление номера п.
На выходах N/2 = 4 «бабочек» т=l-й ступени образовываются значения Х2(k), являющиеся входными числами «бабочек» т=2-й ступени. На выходах последней значения выходной последовательности ХЗ (k)=X(k), k=0... 7. Выходная последовательность X(k), k=0,1...7, получается в естественном порядке следования.
Как показано в рассмотренном примере, все входные числа «бабочек» Х0 (k) на начальной ступени являются элементами заданной последовательности х(п), п=0... N-1, причем получаются из х(п) в соответствии с двоичной инверсией номеров т. е. число х(пТ)=х(п) с двоичным представлением номера п является входным числом Х0(k) «бабочки» с номером k, равным инверсному двоичному представлению номера п.
Заметим, что в рассмотренном алгоритме БПФ можно выполнить вычисления по способу с замещением. Если разместить входную последовательность Х 0(k) «бабочек» в массиве из 2v ячеек памяти, то после вычисления выходов «бабочек» входные элементы становятся ненужными и в указанные ячейки памяти могут быть записаны вычисленные выходные числа. На следующей ступени вновь вычисленные значения выходов «бабочек» записываются в ячейки массива вместо использованных входных чисел, и в конце вычислений во входном массиве окажутся записанными значения X(k) в естественном порядке, т. е. значения ДПФ при k=0, I, 2... N-1.
3. ПРОГРАММА И ПРИМЕР РЕАЛИЗАЦИИ АЛГОРИТМА БПФ С ПРОРЕЖИВАНИЕМ ПО ВРЕМЕНИ
Ниже при водится программа вычисления БПФ с прореживанием по времени по способу с замещением и рассматриваются при меры реализации этой программы.
Программа 1 - быстрое преобразование Фурье с основанием два и прореживанием по времени. Программа осуществляет алгоритм БПФ с основанием два и прореживанием по времени комплексной или вещественной последовательности х(п) длиной N отсчетов. Вещественные составляющие отсчетов исходной последовательности записываются в массив А1(N), а мнимые - массив А2(N). В программе для ознакомления с ее работой предусмотрено формирование входной последовательности, соответствующей отсчетам полигармонического сигнала
(3.1)
строки (80-240). При использовании программы для выполнения БПФ произвольной последовательности необходимо заменить строки 80-240, организовав ввод исходной последовательности.
Основными этапами обработки являются: ввод исходных данных (строки 50-240), двоично-инверсная перестановка исходной последовательности (строки 250-350), собственно алгоритм БПФ (строки 360-510), расчет амплитуд и фаз анализируемого сигнала по результатам БПФ (строки 520-590) и вывод результатов (строки 600-690). Пользователю выводятся в виде таблицы значения номера компоненты (гармоники) БПФ, вещественная и мнимая ее составляющие [Аl (1) и А2 (1)], амплитуда и фаза соответствующей гармоники [R (1) и Fl (1)].
Пример 2. Реализация БПФ вещественного сигнала содержащего три составляющие при значениях параметров: А0=2, w0=0=0, А1=I, w1=0,125, 1=0,7854, А2=3, w2=0,3125, 2=1,57.
В качестве исходных данных последовательно вводятся значения:
N=16; J=3; А(0)=2; w(0)=0; w1(0)=0; A(1)= 1; w(1)=0,125; w1 (1)=0,7854; А (2)=З; w(2)=0,3125; w1(2)= 1,57; I 9= 1;
Пример 3. Реализация БПФ комплексного сигнала (3.1), содержащего три составляющие (J=3), при значениях параметров Ak, wk и k таких же, как
в примере 2. Ввод исходных данных аналогичен примеру 2, за исключением того, что значение I 9=0.
4. АЛГОРИТМ БПФ С ПРОРЕЖИВАНИЕМ ПО ЧАСТОТЕ
Рассматриваемый ниже алгоритм вычисления ДПФ (1.1) отличается тем, что входная последовательность х(пТ), п=0,..., N -1, разбивается на две последовательности посередине (т. е. одна последовательность для n=0...N/2-1, а другая - для п=N/2...N-1) и эта процедура продолжается для каждой новой последовательности до тех пор, пока не получается искомая выходная одноэлементная последовательность Х (k); при этом величины Х (k) уже оказываются в выходном массиве в «прореженном» порядке и их приведение к естественному порядку связано с инверсией двоичного представления индексов k в вычисленных значениях Х (k).
Итак, запишем ДПФ (1.1) в виде:
(4.1)
Учитывая, что = получаем
. (4.2)

Подставив вместо k в (4.2) значение 2k или (2k+ 1), получим выражения для четных и нечетных отсчетов ДПФ: .
; (4.3)
, (4.4)
где теперь для значений:
Х0 (п)=х(п) +x(n+N/2); (4.5)
Х1(п)=х(п) -х(n+N/2). (4.6)

Рисунок 5 - Выполнение базовой операции «бабочка»
Следовательно, вычисление N-точечного ДПФ X(k) сводится к вычислению двух N/2-точечных ДПФ при четных и нечетных значениях k для функций х0(п) и x1 (п) и выполнению базовой операции «бабочка» (рис.5) отличие операции «бабочка» здесь заключается в том, что комплексное умножение выполняется после операции сложения-вычитания.
Ту же процедуру можно теперь применить к x0 (п) и х 1 (п) и перейти от N/2-точечных ДПФ к N/4-точечным ДПФ и, таким образом, свести вычисление Х (2k) и Х (2k + 1) через Х (4k), X(4k+2), X(4k+ 1), X(4k+3). Продолжив этот процесс, перейдем в конечном итоге к 2-точечным ДП Ф с последующим прямым вычислением всех выходных отсчетов Х (k). Полный алгоритм БПФ с прореживанием по частоте и его программная реализация аналогичны рассмотренным выше для метода БПФ с прореживанием по времени.
Необходимо отметить, что в обоих алгоритмах БПФ - и с прореживанием по времени, и с прореживанием по частоте требуется примерно Nlog2 N операций (комплексных умножений) и оба алгоритма могут быть реализованы по способу с замещением, используя только один массив ячеек памяти. В обоих алгоритмах должна быть предусмотрена процедура двоичной инверсии - на входе (при прореживании по времени) или на выходе (при прореживании по частоте).
5. ПРИМЕНЕНИЕ МЕТОДА БПФ ДЛЯ ВЫЧИСЛЕНИЯ ОБРАТНОГО ДПФ (ОДПФ)
По определению (1.2) ОДПФ х(пТ) N-точечной последовательности X(k), k=0, 1,..., N-1, выражается соотношением
(5.1)
причем в общем случае и х(пТ), и Х(k)-комплексные. Пусть х(пТ) и Х*(k)-последовательности, комплексно сопряженные соответственно с х(пТ) и X(k). Согласно (5.1) можно записать
(5.2)
Но выражение суммы в правой части (5.2) есть прямое ДПФ последовательности Х*(k), k=0,..., N-1, и, следовательно, эта сумма может быть вычислена при помощи рассмотренных алгоритмов и программ БПФ.
Таким образом обеспечивается вычисление последовательности Nx* (пТ) и для определения х(пТ) остается взять комплексно сопряженное с Nx*(пТ) выражение и разделить его на N:

(5.3)
6. ПРИМЕНЕНИЕ БПФ ДЛЯ ВЫЧИСЛЕНИЯ РЕАКЦИИ ЦФ
Вычисление реакции у(пТ) ЦФ с импульсной характеристикой h(пТ), п=0, 1,..., N-1, на входное воздействие х(пТ), п=О, 1,...M -1, может быть выполнено на основе алгоритма свертки
(6.1)
при п=0, 1,..., N+M-2.
Применение алгоритмов БПФ позволяет выполнить эффективное вычисление выходной последовательности у(пТ) ЦФ. С этой целью следует определить ДПФ H(k) и X(k) в N+M-1 точках для последовательностей h(пТ) и х(пТ), затем определить ДПФ Y(k)=H(k)X(k) выходной последовательности у(пТ). Вычисление у (пТ) по ОДПФ Y(k) выполняется, например, по алгоритму (5.3). Для вычисления ДПФ и ОДПФ используются алгоритмы БПФ. Отметим, что если длина М последовательности х(пТ) велика, то реализация упомянутого выше алгоритма вычисления у(пТ) связана со значительной временной задержкой (для накопления всех М выборок х(пТ)). С целью уменьшения этой задержки можно входную последовательность х(пТ) разбить на отрезки xi(пТ) каждый длиной L и обрабатывать каждый из них независимо от других. Представим
(6.2)

Тогда можно (6.1) записать в виде
(6.3)
Где частная свертка
(6.4)
Таким образом можно начинать расчет методами БПФ частных сверток и формировать у(пТ) путем соответствующего суммирования элементов частных сверток [2].
7. ДРУГИЕ БЫСТРЫЕ АЛГОРИТМЫ ВЫЧИСЛЕНИЯ ДИСКРЕТНОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ
7.1 Обобщенный алгоритм Кули-Тьюки с произвольным основанием с множителями поворота
Кроме рассмотренных выше классических алгоритмов БПФ известных как алгоритмы Кули-Тьюки по основанию 2, известно множество других. Некоторые из них позволяют существенно повысить эффективность вычисления дискретного преобразовании Фурье. Так, алгоритмы Винограда при равном числе сложении требуют примерно в 5 раз меньше умножений, чем алгоритмы Кули-Тьюки.
В основе всех известных алгоритмов лежит принцип разбиении исходного ДПФ на совокупность мало точечных. Различие заключается в способах вычисления мало точечных алгоритмов и последующего объединения частичных результатов. При этом размер преобразования не обязательно равен степени двух, т. е. становится возможным БПФ произвольной длины, что очень важно для ряда практических задач. Так, в технике связи при цифровом преобразовании многоканальных сигналов размер БПФ определяется числом объединяемых каналов.
Кратко рассмотрим только некоторые, наиболее важные алгоритмы, на основе которых впоследствии возникло множество различных эффективных модификаций. Это: 1) обобщенный алгоритм Кули-Тьюки с произвольным основанием с множителями поворота; 2) алгоритм простых множителей Гуда-Винограда и т.д.................


Перейти к полному тексту работы



Смотреть похожие работы


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