Авторизация


...

Кто на сайте?

Сейчас 193 гостей и ни одного зарегистрированного пользователя на сайте

Статистика

-Посетители : 23740
-Материалы : 209

Пользователь сайта продает...

  MB913 C-01

Пользователь сайта покупает...

Быстрое Преобразование Фурье

Автор: Алексей Просмотров: 4981
 
Итого всего лишь 4 комплексных умножения для 8 точечного ДПФ. И это не предел. (При этом имеется ввиду, что все т.н. поворачивающие множители вычислены уже заранее). Для примера рассмотрим входной вектор а (вещественный, длиной N=8) и его ДПФ (комплексный вектор у).

 

Где:
  • N = 8 Длина преобразуемого вектора.
  • a - входной вектор
  • z - ДПФ(а). Далее я его буду обозначать как у, чтобы не вносить путаницу между вычисляемым вектором у и вычисленным при помощи функции Mathcad вектором z
  • Здесь ДПФ получилось длиной 5, вопреки ожидаемых 8. Как мы увидим позже, остальные три координаты являются сопряженными к трем средним координатам вычисленного вектора, а следовательно тривиальным образом восстанавливаются из них. Это относится исключительно к ДПФ действительного вектора.

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

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

Для начала необходимо определить главный корень из i (мнимая единица):

 

 

 

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

Основная формула, это само ДПФ

 

 

 

Здесь:

Расписывать полностью формулу не имеет смысла, и так видно, что для вычисления ДПФ "в лоб", чтобы получить каждый у необходимо 8 комплексных умножений для каждого из них (имеется ввиду что W и его степени вычислены заранее, иначе появятся еще дополнительные комплексные умножения). Итого, в результате 64 комплексных умножения. Что достаточно много. И это число будет расти, вместе с увеличением количества выборок и для 64 точечного преобразования будет уже необходимо 4096 комплексных умножений!!!

Итак, суть БПФ, это разбиение входного вектора на ДПФ половинной длины, затем каждый получившийся вектор разбивается еще пополам и т.д. пока не останутся 2 точечные ДПФ. Очевидно что данный алгоритм применим только в том случае, если N является степенью двойки. Есть две разновидности этого алгоритма: с прореживанием по времени и с прореживанием по частоте. Оба этих алгоритма по вычислительной сложности одинаковы. Рассмотрим алгоритм БПФ с прореживанием по времени (берутся сначала четные элементы входного вектора, затем только нечетные, вычисляется их ДПФ и объединяются).

Представим исходное преобразование в виде суммы четных и нечетных элементов:

 

 

 

На всякий случай проверим... Пока все верно...

Слегка упростим и преобразуем выражение для большей осмысленности действий:

 

 

 

Здесь я воспользовался свойствами поворачивающих множителей

 

 

 

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

Следуем дальше принципу разделяй и властвуй. Снова делим каждое ДПФ на четные и нечетные элементы:

 

 

 

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

 

 

 

Статья находится в разработке

Случайные статьи....

Prev Next

GSM - сигнализация

18-03-2012 Владимир

GSM - сигнализация

  Добрый день!  Представляю вам свою разработку – GSM сигнализацию. Кому-то, наверное, интересно, что послужило мотивацией для создания этого проекта? Все просто, потребность друга в сигнализации для охраны своего офиса, которая будет дешевле других аналогичных устройств и весьма функциональна, а главное -...

Графический индикатор МЭЛТ 128х64. Вывод на индикацию 9 разрядов часто…

28-11-2012 Александр Милевский

Графический индикатор МЭЛТ 128х64. Вывод на индикацию 9 разрядов частотомера с гашением незначащих нулей.

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

Измеритель LC на PIC18F2550 с USB.

04-02-2012 Super User

Измеритель LC на PIC18F2550 с USB.

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

Пример аппаратной реализации шины I2C в режиме «мультимастер».

27-07-2011 Александр Милевский

Пример аппаратной реализации шины I2C в режиме «мультимастер».

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


Все права принадлежат ChipMK.ru. При копировании материала ссылка обязательна. 2011-2017 © ChipMK.ru

ChipMk.ru Яндекс.Метрика
PRCY.ru