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

БПФ это и есть ДПФ. Это не аппроксимация и не альтернативный базис!!! Так что дает оно абсолютно те же коэффициенты разложения в ряд Фурье. Либо спектр комплексных экспонент (наверно под ними имелись ввиду 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))

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

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

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

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

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

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

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

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




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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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