дискретное преобразование фурье на AVR\Pic24F

[стьюдент]

Привет всем радио котам. Возникла проблема: реально ли реализовать ДПФ(дискретное преобразование фурье) на микроконтроллере AVR(например ATmega32). В связи с тем, что в цифровой обработке сигналов я новичек, вынужден попросить вашей помощи. Не могу разобраться в алгоритме ДПФ\БПФ. Есть ли примеры кода на ассемблере\или готовые алгоритмы? Понимаю что в реальном времени сигнал обработать я не успею, на данном этапе мне важно именно понимание алгоритма и математики , которая используется для преобразования фурье. В дальнейшем, после полного понимания алгоритма, буду переделывать проект на Pic24F. У кого есть какие соображения???

[Ser60]

Посмотрите здесь
http://www.microchip.com/stellent/idcpl ... e=en023598
и здесь.
ftp://ftp.efo.ru/pub/efo-ftp/TMP/pub/at ... s-on+1.pdf
И еще в Гугле.

[Shapa]

Да, реально. Лично я реализовал на Кортексе М3. Но потом перешел к алгоритму Герциля, т.к он даёт результат только для нескольких спектральных отсчётов, соответственно он не так ресурсоёмок.

....мне важно именно понимание алгоритма и математики....

А что вы знаете о Рядах Фурье? Каким физическим смыслом наделено разложение в ряд Фурье?

[ibiza11]

+1 Shapa!
Нужно матчасть читать прежде чем что-то пытаться понять в программе. Это вам не светодиодики зажигать.

[Gudd-Head]

Замутил нечто похожее:
http://www.simple-devices.ru/forum/Прог ... ье-для-AVR
Там же и чуток теории написал.

[стьюдент]

А что вы знаете о Рядах Фурье? Каким физическим смыслом наделено разложение в ряд Фурье?

"В обработке сигналов и связанных областях преобразование Фурье обычно рассматривается как декомпозиция сигнала на частоты и амплитуды, то есть обратимый переход от временно́го пространства (time domain) в частотное пространство (frequency domain)."

Это всего лишь сухая теория, какую пользу она несет?! Если у меня на форуме ник стьюдент, то это не значит, что я типичный студент который ищет халявы и не в состоянии предварительно поискать информацию сам

Gudd-Head, нашел вашу статью еще вчера. Насколько я понял у вас не дискретное преобразование фурье? Особо интересует, как с помощью ДПФ выполнять фильтрацию (разделение по частотам) спектра сигнала (сигнал кстати записан в формате .wav).

Ser60, спасибо за ссылки, но к сожалению с английским очень туго, к тому же первоначально буду реализовывать на AVR, а ссылки ведут на dsp Pic и AVR32

[Gudd-Head]

Gudd-Head, нашел вашу статью еще вчера.

Чертовски приятно.

Насколько я понял у вас не дискретное преобразование фурье?

Дискретное. Но не быстрое.
Суть БПФ в упрощении за счёт количества выборок 2^N. Тогда применяют двоичную перестановку и алгоритм "бабочка". Надеюсь, вы про это уже прочитали. Просто я не силён в СИ, а на АСМе с комплексными числами мне не очень хотелось заморачиваться.

Особо интересует, как с помощью ДПФ выполнять фильтрацию (разделение по частотам) спектра сигнала (сигнал кстати записан в формате .wav).

Вообще говоря, фильтрацию проще выполнять с помощью фильтров. Из результатов ПФ вы замучаетесь восстанавливать сигнал. А вот посмотреть спектр сигнала — запросто.

[Alexeyslav]

Собственно алгоритм БПФ хорошо расписан в виде формул на википедии, сложность в реализации на микроконтроллере заключается лишь в комплексной функции exp(x), которую как правило задают заранее просчитанным массивом. А так используется обычный цикл для обсчета интеграла численными методами, а для ускорения обсчета используются исключительно целые числа. Ну, это до тех пор пока объемы RAM в контроллере считаются килобайтами и отсутствует математический сопроцессор.

У самого стала такая проблема для отображения спектра сигнала в усилителе в поле 32 столбца на 16 уровней. Ведь в таком случае использование даже 16-битных вычислений кажется каким-то кощунством и переводняком ресурсов.

[стьюдент]

Дискретное. Но не быстрое.
Суть БПФ в упрощении за счёт количества выборок 2^N. Тогда применяют двоичную перестановку и алгоритм "бабочка". Надеюсь, вы про это уже прочитали. Просто я не силён в СИ, а на АСМе с комплексными числами мне не очень хотелось заморачиваться.
Вообще говоря, фильтрацию проще выполнять с помощью фильтров. Из результатов ПФ вы замучаетесь восстанавливать сигнал. А вот посмотреть спектр сигнала — запросто.

