FFT на Си для AVR

[КРАМ]

[uquote="Eddy_Em",url="/forum/viewtopic.php?p=4290515#p4290515"]kote52, ну так лучше на ПК и проверять все, а когда уж заработает — переносить код на МК. Только МК, умеющий флоаты и имеющий математический сопроцессор, стоит ой как дорого. Иначе придется искать реализацию простого БПФ в целых числах. Но для спектрального анализа нет смысла БПФ применять: ведь фаза нам не нужна, соответственно, не нужны и комплексные числа. Для этого сгодится ДКП, а косинусы можно таблично вычислять.[/uquote]

Для произвольного некогерентного с отсчетами сигнала вычисление амплитуды спектральных составляющих (амплитудный спектр) требует вычисления обеих компонент - и синуса, и косинуса. Иначе амплитуду не вычислить.
Для вычисления ДПФ или БПФ флоат вообще не нужен. Ну то есть можно конечно и с ним - дело вкуса, но совершенно не обязательно. Разрядность исходного массива 10...12 с большим запасом позволяет делать Фурье в целых числах на 32-х и даже 16-ти разрядном ядре. На восьми битах тоже можно, но будет заметно медленнее. Впрочем, автор желает сделать анализ спектра для вывода на индикацию, что очевидно на несколько порядков понижает требования к скорости обработки, числу бинов и разрядности результата.
Так же не требуется никаких копроцессоров - ни для тригонометрии (элементарно используется таблица поворотных коэффициентов для БПФ или синусов/косинусов для ДПФ), ни для вычисления самой "бабочки". Действительно ускоряющим вычисления будет DSP-ядро в архитектуре, что означает либо полноценную WLIV, либо ее элементы, как это сделано в dsPIC33.
Ну и не нужно искать ничего готового, если автор желает научиться это делать. Сложного там ничего нет. Сначала для понимания физики процесса нужно написать ДПФ на небольшое количество бинов, а потом будет сильно понятнее что такое БПФ.

[uquote="С.Н.",url="/forum/viewtopic.php?p=4290519#p4290519"]само по себе ДПФ нужно лишь как обучалка[/uquote]
Отнюдь. Зависит от задачи. Если нужно расфильтровать пару десятков бинов с относительно узкой полосой (анализируемый сигнал узкополосен), то БПФ там даром не нужен.

[YS]

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

2. ДПФ это всего лишь набор скалярных произведений сигнала на ряд гармонических функций. Почитайте про скалярное произведение функций, и многое станет понятно.

3. Хорошая литература по ДПФ и БПФ

Вот тут совершенно шикарно и про ДПФ, и про БПФ
https://www.robots.ox.ac.uk/~sjrob/Teaching/SP/l7.pdf

Тоже хорошая книжка по теме
http://www.dspguide.com/ch8.htm

[kote52]

[uquote="С.Н.",url="/forum/viewtopic.php?p=4290512#p4290512"]прошу прощения - память моя подвела (этой темой 17 лет не занимался плотно), 1/1024 (исходя из N=1024) должно быть под синусом и косинусом.[/uquote]
Что то запутался, т. е. код был верным? И по поводу одной выборки что скажете?

[КРАМ]

[uquote="kote52",url="/forum/viewtopic.php?p=4290535#p4290535"]по поводу одной выборки что скажете?[/uquote]
Какой еще одной выборки?
Длина исходного массива во времени даст полосу фильтра (обратна ей) при прямоугольном окне анализа и несколько шире при окнах с подавлением боковых лепестков (Хэмминга, Блэкмана и других). Про частоту дискретизации вам уже сказали, но нужно учесть, что порядок антиалиасингового фильтра на входе АЦП прямо связан с расстоянием от сигнала до второй зоны Найквиста (половины частоты дискретизации).
То есть количество отсчетов будет величиной вычисляемой и никак не может быть равно единице.

[ARV]

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

[КРАМ]

[uquote="ARV",url="/forum/viewtopic.php?p=4290713#p4290713"]об одной полосе[/uquote]
Не думаю. Речь шла о выборке, а не о бине. А вот желание оставить одну выборку для вычисления одного бина говорит о том, что человек:
1. Не понимает как вычисляют число отсчетов.
2. Не понял, что количество амплитудных спектров на выходе равно половине от числа отсчетов.

