FFT, Практическая реализация Опции

[lexl]

Кто-нибудь может указать перстом, где просто и доступно объясняется БПФ с примерами кода?

[Jools]

Хорошее описание здесь
h-t-t-p://w-w-w.autex.spb.ru/download/dsp/dsp_guide/ch06.pdf
и здесь
h-t-t-p://w-w-w.autex.spb.ru/download/dsp/dsp_guide/ch31.pdf


А код чей нужен? Вот под рукой Паскальный лежал! Лови.

Прикрепленные файлы

 lined_fft_sa_gen.htm ( 39.81 килобайт ) Кол-во скачиваний: 195

 

[bve]

В сети достаточно много материалов, посвященных вычислению БПФ.
Многие содержат исходники, например http://www.fftw.org. Здесь есть реализации
БПФ для Intel-совместимых процессоров с задействованием всей мощи
специализированных команд. Если Вам нужны исходники для сигнальных
процессоров, то прямой путь - на сайты производителей, поскольку у них
обычно приводятся эталонные программы. Хочу заметить, что выжать максимум
из железа Вы сможете только при использовании ассемблера, так что
программы на языках высокого уровня - чисто иллюстрация того или иниго алгоритма.

[_VM]

Приведу интересных сцылочек, а то многие не знают.
http://developer.intel.com/software/products/perflib/
http://developer.intel.com/software/products/ipp/
Раньше был бесплатный набор бибилиотек под названием Intel Processing Library, его в инете наверное до сих пор можно найти. FFT там быстро считалось.

[nikkov]

Есть еще "The FXT library" на http://www.jjj.de/fxt/.
Там есть и исходные коды и книжка на английском,
еще есть в сети книга что-то типа "Numerical Recipes C/C++".
У меня есть к ней исходники.

[wallk]

Если с примерами кода, то лучше всего брать описание стандартных библиотек, например можно тут http://www.nr.com/ порыться. Кстати, а чем стандартные библиотеки не устраивают?

[evgeniy_s]

Есть небольшой хороший пример на С:
http://www.codenet.ru/progr/alg/fft.php
А вообще неплохо было бы почитать чего-нибудь вроде следующей книги: Блейхут Р. Быстрые алгоритмы цифровой обработки сигналов. Пер. с англ. - М.: Мир. 1989. - 448с.

[gertoth]

Лучшая практика - хорошая теория:
Рабинер и Голд. Теория и практика цифровой обработки сигналов
http://dsp-book.narod.ru/RG.html

Примеры лучше изучать по AN, Application Notes; Texas Instrument, Analog Devices.

[AKazak]

Классная книга по цифровой обработке сигналов:

http://lord-n.narod.ru/download/books/wall...vis.B.part1.rar
http://lord-n.narod.ru/download/books/wall...vis.B.part2.rar

Там не только теория, но и практические примеры вычислений!

[Moks]

Извините, а полее подробно и понятно метод "бабочки" растолковать не может? Теория - это хорошо, но от неё мозги опухают. На Си кто-нибудь его делал сам, без использования чьих-то исходников, следуя только требованиям математики, переложенных на язык Си, например?
Помогите, пожалуйста. ссылки, указанные в теме, почитал, но ясности не так уж много стало ...

[DRUID3]

Извините, а полее подробно и понятно метод "бабочки" растолковать не может? Теория - это хорошо, но от неё мозги опухают. На Си кто-нибудь его делал сам, без использования чьих-то исходников, следуя только требованиям математики, переложенных на язык Си, например?
Помогите, пожалуйста. ссылки, указанные в теме, почитал, но ясности не так уж много стало ...