1) зачем восстанавливать сигнал?
2) меня интересует только спектр сигнала, т.е. мне нужна вещественная часть, а внимую можно отбросить???
3) аналоговые фильтры не подойдут. "Нет научной навизны..."
4) можно полные исходники вашей программы?

[стьюдент]

Собственно алгоритм БПФ хорошо расписан в виде формул на википедии, сложность в реализации на микроконтроллере заключается лишь в комплексной функции exp(x), которую как правило задают заранее просчитанным массивом.
.
.
.
У самого стала такая проблема для отображения спектра сигнала в усилителе в поле 32 столбца на 16 уровней. Ведь в таком случае использование даже 16-битных вычислений кажется каким-то кощунством и переводняком ресурсов.

Я не уверен, что можно алгоритм БПФ (перестановки "бабочка") реализовать на 8-ми битном AVR. Дискретное преобразование вроде бы проще, особенно для малого числа точек(кстати изходя из чего выбирается их число?).

[ibiza11]

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

[Shapa]

Это всего лишь сухая теория, какую пользу она несет?! Если у меня на форуме ник стьюдент, то это не значит, что я типичный студент который ищет халявы и не в состоянии предварительно поискать информацию сам

Я не правильно выразился. Правлиьно вопрос должен звучать "Что вы понимаете?". Именно это меня интересовало.

2) меня интересует только спектр сигнала, т.е. мне нужна вещественная часть, а внимую можно отбросить???

Разложение в ряд Фурье есть разложение гармонического сигнла по его гармоникам. Т.е. в "идиотски упрощённом" виде это Fs = x1*F1 + x2*F2 + ... + xn*Fn, где n - номер спектрального отсчета, F(n) - частота спектрального отсчета, а Хn - амплитуда. Разложение в Ряд Фурье производится в комплексном пространстве и один из простых переводов из комплексного пространства в пространство вещественных чисел это вычсление длинны вектора ( Sqrt ( Re^2 + Im^2) )

ibiza11, хорошая статья, сам её когда-то был рад просмотреть

[Gudd-Head]

1) зачем восстанавливать сигнал?

Ну это же ваши слова:

как с помощью ДПФ выполнять фильтрацию

А в моём понимании фильтр вносит линейные искажения в сигнал. После ДПФ сигнал оказывается в частотной области, так что его (после обработки) нужно будет вернуть во временную. Вот зачем.

2) меня интересует только спектр сигнала, т.е. мне нужна вещественная часть, а внимую можно отбросить???

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

3) аналоговые фильтры не подойдут. "Нет научной навизны..."

Кто говорил про аналоговые фильтры? Я имел в виду цифровые. Но вам, видимо, нужна не фильтрация, а сам спектр.

4) можно полные исходники вашей программы?

Всё что есть я выложил на том форуме. Вроде бы.

Я не уверен, что можно алгоритм БПФ (перестановки "бабочка") реализовать на 8-ми битном AVR.

Почему же нельзя? Всё возможно. Весь вопрос в производительности.

Дискретное преобразование вроде бы проще, особенно для малого числа точек(кстати изходя из чего выбирается их число?).

Бабочка и есть БДПФ, просто это один из... способов, что ли. Число точек 2^N и зависит от точности которую вы хотите получить в частотной области.

[стьюдент]

Gudd-Head, посмотрел ваши наработки, я так понял вы не пробовали запускать АЦП ? Ограничились анализом только готовых данных? Или я смотрю устаревшую часть программы? Сохранился ли алгоритм (в визио,..) или все делалось без предварительного алгоритма?(

[Gudd-Head]

Не, проект был чисто теоретический — готовые данные в ОЗУ (?), никакого предварительного алгоритма в сторонней программе.

[стьюдент]

Кто может объяснить в чём ошибка (использую комплексное ДПФ) ? Или использовать формулы ДПФ для действительных сигналов?

[Alexeyslav]

Амплитуды - действительная часть результата, мнимая часть - это фаза соответствующей составляющей сигнала. Тебе надо вывести на экран только действительную часть.

[Meteor]

Надо период (от 0 до 2ПИ) разделить на 8 интервалов, а не на шесть. Получается что седьмая складывается с первой гармоникой и первая гармоника складывается с седьмой.

[Gudd-Head]

Амплитуды - действительная часть результата, мнимая часть - это фаза соответствующей составляющей сигнала.

Амплитуда — это длина комплексного вектора, фаза — угол между вещественной и мнимой частью.

[стьюдент]

Надо период (от 0 до 2ПИ) разделить на 8 интервалов, а не на шесть. Получается что седьмая складывается с первой гармоникой и первая гармоника складывается с седьмой.

Не понял как это реализовать. Увеличить число точек?