[kote52]

[uquote="КРАМ",url="/forum/viewtopic.php?p=4290714#p4290714"][uquote="ARV",url="/forum/viewtopic.php?p=4290713#p4290713"]об одной полосе[/uquote]
Речь шла о выборке, а не о бине.
1. Не понимает как вычисляют число отсчетов.
2. Не понял, что количество амплитудных спектров на выходе равно половине от числа отсчетов.[/uquote]
Мужики не обижайтесь, я много прочитал и пока винегрет в моей голове, если что то где то назвал не своим именем! А где то перечитал форум и там тоже люди не правильно изъясняются!
1.возможно не понимаю, в своём первом сообщение в этой теме на 8 странице я изложил как хотел бы настроить мк, отсюда и плясал бы. Поправьте меня если я не понял, 1 бин это к примеру 1024, кратно 2^n преобразования ацп.
2.второе узнал от вас здесь

[КРАМ]

Бин - это один фильтр, один частотный отсчет. Для получения одного бина в ДПФ нужно корректно полученый входной массив умножить на синус, проинтегрировать и нормировать к числу входных отсчетов, получив Имеджинери компоненту, а так же на косинус с теми же действиями, получив реал компоненту. Корень квадратный из суммы компонент даст модуль (амплитуду) сигнала в фильтре, ну а арктангенс отношения мнимой к действительной с отрицательным знаком даст фазу относительно базиса - тех самых синуса и косинуса на которые умножали входной массив.
Размер массива во временной области, как я уже сказал, определит ширину фильтра в частотной области, а частота дискретизации должна удовлетворять теорему отсчетов.
То есть произведение частоты дискретизации и длины входного массива во времени даст размер массива в количестве отсчетов. Сиречь, занимаемый этим массивом объем памяти.

[С.Н.]

[uquote="КРАМ",url="/forum/viewtopic.php?p=4290809#p4290809"]Бин - это один фильтр, один частотный отсчет.[/uquote]
Интересный термин "Бин". Ранее не встречал. Совсем отстал от терминологии новой. Хотя пока с Вуза не ушел, занимался параметрическими методами спектрального оценивания и за эволюцией терминов Фурьятины не следил.

Добавлено after 25 minutes 45 seconds:
[uquote="kote52",url="/forum/viewtopic.php?p=4290535#p4290535"][uquote="С.Н.",url="/forum/viewtopic.php?p=4290512#p4290512"]прошу прощения - память моя подвела (этой темой 17 лет не занимался плотно), 1/1024 (исходя из N=1024) должно быть под синусом и косинусом.[/uquote]
Что то запутался, т. е. код был верным? И по поводу одной выборки что скажете?[/uquote]
Код почти правильный. Мое первое утверждение пока осталось - массивы реальной и мнимой части СПМ следует изначально обнулить.
И вторую часть СПМ (k>=N/2) следует просто скопировать из первой и не считать зря. Кстати вспомнил откуда симметрия. Это ТФКП (теория функции комплексных переменных). Поскольку исходные данные для преобразования Фурье. были вещественные, то реальная часть СПМ есть функция четная относительно 0 частот, а мнимая нечетная. А ноль частоты ДПФ это, как не парадоксально, это k=0 и k=1024 при Вашей длины выборки 1024.
Real[1024-k]=Real[k]
Im[1024-k]=(-1)*im[k]
Извините, если мозги терминами зря забиваю. Вы скажите и я больше не буду.

[КРАМ]

[uquote="С.Н.",url="/forum/viewtopic.php?p=4290904#p4290904"]Интересный термин "Бин".[/uquote]
bin - бункер. Термин подразумевает полосу, а не точку в выходном наборе ДПФ/БПФ.

[Jurabay]

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

[КРАМ]

И что мы получим на выходе компаратора?

[MLX90640]

Прикольно! Это новое слово в ЦОС! Плиз, расскажите всем о своем открытии, это надо продвигать в массы

[Jurabay]

Естественно, на выходе компаратора мы получим ряд нулей и единиц. Но вся частотная информация сохранится, анализируем.
Кто помнит, был такой определитель номера советского стандарта, так вот, там на входе стоял компаратор 554СА3!

[MLX90640]

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