Делал. Писал сам все. Правда, перелопатив тучу чужих исходников. Лопатить начал от тяжелой жизни. Не знаю как в этих "аплеухах" но вот в инете лежит уйма голимых и нерабочих исходников FFT. Об упомянутой книге Айфичера и Джервиса у меня самое отвратное впечатление. Я ее купил бумажную аж за 120 гривен . Тоже думал, открою быстренько передеру исходник и забуду о ЦОС как о кошмарном сне. Очепяток и явных ошибок (многие алгоритмы 100% не проверялись и были содраны с паскалевских или фортрановских сорцоф ) там офигеть как много для книги за такую цену.
"Догнал" БПФ читая незамысловатую "Программирование звука для ПК" Тима Кинтцеля в купе с материалом с http://algolist.manual.ru/maths/fft.php . Последняя ссылка это о-о-о-о-очень хороший материал по оптимизации, правда при "рытье" "сырцов" с нее мне пришлось таки выучить C как следует , но что-то не все там у меня заработало . Сейчас медленно но уверенно пишу БПФ без сортировки с реверсом битов порядковых номеров, если повезет, попозже сяду за 2-D FFT. Вот еще один какой-то ресурс с БПФ, но я не проверял работоспособность исходника: http://alglib.sources.ru/fft/fft.php .
На ХвыТыПы лежит книга, что-то типо "Справочник по цифровой фильтрации" там тоже дан пример FFT на C.
begin off top
То, что хотите писАть сами - очень хорошо, чем лучше Вы понимаете то что запихиваете в контроллер тем, как ни странно , менее ресурсов Вам от контроллера требуется. У многих уже выработался какой-то странный стереотип, что DSP developer это обязательно MathLab, BlackFin и диплом кандидата по матстатистике прикрученный шурупами к стене . На самом деле все прозаичнее, и разобравшись, идеи DSP вполне можно использовать и на AVR. Правда часто возникает иная ситуация (у моих сверстников особенно) - после прочтения 2-х-3-х статей в инженерных журналах да после окончания какого-нибудь 3-х дневного семинара слаживается впечатление, что все, он уже ДыСыПы девелопер, там же ничо сложного. Вот проц, вот книжка с блок-схемами, вот "сорцы". Плаг-энд-плей кАроче . Остается найти богатого заказчика с жилкой фантазии на тему научно-технической революции и высоких технологий. И задача в 60-е годы спокойно решаемая малой кровью решается "на новом уровне" и по цене строительства жилищного кооператива. Зато заказчик (или конечный покупатель) получает душевную отраду отвинтив крышку прибора, вот они высокие технологии уже и у него
end off top
P.S.: Бабочка непонятна потому, что их уж очень много рисуют, а рисование довольно нехило отвлекает от математики . Вобщем и целом принцип БПФ (очень хорошо описанный в книженции поглавно хранящейся сдеся: http://vadis7.chat.ru/articl.htm) это сведение вычислений к 2-х точечному ДПФ и хитрый перебор коэффициентов для каждого следующего 2-х точечного преобразования с учетом симметричности и периодичности матрицы преобразования. Все это порождает целое семейство возможных алгоритмов (каких БПФ только нет, сводящиеся к 4-х точечному - уменьшает количество умножений - актуально для процов без перемножителей, без реверса битов - более быстрое но возвращает отдельный вектор преобразования, ну и известные с временной (советую с него и начать изучение http://algolist.manual.ru/maths/fft.php закачайте PDF там все предельно четко на 2-ой и 3-ей странице дано) и частотной децимацией и т.д.). Читать фолианты по-типу Блейхута не рекомендую, это как изучать программирование с Кнута. Если не сформирован круг практических задач - нечего изучать. Да и не больно доходчиво там все дано.

P.P.S: Вобщем читайте, спрашивайте...

[SasaTheProgramme...]

Извините, а полее подробно и понятно метод "бабочки" растолковать не может? Теория - это хорошо, но от неё мозги опухают. На Си кто-нибудь его делал сам, без использования чьих-то исходников, следуя только требованиям математики, переложенных на язык Си, например?
Помогите, пожалуйста. ссылки, указанные в теме, почитал, но ясности не так уж много стало ...

Так. Дискретное Преобразование Фурье (ДПФ) чисто арифметически является к умножением вектора на матрицу. Но эта матрица имеет настолько специфический вид, что её можно представить как произведение нескольких сильно разреженных матриц. С формальной точки зрения это ничего не даёт, но с вычислительной - можно поднапрячься и исключить операции с нулевыми значениями в этих матрицах. Это, собственно, суть БПФ - количество операций оказывается существенно меньше, чем при "честном" матричном умножении. Ещё раз - тут используются особенности данной матрицы, в общем случае такой трюк невозможен.
Далее начинается реализация. Вместо записи выражения в матричной форме, которая подразумевает полное формальное умножение, рисуют граф - кто с кем складывается и с каким коэффицинтом. Если пойти по шагам, то получится что-то вроде V*M1*M2*...Mn->V|G1|*M2*...Mn->...V|G1|G2|..|Gn|. На каждом шаге умножение на матрицу заменяют графом со стрелочками, показывающими какие конкретно элементы и как складываются. При этом оказывается, что элементы всех векторов-результатов - и промежуточных и окончательного - получаются суммой двух слагаемых, т.е. суммой двух значений из предыдущего вектора с коэффициентами. Более того, можно так переставить матрицы, что значения будут получаться "два из двух", т.е. два значения из предыдущего вектора определяют два значения последуюшего. Если выделить на графе этот момент, то четыре линии будут отдалённо напоминать бабочку (отсюда и название). Таким вот образом, ДПФ сводят к выполнению двух операций - бабочки и перестановки индексов, которая подставляет бабочке значения в нужном порядке.
P.S. Не поленись, проделай это на бумаге для матрицы преобразования 8*8 и всё сразу станет на свои места.

[DRUID3]

Извините, а полее подробно и понятно метод "бабочки" растолковать не может? Теория - это хорошо, но от неё мозги опухают. На Си кто-нибудь его делал сам, без использования чьих-то исходников, следуя только требованиям математики, переложенных на язык Си, например?
Помогите, пожалуйста. ссылки, указанные в теме, почитал, но ясности не так уж много стало ...

Так. Дискретное Преобразование Фурье (ДПФ) чисто арифметически является к умножением вектора на матрицу. Но эта матрица имеет настолько специфический вид, что её можно представить как произведение нескольких сильно разреженных матриц. С формальной точки зрения это ничего не даёт, но с вычислительной - можно поднапрячься и исключить операции с нулевыми значениями в этих матрицах. Это, собственно, суть БПФ - количество операций оказывается существенно меньше, чем при "честном" матричном умножении. Ещё раз - тут используются особенности данной матрицы, в общем случае такой трюк невозможен.
Далее начинается реализация. Вместо записи выражения в матричной форме, которая подразумевает полное формальное умножение, рисуют граф - кто с кем складывается и с каким коэффицинтом. Если пойти по шагам, то получится что-то вроде V*M1*M2*...Mn->V|G1|*M2*...Mn->...V|G1|G2|..|Gn|. На каждом шаге умножение на матрицу заменяют графом со стрелочками, показывающими какие конкретно элементы и как складываются. При этом оказывается, что элементы всех векторов-результатов - и промежуточных и окончательного - получаются суммой двух слагаемых, т.е. суммой двух значений из предыдущего вектора с коэффициентами. Более того, можно так переставить матрицы, что значения будут получаться "два из двух", т.е. два значения из предыдущего вектора определяют два значения последуюшего. Если выделить на графе этот момент, то четыре линии будут отдалённо напоминать бабочку (отсюда и название). Таким вот образом, ДПФ сводят к выполнению двух операций - бабочки и перестановки индексов, которая подставляет бабочке значения в нужном порядке.
P.S. Не поленись, проделай это на бумаге для матрицы преобразования 8*8 и всё сразу станет на свои места.

Позвольте все же заметить, что

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

Есть множество алгоритмов обходящихся без перестановки индексов. Вобщем и целом алгоритм БПФ сводится к 2-х (или 4-х) точечному ДПФ и алгоритму переразбиения массива входных данных на эти ДПФ.

[st256]

Извините, а полее подробно и понятно метод "бабочки" растолковать не может? Теория - это хорошо, но от неё мозги опухают. На Си кто-нибудь его делал сам, без использования чьих-то исходников, следуя только требованиям математики, переложенных на язык Си, например?
Помогите, пожалуйста. ссылки, указанные в теме, почитал, но ясности не так уж много стало ...

Так. Дискретное Преобразование Фурье (ДПФ) чисто арифметически является к умножением вектора на матрицу. Но эта матрица имеет настолько специфический вид, что её можно представить как произведение нескольких сильно разреженных матриц. С формальной точки зрения это ничего не даёт, но с вычислительной - можно поднапрячься и исключить операции с нулевыми значениями в этих матрицах. Это, собственно, суть БПФ - количество операций оказывается существенно меньше, чем при "честном" матричном умножении. Ещё раз - тут используются особенности данной матрицы, в общем случае такой трюк невозможен.
Далее начинается реализация. Вместо записи выражения в матричной форме, которая подразумевает полное формальное умножение, рисуют граф - кто с кем складывается и с каким коэффицинтом. Если пойти по шагам, то получится что-то вроде V*M1*M2*...Mn->V|G1|*M2*...Mn->...V|G1|G2|..|Gn|. На каждом шаге умножение на матрицу заменяют графом со стрелочками, показывающими какие конкретно элементы и как складываются. При этом оказывается, что элементы всех векторов-результатов - и промежуточных и окончательного - получаются суммой двух слагаемых, т.е. суммой двух значений из предыдущего вектора с коэффициентами. Более того, можно так переставить матрицы, что значения будут получаться "два из двух", т.е. два значения из предыдущего вектора определяют два значения последуюшего. Если выделить на графе этот момент, то четыре линии будут отдалённо напоминать бабочку (отсюда и название). Таким вот образом, ДПФ сводят к выполнению двух операций - бабочки и перестановки индексов, которая подставляет бабочке значения в нужном порядке.
P.S. Не поленись, проделай это на бумаге для матрицы преобразования 8*8 и всё сразу станет на свои места.

Позвольте все же заметить, что

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

Есть множество алгоритмов обходящихся без перестановки индексов. Вобщем и целом алгоритм БПФ сводится к 2-х (или 4-х) точечному ДПФ и алгоритму переразбиения массива входных данных на эти ДПФ.

Ну блиинннн.... Вектора... Матрицы (кои тоже суть вектора)... Премножения... Сразу видно, что собрались ведущии стратеги Европпы и Азии в DSP контенте.


Не нужно никаких матриц для понимания БПФ. Нужно правильно выполнять 4 арифметических действия над комплексной экспонентой. Кстати, БПФ я могу свести и к 5-ти точечному ДПФ. И к 7-ми. И опять-таки без лишнего выпендрежа.

[Moks]

А вот отсюда можно поподробней и внятней, а?
DRUID : некоторые ссылки не работают, к сожалению.
SasaTheProgrammer: не такого ответа я хотел бы. Ты непоянтное объяснил ещё более непотным языком, от этого не легче.
st256: А про сведение к малому не можешь подробнее объяснить или ссылки полезные дать?

Заранее спасибо. Кстати, а БПФ так же, как и ДПФ даёт спектральное представление в виде Cn коэффициентов? Извиняюсь за наивный вопрос ... Что именно считает БПФ?

[DRUID3]

А вот отсюда можно поподробней и внятней, а?
DRUID : некоторые ссылки не работают, к сожалению.

Когда я писАл пост http://vadis7.chat.ru/articl.htm еще работала, странно. Ну качаем тогда отсюда (книга в самом низу) http://www.analog.spb.ru/pub_dsp.htm

Кстати, а БПФ так же, как и ДПФ даёт спектральное представление в виде Cn коэффициентов? Извиняюсь за наивный вопрос ... Что именно считает БПФ?

БПФ это и есть ДПФ. Это не аппроксимация и не альтернативный базис!!! Так что дает оно абсолютно те же коэффициенты разложения в ряд Фурье. Либо спектр комплексных экспонент (наверно под ними имелись ввиду Cn) либо амплитуд синусов и косинусов (в соответствии с известной формулой Эйлера exp(j*w) = cos(w)+ j*sin(w) т.е. будут коэффициенты Sc(w) и Ss(w)). Можно так же получить и модуль спектральной плотности («энергетический спектр») sqrt(Sc(w)*Sc(w) + Ss(w)*Ss(w)) или спектр «фаз» atan(Ss(w)/ Sc(w))

[Alex B._]

2Moks
SasaTheProgrammer объяснил, по-моему лучше некуда. Готовых исходников пруд-пруди, если не хочется вникать - непонятно, зачем тогда вообще спрашиваете...
чтоб было понятней - БыстроеПреобразованиеФурье - это алгоритм вычисления ДПФ для буфера, размер которого кратен степени 2^n (не степени двойки, а именно степени двойки в степени n). Почему это позволяет в разы сократить количество умножений со сложением, написано по ссылкам, которые вам дали. Для буфера произвольного размера придется делать честное ДПФ

[st256]

А вот отсюда можно поподробней и внятней, а?

st256: А про сведение к малому не можешь подробнее объяснить или ссылки полезные дать?

Заранее спасибо. Кстати, а БПФ так же, как и ДПФ даёт спектральное представление в виде Cn коэффициентов? Извиняюсь за наивный вопрос ... Что именно считает БПФ?

Что такое ДПФ? Это, грубо говоря, спектр дискретезированного сигнала. Т.е. на входе ДПФ имеется, допустим, 1024 отсчета сигнала. Тогда на выходе ДПФ Вы получите 1024 отсчета спектра этого сигнала.

БПФ это алгоритм ускоренного вычисления ДПФ. Т.е. Вы получаете те же 1024 отсчета, но затратив гораздо меньше операций.

Про сведение к малому. Допустим, Вы хотите сделать БПФ на 16 точек и имеете для этого 16 отсчетов сигнала. Вы разбиваете 16 входных отсчетов сигнала на два массива по 8 точек и вычисляете два восьмиточечных ДПФ, а потом их объединяете особым образом в 16-ти точечное. Кстати, 8-ми точечное ДПФ опять можно раздить на два 4-х точечных и т.д.

Самое простое БПФ это 2-х точечное. Или его еще называют бабочка. Бабочки могут быть разные. Например такие:

Ya = Xa + W * Xb
Yb = Xa - W * Xb

где Xa и Xb - входные отсчеты
Ya и Yb - выходные отсчеты
W - особый комплексный коэффициент

Почитать об этом можно в любой книжке про ЦОС.

БыстроеПреобразованиеФурье - это алгоритм вычисления ДПФ для буфера, размер которого кратен степени 2^n (не степени двойки, а именно степени двойки в степени n).

Совсем необязательно.

[Moks]

st256: Спасибо за растолковывание одной из бабочек, я уже почитал про это.

Alex B._: в адвокаты заделался. "SasaTheProgrammer объяснил, по-моему лучше некуда. Готовых исходников пруд-пруди, если не хочется вникать - непонятно, зачем тогда вообще спрашиваете...
" Знаешь, что для некоторых является тривиальным, не значит, что для других тоже. А в исходниках разбираться - дело наблагодарное, надо самому математику уметь перевести на язык железа.

DRUID3: Спасибо, вчера почему-то ссылка не работала... Но сегодня всё окей, огромное спасибо. Кстати, при проверке и прогонке алгоритмов, как ты писал ранее, ты случайно не проверял работоспособность FFT, предложенного фирмой SiLabs и выложенной на сайте силабс.ру ? Если да, то что ты можешь о нём сказать (алгоритме, я имею в виду).
Всем спасибо за прошлые советы и, возможно, будущие.

[Alex B._]

>> Alex B._: в адвокаты заделался.
да не, просто высказал свое мнение

>> Знаешь, что для некоторых является тривиальным,
>> не значит, что для других тоже.
несомненно.

[SasaTheProgramme...]

SasaTheProgrammer: не такого ответа я хотел бы. Ты непоянтное объяснил ещё более непотным языком, от этого не легче.

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

Заранее спасибо. Кстати, а БПФ так же, как и ДПФ даёт спектральное представление в виде Cn коэффициентов? Извиняюсь за наивный вопрос ... Что именно считает БПФ?

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

Вот - "раскопал своих подвалов":

Р.Отнес
Л.Эноксон
"Прикладной анализ временных рядов"
Москва "Мир" 1982

Очень доходчиво, шаг за шагом. Но разбираться с математикой придётся всё равно.

Сообщение отредактировал SasaTheProgrammer - Oct 5 2006, 19:14

[Moks]

Кстати, а кто доходчиво может граф посторить для N=16 хотя бы. А то в примерах указан для N=8, никак не докумекаю, а мне нужно N=512. Никак в голове не раскладываются 9 ступеней, которые нужно пройти.
Зы: ну не люблю я готовые библиотеки, не люблю. Хочу сам докумекать!

[Moks]

Кстати, а кто доходчиво может граф посторить для N=16 хотя бы. А то в примерах указан для N=8, никак не докумекаю, а мне нужно N=512. Никак в голове не раскладываются 9 ступеней, которые нужно пройти.
Зы: ну не люблю я готовые библиотеки, не люблю. Хочу сам докумекать!

Люди, ау!
Вот пытаюсь "Добить" метод разреживания по частоте с бабочкой, но никак не могу граф поставить для N=512. Не получаются у меня заявленные (N/2)log2(512) = 2304 перемножения. Кто-нибудь, помогите графом для случая N>=16 отсчётов...

[shasik]

Люди, ау!
Вот пытаюсь "Добить" метод разреживания по частоте с бабочкой, но никак не могу граф поставить для N=512. Не получаются у меня заявленные (N/2)log2(512) = 2304 перемножения. Кто-нибудь, помогите графом для случая N>=16 отсчётов...

1. На счет бабочек...
На мой взгляд одно из лучший творений - А.М. Трахтман, В.М. Трахтман. Основы теории дискретных сигналов на конечных интервалах , там не только про БПФ. Если проблемы с бабочками для БПФ начни с чего-нибудь по проще, например: преобразование Адамара. Все очень понятно, никакой комплексной арифметики, експонент и др., только нолики и единички (точнее +/-1). Если понял алгоритм быстрого преобразования Адамара, то перейти к БПФ формально очень даже просто - добавь умножения на exp(...) и все...
Еще раз - очень рекомендую эту книгу, это фундаментальная (!) вестчь (кстати, эта книга - мой скан).

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

3. На счет копания в громадной кучи исходников по БПФ
Я в свое время решал этот вопрос следующим образом. Сначала я смотрел как реализована двоично-инверсная перестановка отсчетов сигнала. Если какие-нибудь операции с битами и прощая хр..нь, то дальше читать не стоит. Программа будет явно низкого качества, даже если в ее основу положены очень хорошие идеи. Про наличие операций с битами - это касается только писюков. В DSP процессорах - двоичная инверсия выполняется на аппаратном уровне. Здесь также рекомендую www.jjj.de. Это ссылка уже всплывала, но тем не менее... Там рассмотрено очень много подводных камней, которых возникает огромное множество при практической реализации того-или иного алгоритма и о которых в большинстве научно-теоретических книгах просто не говорят.

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