Преобразование Фурье для AVR

ARV пишет: будет ведь намного быстрее...

...объёмнее и сложнее. Как описывать в цикле перестановку и умножение бабочкой, я себе слабо представляю. Плюс сложение и умножение комплексных чисел...
Мне не горит — я могу и подождать пару секунд. Задача вычисления спектра в реальном времени не ставилась.

Я тут подумал - погонял МатЛаб и вспомнил/выяснил одну особенность...
Отсчёт спектра Nfft/2 лучше не брать в расчёт, т.к. его амплитуда крайне сильно зависит от фазы: от 0 до удвоенного максимального значения, т.к. именно на этом отсчёте спектр зеркалится.
С физической точки зрения это связано с тем, что отсчёты могут браться как от максимальных значений гармоники
[cos(n*pi) = +1, -1, +1, ...], так и от минимальных (нулевых):
[sin(n*pi) = 0, 0, 0, ...].
Кроме того, максимальное значение в каждом аккумуляторе будет не 126*Nfft, а в 2 или 4 раза меньше... надо подумать.

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

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

Та да. Для всех остальных гармоник. Я имею в виду, что сама дискретизация по времени может попасть как на нули, так и на максимумы входного сигнала! Таким образом, амплитуда частотного отсчёта Nfft/2 не несёт достоверной информации о его амплитуде, если заранее не известна его фаза.

У меня как раз задача: дискретное преобразование Фурье именно на AVR (128 точек). Мне кажется у нас очень - очень похожие задачи. Для ускорения старта (в порядке оказания технической помощи) хотелось бы ознакомиться с твоим исходником?

Вот. Только во-первых, это алгоритм с округлением, т.е. не очень точный и во-вторых, не всё закомменчено.

Спасибо. Начинаю разбираться.

lost-s0u1 пишет: Спасибо. Начинаю разбираться.

Угу. Спрашивайте если что.

Новогодние гуляния начались за неделю до Нового года…теперь можно, не отвлекаясь на “текучку “, заняться и Фурье.
Задача такая: анализ мгновенной частоты вращения ДВС в пределах одного оборота. Проблема в том, что количество входных отсчётов (мне привычнее точек) зависит от типа двигателя и никак не соответствует 2^n. Очевидно, что при любой экстраполяции данных, возникнут искажения спектра, то есть применение БПФ не совсем правильно.
На сайте “Простые устройства на AVR” увидел похожую проблему, решаемую Gudd-Head. Рассуждения показались очень схожими с моими. Стал решать аналогично, то есть классическое ДПФ, позволяющее получать спектр по-честному. Итак.
Дано: количество входных точек 70…120, количество выходных гармоник 6…12 (соответствует количеству цилиндров ДВС).
Требуется: произвести ДПФ для заданного количества точек и заданного количества гармоник.
Чтобы не сильно ужиматься, выбрал ATmega16M1 с тактовой частотой 16МГц, RAM=1 кбайт.
Программа прямого ДПФ написалась за 4 дня. Протестировано. Работает, как и ожидалось, сюрпризов не обнаружил пока.
Что получилось: для 128 точек и 64 гармоник
- необходимо 512 байт RAM.
- вычисление одной гармоники требует примерно 4400 циклов или 275 мкс.
Если количество точек и гармоник меньше, то требуется пропорционально меньший объём RAM и время выполнения.
Таким образом, моя задача решается примерно 3 мс. У меня на всё примерно 10мс.
Правда, теперь ещё предстоит обратное ДПФ. Хотел, что называется, сходу и сходу же проблема:
умножение двухбайтного числа на однобайтное и оба со знаком. Может кто что-нибудь встречал. Буду весьма признателен.
Алаверды Gudd-Head:

Замечания, пожелания, вопросы, а также обнаруженные “фичи, багги, глюки” принимаются к рассмотрению с благодарностью.

Всех посетителей сайта с Новым годом. Желаю успехов в создании любых устройств на AVR контроллерах.

lost-s0u1 пишет: умножение двухбайтного числа на однобайтное и оба со знаком.

Использовать процедуру умножения двухбайтных чисел, у одного из которых будет обнулён старший байт (или младший)... или так долго?
"Алаверды", я так понимаю, что-то вроде "спасибо"?

Gudd-Head пишет: Использовать процедуру умножения двухбайтных чисел, у одного из которых будет обнулён старший байт (или младший)... или так долго?

Долго, хотелось бы побыстрее.
Алаверды: ответное действие обычно в знак благодарности(wiki)

Получилось ещё и обратное преобразование Фурье.
Учитывая, что умножения со знаком пришлось делать "в лоб", то работает оно где-то в 3 раза медленнее, чем прямое. Для моей задачи хватает. Пока всё.

как-то все оторвано от жизни у вас. интересно было бы увидеть какой-то реально работающий проект с этим Фурьём

Задача, решённая и приведённая в #524, является конкретно инженерной задачей по диагностике ж/д многоцилиндровых ДВС в условиях обслуживания и ремонта в депо. Возможно, аббревиатура ДВС (двигатель внутреннего сгорания) требовала расшифровки.
Ещё раз спасибо Gudd-Head за первоначальную проработку, которая мне очень пригодилась.
А, вообще то, очевидно, что для микроконтроллера, оперирующего с двоичными цифрами, прямо таки просится не Фурье преобразование, а преобразование Уолша, в котором вместо sin/cos используются функции Уолша, принимающие всего лишь два значения +1 и -1. При этом операции умножения заменяются сложением/вычитанием, что упрощает преобразование и резко ускоряет процесс.
Вот только у меня, к сожалению, нет основательности Gudd-Head к первоначальной проработке, а конкретного примера мне не попалось. Встречались, в основном математические доказательства (я им верю категорически и сразу), но без инженерной конкретики.
Чуть более понятно

(это Томский Государственный университет). Может, когда и дойдут руки, тогда займусь.
Еще есть замечательная книжка: Залманзон Л.А. "Преобразования Фурье, Уолша, Хаара и их применение в управлении, связи и других областях" М.1989г. Но там слишком фундаментальные вещи. Не осилил.

я не сомневаюсь, что задачу вы решаете не пустяковую, высосанную из пальца. но мне, как человеку далекому от ДВС, было бы интереснее увидеть схемки-фотки-видео какого-то прибора, делающего что-то для вас полезное. меня это как-то больше впечатляет