Привет, all.
Не знаю куда писать, но думаю - сюда. Задача - даже не знаю с какой стороны к ней подойти.

Существует большое количество устройств, на базе ATmega32. Недавно, после совещания, шеф потребовал "добавить" спектральный агнализ принимаемого сигнала (не реал-тайм). Вроде бы для этого есть всё нужное оборудование. Если этого сделать нельзя, то надо обосновать почему. Я даже не представляю как подойти к этому вопросу.

Буду балгодарен за любую помощь в этом вопросе.

P.S.
Фурье в ATmega32... Кажется абсурдом.

Зачем же сразу "абсурдом"? Если время неограничено, то можно хоть на калькуляторе считать.
Главный вопрос - влезут ли анализируемые данные в ОЗУ. Укажите фурье на сколько точек нужно, и сколько ОЗУ под расчеты выделить сможете. Ну и разрядность входных/выходных данных тоже. Тогда можно будет что-то сказать.

Интересная задачка.

Давайте скажем честно: Считать на калькуляторе можно.
Но вот результаты этого вряд ли кому-либо будут нужны.
Поэтому без модификации преобразования вам не обойтись.
Посмотрите в эту сторону. Наверняка найдете что-либо
подходящее.

Сам же вам подскажу вот какой вариант:

Что произойдет если вы перемножите сигнал, на
шаблон (синусоиду в вашем случае)? Ответ простой -
если в сигнале есть этот шаблон, то вы получите "единицу".
Ну, а если ее нет, то получите нолик.

Теперь вам остается выяснить только сдвиг фаз и амплитуду.
Ну, если с амплитудой все понятно, то сдвиг фаз придется
попросту подбирать.

Теперь задача сводится к тому, что вам надо сохранить
нужное количество шаблонов синусоид и тупо перемножать
полученные отсчеты на шаблон. После подбора сдвига фаз
у вас в руках будет полная информация типа:

Шаблон №01 (50 Гц): Сдвиг 5 градусов, Амплитуда 0x50
Шаблон №02 (60 Гц): Сдвиг 15 градусов, Амплитуда 0x80
...
Шаблон №?? (?? Гц): Сдвиг 40 градусов, Амплитуда 0xF0

Чем вам не спектральная характеристика?

В общем-то, этот прием является одной из модификаций
преобразования Фурье над дискретным рядом.
Что, собственно, вам и надо.

Дополнительно могу подсказать вот что:
Чем отличается один шаблон от другого?
Да собственно ничем... Частотой только
(это только в вашем случае). Это значит,
что можно хранить один шаблон, правда,
высокой точности. Надо будет всего лишь
"выбирать" из него с нужным шагом, а не
последовательно. И, хотя это излишество,
но оно вам позволит сильно сэкономить в
памяти.

Думаю, вам достаточно вводных данных для
начала. Методу надо минимальное количество
ОЗУ, а так же вычисления только с фиксированной
точкой. Atmega справится - точно.

Сергей.

Может быть пригодится - http://elm-chan.org/works/akilcd/report_e.html

При использовании ядра AVR максимум, по моим оценкам, что можно сделать это реализовать два десятка цифровых фильтров второго порядка при выборке 8кГц и сигнале 10-14 бит. При условии что фильтра будут с фиксированными коэффициентами построенными по двоичному ряду и выполнены на сдвигах и сложениях. То есть жёстко заданными коэффициентами. При условии, что больше проц ни чем не занят.

Собственно под задачи ЦОС и создавались DSP процы. Так что не удивительно, что на дешёвом RISK ядре это сделать не удаётся.

Есть 2 варианта. 1 - уменьшать частоту выборки до безобразно низких величин. 2 - сбрасывать кусок выборки, а потом медленно его обрабатывать.

И в 1 и во 2 случае качество оценки сигнала серьёзно страдает по понятным причинам.

по моему надо сначало в MATLAB е попробовать а потом на микроконтроллер

У человека, похоже, особый случай.
Ему обработка в реальном масштабе времени просто не нужна.

Поэтому есть возможность записать данные за отрезок времени
(не знаю сколько секунда - две - три или всего несколько отсчетов)
и потом реализовывать анализ сохраненных данных.

В этом случае применение фильтров попросту не оправдано.
Можно обойтись более дешевыми и медленными методами.

Но самое важное при этом - найти способ увести все вычисления
в область челочисленной математики. Иначе действительно
ядра AVR попросту не хватит.

Сергей.

