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

Хорошее описание здесь
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


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

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

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

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

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

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

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

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

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

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

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

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

Делал. Писал сам все. Правда, перелопатив тучу чужих исходников. Лопатить начал от тяжелой жизни. Не знаю как в этих "аплеухах" но вот в инете лежит уйма голимых и нерабочих исходников 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: Вобщем читайте, спрашивайте...

Так. Дискретное Преобразование Фурье (ДПФ) чисто арифметически является к умножением вектора на матрицу. Но эта матрица имеет настолько специфический вид, что её можно представить как произведение нескольких сильно разреженных матриц. С формальной точки зрения это ничего не даёт, но с вычислительной - можно поднапрячься и исключить операции с нулевыми значениями в этих матрицах. Это, собственно, суть БПФ - количество операций оказывается существенно меньше, чем при "честном" матричном умножении. Ещё раз - тут используются особенности данной матрицы, в общем случае такой трюк невозможен.
Далее начинается реализация. Вместо записи выражения в матричной форме, которая подразумевает полное формальное умножение, рисуют граф - кто с кем складывается и с каким коэффицинтом. Если пойти по шагам, то получится что-то вроде 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-ми. И опять-таки без лишнего выпендрежа.

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

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