Цитата(Moks @ Oct 11 2006, 21:56)
Люди, ау!
Вот пытаюсь "Добить" метод разреживания по частоте с бабочкой, но никак не могу граф поставить для N=512. Не получаются у меня заявленные (N/2)log2(512) = 2304 перемножения. Кто-нибудь, помогите графом для случая N>=16 отсчётов...
1. На счет бабочек...
На мой взгляд одно из лучший творений -
А.М. Трахтман, В.М. Трахтман. Основы теории дискретных сигналов на конечных интервалах , там не только про БПФ. Если проблемы с бабочками для БПФ начни с чего-нибудь по проще, например: преобразование Адамара. Все очень понятно, никакой комплексной арифметики, експонент и др., только нолики и единички (точнее +/-1). Если понял алгоритм быстрого преобразования Адамара, то перейти к БПФ формально очень даже просто - добавь умножения на exp(...) и все...
Еще раз - очень рекомендую эту книгу, это фундаментальная (!) вестчь (кстати, эта книга - мой скан).
2. И вот когда с БПФ все уже ясно...
Поняв, что такое ДПФ, для чего оно нужно, как использовать БПФ, рекомендую разобраться с вычислением ДПФ с помощью быстрого преобразованием Хартли. Оно не на много сложнее БПФ, но для действительных сигналов выйгрыш в быстродействии очень даже ощутим (одно отсутствие необходимости работы с комплексными числами чего стоит). Есть конечно более быстрые алгоритмы, но по соотношению практическая(!) эффективноть на практическую (!) сложность реализации, на мой взгляд, - БПХ одно из лучших.
3. На счет копания в громадной кучи исходников по БПФ
Я в свое время решал этот вопрос следующим образом. Сначала я смотрел как реализована двоично-инверсная перестановка отсчетов сигнала. Если какие-нибудь операции с битами и прощая хр..нь, то дальше читать не стоит. Программа будет явно низкого качества, даже если в ее основу положены очень хорошие идеи. Про наличие операций с битами - это касается только писюков. В DSP процессорах - двоичная инверсия выполняется на аппаратном уровне. Здесь также рекомендую www.jjj.de. Это ссылка уже всплывала, но тем не менее... Там рассмотрено очень много подводных камней, которых возникает огромное множество при практической реализации того-или иного алгоритма и о которых в большинстве научно-теоретических книгах просто не говорят.
4. Определитесь чего Вы сами хотите...
а) чтобы Вам в двух-трех предложениях на простом русском языке объяснили ДПФ и все что с этим связано, чтобы можно было бы считать себя DSP-программером, - не получится.
б) Вам просто нужна готовая и понятная(!) реализация БПФ для сдачи курсового проекта - типа все работает, типа все делал сам и даже могу объяснить каждую строку кода - получится, в net'е полно "нормальных" исходников
в) чисто спортивный интерес: вот хочется разобраться и все тут - получится, но не сразу. Нельзя изучать мат. анализ, не зная арифметики, т.е. читаем теорию по ДПФ, разбираемся (сами разбираемся), сами все понимаем, затем переходим к пониманию БПФ, бабочек и т.д. О сколько нам открытий чудных готовит просвещенья век...
д) другое...
FFT, Практическая реализация
Mar 22 2005, 15:48