Мои советы:
1) Если есть возможность, не заморачиваться с float-арифметикой. Особенно, если исходные данные у вас целые (например, измерения АЦП), вам нужна лишь оценка частотного спектра и вы не собираетесь делать ему обратное FFT-преобразование.
В этом случае лучше всего создать ЦЕЛОЧИСЛЕННУЮ таблицу синусов, содержащую столько же ячеек, сколько и в буфере данных, которые будут подвергнуты преобразованию (то и другое - массивы, кратные целой степени двойки: 64, 128, 256, 1024, 2048 и т.д.). Однйо этой таблицы достаточно, чтобы все значения синусов и синусов, необходмые для вычислений, можно было выбрать из нее.
Для большинства целей бывает достаточно массива синусов с ячейкой типа char (1 байт). При этом синус нормируется на величину +-128 (signed char). Поскольку максимальные пределы синуса лежат в интервале от -1 до +1, то достаточно значение синуса для угла i*360/n градусов (где i-номер элемента массива) умножить на 128, а затем округлить до БЛИЖАЙШЕГО целого. Эту таблицу прошить во flash, чтобы не тратить под нее оперативку.
Есть вариаты нормировать на 2^15 = 32768, т.е. на MAX_INT, используя массив типа int. Тут точность получится совсем хорошая, но дольше станет умножение. Однако даже этот вариант летает со свистом по сравнению с умножением во float-числах.
Теоретически таблицу можно сделать в четверо короче, используя симметрию функции синуса, но тогда станет несколько сложнее алгоритм выборки.
2) Заранее решить, нужна ли вам реальная (косинусная) и мнимая (синусная) части разложения, или вам, как большинству электронщиков, нужно только значение мощности (корень из суммы квадратов дествительной и мнимой амплитуд). Если это так, то существует алгоритм FFT-преобразования, который сразу дает мощность. В противном случае вам придется n-раз исчислять корень квадратный, что неприятно.

Опустив момент, что такое преобразование не может называться преобразованием Фурье , все же скажу - исходники в студию. А то мы тут в одной теме не так давно корячились, а никто такой сильный алгоритм не подсказал

внесу свой голос в общий гомон
в AVR даже достаточно "больших" моделей всего 4К ОЗУ, это ну при самых суперизворотах (ассемблер) максимум 2048 отсчетов АЦП (при этом на остальную программу ОЗу уже не остается). Не стоит забывать и об этом ограничении...
и еще несколько слов о библиотеках Элм-Чена, которые рекомендуют при всяком удобном случае. Я их детально изучал и информирую: процедуры "быстрого" умножения и извлечения корня, написанные им для целочисленной арифметики, на самом деле быстрые, но дают ДИЧАЙШУЮ погрешность! например, 2*2=4, но 2*3=7 и т.д. Погрешность может достигать 30%! Для большого круга "оценочных" задач библиотеки подходят, но говорить о каких-то "измеренческих" задачах, наверное, не стоит...

Из практики. На ATMega8 делал расходомер, на входе частота. В диапазоне 4..100 Гц частоту определял по спектру, погрешность 0.2 Гц, время преобразования 3 сек. Потом ушли на ARM.

Да - реал-тайм действительно не нужен. Надо производить спектральный анализ в диапазоне 0.8...1.8 КГц. Я тут несколько раз прочитал предложенный тобой вариант. И не догоняю каким образом можно определить амплитуду. Либо я чего-либо не догоняю, либо метод просто не работает.

Полос сколько? А то мы тут недавно изготавливали нечто похожее. С частотой дискретизации 3.2кГц, 32 семпла, т.е. 16 полос с шагом 100Гц от 0 до 1.6кГц. Там реалтайм влегкую. http://electronix.ru/forum/index.php?s=&am...st&p=491456

То что он предлагает есть каноническое Дискретное Преобразование Фурье, при чем там "модификация преобразования" - непонятно. Только умножать надо и на синусы и на косинусы. Умножение на косинус даст вам вещественную составляющую коэффициента фурье, а на синус - мнимую. Амплитуда получается вычислением квадратного корня из суммы квадратов вещественной и мнимой частей, фаза - через арктангенс. ДПФ может иметь преимущество над БПФ только в случае большого количества точек при котором вас интересует какой то узкий диапазон частот, тогда можно умножить только на синусы и косинусы только интересующих вас частот, БПФ же ВСЕГДА считает все частоты, но зато он и быстрее в вычислении.

100% так и есть.
Модификация не в преобразовании, а в исполнении.
Суть в том, что таблицу для умножений можно держать
одну, а не две и не 22. Даже в том случае, когда надо
вычислять не одну частоту, а несколько. Лишь бы не
спектр.


За один раз действительно вычисляется только узкий диапазон
частот, а не весь спектр. Если интересует еще одна частота, то
надо проводить вычисления второй раз и третий и т.д.
Но, если надо вычислять 20 и более частот, то стоит подумать
над другими методами.

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

Да и вопрос-то был, насколько я понимаю, не в том что надо
делать, а "как".

А вообще хочется автору (GDI) поставить плюсик. Жаль тут это
не предусмотрено.


Сергей.

Пробовал таким способом реализовывать DTMF декодирование. Время распознавания - в десятки раз. Выделение на фоне шума в разы хуже.

Не забудьте и окно в flash-memory в таблицу записать, чтобы потом на него умножать.

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