[Jurabay]

Вот вырезка из программы на CodeVisionAVR определителя номера стандарта CLIP FSK:

while(!Terminated)
{
#asm("sleep") //ждем прерывание от таймера
if(ACSR&(1<<ACO))//выход компаратора
x = 1;
else
x=-1;
//========демодуляция=========
z4 = z3;
z3 = z2;
z2 = z1;
z1 = x;
d = x*z4;
//========фильтрация==========
y = DigFil(d);

if(y==-1)ZeroCount++;
else ZeroCount=0;

if(ZeroCount==100)
Marker=1;

if(Marker==1 && y==1)//принят стартовый бит
.
.
.
//-------- скользящее среднее -------------------------------------
inline signed char DigFil(signed char invar)
{
static signed char z1=0,z2=0,z3=0,z4=0,z5=0;

z5=z4;
z4=z3;
z3=z2;
z2=z1;
z1=invar;

return csign(z1+z2+z3+z4+z5);
}

Добавлено after 13 minutes 51 second:
Что значит определить частоту? Это значит сказать что амплитуда этой частоты (или Бин в БПФ, что тоже самое) превышает какой то порог по сравнению с другими. Этот порог все равно будете определять в попугаях.

[КРАМ]

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

[Jurabay]

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

А аналоговый компаратор - это 2-х разрядный АЦП, это так, кому интересно.

[КРАМ]

[uquote="Jurabay",url="/forum/viewtopic.php?p=4330557#p4330557"]Если проводить БПФ с реальным сигналом, ни одного бина с нулевой амплитудой вы не получите[/uquote]
Это чушь. Вы просто ничего не понимаете в преобразовании Фурье. Все зависит от разрядности и реального входного спектра.
[uquote="Jurabay",url="/forum/viewtopic.php?p=4330557#p4330557"]придется все равно по какому то пороговому значению.[/uquote] Не придется. Входная разрядность и будет естественным ограничителем. Кроме того, в вашем случае выходные значения будут однобитными.
[uquote="Jurabay",url="/forum/viewtopic.php?p=4330557#p4330557"]А аналоговый компаратор - это 2-х разрядный АЦП[/uquote]
Даладна!!!! И где же вы там второй разряд обнаружили? Для двух разрядов нужно две сигнальных линии и на выходе получим ЧЕТЫРЕ возможных значения. Ну или одну serial, которая уже любое количество разрядов осилит. Компаратор сам по себе - ни разу не сигма-дельта модулятор, есличо.
Однобитный параллельный АЦП - это 6 дБ динамического диапазона. Для детектирования двухчастотного и равноамплитудного сигнала в отсутствии сравнимых с ним помех достаточно. Сделать нормальную фильтрацию общего применения - нет.

[Jurabay]

Хорошо, согласен: компаратор - одноразрядный АЦП.

А для тех, кто на бронепоезде, еще фрагмент программы на AVR. Выделяем ответ АТС с телефонной линии, 500Гц.
Сигнал после компаратора, есть и порог: переменная Limit.

#define BMM 1024 //Big Magic Multiplier для выхода в область целых чисел
#define Limit 50 //порог срабатывания

while(1)//вечный цикл
{
#asm("sleep")//засыпаем и
//ждем прерывание от таймера
PORTB.0=1;//выход на осциллограф для контроля времени
if(ACSR&(1<<ACO))//сигнал с компаратора
x=BMM;
else
x=-BMM;

//--- цифровой фильтр --------
y = x+a1*z1-a2*z2;
z2 = z1;
z1 = y>>10;
//----------------------------

//--- фильтр нижних частот ---
y=DigFil(abs(z1));


if(y>Limit)//если больше порога - есть сигнал!
PORTB.1=1;//зажечь светодиод
else
PORTB.1=0;//погасить светодиод

PORTB.0=0;//выход на осциллограф для контроля
}

Добавлено after 16 minutes 50 seconds:
[uquote="КРАМ"]
Это чушь. Вы просто ничего не понимаете в преобразовании Фурье. Все зависит от разрядности и реального входного спектра.
[/uquote]
Вот почему я не люблю заходить на русскоязычные форумы, не разобравшись, начинают ярлыки вешать и заставляют защищаться по типу:
"Ты сам дурак".