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

[lexl]

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

[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: Вобщем читайте, спрашивайте...