Помогите с БПФ - быстрое преобразование Фурье

[poff]

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

Ближе к сути:

1. Система построена на базе ATMEGA8.
2. Результатом работы подпрограммы БПФ вижу четкое разделение входного звукового сигнала на три полосы 100-1000гц, 1200-3000гц, 3200-5000гц
(соответственно результаты будут использоваться другими подпрограммами для реализации различных эфектов).
3. Хочется использовать один вход АЦП.
4. Для написания программы использую асемблер.

Литература по данной теме не предлагает перехода в практическую плоскость.
Единственная книга, которая помогла - Юкио Сато "Обработка сигналов".

Господа! если кто решал аналогичные задачи, поделитесь опытом.
Предлагаю расписать алгоритм по шагам.

Шаг 1. Измеряем с определенной частотой, 10Кгц например, уровень входного сигнала.
Шаг 2. ?
Шаг 3. ?
ИТД

Заранее благодарен.

[Anode_Katode]

М-да... Задача оригинальная. Прямые преобразования Эйлера-Фурье не прокатят. Около года назад я тоже озадачился нечто подобным, жаль только не надолго меня хватило(((
Смыл в использовании численных методов для разложения в ряд гармонических составляющих, в частности схемы Рунге (по крайней мере я пытался его осмыслить). Вот ссылка на теорию http://www.ipages.ru/index.php?ref_item ... 3&ref_dl=1

[Meteor]

1)Частоту дискретизации лучше взять повыше раз в 5 (20...30 кГц).
2) Поищите информацию о проектировании цифроых фильтров ибо для меги БПФ и тем более ДПФ будет непосильной задачей.
3) Весь проект потребует значительной памяти - как минимум на 3 выборки, а лучше еще иметь запас.

[pyzhman]

А вот попробуйте это:

[ChipKiller]

Литература по данной теме не предлагает перехода в практическую плоскость.
Единственная книга, которая помогла - Юкио Сато "Обработка сигналов".

... а может не там искали ? http://www.atmel.com/dyn/general/tech_doc.asp?doc_id=8778&family_id=607

[Rinon Ninqueon]

у мну тут есть исходник анализатора спектра на Си
DFT прокоментирована хорошо

как лапы дойдут, выложу

[ARV]

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

[phanis]

Вот кое что, довольно шустрая библиотека
http://vrtp.ru/index.php?showtopic=12319&st=0
http://elm-chan.org/works/akilcd/report_e.html
http://www.remexpert.com/ipb/topic3779s0.html?p=15994&#entry15994

[George22]

http://elm-chan.org/works/akilcd/report_e.html

Chan в 2005-ом это сделал именно на Mega8.
Кто-нибудь разбирался в какой среде разработки это сделано:
там и С-файлы и ассемблерные S-файлы?

[poff]

to phanis. Спасибо, похоже, это то что нужно. Буду разбираться, но если у кого-то есть мысли по поводу - милости просим..

[Сэр Мурр]

Делайте компаратор длительности импульса. Задайте столько окон анализа, сколько хотите иметь полос выделения (анализа) сигнала. Для этого компаратора не важен уровень сигнала- главное- его должно хватать для срабатывания. Алгоритм- очень простой, и не будет нагружать контроллер.
На АЦП можно реализовать индикацию уровня сигнала.
Конечно, это не так точно, как БПФ, но для простых случаев достаточно. Запросто можно реализовать многополосный анализатор спектра.

[Rinon Ninqueon]

вотъ
там spectr.c главное
смотри последовательность в "main" (закоментированно)
массив должен быть Data, а не Data_h и Data_l
и ещё, должно быть: Data[K-1] = Data[K-1] * Okno[K-1];

[poff]

to Сэр Мурр. Изначально я так и хотел сделать, но ненашел поддержки среди коллег - забраковали мою идею. В любом случае стоит разобраться с БПФ, в лучшем случае получится хорошая программа , в худшем - расширится кругозор. Спвсибо за поддержку.

[driver_gv]

Делал такую цветомузыку на PIC , FFT , 6 полос, 6 каналов шим 6 бит. Писал на асме, только целочисленная математика 16/32 бит со знаком.
Все получается и работает в реалтайме. Памяти надо много.

Сначала оцифровать не хуже 128 отсчетов на 4 периода , множим на синус и косинус, отдельно складываем , делим на количество отсчетов и корень квадратный из квадратов синуса и косинуса.
Я еще накладывал функцию Хемминга для подавления боковых лепесков и расширения центрального.
Например фильтр на 4000Гц светится от 3 до 5,5 кГц с переменной яркостью в зависимости от отстройки от центральной частоты.

Сначала рекомендую потренироваться в екселе.

[poff]

to driver_gv. Сейчас пытаюсь анализировать код анализатора от Chanа (см. ссылки выше). Альтернативные решения не помешают. Если это возможно, не могли бы Вы перекинуть мне исходники в асме для Пика.
Заранее благодарен..

[driver_gv]

По некорым причинам не могу публиковать исходник этого проекта.
Советутю прочесть http://91.210.216.1/Books/Микроконтроллеры/Цифровая%20обработка%20сигнала/Уолт%20Кестер/
и можно поискать его книги.
Примерный алгоритм расчета я описал, будет не понятно - спрашивайте.
Оцифровывать для цветомузыки надо 40 -60 кГц для диапазона фильтров до 10 -15 кГц

[Paguo-86PK]

Странно, в журнале РАДИО за 80-ые в разделе цифровой техники я читал, что наша промышленность до сих пор штампует телевизоры на лампах, тогда как западные модели телевизоров начала 80-ых имели цифровой звуковой тракт с АЦП и на процессоре с тактовой частотой порядка 20МГц для регулировки тембра по представленным формулам
Неужели современные чипы так слабы в Фурье и годятся лишь для тембровки, как 30 лет назад!?

[pyzhman]

У каждого чип специализированная задача. Пики и атмелы, о которых здесь идет речь, не DSP, обрабатываают чисто цифру. Да, есть АЦП. Но не шустрый. А в тв применены соответственно свои м/с. Под свои задачи разработанные. Никто микроскопом гвозди не забивает.