Jump to content

    

Корреляция методом умножения в частотной области

Здравствуйте. 

Направьте в нужное русло.

Есть записанный сигнал  из 251 точек

Есть непрерывный поток отсчетов с той же дискретизацией.

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

1 записаный сигнал в обратный порядок

2 дополнение до 512 нулями

3 преобразование записанного сигнала ДПФ

в цикле

4 накапливаю 261 отсчет входящего сигнала

5 дополняю нулями до 512

6 преобразую ДПФ

7 умножаю 2 сигнала

8 результат в ОДПФ

9 сумма дельт отсчетов результата.

Получаю результат приведенный на графике.

И вроде бы что то похоже на правду, но не совсем не похоже на корреляцию.

 

На втором рисунке сильная помеха которая по идее не должна коррелировать.

Снимок экрана 2019-10-11 10-26-59.png

Снимок экрана 2019-10-11 10-28-43.png

Share this post


Link to post
Share on other sites

а вы двигаетесь окном по входному сигналу по одному отсчёту или прыгаете по 261?

Share this post


Link to post
Share on other sites

Так все-таки какая длина сигнала, 251 или 261 ?

А зачем вы используете ДПФ ? Почему бы сразу не находить корреляцию двух массивов - искомого сигнала и текущего окна из 261 (251 ?) точки. Окно надо двигать на один отсчет при его появлении и считать корреляцию также каждый новый отсчет. ИМХО.

Edited by MSP430F

Share this post


Link to post
Share on other sites
5 minutes ago, Lmx2315 said:

а вы двигаетесь окном по входному сигналу по одному отсчёту или прыгаете по 261?

прыгаю по 261

Share this post


Link to post
Share on other sites
2 минуты назад, VladimirG сказал:

прыгаю по 261

так у вас мало шансов целиком поймать ваш сигнал в окно, очень должно повезти, вы же я так понял не cos-нус ловите. Вам надо либо БПФ увеличивать и большим окном ловить, либо смещать окно по сэмплу.

Share this post


Link to post
Share on other sites

нужно будет 512 fft размером по 512 (261 + нули) для скольжения (прижкам) по тактам чтобы найти. лучше возьмите фильтр 261 порядка и гоните на него входной поток.

Share this post


Link to post
Share on other sites
25 minutes ago, MSP430F said:

Так все-таки какая длина сигнала, 251 или 261 ?

А зачем вы используете ДПФ ? Почему бы сразу не находить корреляцию двух массивов - искомого сигнала и текущего окна из 261 (251 ?) точки. Окно надо двигать на один отсчет при его появлении и считать корреляцию также каждый новый отсчет. ИМХО.

 

Длинна искомого 251.

261 я получаю по формуле 512 - 251. Откладывал этот вопрос на длительное время, и не могу сходу найти литературу из которой  я это взял.

А эффективность вычисления, я могу ошибаться но в том же источнике было сказано, что умножение в частотной быстрее свертки.

Для fft я использую функцию fftw_plan_dft_1d(N, corr_in, corr_out, FFTW_FORWARD, FFTW_ESTIMATE) из библиотеки fftw3

Share this post


Link to post
Share on other sites

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

 Последовательность отсчетов входного сигналов дополнить нулями так, чтобы длины последовательностей  стали  одинаковыми  и  не  меньшими,  чем

x1 + x2 -1 тогда в центральной части вы получите валидный кусок, который вас интересует а вообще это тема "Дискретная фильтрация с помощью ДПФ"

в вашем случае надо дополнить до ближайшей степени 2.

Share this post


Link to post
Share on other sites

Странно как-то. Если размер искомой последовательности 251 отсчет, то ее надо искать в последовательности такого же размера. Вы же не будете искать подобный треугольник среди квадратов ? В таком случае вам придется дополнить массив всего лишь пятью нулями, чтобы получить массив из 256 элементов, как раз для БПФ. И все-таки, я бы не стал связываться с БПФ вообще. Есть совершенно простая формула для вычисления коэффициента корреляции (Пирсона) даже в википедии.

См. Коэффициент корреляции

Edited by MSP430F

Share this post


Link to post
Share on other sites

для коротких (256) последовательностей выигрыша от FFT туда/обратно не особо много по сравнению с прямым вычислением корреляции, 

напрямую надо 256 МАСов на отсчёт, а для ффт, по ~100 тактов на отсчёт туда и столько же обратно.

 

Share this post


Link to post
Share on other sites

Приветствую!

20 minutes ago, _pv said:

для коротких (256) последовательностей выигрыша от FFT туда/обратно не особо много по сравнению с прямым вычислением корреляции

Выигрыш будет если сразу искать последовательность в длинном буфере - например при  размере входных данных/FFT 8192 вы за цикл FFT/IFFT сразу найдете корреляцию и положение сигнала для 8192 - 2*251 позиций.

Удачи! Rob  

Share this post


Link to post
Share on other sites
58 minutes ago, RobFPGA said:

Выигрыш будет если сразу искать последовательность в длинном буфере

длина "образца" 251 отсчётов и не меняется . то есть для просто свёртки всегда надо 251 МАС на каждый отсчёт.

а у FFT, при увеличении длины, количество тактов на отчёт растёт (N*logN / N = logN), то есть увеличение буфера сделает только хуже, не?

вот таблица для какого-то арма вроде:

N        FFT cycles    cycles/sample
64        4882        76
128        11153        87
256        25700        100
512        58436        114
1024        132145        129
2048        294364        144
4096        666376        163
8192        1546983        189
16384        3605714        220
32768        8115185        248
65536        17498392    267
131072        38844895    296
262144        88794243    339
 

FFT туда обратно для N=512, надо 58k*2 = 116к тактов, для 8192 - 3M тактов.

пусть МАС мы делаем за один такт, тогда для просто свёртки с образцом длиной 251 при длине "буфера" 512 надо 512*251 = 128к тактов, а для 8192 - 8192*251 - уже 2М тактов.

а если МАС не за один такт, да ещё и в память за данными слазить надо, не только лишь все процессоры умеют это делать параллельно с АЛУ, то ФФТ может и быстрее будет, но вот зависимость от длины всё равно останется такой же.

то есть при фиксированной длине "образца", увеличение длины ФФТ не поможет.

Share this post


Link to post
Share on other sites

Приветствую!

33 minutes ago, _pv said:

... то есть при фиксированной длине "образца", увеличение длины ФФТ не поможет.

Мерить удава в попугаях всегда удобно -  можно выбрать сорт попугаев :biggrin: 

Из вашей таблицы   видим что 8K FFT занимает аж  1546983 тактов  -   при этом мы можем получить  8K-2*261= 7670 отсчетов кореляции.   Сколько нужно тактов, чтобы посчитать это же  простым MAC?  7670*251 =  2001870 что приблизительно в 1.3 раза  больше чем при варианте с FFT. И это если использовать для MAC очень маленьких попугаев - без учета того что их еще надо из клетки памяти доставать.  :acute: То есть реально MAC будет как минимум в ~2.6 1.3 раза медленнее. :unknw:

Удачи! Rob. 

P.S. забыл  про IFFT.

Share this post


Link to post
Share on other sites
1 hour ago, RobFPGA said:

Мерить удава в попугаях всегда удобно -  можно выбрать сорт попугаев :biggrin: 

этот пример не про абсолютные величины попугаев, а про то, что с увеличением длины для FFT становится только хуже, потому что длина "образца" не меняется и всегда остаётся равна 251.

возмите максимальную длину ФФТ 262144 и там уже будет 339 тактов на отсчёт, вместо 251 "тактов" на отсчёт для просто свёртки.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now