А за это спасибо.
Очень приятно, Дмитрий.

Что-то не так, потому что когда  я делал подобные вещи - у меня и в 1-битном варианте(а-ля АОН), и в 8-битном никаких замечаний. И это все-же назывался корреляционный прием. Единственная сложность была - при отсутствии сигнала в канале все равно ведь на выходных суммах были свои максимумы - втупую не получалось, надо было отслеживать изменения накопленных сумм и вводить некие пороги срабатывания - задача не из приятных, потому что на большее не хватало времени. Время накопления + небольшой кусок пост-обработки составляло 10мС
ЗЫ для 256 входных отсчетов, ессно.

Рассказываю.
Испытали метод ssvSerge. Вначале в Excel, а потом в микроконтроллере. Проверяли наличие/отсутствие помехи на 1КГц. Определение 100% и при крутых шумах. Метод принят на вооружение. Вот только одно "но" таблица выборки растет не по дням, а по часам. Я добавил три частоты для анализа и таблица выросла почти втрое. Эдак никакой памяти не хватит.

P.S. Поправил. Решил уточнить.
Таблицу сделали 16 бит (после ADC 10 бит) и отсчеты делали в течении одной секунды.

Попробуйте "саморазворачивающийся синус" основанный на решении разностного уравнения Y[n]= B*Y[n-1] - Y[n-2]


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

Хм. Все зависит от частот сигнала, разрешения спекроанализатора и прочего.
Может кому-то это на АтМега32 и кажется абсурдом, но 20 с лишним лет назад 8-битный Z80, который никак не РИСК, и без аппаратного умножения, и с тактовой 3.5мгц - легко выполнял задачу спектроанализатора музыкального сигнала на компутере Sinclair ZX Spectrum
Причем не только "спектроанализировал" в реалтайме, но еще и на экране рисовал "столбики".

Ну да, при однобитном входном сигнале с компаратора Но результат-то был...
Так что - все зависит от того, а что собственно получить надо?

Иначе и быть не может. Математика - штука сильная.



Вы меня, конечно, простите, но либо я вас не понял, либо вы с
трудом представляете что делаете.

У вас таблица 16 бит, значит, вы использовали 32-х битное
умножение. Иначе вам проще урезать ваши 10 бит АЦП до 8-ми.

И потом вы целую серию выборок умножали? Вы уверены, что у
вас не хватает ресурсов на классическое БПФ?

Ну, а если же вы просто проверяли работоспособность метода,
то этот тест не имеет никакого смысла. Метод - работает.
Вопрос только в целесообразности его применения.


Пробуйте выбирать не точные значения, а ближайшие.
Если ошибка будет в допустимых для вас пределах, то
так и оставляйте. Если же нет, то добавляйте новоую позицию
в таблицу.

Это приведет к девиации опорных значений. Результат -
расползание спектра. Т.е. пик вы получите значительно
меньше, чем в правильном случае. Это я к тому, что оценивать
вам надо будет не промежуточный результат, а самый конечный,
который у вас будет.

Сергей.

Несколько дней пробовал разобраться в быстром преобразовании фурье.
Никак не разберусь можно ли его реализовать в целочиселнной математике.
Если да, то ткните носом.

несколькими постами ранее советовали обратить внимание на библиотеку Элм-Чена, и ссылку давали... и я немножко комментировал эту библиотеку.
достаточно быстрая и с приемлемой (по крайней мере для моих задач) точностью работает.

Вы бы огласили, сколько Вам полос нужно в заявленном диапазоне.

Если не секрет, какую максимальную погрешность дает?

Тестировал у себя на AT90USB1287 билиотеки от elm-chan (http://elm-chan.org/works/akilcd/report_e.html) - Точность нужно мерять, но работает реалтайм, дает до 1024 отсчета (512 "полосок" спектра), давал частоты с звуковухи, выделял основную частоту и выводил на LCD - работает. Получилось частота дискретизации около 16кГц, соответственно эффективное окно спектра около 8кГц, всё, что выше, "отражается" и опять ползет вниз - нужен ВЧ фильтр, хотябы емкость. Точность оценить не берусь - неполучилось точно определить частоту дискретизации, но вывод практически линеен, очень похоже на то, что показывает осцил 8) Хочу на всём этом сделать тупо украшалку на усь - только вместо LCD светодиоды 8) поэтому точность мне не так важна. Важно - оно очень быстрое, при спектре в 64-128 полос совсем не чуствуется тормозов - FPS за сто уходит 8)

Мне не столько скорость важна (хотя и она не помешает), сколько точность.
Хотя бы 5%.
Видимо, придется использовать преобразование Хартли, учитывая предыдущие замечания о точности.

А что мешает попробовать и оценить точность? Можно же и внешний АЦП использовать.

Делал DTMF кодер - декодер (Метод Герцеля) все завелось на Меге